基于C语言的小型模拟操作系统标准设计.doc

本科生毕业设计（创作）

题　　目 基于C语言小型模拟操作系统设计
（只包含进程管理和存放管理）　
姓　　名　　 王在平　　　　　　　　
学　　号　　 10624231　　　　　
院 　系　　 计算机系　　　　　　　
专　　业　　 计算机科学和技术　　　　　
指导老师　 杨 瑞 　　　　　　

年 6 月
教务处制
本科生毕业设计（论文、创作）申明

本人郑重申明：所呈交毕业设计，是本人在指导老师指导下，进行研究工作所取得结果。除文中已经注明引用内容外，本设计研究结果不包含任何她人创作、已公开发表或没有公开发表作品内容。对本论文所包含研究工作做出贡献其它个人和集体，均已在文中以明确方法标明。本设计创作申明法律责任由本人负担。

作者署名：

年 月 日

本人申明：该毕业设计是本人指导学生完成研究结果，已经审阅过毕业设计全部内容，确保题目、关键词、摘要部分中英文内容一致性和正确性，并经过一定检测手段确保毕业设计未发觉违反学术道德诚信不端行为。

指导老师署名：

年 月 日

基于C语言小型模拟操作系统设计
（只包含进程管理和存放管理）
摘 要
本设计采取Visual C++开发工具在Windows环境下设计一个模拟操作系统。依据操作系统理论知识学习实现了进程管理和存放管理。进程管理部分关键实现了进程创建和撤销、进程运行。进程创建和撤销关键应用指针和链表知识，进程运行方法采取是时间片轮转调度算法，经过输入相关指令能够看到多个进程在时间片调度算法下由就绪态到运行态再到完成态全过程。存放管理部分关键实现了进程内存空间分配和回收。存放分配采取基础分页存放管理方法，经过数组来模拟主存空间。创建进程同时完成对用户提出内存块数分配，并显示在屏幕上。内存回收模块作用是将处于指针队列控制块移出队列并释放进程所占用内存。
本人在设计此系统过程中做了以下工作：(1) 仔细阅读了操作系统进程管理和存放器管理部分内容，并具体分析了其中原理。(2) 学习了C语言中数组、指针等相关知识，并对相关算法做了仔细阅读和分析。(3) 熟悉了软件工程开发基础方法、模型、步骤等，确定了系统框架。(4) 使用C语言编写了模拟操作系统。
经过这次模拟操作系统设计，加深了自己对操作系统实现思绪了解，直观了解了操作系统相关原理，提升了自己编写程序和调试程序能力，为以后深入学习提供了一个良好开端。

关键词：操作系统，进程管理，存放管理，分页，时间片

Small simulation operating system design based on C language
(only includes process management and storage management)
Abstract
This design uses the Visual C++ development tools in Windows environment design a simulation operating system. According to the operating system to study the theory knowledge to realize the process management and storage management. Process management part is mainly to achieve the process of creation and cancellation, the operation of the process. Process creation and revoke the main application of pointer and linked list, process the operation mode of using the time slice rotation scheduling algorithm, through input the command can see multiple processes under the time slice scheduling algorithm by the ready state to a running state and then to finish the whole course of state. Storage management part mainly realizes the process memory space allocation and recycling. Storage allocation using basic page storage management mode, through the array to simulate the main memory space.
In the design of the system in the process of doing the following work: 1, read the process management and storage management component of the operating system, and analyzes in detail the principle of 2, to learn the relevant knowledge such as arrays, Pointers in C language, and made a careful reading and analysis of relevant algorithm. 3, familiar with the basic method of the software engineering development, models, procedures, etc., determine the framework of the system. 4, using C language to write the simulation operating system.
By designing simulation operating system, deepen their understanding of operating system implementation approach, intuitive understanding of the relevant principle of the operating system, it improves the ability of writing your own program and debugging, for future further study provides a good place to start.

Key Words：Operating system, process management, memory management, paging, time slice

