课程笔记

第一章

简答题

三种基本的OS

分时操作系统: 同时性，独立性，及时性，交互性

实时操作系统：提供及时响应和高可靠性

批处理操作系统：批量集中处理、多道程序运行、作业脱机工作

第二章处理器调度作业

简答题

处理器两种最基本的状态

用户态：只能运行用户程序，非特权指令

核心态：运行系统指令和全部程序

什么是中断

中断指在程序执行的过程遇到急需处理的事件中，暂时中止现行程序在CPU上的运行，转而执行相应的事件处理程序，待处理完成后再返回断电或调度其他程序执行的过程。

进程的状态转换

我们需要掌握的进程状态有：

创建态
就绪态
运行态
阻塞态
终止态

需要掌握状态的转化关系：

例题：请填空

解：

例题：在一单处理器系统中若有5个用户进程在非管态的某一时刻处于运行状态的用户进程最多有填空1个,最少有[填空2]个处于就绪状态的用户进程最多有[填空3 个处于等待状态的用户进程最多有[填空4]个

答案：1;0;4;5

三态模型是什么？三种状态在什么时候发生转换？

答：三态模型包括：运行态、就绪态与等待态

当进程被调度的时候就绪态转换为运行态

当时间片到的时候或者被处理机抢占时运行态转化为等待态

当进程用“系统调用”的方式申请资源或者请求等待某个事件发生的时候运行态转为等待态

当申请的资源被分配或者等待的事件发生时进程从等待态转换为就绪态

进程控制块（PCB）的作用

PCB是进程的唯一表示，它使得一个在多道程序环境下不能独立运行的程序，成为一个能独立运行的基本单位。OS是根据PCB来对并发执行的进程进行控制和管理的。

进程调度算法的比较

先来先服务算法（FCFS）：

比较有利于长作业，不利于短作业
有利于CPU繁忙行的作业，不利于I/O繁忙型的作业

最短作业优先算法

比FCFS改善平均周转时间和平均带权周转时间，缩短作业的等待时间
对长作业非常不利，可能出现长时间得不到执行
未能根据作业的紧迫程度来划分执行的优先级
难以准确估计作业的执行时间，从而影响调度性能
存在饥饿现象

最高响应比优先算法（HRRF）：

HRRF既考虑作业的等待时间也考虑作业的运行时间，既能够照顾短作业又不会使长作业的等待时间过长，改善了调度性能

时间片轮转算法：

轮转策略可以防止哪些很少使用外围设备的进程过长的占用处理器，让外围设备的那些进程没有机会去启动外围设备。

作业计算题

进程调度算法

非交互系统的策略

先到先得算法（FCFS First Come First Server）
短作业优先算法（SPF Shortest Process First）
高响应比优先算法（HRRN）

响应比 = \frac{等待时间+作业处理时间}{作业处理时间}

交互系统的策略

时间片轮转算法
优先级调度算法

例题：在某个计算机系统中有一台输入机和一台打印机,现有两道程序投入运行,且程序A先开始运行,程序B后开始运行。程序A的运行轨迹为:计算50ms、打印100Ms,再计算 50Ms,打印100Ms,结束。程序B的运行轨迹为:计算50Ms、输入 80ms,再计算100Ms,结束。试说明 (1)两道程序运行时,cpu是否存在空闲等待? 若是,求出等待的时间长短(单位ms)。 (2)程序A、B哪个有等待cpu的情况? 若有,求出等待的时间长短。

解：

17有三个作业A、B、C,它们分别单独运行时的CPU和I/O占用时间如下图所示:

现在请考虑三个作业同时开始执行。系统中的资源有一个CPU和两台输入/输出设备(I/O1和I/O2)同时运行。三个作业的优先级为A最高,B次之,C最低,旦低优先级的进程开始占用CPU,则高优先级进程也要等待其结束方可占用CPU。请问最早结束的作业是[填空1 最后结束的作业是[填空2]? 计算这段时间CPU的利用率。(三个作业全部结束为止,精确到两位小数)[填空3]?

答：B;A;85.70;

例题：在单CPU和两台IO(I,I2)设备的多道程序设计环境下,同时投入三个作业运行。它们的执行轨迹如下: Jobl: 12(30ms), CPU(10ms) 1(30ms)、CPU(1Oms); Job2: Il(20ms)、CPU(20ms)、2(40ms); Job3: CPU(30ms), II(20ms) 如果CPU、I1和I2都能并行工作,优先级从高到低为Job1、Job2和Job3, 优先级高的作业可以抢占优先级低的作业的CPU。试求: (1) 每个作业从投入到完成分别所需的时间。Job1是多少? Job2是多少? 空21Job3是多少? 填空3](单位ms) (2) 设备利用率。Il是多少?I2是多少? (精确到小数后一位)

解：

例题：有5个进程P1,P2,P3,P4,P5依次且同时到达就绪队列,它们的优先数和需要的处理器时间如下表所示。(数字越大,优先级越高)
忽略进程调度等所花费的时间,请回答下列问题 (1)写出分别采用“先来先服务” 和“非抢占式的优先数”调度算法时选中进程执行的次序。(按调度次序填写进程,如P1P223P4P5,中间无需间隔)先来先服务:[填空1]; 非抢占式的优先数:「填空2] (2)分别计算出在两种算法下各进程在就绪队列中的平均等待时间先来先服务:「填空3]; 非抢占式的优先数:「填空4]

答：P1P2P3P4P5；P4P1P3P5P2；9.6；8.6

例题：有一个具有两道作业的批处理系统, 作业调度采用短作业优先的调度算法,进程调度采用以优先数为基础的抢占式调度算法如下表所示的作业序列,作业优先数即为进程优先数,优先数越小优先级越小。 1)请完成下表的1-22的填空(周转时间取整数, 带权周转时间精确到小数点后1位)。

答：从进程提交到进程完成的时间间隔为周转时间.

例题：假设某多道程序设计系统中有供用户使用的内存100K.打印机1台。系统采用可变分区方式管理内存对打印机采用静态分配并假设输入输出操作的时间忽略不计;采用最短剩余时间优先的进程调度算法,进程剩余执行时间相同时采用先来先服务算法;进程调度时机选择在执行进程结束时或有新进程到达时。现有一进程序列如下假设系统优先分配内存的低地址区域,且不许移动己在主存中的进程, 请: (1) 给出进程调度算法选中进程的次序[填空1]。(按调度次序填写进程号,中间无需间隔符,如12345) (2) 全部进程执行结束所用的时间是多少 ?

