操作系统考试

1，临界资源，临界区

​ 临界资源：吧这种一段时间内只允许一个进程访问的资源叫做临界资源。如打印机，磁带机。进程之间应采用互斥方式实现对这个种资源的共享

​ 临界区：不论是硬件临界资源还是软件临界资源，多个进程必须互斥的对他进行访问。吧在每个进程中访问临界资源的那段代码称为临界区

2，磁盘调度算法

​ 磁盘调度的主要目标是使磁盘的平均寻道时间最少

1. 先来先服务算法FCFS

根据进程请求访问磁盘的先后次序进行调度。算法的优点是公平，简单但是平均寻道时间较长

1. 最短寻道时间优先算法SSTF

要求访问的磁道和当前磁头所在的磁道距离最近，使每次的寻道时间最短，但是不能保证平均寻道时间最短。也可能导致进程发生饥饿

1. 扫描算法SCAN

不仅考虑到欲访问磁道与当前磁道的距离，更优先考虑的是磁头的移动方向，避免了饥饿现象，也叫做电梯调度算法。

3，进程调度算法

1. 轮转调度

是一种非常公平的算法。让就绪队列上的每个进程每次仅运行一个时间片。如果队列上有n个进程，则每个进程每次大约都可以获得1/ n的处理机时间

1. 优先级调度

吧处理机分配给就绪队列中优先级最高的进程。分为两种算法：

1. 多队列调度

前面各种进程调度算法都是在系统中仅设置了一个进程就绪队列，无法满足不同用户对进程调度策略的不同要求。

多队列调度算法将进程就绪队列从一个拆分成若干个。将不同类型或性质的进程分配在不同的就绪队列，不同的就绪队列采用不同的调度算法，一个就绪队列中的进程可以设置不同的优先级，不同的就绪队列也可以设置不同的优先级

4，进程同步， 同步机制规则

​ 进程同步机制能使多个进程有条不紊的运行。该机制主要作用就是为多个进程（含线程）的运行进行协调。常用的协调方式：

1. 进程互斥方式，指进程在对临界资源访问时，应采用互斥方式
2. 进程同步方式，指在相互合作去完成同步任务的进程间，由同步机构对他们的执行次序加以协调

实现进程互斥的机制是为每个临界资源加一把锁W，当锁打开时，可以对该资源访问。实现进程同步最常用的机制是信号量机制

​ 信号量机制：是一种进程同步工具

1. 整型信号量。

定义了一个用于表示资源数目的整型量S，S只能通过两个原子操作wait（S）和signal（S）来访问，也叫P、V操作。原子操作在执行中是不可中断的，也就是输当一个进程在修改某信号量时，其他进程不可以对该信号量进行修改

1. 记录性信号量。

除了有一个用于代表资源数目的整型变量S外，还增加了一个进程链表指针list，用于链接所有的等待进程

1. AND型信号量

前两种信号量针对的是多个并发进程仅共享一个临界资源的情况，有一些场景是进程需要获得两个或者多个资源后才能执行任务

AND型信号量基本思想是将进程在整个运行过程中需要的所有资源一次性全部分配给进程，待进程使用完毕后一起释放。只要有一个资源未能分配给进程，其他所有可能为之分配的资源也不分配给他。

5，进程的三种状态

1. 就绪状态。进程已经准备好运行，进程已经分配到除CPU以外的所有资源，只要再获得CPU许可，便可立即执行。如果系统中有许多就绪状态的进程，通常将它们按一定的策略排成一个队列，称为就绪队列
2. 执行状态。进程已获得CPU，程序正在执行。
3. 阻塞状态。正在执行的进程由于发生某些事件（IO请求，申请缓冲区失败）暂时无法继续执行的状态。一般也将处于阻塞状态的进程排成一个队列，叫做阻塞队列

6，进程和线程的区别

​ 进程是资源分配的基本单位

​ 线程是调度的基本单位

​ 在OS中引入进程的目的是为了使多个程序能并发执行，提高系统资源利用率，而引入线程则是为了减少程序在并发执行时所付出的时空开销（进程在创建、撤销、切换时花费的时空开销），使OS具有更好的并发性

