《操作系统概念》+《王道》笔记（一）

概论

操作系统的功能

计算机系统可以粗分为四个组件：硬件、操作系统、应用程序和用户

硬件如中央处理单元、内存、输入/输出设备

操作系统是管理计算机硬件的程序。它还为应用程序提供基础，并且充当计算机用户和计算机硬件的中介

用户视角

从用户视角来看，操作系统设计的主要目的是用户使用方便，次要的是性能，不在乎的是资源利用

系统视角

从计算机视角来看，操作系统是与硬件紧密相连的程序，或者资源分配器

当然，它也是一个控制程序，用于管理用户程序的执行，防止计算机资源的错误或不当使用，特别注重I/O设备的运行和控制

操作系统定义

操作系统是一直运行在计算机上的程序（通常称为内核），除了内核外还有系统程序和应用程序

计算机系统的组成

计算机系统的运行

当计算机电源打开或重启时，它需要引导程序来初始化系统的各个组件，从CPU寄存器、设备控制器到内存内容

引导程序一般位于计算机的固件，如只读内存或电可擦可编程只读内容。它将定位到操作系统内核并将其加到内存

除了内核，系统程序也会在启动时称为系统进程

事件发生通过硬件或软件的中断来通知。硬件可以随时通过系统总线发送信号到CPU以触发中断。软件也可通过执行特别操作即系统调用(system call)(也称为监督程序调用(monitor call)),以触发中断

当CPU被中断时，会停止正在做的事，并处理中断，处理完后重新执行被中断的计算

中断应将控制转移到合适的中断服务程序。如果中断程序需要修改处理器状态，则应明确保存当前状态，并在返回之前恢复该状态

中断向量包含各种设备的中断处理程序的地址

存储结构

内存，也称为随机访问内存，通常为动态随机访问内存（DRAM）

I/O结构

通用计算机由一个CPU和多个设备控制器组成，它们通过共同总线连在一起

每个设备控制器管理某一特定类型的设备，可以允许多个设备与其相连

操作系统为每个设备控制器提供一个设备驱动程序，其为操作系统的其他部分提供统一的设备访问接口

磁盘I/O使用直接内存访问，设备控制器可以在本地缓冲和内存之间传输整块的数据，每块只产生一个中断

计算机系统的体系结构

多处理器系统

集群系统

集群系统由两个或多个独立系统组成，这样的系统称为松耦合的，每个节点可为单处理器系统或多核系统

集群系统共享存储，且使用局域网进行内部连接

非对称集群：一台机器处于热备份模式，而另一台运行应用程序，热备份主机只监视活动服务器

对称集群：两个或多个主机都运行应用程序，并互相监视

操作系统的结构

多道程序设计通过安排作业使得CPU总有一个执行作业，从而提高CPU利用率

分时系统要求计算机系统是可交互的，此时要求响应时间应当较短

操作系统的执行

现代操作系统是中断驱动的，事件总是由中断或陷阱引起的，陷阱或异常是一种软件生成的中断，或源于出错，或源于用户程序的特定请求

为了确保操作系统的正确运行，必须区分操作系统代码和用户代码的执行，这需要使用硬件来区分各种执行模式

这需要两种单独运行模式：用户模式和内核模式（也称为监视模式、系统模式或特权模式）

计算机硬件通过模式位来表示当前模式：内核模式（0）和用户模式（1）

当用户应用通过系统调用，请求操作系统服务时，系统必须从用户模式切换到内核模式，以满足要求

当系统引导时，硬件从内核模式开始。操作系统加载完毕后，开始在用户模式下执行用户程序。一旦有陷阱或中断，硬件会从用户模式切换到内核模式。每次操作系统控制计算机时，处于内核模式，控制交给用户程序时，系统会切换到用户模式

为了保护操作系统和用户程序，将可能引起损害的机器指令作为特权指令，硬件只有在内核模式下才允许执行特权指令

支持虚拟化技术的CPU有一种单独模式，用于表示虚拟机管理器是否在控制系统，此时模式会超过两个，需要用到多个模式位。

进程管理

程序是被动实体，进程是主动实体

内存管理

如果一个程序需要执行，那么它必须映射到绝对地址，并且加载到内存

为了改进CPU的利用率和用户的计算机响应速度，通用计算机应在内存中保留多个程序，这就需要内存管理

存储管理

操作系统的逻辑存储单元为文件

大容量存储器除了外存还有更慢、价格更低的三级存储，包括磁带、CD/DVD和光盘

这些介质分为一次写多次读和读-写

高速缓存有时也简称为缓存，是计算机系统的一条重要原理

内核数据结构

链表包括单向链表、双向链表以及循环链表

堆栈采用后进先出，而队列采用先进先出

二叉树的每个父节点最多拥有两个子节点，二叉查找树要求左子节点小于等于右子节点。在最佳情况下（树是完全平衡的），查找、插入和删除操作的时间复杂度为O(log n)。然而，在最坏的情况下（树退化成链表），这些操作的时间复杂度为O(n)。

