操作系统
信号量解决进程同步问题
例题：
桌子上有一只盘子，最多可容纳两个水果，每次只能放入或取出一个水果。爸爸专向盘子中放苹果，妈妈专向盘子中放橘子，两个儿子专等吃盘子中的橘子，两个女儿专等吃盘子中的苹果。请用信号量操作来实现爸爸、妈妈、儿子、女儿之间的同步与互斥关系。
semaphore s=2,so=0,sa=0;//s表示盘空，so表示橘子，sa表示苹果。
Cobegin
Void father(void)
{
while(1){
p(s);
put apple();
v(sa);
}
}
Void mother(void)
{
while(1){
p(s);
put orange();
v (so);
}
}
Void son(void)
{
while(1){
p(so);
eat orange();
v(s);
}
}
Void daughter(void)
{
while(1){
p(sa);
eat apple();
v(s);
}
}
Coend
PV操作参考进程同步之信号量机制（pv操作）及三个经典同步问题
作业调度算法（先来先服务算法、短作业优先算法），计算周转时间、带权周转时间、平均周转时间、平均带权周转时间
周转时间=完成时间-提交时间
带权周转时间=周转时间/执行时间
平均周转时间=每个周转时间之和/作业总数
平均带权周转时间=每个带权周转时间之和/作业总数
例题：求解下表中4个作业在FCFS（先来先服务算法）和SJF（短作业优先算法）调度算法下的调度次序、周转时间、带权周转时间、平均周转时间、平均带权周转时间。
| 作业 | 提交时间 | 执行时间 | 开始时间 | 完成时间 | 周转时间 | 带权周转时间 |
|---|---|---|---|---|---|---|
| 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.00 | 1 | 1 |
| 2 | 8.50 | 0.50 | 10.00 | 10.50 | 2.00 | 4 | 2 |
| 3 | 9.00 | 0.10 | 10.50 | 10.60 | 1.60 | 16 | 3 |
| 4 | 9.50 | 0.20 | 10.60 | 10.80 | 1.30 | 6.5 | 4 |
平均周转时间=1.725
平均带权周转时间=6.875
短作业优先调度算法
| 作业 | 提交时间 | 运行时间 | 开始时间 | 完成时间 | 周转时间 | 带权周转时间 | 执行顺序 |
|---|---|---|---|---|---|---|---|
| 1 | 8.00 | 2.00 | 8.00 | 10.00 | 2.00 | 1 | 1 |
| 2 | 8.50 | 0.50 | 10.30 | 10.80 | 2.30 | 4.6 | 4 |
| 3 | 9.00 | 0.10 | 10.00 | 10.10 | 1.10 | 11 | 2 |
| 4 | 9.50 | 0.20 | 10.10 | 10.30 | 0.80 | 4 | 3 |
平均周转时间=1.55
平均带权周转时间=5.15
先来先服务算法
先来先服务根据作业的提交时间来执行作业，提交的时间早则首先被执行。
短作业优先算法
根据执行时间来作为执行顺序，同时第一个到达的作业要首先被执行，之后再根据运行时间的长短来执行，短的则优先执行。
资源分配图的简化
资源分配图
在资源分配图中，通常使用圆圈来表示每个进程，用方框表示每种资源类型。由于同一资源类型可能有多个实例，所以在矩形中用圆点数表示实例数。
| 实例 | 说明 |
|---|---|
|
进程P1申请一个R1类资源 |
|
系统分配一个R1类资源给进程P1，此时系统还剩下2个R1类资源 |
|
进程P1申请2个R类资源 |
|
系统分配2个R1类资源给进程P1，此时系统还剩下1个R1类资源 |
|
|
系统分配一个R1类资源给进程P2，然后分配一个R1类资源给进程P1，最后进程P1收到一个R1类资源又继续申请一个R1类资源，此时系统还剩下一个R1类资源可以分配给进程P1，但是还没有分配给P1 |
|
系统分配一个R1类资源给进程P2，然后又分配一个R1类资源给进程P1，最后进程P1收到一个R1类资源又继续申请一个R1类资源，此时系统已经没有R1类资源可以分配给进程P1，于是进程P1收到阻塞 |
例题：
- 第一步：先看R1资源，它有三个箭头是向外的，因此它一共给进程分配了3个资源，此时，R1没有空闲的资源剩余。
- 第二步：再看R2资源，它有一个箭头是向外的，因此它一共给进程分配了1个资源，此时，R2还剩余一个空闲的资源没分配。
- 第三步：看完资源，再来看进程，先看进程P2，它只申请一个R1资源，但此时R1资源已经用光了，所以，进程P2进入阻塞状态，因此，进程P2暂时不能化成孤立的点。
- 第四步：再看进程P1，它只申请一个R2资源，此时，系统还剩余一个R2资源没分配，因此，可以满足P1的申请。这样，进程P1便得到了它的全部所需资源，所以它不会进入阻塞状态，可以一直运行，等它运行完后，我们再把它的所有的资源释放。相当于：可以把P1的所有的边去掉，变成一个孤立的点，如下图所示：
- 第五步：进程P1运行完后，释放其所占有的资源（2个R1资源和1个R2资源），系统回收这些资源后，空闲的资源便变成2个R1资源和1个R2资源，由于进程P2一直在申请一个R1资源，所以此时，系统能满足它的申请。这样，进程P2便得到了它的全部所需资源，所以它不会进入阻塞状态，可以一直运行，等它运行完后，我们再把它的所有的资源释放。相当于：可以把P2的所有的边都去掉，化成一个孤立的点，变成下图：
由于这个资源分配图可完全简化，因此，不会产生死锁。
而如果资源分配图中的点，最终不能够化成孤立的点，则进程资源图不能够完全简化，从而会发生死锁。
分页地址变换
地址变换处理
- 得到页号：自动将逻辑地址分为页号和页内地址
- 用页号查页表，得到块号
- 将块号与页内地址拼接，即得物理地址
分页存储逻辑地址转物理地址
例题：
已知某个分页系统，页面大小为1K(即1024字节)，某一个作业有4个页面，分别装入到主存的第3、4、6、8块中，求逻辑地址2100对应的物理地址。
- 第一步：求逻辑地址的页号 = 2100/1024=2 （整除）
- 第二步：求页内偏移量 = 2100 % 1024 =52 （取余）
- 第三步：产生页表：
| 页号 | 块号 |
|---|---|
| 0 | 3 |
| 1 | 4 |
| 2 | 6 |
| 3 | 8 |
- 第四步：根据逻辑地址的页号查出物理地址的页框号/帧号：
如上图，逻辑地址的第2页对应物理地址的第6页。 - 第五步：求出物理地址 = 6*1024 + 52 = 6196
设有8页的逻辑地址空间，每页有1024个字节，它们被映射到32块的物理存储区，那么逻辑地址的有效位是多少，物理地址至少多少位？
逻辑地址：8x1024=2^3x2^10=2^13
物理地址：32x1024=2^5x2^10=2^15
逻辑地址的有效位是13，物理地址的有效位是15.
十六进制逻辑地址转物理地址
一分页存储管理系统中逻辑地址长度为16位，页面大小为4KB字节，现有一逻辑地址为2F6AH，且第0、1、2页依次存放在物理块5、10、11中。求逻辑地址2F6AH对应的物理地址
解：
- 第一步：将逻辑地址2F6AH转换为二进制为：0010 1111 0110 1010
- 第二步：由于页面大小为4KB字节，（4KB=2的12次方）。所以逻辑地址的后12位为“页内地址”(也叫做页内偏移量)
- 第三步：由于逻辑地址的后12位为页内地址，所以剩下的前4位为页号：即0010为页号
- 第四步：根据页表可知，0010(十进制为2)对于的页框号为11(二进制为1011)
所以最终的物理地址为：1011 1111 0110 1010
即BF6AH
页面置换算法
定义：选择换出页面的算法
评价依据：页面更换频率（缺页率）。 缺页率=缺页次数/页面总访问次数
最佳置换算法（OPT）
最佳置换算法所选择淘汰的页面是最长（未来）时间内不再被访问的页面。
例如：
系统为某进程分配3个物理块，进程访问页面的顺序是0，7，6，5，7，4，7，3，5，4，7，4，5，6，5，7，6，0，7，6。
| 访问页面 | 0 | 7 | 6 |
|---|---|---|---|
| 物理块 | 0 | 0 | 0 |
| 7 | 7 | ||
| 6 |
接下来下一个进入的数字是5，然后需要淘汰最久不被访问的页面。
首先，需要看0，7，6的哪个是最久不被访问的页面。
0在第18次再次访问。
7在第5次再次被访问。
6在第14次再次被访问。
因此需要淘汰0。
按照如上的规律，可以得到以下的结果。
| 访问页面 | 0 | 7 | 6 | 5 | 7 | 4 | 7 | 3 | 5 | 4 | 7 | 4 | 5 | 6 | 5 | 7 | 6 | 0 | 7 | 6 |
|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
| 物理块 | 0 | 0 | 0 | 5 | 5 | 5 | 5 | 5 | 5 | 5 | 5 | 5 | 5 | 5 | 5 | 5 | 5 | 0 | 0 | 0 |
| 7 | 7 | 7 | 7 | 7 | 7 | 3 | 3 | 3 | 7 | 7 | 7 | 7 | 7 | 7 | 7 | 7 | 7 | 7 | ||
| 6 | 6 | 6 | 4 | 4 | 4 | 4 | 4 | 4 | 4 | 4 | 6 | 6 | 6 | 6 | 6 | 6 | 6 | |||
| 缺页中断 | x | x | x | x | x | x | x | x | x |
缺页率：9/20*100%=36%
缺页中断：在请求分页系统中，可以通过查询页表中的状态位来确定所要访问的页面是否存在于内存中。每当所要访问的页面不在内存时，会产生一次缺页中断，此时操作系统会根据页表中的外存地址在外存中找到所缺的一页，将其调入内存。
通俗的讲也就是每次往物理块中添加数据就会产生一次缺页中断。
先进先出页面置换算法（FIFO）
先进先出页面置换算法淘汰的页面是淘汰最先进入内存的页面。
| 访问页面 | 6 | 0 | 1 | 2 | 0 | 3 | 0 | 4 | 2 | 3 |
|---|---|---|---|---|---|---|---|---|---|---|
| 物理块 | 6 | 6 | 6 | 2 | 2 | 2 | 2 | 4 | 4 | 4 |
| 0 | 0 | 0 | 0 | 3 | 3 | 3 | 2 | 2 | ||
| 1 | 1 | 1 | 1 | 0 | 0 | 0 | 3 | |||
| 缺页中断 | x | x | x | x | x | x | x | x | x |
缺页率：9/10*100%=90%
最近最久未使用置换算法（LRU）
最近最久未使用置换算法淘汰的页面是淘汰最近最久未使用的页面。
| 访问页面 | 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 | ||||
| 缺页中断 | x | x | x | x | x | x | x |
缺页率：7/12*100%=58.3%
堆栈实现LRU：
系统使用特殊的堆栈来存放内存中每一个页面的页号。每当访问一页时就调整一次，即把被访问页面的页号从栈中移出再压入栈顶。因此，栈顶始终是最新被访问页面的页号。当发生缺页中断时，总是淘汰栈底页号所对应的页面。
磁盘的调度算法
先来先服务（FCFS）
先来先服务算法是根据进程请求访问磁盘的先后顺序进行调度。
例题：
某一磁盘请求序列（磁盘号）：98，183，37，122，14，124，65，61.按照先来先服务磁盘调度对磁盘进行请求服务，假设当前磁头在53道上，则磁臂总移动倒数为多少？
| 下一个磁道 | 移动磁道数 |
|---|---|
| 98 | 45 |
| 183 | 85 |
| 37 | 146 |
| 122 | 85 |
| 14 | 108 |
| 124 | 110 |
| 65 | 59 |
| 61 | 4 |
总移动磁道数=45+85+146+85+108+110+59+4=642.
最短寻道时间优先磁盘调度算法（SSTF）
最短寻道时间优先磁盘调度算法是每次都优先满足当前磁头位置最近的磁道访问请求。
例题：
若干个等待访问磁盘者依次要访问的磁道为19，43，40，4，79，11，76，当前磁头位于42号柱面，若用最短寻道时间优先磁盘调度算法，则访问序列是什么？
思路：将要访问的磁道与当前磁头所在柱面相减并取绝对值，绝对值越小的优先访问。
访问序列为40，43，19，11，4，76，79.
扫描算法（SCAN）
- 考虑当前移动方向，一直移动到最外/内层磁道时，折返，进行反方向移动。就好比电梯。
- 寻道方向：…，里->外，外->里，….;
若干个等待访问磁盘者依次要访问的磁道为86,147,91,177,94,150,102,175,130，当前磁头位于143号柱面，刚刚处理完125号柱面，使用SCAN算法则访问序列是什么？
答：
- 当前方向：从143向磁道号增加的方向
- 依次访问：147，150，175，177
- 反方向：130，102，94，91，86（电梯原理）
循环扫描（CSCAN）
- 循环扫描
- 寻道方向：…..,里->外，里->外，….。或者相反。
若干个等待访问磁盘者依次要访问的磁道为86,147,91,177,94,150,102,175,130，当前磁头位于143号柱面，刚刚处理完125号柱面，使用CSCAN算法则访问序列是什么？
答：
- 当前方向：从143向磁道号增加的方向
- 依次访问：147，150，175，177
- 再从0开始增加方向：86，91，94，102，130
磁盘空间分配
多级索引分配
例题：
设一个盘块大小为1k,每个盘块号占4Byte,若系统采用2级索引，求文件的最大长度。
答:
每个索引块最多可存放1k/4=256个盘块号；
采用2级索引是，一个文件最多可拥有的数据块数为256x256=2^6x2^10=64k
文件的最长长度为64kx1k=64m.
混合索引分配
存放在某磁盘上的文件系统采用混合索引分配方式，其中FCB由6个地址项构成，前四个地址项是直接寻址方式，第五个地址项是一次间接寻址方式，第六个地址项是二次间接寻址。若每个盘块的大小为1KB，盘块号用4个字节描述。那么：
（1）源文件系统允许文件的最大长度是多少？
（2）将文件的字节偏移量800、8193和819300 转换为物理块号和块内偏移。
答：
（1）每个盘块能存放的盘块号的个数：1024/4=256
文件系统允许的文件最大长度：
（4+256+256x256）x1K=65796KB
（2）
- 800/1024商0余800，因为0<4，所以，第一个地址项中存放的块号即为其所在物理块号，块内偏移800。
- 8193/1024商8余1，4<=8<4+256，所以一次间接寻址，8-4=4，读第五个地址项中存放的块号物理块的内容，其内容中的第五个块号即为其所在物理块号，块内偏移1。
- 819300/1024商800余100，4+256<=800<4+256+256x256，所以二次间接寻址，800-(4+256)=540，540/256商2余28，读第六个地址项中存放的块号的物理块的内容，再读其内容中的第三个块号所在物理块的内容，其内容的第29个块号即为其所在物理块号，块内偏移为100。
磁盘空间的管理位置分配
位示图
位示图：用二进制的一位表示磁盘中一个盘块的使用情况。
- “0”，对应块是空闲块；
- “1”，对应块已被分配出去。
盘块分配
(1) 顺序扫描位示图，从中找出一个或一组其值为“0”的二进制位(“0”表示空闲)。
(2) 将所找到的一个或一组二进制位， 转换成与之相应的盘块号。假定找到的其值为“0”的二进制位，位于位示的第i行、第j列，则其相应的盘块号应按下式计算：
b=n(i-1)+j
式中， n代表每行的位数。
(3) 修改位示图， 令map［i,j］=1。
盘块的回收
(1) 将回收盘块的盘块号转换成位示图中的行号和列号。 转换公式为：
i=(b-1)DIV n+1
j=(b-1)MOD n+1
(2) 修改位示图。 令map ［i,j］=0。
例题：
有一计算机系统采用如下图所示的位示图（行号、列号都从0开始编号）来管理空闲盘块。如果盘块从1开始编号，每个盘块的大小为1KB。 （1）现要为文件分配两个盘块，试具体说明分配过程。 （2）若要释放磁盘的第300块，应如何处理？
