[toc]

软件设计师笔记_第四章_操作系统_精简考点

基本

操作系统的定义

操作系统定义：能有效地组织和管理系统中的各种软硬件资源；合理地组织计算机系统工作流程，控制程序的执行，并且向用户提供一个良好的工作环境和友好的接口。

操作系统的作用

1. 通过资源管理提高计算机系统的效率
2. 改善人机界面向用户提供友好的工作环境

操作系统的特征

操作系统的4个特征是并发性、共享性、虚拟性和不确定性。

操作系统的功能

操作系统的功能可分为进程管理、存储管理、文件管理、设备管理、作业管理。

操作系统的分类

1. 批处理操作系统
2. 分时操作系统（轮流使用CPU工作片）
3. 实时操作系统（快速响应）
4. 网络操作系统
5. 分布式操作系统（物理分散的计算机互联系统）
6. 微机操作系统（Windows）
7. 嵌入式操作系统

计算机的启动流程

计算机启动的基本流程为：BIOS——>主引导记录——>操作系统

进程

进程是系统进行资源分配和调度的一个独立单位。

进程的组成

进程通常由程序块，数据块，进程控制块（PCB）组成。

• 进程控制块PCB（是进程的唯一标志）
• 程序块（描述进程要做什么）
• 数据块（存放进程执行时所需数据）

进程和程序的区别

进程是程序的一次执行过程。没有程序就没有进程。

程序是一个静态的概念，进程是一个动态的概念。进程由程序开始执行而创建，由程序执行结束而结束。

进程的基础状态模型-三态图

进程一般有3中基础状态：运行，就绪和阻塞。

• 就绪：一个进程获得了所有资源，一旦得到CPU资源就可以运行。此时的线程处于就绪状态。
• 运行：一个进程得到了CPU资源，在系统上运行时。
• 阻塞：一个进程由于某个原因处于暂时停止运行的状态。

==注意：运行可以直接转换为就绪或等待，就绪只能转换为运行，等待只能转化为就绪。==

进程的复杂状态模型-五态图

实际一个系统中的进程状态转换更为复杂。

• 新建：对应一个进程刚刚被创建时的状态。
• 终止：对应一个进程运行完毕的状态。

==注意：运行可以直接转换为就绪或等待或终止，就绪只能转换为运行，等待只能转化为就绪。==

真题示例1

在单处理机系统中，采用先来先服务调度算法。系统中有4个进程P1、P2、P3、P4 (假设进程按此顺序到达)，其中P1为运行状态，P2为就绪状态，P3和P4为等待状态，且P3等待打印机，P4等待扫描仪。若P1 时间片到了，则P1、P2、P3和P4的状态应分别为（ ）。

A 等待、就绪、等待和等待 B 运行、就绪、运行和等待 C 就绪、运行、等待和等待 D 就绪、就绪、等待和运行

解题思路：

• P1 状态：因为时间片到了，P1 不能继续占用 CPU ，它从运行状态转变为就绪状态，等待下一次被调度执行。
• P2 状态：在先来先服务调度算法下，P2 在就绪队列中等待，且 P1 时间片到了释放了 CPU ，按照先来先服务的规则，P2 将获得 CPU 进入运行状态。
• P3 和 P4 状态：P3 等待打印机，P4 等待扫描仪，它们所等待的资源未得到满足，依然处于等待状态 。

真题示例2

假设系统采用PV操作实现进程同步与互斥，若有n个进程共享一台扫描仪，那么当信号量S的值为-3时，表示系统中有（ ）个进程等待使用扫描仪。

答案是2。

系统采用PV操作实现进程的同步与互斥，当执行一次P操作表示申请一个资源，信号量S减1，如果S<0,其绝对值表示等待该资源的进程数。

真题示例3

