1.HRRN(三、处理机调度)
题目：高响应比优先调度算法，每次调度之前都要先计算响应比。
设有4个进程P1，P2，P3，P4．它们的就绪时间和要求服务时间如下表所示。若这4个进程在—台处理机上按单道方式运行，采用响应比高者优先调度算法。
（1）试写出各作业的执行顺序；
（2）求各作业的周转时间及平均周转时间。
（3）求各作业的带权周转时间及平均带权周转时间。
类似：
思路：
1. 响应比=优先级=（等待时间+要求服务时间）/要求服务时间，每进行完一个进程就要算剩下的进程的响应比，然后选择最高的
2. 记住算等待时间应该先算出每个进程结束后的时间点A，然后再减去该进程的到达时间B即可得到该进程的等待时间C：A-B=C
3. FCFS:先来先服务
SJF:短作业优先
HRRN:动态优先级调度算法
RR：轮转
（1）以时间为横轴，进程为数轴，提前写好各进程进来的时间然后再根据调度算法进行分析
（2）如果加入了存储空间的限制还要再细致的分析，注意同一作业不能在几台外设同时工作
（3）HRRN主要就是考计算了
题目：
答案：
2.页面置换算法（六、虚拟存储器）
题目：在一个请求分页系统中，假如一个进程的页面走向是3，1，4，2，5，2，1，2，3，4。系统分配给该进程的物理块数为4，目前进程的1,2,3,4页面已经装入内存，请分别计算采用OPT算法、LRU算法时，访问过程中所发生的缺页次数和缺页率。
思路：
OPT:淘汰未来最长时间不使用
FIFO(first in first out):先进先出
LRU（least recently used）:淘汰最近最长未使用
LFU(least frenquently used)：淘汰最近使用最少
CLOCK:时钟转动
3.磁盘调度算法（七、输入输出系统）
题目：如磁头的当前位置是100号磁道，磁头正向磁道号增加的方向移动。现有磁盘读写请求队列：190，10，160，80，90，125，30，20，28，130，22；分别计算采用最短寻道优先算法和电梯调度算法时磁头经过的总磁道数，并写出磁头访问队列？
思路：
FCFS(first come first serve):先来先调度
SSTF(short track):选择跨越轨道最短的，最短寻道优先
SCAN（电梯扫描）：先一个方向（看磁头方向）走到死然后再换向
CSCAN：只有一个方向
题目：例二：假定磁盘有300个柱面，编号0~299，当前存取臂的位置在200号柱面上，并
刚刚完成了125号柱面的服务请求，如果请求队列的先后顺序是：86，147，91，177，194，150，202，275，230；试问：为完成上述请求，下列
算法存取臂移动的总量是多少？并算出存取臂移动的顺序。 (1)先来先服务算法FCFS； (2)最短查找时间优先算法SSTF。
注意：以后不再考虑125这个柱面；存取臂移动总量也不算125这个柱面；
4.动态分区分配算法（五、存储器管理）
题目：给定内存空闲分区，按地址从小到大为：100K、500K、200K、300K、600K。现有用户进程依次分别212K、417K、112K、426K。（1）分别用首次适应算法、循环首次适应算法、最佳适应算法、最坏适应算法将它们装入到内存的哪个分区？（2）哪个算法最有效利用内存？
思路：
首次适应算法:每次从链首开始，找到第一个能满足需求的空闲分区
循环首次适应算法:每次开始从上一个结束的地方开始
最佳适应算法：每次选择最小最适应的空闲分区
最坏适应算法：每次选择最大的空闲分区
△：注意有些题是划分了空闲分区则有边界，不能两个分区合并来看。而有些题没有换分空闲分区块则无边界可以自由划分
5.程序运行的时间关系图（一、系统概述）
题目：经典问题分析：有三个进程A、B、C，他们使用同一个设备进行I/O操作，并且按A、B、C的指定次序执行。进程A共计运行180ms，每隔40ms需要进行I/O操作，I/O时间是20ms。进程B共计运行150ms，每隔20ms需要进行I/O操作，I/O时间是10ms，进程C共计运行160ms，每隔20ms需要进行I/O操作，I/O时间是20ms。假设调度的时间可以忽略，且同时到达内存，请画出在单道环境和多道程序环境下运行的时间关系图，并比较两者的效率。
思路：
以时间为横轴，程序为数轴，注意是抢占式还是非抢占式，注意同一进程计算和I/O操作不能同时进行即可
6.银行家算法（三、死锁）
题目：现有五个进程P1，P2，P3，P4，P5共享R1，R2，R3这三类资源，进程对资源的需求量和目前分配情况如表所示，若系统还剩余资源数分别为R1类1个，R2类1个，R3类3个，请按银行家算法求解下列问题（要求写出详细的分析过程）：
（1）目前系统是否处于安全状态？
（2）如果进程P4提出申请资源数量为（0，0，1），系统能否满足其请求？
（3）经过一段时间后，P1又提出申请资源数量为（1，0，0），系统能否满足其请求？
思路：
1.注意英语的翻译，最大需求MAX，已经分配Allocation,要先求出最多还需要Need
2.注意新一轮的选择从头开始并且优先选择进程号较小的
3.如果进程要提出申请资源，应从现有资源中再拿出给它，然后再算它还需要多少，目前available剩余多少，然后跟之前一样的分析
4.不安全即表示最后会发生死锁
例题：
7.时间片轮转调度算法（三、处理机调度）
题目：设有5个进程PA、PB、PC、PD、PE，它们的就绪时间和要求服务时间如下表所示。若这5个进程在—台处理机上运行，采用时间片轮转(RR)调度算法。
（1）当时间片为1分钟时，求各进程的完成时间、周转时间和平均周转时间。
（2）当时间片为4分钟时，求各进程的完成时间、周转时间和平均周转时间。
8.盘块分配（八、文件管理）
题目：有一个计算机系统利用如图所示的位示图（行号、列号都从0开始编号）来管理空闲盘块。如果盘块从1开始编号，每个盘块的大小为1KB。
（1）现要为文件分配1个盘块，试具体说明分配过程。
（2）若要释放磁盘的第400块，应如何处理？
9.P、V操作（四、进程同步）
例：有3个进程PA，PB，PC并发运行合作解决文件打印问题：PA将记录式文件（文件由多个大小相等的记录构成）从磁盘读入内存的缓冲区SA中，每执行一次读一个记录；PB将缓冲区SA的内容复制到缓冲区SB，每执行一次复制—个记录；PC将缓冲区SB的内容打印出来，每执行一次打印一个记录。缓冲区SA、SB的大小等于10个记录大小,并且进程PA，PB，PC对缓冲区SA和缓冲区SB的访问是互斥的。请用P，V操作来保证文件的正确打印。
答：
semaphore mutex1=1; //缓冲区1互斥信号量
semaphore mutex2=1; //缓冲区2互斥信号量
semaphore empty1=1; //缓冲区1空
semaphore full1=0; //缓冲区1初始化空
semaphore empty2=1; //缓冲区2空
semaphore full2=0; //缓冲区2初始化空
pa()
{
while(1)
{
read; //读文件
P(empty1); //获取空缓冲区1
P(mutex1); //进入临界区1
add; //数据放入缓冲区
V(mutex1); //退出临界区1
V(full1); //缓冲区1满
}
}
pb()
{
while(1)
{
P(full1); //获取满缓冲区1
P(mutex1); //进入临界区1
remove; //从缓冲区中取数据
V(mutex1); //退出临界区1
V(empty1); //缓冲区1空
P(empty2); //获取空缓冲区2
P(mutex2); //进入临界区2
add; //数据放入缓冲区
V(mutex2); //退出临界区2
V(full2); //缓冲区2满
}
}
pc()
{
while(1)
{
P(full2); //获取满缓冲区2
P(mutex2); //进入临界区2
remove; //从缓冲区中取数据
V(mutex2); //退出临界区2
V(empty2); //缓冲区2空
print; //打印
}
}
10.纯计算问题（五六七八章）
1.逻辑地址转物理地址：
例：已知某分页系统，主存容量为64K字节，页面大小为1K，对一个4页大的进程，其0、1、2、3页分别被分配到内存的2、4、6、7块中，试：将十进制的逻辑地址1023、2500、3500转换成物理地址，
并以十进制的逻辑地址3500为例画出地址动态重定位的过程图。
2.文件块内偏移量
例：某个磁盘上的文件系统，采用混合索引分配方式，其FCB中共有13个地址项，第0～9个地址项为直接地址，第10个地址项为一次间接地址，第11个地址项为二次间接地址，第12个地址项为三次间接地址。如果每个盘块的大小为1024个字节，若盘块号需要用4个字节来描述，而每个盘块最多存放256个盘块地址：（1）该文件系统允许文件的最大长度是多少？（2）将文件的字节偏移量5000转换为物理块号和块内偏移量。
答案：
（1）该文件系统中一个文件的最大长度可达：0.5KB*(10+170+170*170+170*170*170)=2471040KB=2.356GB
（2）5000/512得到商为9，余数为392，即字节偏移量5000对应用的逻辑块号为9，块内偏移量为392。由于9<10（块号为0对应第一块），故可直接从该文件FCB的第10个地址项处得到物理盘块号，块内偏移量为392。
15000/512得到商为29，余数为152即字节偏移量15000对应的逻辑块号为29，块内偏移量为152。由于10<29<10+170，而29-10=19，故可从FCB的第11个地址项，即一次间址项中得到一次间址块的地址；并从一次间址块的第20项（即该块的第57～59这3个字节）中获得对应的物理盘块号，块内偏移量为152。
150000/512得到商为292，余数为496。即字节偏移量150000对应的逻辑块号为292，块内偏移量为496。由10+170<292<10+170+170*170，而292-10-170=112，故可从FCB的第12个地址项，即二次间址项中得到二次间址块的地址；并从二次间址块的第1项中(即该块的第0～2这3个字节)获得一个一次间址块的地址，再从该一次间址块的第113项（即该块的第336～338这3个字节）中获得对应的物理盘块号，块内偏移量为496。
书上例题：
存储器
一、本章大致框架：
二、计算题例题
1.内存空闲分区
1.1题目：
给定内存空闲分区，按地址从小到大为：100K、500K、200K、300K、600K。现有用户进程依次分别212K、417K、112K、426K。（1）分别用首次适应算法、循环首次适应算法、最佳适应算法、最坏适应算法将它们装入到内存的哪个分区？（2）哪个算法最有效利用内存？
1.2答案：
(1)
①首次适应算法：212K选中分区2，这时分区2还剩下288KB。417K选中分区5，这时分区5还剩下183KB。112K选中分区2，这时分区2还剩下176KB。426KB无分区能满足要求，等待。
②循环首次适应算法：本题目中与首次适应算法相同。
③最佳适应算法：212K选中分区4，这时分区4还剩88KB。417K选中分区2，这时分区2还剩83KB。112K选中分区3，这时分区3还剩88K。426K选中分区5，这时分区5还剩174KB。
④最坏适应算法：212K选中分区5，这时分区5还剩388KB。417K选中分区2，这时分区2还剩83KB。112K选中分区5，这时分区5还剩276KB。426K无分区能满足，等待。
(2)最佳适应算法最有效使用内存。
2.分页存储管理基本计算
2.1题目：
某系统采用页式存储管理策略，拥有逻辑空间32页，每页2KB，拥有物理空间1MB。
（1）写出逻辑地址的格式。
（2）若不考虑访问权限等，进程的页表有多少项？每项至少有多少位？
（3）如果物理空间减少一半，页表结构应相应作怎样的改变？
2.2答案：
(1)已经给出了页号的数目：32，本题需要解释的是需要多少位来表示，关键：页号是不占任何空间和内存的，所以不用考虑，因此无论是页面大小和页框中
(2)页表项中空间的位数=物理空间大小/页的大小=1MB/2KB=1024KB/2KB=512，则需要9位
(3)逻辑空间的页数=页表项的个数，页表项的位数与逻辑空间的大小有关
3.分段存储-地址转换1
3.1题目：
对于下表所示的段表，请将逻辑地址（0,137）
-》（段号，段内偏移量）,(1,4000),(2,3600),(5,239)转换成物理地址。
3.2答案：
我们需要注意的是：
（1）如果段内偏移大于段长，那么这是一个无效的逻辑地址，因为它超出了段的范围。
（2）此处的单位K（B）表示1024(B)
（3）判断段号是否越界：比较段号，即看逻辑地址中段号是不是在段表中
（4）
物理地址=（分段存储）段始址+段内偏移=（分页存储）页表项地址+页内地址=内存块号*页面大小+页内偏移量（页内地址）
（5）页表项地址=页表起始地址+页号*页表项长度
现在，让我们逐个转换给定的逻辑地址：
对于逻辑地址 (0, 137)：段号为0，段始址为50K，段长为10K。因为137小于10K，所以这是一个有效的地址。物理地址 = 50K + 137 = 50000 + 137 = 51337。
对于逻辑地址 (1, 4000)：段号为1，段始址为160K，段长为3K。因为4000大于3K，所以这是一个无效的逻辑地址，因为它超出了段的范围。
对于逻辑地址 (2, 3600)：段号为2，段始址为270K，段长为5K。因为3600小于5K，所以这是一个有效的逻辑地址。物理地址=70K+3600=75280.
对于逻辑地址 (5, 239)：段表中没有段号5，所以这是一个无效的逻辑地址。
因此，只有第一个逻辑地址 (0, 137) 是有效的，并且它的物理地址是50137。其他逻辑地址要么超出了它们各自段的范围，要么指向了一个不存在的段。
4.分页存储-地址转换2
4.1题目：
已知某分页系统，主存容量为64K字节，页面大小为1K，对一个4页大的作业，其0、1、2、3页分别被分配到主存的2、4、6、7块中，试：将十进制的逻辑地址1023、2500、3500、4500转换成物理地址。
4.2答案：
分析：
（1）物理地址=(物理块号×页面大小)+页内偏移，本题主要是求出页内偏移量，求出页面号找到对应的物理块号
（2）下面解答中的所求的页面号不是没有用，而是用这个量来判断页号是否越界，即存不存在
（3）给定的分页系统中，主存容量为64K字节，页面大小为1K字节。因此，主存可以分为64个页。由题可得，对于一个4页大的作业，其页面分配如下：
（4）先求页号（逻辑地址/页面大小），根据页号（通过页表项对应，注意要判断在不在里面）找对应的物理块号，然后根据块的大小算起始地址，然后再加上便宜地址即可
逻辑页0 -> 物理块2
逻辑页1 -> 物理块4
逻辑页2 -> 物理块6
逻辑页3 -> 物理块7
具体解答：
1.对于逻辑地址1023：
2.对于逻辑地址2500：
3.对于逻辑地址3500：
4.对于逻辑地址4500：
5.页面置换算法
5.1题目：
题目：在一个请求分页系统中，假如一个作业的页面走向是2,3,2,1,5,2,4,5,3,2,5,2。目前没有任何页面装入内存，当分配给该作业的物理块数为3时，请分别计算采用OPT算法、FIFO算法、LRU算法、CLOCK算法时，访问过程中所发生的缺页次数和缺页率。
5.2答案：
首先，我们需要理解每种页面替换算法的工作原理：
OPT（最优替换算法）：替换最长时间内不再被访问的页面。
FIFO（先进先出算法）：替换最早装入内存的页面。
LRU（最近最少使用算法）：替换最近最长时间未被访问的页面。
CLOCK（时钟算法）：是一种简单时钟算法，它维护一个循环的比特位，用于追踪页面的使用情况。
接下来，我们将模拟每种算法下的页面访问过程，并计算缺页次数和缺页率。由于这是一个理论上的模拟，我们将假设每种算法都能完美地执行其策略，不考虑实际实现中的复杂性和开销。
给定的页面走向是：2, 3, 2, 1, 5, 2, 4, 5, 3, 2, 5, 2。分配给该作业的物理块数为3。
1. OPT算法：
初始时，内存为空。页面2, 3, 2依次装入内存，无缺页。
当访问页面1时，由于页面2将在未来被再次访问，而页面3不会，因此替换页面3。缺页1次。
页面5装入内存，无缺页。
再次访问页面2，已在内存中，无缺页。
页面4装入内存，无缺页。
访问页面5，已在内存中，无缺页。
页面3被访问，由于页面1和页面4在未来不会被访问，替换页面4。缺页1次。
页面2已在内存中，无缺页。
页面5已在内存中，无缺页。
最后两次访问页面2，均在内存中，无缺页。
2. FIFO算法：
初始时，内存为空。页面2, 3, 2依次装入内存，无缺页。
访问页面1时，替换最早装入的页面2。缺页1次。
页面5装入内存，无缺页。
再次访问页面2，已在内存中，无缺页。
页面4装入内存，无缺页。
访问页面5，已在内存中，无缺页。
页面3被访问，替换最早装入的页面3。缺页1次。
页面2已在内存中，无缺页。
页面5已在内存中，无缺页。
最后两次访问页面2，均在内存中，无缺页。
3. LRU算法：
初始时，内存为空。页面2, 3, 2依次装入内存，无缺页。
访问页面1时，由于页面3是最长时间未被访问的，替换页面3。缺页1次。
页面5装入内存，无缺页。
再次访问页面2，已在内存中，无缺页。
页面4装入内存，无缺页。
访问页面5，已在内存中，无缺页。
页面3被访问，由于页面1是最长时间未被访问的，替换页面1。缺页1次。
页面2已在内存中，无缺页。
页面5已在内存中，无缺页。
最后两次访问页面2，均在内存中，无缺页。
4. CLOCK算法：
初始时，内存为空。页面2, 3, 2依次装入内存，无缺页。
访问页面1时，替换第一个遇到的未使用的页面（页面3）。缺页1次。
页面5装入内存，无缺页。
再次访问页面2，已在内存中，无缺页。
页面4装入内存，无缺页。
访问页面5，已在内存中，无缺页。
页面3被访问，替换第一个遇到的未使用的页面（页面1）。缺页1次。
页面2已在内存中，无缺页。
页面5已在内存中，无缺页。
最后两次访问页面2，均在内存中，无缺页。
文件管理
1.磁盘调度算法
1.1题目：
题目：假定磁盘有200个柱面，编号0~199，当前存取臂的位置在143号柱面上，并刚刚完成了125号柱面的服务请求，如果请求队列的先后顺序是：86，147，91，177，94，150，102，175，130；试问：为完成上述请求，下列算法存取臂移动的总量是多少？并算出存取臂移动的顺序。 (1)先来先服务算法FCFS； (2)最短查找时间优先算法SSTF； (3)扫描算法SCAN。 (4)电梯调度。
1.2答案：
1.2.1分析：
要先分析出各个调度算法的调度顺序
1.2.2答案：
(1) FCFS算法移动总量为565，调度顺序依次为143-86-147-91-177-94-150-102-175-130。
(2) SSTF算法移动总量为162，调度顺序依次为143-147-150-130-102-94-91-86-175-177。
(3)SCAN(磁头向地址增大的方向移动)为125，调度顺序依次为143-147-150-175-177-130-102-94-91-86。
2.文件系统如何工作
2.1题目：
题目：一个文件的逻辑记录大小为125字节，共有20个逻辑记录，文件系统采用链接方式将这个文件存储到磁盘上，磁盘分块大小为512字节，请问：
(1)采用什么方法可有效地利用磁盘空间？
(2)若用户要读包含第l285字节的逻辑记录，文件系统将如何工作？
2.2答案：
2.2.1分析：
（1）先求出每块中可存储多少个逻辑记录，然后再根据总的逻辑记录来求一个有多少块。
（2）记录号和存储块号都是从0开始排序的。
2.2.2答案：
(1)可采用记录的成组方法，因[512／125]＝4，所以成组的逻辑记录个数应为4。20个逻辑记录共需要5个存储块(0—4)。
(2)首先，由[1285／(125x 4)]＝2，可知包含1285字节的逻辑记录在链接结构的2号块（即第3块上），将该块读入主存缓冲区；然后由l285 mod (125x 4)=285，且[285／125]＝2，可知文件系统从主存缓冲区中取出2号记录（第3个记录）的第35个字节传输给用户即可。
(注意：记录号和存储块号都是从0开始排序的。)
3.求文件最大长度
3.1题目：
题目：在放在某个磁盘上的文件系统，采用混合索引分配方式，其FCB中共有13个地址项，第0～9个地址项为直接地址，第10个地址项为一次间接地址，第11个地址项为二次间接地址，第12个地址项为三次间接地址。如果第个盘块的大小为512字节，若盘块号需要用3个字节来描述，而每个盘块最多存放170个盘块地址：
（1）该文件系统允许文件的最大长度是多少？
（2）将文件的字节偏移量5000、15000、150000转换为物理块号和块内偏移量。
3.2答案：
3.2.1解释：
（1）1GB=1024MB=1024*1024KB=1024*1024*1024B
（2）文件长度跟地址长度有关。直接地址就是只能存一个盘块地址；一次间接地址相当于有了一个盘块，可存放一个盘块可存放的盘块地址
（3）
通过计算文件占用的盘块地址，我们可以确定文件的总大小，因为每个盘块的大小是固定的，文件占用的盘块数量*每个盘块的大小就等于文件的总长度。
（4）求物理盘块号可先求出逻辑块号，然后判断逻辑块号在哪个地址项区间，通过+1来确定物理块号。
3.2.2答案：
（1）该文件系统中一个文件的最大长度可达：0.5KB*(10+170+170*170+170*170*170)=2471040KB=2.356GB
（2）5000/512得到商为9，余数为392，即字节偏移量5000对应用的逻辑块号为9，块内偏移量为392。由于9<10（块号为0对应第一块），故可直接从该文件FCB的第9个地址项处得到物理盘块号，块内偏移量为392。
15000/512得到商为29，余数为152即字节偏移量15000对应的逻辑块号为29，块内偏移量为152。由于10<29<10+170，而29-10=19，故可从FCB的第10个地址项，即一次间址项中得到一次间址块的地址；并从一次间址块的第1项（即该块的第57～59这3个字节）中获得对应的物理盘块号，块内偏移量为152。
150000/512得到商为292，余数为496。即字节偏移量150000对应的逻辑块号为292，块内偏移量为496。由10+170<292<10+170+170*170，而292-10-170=112，故可从FCB的第12个地址项，即二次间址项中得到二次间址块的地址；并从二次间址块的第1项中(即该块的第0～2这3个字节)获得一个一次间址块的地址，再从该一次间址块的第113项（即该块的第336～338这3个字节）中获得对应的物理盘块号，块内偏移量为496。
4.盘块分配过程
4.1题目：
题目：有一个计算机系统利用如图所示的位示图（行号、列号都从0开始编号）来管理空闲盘块。如果盘块从1开始编号，每个盘块的大小为1KB。
（1）现要为文件分配两个盘块，试具体说明分配过程。
（2）若要释放磁盘的第300块，应如何处理？
4.2答案：
（1）为某文件分配两个盘块的过程如下：
第一、顺序检索位示图，从中找到第一个值为0的二进制位，得到其行号为i1=2，列号为j1=2；第二个值为0的二进制位，得到其行号为i2=3，列号j2=6。
第二、计算出找到的两个空闲块的盘块号分别分：
B1=i116+j1+1=216+2=35 (如果盘块号从0开始，则应该为34号)
B2=i216+j2+1=316+6=55 (如果盘块号从0开始，则应该为54号)
第三、修改位示图，令map[2,2]=1，map[3,6]=1,并将对应块34、54分配出去。
（2）释放磁盘的第300块时，应进行如下处理：
第一、计算出磁盘第300块所对应的二进制位的行号i和列号j：
i=(300-1)DIV16 =18 j=(300-1)MOD16 =11
第二、修改位示图，令：map[18,11]=0,表示对应块为空闲块。
一、生产者-消费者问题
1.生产者-消费者问题的特征：
若干进程通过有限的共享缓冲区交换数据。其中，”生产者”进程不断写入，而”>
2.例1 输入加工和输出：
（1）题目描述：
题目：假设有输入、加工和输出3个并发进程共享一个缓冲区B，输入进程负责从输入设备读入一条记录，每读一条记录后把它存放在缓冲区B中，加工进程在缓冲区B中加工输入进程存入的记录。输出进程负责把加工后的记录打印输出。缓冲区B中每次只能存放一条记录，当记录被加工输出后，缓冲区B中才可存放下—条新记录。请用P、V操作来描述它们并发执行时能正确工作的程序。
（2）P,V代码：
Semaphore mutex = 1, empty = 1, full = 0, handle = 0;
//读入进程
void input () {
do {
wait( empty );
wait( mutex );
读入一条记录，每读一条记录后把它存放在缓冲区B中
signal( mutex );
signal( full );
} while( True )
}
// 加工进程
void process () {
do {
wait( full );
wait( mutex );
加工输入进程存入的记录
signal( mutex );
signal( handle );
} while( True )
}
// 输出进程
void process () {
do {
wait( handle );
wait( mutex );
加工后的记录打印输出
signal( mutex );
signal( empty );
} while( True )
}（3）具体分析：
下面解释每个信号量的作用：
mutex：这是一个二进制信号量，用于保证对缓冲区的互斥访问。任何时候只有一个进程能够进入临界区（对缓冲区进行操作的部分）。
empty：表示缓冲区B中空位的数量。输入进程在读入数据到缓冲区之前必须执行wait(empty)操作(P操作)，以确保缓冲区有空间。
full：表示缓冲区B中已填充数据的数量。加工进程在从缓冲区取数据之前必须执行wait(full)操作，以确保缓冲区中有数据可以加工。
handle：表示缓冲区B中已加工数据的数量。输出进程在从缓冲区取数据输出之前必须执行wait(handle)操作，以确保缓冲区中有已加工的数据可以输出。
每个进程在一个无限循环中运行，执行以下步骤：
输入进程
：等待缓冲区有空位（wait(empty)），然后等待获取互斥锁（wait(mutex)）来确保独占访问缓冲区。之后读入一条记录到缓冲区B，释放互斥锁（signal(mutex)），并增加full信号量的值（signal(full)），表示缓冲区中有一条新记录可以加工。
加工进程
：等待缓冲区有记录（wait(full)），然后等待获取互斥锁（wait(mutex)）。接着加工缓冲区中的记录，释放互斥锁（signal(mutex)），并增加handle信号量的值（signal(handle)），表示缓冲区中有一条记录已加工，可以输出。
输出进程
：等待缓冲区有已加工的记录（wait(handle)），然后等待获取互斥锁（wait(mutex)）。之后输出缓冲区中的记录，释放互斥锁（signal(mutex)），并增加empty信号量的值（signal(empty)），表示缓冲区有一个空位可以用于新的输入。
通过这种方式，这三个进程可以有效地同步它们对共享资源——缓冲区B——的访问，避免数据冲突和竞争条件。
3.例2 成品仓库：
(1)题目描述：
题目：设有一个成品仓库，总共能够存放10台成品，生产者生产产品放入仓库，消费者从仓库中取出成品消费。为了防止积压，仓库满时就停止生产。由于仓库搬运设备只有一套，故成品的存入和取出只能分别执行，使用 wait () 和 signal() 操作来实现该方案。
(2)P,V代码：
Semaphore mutex=1,full=0,empty=10;
void producer()
{
do{
生产商品；
p(empty);
p(mutex);
将商品放入仓库
v(mutex);
v(full);
}
while(1)
}
void consumer(){
do{
p(full);
p(mutex);
从仓库中取出商品
v(mutex);
v(empty);
消费
}
while(1)
}4.例3 招待所床位：
(1)题目描述：
题目：某招待所有100个床位，住宿者住入要先登记(在登记表上填写姓名及床位号)，离去时要撤销登记(在登记表上删去姓名和床位号)。请给出住宿登记及撤销登记过程的算法描述。
(2)P,V代码：
semaphore mutex = 1; // 控制对登记表的互斥访问
semaphore emptyBeds = 100; // 表示空闲床位的数量
// 住宿登记过程
void checkIn() {
P(emptyBeds); // 确保有空的床位
P(mutex); // 进入临界区，开始填写登记表
// 在登记表上填写姓名及床位号
V(mutex); // 离开临界区，释放登记表
// 其他入住操作
}
// 撤销登记过程
void checkOut() {
P(mutex); // 进入临界区，开始撤销登记
// 在登记表上删去姓名和床位号
V(mutex); // 离开临界区，释放登记表
V(emptyBeds); // 增加空闲床位的数量
// 其他离店操作
}
(3)具体分析：
为了同步住宿者的入住和撤销登记过程，我们需要确保在填写登记表和撤销登记时的互斥操作，以防止数据不一致。我们可以使用两个信号量：一个用于控制对登记表的访问，另一个用于跟踪空闲床位的数量。
5.例4 文件打印问题：
(1)题目描述：
题目：有3个进程PA，PB，PC合作解决文件打印问题：PA将文件记录N从磁盘读入主存的缓冲区1，每执行一次读一个记录；PB将缓冲区S1的内容复制到缓冲区2，每执行一次复制—个记录；PC将缓冲区2的内容打印出来，每执行一次打印一个记录。缓冲区的大小等于一个记录大小。请用P，V操作来保证文件的正确打印。
(2)P,V代码：
semaphore mutex1=1; //缓冲区1互斥信号量
semaphore mutex2=1; //缓冲区2互斥信号量
semaphore empty1=1; //缓冲区1空
semaphore full1=0; //缓冲区1初始化空
semaphore empty2=1; //缓冲区2空
semaphore full2=0; //缓冲区2初始化空
pa()
{
while(1)
{
read; //读文件
P(empty1); //获取空缓冲区1
P(mutex1); //进入临界区1
add; //数据放入缓冲区
V(mutex1); //退出临界区1
V(full1); //缓冲区1满
}
}
pb()
{
while(1)
{
P(full1); //获取满缓冲区1
P(mutex1); //进入临界区1
remove; //从缓冲区中取数据
V(mutex1); //退出临界区1
V(empty1); //缓冲区1空
P(empty2); //获取空缓冲区2
P(mutex2); //进入临界区2
add; //数据放入缓冲区
V(mutex2); //退出临界区2
V(full2); //缓冲区2满
}
}
pc()
{
while(1)
{
P(full2); //获取满缓冲区2
P(mutex2); //进入临界区2
remove; //从缓冲区中取数据
V(mutex2); //退出临界区2
V(empty2); //缓冲区2空
print; //打印
}
}
(3)具体分析：
为了同步住宿者的入住和撤销登记过程，我们需要确保在填写登记表和撤销登记时的互斥操作，以防止数据不一致。我们可以使用两个信号量：一个用于控制对登记表的访问，另一个用于跟踪空闲床位的数量。
6.例5 生产者—消费者问题：
(1)题目描述：
题目：在生产者—消费者问题中，有一群生产者进程在生产产品，并将这些产品提供给消费者进程去消费。为使生产者进程与消费者进程能并发执行，在它们之间设置了一个有界的公用缓冲池，生产者进程向缓冲池中投入产品，消费者进程从缓冲池中取得产品。假定在生产者进程和消费者进程之间的公用缓冲池中，具有n个缓冲区，每个缓冲区的大小与每一个产品的大小相等。这时可利用互斥信号量mutex实现生产者进程和消费者进程对缓冲池的互斥访问。利用信号量empty和full分别表示缓冲池中没有存放产品的空缓冲区和已经存放产品的缓冲区的数量。又假定这些生产者进程和消费者进程相互等效，只要缓冲池未满，生产者进程便可将产品送入缓冲池；只要缓冲池未空，消费者进程便可从缓冲池中取走产品。请用信号量实现生产者—消费者同步问题。
(2)P,V代码：
semaphore mutex = 1; // 用于互斥访问缓冲池
semaphore empty = n; // 表示空缓冲区的数量
semaphore full = 0; // 表示满缓冲区的数量
// 生产者进程
void producer() {
while (true) {
// 生产产品
P(empty); // 检查是否有空缓冲区
P(mutex); // 进入临界区，开始访问缓冲池
// 将产品放入缓冲池
V(mutex); // 离开临界区，释放缓冲池
V(full); // 增加满缓冲区的数量
}
}
// 消费者进程
void consumer() {
while (true) {
P(full); // 检查是否有满缓冲区
P(mutex); // 进入临界区，开始访问缓冲池
// 从缓冲池中取出产品
V(mutex); // 离开临界区，释放缓冲池
V(empty); // 增加空缓冲区的数量
// 消费产品
}
}
(3)具体分析：
在这个实现中，mutex 信号量确保了同时只有一个生产者或消费者可以访问缓冲池。empty 信号量用于跟踪空缓冲区的数量，full 信号量用于跟踪满缓冲区的数量。
生产者在开始生产之前，会执行 P(empty) 来检查是否有空缓冲区。如果有空缓冲区，它将继续执行 P(mutex) 来进入临界区并放入产品。完成放入产品后，生产者执行 V(mutex) 来离开临界区，并执行 V(full) 来增加满缓冲区的数量。
消费者在开始消费之前，会执行 P(full) 来检查是否有满缓冲区。如果有满缓冲区，它将继续执行 P(mutex) 来进入临界区并取出产品。完成取出产品后，消费者执行 V(mutex) 来离开临界区，并执行 V(empty) 来增加空缓冲区的数量。
通过这种方式，我们可以确保生产者和消费者之间的正确同步，以及缓冲池不会出现溢出或下溢的情况。
二、读者-写者问题：
1.读者-写者问题的特征：
一个文件可能被多个进程共享，为了保证读写的正确性和文件的一致性，系统要求，当有读者进程读文件时，不允许任何写者进程写，但允许多读者同时读；当有写者进程写时，不允许任何其它写者进程写，也不允许任何读者进行读。 为了解决读者和写者问题，需设置两个信号量：
（1）读互斥信号量rmutex,用于使读者互斥地访问共享变量readcount,这里 readcount是记录有多少读者正在读;
（2）写互斥信号量wmutex,用于实现读写互斥和写写互斥地访问共享文件。
2.例1 窄桥：
(1)问题描述 ：
题目：（
类似
读者优先的读写问题）有一窄桥每次只能过一辆车，每次为了保证正常通行，只要桥上没有车，就允许一端的车过桥，待其全部过完后才允许另一端的车过桥。请用信号量和PV操作写出过窄桥的同步算法。
(2)P,V代码：
semaphore wait = 1； // 互斥信号量，表示独木桥的数量
int count1 = 0; // 东侧车辆在独木桥上的数量
semaphore mutex1 = 1; // 东侧车辆的互斥信号量，保证count1操作的完整执行
int count2 = 0; // 西侧车辆在独木桥上的数量
semaphore mutex2 = 1; // 西侧车辆的互斥信号量，保证count2操作的完整执行
cobegin
process P东() {
P(mutex1);
count1++;
if(count1 == 1) // 东侧第一个准备上桥的车去抢夺独木桥
P(wait);
V(mutex1);
{过独木桥};
P(mutex1);
count1--;
if(count1 == 0) // 东侧最后一个已经下桥的车去释放独木桥
V(wait);
V(mutex1);
}
process P西() {；
P(mutex2);
count2++;
if(count2 == 1) // 西侧第一个准备上桥的车去抢夺独木桥
P(wait);
V(mutex2);
{过独木桥};
P(mutex2);
count2--;
if(count2 == 0) // 西侧最后一个已经下桥的车去释放独木桥
V(wait);
V(mutex2);
}
coend
(3)具体分析：
对于东侧车辆（P东）：
首先，车辆请求P(mutex)，进入临界区，增加count的值。
如果count的值变为1，说明这是第一辆准备过桥的东侧车辆，它会请求mutex信号量，试图抢占独木桥。
车辆通过独木桥后，再次请求P(mutex)，减少count的值。
如果count的值变为0，说明这是最后一辆已经过桥的东侧车辆，它会释放wait信号量，允许另一侧的车辆过桥。
3.例2 读者-写者问题：
(1)问题描述：
题目：一个数据对象，如文件或记录，能被多个进程共享，可把那些只要求读数据对象的进程称为“读者”，其它进程则称为“写者”。显然，多个读者可同时读一个共享对象，但不允许一个写者与读者同时访问共享对象，也不允许多个写者同时访问共享对象，否则会造成数据的不一致性。这个经典同步问题就是“读者-写者问题”。若考虑读者优先，即除非有写者正在写，否则读者就毋须等待。请用信号量实现读者-写者同步问题。
(2)P,V代码：
semaphore mutex = 1; // 用于保护对共享数据对象的互斥访问
semaphore write = 1; // 用于控制写者访问共享数据对象
int readCount = 0; // 记录当前正在读取的读者数量
// 读者进入
void readerEnter() {
P(mutex); // 进入临界区，开始修改readCount
readCount++; // 增加正在读取的读者数量
if (readCount == 1) { // 如果是第一个读者，需要阻止写者写入
P(write); // 阻止写者写入
}
V(mutex); // 离开临界区，释放mutex
}
// 读者离开
void readerLeave() {
P(mutex); // 进入临界区，开始修改readCount
readCount--; // 减少正在读取的读者数量
if (readCount == 0) { // 如果是最后一个读者，允许写者写入
V(write); // 允许写者写入
}
V(mutex); // 离开临界区，释放mutex
}
// 写者进入
void writerEnter() {
P(write); // 阻止其他读者和写者
// 写入操作
}
// 写者离开
void writerLeave() {
V(write); // 允许其他读者和写者访问
}
(3)具体分析：
在这个实现中，mutex 信号量用于保护对 readCount 的访问，确保其操作的原子性。write 信号量用于控制对共享数据对象的写访问，确保写者的独占访问。
当读者想要读取数据时，它们会调用 readerEnter 函数。如果读者是第一个读者，它会阻止写者写入，否则可以直接读取。当读者完成读取后，它们调用 readerLeave 函数，如果它们是最后一个读者，会允许写者写入。
写者在写入数据之前必须调用 writerEnter 函数，这将阻止其他读者和写者访问数据。写者完成写入后，调用 writerLeave 函数，允许其他读者和写者访问。
这种实现确保了读者可以并发地读取数据，而写者在写入时具有独占访问权。同时，它也避免了写者长时间等待的情况，因为一旦没有读者在读取，写者就可以立即写入。
三、哲学家进餐问题：
1.哲学家问题的特征：
在哲学家进餐问题中，通常有多个哲学家围坐在圆桌旁，每个哲学家需要两把叉子才能进餐，而桌子上的叉子是共享资源。在这个问题中，哲学家相当于生产者和消费者，而叉子相当于盒子中的产品。
在您提出的问题中，有两个进程P1和P2，它们需要交替访问共享资源（盒子中的产品）。这与哲学家进餐问题中的每个哲学家需要同时获得两把叉子才能进餐类似。
2.例1 产品分拣：
(1)问题描述：
题目：一个同步问题：在一个盒子里，混装了数量相等的X、Y两种产品。现在用自动分拣系统把X、Y两种产品分开，设分拣系统有二个进程P1和P2，其中P1拣X产品；P2拣Y产品。规定每个进程每次只能拣一个产品；当一个进程在拣时，不允许另一个进程去拣；当一个进程拣了一个产品时，必须让另一个进程去拣。试用信号量和PV操作写出两进程P1和P2能并发正确执行的程序。
(2)P,V代码：
semaphore mutex = 1; // 用于互斥访问盒子
semaphore turn = 1; // 用于控制P1和P2交替拣选
// 进程P1拣X产品
void P1() {
while (true) {
P(mutex); // 进入临界区，开始拣选
// 拣选一个X产品
V(mutex); // 离开临界区，释放盒子
V(turn); // 允许P2拣选
P(turn); // 等待P2拣选完成
}
}
// 进程P2拣Y产品
void P2() {
while (true) {
P(mutex); // 进入临界区，开始拣选
// 拣选一个Y产品
V(mutex); // 离开临界区，释放盒子
V(turn); // 允许P1拣选
P(turn); // 等待P1拣选完成
}
}
(3)具体分析：
在这个实现中，mutex 信号量确保了同时只有一个进程可以访问盒子。turn 信号量用于控制P1和P2交替拣选产品。
进程P1在拣选X产品之前，会执行 P(mutex) 来进入临界区。拣选完成后，执行 V(mutex) 来离开临界区，并执行 V(turn) 来允许P2拣选。然后，P1执行 P(turn) 来等待P2拣选完成。
进程P2在拣选Y产品之前，也会执行 P(mutex) 来进入临界区。拣选完成后，执行 V(mutex) 来离开临界区，并执行 V(turn) 来允许P1拣选。然后，P2执行 P(turn) 来等待P1拣选完成。
通过这种方式，我们可以确保P1和P2交替拣选产品，并且每个进程在拣选完成后都会等待另一个进程完成拣选，从而实现正确的同步。
3.例2 爸爸装水果：
(1)问题描述：
题目：桌子上有一个能盛得下5个水果的空盘子，爸爸不停地向盘子中放入苹果或者桔子，儿子不停地从盘子中取出桔子享用，女儿不停的从盘子中取出苹果享用。规定三人不能同时从盘子中取放水果。试用信号量实现爸爸、儿子和女儿三个进程间的同步。
(2)P,V代码：
semaphore mutex = 1; // 用于互斥访问盘子
semaphore fruit = 5; // 表示盘子中水果的数量
semaphore dad = 1; // 用于控制爸爸放入水果
semaphore son = 1; // 用于控制儿子取出桔子
semaphore daughter = 1; // 用于控制女儿取出苹果
// 爸爸进程
void dad() {
while (true) {
P(dad); // 获取放入水果的权限
P(mutex); // 进入临界区，开始放入水果
// 放入一个水果
V(mutex); // 离开临界区，释放盘子
V(fruit); // 增加水果的数量
V(dad); // 释放放入水果的权限
}
}
// 儿子进程
void son() {
while (true) {
P(son); // 获取取出桔子的权限
P(mutex); // 进入临界区，开始取出水果
// 取出一个桔子
V(mutex); // 离开临界区，释放盘子
V(fruit); // 减少水果的数量
V(son); // 释放取出桔子的权限
}
}
// 女儿进程
void daughter() {
while (true) {
P(daughter); // 获取取出苹果的权限
P(mutex); // 进入临界区，开始取出水果
// 取出一个苹果
V(mutex); // 离开临界区，释放盘子
V(fruit); // 减少水果的数量
V(daughter); // 释放取出苹果的权限
}
}
(3)具体分析：
为了实现爸爸、儿子和女儿三个进程间的同步，我们需要确保以下几点：
三个进程不能同时从盘子中取放水果。
爸爸在放入水果时，不能有儿子或女儿在取出水果。
儿子和女儿在取出水果时，不能有爸爸在放入水果。
在这个实现中，mutex 信号量用于保护对盘子的互斥访问，确保同一时刻只有一个进程可以访问盘子。fruit 信号量用于跟踪盘子中水果的数量，防止盘子溢出或下溢。dad、son 和 daughter 信号量用于控制爸爸、儿子和女儿的独占访问权，确保他们不会同时取放水果。
爸爸在放入水果之前，会执行 P(dad) 来获取放入水果的权限，然后执行 P(mutex) 来进入临界区并放入水果。完成放入水果后，爸爸执行 V(mutex) 来离开临界区，并执行 V(fruit) 来增加水果的数量，最后执行 V(dad) 来释放放入水果的权限。
儿子和女儿在取出水果之前，会执行 P(son) 或 P(daughter) 来获取取出水果的权限，然后执行 P(mutex) 来进入临界区并取出水果。完成取出水果后，儿子和女儿执行 V(mutex) 来离开临界区，并执行 V(fruit) 来减少水果的数量，最后执行 V(son) 或 V(daughter) 来释放取出水果的权限。
通过这种方式，我们可以确保爸爸、儿子和女儿之间的正确同步，以及盘子中水果数量的正确控制。
暂无评论内容