（红色知识点有简答或综合题）

3. 操作系统的主要功能（处理机，存储器，设备，文件的功能及其主要任务）

处理机 存储器 设备 文件 接口
处理机管理功能
进程控制，进程同步，进程通信，调度
处理机管理的主要任务是对处理机的分配和运行进行管理

存储器管理功能
内存分配和回收，内存保护，地址映射，内存扩充
存储器管理的主要任务是为多道程序的运行提供良好的环境，提高存储器的利用率，方便用户使用并能从逻辑上扩充内存。

设备管理功能
缓冲管理，设备分配，设备处理
设备管理需要完成用户进程提出的 I/O 请求，为用户进程分配所需的 I/O 设备，同时要提高 CPU 和 I/O 设备的利用率。

文件管理功能
文件存储空间的管理，目录管理，文件的读/写管理，文件保护
文件管理的主要任务是对用户文件和系统文件进行管理以方便用户使用，并保证文件的安全性。

接口管理功能
用户接口，程序接口
为了方便用户对OS的使用

3. 信号量的定义，值的含义，wait、signal操作，应用（前驱图的伪码描述、生产者-消费者问题的引申问题的解决）

wait 操作的伪代码如下：

wait(S){
    while(S<=0);
    S--;
}

signal 操作的伪代码如下：

signal(S){
    S++;
}

:::tips

前驱图（一个有向无环图）：

实现前趋关系

设有两个并发执行的进程 P1 和 P2 分别有语句 S1 和 S2，希望在 S1 执行后再执行 S2。如果进程之间必须保证执行的顺序是一前一后的，可以设置一个初始值为 0 的同步信号量 S，然后在前操作之后执行 signal(s)，在后操作之前执行 wait(s)。前操作执行完之后 s 的会加一，此时后操作调用 wait 满足了条件即可开始执行。

15. (其它, 7.6分)解答题.docx

我的答案：
P1{ S1; signal(a); signal(b); }
P2{ wait(a); S2; signal(c); }
P3{ wait(b); S3; signal(d); }
P4{ wait(c); wait(d); S4; }
Main()
{
Semaphore a,b,c,d =0,0,0,0;
cobegin
P1(); P2(); P3(); P4();
coend
}
正确答案：
P1{ S1; signal(a); signal(b); }
P2{ wait(a); S2; signal(c); }
P3{ wait(b); S3; signal(d); }
P4{ wait(c); wait(d); S4; }

Main()
{
Semaphore a,b,c,d =0,0,0,0,0,0,0;
cobegin
P1(); P2(); P3(); P4();
coend
}

P1{S1; signal(s12); signal(s13); }
P2{wait(s12); S2; signal(s24); signal(s25); }
P3{wait(s13); S3; signal(s36); }
P4{wait(s24); S4; signal(s46); }
P5{wait(s25); S5; signal(s56); }
P6{ wait(s36); wait(s46); wait(s56); S6; }
Main()
{
Semaphore s12,s13,s24,s25,s36,s46,s56=0,0,0,0,0,0,0;
cobegin
P1(); P2(); P3(); P4(); P5(); P6();
coend
} :::

:::tips

生产者-消费者问题的引申问题的解决

:::

5. 临界资源和临界区，进程同步机制应遵循的准则

2. 调度算法（FCFS，SJF）

:::tips 先来先服务
先来先服务(first-come first-served，FCFS)调度算法是最简单的调度算法，可用于作业调度和进程调度。作业调度时，系统将按照作业到达的先后次序来进行调度，从后备作业队列中选择几个最先进入该队列的作业，将它们调入内存并分配资源和创建进程，放入就绪队列。进程调度时，每次调度是从就绪的进程队列中选择一个最先进入该队列的进程，为之分配处理机运行。
FCFS 算法是从公平角度考虑的非抢占式算法，不会导致饥饿，虽然在单处理机系统中已很少作为主调度算法，但经常把它与其它调度算法相结合使用。

短作业优先
在实际情况中，短作业(进程)占有很大比例，而长进程的存在可能会导致大量短进程无法即使执行。短作业优先(short job first，SJF)的调度算法以作业的长短来计算优先级，作业运行时间越短其优先级越高，SJF 算法可以用于作业调度和进程调度。
SJF 调度算法对于 FCFS 算法有明显的改进，但仍然存在一些缺点。SJF 算法必须预知作业的运行时间，但是往往很难准确估计作业的运行时间。SJF 算法会使长作业的周转时间会明显地增长，甚至可能出现饥饿现象。同时 SJF 算法完全未考虑作业的紧迫程度，不能保证紧迫性作业被及时处理。

设有4道作业，它们的提交时间及执行时间如下：试计算在单道程序环境下，采用先来先服务调度算法和最短作业优先调度算法时的平均周转时间和平均带权周转时间，并指出它们的调度顺序。（时间单位：小时，以十进制进行计算。）

:::

3. 死锁的定义、产生的原因、必要条件、处理死锁的方法

:::tips 死锁的定义
死锁的定义是如果一组进程中的每一个进程都在等待仅由该组进程中的其它进程才能引发的事件，那么该组进程是死锁的(Deadlock)。

