大家好，又见面了，我是你们的朋友全栈君。
【实验目的】
进程管理是操作系统中的重要功能，用来创建进程、撤消进程、实现进程状态转换，它提供了在可运行的进程之间复用CPU的方法。在进程管理中，进程调度是核心，因为在采用多道程序设计的系统中，往往有若干个进程同时处于就绪状态，当就绪进程个数大于处理器数目时，就必须依照某种策略决定哪些进程优先占用处理器。本实验模拟在单处理器情况下的进程调度，目的是加深对进程调度工作的理解，掌握不同调度算法的优缺点。
【实验内容】
选择两个调度算法作为两个实验题目，实现处理器调度。
【实验原理】
（1）进程控制块
为了管理和控制进程，系统在创建每一个进程时，都为其开辟一个专用的存储区，用以随时记录它在系统中的动态特性。而当一个进程被撤消时，系统就收回分配给它的存储区。通常，把这一存储区称为该进程的“进程控制块”（Process Control Block）。
由于PCB是随着进程的创建而建立，随着进程的撤消而取消的，因此系统是通过PCB来“感知”一个个进程的，PCB是进程存在的唯一标志。
（2）进程控制块队列
在多道程序设计环境里，同时会创建多个进程。当计算机系统只有一个CPU时，每次只能让一个进程运行，其他的进程或处于就绪状态，或处于阻塞状态。为了对这些进程进行管理，操作系统要做三件事。
①把处于相同状态的进程的PCB，通过各自的队列指针链接在一起，形成一个个队列。通常有运行队列、就绪队列、阻塞队列。
②为每一个队列设立一个队列头指针，它总是指向排在队列之首的进程的PCB。
③排在队尾的进程的PCB，它的“队列指针”项内容应该为“NULL”，或一个特殊的符号，以表示这是该队的队尾PCB。
在单CPU系统中，任何时刻都只有一个进程处于运行状态，因此运行队列中只能有一个PCB；系统中所有处于就绪状态的进程的PCB排成一队，称其为“就绪队列”。一般地，就绪队列中会有多个进程的PCB排在里面，它们形成处理机分配的候选对象。如果就绪队列里没有PCB存在，则称该队列为空；所有处于阻塞状态进程的PCB，应该根据阻塞的原因进行排队，每一个都称为一个“阻塞队列”。比如等待磁盘输入/输出进程的PCB排成一个队列，等待打印机输出进程的PCB排成一个队列等。所以，系统中可以有多个阻塞队列，每个阻塞队列中可以有多个进程的PCB，也可以为空。
（3）进程调度算法
进程调度算法用于确定就绪队列中的哪一个进程即将获得CPU。常用的进程调度算法有先来先服务法、时间片轮转法、优先数法等。
①先来先服务调度算法
先来先服务调度算法的基本思想是：以到达就绪队列的先后次序为标准来选择占用处理机的进程。一个进程一旦占有处理机，就一直使用下去，直至正常结束或因等待某事件的发生而让出处理机。采用这种算法时，应该这样来管理就绪队列：到达的进程的PCB总是排在就绪队列末尾；调度程序总是把CPU分配给就绪队列中的第一个进程使用。
②时间片轮转法
时间片轮转调度算法的基本思想是：为就绪队列中的每一个进程分配一个称为“时间片”的时间段，它是允许该进程运行的时间长度。在使用完一个时间片后，即使进程还没有运行完毕，也要强迫其释放处理机，让给另一个进程使用。它自己则返回到就绪队列末尾，排队等待下一次调度的到来。采用这种调度算法时，对就绪队列的管理与先来先服务完全相同。主要区别是进程每次占用处理机的时间由时间片决定，而不是只要占用处理机就一直运行下去，直到运行完毕或为等待某一事件的发生而自动放弃。
③优先数调度算法
优先数调度算法的基本思想是：为每一个进程确定一个优先数，进程就绪队列按照优先数排序。
如何确定进程的优先数（也就是进程的优先级）？可以从如下几个方面考虑。
ⅰ）根据进程的类型。系统中既有系统进程，又有用户进程。系统进程完成的任务是提供系统服务，分配系统资源，因此，给予系统进程较高的优先数能够提高系统的工作效率。
ⅱ）根据进程执行任务的重要性。重要性和紧迫性高的进程应当被赋予较高的优先级。
ⅲ）根据进程程序的性质。一个CPU繁忙的进程，由于需要占用较长的运行时间，影响系统整体效率的发挥，因此只能给予较低的优先数。一个I/O繁忙的进程，给予它较高的优先数后，就能充分发挥CPU和外部设备之间的并行工作能力。
ⅳ）根据对资源的要求。系统资源有处理机、内存储器和外部设备等。可以按照一个进程所需资源的类型和数量，确定它的优先数。比如给予占用CPU时间短或内存容量少的进程以较高的优先数，这样可以提高系统的吞吐量。
ⅴ）根据用户的请求。系统可以根据用户的请求，给予它的进程很高的优先数，作“加急”处理。
④多级队列调度算法
多级队列调度算法也称多级反馈队列调度算法，它是时间片调度算法与优先数调度算法的结合。实行这种调度算法时，系统中将维持多个就绪队列，每个就绪队列具有不同的调度级别，可以获得不同长度的时间片。例如，系统维持N个就绪队列，第1级就绪队列中进程的调度级别最高，可获得的时间片最短，第N级就绪队列中进程的调度级别最低，可获得的时间片最长。
具体的调度方法是：创建一个新进程时，它的PCB将进入第1级就绪队列的末尾。对于在第1级到第N-1级队列中的进程，如果在分配给它的时间片内完成了全部工作，那么就撤离系统；如果在时间片没有用完时提出了输入/输出请求或要等待某事件发生，那么就进入相应的阻塞队列里等待。在所等待的事件出现时，仍回到原队列末尾，参与下一轮调度（也就是每个队列实行先来先服务调度算法）；如果用完了时间片还没有完成自己的工作，那么只能放弃对CPU的使用，降到低一级队列的末尾，参与那个队列的调度。对位于最后一个队列里的进程，实行时间片轮转调度算法。
整个系统最先调度1级就绪队列；只有在上一级就绪队列为空时，才去下一级队列调度。当比运行进程更高级别的队列中到达一个进程（可以肯定，在此之前比运行进程级别高的所有队列全为空）时，系统将立即停止当前运行进程的运行，让它回到自己队列的末尾，转去运行级别高的那个进程。
可以看出，多级队列调度算法优先照顾I/O繁忙的进程。I/O繁忙的进程在获得一点CPU时间后就会提出输入/输出请求，因此它们总是被保持在1、2级等较前面的队列中，总能获得较多的调度机会。对于CPU繁忙的进程，它们需要较长的CPU时间，因此会逐渐地由级别高的队列往下降，以获得更多的CPU时间，它们“沉”得越深，被调度到的机会就越少。但是，一旦被调度到，就会获得更多的CPU时间。
【程序代码】
数据项 | 作用 |
|---|---|
next | 前向指针，指向下一个进程控制块，用来构成进程队列 |
process_name | 进程名称 |
process_number | 进程号，当进程有相同名称时，用来区分进程 |
process_start_moment | 进程启动时刻 |
process_need_time | 进程要求运行时间 |
process_time_slice | 时间片 |
process_priority | 优先数 |
图1 进程控制块的数据结构 | |
进程调度算法
①编译命令
gcc process_schedule.cpp –o process_schedule.o –lcurses
②程序清单
头文件process_schedule.h
代码语言：javascript复制#include <curses.h>
#include <stdlib.h>
#include <unistd.h>
#include <string.h>
#define MAX_PROCESS 10
int process_number=0;
typedef struct pcb{
struct pcb *next;
char process_name[20];
int process_number;
int process_start_moment;
int process_need_time;
int process_time_slice;
int process_priority;
}PCB;
PCB pcb_table[MAX_PROCESS];
PCB *pcb_run=NULL;
PCB *pcb_free=NULL;
PCB *pcb_ready=NULL;
PCB *pcb_ready_rear=NULL;
PCB *pcb_blocked=NULL;
PCB *pcb_blocked_rear=NULL;
void init_pcb_table();
void display_process_queue(PCB *queue);
PCB *create_process();
void block_process_by_name();
void wakeup_process();
void FCFS();
void RR();
void HPF();
void MFBQ();源文件process_schedule.cpp
代码语言：javascript复制#include "process_schedule.h"
int main(int argc,char *argv[]){
char select;
initscr();
init_pcb_table();
bool end=false;
while(!end){
clear();
refresh();
printw("|----------MAIN MENU-------------|n");
printw("| 1:first come first served |n");
printw("| 2:round robin |n");
printw("| 3:highest priority first |n");
printw("| 4:multi_level feedback queue |n");
printw("| 5:display ready process queue |n");
printw("| 6:display blocked process queue |n");
printw("| 7:display running queue |n");
printw("| a:create a process |n");
printw("| b:delete a process |n");
printw("| c:block a process |n");
printw("| d:wakeup a process |n");
printw("| 8:exit |n");
printw("|-----------------------------------|n");
printw("select a function(1~8,a~d):");
refresh();
do{
select=(char)getch();
refresh();
}while(!((49<=select&&select<=56)||(97<=select&&select<=100)));
clear();
refresh();
switch(select){
case '1':
FCFS();
break;
case '2':
RR();
break;
case '3':
HPF();
break;
case '4':
MFBQ();
break;
case '5':
printw(" ready queuen");
display_process_queue(pcb_ready);
break;
case '6':
printw(" blocked queuen");
display_process_queue(pcb_blocked);
break;
case '7':
printw(" running queuen");
display_process_queue(pcb_run);
break;
case 'a':
create_process();
break;
case 'b':
break;
case 'c':
block_process_by_name();
break;
case 'd':
wakeup_process();
break;
case '8':
printw("n");
end=true;
}
printw("press any key to continue.n");
getch();
refresh();
}
endwin();
return 0;
}
void init_pcb_table()
{
int i=0;
pcb_free=&pcb_table[0];
pcb_table[MAX_PROCESS-1].next=NULL;
pcb_table[MAX_PROCESS-1].process_number=0;
pcb_table[MAX_PROCESS-1].process_start_moment=0;
pcb_table[MAX_PROCESS-1].process_need_time=0;
pcb_table[MAX_PROCESS-1].process_time_slice=0;
pcb_table[MAX_PROCESS-1].process_priority=0;
strcpy(pcb_table[MAX_PROCESS-1].process_name,"");
for(i=0;i<MAX_PROCESS-1;i ){
pcb_table[i].next=&pcb_table[i 1];
pcb_table[i].process_number=0;
pcb_table[i].process_start_moment=0;
pcb_table[i].process_need_time=0;
pcb_table[i].process_time_slice=0;
pcb_table[i].process_priority=0;
strcpy(pcb_table[i].process_name,"");
}
}
void display_process_queue(PCB *queue)
{
PCB *p=queue;
int i=4;
move(1,1);
printw("|----------|----------|----------|----------|----------|----------|n");
move(2,1);
printw("| name | number | start | need | slice | priority |n");
move(3,1);
printw("|----------|----------|----------|----------|----------|----------|n");
while(p!=NULL){
move(i,1);
printw("| ");
printw("%s",p->process_name);
move(i,12);
printw("| ");
printw("%d",p->process_number);
move(i,23);
printw("| ");
printw("%d",p->process_start_moment);
move(i,34);
printw("| ");
printw("%d",p->process_need_time);
move(i,45);
printw("| ");
printw("%d",p->process_time_slice);
move(i,56);
printw("| ");
printw("%d",p->process_priority);
move(i,67);
printw("|");
p=p->next;
i ;
}
move(i,1);
printw("|----------|----------|----------|----------|----------|----------|n");
refresh();
}
void FCFS()
{
if(pcb_ready==NULL)
{
printw("ready queue is empty,no process to run.n");
}
else
{
pcb_run=pcb_ready;
if(pcb_ready==pcb_ready_rear)
{
pcb_ready=pcb_ready_rear=NULL;
}
else
{
pcb_ready=pcb_ready->next;
}
pcb_run->next=NULL;
}
}
void RR()
{
}
void HPF()
{
}
void MFBQ()
{
}
PCB *create_process()
{
PCB *p=pcb_free;
if(p==NULL)
return NULL;
else
{
pcb_free=pcb_free->next;
clear();
refresh();
printw("please enter the following fields:n");
printw("| name | start_moment | need_time | time_slice | priority |n");
scanw("%s%d%d%d%d",
p->process_name,
&(p->process_start_moment),
&(p->process_need_time),
&(p->process_time_slice),
&(p->process_priority));
p->process_number=(process_number 1)0;
process_number ;
p->next=NULL;
if(pcb_ready==NULL)
pcb_ready=pcb_ready_rear=p;
else
{
pcb_ready_rear->next=p;
pcb_ready_rear=p;
}
return p;
}
}
void block_process_by_name()
{
char process_name[20];
PCB *p=pcb_ready;
PCB *previous_p=pcb_ready;
if(p==NULL)
{
printw("ready queue is empty,no process can be blocked!n");
return;
}
display_process_queue(pcb_ready);
printw("enter the process name you want to block:n");
scanw("%s",process_name);
while(p!=NULL){
if(!strcmp(p->process_name,process_name))
break;
previous_p=p;
p=p->next;
}
if(p==NULL)
{
printw("no such a process in ready queue:%snyou typed the wrong namen",
process_name);
return;
}
else
{
if(p==pcb_ready_rear)
{
pcb_ready_rear=previous_p;
}
previous_p->next=p->next;
if(pcb_blocked==NULL)
{
pcb_blocked=pcb_blocked_rear=p;
p->next=NULL;
}
else
{
pcb_blocked_rear->next=p;
pcb_blocked_rear=pcb_blocked_rear->next;
p->next=NULL;
}
}
}
void wakeup_process()
{
PCB *p=pcb_blocked;
if(pcb_blocked==NULL)
{
printw("blocked queue is empty,no process needs to be wakeuped.n");
}
else{
if(pcb_blocked==pcb_blocked_rear)
pcb_blocked=pcb_blocked_rear=NULL;
else
pcb_blocked=pcb_blocked->next;
if(pcb_ready==NULL)
{
pcb_ready=pcb_ready_rear=p;
p->next=NULL;
}
else
{
pcb_ready_rear->next=p;
pcb_ready_rear=pcb_ready_rear->next;
p->next=NULL;
}
}
}//wakeup【实验结果】
【实验心得】
通过这次实验课，我了解了处理机四种调度算法先来先服务调度算法（FCFS）、优先数调度算法、基于时间片的轮转调度法和多级反馈队列调度算法。我所编写的是先来先服务和优先数调度算法。作业调度的主要任务就是根据JCB中的信息，检查系统中的资源能否满足作业队资源的要求，以及按照一定的调度算法，从外存的后备对列选取某些作业调入内存。在每次执行作业调度时，都需要做出以下两个决定:
a. 接纳多少个作业:接纳多少作业取决于多道程序度。而多道程序度取决于：计算机系统规模，运行速度，作业大小，以及能否获得较好的系统性能。
b. 接纳哪些作业: 选择哪些作业取决于，作业调度采用哪种算法。
版权声明：本文内容由互联网用户自发贡献，该文观点仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请发送邮件至 举报，一经查实，本站将立刻删除。