平衡二叉查找树要求任何两个子树的高度差不超过1。由于保持树的平衡，查找、插入和删除操作通常都能保持在O(log n)的时间复杂度。

哈希函数存在哈希碰撞的潜在问题，一种解决方案是使用哈希链表，将所有具有相同哈希值的项链接起来

当需要表示大量资源的可用性时，可以使用位图，即n个二进制位的串

操作系统结构

操作系统的服务

操作系统有一组服务用于提供用户功能，有用户界面、程序执行、I/O操作、文件系统操作、通信和错误检查

而另一组系统服务，则用于确保系统本身运行高效，如资源分配、记账、保护和安全

用户与操作系统的界面

用户与操作系统的界面有两种基本方案：命令解释程序和图形用户界面（GUI）

命令解释程序的实现有两种方法：一种是命令解释程序本身包含代码执行这些命令；另一种是通过系统程序实现大多数命令，命令解释程序只需将参数传给确定的一个执行文件

GUI则是利用桌面的概念

系统调用

系统调用提供操作系统服务接口。通常，系统每秒执行成千上万的系统调用

开发人员根据应用程序接口（API）来设计程序，在后台，API函数通常为应用程序员调用实际的系统调用

系统一般提供系统调用接口，以链接到操作系统的系统调用，每个系统调用都有一个相关数字

向操作系统传递参数有三种常用方法：寄存器、块表和堆栈

系统调用的类型

系统调用可分为六大类：进程控制、文件管理、设备管理、信息维护、通信和保护

系统程序

系统程序也称为系统工具，可以理解为系统调用的更抽象层次，可用分为文件管理、状态信息、文件修改、程序语言支持、 程序加载与执行、通信和后台服务

操作系统的设计与实现

系统设计分为用户目标和系统目标，用户要求系统具有一定的优良性能，研发人员要求操作系统应易于设计、实现和维护

一个重要原则是策略与机制的分离，这样可以提高灵活性，策略可随时间或地点而改变

操作系统的结构

MS-DOS系统并没有很好地区分功能的接口和层次

而UNIX则由两个独立部分：内核和系统程序

UNIX、Linux和Windows仍然采用单片结构，虽然难以实现与设计，但系统调用接口和内核通信的开销非常小

系统可以分层法来实现模块化。一个典型的操作系统层包括数据结构和一组可为更高层所调用的程序集，同时它也可以调用更底层的操作

微内核也可以对内核模块化，其从内核中删除所有不必要的部件，将它们当作系统级与用户级的程序来实现，这样可以让内核变得更小。通常微内核会提供最小的进程与内存管理以及通信功能

微内核的优点之一是便于扩展操作系统

当然还有可加载的内核模块这项技术，内核此时有一组核心组件，用于通过模块链入额外服务。这种设计的核心思想是内核提供核心服务，而其他服务在内核运行时动态实现，这样可以避免每次更改后重新编译

王道第一章

操作系统的基本概念

操作系统特征

操作系统的特征包括：

• 并发：计算机系统中同时存在多个运行的程序。这里需要理解并发是指宏观上一段时间内有多道程序在同时执行，但在每个时刻，单处理机环境下仅能有一道程序执行，即微观上这些程序是分时交替执行的

• 共享：包括互斥共享方式和同时访问方式。这里的同时访问同样是指宏观上的

  互斥要求一种资源在一段时间内只能满足一个请求，而同时访问则要求一个请求分几个时间片段间隔地完成

  1. 资源共享是以程序并发为条件的，如果不允许并发，则不存在资源共享问题

  2. 若系统不对资源共享实施有效管理，则会影响到程序的并发执行

• 虚拟

• 异步：异步性使得操作系统运行在一种随机的环境下，可能导致进程产生于时间有关的错误。然而操作系统必须保证运行环境相同多次运行进程后都能获得相同的结果

操作系统提供的接口主要分为两类：命令接口和程序接口，命令接口又分为第联机命令接口和脱机命令接口

联机命令接口是交互式的，而脱机命令接口则适用于批处理系统，用户不能直接干预作业的运行

习题

操作系统是对(C)进行管理的软件。

A.软件B.硬件C.计算机资源D.应用程序

操作系统管理计算机的硬件和软件资源，这些资源统称为计算机资源。注意，操作系统不仅管理处理机、存储器等硬件资源，而且也管理文件，文件不属于硬件资源，但属于计算机资源。

用户可以通过(B)两种方式来使用计算机。

A.命令接口和函数B.命令接口和系统调用

C.命令接口和文件管理D.设备管理方式和系统调用

操作系统主要向用户提供命令接口和程序接口(系统调用),此外还提供图形接口；当然，图形接口其实是调用了系统调用而实现的功能。

系统调用是由操作系统提供给用户的，它(B).

A.直接通过键盘交互方式使用B.只能通过用户程序间接使用