死锁出现的场合（产生的原因）
竞争不可抢占性资源引起死锁
竞争可消耗资源引起死锁
进程推进顺序不当引起死锁

必要条件
互斥条件 进程对所分配到的资源进行排它性使用
请求和保持条件 进程已经保持了至少一个资源，但又提出了对其他已被占用的资源的请求
不可抢占条件 进程已获得的资源在未使用完之前不能被抢占，只能自己主动释放
循环等待条件 在发生死锁时必然存在一个进程一资源的循环链

处理死锁的方法
预防死锁 通过设置某些限制条件，破坏产生死锁四个必要条件中的一个或几个
避免死锁 在资源的动态分配过程中，用某种方法防止系统进入不安全状态
检测死锁 发生死锁后及时地检测出死锁的发生
解除死锁 当检测到系统中已发生死锁时，就采取相应措施将进程从死锁状态解除 :::

4. 死锁的避免（银行家算法）

:::tips

系统中有五个进程P1、P2、P3、P4、P5，有三种类型的资源：A、B、和C。在T0时刻系统状态如下表所示。若采用银行家算法实施死锁避免策略，回答下列问题： （1）T0时刻是否为安全状态？为什么？（2）若这时P3请求资源（3，0，0），是否能实施资源分配？为什么？

(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个，方能完成其任务。
Need［i,j］=Max［i,j］-Allocation［i,j］

设Requesti是进程Pi的请求向量，如果Request i[j]=K，表示进程Pi需要K个Rj类型的资源。当Pi发出资源请求后，系统按下述步骤进行检查：
(1) 如果Request i[j]≤Need[i, j]，便转向步骤(2)； 否则认为出错，因为它所需要的资源数已超过它所宣布的最大值。
(2) 如果Request i[j]≤Available[j]，便转向步骤(3)； 否则，表示尚无足够资源，Pi须等待。
(3) 系统试探着把资源分配给进程Pi，并修改下面数据结构中的数值：
Available[j] = Available[j] - Request i[j];
Allocation[i, j] = Allocation[i, j] + Request i[j];
Need[i, j] = Need[i, j] - Request i[j];
(4) 系统执行安全性算法，检查此次资源分配后系统是否处于安全状态。若安全，才正式将资源分配给进程Pi，以完成本次分配；否则，将本次的试探分配作废，恢复原来的资源分配状态，让进程Pi等待。 :::

2. 分页存储中逻辑地址的结构，页表，地址变换

:::tips

地址变换

在一分页存储管理系统中，逻辑地址长度为16位，页面大小为2048字节，现有一逻辑地址为1B6AH ，且第0、1、3页依次存放在物理块6、8、10中，问相应的物理地址为多少？
正确答案：

:::

3. 页面置换算法（FIFO,LRU）

:::tips


:::

4. 抖动的预防

:::tips 采取局部置换策略 当某进程发生缺页时，只能在分配给自己的内存空间内进行置换，不允许从其它进程去获得新的物理块
把工作集算法融入到处理机调度中 在调度程序从外存调入作业之前，必须先检查每个进程在内存的驻留页面是否足够多。如果都已足够多，此时便可以从外存调入新的作业，反之则应首先为那些缺页率居高的作业增加新的物理块
利用“L = S”准则调节缺页率 L 是缺页之间的平均时间，S 是置换一个页面所需的时间。如果是 L 远比 S 大说明很少发生缺页，反之则说明频繁发生缺页。理论和实践证明利用“L = S”准则，对于调节缺页率十分有效
选择暂停的进程 当多道程序度偏高时，基于某种原则选择暂停某些当前活动的进程，将它们调出到磁盘上，以便把腾出的内存空间分配给缺页率发生偏高的进程 :::

1. I/O控制方式

:::tips 轮询的可编程 I/O 方式
中断的可编程l/O方式
直接存储器访问（DMA）方式
I/O通道方式 :::

2. 中断处理程序

:::tips 当一个进程请求 I/O 操作时，该进程将被挂起，直到 I/O 设备完成 I/O 操作后，设备控制器便向 CPU 发送一个中断请求，CPU 响应后便转向中断处理程序执行相应的处理，处理完后解除相应进程的阻塞状态。中断处理程序的处理过程可分成以下几个步骤：

1. 测定是否有未响应的中断信号：若没有继续执行下一条指令，若有则停止原有进程的执行，准备转去执行中断处理程序；
2. 保护被中断进程的 CPU 环境：先保护被中断进程的 CPU 环境，以便以后能恢复运行；
3. 转入相应的设备处理程序：确定引起本次中断的 I/O 设备，并向提供中断信号的设备发送确认信号；
4. 中断处理：对不同的设备，有不同的中断处理程序；
5. 恢复 CPU 的现场并退出中断：当中断处理完成以后，需要恢复 CPU 的现场，退出中断。

I/O 操作完成后，驱动程序必须检查本次 I/O 操作中是否发生了错误，最终向调用者报告本次 I/O 的执行情况。 :::

5. 磁盘调度算法（FCFS,SSTF,SCAN,CSCAN）

:::tips

先来先服务

先来先服务(FCFS)是最简单的磁盘调度算法，它根据进程请求访问磁盘的先后次序进行调度。

总移动量
=（98-10）+（100-10）+（191-100）+6（191-31）+（31-20）+（150-20）+ (150-32)
= 88 + 90 + 91 + 160 + 9 + 130 + 118
= 686。
此算法的优点是公平、简单，且每个进程的请求都能依次地得到处理。但此算法由于未对寻道进行优化，致使平均寻道时间可能较长，故 FCFS 算法仅适用于请求磁盘 I/O 的进程数目较少的场合。

最短寻道时间优先

最短寻道时间优先(SSTF)算法是基于贪心算法来设计的，要求访问的磁道与当前磁头所在的磁道距离最近，以使每次的寻道时间最短，但这种算法不能保证平均寻道时间最短。

总移动量
=（100-98）+（150-100）+（191-150）+（191-32）+（32-31）+（31-20）+ (20-10)
= 2 + 50 + 41 + 159 + 1 + 9 + 10
= 272
SSTF 算法平均每次磁头移动的距离明显低于 FCFS 算法的距离，较之 FCFS 有更好的寻道性能。

扫描算法

SSTF 算法会产生饥饿的原因在于，磁头有可能在一个小区域内来回来去地移动。扫描算法(SCAN)可以防止这个问题，可以规定只有磁头移动到最外侧磁道的时候才能往内移动，移动到最内侧磁道的时候才能往外移动。由于磁头移动的方式很像电梯，因此也叫电梯算法。

总移动量
=（100-98）+（150-100）+（191-150）+（199-191）+（199-32）+（32-31）+ (31-20) + (20-10)
=2 + 50 + 41 + 8 + 167 + 1 + 9 + 10
=288
扫描算法的优点是性能较好，平均寻道时间较短，不会产生饥饿现象。缺点是只有到达最边上的磁道时才能改变磁头移动方向，事实上有时并不需要到达最边上的磁道。同时当磁头刚从里向外移动而越过了某一磁道时，恰好又有一进程请求访问此磁道，这时该进程必须等待磁头继续从里向外，然后再从外向里扫描完处于外面的所有要访问的磁道后，才处理该进程的请求，致使该进程的请求被大大地推迟。

循环扫描算法

SCAN 算法对于各个位置磁道的响应频率不平均，循环扫描(C-SCAN)算法可以解决这个问题。它规定只有磁头朝某个特定方向移动时才处理磁道访问请求，而返回时直接快速移动至起始端而不处理任何请求。

总移动量
=（100-98）+（150-100）+（191-150）+（199-191）+（10-0）+（20-10）+ (31-20) + (32-31)
= 2 + 50 + 41 + 8 + 10 + 10 + 9 + 1
= 131
C-SCAN 算法的优点是比起 SCAN，对于各个位置磁道的响应频率很平均。缺点是只有到达最边上的磁道时才能改变磁头移动方向，比起 SCAN 算法来平均寻道时间更长。 :::

1. 文件的打开

:::tips 当用户要求对一个文件实施多次读/写或其它操作时，每次都要从检索目录开始。为了避免多次重复地检索目录，当用户第一次请求对某文件进行操作时，须先利用 open 系统调用将该文件打开。打开是打开就是在用户和指定文件之间建立起一个连接，具体指系统将指名文件的属性（包括该文件在外存上的物理位置)，从外存拷贝到内存打开文件表的一个表目中，并将该表目的编号(或称为索引号）返回给用户。 :::

3. 提高文件访问速度的途径、磁盘高速缓存

:::tips (1) 改进文件的目录结构以及检索目录的方法来减少对目录的查找时间；
(2) 选取好的文件存储结构，以提高对文件的访问速度；
(3) 提高磁盘的I/O速度，能将文件中的数据快速地从磁盘传送到内存中，或者相反。其中的第1和第2点已在上一章或本章作了较详细的阐述，本节主要对如何提高磁盘的I/O速度作一简单介绍。 :::

3. 索引结构（直接索引和混合索引）的原理

:::tips




::: 3.索引结构（直接索引和混合索引）的原理

   操作系统中，最常见的文件分配方式有连续分配、链式分配和索引分配，连续分配无法改变文件的大小且易产生外部碎片，链式分配解决了以上的问题但是无法实现文件的随机访问、查找效率低。为此，便提出了一种更为高级的文件分配方式——索引分配。

一、直接索引

直接索引不使用FAT文件分配表，而是在文件控制块（FCB）中设置一个区域，成为索引块或索引表，每个文件都有一个FCB（Linux系统中使用inode索引节点），因此每个文件都有其对应的索引表。目录条目包括索引表的地址，索引表中不存储任何文件信息，而是存储一个个索引表项，每个索引表项都有一个指向分配给该文件某个磁盘块的指针，要读取文件的第i块数据，通过索引表的第i个表项中的指针来定位所需的块在磁盘中的位置。
二.混合索引
混合索引指将多种分配方式与索引分配相结合的分配方式，如既采用连续分配方式，又采用索引分配方式，即一个文件前面的数据块采用连续分配，后面的数据块采用索引分配。 :::success

:::