7，死锁

死锁概念

​ 死锁：一组进程中的每一个进程都在等待仅由改组进程中的其他进程才能引发的事件，那么该组进程是死锁的

​ 产生死锁的四个必要条件，打破一个死锁就不会发生：

1. 互斥。必须存在需要互斥使用的资源。
2. 占有等待。在出现死锁的系统中一定有已分配到了某些资源且在等待另外资源的进程。
3. 不可剥夺。在出现死锁的系统中一定有不可剥夺使用的资源。不可剥夺是指在进程未主动释放资源之前不可夺走其占有的资源
4. 循环等待。一定存在一个处于等待状态的进程集合

预防死锁

​ 通过破坏死锁存在的必要条件来防止死锁发生。

1. 破坏互斥条件

如果允许资源都能共享使用，则系统不会进入死锁。不过一些资源共享使用无法保证正确性。比如，对临界资源的访问就必须互斥进行

1. 破坏占有等待条件，有两种方法

   1. 使进程申请到了它所需要的所有资源才能开始运行
   2. 在进程提出申请资源前，必须释放已占有的所有资源

2. 破坏非剥夺条件，有两种方法

   1. 当进程Pi申请Ri类资源时，资源管理者检查Ri中有无可分配的资源。有，则分配给Pi，否则，将Pi战友的全部资源回收而让申请进程进入等待状态
   2. 当进程Pi申请Ri类资源时，资源管理者检查Ri中有无可分配的资源。有，则分配给Pi，否则，检查占有Ri类资源的进程Pj。若Pj处于等待资源状态，则剥夺Pj拥有的Ri类资源分配给Pi，若Pj不处于等待资源状态，则置Pi于等待资源状态
3. 破坏循环等待条件

避免死锁

​ 在进行资源分配时，判断如果满足这次分配资源后是否仍存在一条确保系统不会进入死锁状态的路径，如果没有这样的路径，即使现有资源满足申请，也拒绝分配。

​ 避免死锁主要采用银行家算法：银行家算法是从当前状态出发，按照系统各类资源剩余量逐个检查各进程需要申请的资源量，找到一个各类资源申请量均小于等于系统剩余资源量的进程P1。然后分配给该P1进程所请求的资源，假定P1完成工作后归还其占有的所有资源，更新系统剩余资源状态并且移除进程列表中的P1，进而检查下一个能完成工作的客户，......。如果所有客户都能完成工作，则找到一个安全序列，银行家才是安全的。若找不到这样的安全序列，则当前状态不安全。

​ 银行家算法中相关数据结构：描述系统中课利用的资源、所有进程对资源的最大需求、系统中的资源分配、以及所有进程还需要多少资源的情况。

1. 可利用资源向量Available。这是一个含有m个元素的数组，其中的而每一个元素代表一类可利用资源数目，其初始值是系统中所配置的该类全部可用资源的数目，其数值随该类资源的分配和回收而动态的改变。如果Available[j]=K,则表示系统中现有Rj类资源K个。
2. 最大需求矩阵Max。这是一个n*m的矩阵，它定义了系统中n个进程中的每一个进程对m类资源的最大需求。如果Max[i,j]=K；则表示进程i需要Rj类资源的最大数目为K。
3. 分配矩阵Allocation。这也是一个n*m的矩阵，它定义了系统中每一类资源当前已分配给每一进程的资源数。如果Allocation[i,j]=K，则表示进程i当前已分得Rj类资源的数目为K。
4. 需求矩阵Need。这也是一个n*m的矩阵，用以表示每一个进程尚需的各类资源数。如果Need[i,j]=K,则表示进程i还需要Rj类资源K个，方能完成任务。

检测死锁

​ 可以利用资源分配图来检测是否发生死锁

解除死锁

1. 抢占资源

从一个或多个进程中抢占足够数量的资源，分配给死锁进程，以解除死锁状态

1. 终止进程

