考试 软考

软件设计师 - 操作系统部分笔记

应该和之前的笔记编写时间相差不多，因为文件创建时间已经超过考试时间，可能某次移动文件是创造写吧

操作系统的地位

计算机系统由硬件和软件两部分组成。通常把未配置软件的计算机称为裸机。直接使用裸机不仅不方便，而且将严重降低工作效率和机器的利用率。操作系统 (Operating System) 目的是为了填补人与机器之间的鸿沟，即建立用户与计算机之间的接口，而为裸机配置的一种系统软件

操作系统在计算机系统中的地位如下图所示

计算机系统层次结构图

从图中可见，操作系统是裸机上的第一层软件，是对硬件系统功能的首次扩充。它在计算机系统中占据重要而特殊的地位，所有其他软件，如编辑程序、汇编程序、编译程序、数据库管理系统等系统软件，以及大量的应用软件都是建立在操作系统基础上的，并得到它的支持和取得它的服务

从用户角度看，当计算机配置了操作系统后，用户不再直接使用计算机系统硬件，而是利用操作系统所提供的命令和服务去操纵计算机，操作系统已成为现代计算机系统中必不可少的最重要的系统软件，因此把操作系统看作是用户与计算机之间的接口

进程管理

进程管理也称为处理机管理。在多道程序批处理系统和分时系统中有多个并发执行的程序，为了描述系统中程序执行时动态变化的过程引入了进程。进程是资源分配和独立运行的基本单位。进程管理重点需要研究诸进程之间的并发特性，以及进程之间相互合作与资源竞争产生的问题

程序顺序执行的特征

前趋图是一个有向无循环图，由结点和有向边组成，结点代表各程序段的操作，而结点间的有向边表示两个程序段操作之间存在的前趋关系。程序段 Pi 和 Pj 的前趋关系表示成 Pi→Pj，其中，Pi 是 Pj 的前趋，Pj 是 Pi 的后继，其含义是 Pi 执行结束后 Pj 才能执行

下图为 3 个结点的前趋图，输入是计算的前趋，输入结束才能进行计算；计算是输出的前趋，计算结束才能输出

3-个结点的前趋图

程序顺序执行时的主要特征包括顺序性、封闭性和可再现性

程序并发执行的特征

若在计算机系统中采用多道程序设计技术，则主存中的多道程序可处于并发执行状态。对于上述有 3 个程序段的作业类，虽然每个作业有前趋关系的各程序段不能在 CPU 和输入/输出各部件并行执行，但是同一个作业内没有前趋关系的程序段或不同作业的程序段可以分别在 CPU 和各输入/输出部件上并行执行。例如，某系统中有一个 CPU 、一台输入设备和一台输出设备，前驱图如下

程序并发执行

程序并发执行时的特征如下

  1. 失去了程序的封闭性
  2. 程序和机器的执行程序的活动不再一一对应
  3. 并发程序间的相互制约性

进程的状态及其状态间的切换

三态模型

在多道程序系统中，进程在处理器上交替运行，状态也不断地发生变化，因此进程一般有 3 种基本状态：运行、就绪和阻塞

  1. 运行。当一个程序在处理机上运行时，则称该进程处于运行状态。显然，对于单处理机系统，处于运行状态的进程只有一个
  2. 就绪。一个进程获得了除处理机外的一切所需资源，一旦得到处理机即可运行，则称此进程处于就绪状态
  3. 阻塞。阻塞也称等待或睡眠状态，一个进程正在等待某一事件发生 (例如请求 I/O 等待 I/O 完成等) 而暂时停止运行，这时即使把处理机分配给进程也无法运行，故称该进程处于阻塞状态
进程状态 CPU 资源
运行 √ √
就绪 × √
阻塞 × ×

进程的三态模型

五态模型

事实上，对于一个实际的系统，进程的状态及其转换更复杂。例如，引入新建态和终止态构成了进程的五态模型

进程的五态模型

进程间的通信

在多道程序环境的系统中存在多个可以并发执行的进程，故进程间必然存在资源共享和相互合作的问题。进程通信是指各个进程交换信息的过程

同步与互斥：同步是合作进程间的直接制约问题，互斥是申请临界资源进程间的间接制约问题

进程间的同步

在计算机系统中，多个进程可以并发执行，每个进程都以各自独立的、不可预知的速度向前推进，但是需要在某些确定点上协调相互合作进程间的工作。例如，进程 A 向缓冲区送数据的操作，否则进程 B 必须停下来等待进程 A 的操作结束

可见，所谓进程间的同步是指在系统中一些需要相互合作，协同工作的进程，这样的相互联系称为进程的同步

进程间的互斥

进程的互斥是指系统中多个进程因争用临界资源而互斥执行。在多道程序系统环境中，各进程可以共享各类资源，但有些资源一次只能供一个进程使用，称为临界资源 (Critical Resource, CR) ，如打印机、共享变量和表格等

临界区管理的原则

临界区 (Critical Section, CS) 是进程中对临界资源实施操作的那段程序。对互斥临界区管理的 4 条原则如下

  1. 有空即进。当无进程处于临界区时，允许进程进入临界区，并且只能在临界区运行有限的时间
  2. 无空等待。当有一个进程在临界区时，其他欲进入临界区的进程必须等待，以保证进程互斥地访问临界资源
  3. 有限等待。对于要求访问临界资源的进程，应保证进程能在有限的时间进入临界区，以免陷入 “饥饿” 状态
  4. 让权等待。当进程不能进入自己的临界区时，应立即释放处理机 (CPU) ，以免进程陷入忙等状态

信号量机制

