基于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)AbstractThis 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 processNN+1; / 存放每个进程页表int blockN; / 内存块状态标志数组，0：空闲，1：使用int blockCount; / 统计目前内存剩下空间int processCount; / 统计目前进程数bool flag = true;int M;typedef struct nodeint 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来模拟进程使用内存块情况。用一个内存状态标志数组来统计内存占用情况。012N-10 1 2 N-1 N.进程号进程块数块占用标志图 3-2-1 内存二维数组示意图3.2.2 关键代码void init()int i, j;for (i=0; iN; i+)blocki = 0;for (i=0; i80; i+)blockrand()%(N-1) = 1;blockCount = 0;for (i=0; iN; i+)if (blocki = 0)blockCount+;for (i=0; iN; i+)processi0 = 0;for (j=1; jN; j+)processij = -1;processCount = 0;printf(初始化结果以下：);output();flag = false;3.2.3 测试结果图 3-2-23.3 创建进程3.3.1 进程结构PCB描述每个进程用一个进程控制块(PCB)表示。进程控制块包含以下信息：进程名、轮数、需要运行时间、已用CPU时间、进程状态、指针。typedef struct nodeint 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; PCB1PCB2PCB3PCB6PCB7PCB9PCB8PCB5PCB4.43087901运行指针就绪队列指针完成队列指针图 3-3-2 PCB链接队列示意图3.3.3步骤图输入进程数：Mj=0Jnext =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;processna0 = pages;i=1i=pagesprocessnai = k;blockk = 1;k+;i+;falsetrueetruefalsej+;truefalse开始结束图 3-3-3 创建进程步骤图3.3.4 关键代码bool createProcess()int na;int pages, k = 0; PCB *p;int time;/char na10;ready=NULL;finish=NULL;run=NULL; printf( 输入进程数：); scanf(%d,&M); int aN; for(int j=0;jM;j+) loop:printf(请输入进程号(小于%d)和运行时间和所需页面数：, N);scanf(%d%d%d, &na, &time,&pages); aj=na; for(int k=0;k 99)printf(错误！进程号过大！n);goto loop;if (pages blockCount)printf(错误！内存分配失败，没有你要求进程块数！n);return false;blockCount -= pages;processna0 = pages;for (int i=1; i=pages; i+) while (blockk=1 & kpid,pid); p-pid=na;p-cputime=0; p-needtime=time; p-state=W; p-round =0;p-count =0;if(ready!=NULL) insert(p);elsep-next=ready; ready=p;tail=ready;processCount+;printf(创建新进程成功！nn);return true;3.3.5 测试结果图 3-3-53.4 查看内存3.4.1 页表在分页系统中，许可将进程各个页离散存放在内存不一样物理块中，但系统应能确保进程正确运行，即能在内存中找到每个页面对应物理块。为此，系统又为每个进程建立了一张页面映像表，简称页表。在进程地址空间内全部页(0n)，依次在页表中有一页表项，其中统计了对应页在内存中对应物理块号，见图3-4-1。在配置了页表后，进程实施时经过查找页表，即可找到每页在内存中物理块号。内存输出函数output()关键功效是输出内存初始化下内存占用信息和在系统实施撤销进程函数endProcess()后输出内存占用情况。0123452368911.页号块号页表图3-4-1 页表3.4.2 步骤图开始processCount 0processid0 0j=processid0;输出 页号：count 块号：processidjcount+；printf(|-|n);printf(| 页号| 块号|n);printf(|-|n);结束j=1,count=0;j+falsetruetruefalse输入要查看进程：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 0)int id;printf(请输入要查看进程号: );scanf(%d,&id);printf(内存具体使用情况以下：n);if (processid0 0) printf(*n); printf(进程号: %d n, id); printf(|-|n); printf(| 页号| 块号|n);printf(|-|n);for (int j=1,count=0; jnext;tail-next =run;run-state=R;调用输出函数：prt();run != NULLrun-cputime=run-cputime+timeSlice;run-needtime=run-needtime-timeSlice;run-round+=timeSlice;run-count+;run != tailtail-next = ready;ready = NULL;run-state = F; run = NULL;run = NULL;ready!= NULLrun=ready;run-state=R;ready=ready-next;run-state = W;tail = run;run = ready; run - state = R; ready = ready - next;调用输出函数：prt();结束run-needtimeneedtime = 0;run-next = finish; finish = run;falsetruefalsefalsetruetrue输入时间片：timeSlice图 3-5-3（a）进程运行步骤图开始run!=NULLq=ready;q!=NULL&q!=runq-next= runq = q-next;q=finish;q!=NULLq=q-next;结束输出运行队列时间片信息输出就绪队列时间片信息输出完成队列时间片信息truefalsetruefalsetruefalse图 3-5-3（b）prt输出函数步骤图3.5.4 关键代码bool Roundrun() int timeSlice; if(processCountnext;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 needtime = 0;run-next = finish; finish = run;if(run != tail)tail-next = ready;elseready = NULL;run-state = F;run = NULL;if(ready != NULL)firstin();elseif(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-23.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)。123readyp1(a)NULL123readyp2p1NULL(b)123NULL(c)readyp1123NULL(d)readyp1p2图 3-5-13.6.2 回收内存数组在模拟回收内存算法中关键采取是数组形式和部分计数变量，所以在回收内存数组中并没有真正回收内存，而是经过改变其中变量模拟回收过程。首先找到要回收内存数组进程号，并用processID0统计所要回收页面数。然后清除processID这一行内容，同时置内存标志数组blockN为0表示释放。最终进程计数器processCount减1，对应把剩下块计数器blockCount加上回收页面数。3.6.3 步骤图开始输入结束进程号：IDp1=ready|finishID!=p1-pid&p1-next!=NULLp2=p1; p1=p1-next;p1=p1-next;ID=p1-pidp1=readyp1=finishready=p1-next;finish=p1-next;p2-next=p1-next;输出：已经删除进程结束输出：结束进程不存在falsefalsetruetruefalsefalse