C.是命令接口中的命令D.与系统的命令一样

系统调用是操作系统为应用程序使用内核功能所提供的接口

下列选项中，不属于多道程序设计的基本特征是(C)。

A.制约性

B.间断性

C.顺序性

D.共享性

引入多道程序设计后，程序的执行就失去了封闭性和顺序性。程序执行因为共享资源及相互协同的原因产生了竞争，相互制约。考虑到竞争的公平性，程序的执行是断续的。顺序性是单道程序设计的基本特征。

处理器为什么要区分核心态和用户态两种操作方式？在什么情况下进行两种方式的切换？

区分执行态的主要目的是保护系统程序。用户态到核心态的转换发生在中断产生时，而核心态到用户态的转换则发生在中断返回用户程序时

操作系统运行环境

处理器运行模式

大多数操作系统的内核包括4方面的内容

1. 时钟管理：时钟用于向用户提供系统时间，同时实现进程的切换，通过始终管理来衡量一个作业的运行程度

2. 中断机制：中断机制可以提高多道程序运行环境中的CPU利用率

3. 原语：操作系统的底层是一些可以被调用的公用小程序，各自完成一个规定的操作，它们被称为原语

   原语是最接近硬件的部分，其运行具有原子性，只能一气呵成，所以不允许中断。同时它们的运行时间较短，调用频繁

4. 系统控制的数据结构及处理：入作业控制块、进程控制块、设备控制块、各类链表等等

中断和异常

中断也称为外中断，通常来自CPU执行指令外部的事件

异常称为内中断，来自CPU执行指令内部的事件

内部异常分为故障、自陷和终止，故障通常是由指令执行引起的异常，自陷是一种事先安排的异常事件，用于在用户态下调用操作系统内核程序。终止是指出现了使得CPU无法继续执行的硬件故障

系统调用

系统调用指令也可以叫做广义指令

习题

用户程序在用户态下要使用特权指令引起的中断属于(D)

A.硬件故障中断B.程序中断C.外部中断D.访管中断

因操作系统不允许用户直接执行某些危险性高的指令，因此用户态运行这些指令的结果会转成操作系统的核心态去运行，这个过程就是访管中断

计算机区分核心态和用户态指令后，从核心态到用户态的转换是由操作系统程序执行后完成的，而用户态到核心态的转换则是由(A)完成的。

A.硬件

B.核心态程序

C.用户程序

D.中断处理程序

计算机通过硬件中断机制完成由用户态到核心态的转换。

在操作系统中，只能在核心态下运行的指令是(B)。

A.读时钟指令B.置时钟指令C.取数指令D.寄存器清零

大多数计算机操作系统的内核包括四个方面的内容，即时钟管理、中断机制、原语和系统控制的数据结构及处理，其中第4部分实际上是系统调用类的指令(广义指令)。A、C和D三项均可以在汇编语言中涉及，因此都可以运行在用户态。从另外的角度考虑，若在用户态下允许执行“置时钟指令”,则一个用户进程可在时间片还未到之前把时钟改回去，从而导致时间片永远不会用完，进而导致该用户进程一直占用CPU,这显然是不合理的。

【2012统考真题】下列选项中，不可能在用户态发生的事件是(C)。

A.系统调用

B.外部中断

C.进程切换

D.缺页

缺页处理和时钟中断都属于中断，在核心态执行。进程调度是操作系统内核进程，无须用户干预，也在核心态执行

操作系统引导

常见操作系统的引导过程如下：

1. 激活CPU，执行BIOS的指令
2. 硬件自检，如无故障，屏幕会显示CPU、内存、硬盘等信息
3. 加载带有操作系统的硬盘，CPU将引导扇区的内容加载到内存中
4. 加载主引导记录
5. 扫描磁盘分区表，加载硬盘活动分区
6. 加载分区引导记录
7. 加载启动管理器
8. 加载操作系统

引导程序位于硬盘中

虚拟机

第一类虚拟机管理程序是唯一一个运行在最高特权级的程序，就像一个操作系统

第二类虚拟机管理程序依赖于操作系统分配和调度的资源，很像一个普通的进程

运行在两类虚拟机管理程序上的操作系统称为客户操作系统，运行在底层硬件上的操作系统称为宿主操作系统

习题

02.下列关于分层式结构操作系统的说法中，(C)是错误的。

A.各层之间只能是单向依赖或单向调用

B.容易实现在系统中增加或替换一层而不影响其他层

C.具有非常灵活的依赖关系

D.系统效率较低

单向依赖是分层式OS的特点。分层式OS中增加或替换一个层中的模块或整层时，只要不改变相应层间的接口，就不会影响其他层，因而易于扩充和维护。层次定义好后，相当于各层之间的依赖关系也就固定了，因此往往显得不够灵活，C错误。每执行一个功能，通常都要自上而下地穿越多层，增加了额外的开销，导致系统效率降低。

