概述
课程内容提要
进程管理
进程的状态
运行时候不会一下子全部执行完成，如果任务量大的时候，时间片内没有处理完会重新回到就绪状态排队。
左边的是三态模型，右边是五态模型，对应编程或者人为的阻塞。
前驱图
前驱图表达的是要完成的一系列活动先后的约束关系
进程的同步和互斥
同步 — 异步 互斥 — 互补
PV操作（难点）
信号量S的物理意义, S>=0表示某资源的可用数，S<0, 则其绝对值表示阻塞队列中等待该资源的进程数。
V操作T那里加个箭头好理解些，即如果S <= 0, 从进程队列里面取出放到V操作里面。
类似停车场的收费系统和仓库的管理系统，都是需要把控进和出。
P操作具有阻塞的功能，而V操作具有激活的功能。同一对PV操作可以实现同步进程的阻塞和激活。
实例：并发进程的约束关系，对进程进行加锁解锁。每次执行P操作，s–, 每次执行一次V操作, s++。 执行操作后根据判断条件，进行进程的阻塞和激活。
实战题：
P操作具有阻塞的功能，而V操作具有激活的功能。同一对PV操作可以实现同步进程的阻塞和激活。
PV操作的解题核心关键就是找出进程间的约束关系。
根据这个原理，首先收银员需要阻塞等待购书者的付款操作才能执行，所以a1和b1分别对应同一组信号量的V和P操作。而购书者付款后需要阻塞等待收银员收费后（如登记，图书消磁等操作）通知才可以离开，所以这里a2和b2分别对应同一组信号量的P和V操作。
故选AC， 排除法
前驱图转PV操作
解答：
死锁问题
例题答案：13个
对于这种题目，假设有n个进程，每个进程需要m个系统资源，问系统至少要多少个资源才不会发生死锁。公式是 n * (m - 1) + 1。 因为当任意一个进程拿到它所需要的的资源处理完成后就可以释放资源给其他进程使用了。当然光靠上面的解释其实还是有问题，因为如果这么说只需要m个资源就可以填充任意一个进程了。但是实际上要考虑资源的分配方式，如果存在多个进程请求资源，系统是依次分配的，如此并不会把所有资源一起给到一个进程而忽略其他进程的需求。
死锁的预防和避免。
预防：打破四大条件 — 互斥，保持和等待，不剥夺，环路等待
避免：有序资源分配法（效率低），银行家算法
银行家算法
解答：B
根据表格，R1已分配 1+2+2+1+1=7个，R2已分配 2+1+1+2+1=7个，R3已分配1+1+0+0+3=5个，因此R1只剩2个资源，R2剩1个资源，R3剩0个资源。因此，为了避免发生死锁，第一个执行的进程至少R3不能继续要资源了，排出第一个应该是P2， 故排除AD选项。P2进程结束后可以返还R1资源2个，R2资源2个，R3资源1个。此时， R1剩4个，R2剩2个，R3剩1个，此时P1进程还需要R1资源5个，为了避免发生死锁，排除C，故选B
存储管理
分区存储组织
首次适应算法会找到第一个满足大小的空闲空间分割给新的作业
最佳适应法会把空闲空间从小到大排序，作业放到第一个满足大小的空闲空间中。缺点是分配次数多了之后，整个内存空间的碎块会不断增多
最差适应法会把空闲空间从大到小排序，作业放到第一个满足大小的空闲空间中。
循环首次适应法就是把空闲空间组成一个循环的链表，分配空间的时候在这个链表上找到第一个满足空间大小的位置。
页式存储组织
优点是利用率高，通过把程序断开成一个个片段，根据建立程序与页码的索引，可以实现导入大于内存空间的
程序或资源。
缺点是：建立索引增大了系统开销，可能产生抖动现象。
根据逻辑地址得出物理地址的过程需要通过页面的索引来得出，这种转换无疑就增加了系统开销
页式存储的特点是每页的大小都是固定的，通过逻辑地址得到物理地址
页式存储需要保存页号和块号
右图是根据逻辑地址得出物理地址的方式，通过页号查询页表得到块号，块号+页内地址就是物理地址。
解答：
根据逻辑地址得出物理地址的方式（通过页号查询页表得到块号，块号+页内地址）以及页面大小为4k，可知页面地址的长度为 2^10 * 4 = 2^12, 12个二进制位对应3个16进制位，故页面地址是逻辑地址的十六进制的后三位，即A29， 那么最前面的5就是页号。页号查表可知其块号（页帧号）为6，选D
第二个空淘汰的页面应该在内存中，根据状态位，可以排除3。而且上个空确定了页面5存在内存，并且淘汰的页号应该不在访问位，故排除得答案为B
段式存储组织
根据逻辑结构（如函数）划分段，各段的大小可能是不相同的。
段式存储需要保存段号，段长和基址
段页式存储组织
块表
页面置换算法（页面淘汰算法）
最优算法是无法直接应用的，因为需要根据输入的页面序列调整以达到最优，但是输入是不确定的。通常用于和其他算法比较其他算法的性能。
随机算法就是随机淘汰一个页面，性能不稳定。
先进先出算法里面可能产生的抖动意思就是分配更多的资源但是起不到提高效率的效果
最近最少使用算法，刚刚被访问过的页面不会淘汰出去
上面用的是先进先出算法，解释了上面是抖动。第一个表格分配页面资源是3页，采用算法之后缺页的次数是9. 而增加页面资源到4页后，缺页次数增加到了10.
FIFO： 先进先出算法
LRU： 最近最少使用算法
上图中的√是没有命中，第一个3的位置，因为前面的0命中了，此时内存中的页数为0,1,2， 访问的是1,2,0，
故先进先出算法淘汰第一个内存中的页数0，最近最少使用算法不会淘汰最近使用的页面，故淘汰第一个最后访问的页面1
解答：B， C
因为用户程序就是执行swap指令，它划分成立6个页面。又因为系统中没有使用块表，所以每个页面都分为块号+页面地址，一个页面获取物理地址需要访问2次内存（查表和读取相应的物理地址），故6个页面需要访问12次内存。
1k = 1024b 2 * 1024 = 2048 3 * 1024 = 3072 5 * 1024 = 5120， 根据内存单元位置和图示，可以看出swap， A, B 都是处于两个页之间，执行swap指令时，访问一个页面无法完全载入数据就会导致2次缺页中断（？），因此有6次缺页中断。但是有一个约定俗成（？）就是指令是一定一次载入的，因此指令swap只会导致1次缺页中断，合计5次。
文件管理
索引文件结构
一般的索引文件结构有13个节点( 0 - 13), 分为直接索引，一级间接索引，二级间接索引，三级间接索引。直接索引就是结点对应物理盘块，物理盘块存放索引文件的内容。正常情况下存储的文件大小非常有限，但是引入间接索引后可以扩展存储的容量。间接索引存放的是物理盘块的地址，通过物理盘块的一级一级的索引找到索引文件的内容。
上图中如果一个结点是4k大小的话，一级间接索引存储空间大小为：4 * 1024， 二级间接索引存储空间大小为 4 * 1024 * 1024， 三级依此类推……。间接索引的层数越多，效率越低。
解答：C, D
给空白方块标上逻辑块号依次为0,1,2,3,4,5（这里看出第5对应58）, 因为一个物理盘块1k大，1个地址4字节，所以每个盘块可以存储 1024 / 4 = 256 个地址， 所以261对应位置为 58。
文件和树形目录结构
空闲存储空间的管理
重点：位示图法
取值0和1分别表示空闲和占用
解答：
置为1表示占用
设备管理
数据传输控制方式
重点：程序控制方式（CPU处理，通常不好介入），程序中断方式（具有中断机制，有反馈），DMA方式（又名直接存取控制方式，由DMA控制器管控）
虚设备与SPOOLING技术
解决了外部设备的低速和内部处理的高速的矛盾
微内核操作系统
本文链接： http://www.ionluo.cn/blog/posts/1416bd31.html
版权声明： 本作品采用 知识共享署名-非商业性使用-相同方式共享 4.0 国际许可协议 进行许可。转载请注明出处！