答案：12435，47

第三章内存

简答题

OPT算法为什么无法实现？

答：因为我们无法预测一个程序的未来如何运行

计算题

内存地址分配算法

最先适应算法

通俗来讲就是：把进程尽量往低地址空闲区域放，放不下的话在更加地址慢慢升高。每一次存放，都从最低地址开始寻找满足的空闲区域，直至最高地址。即每次存放都从0开始。

下次适应算法

该算法是在FF算法的基础上进行改进的，大体上与FF算法相似，而不同点就是：

FF算法每次存储都是从0开始寻找符合要求的空闲区域；
NF算法每次存储都是接着上次分配区域的下一个地址；
最佳适应算法

该算法和FF算法相似，每当进程申请空间的时候，系统都是从头部开始查找。空闲区域是从小到大记录的，每次查找都从最小的开始，直到查找的满足要求的最小空闲区域。

最坏适应算法

该算法与BF算法相反，BF是用最小的空闲区域来存储东西，而WF是用最大的空闲区域来存储。

例题：给定主存空闲分区,按地址从小到大为:100KB、500KB、 200KB、30KB和600KB,编号分另为1-5。现有用户进程依次分别为 212KB、417KB、112KB和426KB: (1)分别采用最先适应、最优适应、最坏适应算法和下次适应算法将它们装入到主存的那个分区?

答：

页面置换算法

页面置换算法：

最佳置换算法（OPT）
先进先出算法（FIFO）
最近最久未使用算法（LRU）
选择最近最长时间未访问过的页面予以淘汰，它认为过去一段时间内未访问过的页面，在最近的将来可能也不会被访问。
时钟置换算法（Clock）

例题：一个请求页式存储管理系统使用FIFO、OPT和LRU页面置换算法,如果一个作业的页面走向为：
（1）2、3、2、1、5、2、4、5、3、2、5、2
当分配给该作业的物理块数分别为M=3和M=4时,试计算访问过程中发生的缺页中断次数F。

答案：9;6;7;6;5;6

例题：在一个请求分页式系统中假如一个作业共有5个页面, 其页面调度次序为:1,4,3, 1,2,5,1,4,2,1,4,5。若分配给改作业的主存块数为 3,分别采用 FIFO、LRU、Clock页面置换算法,试计算访问过程中所发生的缺页中断次数和缺页中断率。(保留小数点后1位)

答：9；75.0；8；66.7；8；75.0

例题：一个程序要将100×100数组置初值0。现假设分配给该程序的主存块数有三块,程序固定占用一块,页面的大小为每页100个字,数组中每一行元素存放在一页中。开始时, 第一页数据已经调入主存。若采用 FIFO算法,则下列两种对数组的初始化程序段引起缺页中断次数各是多少?
.

答案：9999；99

根据页表结构进行计算

熟悉一级二级页表的结构掌握如下计算知识点：

逻辑地址与物理地址的转换

物理地址 = 页面始址+页内偏移量

页号 = 逻辑地址 // 页面长度

页内偏移量 = 逻辑地址%页面长度

根据逻辑地址结构计算页表的大小、页表最大占用
数据访问时间
计算访问了几次内存

例题：某计算机主存按字节编址,逻辑地址和物理地址都是32位, 页表项大小为4字节。请回答下列问题。若使用一级页表的分页存储管理方式,逻辑地址结构为：
(1)页的大小是多少KB? (2)页表最大占用多少MB?

答案：4；4

解析：页内偏移量为12位说明页的大小为： $2^{12}$ B = 4KB

一共有20位的页号，也就说最多有 $2^{20}$ 个页表项

页表最多占用： $2^{20}$ * 4B = 4MB

例题：某系统采用二级页表的分页存储管理方式,系统按字节编址虚拟地址格式为: 页目录号(10位)|页表索引(10位) 页内位移(12位)
请问:
1.页框的大小为多少KB？进程的虚拟地址空间大小为多少K个页面? 2.若页目录表项和页表项均占4B,则一个进程的页目录表和页表共占多少页? 3.若某指令周期内访问的虚地址是01000000H和01112048H,则进行地址转换时共访问了多少个二级页表？

答案：4;1024;1025;1

解析：

（1）页框的大小为： $2^{12}$ B = 4KB, 虚拟地址有 $2^{10} * 2^{10}$ = 1024K个页面

（2）页目录表大小为 $2^{10} * 4$ = 4KB ，页表大小为 $2^{10} * 2^{10} * 4B$ = 1024KB 一种占1025页（一页4KB）

（3）二级页表是前10位，两个地址的前10位都是0000000100 ，一共只访问了1个二级页表

例题：假定某采用分页式存储管理的系统中,主存容量为1MB,被分成256块,块号为0,1,2,…255。某作业的地址空间占4页,其页号为0,1,2,3,被分配到主存的第2,4,1,5块中。请问:
(1)主存地址应该用多少位来表示? (2)作业每一页的长度为多少? 逻辑地址中的页内地址(单元号)应该用多少位来表示? (3)把作业中每一页分到的主存块中的起始地址填入下表。

页表地址转换