目 录
1 绪 论 - 1 -
1.1背景 - 1 -
1.3设计目标 - 1 -
1.4 意义 - 1 -
1.5论文组织安排 - 1 -
2 系统分析和设计 - 3 -
2.1 进程管理要求 - 3 -
2.1.1 进程状态 - 3 -
2.1.2 进程控制块 - 3 -
2.1.3 进程创建 - 3 -
2.1.4 进程调度 - 4 -
2.1.5进程撤销 - 4 -
2.2 存放管理要求 - 4 -
2.2.1 内存分配 - 4 -
2.2.2 回收内存 - 5 -
2.3 总体设计要求 - 5 -
3 系统具体设计 - 6 -
3.1 全局变量 - 6 -
3.2 内存初始化 - 6 -
3.2.1 内存定义 - 6 -
3.2.2 关键代码 - 7 -
3.2.3 测试结果 - 8 -
3.3 创建进程 - 8 -
3.3.1 进程结构PCB描述 - 8 -
3.3.2 进程队列描述 - 8 -
3.3.3步骤图 - 9 -
3.3.4 关键代码 - 11 -
3.3.5 测试结果 - 12 -
3.4 查看内存 - 13 -
3.4.1 页表 - 13 -
3.4.2 步骤图 - 13 -
3.4.3关键代码 - 15 -
3.4.4 测试结果 - 16 -
3.5 运行进程 - 16 -
3.5.1 时间片轮转调度算法 - 16 -
3.5.2 算法工作安排 - 16 -
3.5.3 步骤图 - 18 -
3.5.4 关键代码 - 21 -
3.5.5 测试结果 - 23 -
3.6 撤销进程 - 23 -
3.6.1 结束进程控制块 - 23 -
3.6.2 回收内存数组 - 24 -
3.6.3 步骤图 - 24 -
3.6.4 关键代码 - 26 -
3.6.5 测试结果 - 27 -
4 问题和总结 - 28 -
附录 - 29 -
参考文件 - 37 -
致谢 - 38 -

1 绪 论
1.1背景
操作系统（OS,Operating System）是计算机系统关键和灵魂，是计算机系统必不可少组成部分，任何其它软件全部必需在操作系统支持下才能运行。
操作系统功效强大、代码量大，阅读了解实际系统对于通常学习者来说几乎是不可能，所以为了愈加好地了解操作系统运行机制，依据操作系统原理和实际系统组织结构和部分具体实现，设计一个模拟操作系统来帮助我们愈加好地掌握操作系统原理是很必需。
1.2 设计目标
在多道程运行环境下，用户能够经过模拟操作系统交互界面创建进程并根据基础分页存放管理方法分配必需内存空间，根据时间片轮转算法选择一个或多个进程在处理机上运行。当程序实施完成时，系统能够撤销进程并收回它所占用内存空间。模拟操作系统不包含具体硬件，经过设计合理数据结构来表示硬件资源，并经过输出部分提醒信息表示系统目前运行状态。
经过设计模拟操作系统，加深学生对操作系统实现思绪了解，提升综合利用所学知识能力，和培养系统设计能力，为以后更深入设计和分析系统打下坚实基础。
1.3 意义
经过在平时原有认识基础上又深入系统学习了操作系统相关知识，强化了自己认知。经过本模拟操作系统设计使自己愈加直观了解了操作系统相关知识，大大提升了自己分析问题和处理问题能力，为以后深入学习起到了很好铺垫。
1.4 论文组织安排
本文安排以下：
第一章 绪论。介绍课题背景、设计目标和意义。
第二章 系统分析和设计。介绍进程管理存放管理设计要求和总设计框架。
第三章 系统具体设计。介绍各个代码块具体设计步骤。
第四章 问题和总结。总结自己设计过程和设计中碰到关键问题及处理方法。

2 系统分析和设计
2.1 进程管理要求
2.1.1 进程状态
因为本系统采取是基于时间片调度算法模拟进程运行过程，所以设定进程基础状态为就绪运行、运行状态和完成状态。图2-1