相对于微内核系统，(C)不属于大内核操作系统的缺点。

A.占用内存空间大B.缺乏可扩展性而不方便移植

C.内核切换太慢D.可靠性较低

微内核和宏内核作为两种对立的结构，它们的优缺点也是对立的。微内核OS的主要缺点是性能问题，因为需要频繁地在核心态和用户态之间进行切换，因而切换开销偏大。

进程

进程概念

进程是执行的程序。除了程序代码（文本段），进程中还包括当前活动，如程序计数器的值、处理器寄存器的内容

进程堆栈中存储了临时数据，而数据段中存储了全局变量

程序只是被动实体，进程是活动实体

进程本身也可作为一个环境，用于执行其他代码

下面是进程的状态图

进程控制块（任务控制块或PCB）用于表示进程，PCB中包含了许多进程信息

进程调度

进程在进入系统时会加入作业队列，驻留在内存中的、就绪的、等待运行的进程保存在就绪队列

等待特定I/O设备的进程列表称为设备队列

通常，对于批处理系统，提交的进程多于可以立即执行的。这些进程会被保存到大容量存储设备的缓冲池，以便以后执行。长期调度程序从缓冲池中选择进程加到内存，以便执行。短期调度程序从准备执行的进程中选择进程，并分配CPU

长期调度程序控制多道程序程度（内存中的进程数量）。如果多道程序程度稳定，创建进程的平均速度必须等于进程离开系统的平均速度

大部分进程可以分为I/O密集型和CPU密集型进程，长期调度程序应该选择I/O密集型和CPU密集型的合理进程组合

有的系统会额外引入中期调度程序，将进程从内存中移除，从而降低多道程序程度，之后又被重新调入，在中断处继续执行，即交换

当中断发生时，系统需要保存当前运行在CPU上的进程的上下文。进程上下文通常以PCB表示，包括CPU寄存器的值、进程状态等。切换CPU到另一个进程需要保存当前进程状态和恢复另一个进程的状态，这个任务称为上下文切换

进程运行

创建进程称为父进程，而新的进程称为子进程，每个新进程可以再创建其他进程，从而形成进程树

操作系统中对进程的标识采用位移到进程标识符（PID）。

可以通过PS命令得到一个进程列表

子进程可以从操作系统那里直接获得资源，也可以只从父进程那里获得资源子集。限制子进程只能使用父进程的资源，可以防止创建过多进程，导致系统超载

如果一个进程终止，那么它的所有子进程也应终止，这种现象称为级联终止

当进程已终止，但父进程尚未调用wait()，此时它在进程表中的条目仍然存在，这样的进程称为僵尸进程

进程间通信

进程间通信有两种基本模型：共享内存，消息传递和管道通信

生产者进程生成信息，以供消费者进程消费，共享内存可以用于解决生产者-消费者问题

缓冲区用于被生产者填充和被消费者清空，无界缓冲区没有限制缓冲区的大小，生产者总是可以生成新项，有界缓冲区假设固定大小的缓冲区，如果缓冲区已满，生产者必须等待实现缓冲区可以采用一个循环数组和两个逻辑指针：in和out

对于分布式环境，消息传递特别有用，逻辑链路操作包括send和receive

直接通信需要通信的每个进程指定通信的接收者和发送者，包括对称和非对称的形式

而间接通信中，通过邮箱或端口来发送和接收对象

这种模式下允许一次最多一个进程执行receive操作

而消息驻留的临时队列有三种实现方法：零容忍、有限容量和无限容量

多线程编程

概述

每个线程是CPU使用的一个基本单元：它包括线程ID、程序计数器、寄存器组和堆栈

同一进程的线程共享代码段、数据段和其他操作系统资源

多线程有四大类优点

1. 响应性：部分阻塞时，仍能继续执行，增加对用户的响应程度、
2. 资源共享：线程默认共享它们所属进程的内存和资源
3. 经济：进程创建和管理比线程创建和管理要花费更多资源和事件
4. 可伸缩性：线程可在多处理核上并行运行

多核编程

并行系统可以同时执行多个任务，并发系统支持多个任务，允许所有任务都能取得进展

Amdahl定律

若S=25%，N=2，则加速比为1.6倍，若N=4，加速比为2.28倍

并行分为两种类型：数据并行注重将数据分布于多个计算核上，并在每个核上执行相同操作；任务并行将任务分配到多个计算核，每个线程都执行一个独特的操作

多线程模型

线程分为用户层的用户线程和内核层的内核线程，用户线程位于内核之上，它的管理无需内核支持，而内核线程有操作系统来支持与管理

多对一模型映射多个用户级线程到一个内核线程，如果一个线程执行阻塞系统调用，那么整个进程将会阻塞，且多对一模型中多个线程不能并行允许在多核系统上

一对一模型映射每个用户线程到一个内核线程，该模型允许一个线程阻塞系统调用时，其他线程继续允许，拥有更好的并发功能。缺点在于创建一个用户线程就要创建一个相应的内核线程，开销更大

