您所在位置：主题：操作系统C语言编程
yangyiyy001
[专家分：0] 发布于 2006-04-07 10:25:00
操作系统
一、常用的页面调度算法
（1）先进先出调度算法（FIFO）：该算法淘汰进入内存时间最长的页面，这是一种简单的页面淘汰算法。FIFO算法有可能产生异常现象（Belady异常），即当分给一个进程的页面数增多时，缺页中断次数反而增加。
（2）最近最少使用调度算法（LRU）：该算法淘汰上一次访问时间距当前时间间隔最长的页面。该算法是依据局部性特征提出的，认为末被使用时间最长的页面，那么它很可能最近不被使用，故应淘汰。LRU算法的实现开销较大，需要有硬件支持。
（3）最佳更换算法（OPT）：该算法淘汰今后不再访问的页面或是在最远的将来才被访问的页面。该算法是一种理论上的算法，无法实现。
【例1】利用某种程序设计语言编写程序，模拟“先进先出（FIFO）” 算法，完成虚拟存储管理的页面淘汰过程。要求：从键盘上输入允许进程占有的页架数及一个访问串，输出淘汰过程，给出依次被淘汰的页及共发生的缺页次数。
例如：从键盘上输入允许进程占有的页架数为：3
从键盘上输入一个访问串为：7 0 1 2 0 3 0 4 2 3 0 3 2 1 2 0 1 7 0
输出：
FIFO
共14次缺页 依次被淘汰的页：7, 0, 1, 2, 3, 0, 4, 2, 3, 0, 1
注：输入/输出的格式任意，只要能反映淘汰过程即可。
【例2】利用某种程序设计语言编写程序，模拟“最近最少使用调度算法（LRU）” 算法，完成虚拟存储管理的页面淘汰过程。要求：从键盘上输入允许进程占有的页架数及一个访问串，输出淘汰过程，给出依次被淘汰的页及共发生的缺页次数。
例如：从键盘上输入允许进程占有的页架数为：3
从键盘上输入一个访问串为：7 0 1 2 0 3 0 4 2 3 0 3 2 1 2 0 1 7 0
输出：
LRU更换算法：
共发生12次缺页，依次淘汰页为：7 1 2 3 0 4 0 3 2
【例3】利用某种程序设计语言编写程序，模拟“最佳更换（OPT）” 算法，完成虚拟存储管理的页面淘汰过程。
要求：从键盘上输入允许进程占有的页架数及一个访问串，输出淘汰过程，给出依次被淘汰的页及共发生的缺页次数。
例如：
从键盘上输入允许进程占有的页架数为：3
从键盘上输入一个访问串为：7 0 1 2 0 3 0 4 2 3 0 3 2 1 2 0 1 7 0
输出：
OPT
共9次缺页 依次被淘汰的页：7 , 1 , 0 , 4 , 3, 2
二、作业调度算法
常用的作业调度算法：
1．先来先服务算法
该算法是一种较简单的调度算法，它是按照作业进入输入井的先后次序来挑选作业，先进入的作业优先被挑选。
先来先服务算法具有一定的公平性，容易实现。但可能使计算时间短的作业长时间地等待，使作业周转时间变长造成这些用户不满意，也增加了平均等待时间。。
2．短作业优先算法
这种算法要求用户预先估计自己作业所需要计算的时间。调度时优先选择计算时间短的作业。这种算法能降低作业的平均等待时间，从而提高系统的吞吐能力。
3．最高响应比优先算法
最高响应比优先算法综合考虑等待时间和计算时间，把响应比定义为：
响应比=等待时间/计算时间
可以看出计算时间短的作业响应比较高，所以能被优先选中；但等待时间长的作业响应比也会较高，这样就不会因不断地有小作业进入输入井而使大作业无限制地被推迟。
4．优先数调度算法
系统为每一作业确定一个优先级，优先级高的作业优先被选取。优先级的确定可根据作业的缓急程度、估计计算时间、作业等待时间、资源申请情况、付费情况等因素综合考虑，既照顾用户要求，也考虑系统效率。
【例4】利用某种程序设计语言编写程序，用“先来先服务（FCFS）”算法模拟作业调度。
要求：按作业的到达顺序依次输入各作业需要的运行时间，按“先来先服务”算法调度输出平均等待时间。
例如(FCFS)，输入：8，5，7，1
J1 J2 J3 J4
0 8 13 20 21
输出：aver=(0+8+13+20)/4=41/4=10.25
注：输入的格式任意，只要输出平均等待时间即可。
【例5】利用某种程序设计语言编写程序，用“最短作业优先（SJF）”算法模拟作业调度。
要求：按作业的到达顺序输入各作业需要的运行时间，按“最短作业优先”算法调度输出平均等待时间。
例如(SJF)，输入：8，5，7，1
J4 J2 J3 J1
0 1 6 13 21
输出：aver=(0+1+6+13)/4=20/4=5
注：输入的格式任意，只要输出平均等待时间即可。
一、常用的页面调度算法
（1）先进先出调度算法（FIFO）：该算法淘汰进入内存时间最长的页面，这是一种简单的页面淘汰算法。FIFO算法有可能产生异常现象（Belady异常），即当分给一个进程的页面数增多时，缺页中断次数反而增加。
（2）最近最少使用调度算法（LRU）：该算法淘汰上一次访问时间距当前时间间隔最长的页面。该算法是依据局部性特征提出的，认为末被使用时间最长的页面，那么它很可能最近不被使用，故应淘汰。LRU算法的实现开销较大，需要有硬件支持。
（3）最佳更换算法（OPT）：该算法淘汰今后不再访问的页面或是在最远的将来才被访问的页面。该算法是一种理论上的算法，无法实现。
【例1】利用某种程序设计语言编写程序，模拟“先进先出（FIFO）” 算法，完成虚拟存储管理的页面淘汰过程。要求：从键盘上输入允许进程占有的页架数及一个访问串，输出淘汰过程，给出依次被淘汰的页及共发生的缺页次数。
例如：从键盘上输入允许进程占有的页架数为：3
从键盘上输入一个访问串为：7 0 1 2 0 3 0 4 2 3 0 3 2 1 2 0 1 7 0
输出：
FIFO
共14次缺页 依次被淘汰的页：7, 0, 1, 2, 3, 0, 4, 2, 3, 0, 1
注：输入/输出的格式任意，只要能反映淘汰过程即可。
【例2】利用某种程序设计语言编写程序，模拟“最近最少使用调度算法（LRU）” 算法，完成虚拟存储管理的页面淘汰过程。要求：从键盘上输入允许进程占有的页架数及一个访问串，输出淘汰过程，给出依次被淘汰的页及共发生的缺页次数。
例如：从键盘上输入允许进程占有的页架数为：3
从键盘上输入一个访问串为：7 0 1 2 0 3 0 4 2 3 0 3 2 1 2 0 1 7 0
输出：
LRU更换算法：
共发生12次缺页，依次淘汰页为：7 1 2 3 0 4 0 3 2
【例3】利用某种程序设计语言编写程序，模拟“最佳更换（OPT）” 算法，完成虚拟存储管理的页面淘汰过程。
要求：从键盘上输入允许进程占有的页架数及一个访问串，输出淘汰过程，给出依次被淘汰的页及共发生的缺页次数。
例如：
从键盘上输入允许进程占有的页架数为：3
从键盘上输入一个访问串为：7 0 1 2 0 3 0 4 2 3 0 3 2 1 2 0 1 7 0
输出：
OPT
共9次缺页 依次被淘汰的页：7 , 1 , 0 , 4 , 3, 2
二、作业调度算法
常用的作业调度算法：
1．先来先服务算法
该算法是一种较简单的调度算法，它是按照作业进入输入井的先后次序来挑选作业，先进入的作业优先被挑选。
先来先服务算法具有一定的公平性，容易实现。但可能使计算时间短的作业长时间地等待，使作业周转时间变长造成这些用户不满意，也增加了平均等待时间。。
2．短作业优先算法
这种算法要求用户预先估计自己作业所需要计算的时间。调度时优先选择计算时间短的作业。这种算法能降低作业的平均等待时间，从而提高系统的吞吐能力。
3．最高响应比优先算法
最高响应比优先算法综合考虑等待时间和计算时间，把响应比定义为：
响应比=等待时间/计算时间
可以看出计算时间短的作业响应比较高，所以能被优先选中；但等待时间长的作业响应比也会较高，这样就不会因不断地有小作业进入输入井而使大作业无限制地被推迟。
4．优先数调度算法
系统为每一作业确定一个优先级，优先级高的作业优先被选取。优先级的确定可根据作业的缓急程度、估计计算时间、作业等待时间、资源申请情况、付费情况等因素综合考虑，既照顾用户要求，也考虑系统效率。
【例4】利用某种程序设计语言编写程序，用“先来先服务（FCFS）”算法模拟作业调度。
要求：按作业的到达顺序依次输入各作业需要的运行时间，按“先来先服务”算法调度输出平均等待时间。
例如(FCFS)，输入：8，5，7，1
J1 J2 J3 J4
0 8 13 20 21
输出：aver=(0+8+13+20)/4=41/4=10.25
注：输入的格式任意，只要输出平均等待时间即可。
【例5】利用某种程序设计语言编写程序，用“最短作业优先（SJF）”算法模拟作业调度。
要求：按作业的到达顺序输入各作业需要的运行时间，按“最短作业优先”算法调度输出平均等待时间。
例如(SJF)，输入：8，5，7，1
J4 J2 J3 J1
0 1 6 13 21
输出：aver=(0+1+6+13)/4=20/4=5
注：输入的格式任意，只要输出平均等待时间即可。