大家好,又见面了,我是你们的朋友全栈君。如果您正在找激活码,请点击查看最新教程,关注关注公众号 “全栈程序员社区” 获取激活教程,可能之前旧版本教程已经失效.最新Idea2022.1教程亲测有效,一键激活。
Jetbrains全系列IDE稳定放心使用
【实验目的】
进程管理是操作系统中的重要功能,用来创建进程、撤消进程、实现进程状态转换,它提供了在可运行的进程之间复用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
#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
#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 queue\n");
display_process_queue(pcb_ready);
break;
case '6':
printw(" blocked queue\n");
display_process_queue(pcb_blocked);
break;
case '7':
printw(" running queue\n");
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)%100;
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:%s\nyou typed the wrong name\n",
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. 接纳哪些作业: 选择哪些作业取决于,作业调度采用哪种算法。
发布者:全栈程序员-用户IM,转载请注明出处:https://javaforall.cn/189038.html原文链接:https://javaforall.cn
【正版授权,激活自己账号】: Jetbrains全家桶Ide使用,1年售后保障,每天仅需1毛
【官方授权 正版激活】: 官方授权 正版激活 支持Jetbrains家族下所有IDE 使用个人JB账号...