第一篇：操作系统 单处理机系统的进程调度
一.实验内容描述
1.目的
（1）了解Windows内存管理器（2）理解Windows的地址过程 2.内容
任意给出一个虚拟地址，通过WinDbg观察相关数据并找到其物理地址
二.理论分析
Windows采用页式虚拟存储管理技术管理内存，页面是硬件级别上的最小保护单位 1.Windows内存管理器
Windows的内存管理主要由Windows执行体中的虚存管理程序负责，并由环境子系统负责，并由环境子系统负责与具体API相关的一些用户态特性的实现。虚存管理程序是Windows中负责内存管理的那些子程序和数据结构的集合 内存管理器的主要任务是：
地址变换：将一个进程的虚拟地址空间转译为物理内存地址
交换：当内存不足时，将内存中的有些内容转移到磁盘上，并且以后还要再次将这些内容读回
2.Windows内存管理策略
Windows采用页式虚拟存储管理技术管理内存，页面是硬件级别上最小的保护单位。根据硬件的体系结构不同，页面尺寸被分为两种，大页面和小页面。X86系统下小页面为4KB，大页面为4MB。大页面的优点是：当引用同一页面内其他数据时，地址转移的速度会很快。不过使用大页面通常要较大的内存空间，而且必须用一个单独的保护项来映射，因此可能会造成出现错误而不引发内存访问违例的情况。通常PC机都为小页面 3.Windows虚拟地址空间布局 x86结构下的布局方式：
默认情况下，32位Windows系统中每个用户进程可以占有2GB的私有地址空间。操作系统占有另外的2GB 2GB用户的进程地址空间布局如表：
2GB的系统地址空间布局如同：
3.虚拟地址转译
地址转译是指将进程的虚拟地址空间映射到实际物理页面的过程。x86系统中地址转译过程如图：
关键数据结构如下： 页目录：每个进程都有一个页目录，它是内存管理器为了映射进程中所有的页表位置而创建的一个页面。进程也目录的地址被保存在内核进程快KPROCESS中，在x86系统上，它被映射到虚拟地址0xC0300000，当一个进程正在执行时，CPU可以通过寄存器CR3知道该进程页目录的位置。页目录由目录项（PDE）构成，每个PDE长4字节，描述了该进程中所有可能的页表的状态和位置。其格式和PTE类似。x86系统上，要描述完整的4GB虚拟地址空间，需要1024个页表。因此映射这些页表的进程页目录需包含1024个PDE，恰好占用一个页面。
页表：进程的页目录项指向页表。每个页表占用一个页面，由1024项PTE组成。一个有效的PTE大小为4字节，包含两个主域：数据所在的物理页面的页面帧编号（PNF）或者内存中一个页面的物理地址的PFN；一些描述该页面状态和保护属性的标志。
虚拟地质结构：x86系统上，一个32位虚拟地址被解释为三个单独的部分，页目录索引、页表索引和字节索引。由于页目录项有1024个，因此页目录索引为10位；一个也表中含有1024个PTE。因此页表索引也为10位，字节索引为12位，正好表示一页（4KB）内容
三.实验步骤及结果
1.查找页目录首地址
以程序WG.exe作为观测对象。
启动WinDbg到内核调试模式，运行程序WG.exe。终断目标机运行，输入命令：kd>!process
发现WG.exe进程正处于运行状态 输入命令：
在KPROCESS中名为DirectoryTableBase的域，对应值为0x9fa6000，即WG.exe进程页目录的物理地址 查看CR3寄存其中的内容，输入命令：
CR3寄存其中的值和KPROCESS中记录的页目录基址相同。这是因为在CPU切换执行任务时，其内容要更新为当前进程的页目录基址。2.地址转译过程
假设给定的虚拟地址为0x401001 输入命令：
可以看到：
PDE的虚拟地址为C0300004.PTE的虚拟地址为C0001004 最后一行信息“pfn 9e4a---DA--UWEV”表示PDE中的具体内容，9e4a是给定虚拟地址所在页表在内存中对应的物理页号，“---DA—UWEV”是标志信息，“pfn a173----A--UREV”表示PTE中的具体内容，a173是数据页装入内存的物理页号。
将数据页对应的物理页号a173加上业内索引（0x1）即可得到虚拟地址0x401001的物理地址
3.观察系统页表
给定观测虚拟地址为0x80001001 输入命令：
当前正在执行的进程是：WG.exe 输入命令：
得到PDE为C0300800，其对应的物理页号为3b 继续让目标机运行，启动A.exe，然后中断目标机运行。输入命令：
当前正在执行的进程为A.exe 输入命令：
PDE信息和对应的物理页号与前面观测到的相同
四.结论
1.数据页对应的物理页号加上相应业内索引即可得到虚拟地址的物理地址 2.不同的进程页目录都指向了相同的系统表页
五.心得体会
在这次上机实验，通过对WinDbg和VPc的调试运用，我熟悉了Windows内存管理器的结构，也认知到Windows如何进行地址转译和转换。对相关的知识也进行了温习，更牢的掌握了相关知识。当然这些还远远不够，我以后还要继续不断努力，去学习了解掌握操作系统的各方面知识。
附录：
1.A.exe代码
#include
#define N 1
HANDLE mutexSemaphore;HANDLE synchSemaphore_1;HANDLE synchSemaphore_2;
HANDLE mutexDisplay;
void Display(char*str,int delayTime){ if(WaitForSingleObject(mutexDisplay,INFINITE)==WAIT_OBJECT_0){ printf(“%snn”,str);ReleaseMutex(mutexDisplay);Sleep(delayTime);} }
void useTime(double limit){ for(double i=0;i<=limit;i+=0.001);}
void CreateProduct(){ Display(“Creating a production...”,0);useTime(200000);Display(“Creating finished.”,100);}
void PutProduct(){ Display(“Putting a production...”,0);useTime(150000);Display(“Putting finished”,100);}
void GetProduct(){ Display(“Getting a production...”,0);useTime(100000);Display(“Getting finished.”,100);}
void ConsumeProduct(){ Display(“Cosuming a production...”,0);useTime(100000);Display(“Cosuming finished.”,100);}
void Producer(){ while(true){ CreateProduct();
if(WaitForSingleObject(synchSemaphore_1,INFINITE)==WAIT_OBJECT_0){
if(WaitForSingleObject(mutexSemaphore,INFINITE)==WAIT_OBJECT_0){ PutProduct();ReleaseSemaphore(mutexSemaphore,1,NULL);} ReleaseSemaphore(synchSemaphore_2,1,NULL);} } }
void Consumer(){ while(true){
if(WaitForSingleObject(synchSemaphore_2,INFINITE)==WAIT_OBJECT_0){
if(WaitForSingleObject(mutexSemaphore,INFINITE)==WAIT_OBJECT_0){ GetProduct();ReleaseSemaphore(mutexSemaphore,1,NULL);} ReleaseSemaphore(synchSemaphore_1,1,NULL);} ConsumeProduct();} }
int main(){ HANDLE thread[2];DWORD threadID[2];
synchSemaphore_1=CreateSemaphore(NULL,N,N,NULL);synchSemaphore_2=CreateSemaphore(NULL,0,N,NULL);mutexSemaphore=CreateSemaphore(NULL,1,1,NULL);
mutexDisplay=CreateMutex(NULL,FALSE,NULL);
printf(“Program start.Please use WinDbg to observe main thread.nPress any key to continue...n”);getchar();
thread[0]=CreateThread(NULL,0,(LPTHREAD_START_ROUTINE)(Producer),NULL,CREATE_SUSPENDED,&threadID[0]);printf(“A producer was created.Please use WinDbg to observe producer thread.nPress any key to continue...n”);getchar();
thread[1]=CreateThread(NULL,0,(LPTHREAD_START_ROUTINE)(Consumer),NULL,CREATE_SUSPENDED,&threadID[1]);printf(“A Consumer was created.Please use WinDbg to observe Consumer thread.nPress any key to continue...n”);getchar();
printf(“Please select:n[1]Make producer thread runn[2]Make Consumer thread runn”);bool flag=true;bool flag_1=true,flag_2=true;int count=0;while(flag){ if(getchar()=='1'&&flag_1){ ResumeThread(thread[0]);count++;flag_1=false;} else if(getchar()=='2'&&flag_2){ ResumeThread(thread[1]);count++;flag_2=false;} if(count==2)flag=false;} WaitForMultipleObjects(1,thread,TRUE,INFINITE);
return 0;}
2.WG.exe代码： #include
int main(){ int a=0;printf(“I'm Wangn”);while(true){a++;} }
第二篇：操作系统-课程设计报告-处理机调度程序
操作系统
课程设计报告
学校：广州大学
学院：计算机科学与教育软件学院 班级：计算机127班 课题：处理机调度程序
任课老师：陶文正、陈文彬
姓名：黄俊鹏
学号：1200002111 班内序号：27 成绩：
日期：2015年1月6日
一、设计目的
在多道程序和多任务系统中，系统内同时处于就绪状态的进程可能有若干个。也就是说能运行的进程数大于处理机个数。为了使系统中的进程能有条不紊地工作，必须选用某种调度策略，选择一进程占用处理机。要求学生设计一个模拟处理机调度算法，以巩固和加深处理机调度的概念。
二、设计要求
1）进程调度算法包括：时间片轮转法，短作业优先算法，动态优先级算法。2）可选择进程数量
3）本程序包括三种算法，用C语言实现，执行时在主界面选择算法（可用函数实现）（进程数，运行时间，优先数由随机函数产生）执行，显示结果。
三、设计思路及算法思想
1.界面菜单选项
一级菜单提供2个选项： ① 自动生成进程数量 ② 手动输入所需进程数量
一级菜单选择完毕后进入二级菜单： ① 重新生成进程 ② 时间片轮转法 ③ 短作业优先算法 ④ 动态优先级算法 ⑤ 退出程序
2.调度算法
程序所用PCB结构体
需要用到的进程结构体如上图所示
1)时间片轮转法
主要是设置一个当前时间变量，curTime和时间片roundTime。
遍历进程组的时候，每运行一个进程，就把curTime += roundTime。进程已运行时间加roundTime
2)短作业优先算法
遍历进程组，找到未运行完成并且运行时间最短的进程，让它一次运行完成，如此往复，直到所有进程都运行完成为止。
3)动态优先级算法
做法跟短作业优先算法类似，此处主要是比较进程的优先数，优先级高者，先执行。直到全部执行完毕。当一个进程运行完毕后，适当增减其余进程的优先数，以达到动态调成优先级的效果。
3.程序流程图
四、运行截图
1）启动后输入5，生成5个进程
2）输入1，选择时间片轮转法。
自动输出结果，分别是时间片为1和4的结果
3）输入2，选择短作业优先算法
4）输入3，选择动态优先级算法
5）输入0，重新生成进程，再输入3，生成3个进程，选择2.短作业优先算法
6）输入q，退出
五、心得体会
通过这次实验，让我对操作系统的进程调度有了更进一步的了解。这个实验的模拟程度跟真实系统相比只是冰山一角，由此可见操作系统是何其复杂的软件产品，仅进程调度就有那么丰富和内涵的知识需要掌握。
但是再复杂的系统，都是由小部件构成的。古语云：不积跬步,无以至千里。不积小流,无以成江海。掌握这些基础的知识，可以为以后打下扎实的基础。
六、附录（源代码）
//
// main.c
// ProcessDispatch //
// Created by Jeans on 1/5/15.// Copyright(c)2015 Jeans.All rights reserved.//
#include
//最小进程数
#define MIN_PROCESS //最大进程数
#define MAX_PROCESS
//最小优先数
#define MIN_PRIORITY
0 //最大优先数
#define MAX_PRIORITY
//最小运行时间
#define MIN_RUNNING_TIME
//最大运行时间
#define MAX_RUNNING_TIME
typedef struct PCB{
char name;
//进程名
int priority;
//优先数
int runningTime;
//运行时间
int arriveTime;
//到达时间
int beginTime;
//开始时间
int finishTime;
//完成时间
int cyclingTime;
//周转时间
double weigthCyclingTime;//带权周转时间
int hadRunTime;
//已经运行时间
int finish;
//是否完成 }PCB;//获取随机数
int GetRandomNumber(int min,int max){
return arc4random()%(max-min)+ min;}
//初始化PCB组
void InitPCBGroup(PCB p[],int num){
char name = 'A';
for(int i = 0;i < num;i++){
p[i].name = name;
p[i].priority = GetRandomNumber(MIN_PRIORITY, MAX_PRIORITY);
p[i].runningTime = GetRandomNumber(MIN_RUNNING_TIME,MAX_RUNNING_TIME);
name++;
} }
void PrintResult(PCB p[],int num){
double avgCycTime = 0,avgWeiCycTime = 0;
printf(“|进程名
到达时间
运行时间
开始时间
完成时间
周转时间
带权周转时间
优先数
|n”);
for(int i = 0;i < num;i++){
printf(“|%3c
%-4d
%-4d
%-4d
%-4d
%-4d
%-6.2f
%-4d|n”,p[i].name,p[i].arriveTime,p[i].runningTime,p[i].beginTime,p[i].finishTime,p[i].cyclingTime,p[i].weigthCyclingTime,p[i].priority);
avgCycTime += p[i].cyclingTime;
avgWeiCycTime += p[i].weigthCyclingTime;
//还原
p[i].arriveTime = 0;
p[i].beginTime = 0;
p[i].finishTime = 0;
p[i].cyclingTime = 0;
p[i].weigthCyclingTime = 0;
p[i].hadRunTime = 0;
p[i].finish = 0;
}
avgWeiCycTime /= num;
avgCycTime /= num;
printf(“平均周转时间：%.2f
平均带权周转时间:%.2fn”,avgCycTime,avgWeiCycTime);} //时间片轮转法
void RealRoundRobin(PCB p[],int num,int roundTime){
printf(“nn-----------------------------时间片：%d------n”,roundTime);
int finishNum = 0;
int curTime = 0;
while(finishNum!= num){
for(int i = 0;i < num;i++){
if(p[i].finish)continue;
//开始时间
if(p[i].beginTime == 0 && i!= 0){
p[i].beginTime = curTime;
}
//已经完成
if(p[i].hadRunTime + roundTime >= p[i].runningTime){
p[i].finishTime = curTime + p[i].runningTimep[i].arriveTime;
p[i].weigthCyclingTime = p[i].cyclingTime/(double)p[i].runningTime;
p[i].finish = 1;
finishNum ++;
curTime += p[i].runningTimep[min].arriveTime;
p[min].weigthCyclingTime = p[min].cyclingTime/(double)p[min].runningTime;
p[min].finish = 1;
finishNum++;
curTime = p[min].finishTime;
}
PrintResult(p, num);}
//动态优先级算法
void DynamicPriorityFirst(PCB p[],int num){
printf(“nn-----------------------------动态优先级算法--n”);
int finishNum = 0;
int curTime = 0;
while(finishNum!= num){
int min = 0;
//查找优先级最高下标
for(int i = 1;i < num;i++){
if(p[i].finish == 0 && p[min].priority >= p[i].priority)
min = i;
else if(p[i].finish == 0 && p[min].finish == 1)
min = i;
}
p[min].beginTime = curTime;
p[min].hadRunTime = p[min].runningTime;
p[min].finishTime = p[min].beginTime + p[min].runningTime;
p[min].cyclingTime = p[min].finishTime-p[min].arriveTime;
p[min].weigthCyclingTime = p[min].cyclingTime/(double)p[min].runningTime;
p[min].finish = 1;
finishNum++;
curTime = p[min].finishTime;
}
PrintResult(p, num);}
int main(int argc, const char * argv[]){
PCB pcbGroup[30];
//pcb数组
int processNum = 0;//进程数
while(1){
//选择进程数量
while(1){
if(processNum!= 0)
break;
printf(“n----------n”);
printf(“当前默认进程数范围%d--%dn”,MIN_PROCESS,MAX_PROCESS);
printf(“1)输入0可随机生成进程数目n2)输入%d-%d范围内数字，回车，可生成指定数目进程n>>>>>>”,MIN_PROCESS,MAX_PROCESS);
int num = 0;
scanf(“%d”,&num);
if(num == 0){
processNum = GetRandomNumber(MIN_PROCESS, MAX_PROCESS);
break;
}else{
if((num >= MIN_PROCESS)&&(num <= MAX_PROCESS)){
processNum = num;
InitPCBGroup(pcbGroup,processNum);
break;
}else
printf(“n输入有误，请重新输入.n”);
}
}
//选择算法
printf(“n-----------------------------请输入对应选项序号-----------------------------n”);
printf(“0.重新生成进程 | 1.时间片轮转法 | 2.短作业优先算法 | 3.动态优先级算法 | q.退出n>>>>>>”);
char ch;
while((ch = getchar())== 'n');
switch(ch){
case '0'://0 重新生成进程
processNum = 0;break;
case '1'://1 时间片轮转法
RoundRobin(pcbGroup, processNum);break;
case '2'://2 短作业优先算法
ShortestJobFirst(pcbGroup, processNum);break;
case '3'://3 动态优先级算法
DynamicPriorityFirst(pcbGroup,processNum);break;
case 'q'://q 退出
exit(0);
default:
break;
}
}
return 0;}
第三篇：操作系统进程调度实验
一.实验目的及实验环境 1.实验目的
通过观察、分析实验现象，深入理解进程及进程在调度执行和内存空间等方面的特点，掌握在POSIX 规范中fork和kill系统调用的功能和使用。2.实验环境
（1）硬件
CPU：I7-4500U 内存：8G DDR3 1600 显示器：华硕笔记本显示器 硬盘空间：80G
（2）软件
虚拟机名称及版本：非虚拟机
操作系统名称及版本：Ubuntu Kylin 16.04 编译器：gcc 二.实验内容
1、实验前准备工作
学习man 命令的用法，通过它查看fork 和kill 系统调用的在线帮助，并阅读参考资料，学会fork 与kill 的用法，复习C 语言的相关内容。
2、实验内容
根据下发的Linux进程管理实验PPT内容，将实验代码补充完整。并考虑： 先猜想一下这个程序的运行结果。假如运行“./process 20”，输出会是什么样？然后按照注释里的要求把代码补充完整，运行程序。可以多运行一会儿，并在此期间启动、关闭一些其它进程，看process 的输出结果有什么特点，记录下这个结果。开另一个终端窗口，运行“ps aux|grep process”命令，看看process 究竟启动了多少个进程。回到程序执行窗口，按“数字键+回车”尝试杀掉一两个进程，再到另一个窗口看进程状况。按q 退出程序再看进程情况。
3、回答问题
编写、编译、链接、执行实验内容设计中的代码，并回答如下问题： 1）你最初认为运行结果会怎么样？
手动输入进程数，选择输入要杀死的进程编号，按q杀死所有进程。需手动输入进程数，然后键入编号杀死进程，键入q杀死父进程即杀死2）实际的结果什么样？有什么特点？试对产生该现象的原因进行分析。所有进程。
3）proc_number 这个全局变量在各个子进程里的值相同吗？为什么？ 不相同，proc_number是存储各个子进程的编号的，所以在各个子进程中
是不同的。
4）kill 命令在程序中使用了几次？每次的作用是什么？执行后的现象是什么？
使用了2次，第一次是在while循环中的if语句中使用，用来杀死用户键入的指定进程。第二次是杀死父进程，回到程序的开始。
5）使用kill 命令可以在进程的外部杀死进程。进程怎样能主动退出？这两种退出方式哪种更好一些？
调用return 函数或exit函数都可以正常退出，而使用kill函数是异常退出，使用正常退出的方法比较好。
6）写出fork（）和kill（）函数原型，并解释函数的功能和参数的含义？
原型： #include
功能：
一个现有进程可以调用fork函数创建一个新进程。由fork创建的新进程被称为子进程。fork函数被调用一次但返回两次。两次返回的唯一区别是子进程中返回0值而父进程中返回子进程ID。原型：#include
int kill(pid_t pid, int sig);
功能：
向某个进程传递一个信号
7）ps aux|grep process命令功能是什么？并解释结果的含义。
ps命令是最基本进程查看命令.使用该命令可以确定有进程正在运行数量和运行的状态、进程是否结束、是否有僵尸进程、进程占用的资源。grep命令查看某进程的状态并打印在屏幕上，ps aux是显示所有进程和他们的状态。ps aux输出格式：
USER PID %CPU %MEM VSZ RSS TTY STAT START TIME COMMAND
三．方案设计
每创建一个子进程时，将其pid存储在数组pid[i]中，i存储在proc_number中，然后调用死循环函数do_something()，输出该进程的proc_number，当输入数字是主进程执行kill(pid[pid-48],SIGTERM)，杀死ch-48进程。当输入q时循环退出，kill(0,SIGTERM),杀死本组所有进程，程序退出。
#include
四．测试数据及运行结果
注释：由于我的电脑运行这段代码报错，所以我和我组高宏伟同学使用的是同一实验数据，同一代码。五．总结
1． 实验过程中遇到的问题及解决办法；
实验中由于代码中的大部分已经给出，只需填写重要部分。遇到了不懂fork的返回值，所以if和else语句会同时执行，知道了fork的原理后，fork会返回两个值一个到子进程，一个到父进程。2． 对设计及调试过程的心得体会。
本次实验学会了创建进程命令fork和杀死进程命令kill。在开始的时候不理解fork 和kill的原理，有点懵。后来通过看书和上网查询知道了fork和kill的原理后明白了代码要填写的空白。六．附录：源代码（电子版）
#include
#define MAX_CHILD_NUMBER 10 #define SLEEP_INTERVAL 2
int proc_number=0;void do_something();
int main(int argc,char* argv[]){ int child_proc_number=MAX_CHILD_NUMBER;int i,ch;pid_t child_pid;
pid_t pid[10]={0};if(argc>1){
child_proc_number = atoi(argv[1]);
child_proc_number =(child_proc_number>10)?10:child_proc_number;
for(i=0;i child_pid=fork(); proc_number=i; if(child_pid==0){do_something(); }else if(child_pid>0){ pid[i]=child_pid; printf(“A Parent process,the pid is %dn”,getpid()); } } printf(“input the number you want to killn”); while((ch=getchar())!='q') { if(isdigit(ch)){ ch=(int)ch-48; if(kill(pid[ch],SIGKILL)<0){ perror(“kill”); exit(1); }else{ printf(“process %d has been killed!nn”,pid[ch]); } }else{ printf(“is not digitn”); } getchar(); printf(“input the number you want to kill:n”); } kill(0,SIGTERM);} return 0;} void do_something(){ for(;;){ printf(“This is process No.%*dn”,proc_number+3,proc_number); sleep(SLEEP_INTERVAL);} } 实验一 进程控制与处理机调度综合实验 一、实验目的 通过模拟进程控制方法及单处理机系统的进程调度，了解进程的结构，进程的创建与撤消，进程的组织及进程的状态及其转换，掌握进程调度策略。 二、实验环境 开发工具使用windows平台下的vc++6.0。 三、实验内容 本实验为单机模拟进程调度算法，在程序设计时不需真正地建立线程或者进程。实验模拟创建若干进程（人为输入或随机数产生），选择一种或几种单处理机的进程调度算法，如FCFS（先来先服务），SPF（短进程优先），RR（时间片轮转法），优先级算法等，模拟进行进程调度。每进行一次调度，都打印一次运行进程、就绪队列、以及各个进程的PCB，并能在进程完成后及时撤消该进程。 四、完成情况 1、进程及进程的运行状态 进程是现代计算机中的基本要素，是系统分配资源和调度的基本单位。进程与程序不同，进程是系统中动态的实体，有它的创建、运行和撤销的过程。PCB块是系统感知进程存在的唯一实体。进程的创建必须首先创建进程的PCB块，而进程的运行也伴随着PCB块的变化，进城撤销也要同时撤销它的PCB块。所以本实验的任务就是通过模拟调度进程的PCB块来调度进程。进程的PCB块包含以下四方面的内容： a)进程标示符 b)处理及状态信息 c)进程调度信息 d)进程控制信息 进程在运行中存在三种基本状态，分别是运行状态、就绪状态和阻塞状态。 2、进程调度 一个运行进程的时间片用完或发生阻塞时，系统就会选择一个就绪进程调度执行。进程的调度算法有很多如FCFS、SPF、优先级调度和时间片轮转方法。进程调度算法模拟试验就是通过调度进程的PCB块来模拟调度进程。在系统中PCB块就表现为一个结构体，PCB块之间的连接方式存在两种，一种是连接方式，一种是索引方式。本试验中可选择任意一种连接方式。 3、例程 设计一个有 N个进程共行的进程调度程序。进程调度算法：采用最高优先数优先的调度算法（即把处理机分配给优先数最高的进程）。 每个进程有一个进程控制块（PCB）表示。进程控制块可以包含如下信息：进程名、优先数、到达时间、需要运行时间、已用CPU时间、进程状态等等。进程的优先数及需要的运行时间可以事先人为地指定（也可以由随机数产生）。进程的到达时间为进程输入的时间。进程的运行时间以时间片为单位进行计算。每个进程的状态可以是就绪 W（Wait）、运行R（Run）、或完成F（Finish）三种状态之一。就绪进程获得 CPU后都只能运行一个时间片。用已占用CPU时间加1来表示。如果运行一个时间片后，进程的已占用 CPU时间已达到所需要的运行时间，则撤消该进程，如果运行一个时间片后进程的已占用CPU时间还未达所需要的运行时间，也就是进程还需要继续运行，此时应将进程的优先数减1（即降低一级），然后把它插入就绪队列等待CPU。每进行一次调度程序都打印一次运行进程、就绪队列、以及各个进程的 PCB，以便进行检查。重复以上过程，直到所要进程都完成为止。 调度算法的流程图如下： 开始初始化进程PCB，输入进程信息各进程按优先数从高到低排列y就绪队列空？结束就绪队列首进程投入运行时间片到CPU占用时间+1运行已占用CPU时间已达到所需CPU时间y进程完成撤销该进程是运行进程的优先数减1把运行进程插入就绪队列 图1-1 流程图 源代码：#include “stdio.h” #include int insert=0;if((ready==NULL)||((p->super)>(ready->super)))/*优先级最大者,插入队首 */ { p->link=ready;ready=p;} else /* 进程比较优先级,插入适当的位置中*/ { first=ready;second=first->link; while(second!=NULL) { if((p->super)>(second->super))/*若插入进程比当前进程优先数 大,*/ { /*插入到当前进程前面*/ p->link=second; first->link=p; second=NULL; insert=1;} else /* 插入进程优先数最低,则插入到队尾*/ { first=first->link;second=second->link; } } if(insert==0) first->link=p;} } void input()/* 建立进程控制块函数*/ { int i,num;printf(“n请输入进程数量:”);scanf(“%d”,&num);for(i=0;i printf(“n 进程号No.%d:n”,i); p=getpch(PCB); printf(“n 输入进程名:”); scanf(“%s”,p->name); printf(“n 输入进程优先数:”); scanf(“%d”,&p->super); printf(“n 输入进程运行时间:”); scanf(“%d”,&p->ntime); printf(“n”); p->rtime=0;p->state='w'; p->link=NULL; sort();/* 调用sort函数*/ } } int space(){ int l=0;PCB* pr=ready;while(pr!=NULL){ l++; pr=pr->link;} return(l);} void show(){ printf(“nqnametstatetsupertndtimetruntimen”);} void disp(PCB * pr)/*建立进程显示函数,用于显示当前进程*/ { printf(“ %st”,pr->name);printf(“ %ct”,pr->state);printf(“ %dt”,pr->super);printf(“ %dt”,pr->ntime);printf(“ %dt”,pr->rtime);printf(“n”);} void check()/* 建立进程查看函数 */ { PCB* pr;printf(“n****当前正在运行的进程是:%s”,p->name);/*显示当前运行进程*/ show();disp(p);pr=ready;if(pr==NULL) printf(“n****当前就绪队列为空!”); else { printf(“n****当前就绪队列状态为:”);/*显示就绪队列状态*/ show(); while(pr!=NULL) { disp(pr); pr=pr->link; } } } void destroy()/*建立进程撤消函数(进程运行结束,撤消进程)*/ { printf(“n 进程[%s]已完成.n”,p->name);free(p);} void running()/* 建立进程就绪函数(进程运行时间到,置就绪状态*/ {(p->rtime)++;if(p->rtime==p->ntime)destroy();/* 调用destroy函数*/ else { (p->super)--; p->state='w'; sort();/*调用sort函数*/ } } void main()/*主函数*/ { int len,h=0;char ch;input();len=space();while((len!=0)&&(ready!=NULL)){ ch=getchar(); h++; printf(“n 当前运行次数为:%d n”,h); p=ready; ready=p->link; p->link=NULL; p->state='R'; check(); running(); printf(“n 按任一键继续......”); ch=getchar();} printf(“nn 进程已经完成.n”);ch=getchar();} 输入数据后运行结果如下图所示： 五、问题及解决办法 问题：当插入的进程优先级大于当前进程优先级的时候，插入的进程应该放在什么 位置？ 方法：通过指针的指向变换，把插入的进程放置在当前进程前面。 六、实验心得 通过本次实验，了解了进程的结构，进程的创建、撤销，掌握了进程调度策略处理机调度的理解，我更加深刻的认识到调度进程的pcb块来调度进程的过程，以及按照优先权进行排序的算法实现。对操作系统有了进一步的认识，后面会更加努力学习，掌握这门学科。 进程调度算法模拟 专业：XXXXX 学号：XXXXX 姓名：XXX 实验日期：20XX年XX月XX日 一、实验目的 通过对进程调度算法的模拟加深对进程概念和进程调度算法的理解。 二、实验要求 编写程序实现对5个进程的调度模拟，要求至少采用两种不同的调度算法分别进行模拟调度。 三、实验方法内容 1.算法设计思路 将每个进程抽象成一个控制块PCB，PCB用一个结构体描述。 构建一个进程调度类。将进程调度的各种算法分装在一个类中。类中存在三个容器，一个保存正在或未进入就绪队列的进程，一个保存就绪的进程，另一个保存已完成的进程。还有一个PCB实例。主要保存正在运行的进程。类中其他方法都是围绕这三个容器可以这个运行中的PCB展开。 主要用到的技术是STL中的vector以维护和保存进程容器、就绪容器、完成容器。 当程序启动时，用户可以选择不同的调度算法。然后用户从控制台输入各个进程的信息，这些信息保存到进程容器中。进程信息输入完毕后，就开始了进程调度，每调度一次判断就绪队列是否为空，若为空则系统时间加一个时间片。判断进程容器中是否有新的进程可以加入就绪队列。2.算法流程图 主程序的框架： 开始void FCFS();//先来先服务void SJF();//最短进程优先调度void RR();//简单时间片轮转void PD();//最高优先数优先void PCBInput();//输入进程信息选择调度算法输入进程信息将输入容器中以满足进入条件的进程调入就绪队列void ProcessQueueProcess();//查看当前时间下，有无进程加入。若有则把该进程调入就绪队列按照选择的算法开始选择就绪队列的进程开始执行void ProcessSelect();//若当前就绪队列不为空则根据选择的调度算法开始调度,否则，系统时间加一个时间片.以等待新的进程到判断就绪容器和输入容器是否为空!processScheduler.m_WaitQueue.empty()||!processScheduler.m_ProcessQueue.empt()Y打印各进程信息进行统计计算周转时间等结束void PCBDisplay();//打印当前状况下。就绪队列、完成队列、运行中的进程信息void SchedulerStatistics();//调度统计，计算周转时间等进程调度过程： 开始为空判断就绪队列是否为空if(m_WaitQueue.empty())非空让系统等待一个时间片TimePast()根据设定的调度算法从就绪队列中调入一个进程并执行（此时进程从就绪队列中删除，赋值到表示运行中的成员变量中）void FCFS();//先来先服务void SJF();//最短进程优先调度void RR();//简单时间片轮转void PD();//最高优先数优先进程运行一个时间片N是否达到该进程停止运行的条件Y选入的进程状态是否为“完成”如进程已完成，或者分得的时间片个数已到ProcessRun()Yvector m_WaitQueue;//进程就绪队列进程未完成，将进程优先数减一，并放回到就绪队列中设置进程完成时间，将该进程放入完成队列vector m_FinishQueue;//完成队列结束 3.算法中用到的数据结构 struct fcfs{ //先来先服务算法从这里开始 char name[10]; float arrivetime; float servicetime; float starttime; float finishtime; float zztime; float dqzztime; }; //定义一个结构体，里面包含的有一个进程相关的信息 4.主要的常量变量 vector m_ProcessQueue;//进程输入队列 vector m_WaitQueue;//进程就绪队列 vector m_FinishQueue;//完成队列 vector ::iterator m_iter;//迭代器 PCB m_runProcess;//运行中的进程 int m_ProcessCount;//进程数 float m_RunTime;//运行时间 int m_tagIsRun;//是否在运行标志。表示正在运行，表示没有 float m_TimeSlice;//时间片大小 int m_TimeSliceCount;//指时间片轮转中一次分到的时间片个数 char m_SchedulerAlgorithm;//调度算法 5.主要模块 void PCBInput();//输入进程信息 void PCBSort();//对进程控制块按照优先级排序(采用冒泡排序)void ProcessSelect();//若当前就绪队列不为空则根据选择的调度算法开始调度。否则，系统时间void PCBDisplay();//打印当前状况下。就绪队列、完成队列、运行中的进程信息 void ProcessRun();//进程运行一次。运行时间加个时间片。并判断进程是否达到完成条件。若是则void ProcessQueueProcess();//查看当前时间下，有无进程加入。若有则把该进程调入就绪队列 void ProcessDispatch();//进程分派，进程执行完成后决定进程该进入哪个队列(就绪、完成)void TimePast(){ m_RunTime +=m_TimeSlice;ProcessQueueProcess();}//当前系统时间加个时间void SchedulerStatistics();//调度统计，计算周转时间等 void FCFS();//先来先服务 void SJF();//最短进程优先调度 void RR();//简单时间片轮转 void PD();//最高优先数优先 加.以等待新的进程到来 ProcessStatus='f'.否则为'w';片，并检查是否有新的进程加入 四、实验代码 #include using namespace std; struct fcfs{ //先来先服务算法从这里开始 char name[10]; float arrivetime; float servicetime; float starttime; float finishtime; float zztime; float dqzztime; }; //定义一个结构体，里面包含的有一个进程相关的信息 fcfs a[100]; void input(fcfs *p,int N) { int i; cout< printf(“ 请您输入进程的名字 到达时间 服务时间:(例如: a 0 100)nn”); for(i=0;i<=N-1;i++) { printf(“ 请您输入进程%d的信息:t”,i+1); scanf(“ttt%s%f%f”,&p[i].name,&p[i].arrivetime,&p[i].servicetime); } } void Print(fcfs *p,float arrivetime,float servicetime,float starttime,float finishtime,float zztime,float dqzztime,int N) { int k; printf(“nn调用先来先服务算法以后进程运行的顺序是: ”); printf(“%s”,p[0].name); for(k=1;k { printf(“-->%s”,p[k].name); } cout< printf(“n 具体进程调度信息:n”); printf(“t进程名 到达时间 服务时间 开始时间 结束时间 周转时间 带权周转时间n”); for(k=0;k<=N-1;k++) { printf(“t%st%-.2ft %-.2ft %-.2ft %-.2ft %-.2ft %-.2fn”,p[k].name,p[k].arrivetime，p[k].servicetime,p[k].starttime,p[k].finishtime,p[k].zztime,p[k].dqzztime); } getchar(); //此处必须要有这个函数，否则就看不到显示器上面的输出，可以看到的结果只是一闪而过的一个框剪 } void sort(fcfs *p,int N)//排序 { for(int i=0;i<=N-1;i++) for(int j=0;j<=i;j++) if(p[i].arrivetime { fcfs temp; temp=p[i]; p[i]=p[j]; p[j]=temp; } } void deal(fcfs *p, float arrivetime,float servicetime,float starttime,float finishtime,float &zztime,float &dqzztime,int N) //运行阶段 { int k; for(k=0;k<=N-1;k++) { if(k==0) { p[k].starttime=p[k].arrivetime; p[k].finishtime=p[k].arrivetime+p[k].servicetime;} else { p[k].starttime=p[k-1].finishtime; p[k].finishtime=p[k-1].finishtime+p[k].servicetime;} } for(k=0;k<=N-1;k++) { p[k].zztime=p[k].finishtime-p[k].arrivetime; p[k].dqzztime=p[k].zztime/p[k].servicetime; } } void FCFS(fcfs *p,int N) { float arrivetime=0,servicetime=0,starttime=0,finishtime=0,zztime=0,dqzztime=0; sort(p,N); deal(p,arrivetime,servicetime,starttime,finishtime,zztime,dqzztime,N); Print(p,arrivetime,servicetime,starttime,finishtime,zztime,dqzztime,N); getchar(); } //先来先服务算法到此结束 struct sjf{//最短进程优先调度算法从这里开始 char name[10];float arrivetime;//到达时间 float servicetime;//运行时间 float starttime; //开始时间 float finishtime; //完成时间 };sjf a1[100]; void input(sjf *p,int N1)//进程信息输入 { int i;cout< printf(“ 请您输入进程的名字 到达时间 服务时间:(例如: a 0 100)n”); for(i=0;i<=N1-1;i++){ printf(“ 请您输入进程%d的信息:t”,i+1); scanf(“ttt%s%f%f”,&p[i].name,&p[i].arrivetime,&p[i].servicetime);} } void Print(sjf *p,float arrivetime,float servicetime,float starttime,float finishtime,int N1)//最终结果输出 { int k; printf(“nt调用最短进程优先调度算法以后进程的调度顺序为:”); printf(“%s”,p[0].name); for(k=1;k {printf(“-->%s”,p[k].name);} cout< printf(“n给个进程具体调度信息如下:n”); printf(“nt进程名t到达时间t运行时间t开始时间t完成时间n”); for(k=0;k<=N1-1;k++) { printf(“ t%st %-.2ftt %-.2ftt %-.2ftt %-.2ftn”,p[k].name,p[k].arrivetime，p[k].servicetime,p[k].starttime,p[k].finishtime); } getchar(); } void sort(sjf *p,int N1)//排序 { for(int i=0;i<=N1-1;i++) for(int j=0;j<=i;j++) if(p[i].arrivetime { sjf temp; temp=p[i]; p[i]=p[j]; p[j]=temp; } } void deal(sjf *p, float arrivetime,float servicetime,float starttime,float finishtime,int N1)//运行阶段 { int k; for(k=0;k<=N1-1;k++) { if(k==0) { p[k].starttime=p[k].arrivetime; p[k].finishtime=p[k].arrivetime+float(p[k].servicetime)/60;} else { p[k].starttime=p[k-1].finishtime; p[k].finishtime=p[k-1].finishtime+float(p[k].servicetime)/60;} } } void sjff(sjf *p,int N1){ float arrivetime=0,servicetime=0,starttime=0,finishtime=0; sort(p,N1); for(int m=0;m {if(m==0) p[m].finishtime=p[m].arrivetime+float(p[m].servicetime)/60; else p[m].finishtime=p[m-1].finishtime+float(p[m].servicetime)/60; int i=0; for(int n=m+1;n<=N1-1;n++) { if(p[n].arrivetime<=p[m].finishtime) i++; } float min=p[m+1].servicetime; int next=m+1; for(int k=m+1;k { if(p[k+1].servicetime {min=p[k+1].servicetime; next=k+1;} } sjf temp; temp=p[m+1]; p[m+1]=p[next]; p[next]=temp; } deal(p,arrivetime,servicetime,starttime,finishtime,N1); Print(p,arrivetime,servicetime,starttime,finishtime,N1); getchar();}//最短进程优先调度算法到这里结束 char menu()//用来输出相关信息的函数 { char cse1; while(1) { system(“cls”); fflush(stdin); cout< cout< cout<<“t”<<“|| <<<<<<<<<<<<欢<<<<<<<<<<< >>>>>>>>>>>>迎>>>>>>>>>>> ||”< cout<<“t”<<“|| ||”< cout<<“t”<<“||”<<“t 进程调度算法模拟”<<“tt”<<“||”< cout<<“t”<<“|| ||”< cout<<“t”<<“||”<<“tt 1.先来先服务调度算法 ”<<“tt”<<“||”< cout<<“t”<<“|| ||”< cout<<“t”<<“||”<<“tt 2.最短进程优先调度算法”<<“tt”<<“||”< cout<<“t”<<“|| ||”< cout<<“t”<<“|| <<<<<<<<<<<<<<<<<<<<<<<<<您>>>>>>>>>>>>>>>>>>>>>>>>> ||”< cout< cout< cout<<“tt 请输入您的选择（1/2）：”; cse1=getchar(); if(cse1<'1'||cse1>'2') cout<<“你的输入有错！”< else break; } return cse1;} int main(int argc, char *argv[]){ while(1) { switch(menu()) { case '1': int N; cout< cout< printf(“tt<<---！!@@@先来先服务调度算法@@@！!--->>n”); cout< printf(“输入进程数目:”); scanf(“%d”,&N); input(a,N); FCFS(a,N); case '2': int N1; cout< cout< printf(“tt<<---！!@@@最短进程优先调度算法@@@！!--->>n”); cout< printf(“输入进程数目: ”); scanf(“%d”,&N1); input(a1,N1); sjf *b=a1; sjf *c=a1; sjff(b,N1); getchar(); } } system(“PAUSE”); return EXIT_SUCCESS;} 五、实验结果 1.执行结果 2.结果分析 先来先服务调度算法就是根据进程达到的时间为依据，哪一个进程先来那么该进程就会先执行；最短进程优先调度算法则是以每个进程执行所需时间长短为依据，某一个进程执行所需花的时间要短些那么该进程就先执行。以上就是本次进程调度实验的依据。 六、实验总结 通过本次实验了解到算法很重要，又更加明白算法本身可以节约时间，而且不同的函数之间在调用的时候要注意很多的问题。第四篇：操作系统 实验一 进程调度
第五篇：操作系统进程调度算法模拟实验报告
点击咨询 