章节提要
占比 5-7分
一、进程管理
（注：下图来自前言中up主视频）
（说明：计算机系统层次结构）
1、进程的状态
1）运行：当一个进程在CPU上运行时，则称该进程处于运行状态。
2）就绪：当一个进程除CPU外其他一切资源全部获得，则称该进程处于就绪状态
3）等待（阻塞或睡眠）：当一个进程除CPU外还缺少其他资源，则称该进程处于等待状态。
（时间片轮转来分配CPU资源，即一个进程从就绪到运行只能运行一个时间片，等时间片到无论任务是否完成均退出运行态转为就绪态，等待下一次调度（时间片轮转））
2、前趋图
前趋图是一个 有向无循环图。
（注：下图来自《软件设计师教程》（第5版）（褚华、霍秋艳主编，清华大学出版社））
3、进程的同步与互斥
1） 同步与互斥不互为“反义词”。同步是合作进程间的直接制约问题，互斥是申请临界资源进程间的间接制约问题。
2）进程的同步：在系统中一些需要相互合作、协同工作的进程。
2）进程的互斥：系统中多个进程因争用临界资源而互斥执行。
4、PV操作
1）临界资源：诸进程间需要互斥方式对其进行共享的资源，如打印机、磁带机等。
2）临界区：每个进程中访问临界资源的那段代码称为临界区。
3）信号量S：是一种特殊的变量。S>=0表示某资源的可用数，若S<0,则其绝对值表示阻塞队列中等待该资源的进程数。
4）P操作定义：S=S-1，若S>=0，则执行P操作的进程继续执行；若 S<0,则置该进程为 阻塞 状态（因为无可用资源），并将其插入阻塞队列。
5）V操作定义：S=S+1，若S>0，则执行V操作的进程继续执行；若 S<=0,则从阻塞状态 唤醒 一个进程，并将其插入就绪队列，然后执行V操作的进程继续。
6）练习题
正确答案：AC
解析：付款后需要有V操作来唤醒收银员的收费操作，即a1为V操作，来唤醒b1相同信号量的P操作（没有人付款收银员的收款操作处于“阻塞”状态，有人付款才唤醒收银员的收费操作）；而购书者付款后，需要等待收银员的收费操作完成，即付款后还需要P操作进行阻塞（a2）,等待收费完成后的V操作进行唤醒（b2）。由此可知a1和b1是相同信号量的V操作和P操作，a2和b2是相同信号量的P操作和V操作。
PV操作解题的核心是找出约束关系（假设先执行某一个进程，然后看会发生什么问题，加入PV操作后可以解决此问题则为正确答案）。
6、PV操作与前趋图
1）例题
正确答案：CAA
解析：（v处理，P等待），将用到的信号量标到线上（从上到下，从左到右）
每条线箭头的起点位置是V操作，箭头的终点位置是P操作.
（注：下图来自希赛网解析）
（说明：前驱图解题方法）
前驱图解题具体方法说明：有几个箭头需要几个信号量（每个箭头信号量按进程编号组成的十进制数从小到大或者直接按上面的方法进行编号），每个进程完成后 （即指出的箭头）需要执行V操作；每个进程开始前（即指入的箭头）需要执行P操作。
（注：下图来自前言中up主视频）
（说明：共4个箭头，需4个信号量；四个箭头分别是P1->P2、P2->P3、P3->P4、P1->P3。按箭头两端的进程编号组成的十进制数从小到大排序：P1->P2、P1->P3、P2->P3、P3->P4（因为12<13<23<34）。所以依次对四个箭头赋予四个信号量：S1、S2、S3、S4。针对每个箭头对箭头指出端为V操作，箭头指入端为P操作即可）
PV操作是操作系统提供的具有特定功能的原语。利用PV操作可以 实现资源的互斥使用。
P操作用来检查资源是否可用；V操作用来释放资源。
（注：下图来自希赛网）
（说明：进程管理PV操作相关）
信号量的取值范围：（资源数-进程数）~ 资源数（常考）
（注：下图来自前言中up主视频）（了解即可，重点掌握前趋图）
（说明：互斥信号量在一个图中成对出现，而同步信号量在两个图中交叉出现）
7、死锁问题
1）概念：
（注：下图来自前言中up主视频）
（说明：发生死锁条件）
正确答案：13
解析：系统不可能发生死锁的最小资源数n：n>=(w-1)*m+1
（m个进程，每个进程需要资源w个）
利用上述可求得n>=(5-1)*3+1=13。
3）银行家算法
-内容：
-例题:
正确答案：B
解析：
进程资源图（补充）
（注：下图来自前言中up主视频）
（说明：处理进程资源图相关问题原则：先分配（资源），再申请（资源）；或者先申请（资源）再分配（资源），从而判断是否能够满足要求，如果可以则为非阻塞结点，不可满足则为阻塞结点。方法：从非阻塞结点开始化简，当非阻塞结点满足条件后释放其申请的资源，对剩余进程继续进行分配/申请。当所有进程均可完成时，称该图是 可化简的）
（分配：指向P的箭头；申请：P指出的箭头）
（非阻塞结点：可完成；可化简（存在一种次序，可以使进程完成））
当一个进程资源图中所有结点均为阻塞结点时，处于死锁状态。
线程可与同属一个进程的其它线程共享进程所拥有的全部资源（注：线程与线程之间是不可见的）。
真题链接
在支持多线程的操作系统中，假设进程P创建了若干个线程，那么 该进程中某线程的栈指针 是不能被这些线程共享的。
二、存储管理
1、分区存储组织
（25k空间空出来原因：可能之前分配的作业已经执行完）
2、页式存储组织
页面淘汰原则：淘汰在内存中的页号（即状态位为1），优先淘汰访问位为0的页号；若访问位都为1，则优先淘汰修改位为0的页号。（注：淘汰的页号需要在内存中（即淘汰内存中的页号））
分页存储管理：页面大小为4k时，地址结构如图：
（注：下图来自前言中up主视频）
（说明：做题方法：如果逻辑地址为四位十六进制数表示，则 该十六进制数的第一位表示页号，后三位表示页内地址。若要求该逻辑地址转化为的物理地址（ 物理地址=物理块号（页帧号）+页内地址 （该+不是算术加法，是直接将物理块号（页帧号）和页内地址拼接起来就可以），即 求页号对应的物理块号（页帧号）[直接查表]，然后物理块号后面接上页内地址即为物理地址（转换后的物理地址仍然是十六进制））
页面大小为多少kb就看其是2的多少次方，这个次方数就是页内地址的位数，逻辑地址/物理地址中，从后往前，去掉页内地址位数个数字，剩下的为页号。（逻辑地址/物理地址转为二进制后，然后再去掉页内地址位数个数字）
1）例题
正确答案：D、B
解析：逻辑地址=页号+页内地址。页面大小4K=212，说明一个页的页内地址是12位（二进制），高于12位的部分为页号（从右往左数），对应的16进制，页内地址就是3位（从右往左数高于3位的为页号），所以页内地址为A29H，页号为5，物理块号（页帧号）为6（查表），物理地址=页帧号+页内地址，所以物理地址为6A29H。页面淘汰原则：1）淘汰访问位为0；2）多个访问位为0，则淘汰修改位为0。所以淘汰1号页。
3、段式存储组织
4、段页式存储组织
（注：下图来自前言中up主视频）
（说明：分别数有多少位数字（数的位数=大数-小数+1）来表示段号、段内页号或页内地址即可，所求结果即为 2数的位数分别可代表最多的段数、每个段最大允许的页数、页的大小）
5、快表
（快表放在Cache中，慢表放在内存中）
6、页面置换算法
抖动：刚被换出的页面很快又被访问，需重新调入，导致系统频繁地更换页面，以至于一个进程在运行过程中把大部分时间花费在完成页面置换的工作上。
1）例题
2）例题
正确答案：B、C
解析：没有使用快表说明每读一次程序的块，需要先在内存上来查表，然后读取相应的内存块，所以每一个块需要进行两次内存的访问，总共6个块，所以访问12次内存。默认指令一次性调入（无论占几个块），指令跨页产生一次缺页中断，操作数跨页产生两次缺页中断。 所以产生5次缺页中断。
单缓冲区、双缓冲区（补充）
了解即可
（注：下图来自前言中up主视频）
磁盘调度算法（补充）
先来先服务（FCFS）：根据进程请求访问磁盘的先后次序进行调度。
最短寻道时间优先（SSTF）：要求访问的磁道与当前磁头所在的磁道距离最近，使得每次的寻道时间最短。
扫描算法（SCAN）或电梯调度算法：
（注：下图来自前言中up主视频）
单向扫描调度算法（CSCAN）或循环扫描算法：
（注：下图来自前言中up主视频）
真题链接
在移臂（磁盘）调度算法中，先来先服务和最短寻找（道）时间优先 算法可能会随时改变移动臂（磁头）的运动方向。（重复考，重点记忆）
旋转调度算法：
读取记录时间=磁盘旋转速度/记录数。
如果是顺序处理，而且没有对信息存储进行优化，则磁头（磁头初始在0）在读取完一个记录后，然后进行处理，由于磁头在处理过程中不会停止，所以，当磁头处理完之后，到达了按顺序读取的下一个记录的下一个记录（应该处理2，但磁头此时已经到达3），即磁头需要旋转一圈，然后来读取下一个记录。所以处理时间为 读取第一个记录的时间+处理第一个记录的时间+（总记录数-1）*（磁头旋转到应该读取的记录的开始位置的时间+读取单条记录的时间+处理单条记录的时间）（单缓冲区）
如果对信息存储进行优化，即将记录进行顺序处理的间隔分步，即将每一个记录的下一个读取的记录安排在磁头读取完并处理完记录后，这样磁头处理完记录后就可以直接读取下一条记录，不用再旋转一圈，则时间为 总记录数 *（读取单条记录的时间+处理单条记录的时间）（单缓冲区）。
存取时间=寻道时间+旋转延迟时间+传输时间（看清题目是读取多少块，每块之间的寻道时间+块之间的旋转延迟时间和传输时间）。
例题：
（注：下图来自《软件设计师教程》（第5版）（褚华、霍秋艳主编，清华大学出版社））