终止系统中一个或多个死锁进程，直至打破循环环路，使系统从死锁状态解脱出来

8，缺页率

在运行时，如果要访问的页（段）已经装入内存便可执行下去，如果要访问的页（段）尚未调入内存（称为缺页或缺段），便发出缺页（段）中断请求，此时OS利用请求调页（段）功能将他们调入内存，继续执行。

在进程的运行过程中，访问页面成功的次数为S，失败次数为F，总访问次数A=S+F，缺页率f=F/A

缺页率受下面几个因素影响：

1. 页面大小，页面划分越大，缺页率越低
2. 进程所分配的物理块数目，物理块数目越多，缺页率越低
3. 页面置换算法，算法的优劣决定了进程执行过程中缺页的次数

9，置换算法

常见置换算法

1. 最佳置换算法

其所选的淘汰页是在最长时间内不再被访问的页面。

优点：可保证缺页率是最低的

缺点：该算法无法实现，但可以用来去评价其他算法

假定系统为某进程分配了三个物理块，并有以下的页面号：

则置换图如下，共发生了6次页面置换

1. 先进先出置换算法

该算法总是选择在内存中驻留时间最久的页面淘汰

1. 最近最久未使用算法（LRU， Least Recently Used）

LRU算法选择最近最久未使用的页面淘汰，该算法赋予每个页面一个访问字段，用来记录一个页面自上次访问以来所经历的时间t，当淘汰页面时，会选择现有页面中t最大的进行淘汰

1. 最少使用算法（LFU， Frequently）

LRU算法为内存中每个页面设置一个移位寄存器，用来记录该页面访问的频率。该置换算法选择在最近使其使用最少的页面作为淘汰页。该算法使用了移位寄存器，每次访问某页时，便将该移位寄存器的最高位置1，LFU算法的访问图与LRU算法的访问图完全相同。

10，分区式内存管理

1. 固定分区分配

为了在内存中装入多道程序，且使这些程序之间不会发生相互干扰，于是将整个用户空间划分为若干个固定大小的区域，在每个分区中只装入一道作业。

1. 动态分区分配

根据进程的实际需要 ，动态的为之分配内存空间

1. 基于顺序搜索的动态分区分配算法

为了实现动态分区分配，通常将系统中的内存空间连接成一个链。顺序搜索是指依次搜索空闲分区链上的空闲分区，去找一个其大小能够满足要求的分区。共有四种算法：

1. 首次适应算法

   在分配内存时，从链首开始顺序查找，直至找到一个大小能满足要求的空闲分区为止。然后按照作业的大小从该分区划出一块内存分配给请求者。

   优点：优先利用内存中地址部分的空闲分区，保留了高址部分的大空闲区。为以后到达的大作也分配大得内存空间创造了条件

   缺点：低址部分不断被划分，会留下许多难以利用的，很小的空闲分区（碎片），而每次查找都是从低址开始的，又增加了查找可用空心分区的开销

2. 循环首次适应算法

   为了避免首次适应算法的缺点，循环首次适应算法不在每次都从链首开始查找，而是从上次找到的空闲分区的笑一个空闲分区开始查找，直至找到满足要求的空闲分区。

   优点：使内存中空闲分区分布的更均匀，减少了查找空闲分区的开销

   缺点：会缺乏大得空闲分区

3. 最佳适应算法

   每次为作业分配内存时，总能把满足要求，又是最小的空闲分配给作业，避免大材小用。

   孤立地看，该算法似乎是最佳的，然而宏观上却不一定。因为每次分配后所切割下来的剩余部分总是最小的，会留下很多难以利用的碎片

4. 最坏适应算法

   与最佳适应算法策略相反，他在扫描链表时，总是挑选一个最大的空间，从中分一部分给作业使用，以至于存储器中缺乏大的空间。

   实际上，该算法未必最坏，优点是可以使剩下的空闲区不至于太小，产生碎片的可能性最小，对中小作业有利。

11，分段存储地址转换

​ 物理地址=段号+段内地址

​ 逻辑地址=段号+段内地址