在单处理机计算机系统中有1台打印机、1台扫描仪，系统采用先来先服务调度算法。假设系统中有进程P1、P2、P3、P4,其中P1为运行状态，P2为就绪状态，P3等待打印机，P4等待扫描仪。此时，若P1释放了扫描仪，则进程P1、P2、P3、P4的状态分别为（ ）。

本题解题关键在于理解进程状态以及先来先服务调度算法的特点，具体思路如下：

• 分析 P1 状态：P1 释放扫描仪，只是释放了占用的资源，它本身仍在运行，所以 P1 还是运行状态 。
• 分析 P2 状态：系统采用先来先服务调度算法，P2 处于就绪状态且在就绪队列中等待，在 P1 未结束运行且无更高优先级抢占情况下，P2 只能继续等待，状态依旧是就绪。
• 分析 P3 状态：P3 等待打印机，P1 释放的是扫描仪，与 P3 等待的资源无关，所以 P3 仍处于等待打印机的等待状态。
• 分析 P4 状态：P4 等待扫描仪，P1 释放了扫描仪，满足 P4 等待的资源条件，P4 从等待状态变为就绪状态，等待被调度执行

PV操作与信号量 ******

信号量表示资源数量。

如果信号量S<0,其绝对值表示等待该资源的进程数。

• P操作申请资源，相当于给信号量-1
• V操作释放资源，相当于给信号量+1

PV操作与前趋图

S信号量：表示资源数，初值即为初始状态无操作时，资源的数量；信号量小于0的时候，还可以表示排队的进程数量。

针对箭线标注信号量，箭线的起点位置是V操作；箭线的终点位置是P操作。

PV 操作原理：P 操作表示申请资源，使信号量的值减 1 ，若信号量的值小于 0 ，则进程进入等待队列；V 操作表示释放资源，使信号量的值加 1 ，若信号量的值小于等于 0 ，则唤醒等待队列中的一个进程。

进程同步与互斥：即通过信号量协调进程间的执行顺序，保证进程按正确的先后顺序执行。通过前驱图确定进程之间的先后关系，然后利用 PV 操作来实现这种同步关系。

真题示例1

解题思路：

• 先在前趋图中给每个箭头画上P操作和V操作。其中箭头起点为V操作，箭头终点为P操作。
• 然后对前趋图中的箭头，按从左到右，从上到下的顺序。依次标注上信号量。

分析进程间的依赖关系：从前驱图可知，P1 执行完后 P2 才能执行，P2 执行完后 P3 和 P4 才能执行，P3 和 P4 执行完后 P5 才能执行。

• 根据前驱图，P1进程运行完需要V(S1)操作通知P2进程，所以空①应填V(S1)。
• P2进程运行完需要利用V(S2)、V(S3)操作分别通知P3、P4进程，所以空②应填V(S2)V(S3)。
• 根据前驱图，P3进程运行完需要利用V(S4)、V(S5)操作分别通知P4、P5进程，故空③应为填写V(S4)V(S5)。
• P4需要等待P2和P5进程的通知，需要执行2个P操作，由于P4进程的程序中执行前有1个P操作P(S4)，故空④应为填写P(S3)。
• 根据前驱图，P4进程执行完需要通知P5进程，故P4进程应该执行1个V操作，即空⑤应填V(S6)。
• P5进程运行前需要等待P3和P4进程的通知，需要执行2个P操作，故空⑥应填写P(S5)和P(S6)。

真题示例3

解题思路：

• 先在前趋图中给每个箭头画上P操作和V操作。其中箭头起点为V操作，箭头终点为P操作。
• 然后对前趋图中的箭头，按从左到右，从上到下的顺序。依次标注上信号量。

解题分析：

