单处理机的进程调度
- 格式：doc
- 大小：29.50 KB
- 文档页数：3
下载文档原格式
合集下载
进程调度算法总结
进程调度算法总结所谓进程，简单来说是计算机中的各种任务，那么计算机如何分配系统资源以供这些任务使⽤呢？此篇博客⽬的就是为⼤家整理⼀下⼏种常见进程调度算法。
进度调度就是按照⼀定的策略，动态地把处理机分配给处于就绪队列的进程，使之执⾏。
常见的进程调度算法：1、先来先服务和短作业（进程）优先调度算法2、⾼优先权优先调度算法3、基于时间⽚的轮转调度算法下⾯细说：1、先来先服务和短作业优先调度算法1.1、先来先服务调度算法这种调度算法由字⾯意思理解很直观，所谓先来先服务，就是谁先来先服务谁。
结合进程，先来先服务调度算法就是对于优先到达就绪队列的进程采取优先服务的策略，直到该进程运⾏结束或发⽣某事件导致阻塞才放弃处理机。
这种调度算法是⼀种最简单的调度算法，适⽤于作业和进程。
当⽤于作业时，先进⼊后备队列的作业先运⾏。
1.2、短作业（进程）优先调度算法短作业（进程）优先调度算法，是对短作业或短进程进⾏得调度算法。
何为短？就是估计运⾏时间短。
该算法从后备队列或就绪队列选择估计运⾏时间较短的作业或进程，将他们调⼊内存运⾏，直到该进程运⾏结束或发⽣某事件导致阻塞才放弃处理机重新进⾏调度。
2、⾼优先权优先调度算法2.1、优先权调度算法上述所说的两种调度算法，过于简单，当系统中有紧急作业或进程，且不满⾜先进队列或运⾏时间短时，这些作业或进程将很难得到资源。
那么对于这些作业或进程，⼜该怎么办呢？因此，⼜有了优先权调度算法，所谓优先权调度算法，顾名思义就是谁的优先权⾼，谁就西安得到资源得以运⾏。
进⼀步将算法分为以下两种：2.1.1、⾮抢占式优先权算法在这种⽅式下，系统⼀旦把处理机分配给就绪队列中优先权最⾼的进程后，该进程便⼀直执⾏下去，直⾄完成；或因发⽣某事件使该进程放弃处理机时，系统⽅可再将处理机重新分配给另⼀优先权最⾼的进程。
这种调度算法主要⽤于批处理系统中；也可⽤于某些对实时性要求不严的实时系统中。
2.1.2、抢占式优先权算法在这种⽅式下，系统同样是把处理机分配给优先权最⾼的进程，使之执⾏。
实验二--单处理器系统的进程调度
实验二–单处理器系统的进程调度
简介
在操作系统中，进程调度是非常重要的一项工作。
进程调度负责将CPU分配
给各个进程，使得每个进程都能够有机会占用CPU资源。
在单处理器系统中，CPU只有一个，因此进程调度是非常重要的。
本次实验将会探究单处理器系统的进程调度，了解各种进程调度算法的实现和
比较，利用模拟操作系统的实验平台进行实验。
实验目的
1.了解进程调度的基本概念和实现方法；
2.学习多种进程调度算法，并比较其优缺点；
3.熟悉模拟操作系统的实验环境，学习如何将算法实现到具体的系统中。
实验内容
进程调度的基本概念
进程调度是指将CPU资源分配给各个进程的过程。
在单处理器系统中，当有
多个进程需要使用CPU时，操作系统需要进行进程调度，使得每个进程都能够得
到CPU资源。
在进程调度中，需要考虑各个进程的优先级、进程的状态和进程的等待时间等
因素。
根据不同的调度算法，可以根据这些因素来确定哪个进程应该先占用CPU。
进程调度算法比较
常见的进程调度算法包括：
1.先来先服务算法（FCFS）
2.短作业优先算法（SJF）
3.优先级调度算法
4.时间片轮转算法（RR）
下面将对这些算法进行比较和介绍。
先来先服务算法（FCFS）
先来先服务算法是最简单的一种进程调度算法。
该算法将按照进程的到达时间
的先后顺序进行调度，先到达的进程先得到CPU资源。
这种算法的优点是实现简单，适用于短作业和计算密集型进程。
缺点是无法充分利用CPU资源，导致长作业需要等待较长时间才能被调度，容易产生。
单处理机系统的进程调度
单处理机系统的进程调度
编写程序完成单处理机系统中的进程调度，要求采用时间片轮转调度算法。
实现具体包括：首先确定进程控制块的内容和组成方式；然后完成进程创建原语和进程调度原语；最后编写主函数，对所做工作进行测试。
这个实验主要有三个问题：如何组织进程、如何创建进程和如何实现处理机调度。
进程控制块结构定义如下：
struct pcb
{
int name; //进程标识符
int status; //进程状态
int ax,bx,cx,dx; //进程现场信息，通用寄存器内容
int pc; //进程现场信息，程序计数器内容
int psw; //进程现场信息，程序状态字寄存器内容
int next; //下一个进程控制块的位置
}
存放进程控制块的区域：
#define n 10 //假定系统允许进程个数为10
struct pcb pcbarea[n]; //模拟进程控制块区域的数组
实验中指向运行进程的进程控制块指针、就绪队列指针和空闲进程控制块队列指针定义如下：
int run; //定义指向正在运行进程的进程控制块的指针struct
{ int head;
int tail
}ready; //定义指向就绪队列的头指针head和尾指针tail int pfree; //定义指向空闲进程控制块队列的指针。
用C语言模拟Linux操作系统下处理机调度实验报告
实验二：处理机调度一、实验目的：1、了解Linux下Emacs编辑器的使用方法，掌握各种常用的键盘操作命令；2、理解并掌握处理机调度算法。
二、实验内容及要求：在采用多道系统的设计程序中，往往有若干进程同时处于就绪状态。
当就绪状态进程数大于处理机数时，就必须按照某种策略来决定哪些进程优先占用处理机。
本实验模拟在单处理机情况下处理机调度。
1、优先调度算法实现处理机的调度：设计思路：1每个进程用一个进程控制块PCB来代表，进程控制块包括进程名(进程的标识、指针(按优先数的大小把进程连成队列，用指针指出下一个进程的进程控制块首地址，最后一个进程中的指针为"0"、要求运行时间、优先数、状态(就绪、结束；2每次运行处理机调度程序前，为每个进程确定它的"优先数"和"要求运行时间"；3把给定的进程按优先数的大小连成队列，用一单元指出队首进程；4每模拟执行一次进程，优先数减一，要求运行时间减一；5如果要求运行的时间>=0，再将它加入队列（按优先数的大小插入，重置队首标志）；如果要求运行的时间=0，那么把它的状态修改为结束，且推出队列；6若就绪队列不为空，重复上述，直到所有的进程都结束；7程序有显示和打印语句，每次运行后显示变化。
2、按时间片轮转法实现处理机调度：设计思路：1每个进程用一个进程控制块PCB来代表，进程控制块包括进程名(进程的标识、指针(把进程连成循环队列，用指针指出下一个进程的进程控制块首地址，最后一个进程中的指针指出第一个进程的进程控制块首地址、已运行时间、状态(就绪、结束；2每次运行处理机调度程序前，为每个进程确定它的"要求运行时间"；3用指针把给定的进程按顺序排成循环队列，用另一标志单元记录轮到的进程；4每模拟运行一次进程，已运行时间加一；5进程运行一次后，把该进程控制块的指针值送到标志单元，以指示下一个轮到的进程。
处理机管理有哪些主要功能
1、处理机管理有哪些主要功能？它们的主要任务是什么？答：处理机管理的主要功能是：进程管理、进程同步、进程通信和处理机调度；进程管理：为作业创建进程，撤销已结束进程，控制进程在运行过程中的状态转换。
进程同步：为多个进程（含线程）的运行进行协调。
通信：用来实现在相互合作的进程之间的信息交换。
处理机调度：（1）作业调度。
从后备队里按照一定的算法，选出若干个作业，为他们分配运行所需的资源（首选是分配内存）。
（2）进程调度：从进程的就绪队列中，按照一定算法选出一个进程，把处理机分配给它，并设置运行现场，使进程投入执行。
2、前趋图是一个有向无循环图，记为DAG，用于描述进程之间执行的前后关系。
3、试说明PCB 的作用，为什么说PCB 是进程存在的惟一标志？PCB 是进程实体的一部分，是操作系统中最重要的记录型数据结构。
作用是使一个在多道程序环境下不能独立运行的程序，成为一个能独立运行的基本单位，成为能与其它进程并发执行的进程。
OS是根据PCB对并发执行的进程进行控制和管理4、试说明进程在三个基本状态之间转换的典型原因1）就绪状态→执行状态：进程分配到CPU资源2）执行状态→就绪状态：时间片用完3）执行状态→阻塞状态：I/O请求4）阻塞状态→就绪状态：I/O完5、为什么要在OS 中引入线程？在操作系统中引入线程，则是为了减少程序在并发执行时所付出的时空开销，使OS具有更好的并发性，提高CPU的利用率。
进程是分配资源的基本单位,而线程则是系统调度的基本单位。
6、试说明线程具有哪些属性1)轻型实体2）独立调度和分派的基本单位3）可并发执行4）共享进程资7、试从调度性，并发性，拥有资源及系统开销方面对进程和线程进行比较1）调度性。
线程在OS 中作为调度和分派的基本单位，进程只作为资源拥有的基本单位。
2）并发性。
进程可以并发执行，一个进程的多个线程也可并发执行。
3）拥有资源。
进程始终是拥有资源的基本单位，线程只拥有运行时必不可少的资源，本身基本不拥有系统资源，但可以访问隶属进程的资源。
处理机调度实验报告1
实现思想：
设置多个就绪队列，各个队列优先级逐个降低，各个队列时间片逐个增加，优先级越高的队列执行时间片就越短，一般时间片按倍增规则，例如，第二队列的时间片要比第一个队列的时间片长一倍，……，第i+1个队列的时间片要比第i个队列的时间片长一倍，整合了时间片、FCFS、优先级三种机制。
三．实验过程及内容：(对程序代码进行说明和分析，越详细越好，代码排版要整齐，可读性要高)
time+=pcbdata1[t_ready[0]].time_need;
j=time-pcbdata1[t_ready[0]].time_start;
k=(float)j/pcbdata1[t_ready[0]].time_need;
t_order[0]=0;
printf("完成时间--%d,周转时间--%d,带权周转时间--%.1f\n",time,j,k);
}
}
//**************调度函数
void FCFS()
{
int i,j,temp;
double k;
for(i=0;i<num;i++)
{order[i]=pcbdata[i].time_start;
ready[i]=i;
}
for(i=0;i<num;i++) //按到达时间排序
for(j=i+1;j<num;j++)
t_ready[i]=ready[i];
}
time=order[0];
for(l=0;l<num1;l++){
//判断到达的进程数，用temp_num存放
for(i=0;i<num&&pcbdata1[ready[i]].time_start<=time;i++)
设置多个就绪队列，各个队列优先级逐个降低，各个队列时间片逐个增加，优先级越高的队列执行时间片就越短，一般时间片按倍增规则，例如，第二队列的时间片要比第一个队列的时间片长一倍，……，第i+1个队列的时间片要比第i个队列的时间片长一倍，整合了时间片、FCFS、优先级三种机制。
三．实验过程及内容：(对程序代码进行说明和分析，越详细越好，代码排版要整齐，可读性要高)
time+=pcbdata1[t_ready[0]].time_need;
j=time-pcbdata1[t_ready[0]].time_start;
k=(float)j/pcbdata1[t_ready[0]].time_need;
t_order[0]=0;
printf("完成时间--%d,周转时间--%d,带权周转时间--%.1f\n",time,j,k);
}
}
//**************调度函数
void FCFS()
{
int i,j,temp;
double k;
for(i=0;i<num;i++)
{order[i]=pcbdata[i].time_start;
ready[i]=i;
}
for(i=0;i<num;i++) //按到达时间排序
for(j=i+1;j<num;j++)
t_ready[i]=ready[i];
}
time=order[0];
for(l=0;l<num1;l++){
//判断到达的进程数，用temp_num存放
for(i=0;i<num&&pcbdata1[ready[i]].time_start<=time;i++)
第8章 进程调度
❖ 假定当前系统中没有两个进程具有相同的优先权以及其后 也没有其他进程进入就绪队列，如果prit(pk)＜ prit(pi)，pk运 行，pi等待，则有
Tw(pi) = ∑Ω 。
▪ 显然一个进程的期望等待时间是指一个
进程花在就绪队列中的平均等待服务的 时间。
4
4.0
1
5.0
4
P3
P2
P4
78
12
16
▪平均等待时间 = (0 + 6 + 3 + 7)/4 = 4
强占SJF的实例
▪ 强占SJF调度算法
进程 P1 P2 P3 P4
▪ Gantt 图表如下 ：
到达时间 0.0 2.0 4.0 5.0
需要服务时间 7 4 1 4
P1
P2 P3 P2
P4
时间 0 2
FCFS 和SJF例题
[例8.1]: 试分别计算图8.2(a)和(b)所示的就绪队列中 进程的期望周转时间和期望等待时间。 假定就绪
队列中有4个进程，如下图所示：
进程 服务时间
p0
30
p1
10
p2
40
p3
20
▪ 下面分别计算图8.2(a)和(b)中所示的就绪队列中进程的期望
周转时间和期望等待时间。
列，因为它要求进程的抵达速度和CPU 的运行速度一样快，目前系统还不能长 期这样运行。
8.2 非强占方式调度算法
▪ 非强占调度算法是不强迫一个已经分配到CPU的进
程改变就绪状态。
▪ 在非强占调度算法的系统中不存在从CPU直接返回
到就绪队列的路径。见附图1。
返回就绪队列的路径
就绪队列
┉
调度程序
Tw(pi) = ∑Ω 。
▪ 显然一个进程的期望等待时间是指一个
进程花在就绪队列中的平均等待服务的 时间。
4
4.0
1
5.0
4
P3
P2
P4
78
12
16
▪平均等待时间 = (0 + 6 + 3 + 7)/4 = 4
强占SJF的实例
▪ 强占SJF调度算法
进程 P1 P2 P3 P4
▪ Gantt 图表如下 ：
到达时间 0.0 2.0 4.0 5.0
需要服务时间 7 4 1 4
P1
P2 P3 P2
P4
时间 0 2
FCFS 和SJF例题
[例8.1]: 试分别计算图8.2(a)和(b)所示的就绪队列中 进程的期望周转时间和期望等待时间。 假定就绪
队列中有4个进程，如下图所示：
进程 服务时间
p0
30
p1
10
p2
40
p3
20
▪ 下面分别计算图8.2(a)和(b)中所示的就绪队列中进程的期望
周转时间和期望等待时间。
列，因为它要求进程的抵达速度和CPU 的运行速度一样快，目前系统还不能长 期这样运行。
8.2 非强占方式调度算法
▪ 非强占调度算法是不强迫一个已经分配到CPU的进
程改变就绪状态。
▪ 在非强占调度算法的系统中不存在从CPU直接返回
到就绪队列的路径。见附图1。
返回就绪队列的路径
就绪队列
┉
调度程序
操作系统单处理机系统的进程调度
操作系统单处理机系统的进程调度第一篇：操作系统单处理机系统的进程调度一.实验内容描述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知道该进程页目录的位置。
第3章_进程调度
二、常用的调度方法
1. 先来先服务（FCFS算法） 按照作业提交或进程变为就绪状态的先后次序，分派CPU； 当前作业或进程占用CPU，直到执行完或阻塞，才主动地出让 CPU。
特点：非常简单，易于实现；但对短作业而言，带权周转时 间可能太大。
按FCFS原则的进程调度
进程名 到达时间 服务时间 开始时 间 完成时 间 周转时 间 带权周 转时间
A
B
0
2
3
6
0 3
3 9 13
3
1.00
7
9 12 12
1.17
2.25 2.40 6.00
C
D E
4
6 8
4
5 2
9
13 18
18
20
2.短作业（进程）优先 对执行时间短的作业（进程）优先分派处理机。
特点：
•比FCFS改善了平均周转时间和平均带权周转时间，缩短作业
的等待时间，提高了系统的吞吐量； •对长作业非常不利，可能长时间得不到执行； •难以准确估计作业（进程）的执行时间，从而影响调度性能 按什么标准： 时间？ 什么是短作业？ 以前没有执行过！ 程序长度？
仅当较高优先级的队列为空，才调度较低优先级的队列 中的进程执行。如果进程执行时有新进程进入较高优先级的 队列，则抢先执行新进程，并把被抢先的进程投入原队列的 末尾。
8、公平分享调度策略 1986年Bach提出：按进程组（用户）分配CPU。 以前的做法，按进程分配CPU： A用户：1个进程 ，10%的CPU分额 B用户：6个进程 ，60%的CPU分额 C用户：3个进程 ，30%的CPU分额 现在 ：每个用户都按1/3的比例分配CPU A用户的每个进程，1/3的CPU分额 B用户的每个进程，1/18的CPU分额 C用户的每个进程，1/9的CPU分额
操作系统第3章 处理机调度(调度)
3.2 调度算法
进程调度的核心问题就是采用什么样的算法将处 理机分配给进程，常用的进程调度算法有：
先来先服务调度算法
短作业/进程优先调度算法
优先权调度算法
高响应比优先调度算法
时间片轮转调度算法
多级队列调度算法
多级反馈队列调度算法
返回目录
一、先来先服务调度算法FCFS
基本思想:按照进程进入就绪队列的 先后次序来分配处理机。
抢占（剥夺）方式
非抢占方式
一旦把处理机分配给某进程后，便让该进程 一直执行，直到该进程完成或因某事件而被 阻塞，才再把处理机分配给其它进程，不允 许进程抢占已分配出去的处理机。
特点：实现简单，系统开销小，常用于批处 理系统；但不利于处理紧急任务，故实时、 分时系统不宜采用。
抢占方式
允许调度程序根据某种原则（时间片、优 先权、短进程优先），停止正在执行的进 程，而将处理机重新分配给另一进程。
调度算法（太长---FCFS）； 上下文切换（太短---上下文切换频繁）； 平均周转时间。
短时间片增加上下文切换频率
周转时间随时间片变化
三、时间片轮转调度算法—例(1)
EG： 进程 到达时间
P1
0
P2
2
P3
4
P4
5
RR（时间片为1）
服务时间
7 4 1 4
P1 P2 P1 P2 P3 P1 P4 P2 P1 P4 P2 P1 P4 P1 P4
FCFS SPF-非 SPF-抢
周转T 124.25 100
75.75
等待T 74.25 49.5
25.25
二、SJF/SPF ——抢占式
到达顺序: 进程名 到达时间 服务时间
- 1、下载文档前请自行甄别文档内容的完整性，平台不提供额外的编辑、内容补充、找答案等附加服务。
- 2、"仅部分预览"的文档,不可在线预览部分如存在完整性等问题,可反馈申请退款(可完整预览的文档不适用该条件!)。
- 3、如文档侵犯您的权益，请联系客服反馈,我们会尽快为您处理(人工客服工作时间：9:00-18:30)。
#include “stdio.h”
#define running 1 // 用running表示进程处于运行态
#define aready 2 // 用aready表示进程处于就绪态
#define blocking 3 // 用blocking表示进程处于阻塞态
#define sometime 5 // 用sometime表示时间片大小
#define n 10 //假定系统允许进程个数为n
struct
{
int name; //进程标识符
int status; //进程状态
int ax,bx,cx,dx ; //进程现场信息，通用寄存器内容
int pc ; //进程现场信息，程序计数器内容
int psw; //进程现场信息，程序状态字内容
int next; //下一个进程控制块的位置
}pcbarea[n]; //模拟进程控制块区域的数组
int PSW, AX,BX,CX,DX , PC ,TIME ; //模拟寄存器
int run; //定义指向正在运行进程的进程控制块的指针struct
{
int head;
int tail;
}ready; //定义就绪队列的头指针head和尾指针tail int pfree; //定义指向空闲进程控制块队列的指针
scheduling( ) //进程调度函数
{
int i;
if (ready.head==-1) //空闲进程控制块队列为空，退出
{
printf(“无就绪进程\n”);
return;
}
i=ready.head; //就绪队列头指针赋给i
ready.head=pcbarea[ready.head].next; //就绪队列头指针后移
if(ready.head==-1) ready.tail=-1; //就绪队列为空，修正尾指针ready.tail
pcbarea[i].status=running; //修改进程控制块状态
TIME=sometime; //设置相对时钟寄存器
//恢复该进程现场信息
AX=pcbarea[run].ax;
BX=pcbarea[run].bx;
CX=pcbarea[run].cx;
DX=pcbarea[run].dx;
PC=pcbarea[run].pc;
PSW=pcbarea[run].psw;
run=i;
}//进程调度函数结束
create(int x) //进程创建函数
{
int i;
if(pfree==-1) //空闲进程控制块队列为空
{
printf(“无空闲进程控制块，进程创建失败\n”);
return;
}
i=pfree; //取空闲进程控制块队列的第一个
pfree=pcbarea[pfree].next; // pfree后移
//填写该进程控制块的内容
pcbarea[i].name=x;
pcbarea[i].status=aready;
pcbarea[i].ax=x;
pcbarea[i].bx=x;
pcbarea[i].cx=x;
pcbarea[i].dx=x;
pcbarea[i].pc=x;
pcbarea[i].psw=x;
if (ready.head!=-1) //就绪队列不为空时，挂入就绪队列的方式{
pcbarea[ready.tail].next=i;
ready.tail=i;
pcbarea[ready.tail].next=-1;
}
else //就绪队列为空时，挂入就绪队列的方式{
ready.head=i;
ready.tail=i;
pcbarea[ready.tail].next=-1;
}
}//进程创建函数结束
main()
{ //系统初始化
int num,i,j;
run=ready.head=ready.tail =-1;
pfree=0;
for(j=0;j<n-1;j++)
pcbarea[j].next=j+1;
pcbarea[n-1].next=-1;
printf(“输入进程编号（避免编号冲突，以负数输入结束，最多可以创建10个进程）：\n”); scanf(“%d”,&num);
while(num>=0)
{
create(num) ;
scanf(“%d”,&num) ;
}
scheduling(); //进程调度
if(run!=-1)
{
printf(“进程标识符进程状态寄存器内容：ax bx cx dx pc psw:\n”);
printf(“%8d%10d%3d%3d%3d%3d%3d%3d\n”, pcbarea[run].name, pcbarea[run].status, pcbarea[run].ax, pcbarea[run].bx, pcbarea[run].cx, pcbarea[run].dx, pcbarea[run].pc, pcbarea[run].psw);
}
}//main()结束。