运行
运行完
进入
时间片用完
进程调度
释放
就绪
完成

图2-1 进程基于时间片轮转算法基础状态

2.1.2 进程控制块
进程控制块PCB(Process Control Block)是进程最关键数据结构，它用于描述和控制进程，是进程存在唯一标识。进程控制块内容有进程标示符、处理机状态、进程调度信息、进程控制信息。
本系统采取链式方法来组织进程控制块。把含有同一状态进程控制块链接成一个队列，这么就形成了就绪状态、运行状态和完成状态。
2.1.3 进程创建
一旦操作系统接收到用户输入创建命令，便调用进程创建函数按下列方法为用户创建一个新进程。
(1) 申请一个空白PCB。
(2) 为进程分配内存。
(3) 初始化PCB中内容。
(4) 将PCB插入到就绪队列，等候调度。
2.1.4 进程调度
进程调度采取时间片轮转调度算法，时间片大小由用户自己定义。
进程调度函数关键完成下列工作：
(1) 从就绪队列中选择队首进程插入到运行队列。
(2) 修改PCB中信息。
(3) 假如进程运行完便插入到完成队列，从就绪队列取下一进程到运行队列。
(4) 不然将这一进程插入到就绪队列队尾，等候下一次调度。

2.1.5进程撤销
进程撤销函数关键完成下列工作：
(1) 将进程控制块PCB移出队列。
(2) 释放进程所占内存。
(3) 将撤销信息显示在屏幕上。
2.2 存放管理要求
2.2.1 内存分配
因为本系统采取内存分配策略是基础分页存放管理方法，又称为离散分配方法。所以有必需对内存进行分块和初始化。采取二维数组模拟基础分页存放。
内存分配关键完成下列工作：
(1) 初始化内存数组，将其分割成一组不连续块。
(2) 为进程分配用户提出请求页数。
(3) 将分配页号和块号显示在屏幕上。
2.2.2 回收内存
当进程运行完释放内存时，系统依据用户要求从对应链表上摘下，然后释放内存数组数据，此时可能出现两种情况。
(1) 回收PCB在就绪队列。
(2) 回收PCB在完成队列。
2.3 总体设计要求
本系统包含以下代码块：
(1) 主函数模块。调用初始化代码块和菜单代码块。
(2) 初始化代码块。初始化内存数组。
(3) 菜单代码块。调用创建进程、查看内存、运行进程、撤销进程代码块。
(4) 创建进程代码块。创建并初始化进程控制块和分配内存空间。
(5) 查看内存代码块。查看内存分配情况。
(6) 运行进程代码块。采取时间片轮转调度算法调度进程运行。
(7) 结束进程代码块。结束进程并释放其占用内存空间。
函数之间调用关系图2-3所表示。

创建进程
查看内存
主函数
初始化
菜 单
撤销进程
运行进程

图 2-3 总体设计模块

3 系统具体设计
3.1 全局变量
系统代码中定义部分全局变量
#define N 100 // 共有100个内存块
int process[N][N+1]; // 存放每个进程页表
int block[N]; // 内存块状态标志数组，0：空闲，1：使用
int blockCount; // 统计目前内存剩下空间
int processCount; // 统计目前进程数
bool flag = true;
int M;
typedef struct node{
int pid;
int round;
int needtime;
int cputime;
int count;
int state;
struct node *next;
}PCB;
PCB *finish,*ready,*tail,*run;
3.2 内存初始化
3.2.1 内存定义
定义内存块共有N个，初始化后内存空间应该有一部分已经被使用，这能够用系统提供随机数函数rand()完成。
假定内存空间已经按块划分，目标程序无需关心内存块大小等底层细节，只需按算法对内存块进行分配即可。采取二维数组3-2-1来模拟进程使用内存块情况。用一个内存状态标志数组来统计内存占用情况。

0
1
2

N-1

0 1 2 N-1 N
...
进程号
进程块数
块占用标志

