管程
信号量挺琐碎的，而且容易出错，顺序错了都会影响结果。
管程内的数据只有在管程内的过程（函数）才能访问；一次只允许一个进程进入管程。
monitor 是 java 语法的管程，每次只允许一个进程访问（互斥），进程只能通过管程提供的特定入口进入。我们可以自己定义逻辑判断，让进程等待或释放（同步）。
关键字 synchronized 修饰的函数同一时间段内只能被一个进程访问。
死锁
A等B，B等C，C等A，都在等对方手里的资源。
和饥饿不一样，饥饿是如果一直来新进程自己可能一直无法继续。
死锁的四个条件：
- 互斥，对某一资源互斥使用。
- 不剥夺，不能抢资源。
- 请求和保持，在新资源还在请求时可以保持自己手里已有的资源。
- 循环等待，存在资源的循环等待链。比如有12两个资源，进程一申请顺序：12，进程二申请顺序：21，两者正好互相锁住。
可能发生死锁的情况：
- 竞争不能共用的系统资源时；
- 进程推进顺序不当；（哲学家拿筷子，都先拿左手的）
- 信号量使用不当（如生产者消费者一例，先互斥锁再信号量锁。生产者先进入满仓库，因为当前只有自己进程进入仓库所以互斥锁不干扰；但是仓库已满，无法放入导致阻塞；消费者又因为生产者正在访问，互斥锁限制导致阻塞）。
预防死锁
破坏四个条件之一。
- 把资源改为可以共享使用的；不过不是所有设备都能强行改的。
- 剥夺：要么如果当前进程资源不足时立刻全部释放资源，等一会再重新运行；要么根据优先级，高优先级抢低优先级的资源使用。但是比较复杂而且会影响前一个进程，常用于易于保存和恢复状态的进程（如 CPU）；效率低；方案一还可能导致饥饿。
- 请求保持：采用静态分配方法，进程开始运行时就把所有需要的资源都给他，全程让他运行。但是可能有的资源这个进程就用一两下，一直占着会比较浪费；可能导致饥饿。
比如上例，两个进程申请资源顺序都从小到大，先1后2，就不会死锁了。但是实际资源使用顺序可能并不是从小到大，效率低；而且增添设备要修改编号，不方便；而且用户编程要注意顺序，比较费事。
避免死锁
安全序列就是按某种顺序分配资源，所有进程都能顺利得到，不会死锁。存在一种安全序列的情况，那么当前系统就是处于安全状态。
银行家算法：
如图，剩余资源 (3, 3, 2)，视作一个一维数组。P0 全分配也不够，不行；P1可以，全分配给P1后P1归还资源，剩余资源数变成 (5, 3, 2)；然后P2不够，P3可以，变成 (7, 4, 3)；p4 变成 (7, 4, 5); P1 变成 (7, 5, 5)，最后 P2 P4，五轮循环全部分配。
最大需求：Max
已分配：Allocation
最多还需要：Need
当次发起申请的请求量：Request
Request≥Need：出错了
Request≤Available：说明有多余空闲。系统先尝试分配一下，成功后证明安全，正式分配。
检测、消除死锁
点表示进程，方框表示资源，箭头表示分配。如果所有箭头都能被顺利消除，证明不会发生死锁。
P1向R2要一个。R2给了P2一个自己还剩下一个，所以可以要到。（P1释放后，就能把P1的所有边去掉了）
P2向R1要一个。但是R1三个都给出去了，所以P2要不到，阻塞了。
P1运行完释放，R1里就有两个空闲的了，P2就能要到了。
下例就没法全部消除，死锁了。只有P3能正常运行并释放。
解决办法：可以挂起或终止死锁的部分节点，或者回退到没有发生死锁的断点。
内存
存放数据的硬件，程序要先被放到内存中才能被处理.
代码被编译成指令，通常还会涉及到几个地址。比如一个加法指令涉及的三部分（A，B，C）A代表：这是一个加法指令；B C代表：把B中的数据加到C中。
指令中采取的是相对的逻辑地址，因为还不能确定物理存到了哪里。
装入有三种：
- 绝对装入，编译时就知道要放到哪个物理地址里，编译时直接采用物理地址；适用于单道程序环境。
- 静态重定位装入，编译时采用相对地址，装入时根据相对地址存入到物理地址。但是如果内存中容量不够，就不能装入。用于早期操作系统。
- 动态重定位装入，刚进内存不会装入，等到程序运行时再装入。允许程序运行中在内存里移动。现代操作系统。
链接也有三种，装入前链接成一块，边装入边链接，运行时再链接。
内存管理
内存中存了多少？空闲多少？进程分配到哪里？怎么释放？内存扩充（游戏60G，内存4G，采用虚拟内存的方式扩充）、地址转换（就是装入。逻辑地址和物理地址之间的链接 是操作系统解决，程序员不用管）、内存保护。
覆盖与交换技术
覆盖技术：解决内存太小的问题。内存中分固定区和覆盖区。
缺点在于固定区覆盖区要程序员自己规定，不透明。
交换技术：把内存中某些进程拿出来，再把某些进程换进去。磁盘中专门有一块交换区，追求交换的速度，采用连续存储方式，IO 比文件区要快得多。缺页率高时换出得多。优先换出阻塞和优先级低的进程。
覆盖是同一个进程中的，交换是多个进程中的。
内存保护限制每个进程只能访问自己范围内的数据。可以设置上下限寄存器；或者重定向寄存器决定上限，界地址寄存器代表最大长度。
内存分配
连续分配：内存分为系统区和用户区。系统区存放操作系统相关数据；用户区存进程，只能存一个。实现简单，没有外部碎片（内存空闲区域太小，没法分配给进程的情况），可以通过覆盖技术扩大内存，不一定要保护；但是利用率低，而且有内部碎片（分配给某个进程的内存区域，有些部分没有用到）。
固定分区分配：内存分成很多个分区，每个分区只装一道作业。
（分区大小相等，缺乏灵活性，但是适用于一台计算机控制多个相同对象的场合；
也可以设置不同大小的分区，适用于各种作业）
操作系统需要叫分区说明表的数据结构，让内核程序知道哪些分区可用不可用，起始位置，大小等。没有外部碎片，但是有内部碎片；而且可能有过大的用户程序，所有分区都满足不了，就只能覆盖，降低效率。
动态分区分配：根据进程大小动态建立分区。系统区大小都是不固定的。可以采取空闲表或空闲链的数据结构存储信息。
动态分配的算法：
- 要插入的进程比空闲区小：更新空闲区起始位置和大小。
- 要插入的进程和空闲区一样大：直接在空闲分区表中删掉这一条空闲区的记录。
动态分区回收算法
- 要回收的分区前面或后面有一块空闲：更新那块空闲的起始位置和大小。
- 前后没有空闲：新增一条空闲记录。
- 前后都有空闲：空闲表中两条记录 更新成一整条。
动态分配算法 没有内部碎片，但有外部碎片。可以通过“拼凑”来解决。
具体怎么选择空闲分区分配？
动态分区分配算法
首次适应算法：从小地址到大逐渐找。空闲区按地址从小到大存储在空闲链中。
最佳适应算法：优先找能容得下的最小的空闲区，大的留着给大的进程预备着。空闲分区从小到大存储在空闲链中。小碎片会越来越多，导致外部碎片。
最坏适应算法：优先使用最大的空闲分区，避免外部碎片。但是大进程到来的时候可能插入不进来了。
临近适应算法：因为首次适应算法每次都从头找，头部可能有很多小碎片，每次又要遍历。临近适应算法每次从上次结束的地方开始查找。也是优先使用最大分区，类似最坏适应算法。
基本分页存储算法
是一种非连续分配。
每个分区10MB，A进程23MB，可以拆成10+10+3MB存储。
但是这样导致第三个分区内部碎片达到7MB。如果分区大小为2MB，那么只有最后一个分区有1MB内部碎片。
每个分区是一个页框，有页框号，从0开始。把进程分配成页框的大小，叫做一个个页，有页号。
分的页并不是连续存储在分区中的，可以不连续存储，根据逻辑地址找页与页之间的关系。
页号：逻辑地址/页面长度。
偏移量：逻辑地址%页面长度。
如第80个内存单元，页面长度50，那么页号=1，偏移量=30.
如果页面大小是2的整数次幂，那么页面范围就是00000……0001000……0000到00000……00010111……11111，末尾的部分就是页面偏移量。
页表存储页面信息，页表项包含页号和块号信息，每个页表项应该能表示出所有块数的信息。比如有2^20个块，则每个页表项要有20种状态，20位即至少三个字节。(但是通常采用4个字节 这样让总内存数可以等于证书个页表项)
基本地址变换机构
用于实现分页管理逻辑地址转变为物理地址的操作。
基本地址变换结构 每次要访问两次内存。
查页表，知道要访问的数据的位置：一次；
去访问数据：二次。
具有快表的地址变换机构
让最近访问过的页表项存到快表中。
如果快表中有该页表项，直接取出该项计算出物理地址，就不用到慢表中查表了。
访问快表命中了，就只需要一次访存。
两级页表
- 单极页表必须连续存储；
- 并不是整张页表都会被频繁访问到。
可以把长长的页表再分成离散的几块，即第二级页表。又叫顶级页表。这样就解决了问题1.
然后对于没有进内存的目标页，访问的时候产生缺页中断，然后调入页。
但是没有快表的话，两级页表要访存3次。
基本分段存储管理方式
按逻辑把程序分为一个个段（如 主函数，sum 函数……）分段离散的存储到内存中。可读性更高。
段号规定了可以有多少个段，段内地址规定了段的大小。
当然啦，为了查找到哪个段放在哪里，也需要段表。段表每一条包含段号、基址（起始位置）、段长。
段表寄存器存储在系统区的 PCB 中，即段表的位置。
相比分页，分段是有意义的，是二维的，用户既要给出段名（如 main 函数的段），又要给出地址。
分段也更容易实现信息共享和保护。首先什么代码可以共享？不能修改的代码可以共享，如常量，防止多个进程并发访问会出问题。
然后分段是按逻辑分的。比如每个函数分一个段。分页是按大小直接截断的。所以分段可能提取出可以共享的代码片段，分页会更难一些。
分段也是两次访存，也可以尝试快表。
段页式管理方式
分段和分页的缺点是什么？
分页划分固定分区，但不便于信息共享和保护。
分段根据程序分配大小不确定的分区，可能有外部碎片（紧凑还是付出代价很大的）。而且进程太大的话也难以找到一大块连续区域。
那，把大的段分页就好了。
分页的页表包含：页号 页内偏移量信息。分段的段表包含：段号 段长 基址信息（段号可以隐含）。
段页式系统的逻辑地址结构 段包含：段号 页表长 页存放块号（起始地址）。页包含：页号 页面存放的内存块号。
虚拟内存
归根结底，以上的内存分配方法需要把整个程序都装入内存运行。而且由于内存的驻留性，程序运行完之前整个都一直留在内存中。
第一，没必要，程序的某些部分不常使用，不用一直占在内存里，内存利用率低。第二，太大的程序装不进来。第三，很多程序排队时，这样一次只能运行很少的几个，并发性差。
根据之前快存学到的局部性原理，可以把常用的部分留到内存中，不常用的拿出去。要用到的不在内存里，就拿进来；内存太满，就把不常用的再拿出去。
虚拟内存有多次性（分多次装入）、对换性（可以换出来）、虚拟性。
存储方式：采用连续型并不合适，因为要分多次装入。改用请求式管理。
请求分页管理
和基本分页管理的区别在于：1. 要访问的信息可能在内存中，也可能不在。不在的话要调入进来。要存储该页是否在内存中的信息。
- 暂时不用的可以换出去。如果在内存中做过修改，那么不用拿回到外存；如果做过修改了就要了。
先根据状态位判断要访问的页在不在内存中，不在里面，就先产生缺页中断，调入内存。如果有空闲块就插到空闲块里，没有就根据页面置换算法换出来一个不常用的。调出内存的页面如果发生改变就要写入外存，没有就直接丢掉。最后还要修改请求页表中的状态信息。
缺页中断是自行产生的内中断。
几个值得注意的点：
- 我们知道，如果内存中的内容被修改（发生了”写“操作），状态位中的修改位变为1，移出内存时要再写入外存。实际上修改位的改变不一定用在内存中修改，可能只修改快表中的修改位即可，这样少访存。
- 换入换出页面太频繁，开销会很大。
- 页面调入内存后，直接就放到快表里，之后访问就访问快表就行。
页面置换算法
追求更小的缺页率，这样换入换出更少。
最佳置换算法 OPT：选择不再使用，或者最长时间内不再被访问的页面淘汰。
插入701之后满了，再想插入2就要顶掉一个。看看后面要访问的页面，7是最不着急的，先把7顶掉。后面以此类推。
注意缺页不一定就会发生页面置换。如果还有块空闲就不用。
但最大问题就是操作系统无法提前预判后面的页面访问序列。
先进先出置换算法 FIFO：最早进来的页面最早被淘汰。就是队列的数据结构。
但是这就是再猜啊。怎么能因为用的早就觉得下一秒他不会用了呢？买彩票呢。可能会引发 Belady 异常（为进程分配的物理块变大时，缺页次数反而变多）。
最近最久未使用置换算法 LRU：
哪个最久没用过，就先替换掉哪个。
性能确实好，但是开销大，实现困难。
时钟置换算法 CLOCK：每个页面添加一个访问位，初值都是0，访问过了改为1.每次优先替换掉0的页面。如果全为1，则全置0后再次扫描。
改进的时钟置换算法：同时考虑访问位和修改位。
替换：第一轮扫描找0，0的替换。这种不仅最近没用过，而且不用写入外存。
第二轮找0，1的替换。这种最近没用过，但是之前修改过，要写入外存。
如果这两轮都没找到，说明所有的第一位都是1.全部置0，再进行扫描。
第三轮找0，0，类似第一轮。
第四轮找0，1，类似第二轮。
页面分配策略
驻留集：请求分页存储管理中分给内存的物理块的集合。虚拟存储中，驻留集大小一般小于进程总大小。太小，频繁缺页出入内存效率低；太大，并发性降低。
固定分配：一开始给定每个进程固定大小的驻留集。
动态分配：根据运行过程中的情况动态分配大小。
局部置换：缺页时只能当前进程自己的物理块置换需要的页进来。
全局置换：可以用空闲的物理块，或其他进程的物理块置换。全局置换大小肯定不固定，肯定是动态分配。
调入哪些页？
首次调入时，根据局部性原理，某个页相邻的页也会容易用到。因此一调调一小片。
运行中缺页调入时，只调缺少的页。
从何处调入页面？
抖动/颠簸现象：刚换出去的页面又换进来。主要原因是驻留集太少了，少于要频繁使用的块。
工作集：运行时进程实际访问的页面集合。驻留集不应小于工作集。