多对多模型

多对多模型多路复用多个用户级线程到同样数量或更少数量的内核线程

当然他也有变种，即双层模型

多线程问题

线程撤销是在线程完成之前终止线程，需要撤销的线程叫目标线程

异步撤销：一个线程立即终止目标线程

延迟撤销：目标线程不断检查它是否应终止，这允许目标线程有机会有序终止自己

进程调度

基本概念

I/O密集型程序通常具有大量短CPU执行

调度程序的功能包括：

• 切换上下文
• 切换到用户模式
• 跳转到用户程序的合适位置，以便重新启动程序

调度准则

周转时间：从进程提交到进程完成的时间段称为周转时间

吞吐量：一个时间单元内进程完成的数量

等待时间：等待时间为在就绪队列中等待所花时间之和

响应时间：从提交请求到产生第一响应的时间

调度算法分类

先到先服务调度

先到先服务(FCFS)调度算法

顾名思义，先请求CPU的进程首先分配到CPU，缺点是往往平均等待时间很长

该算法是非抢占的

最短作业优先调度

最短作业优先(SJF)调度算法

当CPU变为空闲时，它会被赋给具有最短CPU执行的进程

SFJ算法的平均等待时间最短

最短作业优先调度分为抢占式和非抢占式

在抢占式算法中，如果到达就绪队列的新进程的CPU执行比当前尚未完成的进程更短，则会抢占当前的运行进程

轮转调度

轮转(PR)调度算法是专门为分时系统设计的

将一个较小的时间单元定义为时间片（时间量）

每个进程执行完一个时间片之后，如果没有执行完则进入就绪队列的队尾，如此循环下去

如果该进程执行时间不足一个时间片，则执行完后立刻切换下一个进程，不需要等待时间片用完

==在某个时间点，如果恰好有进程执行完时间片，又有新进程进来，那么应该先将新进程加到队尾，然后再将执行完时间片的进程加到队尾==

轮转调度是抢占式的

多级队列

同一级队列的进程使用相同的调度算法，进程无法在队列之间迁移

队列之间通常采用固定优先级抢占调度

多级反馈队列

相比于多级队列，多级反馈队列允许进程在队列之间迁移

如果进程使用过多的CPU时间，那么它会被移到更低的优先级队列

这种方案会将I/O密集型和交互进程放到更高优先级

每个新来的程序都会先进入第1级队列

==如果有新进程到达比当前运行进程所处队列更高优先级的队列时，新进程会被排到下一个去运行==

需要注意的是，==只要是抢占式的算法，被打断的进程都会被排到队列最后==

此时如果为立即抢占式，则新进程会抢占当前运行进程

调度算法实例

假设一个系统中有 5 个进程，它们的到达时间和服务时间如表所示。

进程	到达时间	服务时间
A	0	3
B	2	6
C	4	4
D	6	5
E	8	2

​ 忽略 I/O 以及其他开销时间，若分别按先来先服务（FCFS）、非抢占的短作业优先（SJF）、抢占的短作业优先（SJF）、时间片轮转（RR，时间片=1）、多级反馈队列调度算法（FB，第 i 级队列的时间片=$2^{i-1} $）以及立即抢占的多级反馈队列调度算法（FB，第 i 级队列的时间片=$2^{i-1} $）进行 CPU 调度，请给出各进程的完成时间、周转时间、带权周转时间、平均周转时间和平均带权周转时间并画出甘特图。

先来先服务(FCFS)

非抢占的短作业优先(SJF)

抢占的短作业优先(SJF)

时间片轮转(PR)

多级反馈队列调度算法（第i级队列的时间片=$2^{i-1} $）

立即抢占的多级反馈队列调度算法（第i级队列的时间片=$2^{i-1} $）

多处理器调度

多个CPU需要关注负载分配

非对称多处理 ：一个处理器处理所有调度决定等系统活动，其他处理器只执行用户代码

对称多处理：每个处理器自我调度（每个处理器的调度程序都检查共同就绪队列，以便选择执行一个进程）

处理器亲和性：让一个进程运行在同一个处理器上

软亲和性：试图让同一进程运行在一个处理器上，但也可以迁移

硬亲和性：允许某个进程运行在某个处理器子集上

负载平衡将负载平均分配到SMP系统的所有处理器

负载平衡包括推迁移和拉迁移，从超载处理器上将进程推或拉到空闲处理器上

处理器核的多线程包括两种方法：粗粒度和细粒度

粗粒度的多线程，线程一直在处理器上执行，直到出现长延迟时间，切换到另一个线程

细粒度的多线程在指令周期的边界上切换线程

实时CPU调度

从时间发生到事件得到服务的时间称为事件延迟

两种类型的延迟影响实时系统的性能：中断延迟和调度延迟