图 3-2-1 内存二维数组示意图
3.2.2 关键代码
void init()
{
int i, j;
for (i=0; i<N; i++)
block[i] = 0;
for (i=0; i<80; i++)
block[rand()%(N-1)] = 1;
blockCount = 0;
for (i=0; i<N; i++)
if (block[i] == 0)
blockCount++;
for (i=0; i<N; i++){
process[i][0] = 0;
for (j=1; j<N; j++)
process[i][j] = -1;
}
processCount = 0;
printf("初始化结果以下：");
output();
flag = false;
}
3.2.3 测试结果

图 3-2-2

3.3 创建进程
3.3.1 进程结构PCB描述
每个进程用一个进程控制块(PCB)表示。进程控制块包含以下信息：进程名、轮数、需要运行时间、已用CPU时间、进程状态、指针。
typedef struct node
{
int pid;
int round;
int needtime;
int cputime;
int count;
int state;
struct node *next;
}PCB;
3.3.2 进程队列描述
进程队列包含就绪队列、运行队列和完成队列，指向进程队列指针有就绪头队列指针ready、运行队列头指针run、完成队列头指针finish和队列尾指针tail。图3-3-2把含有统一状态PCB用链接字链接成一个队列。现做以下定义。
PCB *finish,*ready,*tail,*run;

PCB1
PCB2
PCB3
PCB6
PCB7
PCB9
PCB8
PCB5
PCB4
...
4
3
0
8
7
9
0
1
运行指针
就绪队列指针
完成队列指针

图 3-3-2 PCB链接队列示意图
3.3.3步骤图

输入进程数：M
j=0
J<M
输入进程号：na运行时间：time 页面数：pages
p=(PCB *)malloc(sizeof(PCB));

ready!=NULL
tail->next =q;tail=tail->next;
p->next=ready; ready=p; tail=ready;
p->pid=na;p->cputime=0; p->needtime=time;
p->state='W'; p->round =0;p->count =0;
blockCount -= pages;process[na][0] = pages;
i=1
i<=pages
process[na][i] = k;block[k] = 1;k++;
i++;
false
truee
true
false
j++;
true
false
开始
结束

图 3-3-3 创建进程步骤图
3.3.4 关键代码
bool createProcess()
{
int na;
int pages, k = 0;
PCB *p;
int time;
//char na[10];
ready=NULL;
finish=NULL;
run=NULL;
printf(" 输入进程数：");
scanf("%d",&M);
int a[N];
for(int j=0;j<M;j++)
{
loop:printf("请输入进程号(小于%d)和运行时间和所需页面数：", N);
scanf("%d%d%d", &na, &time,&pages);
a[j]=na;
for(int k=0;k<j;k++)
{
if(a[k]==a[k+1])
{
printf("进程号输入反复，请重新输入！\n\n");
goto loop;
}
}

if (na > 99)
{
printf("错误！进程号过大！\n");
goto loop;
}
if (pages > blockCount)
{
printf("错误！内存分配失败，没有你要求进程块数！\n");
return false;
}
blockCount -= pages;
process[na][0] = pages;
for (int i=1; i<=pages; i++)
{
while (block[k]==1 && k<100)
k++;
process[na][i] = k;
block[k] = 1;
k++;
}

p=(PCB *)malloc(sizeof(PCB));
//strcpy(p->pid,pid);
p->pid=na;
p->cputime=0;
p->needtime=time;
p->state='W';
p->round =0;
p->count =0;
if(ready!=NULL)
insert(p);
else
{
p->next=ready;
ready=p;
tail=ready;
}
processCount++;
printf("创建新进程成功！\n\n");
}
return true;
}
3.3.5 测试结果

