操作系统复习
基本定义
并发：是指两个或多个事件在同一时间间隔内发生。
并行：是指两个或多个事件在同一时刻发生。
并发条件：读集与写集是空集、写集和写集是空集。
并发执行特征：失去了封闭性和可再现性。
共享性：是指计算机系统中的各种硬、软件资源都可以为多个用户同时使用。
管态：操作系统的管理程序在执行时CPU所处的状态，又称系统态。
目态：用户程序在执行时CPU所处的状态，又称用户态。
虚拟性：一方面指把物理上的一个实体变成逻辑上的多个对应物，另一方面指虚拟出来的对应物只不过是用户主观上的一种错觉。
进程特性：动态性、并发性、独立性、异步性、结构特性。
进程与程序的区别：
- 从定义上看，进程是程序处理数据的过程，而程序是一组指令的有序集合；
- 进程具有动态性、并发性、独立性和异步性等，而程序不具有这些特性；
- 从进程结构特性来看，他包含程序（以及数据和PCB）；
- 进程和程序并非一一对应；
进程的三种状态：就绪，执行，阻塞。
临界区：进程中访问临界资源的那段程序代码成为临界区或临界段。
临界区的使用原则：空则让进，忙则等待，等则有限，等则让权。
上锁和开锁的原语
上锁原语：LOCK(W)
L1:如果 W=1 那么转向L1；
否则 W=1
返回
开锁原语：UNLOCK(W)
W=0;
返回
信号量基本物理含义：当信号量值大于零时表示系统中某类资源的数目；当信号量值小于零时，其绝对值为系统中因请求该类资源而被阻塞的进程数目。
信号量的值的意义：
- 正数：资源数；
- 负数：等待资源进程数；
同步、互斥的区别：进程互斥是让各个进程竞争共享资源，资源的使用是各自独立的，相互之间无必然联系；进程同步时并发进程对共享资源的使用必须按照某种逻辑顺序来进行。
死锁定于：两个或两个以上的进程在执行过程中，因争夺资源而造成的一种互相等待的现象。
产生死锁的必要条件：
- 互斥条件
- 占有并请求条件。
- 不可剥夺条件
- 循环等待条件。
物理地址：内存单元的地址编号，又称绝对地址或实地址。
逻辑地址：用户程序中使用的地址，又称相对地址或虚地址。
静态重定位：在程序执行过程之前由装入程序完成的重定位过程。
动态重定位：在程序执行过程中，由硬件地址变换机构实现重定位的过程。
虚拟内存：一种利用虚拟储存器来逻辑扩充物理内存的技术。
快表：一组相关联寄存器，具有并行能力。用来存在当前最长访问的那些页面的页表目内容。
二级页表：为节约内存，氛围二级页表结构。第一级用１ｋ个表相，每项４个字节，占４KB内存；第二级再用１０位，这样二级表组合起来即可达到１MB个表项。
中断：是指计算机在执行期间，系统内发生了某一急需处理的事件，使得CPU暂时终止当前正在执行的程序而转区执行相应的事件处理程序，待处理完毕后再返回导刚才暂停程序的被中断处继续执行。
I/O通道：是指专门用于负责输入/输出工作的处理机，是大型机必备的为CPU减负的设备。
缓冲技术：在CPU和外设之间设立缓冲区，用以暂存CPU和外设之间交换的数据，从而缓和CPU和外设速度不匹配所产生的矛盾。
I/O控制方式：程序直接控制方式、中断控制方式、DMA控制方式、通道控制方式。
文件物理结构：从系统角度看到的文件信息的组织形式。
算法
银行家算法
假定系统中有五个进程{P0、P1、P2、P3、P4}和三类资源{A、B、C}，各种资源的数量分别是10、5、7，在T0时刻的资源分配情况如下图所示：
1）判断在T0时刻的安全性。
MAX：进程所需的资源
Allocation：系统已经分配给进程的资源数
Need：进程还需要的资源数
Need = MAX - AllocationAvailable：系统剩余的资源数
Available =Total - Allocation
Work：当前系统所剩资源
work+allocation：计算机处理完当前进程后所剩资源
所以在T0时刻有安全序列{P1，P3，P4，P2，P0}，所以T0时刻是安全的。
2）P1请求资源：P1发出请求向量Request（1，0，2），系统按照银行家算法进行检查。
判断步骤：
- 先判断请求是否小于等于所需：Request（1，0，2）<= Need(1，2，2)
- 判断请求的是否小于等于系统还剩的：Request（1，0，2）<=Allocation（3，3，2）
- 根据请求资源量进行分配（更改表）
- 列表计算
更改表：
结果：
所以P1可以请求成功。
页面置换算法
缺页：当前物理页面中不存在的页面
缺页次数：出现缺页的次数
缺页率：缺页次数/总页数
先进先出算法 FIFO
- 置换最先调入内存的页面，即置换在内存中驻留时间最久的页面。
- 按照进入内存的先后次序排列成队列，从队尾进入，从队首删除。但是该算法会淘汰经常访问的页面，不适应进程实际运行的规律，目前已经很少使用。
| P | 2 | 3 | 2 | 1 | 5 | 2 | 4 | 5 | 3 | 2 | 5 | 2 |
|---|---|---|---|---|---|---|---|---|---|---|---|---|
| 0 | 2 | 2 | 2 | 2 | 5 | 5 | 5 | 5 | 3 | 3 | 3 | 3 |
| 1 | 3 | 3 | 3 | 3 | 2 | 2 | 2 | 2 | 2 | 5 | 5 | |
| 2 | 1 | 1 | 1 | 4 | 4 | 4 | 4 | 4 | 2 | |||
| F=9 | Y | Y | Y | Y | Y | Y | Y | Y | Y |
缺页率：9/12*100%=75%
最佳置换算法 OPT
- 被淘汰的页面将是在未来最长的时间内不再被访问的页面
- 缺页中断率最低，但是该算法需要依据以后各业的使用情况，而当一个进程还未运行完成是，很难估计哪一个页面是以后不再使用或在最长时间以后才会用到的页面。所以该算法是不能实现的。
| P: | 2 | 3 | 2 | 1 | 5 | 2 | 4 | 5 | 3 | 2 | 5 | 2 |
|---|---|---|---|---|---|---|---|---|---|---|---|---|
| M=3 | 2 | 2 | 2 | 2 | 2 | 2 | 4 | 4 | 4 | 4 | 4 | 4 |
| 3 | 3 | 3 | 3 | 3 | 3 | 3 | 3 | 2 | 2 | 2 | ||
| 1 | 5 | 5 | 5 | 5 | 5 | 5 | 5 | 5 | ||||
| F=6 | Y | Y | Y | Y | Y | Y |
缺页率：6/12*100%=50%
最近最少使用算法LRU
- 置换最近一段时间以来最长时间未访问过的页面
| P | 2 | 3 | 2 | 1 | 5 | 2 | 4 | 5 | 3 | 2 | 5 | 2 |
|---|---|---|---|---|---|---|---|---|---|---|---|---|
| 0 | 2 | 2 | 2 | 2 | 2 | 2 | 2 | 2 | 3 | 3 | 3 | 3 |
| 1 | 3 | 3 | 3 | 5 | 5 | 5 | 5 | 5 | 5 | 5 | 5 | |
| 2 | 1 | 1 | 1 | 4 | 4 | 4 | 2 | 2 | 2 | |||
| F=7 | Y | Y | Y | Y | Y | Y | Y |
缺页率：7/12*100%=58.3%
计算物理地址
在采用页式存储管理的系统中，某进程的逻辑地址空间为4页（每页2048字节），已知该进程的页面映像表（页表）如下：
| 页号 | 块号 |
|---|---|
| 0 | 2 |
| 1 | 4 |
| 2 | 6 |
| 3 | 8 |
计算有效逻辑地址4865所对应的物理地址。
地址转换：绝对地址=块号×块长+块内地址
求页号： d = 4865%2048=2……769
对页表：找到块号 6
算地址：物理地址=6*2048+769=13057
磁盘调度
一个磁盘驱动器有150个柱面，考虑一个磁盘序列，它按照到达时间顺序分别是35、52、37、17、80、120、135、104，如果读写磁头最初位于柱面90，请使用FCFS、SSTF、SCAN、CSCAN算法求总寻道长度和平均寻道长度。
先来先服务算法 FCFS
磁头移动顺序：
90 -> 35 -> 52 -> 37 -> 17 -> 80 -> 120 -> 135 -> 104
总寻道长度 = (90-35) + (52-35) + (52-37) + (37-17) + (80-17) + (120-80) + (135-120) + (135-104) = 256
平均寻道长度 = 总长/移动次数 = 256/8 = 32;
最短寻道时间优先 SSTF
先把磁盘序列的时间按照从小到大的顺序排列，磁头从开始柱面移动到距离开始柱面最近的柱面，然后从这个柱面移动到到离这个柱面最近的柱面，以此类推，直到访问所有的柱面。
17 35 37 52 80 90 104 120 135
17 35 37 52 80 90 104 120 135
17 35 37 52 80 90 104 120 135
17 35 37 52 80 90 104 120 135
17 35 37 52 80 90 104 120 135
17 35 37 52 80 90 104 120 135
17 35 37 52 80 90 104 120 135
17 35 37 52 80 90 104 120 135
17 35 37 52 80 90 104 120 135
磁头移动顺序：
90 -> 80 -> 104 -> 120 -> 135 -> 52 -> 37 -> 35 -> 17
扫描算法 SCAN
17 35 37 52 80 90 104 120 135
磁头从初始柱面向左（右）扫描，一直到头，然后向右（左）扫描。
磁头移动顺序：
向左：90 -> 80 -> 52 -> 37 -> 35 -> 17 -> 104 -> 120 -> 135
向右：90 -> 104 -> 120 -> 135 -> 80 -> 52 -> 37 -> 35 -> 17
循环扫描算法 C-SCAN
17 35 37 52 80 90 104 120 135
磁头移动顺序：
向左：90 -> 80 -> 52 -> 37 -> 35 -> 17 -> 135 -> 120 -> 104
向右：90 -> 104 -> 120 -> 135 -> 17 -> 35 -> 37 -> 52 -> 80
向左（右）到头，然后因为是圆形有150个柱面，所以直接转了一圈，计算总寻道长度的时候注意
进程调度
从P1到P4有四个进程，每个进程的到达时间和运行时间如下表所示：
| 进程 | 到达时间 | 执行时间 |
|---|---|---|
| P1 | 0 | 8 |
| P2 | 1 | 4 |
| P3 | 2 | 9 |
| P4 | 3 | 5 |
求FCFS和SJF的平均等待时间、平均周转时间和平均带权周转时间。
先来先服务算法 FCFS
按照进程到达的先后次序 ：
P1 -> P2 -> P3 -> P4
| 进程 | 到达时间 | 执行时间 | 开始时间 | 结束时间 | 等待时间 | 周转时间 | 带权周转时间 |
|---|---|---|---|---|---|---|---|
| P1 | 0 | 8 | 0 | 8 | 0 | 8 | 1 |
| P2 | 1 | 4 | 8 | 12 | 7 | 11 | 2.75 |
| P3 | 2 | 9 | 12 | 21 | 10 | 19 | 2.11 |
| P4 | 3 | 5 | 21 | 26 | 18 | 23 | 4.6 |
等待时间 = 开始时间 - 到达时间
周转时间 = 结束时间 - 到达时间
带权周转时间 = 周转时间/执行时间
平均等待时间 = 等待时间/进程数
平均周转时间 = 周转时间/进程数
平均带权周转时间 = 带权周转时间/进程数
短作业优先调度算法 SJF
按照进程的长短，进程越短越优先
- 非抢占
P1 -> P2 -> P4 -> P3
| 进程 | 到达时间 | 执行时间 | 开始时间 | 结束时间 | 等待时间 | 周转时间 | 带权周转时间 |
|---|---|---|---|---|---|---|---|
| P1 | 0 | 8 | 0 | 8 | 0 | 8 | 1 |
| P2 | 1 | 4 | 8 | 12 | 7 | 11 | 2.75 |
| P4 | 3 | 5 | 12 | 17 | 9 | 14 | 2.8 |
| P3 | 2 | 9 | 17 | 26 | 15 | 24 | 2.66 |
- 抢占
P1 -> P2 -> P4 -> P1 -> P3
| 进程 | 到达时间 | 执行时间 | 开始时间 | 结束时间 | 等待时间 | 周转时间 | 带权周转时间 |
|---|---|---|---|---|---|---|---|
| P1 | 0 | 8/7 | 0/10 | 1/17 | |||
| P2 | 1 | 4 | 1 | 5 | |||
| P3 | 2 | 9 | 17 | 26 | |||
| P4 | 3 | 5 | 5 | 10 |