• 根据前驱图，P1进程运行完需要利用V操作V(S1)、V (S2)分别通知P2、P3进程，所以空①应填V (S2)。
• P2进程需要等待P1进程的通知，故需要利用P(S1)操作测试P1进程是否运行完，由于P3进程执行前已经用P(S2)， 所以空②应填P (S1)。
• 根据前驱图，P3进程需要等待P1和P2进程的通知，需要执行2个P操作，即P (S2)、P (S3)。由于P3进程的程序中执行前有1个P操作P (S2)，故空③应为填写P (S3)。
• P3进程运行结束需要利用1个V操作通知P5进程，故空④应为1个V操作V (S5)。
• 根据前驱图，P4进程执行完需要通知P5进程，故P4进程应该执行1个V操作，即空⑤应填V (S6)。
• P5进程运行前需要等待P3和P4进程的通知，需要执行2个P操作，故空⑥应填写P(S5)和P(S6)。

进程

• 进程调度方式分为可剥夺和不可剥夺两种。

  • 可剥夺式是指当有更高优先级的进程到来时，强行将正在运行进程的 CPU分配给高优先级的进程；
  • 不可剥夺式是指当有更高优先级的进程到来时，必须等待正在运行进程自动释放占用的CPU，然后将CPU分配给高优先级的进程。

• 系统采用PV操作实现进程的同步与互斥，每当执行一次P操作表示申请一个资源，信号量S减1，如果S<0,其绝对值表示等待该资源的进程数。

线程

同一个进程当中的各个线程，可以共享该进程的各种资源，如内存地址空间、代码、数据、文件等，线程之间的通信与交流非常方便。

但每个线程都有自己独立的CPU运行上下文和栈，这是不能共享的（程序计数器、寄存器和栈不能共享）。

死锁

死锁四大条件：互斥、保持和等待、不剥夺、环路等待。

系统不可能发生死锁的最小资源数计算

系统不可能发生死锁的最小资源数 n >= m*(w-1)+1 。其中m为进程数，w为每个进程需要的资源数。

真题范例1

某计算机系统中互斥资源R的可用数为8，系统中有3个进程P1、P2和P3竞争R，且每个进程都需要i个R，该系统可能会发生死锁的最小i值为（ 4 ）。

根据公式 n >= m*(w-1)+1。则 8 >= 3*（i-1）+1 。当i=4时公式不成立。可能会发生死锁。

R资源可用数为8，分配到3个进程中，为了让最后的i值最小，所以每个进程尽量平均分配，可以得到3 、3、2的分配情况，此时如果假设i的取值为3，则必定不会形成死锁。当i>3时系统会形成死锁，此时取整，即最小i值为4。

真题范例2

正确答案C 图①可化简，图②不可化简

解析：

在图①中，R1的可用资源数=1，R2的可用资源数=0，进程P1是非阻塞节点，可以运行完毕: P1释放其占用的资源后，R1的可用资源数=2，R2的可用资源数=1，P2、P3都是非阻塞节点,因为P2申请2个R1资源、P1申请1个R2资源的请求均可以满足而运行完毕。可见进程资源图①是可化简的。图②中，R1和R2的可用资源数都为0，P1、P2和P3都是阻塞节点，所以图②是不可化简的。

真题范例2

假设某计算机系统中资源R的可用数为6，系统中有3个进程竞争R，且每个进程都需要i个资源R，该系统可能会发生死锁的最小i值是 （ 3 ） 。若信号量S的当前值为-2，则R的可用数和等待R的进程数分别为 （ 0、2 ） 。

解题思路：

资源R的可用数为6，系统中有3个进程竞争R，当每个进程分配2个进程数的适合，不会发送死锁。一旦大于2就会发生死锁。

信号量S的物理意义是：S≥0表示某资源的可用数，若S<0,则其绝对值表示阻塞队列中等待该资源的进程数。

本题由于信号量S的当前值为-2,则意味着系统中资源R的可用个数M=0, 等待资源R的进程数N=2。

真题范例3

某系统中有3个并发进程竞争资源R，每个进程都需要5个R，那么至少有（ 13 ）个R，才能保证系统不会发生死锁。

解题思路：

在有限的资源下，要保证系统不发生死锁，则可以按这种逻辑来分析。首先给每个进程分配所需资源数减1个资源，然后系统还有1个资源，则不可能发生死锁。即：3*4+1=13个。