中断延迟时从CPU收到中断到中断处理程序开始的时间，调度程序从停止一个进程带启动另一个进程所需的时间量称为调度延迟

准入控制算法：调度程序承认进程，保证进程完成；如果不能保证任务在截止期限前得以服务，则拒绝请求

单调速率调度

单调速率调度算法采用抢占的、静态优先级的策略

优先级与任务周期成反比

当较低优先级的进程正在运行并且较高优先级的进程可以运行时，较高优先级进程将抢占低优先级

单调速率调度的限制即CPU的利用率是有限的

最早截止期限优先调度

最早截止期限有限调度根据截止期限动态分配优先级，截止期限越早，优先级越高

优先级是可以进行动态调整的

比例分享调度

比例分享调度在所有应用之间分配T股，如果一个应用程序接收N股时间，那么需要确保它有N/T的总的处理器时间

算法评估

确定性模型

确定性模型采用特定的预先确定的负荷，计算在给定负荷下每个算法的性能

排队模型

已知到达率和服务率，计算使用率、平均队列长度、平均等待时间

仿真

通过随机数生成器，根据概率分布生成进程、CPU执行等等驱动仿真的数据

同步

竞争条件：多个进程并发访问和操作同一数据并且执行结果与特定访问顺序有关

为了解决竞争条件，需要进程按一定方式同步，确保一次只有一个进程在操作共享数据

临界区问题

临界区：进程在执行临界区中的代码时，能够修改公共变量、更新一个表、写一个文件等

在进入临界区前，会有请求进入临界区许可的进入区，在临界区之后可以有退出区

其余部分的代码称为剩余区

结构如下：

实现临界区的算法需要满足下面三个要求

• 互斥：如果进程P在其临界区执行，那么其他进程都不能在临界区执行
• 进步：当没有进程在临界区执行，而有进程要进入时，应该在那些不在剩余区执行的进程中选择
• 有限等待：一个进程从请求到进入临界区，期间其余进程进入临界区的次数有限，即该进程不能一直等待

解决临界区的方案可以分为两类，抢占式内核和非抢占式内核

抢占式内核允许处于内核模式的进程被抢占，而非抢占式内核不允许

Peterson解决方案

Peterson解决方案为一种基于软件的解决方案，进程共享两个数据项，turn和flag[]

turn表示哪个进程可以进入临界区

而$flag[i]=ture$表示进程$i$想要进入临界区

硬件同步

上述基于软件实现的方案的缺陷是不能运行在各种各样与其不兼容的现代计算机上

所以我们寻求硬件上的解决方案，硬件基本上是通过加锁来保护临界区

下面是两种基本的实现互斥要求的方法，可以称为原语

原语是在操作系统中调用核心层子程序的指令。与一般广义指令的区别在于它是不可中断的，而且总是作为一个基本单位出现。它与一般过程的区别在于它是原子操作。所谓原子操作，是指一个操作中的所有动作要么全做，要么全不做。

test_and_set指令

boolean test_and_set(boolean *target) {
    boolean rv = *target;
    *target = true;
    
    return rv;
}
do {
    while (test_and_set(&lock))
        ; //do nothing
    临界区
    lock = false;
    剩余区
} while (true);

compare_and_swap指令

int compare_and_swap(int *value, int expected, int new_value) {
    int temp = *value;
    if (*value == expected)
        *value = new_value;
    
    return temp;
}
do {
    while (compare_and_swap(&lock ,0 ,1) != 0)
        ; //do nothing
    临界区
    lock = 0;
    剩余区
} while (true);

下面是另一种改进的test_and_set指令，满足了有限等待的要求，任何等待进入临界区的进程只需等待n-1次

do {
    waiting[i] = true;
    key = true;
    while (waiting[i] && key)
        key = test_and_set(&lock);
    waiting[i] = false;
    临界区
    j = (i + 1) % n;
    while ((j != i) && !waiting[j])
        j = (j + 1) % n;
    if (j == 1)
        lock = false;
    else
        waiting[j] = false;
    剩余区
} while (true);

互斥锁

由于基于硬件的方案复杂且不能为程序员直接使用

所以使用更简单的软件工具，即互斥锁

当一个进程进入临界区时得到锁，离开时释放锁

acquire() {
    while (!available)
        ;
    available = false;
}
release() {
    available = true;
}

锁的缺点是会产生忙等待：当有一个进程在临界区中，任何其他进程在进入临界区时必须连续循环地调用acquire()

优点是当进程在等待锁时，没有上下文切换

信号量

信号量S是个整型变量，除了初始化外只能通过两个标准原子操作：wait()和signal()来访问

wait和signal定义如下

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

计数信号量可以用于控制访问具有多个实例的某种资源，其初值为可用资源数量。

我们也可以使用信号量来解决各种同步问题

为了解决忙等待需要，我们可以将wait()和signal()改进如下

wait()也称为P操作，signal()称为V操作

当进程执行信号量不为正时，则阻塞自己而非忙等待，即将自己放到与信号量相关的等待队列中

