前言

内容：

进程调度
死锁
线程
存储

中论

进程调度

进程调度方式指当有更高优先级的进程到来时如何分配CPU。分为可剥夺和不可剥夺。区别是是否会强制将正在运行其他进程的CPU分配给更高优先级进程。

在某些操作系统中，一个作业从提交到完成需要经历高、中、低三级调度。

高级调度：又称长调度、作业调度、接纳调度。决定处于输入池中的哪个后备作业可以调入主系统做好运行的准备。
中级调度：又称中程调度、对换调度。决定处于交换区中的哪个就绪进程可以调入内存。
低级调度：又称短程调度、进程调度。决定处于内存中的哪个就绪进程可以占用CPU。是系统最活跃、最重要的调度程序

进程调度算法

先来先服务FCFS
时间片轮转
优先级调度
多级反馈调度

死锁

产生原因：当一个进程在等待永远不可能发生的事件时，就会产生死锁，如果系统中多个进程处于死锁，就会造成系统死锁。

产生死锁的四个必要条件

资源互斥
不可剥夺
每个进程占有资源并且等待其他资源
进程资源图是个环路

打破死锁的方法

死锁预防。破坏死锁的四个必要条件
死锁避免。银行家算法
死锁检测。系统定时运行一个检测死锁的程序
死锁解除。系统强制剥夺资源，关闭进程等

死锁资源计算：系统内有n个进程，每个进程都要R个资源

发生死锁的最大资源数 = n*(R-1)

不发生死锁的最小资源数 = n*(R-1)+1

线程

进程特点：拥有资源的独立单位；~~独立调度和分配的基本单位~~。

线程特点：共享资源；独调度和分配的基本单位。线程基本上不拥有私人资源，只拥有一点运行中必不可少的资源（程序计数器、寄存器、栈）。

引入线程的原因：进程在创建、撤销和切换中，系统会有额外开销，因此在系统中设置的进程数目不宜过多，进程切换的频率不宜太高。引入线程后，可以减少额外开销。

存储

分区存储

分区存储就是整存，将某进程运行所需的内存整体一起分配给他，然后再执行。

分区方式

固定分区：主存分为若干个固定分区，会产生内部碎片
可变分区：作业转入时划分，整好划分为作业需要的大小，会产生外部分区
可重定位分区：移动所有已经分配好的分区，使其成为一个连续的区域。只有在外部作业请求空间得不到满足时进行。

分区存储算法

首次是适应法：按内存地址，从头查找满足的空闲块
最佳适应法：将空闲块从小到大排序查找
最差适应法：将空闲块从大到小排序查找
循环首次适应法：按内存地址顺序查找，若后续还需分配则继续查找下一个

分页存储管理

逻辑页分为页号和页内地址。

地址页则为页帧号和页内地址。

需要查表得出逻辑页的页号所对应的页帧号。逻辑页和地址页的页内地址相同，所以需要两者的页大小保持一致

优点：利用率高，碎片小，分配及管理简单。

缺点：增加了系统开销，可能产生抖动现象。

抖动现象：分配给进程的存储块数量小于进程所需要的最小值，导致进程运行频繁地产生缺页中断。具体表现为，对刚被替换出去的页面，立即又要被访问，需要将它调入，但因为无空闲内存又要替换另一页，而后者又是即将被访问的页，造成了系统需花费大量的时间忙于进行这种频繁的页面交换。

分页存储算法（页面置换算法）

最优算法：理论上的算法，无法实现
先进先出FIFO
最近最少使用LRU
淘汰原则：优先淘汰最近未访问的，而后淘汰最近未修改的页面。

快表：一块小容量的相联存储器，由快速存储器组成，按内容访问、速度快，并且可以从硬件上保证按内容并行查找，一般用来存放当前访问最频繁的少数多动页面的页号。

块表将页表存于Cache中，慢表则将页表存在内存中。

慢表访问两次内存才能取出页，块表则是访问一次Cache和一次内存。

分段存储管理

将进程空间分成一段一段，每段有段号和段长。和分页存储不同，分段不需要段内地址统一（因为用的段长长度而不是地址）

分段和分页：
- 页是物理单位，分页的目的是离散分配，提高内存利用率。分页完全只是为了系统的需要，对用户不可见。
- 段是逻辑单位，分段是为了更好满足用户需求，分段用户是可见的。
- 分段比分页容易实现信息共享和保护。因为分页跟逻辑没有关系，可能会将多个逻辑块放在一个页面。而分段会将一个逻辑块为一个段。每个逻辑块都是独立的。

段页式存储管理

对进程空间先分段，后分页

优点：空间浪费小，存储共享容易、能动态链接

缺点：复杂性和开销也随之增加。

段页式地址转换

先从逻辑地址中的段号与段寄存器里的段长进行比较，越界发生中断

然后根据段寄存器中的段表地址找到段表，这时候段表存储内容发生改变，每一个内容应该为页表项的长度，以及页表起始地址

然后根据页号与该段进行比较，如果越界就发生中断

进入内存查询页表，查询页框

最后获得物理地址

一共访问三次内存：第一次访问段表，第二次访问页表，第三次访问数据