段页式存储

页式存储 ****

页式存储：将程序与内存划分为同样大小的块。以页为单位将程序调入内存中。

段式存储

段式存储：按用户作业中的自然段来划分逻辑空间。然后调入内存中。段的长度可以不一样。

页式存储的淘汰原则

页面淘汰时，主要依据原则（考试中默认按照此原则进行淘汰）：先淘汰最近未被访问的（访问位为0），其次多个页面访问位为0时，则淘汰未被修改的（即修改位为0，因为修改后的页面淘汰时代价更大）。

存储管理

真题示例1

某操作系统采用分页存储管理方式，下图给出了进程A和进程B的页表结构。如果物理页的大小为1K字节，那么进程A中逻辑地址为1024 (十进制)用变量存放在（ ）号物理内存页中。假设进程A的逻辑页4与进程B的逻辑页5要共享物理页4，那么应该在进程A页表的逻辑页4和进程B页表的逻辑页5对应的物理页处分别填（ ）。

逻辑地址是从0开始编址的，本题物理页的大小为1KB，而进程A逻辑地址为1024 的变量的逻辑页号为1，对应的物理页号为3。

根据题意，进程A的逻辑页4与进程B的逻辑页5要共享的物理页4,那么应该在进程A页表的逻辑页4对应的物理页处填4,进程B页表的逻辑页5对应的物理页处也填4。

设备管理

真题1

某磁盘有100个磁道，磁头从一个磁道移至另一个磁道需要6ms。文件在磁盘上非连续存放，逻辑上相邻数据块的平均距离为10个磁道，每块的旋转延迟时间及传输时间分别为100ms和20ms，则读取一个100块的文件需要（ ）ms。

步骤一：计算寻道时间

• 每次寻道移动10个磁道，每个磁道移动时间6ms，则每次寻道时间为(10\times6 = 60ms) 。
• 100块文件，每块都需先寻道，所以寻道总时间为(100\times60 = 6000ms) 。

步骤二：计算旋转延迟时间

• 每块的旋转延迟时间为 100ms，一共有 100块文件。那么旋转延迟总时间为100×100=10000ms

步骤三：计算传输时间

每块的传输时间为20ms ，文件共100块。所以传输总时间为(100\times20 = 2000ms) 。

步骤四：计算读取文件的总时间

将寻道时间、旋转延迟时间和传输时间相加，可得总时间为 6000+10000+2000=18000ms

磁盘管理

磁盘调度

• 磁盘调度分为移臂调度和旋转调度两类，在移臂调度的算法中，（ 先来先服务和最短寻道时间优先 ）算法可能会随时改变移动臂的运行方向，

真题1

假设磁盘块与缓冲区大小相同，每个盘块读入缓冲区的时间为10μs，由缓冲区送至用户区的时间是5μs，系统对每个磁盘块数据的处理时间为2μs。若用户需要将大小为10个磁盘块的Docl文件逐块从磁盘读入缓冲区，并送至用户区进行处理，那么采用单缓冲区需要花费的时间为（ ）μs；采用双缓冲区需要花费的时间为（ ）μs。

当第一块数据送入用户工作区后，缓冲区是空闲的，可以传送第二块数据。这样第一块数据的处理C1与第二块数据的输入T2是可以并行的。

依次类推，每一块数据的处理时间为10+5=15。则采用单缓冲区需要花费的时间为 15*10+2

若采用双缓冲区，则可使系统不必等待设备输入。每一块数据的处理时间为10,采用双缓冲需要花费的时间为10*10+5+2=107。

文件管理

位示图

位示图的大小需要多个字 = 磁盘中物理块的数量 / 一个字可记录的物理块数量。

真题1

某文件管理系统在磁盘上建立了位示图(bitmap) ，记录磁盘的使用情况。若计算机系统的字长为32 位，磁盘的容量为300GB ，物理块的大小为4MB ，那么位示图的大小需要（ ）个字。

