处理机调度和死锁
处理机调度的基本概念
高级、中级和低级调度
高级调度
在每次执行作业调度时，都必须做出以下两个决定：
- 接纳多少个作业
- 接纳哪些作业
低级调度
- 非抢占方式
- 抢占方式：抢占的原则有：
- 优先权原则
- 短作业(进程)优先原则
- 时间片原则
中级调度
又称中程调度，其目的是为了提供内存利用率和系统吞吐量。为此，应使那些暂时不能运行的进程不再占用宝贵的内存资源，而将它们调至外存上去等待，而此时的进程状态就称为就绪驻外存状态或挂起状态
调度队列模型
仅有进程调度的调度队列模型
具有高级和低级调度的调度队列模型
具有三级调度的调度队列模型
调度算法
- 先来先服务调度算法
- 短作业(进程)优先调度算法：从后备队列中选择一个或若干个估计运行时间最短的作业，将它们调入内存运行
- 优先权调度算法：
- 非抢占式优先权调度算法：系统一旦把处理机分配给就绪队列中优先权最高的进程后，该进程就一直执行下去，直至完成。
- 抢占式优先权调度算法：系统同样把处理机分配给优先权最高的进程，使之执行。但在其执行期间，只要又出现了另一个其优先权更高的进程，进程调度程序就立即停止当前进程的执行，重新将处理机分配给新的优先权最高的进程
基于时间片的轮转调度算法
- 时间片轮转法：系统将所有进程按先来先服务的原则，拍成一个队列，每次调度时，把CPU分配给队首进程，并令其执行一个时间片。当执行的时间片用完时，由一个计数器发出时钟中断请求，调度程序便停止该进程的执行，并将它送往就绪队列的末尾，然后再吧处理机分配给就绪队列中的新的队首进程，同时也让它执行一个时间片。这样就能保证在一定时间内，均能获得一时间片的处理机执行时间。
- 多级反馈队列调度算法：设置多个就绪队列，并为各个队列赋予不同的优先级。在优先权愈高的队列中，为每个进程所规定的执行时间片就愈小
死锁
死锁：死锁是指两个或两个以上的线程在执行过程中，由于竞争资源或者由于彼此通信而造成的一种阻塞的现象，若无外力作用，它们都将无法推进下去
产生死锁的原因
- 竞争资源
- 进程间推进顺序非法
产生死锁的必要条件
- 互斥条件：一个资源一次只能被一个进程使用
- 请求和保持条件：一个进程因请求资源而阻塞时，对已获得资源保持不放
- 不剥夺条件：进程获得的资源，在未完全使用完之前，不能强行剥夺
- 循环等待条件：若干进程之间形成一种头尾相接的环形等待资源关系
处理死锁的基本方法
- 预防死锁
- 避免死锁
- 检测死锁
- 解除死锁
预防死锁的方法
预防死锁
- 摒弃请求和保持条件
- 摒弃不剥夺条件
- 摒弃环路等待条件
系统安全状态
安全状态，是指系统能按某种进程顺序，来为每个进程分配其所需资源，直至满足每个进程对资源的最大需求，使每个进程都可顺利地完成。如果系统无法找到这样一个安全序列，则称系统处于不安全状态。
存储器管理
程序的装入和链接
程序的装入
- 绝对装入方式：程序中所使用的绝对地址，既可在编译或汇编时给出，也可由程序员直接赋予。但是，一旦程序或数据被修改后，可能要改变程序中的所有地址。因此，通常在程序中采用符号地址，然后在编译或汇编时，再将这些符号地址转换为绝对地址
- 可重定位装入方式
- 动态运行时装入方式：动态运行时的装入程序，在把装入模块装入内存后，并不立即把装入模块的相对地址转换为绝对地址，而是把这种地址转换推迟到程序真正要执行时才进行。因此，装入内存后的所有地址都仍是相对地址
程序的链接
- 静态链接方式
- 装入时动态链接
- 运行时动态链接：在执行过程中，当发现一个被调用的模块尚未装入内存时，立即由OS去找到该模块并将之装入内存，把它链接到调用者模块上。凡在执行过程中未被用到的目标模块，都不会被调入内存和被链接到装入模块上。
动态链接库与静态链接库
- 静态链接库是.lib格式的文件，一般在工程的设置界面加入工程中，程序编译时会把lib文件的代码加入你的程序中因此会增加代码大小，你的程序一运行lib代码强制被装入你程序的运行空间，不能手动移除lib代码。
- 动态链接库是程序运行时动态装入内存的模块，格式* .dll，在程序运行时可以随意加载和移除，节省内存空间。
连续分配方式
分区存储管理的定义：把用户区划分为若干大小不等的分区，供不同程序使用
单一连续分配
只能用于单用户、单任务的操作系统中。采用这种存储管理方式时，可把内存分为系统区和用户区两部分，系统区仅提供给OS使用，通常是放在内存的低址部分，用户区是指除系统区以外的全部内存空间，提供给用户使用
固定分区分配
- 划分分区的方法：
- 分区大小相等，即使所有的内存分区大小相等
- 分区大小不等
动态分区分配
分区分配中的数据结构
- 空闲分区表
- 空闲分区链
分区分配算法
- 首次适应算法FF
- 循环首次适应算法，该算法是由首次适应算法演变而成的
- 最佳适应算法
对换
对换引入
对换，是指把内存中暂时不能运行的进程或者暂时不用的程序和数据，调出到外存上，以便腾出足够的内存空间，再把已具备运行条件的进程或进程所需要的程序和数据，调入内存。
进程的换出与换入
- 进程的换出：每当以进程由于子进程而需要更多的内存空间，但又无足够的内存空间等情况发生时，系统应将某进程换出。其过程是：系统首先选择处于阻塞状态且优先级最低的进程作为换出进程，然后启动盘块，将该进程的程序和数据传送到磁盘的对换区上。
- 进程的换入：系统定时查看所有进程的状态，从中找出就绪状态已换出的进程，将其中换出时间(换出到磁盘上)最久的进程作为换入进程，将之换入，直至已无可换入的进程或无可换出的进程为止。
基本分页存储管理方式
页面与页表
页面
- 页面和物理块：分页存储管理，是将一个进程的逻辑地址空间分为若干个大小相等的页，称为页面或页，并为各页加以编号。相应地，也把内存空间分成与页面相同大小的若干存储块，称为物理块或页框，也同样为它们加以编号。在为进程分配内存时，以块为单位将进程中的若干个页分别装入到多个可以不相邻接的物理块中。由于进程的最后一页经常装不满一块而形成了不可利用的碎片，称之为“页内碎片”
- 页面大小：在分页系统中的页面其大小应适中，且页面大小应是2的幂
基本分段存储管理方式
利用段表实现地址映射
分段和分页的主要区别
- 概念：页是信息的物理单位，段则是信息的逻辑单位，它含有一组其意义相对完整的信息
- 目的：分页是为实现离散分配方式，提高内存利用率。分段的目的是为了能更好地满足用户的需要。
- 大小、长度：页的大小固定且由系统决定，由系统把逻辑地址划分为页号和页内地址两部分，是由机器硬件实现的，因而在系统中只能有一种大小的页面；而段的长度却不固定，决定于用户所编写的程序，通常由编译程序在对源程序进行编译时，根据信息的性质来划分
- 地址空间：分页的作业地址空间是一维的，即单一的线性地址空间，程序员只需利用一个记忆符，即可表示一个地址；而分段的作业空间是二维的，程序员在标识一个地址时，既需给出段名，又需给出段内地址
段页式存储管理方式
利用段表和页表实现地址映射
虚拟存储器
虚拟存储器的定义
- 虚拟存储器，是指具有请求调入功能和置换功能，能从逻辑上对内存容量加以扩充的一种存储器系统。其逻辑容量由内存容量和外存容量之和决定，其运行速度接近于内存速度，而每位的成本接近于外存。
- 基于局部性原理，在程序装入时，可以将程序的一部分装入内存，而将其余部分留在外存，就可以启动程序执行。在程序执行过程中，当所访问的信息不在内存时，由操作系统将所需要的部分调入内存,然后继续执行程序。另一方面，操作系统将内存中暂时不使用的内容换出到外存上，从而腾出空间存放将要调入内存的信息。这样，系统好像为用户提供了一个比实际内存大得多的存储器，称为虚拟存储器。
虚拟存储器的实现方法
- 请求分页存储管理。
- 请求分段存储管理。
- 请求段页式存储管理。
虚拟存储器的特征
- 多次性
- 对换性
- 虚拟性
页面置换算法
- 最佳置换算法：所选择的淘汰页面是以后永不使用的
- 先进先出算法(FIFO)
- 最近最久未使用置换算法(LRU)
设备管理
I/O设备
I/O设备的类型
- 按传输速率分类：低速设备、中速设备、高速设备
- 按信息交换的单位分类：块设备、字符设备
- 按设备的共享属性分类：独占设备、共享设备、虚拟设备
I/O多路复用
IO多路复用是指内核一旦发现进程指定的一个或者多个IO条件准备读取，它就通知该进程
中断
概念
中断就是在计算机执行程序的过程中，由于出现了某些特殊事情，使得CPU暂停对程序的执行，转而去执行处理这一事件的程序。等这些特殊事情处理完之后再回去执行之前的程序
中断分类
- 内部异常中断：计算机硬件异常或故障引起的中断
- 软中断：程序中执行了引起中断的指令而造成的中断
- 外部中断：由外部设备请求引起的中断
中断优先级
机器错误 > 时钟 > 磁盘 > 网络设备 > 终端 > 软件中断
