概述

操作系统管理功能.jpg

操作系统经历了哪些阶段

• 人工
• 批处理
• 多道
• 分时
  计算首次适应算法、最佳适应算法、最坏适应算法

进程管理

进程状态和转换

进程状态和转换.png

程序和进程的关系

程序	进程
静态	动态
	占用系统资源
	并发

程序已进程是多对多的关系

最先适应算法
没有排序
最佳适应算法
从小到大排序
最坏适应算法
从大到小排序

例

在可变分区管理中下，按地址排列的内存空闲区为：10KB，4KB，20KB，18KB，7KB，9KB，12KB，15KB。对于下列的连续存储区的请求：12KB，10KB，9KB，问：使用首次适应算法、最佳适应算法、最坏适应算法，以上连续存储区的各使用哪个空闲区？

分区号	分区大小	分区占用情况
0	10KB	10KB
1	4KB
2	20KB	12KB
3	18KB	9KB
4	7KB
5	9KB
6	12KB
7	15KB

最先适应算法

10 4 20 18 7 9 12 15

分区号	分区大小	分区占用情况
0	10KB	10KB
1	4KB
2	20KB	12KB
3	18KB	9KB
4	7KB
5	9KB
6	12KB
7	15KB

最佳适应算法

4 7 9 10 12 1518 20

分区号	分区大小	分区占用情况
0	4KB
1	7KB
2	9KB	9KB
3	10KB	10KB
4	12KB	12KB
5	15KB
6	18KB
7	20KB

最坏适应算法

20 18 15 12 10 9 7 4

分区号	分区大小	分区占用情况
0	20KB	12KB
1	18KB	10KB
2	15KB	9KB
3	12KB
4	10KB
5	9KB
6	7KB
7	4KB

例：设页面走向为：2、3、2、1、5、2、4、5、3、2、5、2，页面M=3，试用FIFO和LRU两种算法分别计算访问过程中的缺页率。

FIFO

解：第一步，第一行把页面走向抄下来，最后一行用来打勾，其他的行数就是M的行数

2	3	2	1	5	2	4	5	3	2	5	2

解：第二步，新来的数往下面放，新增就打勾

2	3	2	1	5	2	4	5	3	2	5	2
2	2
	3
✔	✔

解：第三步，如果已经存在，就不用放，勾也不用打

2	3	2	1	5	2	4	5	3	2	5	2
2	2	2
	3	3
✔	✔	✔

解:第四步

2	3	2	1	5	2	4	5	3	2	5	2
2	2	2	2
	3	3	3
			1
✔	✔		✔

解:第五步 image.png

，看哪条最长就替换谁

2	3	2	1	5	2	4	5	3	2	5	2
2	2	2	2	5
	3	3	3	3
			1	1
✔	✔		✔	✔

依次类推

2	3	2	1	5	2	4	5	3	2	5	2
2	2	2	2	5	5	5	5	3	3	3	3
	3	3	3	3	2	2	2	2	2	5	5
			1	1	1	4	4	4	4	4	2
✔	✔		✔	✔	✔	✔		✔		✔	✔

数一下打勾数目是9，一共12列
缺页率：9/12*100%=75%

LRU

解：第一步，第一行把页面走向抄下来，最后一行用来打勾，其他的行数就是M的行数

2	3	2	1	5	2	4	5	3	2	5	2

解：第二步，抄下来

2	3	2	1	5	2	4	5	3	2	5	2
2	3	2	1	5	2	4	5	3	2	5	2

解：第三步，前面的第一行和第一行移到当前列的第二行和第三行，2和空移到这里

2	3	2	1	5	2	4	5	3	2	5	2
2	3	2	1	5	2	4	5	3	2	5	2
	2
✔	✔

如果已经存在就跳过，2已经有了

2	3	2	1	5	2	4	5	3	2	5	2
2	3	2	1	5	2	4	5	3	2	5	2
	2	3
✔	✔

2	3	2	1	5	2	4	5	3	2	5	2
2	3	2	1	5	2	4	5	3	2	5	2
	2	3	2
			3
✔	✔		✔

2	3	2	1	5	2	4	5	3	2	5	2
2	3	2	1	5	2	4	5	3	2	5	2
	2	3	2	1
			3	2
✔	✔		✔	✔

依此类推，最后一列因为2已经有了，跳过，换成三