图 3-3-5
3.4 查看内存
3.4.1 页表
在分页系统中，许可将进程各个页离散存放在内存不一样物理块中，但系统应能确保进程正确运行，即能在内存中找到每个页面对应物理块。为此，系统又为每个进程建立了一张页面映像表，简称页表。在进程地址空间内全部页(0~n)，依次在页表中有一页表项，其中统计了对应页在内存中对应物理块号，见图3-4-1。在配置了页表后，进程实施时经过查找页表，即可找到每页在内存中物理块号。
内存输出函数output()关键功效是输出内存初始化下内存占用信息和在系统实施撤销进程函数endProcess()后输出内存占用情况。

0
1
2
3
4
5
2
3
6
8
9
11
...
...
页号
块号
页表

图3-4-1 页表
3.4.2 步骤图

开始
processCount > 0
process[id][0] > 0
j<=process[id][0];
输出 页号：count 块号：process[id][j]
count++；
printf("|------------|\n");
printf("| 页号| 块号|\n");
printf("|------------|\n");
结束
j=1,count=0;
j++
false
true
true
false
输入要查看进程：id

输出：内存无进程！
false

图 3-4-2 查看内存步骤图
3.4.3关键代码
void output()
{
printf("\n内存总量：%d 块, 已用空间：%d 块, 剩下空间：%d 块, 进程总数：%d 个\n", N, N-blockCount, blockCount, processCount);
if (flag && blockCount < N)
{
printf("已使用内存块(%d)：\n", N-blockCount);
for (int k=0,count=0; k<N; k++)
{
if (block[k] == 1)
printf("%2d ", k, ++count);
if (count == 10)
{
putchar('\n');
count = 0;
}
}
putchar('\n');
}
if (processCount > 0)
{
int id;
printf("请输入要查看进程号: ");
scanf("%d",&id);
printf("内存具体使用情况以下：\n");
if (process[id][0] > 0)
{
printf("**************\n");
printf("进程号: %d \n", id);
printf("|------------|\n");
printf("| 页号| 块号|\n");
printf("|------------|\n");
for (int j=1,count=0; j<=process[id][0]; j++)
{
printf("| %2d | %2d |\n",count,process[id][j],count++);
printf("|------------|\n");
}
printf("***输出结束***\n");
}
}
else
printf("目前内存无进程！\n");
putchar('\n');
}
3.4.4 测试结果

图 3-4-4

3.5 运行进程
3.5.1 时间片轮转调度算法
全部就绪进程按 FCFS排成一个队列，总是把处理机分配给队首进程，各进程占用CPU时间片相同。立即CPU处理时间划分成一个个相同时间片，就绪队列诸进程轮番运行一个时间片。当一个时间片结束时，假如运行进程用完它时间片后还未完成，就强迫运行机制进程让出CPU，就把它送回到就绪队列末尾，等候下一次调度。同时，进程调度又去选择就绪队列中队首进程，分配给它一时间片，以投入运行。直至全部进程运行完成。
3.5.2 算法工作安排
(1) 用户能够自行输入进程数量，每一个进程由进程控制块（ PCB）表示，多种队列均采取链表数据结构。
(2) 根据进程输入前后次序排成一个队列。再设一个队首指针指向第一个抵达进程首址。
(3) 实施处理机调度时，开始选择队首第一个进程运行。另外，再设一个目前运行进程指针，指向目前正在运行进程。
(4) 在要求时间片内进程是依据先来先服务方法配列，每个进程只运行时间片大小时间然后转到下一个进程运行，直到全部进程运行完为止。
3.5.3 步骤图
ready!= NULL
开始
run=ready; ready=ready->next;tail->next =run;run->state='R';
调用输出函数：prt();
run != NULL
run->cputime=run->cputime+timeSlice;
run->needtime=run->needtime-timeSlice;
run->round+=timeSlice;run->count++;
run != tail
tail->next = ready;
ready = NULL;
run->state = 'F'; run = NULL;
run = NULL;
ready!= NULL
run=ready;run->state='R';ready=ready->next;
run->state = 'W';tail = run;
run = ready; run -> state = 'R';
ready = ready -> next;
调用输出函数：prt();
结束
run->needtime<= 0
run->needtime = 0;run->next = finish;
finish = run;
false
true
false
false
true
true
输入时间片：timeSlice