例题：在页式存储管理系統中,页面大小为2048个字节,将一个由4个页面(页号为0-3组成的程序装入内存中,该进程的页表如下表所示：
对于下面的逻辑地址,请按西表过算出对应的(物理地)给逻辑地转换的过程： (1)4000(十进制) (2)2019H(十六进制)

例题：在页式虚拟存储管理系统中，用户编程空间为32个页，页面大小为1KB，内存空间为16KB。如果应用程序有10页长，且已知页号为0-3的页已依次分得页框号为4、7、8、10的页框，尝试把逻辑地址0AC5H和1AC5H转化为对应的物理地址。

快表时间消耗

例题：某一级页式存储管理系统，假设其页面全部存储在内存当中。
若访问内存的时间为120ns，那么访问一个数据的时间是多少
若增加一个快表，无论命中与否均需要20ns的开销，假设快表的命中率为80%，则此时访问一个数据的平均时间是多少？

解析：

（1）访问页表需要访问一个内存，访问页表中的地址需要再需要再访问一次内存，一共访问两次内存

（2）如果快表命中则需要20ns+120ns=140ns，如果不命中则需要240ns+20ns=260ns。则访问一个数据的平均时间需要（260+140）/ 2 = 200ns

段式存储

例题：给定段表如下图,给定地址为段号和位移数,试求出对应的主存物理地址,(如越界则填越界中断)。

答案：649；1727；2301；越界中断；1994

解析：如果段长 > 位移数则可以用段首地址加上位移数即可

进阶题目

解析：（1）逻辑空间有32页，也就说页表项有32（ $2^5$ ）个需要5位。每页2KB（ $2^{11}$ ）需要11位

逻辑地址就是：｜5位页号｜11位页内偏移｜；

（2）一共只有1MB的物理空间，1MB/2KB = 512 = $2^9$ 所以需要9位；

（3）如果物理地址减少1半，0.5MB/2KB = 256 = $2^8$ 。页表长度减少1

现有容量为10GB的磁盘分区，磁盘空间以簇（cluster）为单位进行分配，簇的大小为4KB，若采用位图法管理该分区的空闲空间，即用一位（bit）标识一个簇是否被分配，则存放该位图所需簇的个数为

解析：

这里需要注意1位是1b = $\frac{1}{8}B$

一共需要 10GB / 4KB = 2621440b = 327680B = 320KB

需要320KB / 4KB = 80个簇

解析：与上面那题基本一致，但是需要注意单位是字

某系统采用段页式存储管理, 作业逻辑地址被分为4个段,每段最大长度为8页,页面大小4KB, 物理地址长度为20位,现有某作业的部分段表/页表如下图所示则
(1) X段中相对地址14K,对应的逻辑地址和物理地址 (16进制) 分别是多少 ?
(2) 逻辑地址总共多少位 ?

解析：

逻辑地址格式：2,3,12 X段，对应第一段，段号01，对应的是1号页表，14K/4K=3……2K，所以对应3号页面，页号011 2K转化成二进制1000 0000 0000 对应16进制800 所以逻辑地址01011 + 800H = 0B800H 1号页表对应的3号页对应的页框号是27 27*4K = 1 1011 0000 0000 0000=1B000H 1B000H+偏移=1B800H

假设一个任务被分成4个大小相等的段,并且系统为每个段建立了一个有8个表项的页表。因此,该系统是分段与分页的组合。假设页大小为2KB。 (1)每段的最大尺寸为多少? (2)该任务的逻辑空间最大是多少? (3)若此任务访问的逻辑地址5ABCH中的一个数据,试给出逻辑地址格式。

解析：

（1）每个段建立了一个有8个表项的页表，分段的最大尺寸为8*2KB = 16KB

（2）4 8 2KB = 72KB

（3）

考虑下面的C程序:
int X[N],
int step=M ; //M是某个预定义的常量
for(int i=0; i< N; i+= step) X[i]=X[i]+1
(a) 如果这个程序运行在一个页面大小为4KB且有64个TLB表项的机器上,那么M和N取什么值会使得内层循环的每次执行都引起TLB失效?
(b) 如果循环重复很多遍, 结果会和a的答案相同吗? 请解释

解析：

a) int占4B，M的最小值是1024，才能使内层循环的每次执行时都引起TLB失效，由于TLB有64个，所以N的值>64×M。

b) M的值应该大于1024才能在内层循环每次执行时引起TLB失效，但现在N的值要大于64K，所以X会超过256KB。当N的值足够大时，还是会引起TLB失效。

第四章设备管理

计算题

硬盘调度算法

先来先服务算法（FIFO）
最短寻道优先算法（SSTF）

优先处理与当前磁道最近的

电梯算法

从头扫描到最后一个柱面再返回

扫描算法（SCAN）

不管最后柱面的位置，到达末尾后再回来（不撞南墙不回头类型）

LOCK调度算法
循环扫描调度算法

例题：假设磁盘存取臂目前出于8号柱面上,刚刚访问了6号柱面,对应以下的请求访问序列: 9,7,15,18,20, 3,则按照SCAN算法和电梯算法,计算上述两种算法中磁头的移动距离。(设柱面号为0-99) SCAN填空1] 电梯调度算法 [填空2]

答案：187；29

例题：磁头的当前位置为100磁道,磁头正向磁道号增加的方向移动。现有一磁盘读写请求队列:23,376,205,132.19,61.190, 398 29,4,18,40。若采用先来先服务、最短寻道时间优先和扫描算法,试计算出各种算法中移臂所经过的柱面：
(1) 先来先服务算法[填空 1]
(2) 最短寻道时间优先[填空2]
(3) 扫描算法[填空3]

答案：1596; 700; 692

如磁盘的每个磁道分成9个块现有一文件共有A、B、... 共9个记录,每个记录的大小与块的大小相等,设磁盘转速为27ms/转,每读出块后需要2ms的处理时间。若忽略其他辅助时间,试问：
1) 如果顺序存放这些记录并顺序读取, 处理该文件要多少ms？ 2) 如果要顺序读取该文件, 记录如何存放处理时间最短ms？

答案：245；53

解析：对于第一道题需要注意在2ms的处理时间中磁道还是在继续行走的，并不是停下来的。对于第二题每次都寻找与当前磁头最近的即可。

第五章文件管理

简答题

文件目录结构有几种，各有什么优点？

答：

缺点：文件重名和文件共享问题难以解决

优点：

(1) 较好地反应现实世界中具有层次关系答数据集合，确切地反应系统内部文件的分支结构

(2) 不同文件可以重名（只要不位于同一末端子目录中即可）

(3) 易于规定不同层次或子目录中文件的不同存取权限。

计算题

例题： 设有一个包含1000个记录的索引文件,每个记录正好占用一个物理块, 而一个物理块可以存放10个索引表目。建立索引时,一个物理块应有一个索引表目(即:无直接地址项)。该文件至少应该建立(填空1) 级索引? 索引应占(填空2)个物理块? 该文件总共占用多少([填空3]) 物理块 ?

答案：3；111；1111

例题：设某文件为链接文件由5个逻辑记录组成,每个逻辑记录的大小与磁盘块大小相等,均为512字节,并依次存放在50、121、75、 80、63号磁盘块上。若要存取文件的第1569逻辑字节处的信息, 问要访问哪一个磁盘块?[填空],该磁盘块第几个字节?[填空2]

答案：80；33

解析：1569/512得到商为:3, 余数为:33。所以,访问的是 80磁盘块的第33个字节。

