进程调度算法设计_三种调度算法

进程调度算法设计_三种调度算法【实验目的】进程管理是操作系统中的重要功能,用来创建进程、撤消进程、实现进程状态转换,它提供了在可运行的进程之间复用CPU的方法。在进程管理中,进程调度是核心,因为在采用多道程序设计的系统中,往往有若干个进程同时处于就绪状态,当就绪进程个数大于处理器数目时,就必须依照某种策略决定哪些进程优先占用处理器。本实验模拟在单处理器情况下的进程调度,目的是加深对进程调度工作的理解,掌握不…

大家好,又见面了,我是你们的朋友全栈君。如果您正在找激活码,请点击查看最新教程,关注关注公众号 “全栈程序员社区” 获取激活教程,可能之前旧版本教程已经失效.最新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账号...

(0)


相关推荐

发表回复

您的电子邮箱地址不会被公开。

关注全栈程序员社区公众号