荷兰学者 Dijkstra 于 1965 年提出的信号量机制是一种有效的进程同步与互斥工具。目前，信号量机制有了很大的发展，主要有整型信号量、记录型信号量和信号量集机制

整型信号量与 PV 操作

信号量是一个整型变量，根据控制对象的不同被赋予不同的值。信号量分为如下两类

  1. 公用信号量。实现进程间的互斥，初值为 1 或资源的数目
  2. 私用信号量。实现进程间的同步，初值为 0 或某个正整数

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

对于系统中的每个进程，其工作的正确与否不仅取决于它自身的正确性，而且与它在执行中能否与其他相关进程正确地实施同步互斥有关。PV 操作是实现进程同步与互斥的常用方法。P 操作和 V 操作是低级通信原语，在执行期间不可分割。其中 P 操作表示申请一个资源，V 操作表示释放一个资源

P 操作的定义

S := S - 1 ，若 S ≥ 0 ，则执行 P 操作的进程继续执行；反之，则置该进程为阻塞状态 (因为无可用资源) ，并将其插入阻塞队列

P 操作可用如下过程表示，其中 Semaphore 表示所定义的变量是信号量

Procedure P(Var S:Semaphore);
    Begain
        S := S - 1;
        If S < 0 then W(S) {执行P操作的进程插入等待队列}
    End;

V 操作定义

S := S - 1 ，若 S ＞ 0 则执行 V 操作的进程继续执行；反之，则从阻塞状态唤醒一个进程，并将其插入就绪队列，然后执行 V 操作的进程继续

V 操作可用如下进程表示

Procedure V(Var S:Semaphore);
    Begain
        S := S + 1;
        If S <= 0 then R(S) {从阻塞队列中唤醒一个进程}
    End;

利用 PV 操作实现进程的互斥

例如以下俩进程可能会导致 COUNT 的值改变不当

# 1
if 有车通过 then
    COUNT := COUNT + 1;
GOTO L1;

# 2
PRINT COUNT;
COUNT := 0;
GOTO L2;

令信号量互斥 (mutex) 的初值为 1，在进入临界区之前执行 P 操作锁定资源，离开临界区后执行 V 操作，代码如下

# 1
if 有车通过 then
    begin
        P(mutex)
        COUNT := COUNT + 1;
        V(mutex)
    end
GOTO L1;

# 2
begin
    P(mutex)
    PRINT COUNT;
    COUNT := 0;
    V(mutex)
end
GOTO L2;

建议观看： 【操作系统】进程间通信—互斥

利用 PV 操作实现进程的同步

进程的同步是由于进程间合作引起的相互制约的问题，要实现进程的同步可用一个信号量与消息联系起来，当信号量的值为 0 时表示希望的消息未产生，当信号量的值为非 0 时表示希望的消息已经存在。假定用信号量 S 表示某条信息，进程可以通过调用 P 操作测试消息是否到达，调用 V 操作通知消息已准备好。最典型的同步问题是单缓冲区的生产者和消费者的同步问题

建议观看： 【操作系统】进程间通信—同步

同类资源分配不当引起死锁

若系统中有 m 个资源被 n 个进程共享，当每个进程都要求 k 个资源，而 m ＜ nk 时，即资源数小于进程所要求的总数时，可能会引起死锁

例如，m＝5，n=3，k=3，若系统采用的分配策略是轮流地为每个进程分配，则第一轮系统先为每个进程分配一台，还剩下两台；第二轮系统再为两个进程各分配一台，此时，系统中已无可供分配的资源，使得各个进程都处于等待状态导致系统发生死锁

事实上，当 m ≥ n × (k - 1) 时不会发生死锁

死锁的处理

死锁的处理策略主要有四种：鸵鸟策略 (即不理睬策略) 、预防策略、避免策略和检测与解除死锁

死锁预防

死锁预防是采用某种策略限制并发进程对资源的请求，破坏死锁产生的 4 个必要条件之一，使系统在任何时刻都不满足死锁的必要条件。预防死锁的两种策略如下：

  1. 预先静态分配法。破坏了 “不可剥夺条件”，预先分配所需资源，保证不等待资源。该方法的问题是降低了对资源的利用率，降低进程的并发程度；有时可能无法预先知道所需资源
  2. 资源有序分配法。破坏了 “环路条件”，把资源分类按顺序排列，保证不形成环路。该方法存在的问题是限制进程对资源的请求；由于资源的排序占用系统开销

死锁避免

死锁避免是设法破坏产生死锁的 4 个必要条件之一，严格防止死锁的产生。死锁避免则不那么严格地限制产生死锁的必要条件。最著名的死锁避免算法是 Dijkstra 提出的银行家算法，死锁避免算法需要很大的系统开销

建议观看： 银行家算法

线程

传统的进程有两个基本属性：可拥有资源的独立单位；可独立调度和分配的基本单位。引入线程的原因是进程在创建、撤销和切换中，系统必须为之付出较大的时空开销，故在系统中设置的进程数目不宜过多，进程切换的频率不宜太高，这就限制了并发程度的提高

引入线程后，将传统进程的两个基本属性分开，线程作为调度和分配的基本单位，进程作为独立分配资源的单位。用户可以通过创建线程来完成任务，以减少程序并发执行时付出的时空开销

这样，对于拥有资源的基本单位，不用频繁地切换，进一步提高了系统中各程序的并发程度。需要说明的是，线程是进程中的一个实体，是被系统独立分配和调度的基本单位。线程基本上不拥有资源，只拥有一点运行中必不可少的资源 (如程序计数器、一组寄存器和栈)，它可与同属一个进程的其他线程共享进程所拥有的全部资源

软件设计师
This post is licensed under CC BY-NC-SA 4.0 by the author.