当其他进程执行signal()后，可以通过wakeup()操作来将自己从等待状态改为就绪状态

此时信号量有一个整数value和进程链表list

typedef struct{
    int value;
    struct process *list;
} semaphore;
wait(semaphore *S){
    S->value--;
    if (S->value < 0) {
        add this process to S->list;
        block();//用于挂起当前进程
    }
}
signal(semaphore *S){
    S->value++;
	if (S->value<=0){
        remove a process P From S->list;
        wakeup(P);
    }
}

具体唤醒哪个P则取决于CPU的调度算法

经典同步问题

有界缓冲

生产者和消费者共享以下数据结构：

int n;
semaphore mutex = 1; //提供缓冲池访问的互斥要求
semaphore empty = n; //表示空的缓冲区数量
semaphore full =0; //表示满的缓冲区数量

此时生产者和消费者的代码如下

实例

一个实例如下

某银行提供 1 个服务窗口和 10 个供顾客等待的座位。顾客到达银行时，若有空座位，则到取号机上领取一个号，等待叫号。取号机每次仅允许一位顾客使用。当营业员空闲时，通过叫号选取一位顾客，并为其服务。顾客和营业员的活动过程描述如下:

cobegin
{
    process 顾客i
    {
        从取号机获取一个号码;
        等待叫号;
        获取服务;
    }
    process 营业员
    {
        While(TRUE)
        {
            叫号;
            为客户服务;
        }
    }
}coend

请添加必要的信号量和 P,V [或 wait(),signal()] 操作，实现上述过程中的互斥与同步。要求写出完整的过程，说明信号量的含义并赋初值。

该问题可以简化为有界缓冲问题

可以使用如下三个信号量：

mutex 初值为 1，表示取号机可用。

customer_wait 初值为 10，表示有10个座位供顾客等待。

customer_turn 初值为 0，表示当前没有顾客等待服务。

service 初值为 0，等待叫号

补充后完整过程如下：

cobegin 
{ 
    process 顾客 i 
    { 
        P(customer_wait);
        P(mutex);
        从取号机获取一个号码;
        V(mutex);
        V(customer_turn);
        P(service); //等待营业员叫号
        获取服务;
    } 
    process 营业员 
    { 
        While(TRUE) 
        { 
            P(customer_turn); 
            V(customer_wait); 
            V(service); //叫号
            为客户服务;       
        } 
    } 
}coend

读者-作者问题

读数据库的进程称为读者，更新数据库的进程称为作者

我们应当保证作者在写入数据库时具有共享数据库独占的访问权

读者共享以下数据结构：

semaphore rw_mutex = 1; //供作者作为互斥信号量
semaphore mutex = 1; //用于确保更新变量read_count时的互斥
int read_count =0; //跟踪多少进程正在读对象

作者和读者进程的结构如下

mutex保证了只有一个读者能修改read_count的值

除了使用信号量，该问题也可以通过读写锁解决

多个进程可允许并发获取读模式的读写锁，但只有一个进程可获取写模式的读写锁

哲学家就餐问题

该问题需要满足在多个进程之间分配多个资源，而且不会出现死锁和饥饿

任何令人满意的哲学家问题解决方案应该确保没有一个哲学家可能会饿死

例如制定规则：当一名哲学家左右两边的筷子都可用时，才允许他抓起筷子

管程

信号量的解决方案中，可能由于无意编程错误，导致一些时序错误：

• 如果wait和signal的执行顺序错误，会出现多个进程执行在临界区

• 如果用wait代替signal，则会出现死锁

• 如果一个进程省略了wait或signal，则可能违反互斥或发生死锁

为了处理这种错误，更高级的同步工具管程登场

使用方法

管程属于抽象数据类型，封装了数据及对其操作的一组函数

且管程中的操作是互斥的

只有管程内定义的函数才能访问管程内的局部声明的变量和形式参数

管程很像一个类，把对共享资源的操作封装起来

管程结构确保了每次只有一个进程在管程内处于活动状态

一些条件结构可以让管程处理更多复杂的同步问题

将阻塞原因定义为条件变量，每个条件变量保存了一个等待队列，用于记录因该条件变量而阻塞的所有进程。对于条件变量，只有操作wait()和signal()可以调用

死锁

当一个进程申请资源时，如果这时没有可用资源，那么这个进程进入等待状态。有时，如果所申请的资源被其他等待进程占有，那么该等待进程有可能再也无法改变状态。这种情况称为死锁。

正常操作模式下，进程只能按如下顺序使用资源：

1. 申请（如果申请不能立即被允许，那么申请进程应等待，直到它能获得该资源为止）
2. 使用
3. 释放

必要条件

如果在一个系统中以下四个条件同时成立，就能引起死锁

互斥

占有并等待：一个进程应占有至少一个资源，并等待另一个资源，而该资源为其他进程所占有