例题： 【2018统考真题】某文件系统采用索引结点存放文件的属性和地址信息, 蔟大小为4KB。每个文件索引结点占64B, 有11个地址项, 其中直接地址项8个, 一级二级和三级间接地址项各1个,每个地址项长度为4B。请回答下列问题：
问题1: 该文件系统能支持的最大文件长度是多少?「填空1]KB+[填空2]MB+[填空3]GB+[填空4]TB
问题2: 文件系统用1M(1M=2^20)个簇存放文件索引结点, 用512M个簇存放文件数据。若一个图像文件的大小为5600B,则该文件系统最多能存放多少填空M个这样的图像文件？
问题3: 若文件F1的大小为6KB, 文件F2的大小为40KB,则该文系统获取F1和F2最后一个蔟的族号需要的时间是否相同？

答案：32；4；4；4；64；不同

解析：

问题一：直接地址项可以存储：4KB * 8 = 32KB

每个簇能够存储的地址项有4KB/4B = 1024个

一级地址可以存储：1024 * 4KB = 4MB

二级地址可以存储：1024 * 4MB = 4GB

三级地址可以存储：1024 * 4GB = 4TB

问题二：1M个簇可以存放：1M * 4KB / 64B = 64M个文件索引节点

一个图像5600B占两个簇，对于512M个簇来说最多可以存放512M/2 = 256M个图像，但是文件系统中只有64M个索引节点，所以最多只能存储64M这样的图像文件。

问题三：直接地址项能够存储32KB，由于F1的大小只有6KB所以文件可以直接从直接地址中读出，F2的大小32KB需要从一级索引去读取。故两个文件的读取时间不一样。

例题如果一个索引节点为128B, 指针长4B, 状态信息占用68B, 而每块大小为8KB问在索引节点中有多大空间给指针?使用直接、一次间接、二次间接和三次间接指针分别可表示多大的文件? (1) 直接指针表示多少B？ (2) 一次间接指针表示多少MB？ (3) 二次间接指针表示多少GB? (4) 三次间接指针表示多少TB?

答案：98304;16;8;16

解析：索引节点为128B，状态信息占用68B，留给指针的有128B-68B=60B的大小。一个索引块中一共有60/4 = 15 个指针。一级指针有15-3 = 12个；12 * 8KB = 96KB = 98304B

一块中可以存储8KB/4B = 2048个盘块指针，一次间接指针可以表示2048*8KB = 16MB

二次间接指针可以存储：2048 2048 8KB = 2048 * 16MB = 32GB

三次间接指针可以存储：2048 * 32GB = 64TB

