2019-06-20-操作系统
概述
操作系统管理功能.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
