第一篇：操作系统实验二——cpu调度与内存分页
一、试验目的
理解操作系统内存管理的原理及分页内存管理方案
二、试验要求
1、实现分页内存管理方案，假定页和帧的大小均为4KB，物理内存为128MB
2、输入为进程ID，所需内存大小等，输出为页表。
3、请按要求撰写实验报告，并和源程序一起打包上传
4、实验平台不限，linux和windows均可
5、与第一次实验的程序整合成一个程序
三、试验环境
Windows XP Visual C++ 6.0
四、试验内容
为了与上一个实验结合，并且考虑到可能需要兼容以后的实验，所以本次实验不但重写了PCB，而且按照自己对操作系统的理解构造出了一虚拟的I/O设备和两套调度程序（作业调度程序和CPU调度程序）
一、首先从与内存分配相关的作业调度函数说起，程序中为Jobs_scheduler。Job_scheduler的作用如下图所示;
Job_scheduler从大容量存储设备上的缓冲池中载入新生成的进程到内存，同时生成新的PCB到就绪队列中。这里涉及到了两个数据结构class Program，class PCB。Program ：
PCB：
PCB中的state包含五个状态NEW、READY、RUN、WAITING、TERMINATED，加入到ReadyQueue中等待运行的PCB均为READY状态的，运行中会被置为RUN，WAITNG状态为等待I/O设备的进程，如果进程状态为TERMINATED，将会被移出作业队列。
Job_scheduler函数在将program装入内存前，会查看帧表内空闲的帧的数目是否大于等于program所需的页数目，如果成立才装入，并且为PCB构造页表。构造时，先按照帧表通过顺序查找找到可用的帧，然后就将页的内容加载上去。
二、接下来是CPU调度程序，也成为短期调度程序。
CPU_scheduler所做的工作如下图所示，其操作的队列是就绪队列RedayQueue
本程序采用的调度算法为分时调度，时间片大小TimeSlice取为1（当然这个随时都可用改动），里面执行程序的函数Run是模拟CPU功能的，它会返回一个值，Normal表示执行正常，若是返回了INTERRUPT 中断；ERROR 出错就会中断此次运行，并且将所指PCB从ReadyQueue中移除。
这里的Run函数其实模拟了CPU的取指令和翻译指令的功能，本程序只有一个有实际作用的指令，'O'，如果内存中的内容为'0'（十进制ASCⅡ码值），则代表需要利用I/O设备输出该地址内容。如上图所示，PCB会加入到WaitingQueue中等待I/O，并判断此时I/O设备是否开启，如果未开启则开启设备。Run函数也因此返回一个interrupt值。运行结果
在编号为1的进程中的第一个内存单位设置了一条I/O指令，可以看出其发生中断后等待I/O完成才重新回到ReadyQueue中并执行完毕。
以上结果是在内存足够大的情况，下面再看一组内存不能同时满足需求的情况
此次内存设为11帧，编号为1的进程需要10帧，编号为2的进程需要1帧，我们看到，2号进程顺利载入并执行了，但其他进程都要等到1号进程执行完释放内存后才能载入内存，符合预期情况。
五、心得体会
为了很好的仿真，本次试验尽可能地模拟了硬件的工作，如输入输出设备和模拟CPU的run函数，基本上把教材77页调度问题的队列图所示功能模拟出来了，也大体实现了从用户程序到系统进程再到硬件的执行过程。
对于本次实验的核心内容——内存管理，实现了从磁盘到内存额装载过程，实现了页表的创建，实现了内存的释放。缺陷是没有考虑到换入换出等动态的情况，也就是说在此做了一个假设：每个进程相互独立且对于每个单独的进程来说，内存空间是足够大的。
第二点缺陷是，没有按照题目要求分配那么多的内存空间，因为那么大输入输出不好控制。
在本程序中，输入输出与要求有出入，并没有输入进程需要的时间，而是以进程的具体内容代替，在这里又有一个假设：假设进程在CPU中每执行一步需要一个单位的时间，这样进程的大小也就等价于进程需要的时间了（排除有I/O请求的情况），个人认为这样假设比人工限定执行时间更加贴近现实情况。
程序的输入非即时的，而是通过事先设定好的5个进程加上运行后随机生成的若干进程，也是为了模拟实际情况考虑。
因为全手工输入需要输入进程的到达时间，也就是需要根据到达时间来为缓冲池中进程排序的问题，但实际情况下到达时间是多余的，先创建的先加入队列即可，所以采用了随机生成的方式。
为了此次实验，复习了调度和内存管理两章的大部分内容，对操作系统对进程调度和内存分配管理有了更深入的认识，但只是从概念上，没有看到真正操作系统的代码或者算法实例，所以可能很多地方的代码与实际情况出入很大。
代码：
#include #include
/***************
随机数，后面随机生成进程用的 *************/ void rand_seed(){ int seed = static_cast
int rand_int(int a, int b){ return a + rand()%(b1)
{
pc[1]++;
}
else
{
pc[0]++;
pc[1] = 0;
}
pcb.state = READY;} else if(pc[1] < PAGE-1){
pc[1]++;} else
pcb.state = TERMINATED;}
bool io_equipment = OFF;/* I/O设备(DMA)*/ DWORD WINAPI IOEquipment(LPVOID lpParamter){ io_equipment = ON;list
::iterator pw = WaitingQueue.begin();while(pw!= WaitingQueue.end()){
/* 为了体现I/O设备速度较慢，所以在此用了Sleep函数 */
Sleep(1000);
cout << “P” << pw->number << “ I/O : ”<<(char)Memory[AddOfIO] << endl;
if(pw->state == WAITING)
pw->state = READY;
ReadyQueue.push_back(*pw);
pw = WaitingQueue.erase(pw);
if(pw!= WaitingQueue.end())
pw++;
else
pw = WaitingQueue.begin();} io_equipment = OFF;return FINISH;}
HANDLE ioEquipment;/**
模拟CPU执行
只实现了部分功能，并没有完全按照原理模拟
**/ int Run(PCB& pcb){ pcb.state = RUN;list
::iterator p = pcb.PageTable.begin();int addr[2];
addr[1] = pcb.pc[1];addr[0] = pcb.findframe(pcb.pc[0]);
switch(Memory[addr[0] * FRAME + addr[1]]){ case 'O': //如果指令触发了输出设备
pcb.state = WAITING;
pcr[0] = pcb.pc[0];
pcr[1] = pcb.pc[1];
IncPc(pcb, pcr);
pcb.pc[0] = pcr[0];
pcb.pc[1] = pcr[1];
AddOfIO = addr[0] * FRAME + addr[1];
WaitingQueue.push_back(pcb);
/* 如果I/O设备未开启，则打开，否则什么都不做 */
if(io_equipment == OFF)
ioEquipment = CreateThread(NULL, 0, IOEquipment, NULL, 0, NULL);
else
;
return INTERRUPT;default :
break;}
/* 在没有跳转的情况下，运行之后，pc自加 */ pcr[0] = pcb.pc[0];pcr[1] = pcb.pc[1];IncPc(pcb, pcr);pcb.pc[0] = pcr[0];pcb.pc[1] = pcr[1];
return NORMAL;}
HANDLE hMutex = CreateMutex(NULL, FALSE, “screen”);
/* 长期调度程序,将缓冲池中的进程加载到内存上 */ DWORD WINAPI Jobs_scheduler(LPVOID lpParamter){ list
::iterator p = BufferList.begin();while(true){
//WaitForSingleObject(hMutex, INFINITE);
if(p!= BufferList.end()&& p->page_numbers <= FraTable.free_frame)
{
ReadyQueue.push_back(PCB(*p));
p = BufferList.erase(p);
}
else if(p!= BufferList.end())
p++;
else
p = BufferList.begin();
//ReleaseMutex(hMutex);
} }
/* 利用RR算法的短期调度程序 */ DWORD WINAPI CPU_scheduler(LPVOID lpParamter){ list
::iterator p = ReadyQueue.begin();int run_time = 0;int total_time = 1;while(true){
WaitForSingleObject(hMutex, INFINITE);
if(p == ReadyQueue.end())
p = ReadyQueue.begin();
while(run_time < TimeSlice && p->state == READY)
{
p->run_time++;
run_time++;
//cout << total_time++ << endl;
cout << “p” << p->number << “ ” << “run time ” << p->run_time << endl;
if(Run(*p)== NORMAL)
/* do nothing */;
else
{
p = ReadyQueue.erase(p);
break;
}
/* 操作系统负责计时 */
}
run_time = 0;
if(p->state == TERMINATED)
{
Release(*p);
p = ReadyQueue.erase(p);
}
else
{
p++;
}
ReleaseMutex(hMutex);} }
int main(){ int num = 1;Program p1(num++, “O123456089”);Program p2(num++, “0”);Program p3(num++, “01”);Program p4(num++, “01”);Program p5(num++, “01234”);BufferList.push_back(p1);BufferList.push_back(p2);BufferList.push_back(p3);BufferList.push_back(p4);BufferList.push_back(p5);
HANDLE hThread1 = CreateThread(NULL, 0, Jobs_scheduler, NULL, 0, NULL);HANDLE hThread2 = CreateThread(NULL, 0, CPU_scheduler, NULL, 0, NULL);while(true)
{
if(num < 7)
BufferList.push_back(Program(num++, “156789”));}
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块来调度进程的过程，以及按照优先权进行排序的算法实现。对操作系统有了进一步的认识，后面会更加努力学习，掌握这门学科。 一．实验目的 用高级语言编写和调实一个进程调度程序，以加深对进程的概念及进程调度算法的理解． 二．实验要求：设计一个有 N个进程并发执行的进程调度程序。三．算法讲解 进程调度算法：采用最高优先数优先的调度算法（即把处理机分配给优先数最高的进程）和先来先服务算法以及时间片轮转法。 每个进程有一个进程控制块（PCB）表示。进程控制块可以包含如下信息：进程名、优先数、到达时间、需要运行时间、已用CPU时间、进程状态等等。 进程的优先数及需要的运行时间可以事先人为地指定（也可以由随机数产生）。进程的到达时间为进程输入的时间。 进程的运行时间以时间片为单位进行计算。每个进程的状态可以是就绪 W（Wait）、运行R（Run）、或完成F（Finish）三种状态之一。 就绪进程获得 CPU后都只能运行一个时间片。用已占用CPU时间加1来表示。 如果运行一个时间片后，进程的已占用 CPU时间已达到所需要的运行时间，则撤消该进程，如果运行一个时间片后进程的已占用CPU时间还未达所需要的运行时间，也就是进程还需要继续运行，此时应将进程的优先数减1（即降低一级），然后把它插入就绪队列等待CPU。每进行一次调度程序都打印一次运行进程、就绪队列、以及各个进程的 PCB，以便进行检查。重复以上过程，直到所要进程都完成为止。四．实验报告要求 1．写出实验目的： 2。写出实验要求： 3。写出实验内容：（包括算法描述，程序流程图及给出部分实验结果及结果分析）4。实验心得体会。 附：进程调度源程序如下： /*jingchendiaodu.c*/ #include “stdio.h” #include 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);} disp(PCB * pr)/*建立进程显示函数,用于显示当前进程*/ { printf(“n qname t state t super t ndtime t runtime n”);printf(“|%st”,pr->name);printf(“|%ct”,pr->state);printf(“|%dt”,pr->super);printf(“|%dt”,pr->ntime);printf(“|%dt”,pr->rtime);printf(“n”);} check()/* 建立进程查看函数 */ { PCB* pr;printf(“n **** 当前正在运行的进程是:%s”,p->name);/*显示当前运行进程*/ disp(p);pr=ready;printf(“n ****当前就绪队列状态为:n”);/*显示就绪队列状态*/ while(pr!=NULL){ disp(pr);pr=pr->link;} } destroy()/*建立进程撤消函数(进程运行结束,撤消进程)*/ { printf(“n 进程 [%s] 已完成.n”,p->name);free(p); 1.多核CPU调度算法 1.1全局队列调度算法 操作系统维护一个全局的任务等待队列，每个进程在执行阶段可以使用全部的处理器资源。当系统中有一个CPU核心空闲时，操作系统就从全局任务等待队列中选取Ready进程开始在此核心上执行。 优点：CPU核心利用率较高，能保证全局资源的充分利用。 缺点：多处理器同时查找工作时，可能会降低处理器效率。且同一进程可能在不同内核上执行，造成的进程迁移开销较大。1.2局部队列调度算法 操作系统为每个CPU内核维护一个局部的任务等待队列，将所有进程分配到与处理器对应的进程队列中。当系统中有一个CPU内核空闲时，便从该核心的任务等待队列中选取恰当的任务执行。 优点：充分利用局部缓存，降低了进程迁移的开销。任务基本上无需在多个CPU核心间切换，有利于提高CPU核心局部Cache命中率。目前多数多核CPU操作系统采用的是基于全局队列的任务调度算法。 缺点：可能造成某些处理器超负荷，而某些处理器空闲，即资源分配不均衡不充分，引起全局资源的不充分利用。2.简单单核CPU调度算法 2.1 先到先服务调度算法：FCFS（first-come,first-served） 当一个进程进入到Ready队列，其PCB就被链接到队列的尾部。当CPU空闲时，CPU被分配给位于队列头的进程（即当前Ready队列中已等待时间最长的进程）。接着，该运行进程从队列中被删除。 缺点：对于一个进程队列，其总的周转时间太长，且当进程的I/O较为密集时，效率将会变得相当低，CPU利用率也会变得很低。 优点：实现方式简单，适用于长程调度和处理器密集的进程调度。常与优先级策略结合提供一种更有效率的调度方法。 2.2 最短作业优先调度算法：SJF（shortest-job-first） SJF是一种非抢占式的调度算法，其实现原则是取Ready队列中处理时间最短的进程加载入CPU，进入CPU执行的进程执行完后才释放CPU，然后加载第二个进程进入CPU执行。 缺点：忽视了作业等待时间，会出现starvation现象，且作业执行时间无法提前知道，也很难预估。 优点：算法实现简单，能有效地降低作业的平均等待时间，提高系统吞吐量，是理论上的最优调度算法。 2.3 最短剩余时间优先调度算法：SRTF（Shortest Remaining Time First）SRTF调度算法是抢占式的SJF调度算法，调度程序总是首先选择预期剩余时间最短的进程加载进入CPU执行。 缺点：总是选择预期剩余时间最短的进程，会造成starvation现象。有处理时间预估，效率不足够高。 优点：不偏向长进程，没有额外的中断，因此开销较低。且对于一个进程队列，总的周转时间较短，执行效率较高，对短进程的响应较快。2.4 优先级调度算法 每个进程都有一个自己的优先级，Ready队列采用优先级队列实现，CPU每次取Ready队列队首的进程。通常情况，当两个进程的优先级相同时，我们在相同优先级的进程之间采用FCFS调度算法。优先级可以通过内部或外部方式来定义。 缺点：会出现starvation现象（也称无穷阻塞），且不适用于分时系统或交互式事务处理环境。 优点：主要用于批处理系统中，也可用于某些对实时性要求不严的实时系统中。可以采用老化技术，每个进程执行以后其优先级降低，以此来克服starvation的缺点。2.5 轮转法调度算法 轮转法（RR）调度算法是专门为分时系统设计的，是一种基于时钟的抢占策略。定义一个小时间单元，称为时间量或时间片。时间片通常为10ms到100ms。将Ready队列作为循环队列处理。CPU调度程序循环就需队列，为每个进程分配不超过一个时间片间隔的CPU。如果上下文切换时间约为时间片的10%，那么约10%的CPU时间会浪费在上下文切换上。 缺点：时间片长度设计较难，当时间片长度过大时，会退化成FCFS调度算法。调度I/O密集型进程时效率较低。由于轮询调度在调度过程中不考虑瞬时信道条件，因此它将导致较低的整体系统性能。 优点：对不同的分组业务流队列进行同样的无差别的循环调度服务，对于等长业务流队列是公平的，不存在starvation现象。2.6 最高响应比优先调度算法 首先需要理解一个概念，叫作响应比。响应比的计算表达式为 其中R为响应比，w为等待处理器的时间，s为预计服务的时间。当进程被立即调用时，R等于归一化周转时间。 调度算法的过程是，当进程完成执行或被阻塞时，选择R值最大的Ready进程加载进入CPU执行。 缺点：需要预估服务时间s，效率不太高。优点：能克服starvation现象。3.复杂单核CPU调度算法 3.1 多级队列调度算法（multilevel queue-scheduling algorithm）将Ready队列分成多个独立的队列，对Ready队列和每个独立的队列采用不同的调度算法进行执行。常用的方式是，Ready队列采用优先级调度算法，不同队列根据实际情况采用合适的调度算法即可。 优点：综合了多种调度算法，避免了starvation现象，最大限度地提高了调度效率，也提高了CPU利用率。3.2 多级反馈队列调度算法 UNIX OS采用的调度算法。其详细过程如下： 1.进程在进入待调度的队列等待时，首先进入优先级最高的Q1等待。 2.首先调度优先级高的队列中的进程。若高优先级中队列中已没有调度的进程，则调度次优先级队列中的进程。例如：Q1,Q2,Q3三个队列，只有在Q1中没有进程等待时才去调度Q2，同理，只有Q1,Q2都为空时才会去调度Q3。 3.对于同一个队列中的各个进程，按照时间片轮转法调度。比如Q1队列的时间片为N，那么Q1中的作业在经历了N个时间片后若还没有完成，则进入Q2队列等待，若Q2的时间片用完后作业还不能完成，一直进入下一级队列，直至完成。 4.在低优先级的队列中的进程在运行时，又有新到达的作业，那么在运行完这个时间片后，CPU马上分配给新到达的作业（抢占式）。 优点：既能使高优先级的作业得到响应又能使短作业(进程)迅速完成。4.多核CPU调度算法与单核CPU调度算法对比 从上面的不同CPU调度算法，我们不难发现，单核CPU调度算法是多核CPU调度算法的基础，多核CPU调度算法是单核CPU调度算法的延伸和综合使用。我以大篇幅介绍了单核CPU的调度算法，而以少量的篇幅介绍了多核CPU调度算法，其目的也在于说明此结论。 多核CPU调度算法中，无论是全局队列调度算法还是局部队列调度算法，其实现原理均可采用单核CPU调度算法中的某一个或一些综合起来实现。例如局部队列调度算法，每一个局部队列就相当于一个单核CPU调度队列，可以采用合适的单核CPU调度算法去实现。第三篇：操作系统 实验一 进程调度
第四篇：1.操作系统实验内容(进程调度)
第五篇：单核与多核的CPU调度算法
点击咨询 