2	3	2	1	5	2	4	5	3	2	5	2
2	3	2	1	5	2	4	5	3	2	5	2
	2	3	2	1	5	2	4	5	3	2	5
			3	2	1	5	2	4	5	3	3
✔	✔		✔	✔		✔		✔	✔

缺页率：7/12*100%=58.3%

作业调度算法
先来先服务调度算法（First Come First Served，FCFS）
例：在某一时刻系统中有4个作业，已知他们进入系统的时刻，估计运算时间见表，用FCFS算法计算作业的运行情况、平均周转时间和平均带权周转时间。

作业	进入时间	运行时间长短
1	8.00	2.00
2	8.50	0.50
3	9.00	0.10
4	9.50	0.20

准备

作业	进入时间	运行时间长短	开始时刻	完成时刻	周转时间	带权周转时间
1	8.00	2.00
2	8.50	0.50
3	9.00	0.10
4	9.50	0.20

第一步，完成时间=开始时刻+运行时间长短

作业	进入时间	运行时间长短	开始时刻	完成时刻	周转时间	带权周转时间
1	8.00	2.00	8.00	10.00
2	8.50	0.50
3	9.00	0.10
4	9.50	0.20

因为是先来先服务，所以很顺从上到下写下来

作业	进入时间	运行时间长短	开始时刻	完成时刻	周转时间	带权周转时间
1	8.00	2.00	8.00	10.00
2	8.50	0.50	10.00	10.5
3	9.00	0.10	10.5	10.6
4	9.50	0.20	10.6	10.8

第二步，周转时间=完成时刻-进入时间

作业	进入时间	运行时间长短	开始时刻	完成时刻	周转时间	带权周转时间
1	8.00	2.00	8.00	10.00	2.00
2	8.50	0.50	10.00	10.5	2.00
3	9.00	0.10	10.5	10.6	1.6
4	9.50	0.20	10.6	10.8	1.3

第三步，带权周转时间=周转时间/运行时间长短

作业	进入时间	运行时间长短	开始时刻	完成时刻	周转时间	带权周转时间
1	8.00	2.00	8.00	10.00	2.00	1.0
2	8.50	0.50	10.00	10.5	2.00	4.0
3	9.00	0.10	10.5	10.6	1.6	16.0
4	9.50	0.20	10.6	10.8	1.3	6.5

答：平均周转时间：（2+2+1.6+1.3）/4=1.725
平均带权周转时间：（1+4+16+6.5）/4=6.875
作业的调度顺序依次是：1->2->3->4

最短作业优先发（Shortest Job First，SJF）

例：将前面的例题用SJF进行调度

第一步，第一行先抄

作业	进入时间	运行时间长短	开始时刻	完成时刻	周转时间	带权周转时间
1	8.00	2.00	8.00	10.00
2	8.50	0.50
3	9.00	0.10
4	9.50	0.20

第二步，看谁运行时间最短，是3，0.1

作业	进入时间	运行时间长短	开始时刻	完成时刻	周转时间	带权周转时间
1	8.00	2.00	8.00	10.00
2	8.50	0.50
3	9.00	0.10	10.00	10.1
4	9.50	0.20

接下来是4：0.2

作业	进入时间	运行时间长短	开始时刻	完成时刻	周转时间	带权周转时间
1	8.00	2.00	8.00	10.00
2	8.50	0.50
3	9.00	0.10	10.00	10.1
4	9.50	0.20	10.1	10.3

最后

作业	进入时间	运行时间长短	开始时刻	完成时刻	周转时间	带权周转时间
1	8.00	2.00	8.00	10.00
2	8.50	0.50	10.3	10.8
3	9.00	0.10	10.00	10.1
4	9.50	0.20	10.1	10.3

接下来的步骤参考FCFS

作业	进入时间	运行时间长短	开始时刻	完成时刻	周转时间	带权周转时间
1	8.00	2.00	8.00	10.00	2.0	1.0
2	8.50	0.50	10.3	10.8	2.3	4.6
3	9.00	0.10	10.00	10.1	1.1	1.1
4	9.50	0.20	10.1	10.3	0.8	4

答：平均周转时间：（2+2.3+1.1+0.8）/4=1.55
平均带权周转时间：（1+4.6+1.1+4）/4=2.675
作业的调度顺序依次是：1->3->4->2