图 3-5-3（a）进程运行步骤图
开始
run!=NULL
q=ready;
q!=NULL&&q!=run
q->next== run
q = q->next;
q=finish;
q!=NULL
q=q->next;
结束
输出运行队列时间片信息
输出就绪队列时间片信息
输出完成队列时间片信息
true
false
true
false
true
false

图 3-5-3（b）prt输出函数步骤图
3.5.4 关键代码
bool Roundrun()
{
int timeSlice;
if(processCount<1)
{
printf("目前途序无进程，请重新输入!\n\n");
return 0;
}
printf(" 请输入时间片大小: ");
scanf("%d",&timeSlice);
printf(" 时间片轮转法输出信息\n");
printf("*****************************************************************************\n");
run=ready;
ready=ready->next;
tail->next =run;
run->state='R';
prt();

while(run != NULL)
{
run->cputime = run->cputime + timeSlice;
run->needtime = run->needtime - timeSlice;
run->round+=timeSlice;
run->count++;
if(run->needtime <= 0)
{
run->needtime = 0;
run->next = finish;
finish = run;
if(run != tail)
{
tail->next = ready;
}
else
{
ready = NULL;
}
run->state = 'F';
run = NULL;
if(ready != NULL)
{
firstin();
}
}
else
{
if(ready != NULL)
{
run->state = 'W';
tail = run;
run = ready;
run -> state = 'R';
ready = ready -> next;
}
}
prt();
}

printf("*****************************************************************************\n");
printf(" 输出结束\n");
return true;
}
3.5.5 测试结果

图 4-5-2

3.6 撤销进程
3.6.1 结束进程控制块
当用户提出结束进程命令，系统依次用指针搜索就绪队列和完成队列，假如找到要结束进程控制块就将其删去，这里删去并不是真正从内存中把它抹掉，而是把它从链表中分离出来，只要撤销原来链接关系即可。
能够设两个指针变量p1和p2，先使p1指向第一个结点(图 3-6-1(a) )。假如删除不是第一个结点，则使p1后移指向下一个结点(p1->next赋给p1)，在此之前应将p1值赋给p2，使p2指向刚才检验过那个结点，见图 3-6-1 (b)。如此一次一次地使p1后移，直到找到所要删除结点或检验完全部链表全部找不到要删除结点为止。假如找到某一节点是要删除节点，还要区分两种情况： (1)要删除是第一个结点(p1值等于ready值，图3-6-1(a) 那样)，则应将p1->next赋给ready，见图3-6-1 (c)。这时ready指向原来第二个结点。第一个结点即使仍存在，但它已和链表脱离。(2) 假如要删除不是第一个结点，则将p1->next赋给p2->next，见图3-6-1 (d)。

1
2
3
ready
p1
(a)
NULL
1
2
3
ready
p2
p1
NULL
(b)
1
2
3
NULL
(c)
ready
p1
1
2
3
NULL
(d)
ready
p1
p2

图 3-5-1
3.6.2 回收内存数组
在模拟回收内存算法中关键采取是数组形式和部分计数变量，所以在回收内存数组中并没有真正回收内存，而是经过改变其中变量模拟回收过程。
首先找到要回收内存数组进程号，并用process[ID][0]统计所要回收页面数。然后清除process[ID][]这一行内容，同时置内存标志数组block[N]为0表示释放。最终进程计数器processCount减1，对应把剩下块计数器blockCount加上回收页面数。
3.6.3 步骤图

开始
输入结束进程号：ID
p1=ready||finish
ID!=p1->pid&&p1->next!=NULL
p2=p1; p1=p1->next;
p1=p1->next;
ID==p1->pid
p1==ready
p1==finish
ready=p1->next;
finish=p1->next;
p2->next=p1->next;
输出：已经删除进程
结束
输出：结束进程不存在
false
false
true
true
false
false