非抢占：资源只能被进程在完成任务后资源释放

循环等待：存在一种进程资源的循环等待链，链中每个进程已获得的资源同时被下一个进程所请求

死锁处理方法

死锁处理方法包括下面几种

避免死锁相对于预防死锁限制条件较为宽松，但实现起来更复杂

死锁预防

破坏互斥条件不太可行，有些资源必须保证不能同时访问

破坏非抢占条件：当一个已保持了某些不可剥夺资源的进程请求新的资源而得不到满足时，它必须释放已经保持的所有资源，待以后需要时再重新申请

破坏占有并等待条件：预先静态分配，在运行前进程依次申请完他所需要的全部资源

破坏循环等待条件：按顺序资源分配发，给系统中的资源编号，规定每个进程必须按编号递增的顺序请求资源。只要进程提出申请分配资源$R_i$，则该进程在以后的资源申请中就只能申请编号大于$R_i$的资源。

死锁避免

安全状态

如果系统能按一定顺序为每个进程分配资源（不超过它的最大需求），仍然避免死锁，那么系统的状态就是安全的

安全状态不是死锁状态，死锁状态是非安全状态，但不是所有的非安全状态都能导致死锁状态

安全序列$$：对于每个$P_i$，$P_i$仍然可以申请的资源数小于当前可用资源加上所有进程$P_j$（其中$j<i$）所占用的资源

银行家算法

死锁检测和死锁解除

资源分配图

如果分配图没有环，那么系统就没有进程死锁

如果分配图有环，那么可能存在死锁

可以通过资源剥夺、撤销进程、进程回退的方法解除死锁

王道第二章

进程与线程

习题

下面的说法中，正确的是（ C）。

A. 不论是系统支持的线程还是用户级线程，其切换都需要内核的支持

B. 线程是资源分配的单位，进程是调度和分派的单位

C. 不管系统中是否有线程，进程都有拥有资源的独立单位

D. 在引入线程的系统中，进程仍是资源调度和分派的基本单位

下列关于线程的叙述中，正确的是(A)。

A.线程包含CPU现场，可以独立执行程序

B.每个线程有自己独立的地址空间

C.进程只能包含一个线程

D.线程之间的通信必须使用系统调用函数

线程是处理机调度的基本单位，当然可以独立执行程序，A对；线程没有自己独立的地址空间，它共享其所属进程的空间，B错；进程可以创建多个线程，C错；与进程之间线程的通信可以直接通过它们共享的存储空间，D错。

在单处理器系统中，若同时存在10个进程，则处于就绪队列中的进程最多有()个。

A.1

B.8

C.9

D.10

不可能出现这样一种情况，单处理器系统的10个进程都处于就绪态。但9个处于就绪态、1个正在运行是可能存在的。还要想到，可能10个进程都处于阻塞态。

一个进程释放了一台打印机，它可能会改变(C)的状态。

A.自身进程B.输入/输出进程

C.另一个等待打印机的进程D.所有等待打印机的进程

由于打印机是独占资源，当一个进程释放打印机后，另一个等待打印机的进程就可能从阻塞态转到就绪态。

当然，也存在一个进程执行完毕后由运行态转为结束态时释放打印机的情况，但这并不是由于释放打印机引起的，相反是因为运行完成才释放了打印机。

并发进程失去封闭性，是指(D)。

A.多个相对独立的进程以各自的速度向前推进

B.并发进程的执行结果与速度无关

C.并发进程执行时，在不同时刻发生的错误

D.并发进程共享变量，其执行结果与速度有关

程序封闭性是指进程执行的结果只取决于进程本身，不受外界影响。也就是说，进程在执行过程中不管是不停顿地执行，还是走走停停，进程的执行速度都不会改变它的执行结果。失去封闭性后，不同速度下的执行结果不同。

下列几种关于进程的叙述，(A)最不符合操作系统对进程的理解。

A.进程是在多程序环境中的完整程序

B.进程可以由程序、数据和PCB描述

C.线程(Thread)是一种特殊的进程祝您上岸

D.进程是程序在一个数据集合上的运行过程，它是系统进行资源分度的一个独立单元

进程是一个独立的运行单位，也是操作系统进行资源分配和调度的基本单位，它包括PCB、程序和数据以及执行栈区，仅仅说进程是在多程序环境下的完整程序是不合适的，因为程序是静态的，它以文件形式存放于计算机硬盘内，而进程是动态的。

死锁

习题

某计算机系统中有 8 台打印机，由 K 个进程竞争使用，每个进程最多需要 3台打印机。该系统可能会发生死锁的 K 的最小值是（C ）。

A. 2

B. 3

C. 4

D. 5

由于每个进程最多需要使用3台打印机，可以先给每个进程分配2台打印机，最后在总的资源中减1个出来分配给一个进程就能避免死锁。所以用7/2=3.5,向下取整为3，所以最多使用3个进程不会发生死锁。所以发生死锁的最小值为4.