根据题意，计算机系统中的字长为32位，每位可以表示一个物通块的“使用”还是“未用”，一个字可记录32个物理块的使用情况。又因为磁盘的容量为300GB，物理块的大小为4MB，那么该磁盘有300*1024/4=76800个物理块，位示图的大小为76800/32=2400个字

真题2

某文件系统采用位示图(bitmap)记录磁盘的使用情况。若计算机系统的字长为64位，磁盘的容量为1024GB，物理块的大小为4MB，那么位示图的大小需要（ ）个字。

根据题意计算机系统中的字长为64位，每位可以表示一个物理块的“使用”还是“未用”，一个字可记录64个物理块的使用情况。又因为磁盘的容量为1024GB，物理块的大小为4MB，那么该磁盘有1024X1024/4=262144个物理块，位示图的大小为262144/64=4096个字。

真题3

某文件管理系统采用位示图.(bitmap)来记录磁盘的使用情况，若计算机系统的字长为64位，磁盘容量为512GB，物理块的大小为4MB，那么位示图的大小为（ ）个字.

512G=5121024M。所以5121024/4/ 64=2048，位示图的大小为2048个字.

例子

某文件系统采用多级索引结构，若磁盘块的大小为512B，每个块号需占3B，那么根索引采用一级索引时的文件最大长度为（ ） KB：采用二级索引时的文件最大长度为（ ） KB。

根据题意，磁盘块的大小为512B，每个块号需占3B，因此一个磁盘物理块可存放512/3=170个块号。

• 根索引采用一级索引时的文件最大长度为： 170X512/1024=87040/1024=85KB
• 根索引采用二级索引时的文件最大长度为： 170X170X512/1024=28900X512/1024=14450KB

IO管理

真题

• 在计算机系统中，若P1进程正在运行，操作系统强行撒下P1进程所占用的CPU，让具有更高优先级的进程P2运行，这种调度方式称为（ 可剥夺方式 ）。

• 在单处理机系统中，采用先来先服务调度算法。系统中有4个进程P1、P2、P3、P4 (假设进程按此顺序到达)，其中P1为运行状态，P2为就绪状态，P3和P4为等待状态，且P3等待打印机，P4等待扫描仪。若P1时间片到了，则P1、P2、P3和P4的状态应分别为（ 就绪、运行、等待和等待 ）。

• 假设系统采用PV操作实现进程同步与互斥，若有n个进程共享一台扫描仪，那么当信号量S的值为-3时，表示系统中有（ 3 ）个进程等待使用扫描仪。

• 假设某分时系统采用简单时间片轮转法，当系统中的用户数为n、时间片为q时， 系统对每个用户的响应时间T= （ n*q ）。

• 在单处理机计算机系统中有1台打印机、1台扫描仪，系统采用先来先服务调度算法。假设系统中有进程P1、P2、P3、P4,其中P1为运行状态，P2为就绪状态，P3等待打印机，P4等待扫描仪。此时，若P1释放了扫描仪，则进程P1、P2、P3、P4的状态分别为（ 运行、就绪、等待、就绪 ）。

• 假设系统中有n个进程共享3台扫描仪，并采用PV操怍实现进程同步与互斥。若系统信号量S的当前值为-1，进程P1、P2又分别执行了1次P（S）操作，那么信号量S的值应为（ -3 ）。

• 假设系统有n (n≥5) 个进程共享资源R，且资源R的可用数为5。若采用PV操作，则相应的信号量S的取值范围应为（ -(n-5)~5 ）。

• PV操作是操作系统提供的具有特定功能的原语。利用PV操作可以（ 实现资源的互斥使用 ）。

• 在支持多线程的操作系统中，假设进程P创建了线程T1、T2和T3， 那么以下叙述中错误的是（ 线程T1、T2可以共享P进程中T3的栈指针 ）。