例题：某文件系统中, 每块大小为2KB, 每块地址用4B表示, 地址结构采用UINX系统方案,即:10个直接地址(addr[0]~addr[9]) 一级索引(addr[10])、二级索引 (addr[11]和三级索引(addr[12]) 地址各一个。试转换下列文件的字节偏移量为物理地址 (计算它们对应于索引节点的第几号地址项, 块内偏移量是多少?) (1) 12345位于Addr[填空1]中, 偏移量为[填空2] (2) 450000位于Addr[填空3]中, 偏移量为[填空4]

答案：6; 57; 10; 1488

解析：10个直接地址可以存储10*2KB = 20KB = 20480B

故12345在直接地址的储存范围内：

12345 // 2048 = 6

12345 % 2048 = 57

一块可以存储2KB/4B = 512个指针, 一级地址一共可以存储512*2KB = 1MB > 450000B, 存储在Addr[10]中

450000 % 2048 = 1488

例题：某文件系统中, 每块大小为2KB, 每块地址用4B表示,地址结构采用下述方案10个直接地址, 两个一级索引地址和一个二级索引地址试求
(1) 该系统能管理的最大文件是多少[填空1]KB?
(2) 若有一个逻辑大小为256MB的文件,采用上述方式存储在外存,请问该文件占用多少个盘块[填空2]?

答案：526356; 131329;

解析：（1）一块中一共可以存储2KB/4B = 512个地址；

直接地址可以存储10 * 2KB = 20KB

两个一级地址可以存储2 512 2KB = 2048KB

一个二级地址可以存储512 * 1024KB = 524288KB

最大文件大小为：20 + 2048 + 524288 = 526356 KB

（2）计算这种题目的思路是：文件占用的盘块数 = 储存占用的盘块 + 索引盘块

256MB的文件需要占用256MB / 2KB = 128K个盘块（储存盘块）

一个一级地址可以索引512个盘块，两个一级地址可以索引1024个盘块

二级地址也就需要所以索引128K - 10 - 2*512 个盘块

（128K -10 - 2*512）/ 512 = 254（向上取整）

那么一共就需要2（两个一级地址索引盘块）+1（二级索引地址盘块）+254（二级地址中的一级索引盘块） = 257

一共需要：128K + 257 = 131329个盘块

tip

需要注意的是：有的同学（比如我）可能会把最后的结果加上一个10，这是由于没有理解地址和储存之间的关系导致的。直接地址就是存储在地址当中的，不需要额外的去找盘块给它存储。所以计算索引盘块的时候不需要加上它；

例题：一个大小为64MB+40KB的文件,按照UNIX多级索引存储,盘块大小为4KB,采用4字节编址,地扯结构中共有 10个直接地址,一次间接地址、二次间接地址和三次间接地址各一个, 请问该文件共需占用多少个索引盘块[填空1]?如果是61MB的文件呢[填空2 ] ?

答案：17；17

解析：一个盘块可以存储4KB/4B = 1024个地址；

10个直接地址可以存储：10 * 4KB = 40KB

一次间接地址可以存储： 1024 * 4KB = 4MB

二次间接地址可以存储： 1024 * 4MB = 4GB

该文件存储一共需要（64MB + 40KB）/ 4KB = 16K + 10个盘块

一次间接地址可以索引1K个地址

二次间接地址需要(16K + 10 -1K - 10) / 1024 = 15个索引盘块

一共需要15+1+1 = 17个索引盘块

61MB也同理进行计算可以得到需要17个索引盘块

第六章并发程序设计

计算题

进程编程

tip

PV操作题目分析步骤: 1.关系分析。找出题目中描述的各个进程,分析它们之间的同步、互斥关系。 2.整理思路。根据各进程的操作流程确定P、V操作的大致顺序。 3.设置信号量。设置需要的信号量,并根据题目条件确定信号量初值。(互斥信号量初值一般为 1,同步信号量的初始值要看对应资源的初始值是多少)

生产者消费者进程

参考视频：https://www.bilibili.com/video/BV1YE411D7nH?p=23

系统中有一组生产者进程和一组消费者进程,生产者进程每次生产一个产品放入缓冲区,消费者进程每次从缓冲区中取出一个产品并使用。(注:这里的“产品”理解为某种数据) 生产者、消费者共享一个初始为空、大小为n的缓冲区。

只有缓冲区没满时,生产者才能把产品放入缓冲区,否则必须等待。（同步关系，缓冲区满时，生产者要等待消费者取走产品）

只有缓冲区不空时,消费者才能从中取出产品,否则必须等待。（同步关系，缓冲区空时候（即没有产品时），消费者要等待生产者放入产品）

缓冲区是临界资源,各进程必须互斥地访问。（互斥关系）

semaphore mutex = 1; // 互斥信号量，实现对于缓冲区的互斥访问
semaphore empty = n; // 同步信号量，表示空闲缓冲区的数量
semaphore full = 0; // 同步信号量，表示产品的数量，也即非空缓冲区的数量

// 生产者逻辑
producer() {
    while(1){
        生产一个产品;
    P(empty);
    P(mutex);
    把产品放入缓冲区;
    V(mutex);
    V(full);
    }
}

// 消费者逻辑
consumer(){
    while(1){
        P(full);
    P(mutex);
    从缓冲区取出一个产品;
    V(mutex);
    V(empty);
    使用产品;
    }
}

tip

生产者消费者问题是一个互斥、同步的综合问题。

有时候消费者需要等待生产者生产，有时候是生产者要等待消费者消费，这是两个不同的“一前一后的问题”，因此也需要设置两个同步信号量。

多生产者多消费者问题

参考视频：https://www.bilibili.com/video/BV1YE411D7nH?p=24

问题描述：桌子上有一只盘子,每次只能向其中放入一个水果。爸爸专向盘子中放苹果,妈妈专向盘子中放橘子,儿子专等着吃盘子中的橘子,女儿专等着吃盘子中的苹果。只有盘子空时,爸爸或妈妈才可向盘子中放一个水果。仅当盘子中有自己需要的水果时,儿子或女儿可以从盘子中取出水果。用PV操作实现上述过程。

问题分析：

关系分析
互斥关系：盘子要进行互斥的访问
同步关系（一前一后）：
1. 父亲放苹果后，女儿吃苹果
2. 母亲放橘子后，儿子吃橘子
3. 盘子为空后，父亲/母亲放水果
整理思路
设置信号量
1. apple = 0
2. orange = 0
3. mutex = 1
4. plate = 1

semaphore mutex = 1;
semaphore apple = 0;
semaphore orange = 0;
semaphore plate = 1;

dad(){
  while(1){
    准备苹果;
    P(plate);
    P(mutex);
    放入苹果;
    V(mutex);
    V(apple);
  }
}

mom(){
  while(1){  
    准备橘子;
    P(plate);
    P(mutex);
    放入橘子;
    V(mutex);
    V(orange);
  }
}

son(){
  while(1){ 
    P(orange);
    P(mutex);
    拿橘子;
    V(mutex);
    V(plate);
    吃掉橘子;
  }
}

daughter(){
  while(1){ 
    P(apple);
    P(mutex);
    拿苹果;
    V(mutex);
    V(apple);
    吃掉苹果;
  }
}

tip

总结：在生产者消费者问题中，如果缓冲区大小为1，那么有可能不需要设置互斥信号量就可以实现互斥访问缓冲区的功能。当然这不绝对的，要具体问题具体分析。但是当缓冲区大小大于1时就一定要设置互斥信号量，保险起见我们都设置互斥信号量肯定不会出错。

吸烟者问题

参考视频：https://www.bilibili.com/video/BV1YE411D7nH?p=25

假设一个系统有三个抽烟者进程和一个供应者进程。每个抽烟者不停地卷烟并抽掉它,但是要卷起并抽掉一支烟,抽烟者需要有三种材料:烟草、纸和胶水。三个抽烟者中,第一个拥有烟草第二个拥有纸、第三个拥有胶水。供应者进程无限地提供三种材料,供应者每次将两种材料放桌子上,拥有剩下那种材料的抽烟者卷一根烟并抽掉它,并给供应者进程一个信号告诉完成了,供应者就会放另外两种材料再桌上,这个过程一直重复(让三个抽烟者轮流地抽烟)

关系分析：
1. 互斥问题：桌子可以抽像为容量为1的缓冲区
2. 同步问题：
  桌子上有组合一：第一个抽烟者取走东西
  桌子上有组合二：第二个抽烟者取走东西
  桌子上有组合三：第三个抽烟者取走东西
  发出信号：供应者将下一个组合放到桌子上
整理思路
设置信号量
因为缓冲区的大小为1，所以我们可以考虑不设置互斥信号量
offer1 = 0
offer2 = 0
offer3 = 0
finish = 0

semaphore offer1 = 0;
semaphore offer2 = 0;
semaphore offer3 = 0;
semaphore finish = 1;
int i = 0; // 用于实现“三个抽烟者轮流吸烟”

provider(){
    while(1){
        P(finish)
        if(i==0){
            将组合1放在桌子上;
            V(offer1);
        }else if(i==1){
            将组合2放在桌子上;
            V(offer2);
        }else{
            将组合3放在桌子上;
            V(offer3);
        }
        i = (i+1)%3;
    }
}


smoker1(){
  while(1){
   P(offer1);
  从桌上拿走组合1;
  卷烟;
  抽烟;
  V(finish);
  }

}

smoker2(){
  while(1){
    P(offer2);
    从桌上拿走组合2;
    卷烟;
    抽烟;
    V(finish);
  }
    
}

smoker3(){
  while(1){
    P(offer3);
        从桌上拿走组合3;
    卷烟;
    抽烟;
    V(finish);
  }
}

读者-写者问题

参考视频：https://www.bilibili.com/video/BV1YE411D7nH?p=26

有读者和写者两组并发进程,共享一个文件,当两个或两个以上的读进程同时访问共享数据时不会产生副作用,但若某个写进程和其他进程(读进程或写进程)同时访问共享数据时则可能导致数据不一致的错误。因此要求:①允许多个读者可以同时对文件执行读操作;②只允许一个写者往文件中写信息;③任一写者在完成写操作之前不允许其他读者或写者工作:④写者执行写操作前,应让已有的读者和写者全部退出。

semaphore rw = 1; // 用于实现对文件的互斥访问
int count = 0; // 记录当前有几个读进程在访问文件
semaphore mutex = 1; // 用于保存对count的互斥访问
semaphore w = 1; // 用于实现写优先

writer(){
  while(1){
    P(w);
    P(rw);
    写文件...;
    V(rw);
    V(w);
  }
}


reader(){
  while(1){
    P(w);
    P(mutex);
    if(count == 0){
      P(rw);
    }
    count++;
    V(mutex);
    V(w);
    读文件...;
    P(mutex);
    count--;
    if(count==0)
      V(rw);
    V(mutex);
  }
}

tip

总结：读者-写者问题为我们解决复杂的互斥问题提供了一个参考思路。

其核心思想在于设置了一个计数器count用来记录当前正在访问共享文件的读进程数。我们可以用count的值来判断当前进入的进程是否是第一个/最后一个读进程，从而做出不同的处理。

另外，对count变量的检查和赋值不能一气呵成导致了一些错误，如果需要实现一气呵成，自然应该想到用互斥信号量。

哲学家进餐问题

一张圆桌上坐着5名哲学家,每两个哲学家之间的桌上摆一根筷子,桌子的中间是一碗米饭。哲学家们倾注毕生的精力用于思考和进餐,哲学家在思考时,并不影响他人。只有当哲学家饥饿时オ试图拿起左、右两根筷子(一根一根地拿起)。如果筷子已在他人手上,则需等待。饥饿的哲学家只有同时拿起两根筷子才可以开始进餐,当进餐完毕后,放下筷子继续思考。

关系分析：系统中有5个哲学家进程,5位哲学家与左右邻居对其中间筷子的访问是互斥关系
整理思路。这个问题中只有互斥关系,但与之前遇到的问题不同的事,每个哲学家进程需要同时持有两个临界资源才能开始吃饭。如何避免临界资源分配不当造成的死锁现象,是哲学家问题的精髓。
信号量设置。定义互斥信号量数组 chopstick5]={1,1,1,11用于实现对5个筷子的互斥访问。并对哲学家按0~4编号,哲学家i左边的筷子编号为i,右边的筷子编号为(i+1)%5

semaphore chopstick[5] = {1,1,1,1,1};
semaphore count = 4; // 最多只允许4个哲学家同时吃饭
Pi(){
  while(1){
    P(count);
    P(chopstick[i]);
    P(chopstick[(i+1)%5])
    吃饭;
    V(chopstick[i]);
    V(chopstick[(i+1)%5])
    V(count);
  }
}

tip

总结：哲学家进程问题的关键在于解决进程死锁。

这些进程之间只存在互斥关系，但是与之前接触到的互斥关系不同的是，每个进程都需要同时持有两个临界资源，因此就有死锁问题的隐患。

如果在考试中遇到了一个进程需要同时持有多个临界资源的情况。应该产考哲学家进餐的思想，分析题中给出的进程之间是否会发生循环等待，是否会发生死锁。

雨课堂作业题

tip

作业题太简单了，我就把填空题都改成了编程题，哇哈哈；

PV操作

假定有如下独木桥问题:过桥时,同一方向的行人可连续过桥,当某一方有人过桥时,另方向的行人必须等待;当某一方向无人过桥时,另一方向的行人可以过桥。写出用信号量机制解决此问题的算法。

解：

这道题可以抽象为读者-写者问题；

关系分析：问题中只有互斥关系
整理思路: 一个人可以过桥都条件是桥上没有人或者有同方向的人，可以设置一个信号量表示桥的占用情况（互斥占用）。
信号量设置：
A方向正在通行的人数：用于对于ACount的互斥访问 MutexA = 1, 用于对于BCount的互斥访问：MutexB = 1，用于对于独木桥的互斥访问: CoMutex = 1。

可对应写出如下程序：

int ACount = 0;
int BCount = 0;
semaphore MutexA = 1;
semaphore MutexB = 1;
semaphore CoMutex = 1；

PAi(){
  while(1){
    P(MutexA);
    if(ACount == 0)
      P(CoMutex);
    ACount++;
    V(MutexA);
    过桥...
    P(MutexA);
    Acount--;
    if(ACount == 0)
      V(CoMutex);
    V(MutexA);
  }
}


PBi(){
  while(1){
    P(MutexB);
    if(BCount == 0)
      P(CoMutex);
    BCount++;
    V(MutexB);
    过桥....
    P(MutexB);
    BCount--;
    if(BCount == 0)
      V(CoMutex);
    V(MutexB);
  }
}

某车站售票厅,任何时刻最多可容纳20名购票者进入,当售票厅中少于20名购票者时则厅外的购票者可立即进入,否则需在外面等待。若把一个购票者看作一个进程, 写出用信号量机制解决的算法

解析：这个问题是一个典型的生产者与消费者模型，消费者都不需要逻辑的，来一个处理一个，只需要编写生产者的算法即可

直接上代码吧

semaphore mutex = 20; // 用于计数

Buyer(){
  while(1){
    P(mutex);
    进入...
    购票...
    V(mutex)   
  }
;
}

当然了这道题目也可以改的复杂一点，请看下题：

某车站售票厅,任何时刻最多可容纳20名购票者进入,当售票厅中少于20名购票者时则厅外的购票者可立即进入,否则需在外面等待。车站内有两个自动门，购票者可以通过自动门进出。每个自动门在同一时刻只能进入/出去一个购票者。若把一个购票者看作一个进程, 写出用信号量机制解决的算法

解析：

关系分析：用户与用户之间对于自动门的访问是互斥的，自动门是进还是出也是互斥的。
信号量设置：numMutex用于实现大厅的互斥访问，初始化为20；doorMutex用于实现自动门的互斥访问，初始化为2；

semaphore numMutex = 20;
semaphore doorMutex = 2;

Buyer(){
  while(1){
    P(numMutex); 
    P(doorMutex);
    进入...
    V(doorMutex);
    购票...
    P(doorMutex);
    离开...
    V(doorMutex);
    V(numMutex); 
  }

}

某交通路口设置一个自动计数系统,该系统由“观察者”进程和“报告者”进程组成。观察者进程能识别卡车,并对通过的卡车计数,报告者进程定时(可设为每隔一小时,准点时)将观察者的计数值打印输出,每次打印后把计数值清“0”。两个进程的并发执行可完成对每小时中卡车流量的统计,这两个进程的算法描述如下,请初始化此程序,并用PV操作进行编程

解析：这就是披了一个皮的生产者与消费者问题

关系分析：观察者识别卡车，对卡车的数量加一。计数者每个一个小时对卡车的数量进行计数。两者对与信号量的访问是互斥访问的

信号量设置：mutex = 1

semaphore mutex = 1;
int count = 0;

Observer(){
  while(1){
        if(观察到卡车){
      P(mutex);
      count++;
      V(mutex);
    }
  }
  
}

Counter(){
  while(1){
    if(时间间隔一小时){
      P(mutex);
      count = 0;
      V(mutex);
    }
  }
}

三个进程A、B、C,共享两个缓冲区B1和B2。缓冲区B1中可存放n件产品, 缓冲区B2中可存放 m件产品。进程A每次生产一件产品并将其存入缓沖区B1中;进程B每次从缓冲区B1中取出一件产品后再把它送到缓冲区B2中进程C每次从缓冲区B2中取出件产品去消费。为防止把产品存入已满的缓冲区,或从空的缓冲区取产品、或重复取产品,试用PV操作实现它们之间的制约。

解析: ....

死锁

系统有同类资源m个,供n个进程共享,若每个进程对资源的最大需求量为k,试问,当m、n、k分别为下列情况时,是否会发生死锁
$\begin{array}{|c|c|c|c|c|} \hline \text { 序号 } & \mathrm{m} & \mathrm{n} & \mathrm{k} & \text { 是否会死锁 } \\ \hline 1 & 6 & 3 & 3 & \mathrm{} \\ \hline 2 & 9 & 3 & 3 & \mathrm{} \\ \hline 3 & 13 & 6 & 3 & \mathrm{} \\ \hline \end{array}$

解析：

序号1: 6 < 3(3-1)+1 可能会发生死锁

序号2: 9 > 3(3-1)+1 不会发生死锁

序号3: 13 = 3(6-1)+1 不会发生死锁

tip

判断进程是否发生死锁的条件是：进程中资源格式 >= 进程个数(进程最大需求量-1) + 1

在银行家算法中,若出现以下资源分配情况
试问:
(1) 该系统状态是安全的吗? (2) 如果进程依次有如下资源请求,系统是否能进行资源分配? P1: (1,0,2) P4: (3,3,0) P0：(0,2,0)
系统将怎样进行资源分配?

解析：

（1）由银行家算法可得出安全序列：P1、P3、P4、P0、P2；当前的系统是安全的

（2）

如果分配给P1（1，0，2）那么系统有安全序列，能进行资源分配

如果分配给P4（3，3，0）那么系统将进入不安全状态，所以不能进行资源分配

如果分配给P0（0，2，0）那么系统将进入不安全状态，所以不能进行资源分配

假设某系统有同类资源12个,有个进程P1,P2,P3来共享,已知P1、P2、P3所需要资源总数分别为8,6,9,它们申请资源的次序和数量如表所示,系统采用银行家算法为它们分配资源。 (1) 哪两次申请分配会使系统进入不安全状态 ? (2) 执行完前某3次申请,再执行完序号为6的申请后,安全序列是
$\begin{array}{|l|l|l|} \hline \text { 序号 } & \text { 进程 } & \text { 申请量 } \\ \hline 1 & \text { P1 } & 4 \\ \hline 2 & \text { P2 } & 4 \\ \hline 3 & \text { P3 } & 2 \\ \hline 4 & \text { P1 } & 1 \\ \hline 5 & \text { P3 } & 2 \\ \hline 6 & \text { P2 } & 2 \\ \hline \end{array}$

解析：

P1还需资源	P2还需资源	P3还需资源	假设分配系统剩余资源	是否分配？
4	6	9	8	是
4	2	9	4	是
4	2	7	2	是
3	2	7	1	否
4	2	5	0	否
4	0	7	6	是

（1）根据上述的表格进行分析，序号为4和5的申请会让系统进入不安全的状态；

（2）执行完前3次（1，2，3）申请后，再执行6号，执行完6号后P2所有的资源都得到了，返回申请到的6个资源，此时P1可以得到所有的资源了，P1返回资源之后，P3也可以得到所有需要的资源。

所以上述的安全序列是P2->P1->P3

某系统有n台互斥使用的同类设备,3个并发进程各需要4 台设备,可确保系统不发生死锁的设备数n最小为

解析：10

n >= 3*(4-1) + 1 = 10

设有11个同类资源可供四个进程共享,资源分配情况如表,当进程P1,P2,P3,P4又都相继提出1个资源的申请要求,为使系统不致死锁,应先满足哪个进程的要求 ?
$\begin{array}{c|cc} \hline \text { 进程 } & \text { 已占用资源 } & \text { 最大需求数 } \\ \hline \text { P1 } & 2 & 5 \\ \text { P2 } & 2 & 5 \\ \text { P3 } & 4 & 6 \\ \text { P4 } & 1 & 4 \end{array}$

解析：P3

当系统按照上述表格分配资源后各个进程分别还需要的资源有：3，3，2，3，此时系统中还有2个资源。当四个进程相继提出1个资源的请求时，分配给P1和P2会让系统进入不安全的状态，分配给P3系统还可以产生安全序列，因此需要优先满足P3进程的要求。

[2016统考真题] 系统中有3个不同的临界资源R1、R2和R3 被4个进程P1、P2、P3、P4 共享各进程对资源的需求为: P1申请 R1和R2, P2申请R2和R3, P3申请R1和R3, P4申请R2。若系统出现死锁,则处于死锁状杰的进程数至少是。

解析：3

死锁的发生需要以下条件:

互斥条件
不剥夺条件
请求并保持条件
循环等待条件

本题的关键正在于34条件,若要发生死锁,则必须形成环路,做出资源分配图,则只有当P1,P2,P3分别占有一个资源并请求下一个资源时满足条件34.此时,处于死锁的进程数取决于P4是否发生死锁,有两种情况

P4事先已经获取了R2,成功运行,故死锁进程数为3
P4尚未获得R2,未运行,死锁进程数为4

进阶题目

因新冠疫情控制需要，某大学对图书馆阅览室进行了改造，每间隔1.5米摆放桌椅一套，每间阅览室共有桌椅30套，该阅览室有一个入口（每次仅限一人通过）和一个出口（每次仅限一人通过），规定只有当阅览室的桌椅有空闲时才允许进入，用信号量和PV操作描述这个事件。

关系分析，互斥关系
信号量：count = 30表示30套座椅，doorIn = 1， doorOut = 1

semaphore count = 30;
semaphore doorIn = 1;
semaphore doorOut = 1;

Student(){
    while(1){
        P(count);
        P(doorIn);
        进门...
        V(doorIn);
        学习...
        P(doorOut);
        出门...
        V(doorOut);
        V(count);
    }
}

有一只大笼子，最多能装5只动物，但每次只能放一只动物，猎手向笼中放老虎，农民向笼中放猪，动物园等着买笼中的老虎，屠宰场等着买笼中的猪，试分析该问题并用P、V操作写出它们能同步执行的程序（提示：老虎和猪不能同时处在笼子内）。

关系分析：同步问题，互斥问题
信号量设计：笼子：mutex = 1，pig = 0, tiger =

// 方案1
semaphore pigMutex = 1;
semaphore tigerMutex = 1;
semaphore empty = 5;
semaphore full = 0;
semaphore CoMutex = 1; // 用于笼子的互斥访问
int pigCount = 0;
int tigerCount = 0;

hunter(){
    while(1){
        P(tigerMutex);
    if(tigerCount == 0)
      P(CoMutex); // 锁笼子
    P(empty);
    tigerCount++;
    V(tigerMutex);
    V(full);
    }
}

farmer(){
    while(1){   
        P(pigMutex);
    if(pigCount == 0)
      P(CoMutex); // 锁笼子
    P(empty);
    pigCount++;
    V(pigMutex);
    V(full);
    }
}

zoo(){
    while(1){
    P(tigerMutex);
    if(tigerCount>0){
      P(full);
      tigerCount--;
      V(empty);
    }
    if(tigerCount==0)
      V(Comutex);
    V(tigerMutex);
    }
}

slaughter(){
    while(1){
    P(pigMutex);
    if(pigCount>0){
      P(full);
      pigCount--;
      V(empty);
    }
    if(pigCount==0)
      V(Comutex);
    V(pigMutex);
    }
}

// 方案2
sema tiger = 0;
sema mutexTiger = 1;
sema pig = 0;
sema mutexPig = 1;
sema mutexCount = 1;
sema longzi = 0;
int count;

hunter() {
    while(1) {
        P(mutexTiger);
        P(mutexCount);
        if (count == 0) {
            P(mutexPig);
        } else if (count == 5) {
            P(longzi);
        }

        count ++;
        V(tiger);

        V(mutexCount);
        V(mutexTiger);
    }
}

farmer() {
    whlie(1) {
        P(mutexPig);
        P(mutexCount);

        if (count == 0) {
            P(mutexTiger);
        } else if (count == 5) {
            P(longzi);
        }
        count ++;
        V(pig);

        V(mutexCount);
        V(mutexPig);
    }
}

zoo() {
    while(1) {
        P(tiger);
        P(mutexCount);

        if (count == 5) V(longzi);
        count --;

        if (count  == 0) {
            V(mutexPig);
        }

        V(mutexCount);
    }
}

slaughter() {
    while(1) {
        P(pig);
        P(mutexCount);

        if (count == 5) V(longzi);
        count --;

        if (count  == 0) {
            V(mutexTiger);
        }

        V(mutexCount);
    }
}

往年试卷

分析计算题（80分）

考作业调度问题（10分）

银行家调度问题（10分）

页面地址转换

（1）计算页号和页内地址分别占多少位

（2）虚地址（逻辑地址）转化为物理地址

（3）虚地址（逻辑地址）转化为物理地址（发生了缺页）

逻辑地址结构+页面调度（12分）

（1）根据逻辑地址求页号

（2）页面调度结合地址转换

（3）CLOCK调度结合地址转换

优化分布（8分）

硬盘调度算法（8分）

（1）电梯调度

（2）SSTF（最短寻道）

（3）平均寻道距离（总寻道长度 / 序列数）

计算文件存储格式

死锁判断（10分）

程序设计与分析（20分）

PV操作

就是上述的多生产者多消费者问题的模型

桌上有一只盘子,可容纳10个水果,每次只能放入/取出一个水果。爸爸专向盘子中放苹果( apple),妈妈专向盘子中放桔子( orange)儿子专等吃盘子中的桔子,一个女儿专等吃盘子里的苹果。请用信号量和PV操作写出能够正确执行的同步算法；

分析多进程导致的程序不确定性

两个优先级相同的进程,信号量s1,s2的初值均为0.试问:进程并发执行完,X、Y、Z的值各为多少？

课程笔记

第一章​

简答题​

三种基本的OS​

第二章处理器调度作业​

简答题​

处理器两种最基本的状态​

什么是中断​

进程的状态转换​

进程控制块（PCB）的作用​

进程调度算法的比较​

作业计算题​

进程调度算法​

第三章 内存​

简答题​

计算题​

内存地址分配算法​

页面置换算法​

根据页表结构进行计算​

页表地址转换​

快表时间消耗​

段式存储​

进阶题目​

第四章 设备管理​

计算题​

硬盘调度算法​

第五章 文件管理​

简答题​

计算题​

tip

第六章 并发程序设计​

计算题​

进程编程​

tip

生产者消费者进程​

tip

多生产者多消费者问题​

tip

吸烟者问题​

读者-写者问题​

tip

哲学家进餐问题​

tip

雨课堂作业题​

tip

PV操作​

死锁​

tip

进阶题目​

往年试卷​

分析计算题（80分）​

考作业调度问题（10分）​

银行家调度问题（10分）​

页面地址转换​

逻辑地址结构+页面调度（12分）​

优化分布（8分）​

硬盘调度算法（8分）​

计算文件存储格式​

死锁判断（10分）​

程序设计与分析（20分）​

PV操作​

分析多进程导致的程序不确定性​

第一章

简答题

三种基本的OS

第二章处理器调度作业

简答题

处理器两种最基本的状态

什么是中断

进程的状态转换

进程控制块（PCB）的作用

进程调度算法的比较

作业计算题

进程调度算法

第三章内存

简答题

计算题

内存地址分配算法

页面置换算法

根据页表结构进行计算

页表地址转换

快表时间消耗

段式存储

进阶题目

第四章设备管理

计算题

硬盘调度算法

第五章文件管理

简答题

计算题

第六章并发程序设计

计算题

进程编程

生产者消费者进程

多生产者多消费者问题

吸烟者问题

读者-写者问题

哲学家进餐问题

雨课堂作业题

PV操作

死锁

进阶题目

往年试卷

分析计算题（80分）

考作业调度问题（10分）

银行家调度问题（10分）

页面地址转换

逻辑地址结构+页面调度（12分）

优化分布（8分）

硬盘调度算法（8分）

计算文件存储格式

死锁判断（10分）

程序设计与分析（20分）

PV操作

分析多进程导致的程序不确定性