操作系统os-chapter1-6

期末90，考得还行吧。hmb出卷真的要命，有一道大题让你自己设计二级页表系统，我计组忘净了直接寄。

第一章

什么是操作系统

操作系统是一组控制和管理计算机硬件和软件资源、合理地对各类作业(程序）进行调度，以及方便用户的程序集合。操作系统是用户和计算机的接口，同时也是计算机硬件和其他软件的接口。

书上定义为操作系统是一直运行在计算机上的程序（通常称为内核）

操作系统最基本的两个特征：并发和共享

计算机系统组成

计算机系统的组织

计算机系统操作

计算机启动过程

https://zhuanlan.zhihu.com/p/60929600

其实电脑启动的过程是一个十分完善的硬件自检的过程，在加电自检的那几秒钟里面计算机可以完成上百道工序，下面就由我来与大家介绍一下这个过程。

第一步：在主板接通电源之后，系统就由POST(Power On Self Test,上电自检)开始自检，在我们刚刚接通电源的时候，整个系统由BIOS控制，电压还不太稳定（这个过程非常短暂，一般只有几毫秒，这个时候电压的稳定完全依靠主板和电源内部的滤波电容进行），主板芯片组会向CPU发出reset的命令让CPU开始初始化，同时主板芯片组等待电源发出POWE GOOD命令，一旦电源发出POWER GOOD命令，主板芯片组会马上停止reset命令的发出（如果是手动reset那么松开reset按钮时就会停止发出命令），这时候CPU会马上从地址FFFFF0H或FFFF0H开始执行寻址指令（这个地址是在BIOS内而不再内存里面），在这个地址中无论是AMI BIOS还是Award BIOS，在这个地址中都会存储一条跳转命令，直接跳转到系统BIOS中真正的启动代码处，这个时候BIOS就会进行到第二个步骤POST。

第二步：系统BIOS的启动代码首先要做的事情就是POST，POST的主要任务就是在检测系统中的一些关键设备是否存在和正常工作。由于POST在初始化显示卡之前，因此如果POST过程中出现任何的被BIOS认为的致命错误，比如没有找到内存或者说内存错误之类的，POST会通过主板上再带的扬声器来发送长短和数量不等的警报声以传递错误信息，如果在正常情况下，POST会进行的非常快，我们是难以感觉到这个过程的。

第三步：在这一步，系统BIOS会找到显卡，存放显卡BIOS的ROM通常地址在C0000H处，系统BIOS找到显卡BIOS之后调用它的代码，由于显卡生产商的不同，所以显卡的初始化是由显卡BIOS来完成的，所以不同显卡厂商的界面也是不太一样的。

第四步：硬盘引导启动：这一步是根据BIOS设置的启动顺序进行，按照顺序将控制权依次转移给列表中的存储设备，无论是哪个设备，计算机都会依次读取这个设备的第一个扇区，即第一个512字节，如果这512个字节的最后两个字节是0x55和0xAA，表明这个设备可以用于启动；如果不是，表明设备不能用于启动，控制权于是被转交给"启动顺序"中的下一个设备，这最前面的512个字节就被叫做主引导记录（Master boot record，缩写为MBR）。

其中主引导记录的主要作用就是引导硬盘到指定的位置来加载操作系统，一般分为三个部分：第1-446字节：调用操作系统的机器码；第447-510字节：分区表（Partition table）；第511-512字节：主引导记录签名（0x55和0xAA）。

其中分区表的作用是将硬盘分为若干个分区，硬盘分区的好处就是在于可以在不同的分区中安装不同的操作系统，但是主引导记录必须知道每个操作系统具体是在哪个分区。

主引导记录的大小总共只有64个字节，其中分为四项，每项16个字节，也就是说，每块硬盘只有4个主分区，只能安装4套操作系统。每个主分区总共16个字节，分为6个部分：

• 第一个字节：如果为0x80，就表示该主分区是激活分区，控制权要转交给这个分区。四个主分区里面只能有一个是激活的。

• 第二至四个字节：表示主分区第一个扇区的物理位置（柱面、磁头、扇区号等等）。

• 第五个字节：表示主分区类型（具体内容比较多在这里就不再过多阐述）。

• 第六只八个字节：表示主分区的最后一个扇区的物理位置。

• 第九至十二个字节：表示主分区第一个扇区的逻辑地址。

• 第十三至十六个字节：表示主分区的扇区总数。

最后一条规定了 主分区的长度，也就是说，主分区的长度最大不能大于2^32，所以，每个分区512个字节的话，整块硬盘的大小不会超过2TB，所以提高硬盘大小只有两个办法：一是提高硬盘扇区总数；二是提高每个扇区的字节数。

第五步：硬盘启动。这个时候系统会优先从四个主分区里面的那个被激活的分区来启动，叫做引导卷启动（Volume boot record，缩写为VBR），卷引导记录的主要作用是，告诉计算机，操作系统在这个分区里的位置。然后，计算机就会加载操作系统了。但是如果系统被安装在了拓展分区和逻辑分区中，就要通过启动管理器来启动，在这种情况下，计算机读取"主引导记录"前面446字节的机器码之后，不再把控制权转交给某一个分区，而是运行事先安装的"启动管理器"（boot loader），由用户选择启动哪一个操作系统。

第六步：内核加载启动。这个时候计算机的操作系统位置已经确定，就要进行内核加载。在内核加载阶段，Ntldr 将首先加载Windows内核 Ntoskrnl.exe 和 硬件抽象层 (HAL). HAL 有点类似于嵌入式操作系统下的BSP（Borad support package)，这个抽象层对硬件底层的特性进行隔离，对操作系统提供统一的调用接口，操作系统移植到不同硬件时只要改变相应的 HAL 就可以，其它的内核组件不需要修改，这个是操作系统通常的设计模式。

接下来Ntldr 从HKEY_LOCAL_ MACHINE\SYSTEM\CurrentControlSet 下读取这台机器安装的驱动程序，然后依次加载驱动程序。驱动程序加载完成后，Windows做如下设置：

1. 创建系统环境变量

2. 启动 win32.sys ，这个是Windows子系统的内核模式部分。

3. 启动 csrss.exe，这个是Windows子系统的用户模式部分。

4. 启动 winlogon.exe

5. 创建虚拟内存页面文件

6. 对一些必要的文件进行改名

中断与陷阱

操作系统是中断驱动的（interrupt driven）。因为事件的发生通常通过软件或硬件中断来表示。

硬件通过系统总线向CPU发信号来触发，软件通过执行特别操作如系统调用（system call）触发中断，这种中断通常被称为陷阱（trap）。硬件中断具有随机性与突发性，而陷阱是程序安排好的。

CPU如何处理中断：

存储结构

主存（内存：main memory）是CPU唯一能直接访问的大容量存储。CPU要访问硬盘则需通过硬盘控制器。

缓存cache：从低速存储设备临时复制到高速存储设备。

IO结构

DMA

操作系统结构

Multiprogramming(多道程序)

操作系统将多个任务存储在内存中，CPU在作业之间进行调度切换。

优点

• CPU利用率高
• 系统吞吐量大
• IO设备利用率高

缺点

• 响应慢

基本特征：

• 制约性
• 间断性
• 共享性

multitasking（多任务）

即分时复用

操作系统操作

双重模式（dual-mode)

User mode(处理用户代码或进程) 与 Kernel mode（处理系统代码或进程）

划分的原因

很多指令不能让用户直接操作，划分模式以达到限制用户操作的目的

进程管理

处于执行中的程序被称为进程。是系统内部的一个工作单元。程序是被动的实体，进程是动态的实体。每个进程建立进程控制块进行管理。

进程需要一定的资源（包括CPU时间、内存、文件、IO设备）以完成其任务。这些资源可以在进程创建时分配给进程，也可以在执行进程时分配给进程。除了在创建时得到各种物理和逻辑资源外，进程还可以接受传输过来的各种初始化数据（输入）。进程完成后释放资源。

系统由多个进程组成，所有这些进程可以潜在地并发执行。

操作系统负责下述与进程管理相关的活动：

• 创建和删除用户进程和系统进程。
• 挂起和重启进程。
• 提供进程同步机制。
• 提供进程通信机制。
• 提供死锁处理机制。

存储管理

操作系统提供了统一而逻辑的信息存储。操作系统对存储设备的物理属性进行了抽象，定义了逻辑存储单元，即文件。操作系统将文件映射到物理介质上，并通过这些存储介质访问这些文件。

文件系统管理

操作系统负责下列有关文件管理的活动：

• 创建和删除文件和目录。
• 提供操作文件和目录的原语（基元）。
• 将文件映射到二级存储
• 在稳定介质上备份文件

大容量存储

操作系统负责下列有关硬盘管理的活动：

• 空闲空间管理。

• 存储空间分配。

• 硬盘调度。

由于二级存储器使用频繁，因此必须高效。计算机操作的最终速度可能与硬盘子系统的速度和管理该子系统的算法有关。

IO子系统

缓冲区(Buffer)与缓存(Cache)的区别

缓冲区是协调两个速度不匹配的过程（或者任务）。

缓存协调两个速度不匹配的设备，在高速存储器内放置快速存储区存放低层（慢速）数据。

概念：Spooling （即外部设备联机并行操作）

即Simultaneous Peripheral Operation On-Line的缩写，它是关于慢速字符设备如何与计算机主机交换信息的一种技术，通常称为“假脱机技术”。Spooling allows programs to “hand off” work to be done by the peripheral and then proceed to other tasks, or to not begin until input has been transcribed.

例子

以前由于未使用多进程，如果对操作系统执行打印命令，整个操作系统就不能与用户进行交互了，因此人们通常采用SPOOLING技术，将需要打印的内容由进程拷贝到一个功能较弱且廉价的计算机的硬盘上（功能弱体现在功能单一，即以支持SPOOLING操作为主要目的的机器），该计算机有操作系统，与打印机直接相连。这样就可以使高性能计算机免除为服务低速外设而浪费运算资源的情况。

补充

并行与并发

顾名思义，「并发」强调的是可以一起「出『发』」，「并行」强调的是可以一起「执『行』」。

与可以一起出发的并发（concurrent）相对的是不可以一起出发的顺序（sequential）：

• 顺序：上一个开始执行的任务完成后，当前任务才能开始执行
• 并发：无论上一个开始执行的任务是否完成，当前任务都可以开始执行

（也就是说，A B 顺序执行的话，A 一定会比 B 先完成，而并发执行则不一定。）

与可以一起执行的并行（parallel）相对的是不可以一起执行的串行（serial）：

• 串行：有一个任务执行单元，从物理上就只能一个任务、一个任务地执行
• 并行：有多个任务执行单元，从物理上就可以多个任务一起执行

（也就是说，在任意时间点上，串行执行时必然只有一个任务在执行，而并行则不一定。）

综上，并发与并行并不是互斥的概念，只是前者关注的是任务的抽象调度、后者关注的是任务的实际执行。而它们又是相关的，比如并行一定会允许并发。

所以：

• 单核 CPU 多任务：并发（不必等上一个任务完成才开始下一个任务）、串行（只有一个实际执行任务的 CPU 核）
• 多线程：并发、串行（所有线程都在同一个核上执行）；并发、并行（不同线程在不同的核上执行）

---

如下图，并发是两个队列交替使用一台咖啡机，并行是两个队列同时使用两台咖啡机

第一章重点拾遗

操作系统特征

1．并发

在计算机系统中同时存在多个程序，从宏观上看这些程序是同时向前推进的；从微观上讲，任何时刻只有一个程序在执行，即单CPU条件下，这些程序在CPU上轮流执行。

双重含义：

• 用户与用户程序并发
• 用户与操作系统程序并发

2．共享：操作系统与多个用户程序共同使用计算机系统中的资源。

3．随机性：操作系统必须随时对以不可预测的次序发生的事件进行响应。

操作系统的两个设计目标

• 提供一个良好的供其它程序执行的运行环境，具体追求：

• 方便使计算机系统用

  • 操作系统提供方便使用的接口

• 使计算机系统能高效率工作

  • 操作系统扩充硬件的功能：操作系统应使硬件的功能发挥的更好
  • 操作系统使用户合理共享资源，防止各用户间相互干扰
  • 操作系统以文件形式管理软件资源，保证信息的安全和快速存取

两个目标是一对矛盾，需要折中权衡

操作系统形成与发展

操作系统从无到有，其发展是随着计算机硬件技术的发展而发展的。

• 手工操作阶段（程序员即使操作员，汇编，读卡机，设备驱动程序）
• 管理程序（20世纪50年代末至60年代初，编译程序）
• 多道程序系统：批处理系统、分时系统：
  （1）多道程序设计技术：通道技术，中断技术的出现使多道程序设计技术成为可能
  （2）SPOOLing技术（Simultaneous Peripheral Operation-On Line），预输入和缓输出功能
  （3） 分时系统：把CPU时间划成时间片，轮流为用户服务
• 通用操作系统

操作系统分类

单道批处理系统

单道批处理系统：为了实现对作业的连续处理，需要先把一批作业以脱机方式输入到磁盘上，并在系统中配上监督程序（Monitor），在它的控制下，使得这批作业能一个接着一个的连续工作。

具体的工作过程是首先由监督程序将磁带上的第一个作业装入内存，并把运行控制权交给作业；该作业处理完时，又把控制权交给监督程序，再有监督程序把磁带的第二个作业调入内存等等。可以看成是串行的。

优点：解决人机矛盾和CPU与IO设备速度不匹配问题，提高系统资源的利用率和系统吞吐量。

（吞吐率（量）：单位时间内处理作业的个数）

缺点：不能充分的利用系统资源，现很少使用（如下图，如果频繁IO会导致CPU利用率很低）。

特点：

• 自动：作业自动运行，无需干预
• 批量：磁带上的各个作业按顺序地进入内存，先调入先完成
• 单道：内存中仅有一道程序运行，可以看成是串行的

多道批处理操作系统

工作方式

作业（job）：用户要求计算机系统进行处理的一个计算问题。用户程序及其所需的数据和控制命令一起形成作业。作业 = 程序 + 数据 + 作业说明书

用户（准备好自己的作业）将作业交给系统操作员，系统操作员将许多用户的作业组成一批作业，通过输入设备输入到计算机系统中（磁盘上），然后，启动操作系统，执行每个作业，最后由操作员将作业运行结果分发给用户。

多道指某个作业占用CPU，若由于某种原因暂时不用CPU，第二个作业占用CPU。

特点

• 宏观上并行，微观上串行
• 多道，主存中同时存在多个正在运行的程序，它们并发工作，减少CPU的空闲时间，提高了CPU的利用率。
• 成批处理，作业流程自动化，减少了人工操作和作业交接的时间，提高了系统吞吐率。
  • 带来的不足之处：无交互手段，调试程序困难；作业处理时间长，周转效率低；
  • 用户不能直接干预自己作业的运行，一旦发现作业错误，不能及时修改，延长了开发软件时间，所以一般适用于成熟的程序。
• 采用作业调度策略，按一定的合理搭配选择作业进入主存，可以充分利用计算机系统的各种资源。
  • CPU密集型、I/O密集型、均衡型
• 采用SPOOL技术使作业在执行过程中，可以直接从高速磁盘上存取信息，缩短了作业执行时间，提高了运行效率。

SPOOLing系统特点

（Simultaneous Peripheral Operation On-Line，同时的外围设备联机操作–假脱机技术）

在一个计算问题开始之前，把计算所需要的程序和数据从输入设备上预先输入到磁盘上，这样，当进行计算时可以从磁盘上读取程序和数据（速度快），无须再访问输入设备（慢速）。同样，计算过程中，将结果先放到磁盘上保存，全部计算完成后再把全部计算结果输出到打印机上。

利用磁盘作缓冲，将输入、计算、输出分别组织成独立的任务流，使I/O和计算真正并行

作业进入到磁盘上的输入，系统按某种调度策略选择几个搭配得当的作业，调入主存。作业运行的结果输出到磁盘上的输出，之后再从磁盘上的输出将结果送到打印机。

追求目标：系统资源利用率和系统效率

分时操作系统

工作方式

一台主机连接了若干个终端，每个终端有一个用户在使用，交互式地向系统发出命令请求；系统接受每个用户的命令，并采用时间片轮转的方式处理用户的服务请求，并在终端上向用户显示处理结果；用户根据上一步运行结果发出下一道命令。

追求的目标是比较快速响应用户

• 分时系统为用户提供交互命令
• 分时系统中采用分时方法对多个终端用户服务
• 分时方法：将CPU时间划为时间片
• 分时系统以时间片为单位，轮流为各个用户服务

特点

• 同时性（多路性）
  • 同时有多个用户使用一台计算机。
    （宏观上看是多个用户同时使用一个CPU，微观上则是多个用户在不同时刻轮流使用CPU。）
• 独占性（独立性）
  • 各个用户彼此独立，互不干扰地使用计算机，感觉不到计算机同时还在为其他用户服务，有一种独占计算机的错觉。
• 及时性
  • 系统对用户提出的请求能在较短时间内作出响应，让用户满意。
• 交互性
  • 采用人机对话方式，用户在终端上输入、调试、运行自己的程序，能及时修改程序中的错误且直接获得结果。用户根据系统响应结果进一步提出新的请求。（用户能直接干预作业运行的每一步）

分时系统目标与多道程序目标的对比

• 分时系统目标：对用户请求快速反应
• 多道批处理目标：提高计算机系统效率

实时操作系统

主要追求目标

• 及时性（实时性）
  • 对外部请求在严格时间范围内作出反应和处理（强制性的）
• 高可靠性和安全性
  • 系统保证不出错（因此，不追求系统资源利用率）

分布式操作系统

分布式操作系统是网络操作系统的更高级的形式，它保持了网络操作系统的全部功能。

分布式系统

基于两种环境：

• 一种是多处理机（多CPU）系统：紧密耦合

  • 建立在多个CPU上──物理上相邻──总线或开关网连接处理器，共享主存进行通信

• 另一种是基于计算机网络的多计算机系统：松散耦合

  • 建立在网络上──地理上分开，通过网络用报文（Message）连接

• 分布式计算机系统结构：环形，星形，树形

特征

1）是一个统一的操作系统。
2）资源进一步共享（最大限度的共享）。
3）透明性：资源共享，分布。用户并不知道，对用户来讲是透明的。
4）自治性：处于分布式系统中的多个主机处于平等地位。
5）处理能力增强，速度更快，可靠性增强。

中断

中断系统的作用

• 中断是实现多道程序操作系统的前提，没有中断，操作系统无法改变CPU 的状态（即目态－管态之间的互换）（用户态与内核态）

• 中断是现代计算机系统中的基本设施之一，它起着通讯联络作用，协调系统对各种外部事件的响应和处理。中断是实现多道程序的必要条件。

• 操作系统是由中断驱动的。

中断系统的处理原理

​ 中断装置由一些特写的寄存器和控制线路组成，中央处理器和外围设备等识别到的事件保存在特写寄存器中，中央处理器每执行完一条指令后，均由中断装置判别是否有事件发生。若无事件发生，中央处理器继续执行指令；若有事件发生，中断装置中断原占用中央处理器的程序执行，而让操作系统的处理事件的服务程序占用中央处理器对出现的事件进行处理，待操作系统对事件处理完成后，再让原来的程序继续占用中央处理器执行。

多道程序设计技术与中断系统

​ 一个计算机系统，尤其是采用多道程序设计技术的计算机系统，不仅有操作系统和其他的系统软件，而且还有若干应用程序。这些程序只有占用中央处理器执行时才能履行自己的职责。但是，一个中央处理器在任何时刻最多只能被一个程序占用。那么，应该由谁来决定哪个程序在什么时候可以占用中央处理器？我们已经知道中断装置在判别到有某个事件发生时，就会触发一个中断而让操作系统去占用处理器，操作系统对事件处理结束后，又主动让出处理器，让出的处理器应被哪个程序占用？这与所发生的事件的性质、对事件的处理情况、系统中各个程序的状态有关。因而，操作系统在让出处理器时应根据对事件处理情况从那些具备占用处理器条件的程序中选择一个程序，被选中的程序就可占用处理器，直到中再一次发生事件而被中断。被中断的程序什么时候能继续占用处理器？这仍取决于事件的性质和对事件的处理情况，若它具备占用处理器的条件，则与其他程序一起等待操作系统的选择。操作系统总是按预定的策略去选择可占用处理器的程序，因此，刚被中断的程序不一定立即被选中。所以，系统中的若干程序可能交替他占用处理器。于是又出现一个新问题：怎样保证各个被中断的程序能在再一次占用处理器时继承以前执行的情况，继续执行？

​ 中断装置在发现中断事件后，首先把被中断程序的断点（当前的指令地址）等保存起来，然后让操作系统的处理程序占用处理器。操作系统在处理事件之前，把被中断程序在处理器的各寄存器中设置的状态保存起来，在事件处理结束后，选中某个程序占用处理器时再把被保存的该程序的状态恢复到各寄存器中，同时把该程序的返回地址（原断点或亲折启动点）装入指令地址计数器中。于是，被选中的程序就可占用处理器，根据被中断前的情况继续执行。

通道

为了使CPU从I/O事务中解脱出来，同时为了提高CPU与设备、设备与设备之间的并行度，设置了通道。

通道定义：是独立于CPU的专门负责数据输入/输出传输工作的处理机，对外部设备实现统一管理，代替CPU对输入/输出操作进行控制，从而使输入/输出操作可以与CPU并行操作。

引入目的：实现外设与CPU的并行操作，实现设备与设备的并行，从而提高整个系统的效率。

（DMA？）

原语

原语是一些关闭中断（屏蔽中断）的公用小程序

一般是指由若干条指令组成的程序段，用来实现某个特定功能，在执行过程中不可被中断。在操作系统中，某些被进程调用的操作，如队列操作、对信号量的操作、检查启动外设操作等，一旦开始执行，就不能被中断，否则就会出现操作错误，造成系统混乱。所以，这些操作都要用原语来实现。原语是操作系统核心（不是由进程，而是由一组程序模块组成）的一个组成部分，并且常驻内存，通常在管态下执行。

特点

• 处于操作系统最底层，最接近硬件
• 运行具有原子性，操作不允许中断
• 运行时间短，调用频繁

第二章：操作系统结构

考试主要内容在系统调用与操作系统结构。

操作系统服务

看看就行

系统调用

系统调用是内核的一部分，本质上也是一种软中断（trap）

系统调用使用和执行过程

（管态-内核态，目态-用户态）

• 操作系统提供若干功能子程序（系统调用），这些系统调用（更严格地说，系统调用对应的服务程序）在管态下执行（所以内核态时无法执行系统调用，而是直接执行系统调用对应的服务程序）。
• 现代计算机系统硬件提供一条“访管指令”，该指令可以在目态下执行。
• 用户编制程序需要请求操作系统服务时，使用系统调用。编译程序将其转换成目标程序中的 “访管指令” 及一些参数。
• 目标程序执行时，当CPU执行到 “访管指令”，产生自愿性中断，操作系统接过控制权（管态）。
• 操作系统分析相关参数，让对应的 “系统调用” 子程序为用户服务。
• 完成系统调用后，操作系统将CPU状态改变为目态，返回到用户程序继续执行。

执行系统调用的主要操作

• 1、传递系统调用参数
• 2、执行陷入指令
• 3、执行相应的服务程序
• 4、返回用户态

系统调用分类

• 文件操作类
  • 如：打开文件、建立文件、读文件、写文件、关闭文件及删除文件等。
• 资源申请类
  • 如：请求分配主存空间、归还主存空间、分配外围设备及归还外围设备等。
• 控制类
  • 执行中的程序可以请求操作系统中止其执行或返回到程序的某一点再继续执行。操作系统要根据程序中止的原因和用户的要求作出处理，因而这类系统调用有：正常结束、异常结束及返回断点/指定点等。
• 信息维护类
  • 如：设置日期时间、获取日期时间、设置文件属性及获取文件属性等。

系统调用与API

一般应用程序开发人员根据应用程序接口(API)设计程序。API是一系列适用于应用程序员的函数，包括传递给每介函数的参数及其返回的程序员想得到的值。

有三种应用程序员常用的API：

• 适用于Windows系统的Win32 API

• 适用于POSIX系统的POSIXAPI（包括几乎所有UNIX、Linux和MacOSX版本），

• 用于设计运行于Java虚拟机程序的JavaAPI。

不用系统调用而是使用API的原因

• 使用API编程的程序可移植性强
• 实际的系统调用比API更注重细节且困难

系统调用接口

系统调用接口截取API的函数调用，并调用操作系统中相应的系统调用。通常，每个系统调用有一个与其相关的数字，系统调用接口根据这些数字维护一个列表索引。然后，系统调用接口根据索引来调用所需的操作系统内核中的系统调用，并返回系统调用状态及其他返回值。

系统调用的参数传递

​ 向操作系统传递参数有三种方法。最简单的是通过寄存器来传递参数。不过有时，参数数量会比寄存器多。这时，这些参数通常存在内存的块和表中，并将块的地址通过寄存器来传递。Linux和Solaris就采用这种方法。参数也可通过程序放在或压入堆栈中，并通过操作系统弹出。有的系统采用块或堆栈方法，因为这些方法并不限制所传递参数的数量或长度。

操作系统设计与实现

用户目标：方便和容易使用、容易学习、可靠、安全和快速

系统目标：操作系统应该容易设计、实现和维护，也应该灵活、可靠、高效且容错。

结构设计目标

• 正确性
  • 影响操作系统正确性的因素：
    随机性：任务类型和到达系统的时间是随机的；系统中发生的各种事件是随机的，资源使用情况是随机的。
    操作系统必须充分估计和把握各种不确定因素。
    结构良好 → 保证正确性，易于验证其正确性
• 高效性
  • 减少操作系统自身的开销（时间开销、空间开销）
    特别是：核心程序的设计（关键，原则：少而精，有效灵活）
• 易维护性
  • 增、删、改、调整
• 移植性
  • 移植性：能否方便地把操作系统移植到一个新的硬件环境中。
  • 原则：减少与硬件直接相关的程序量，将其独立封装。采用标准语言书写操作系统

机制与策略

一个重要原理是策略(policy)和机制(mechanism )的区分。机制决定如何做， 策略决定做什么。

操作系统结构

模块结构

系统中每一个模块都是根据他们要完成的功能来划分的，这些功能模块按照一定的结构方式组合起来协同完成整个系统的功能。适用于系统小、模块少、使用环境稳定的系统。

优点

• 结构紧密、接口简单直接、系统效率相对较高

缺点

• 各模块相互牵连，不容易把握好模块的独立性，导致系统结构不清晰。

• 可扩展性较差

• 更换或修改模块困难（各模块相互牵连导致耦合度高）

• 系统的可适应性差，复杂度增长迅速

层次结构

按照层次结构设计的操作系统，就是将操作系统的所有功能模块按照功能的调用次序排列成若干层，使得功能模块之间只存在单向调用和单向依赖。

优点

• 模块间的组织和依赖关系清晰明了，系统的可读性、可适应性及可靠性强

• 修改模块对系统影响小，便于修改和扩充。

缺点

• 如何进行有效的分层

微内核结构

主要思想是在操作系统的内核中只留下一些最基本的功能，其他服务用若干个运行在用户态的进程来实现。非常适用于分布式系统。

优点

• 每个服务进程独立，某个服务崩溃不会引起其他服务崩溃，可靠性好。

• 系统灵活性好。

• 便于维护，修改某一服务不会影响其他部分。

• 操作系统可移植性强

缺点

• 微内核相互通信，导致系统效率不高。

一二章习题拾遗

• 无进程处于运行状态则就绪和等待队列均为空（错）。
  • 死锁时无进程运行，等待队列不为空。
• 实时操作系统必须在被控对象规定时间内处理完来自外部的事件
• 描述操作系统的典型观点
  • 操作系统是众多软件的结合（对
  • 操作系统是用户和计算机间的接口（对
  • 操作系统是资源管理者（对
  • 操作系统是虚拟机（错）
• 中断发生后，进入中断处理的程序属于操作系统程序
• OS通常为用户提供四种使用接口：
  • 终端命令
  • 图标菜单
  • 系统调用
  • 类似DOS的批命令文件或UNIX的shell文件
• 单处理器中可以并行的是
  • 处理器与设备
  • 处理器与通道
  • 设备与设备
  • 进程与进程，这个不能并行，只能并发串行
• 进程切换不可能发生在用户态，而系统调用、外部中断、缺页可以
• 中断处理和子程序调用都需要压栈以保护现场。中断处理一定会保存而子程序调用不需要保存的是程序状态字寄存器
  • 因为子程序调用是系统能够预知的，且一般在进程内部执行，不会更改程序状态，只要更新寄存器就行。
• 计算机开机后，操作系统最终被加载到RAM
• 处理外部中断时，操作系统保存通用寄存器内容，中断隐指令自动保存程序计数器，
• 访存会使CPU从用户态变到内核态

第三章：进程

进程：一个程序在一个数据集合上的一次执行过程。（进程是具有独立功能的程序关于某个数据集合上的一次运行活动，是系统进行资源分配和调度的独立单位。）

程序与进程之间的区别

• 进程是由程序和数据组成的，进程离开程序是没有意义的。
• 程序是静态的，进程是动态的。
• 进程有生命周期，有诞生有消亡。进程是短暂的，而程序是相对长久的。
• 一个程序可以对应多个进程。
  • 可再入程序（两个及两个以上进程共用一个程序）：可被多个进程同时调用的程序。
    • 具有下列特征：它是纯代码的，即在执行过程中自身不会改变，调用它的进程应该提供数据区（工作区）。
• 进程有创建其它进程的功能，而程序没有。
  • 进程比程序更能真实地描述并发执行。

进程控制块

系统为了管理进程设置了一个专门的数据结构，用于记录进程的外部特征，描述进程的运动变化过程。
系统利用PCB来控制和管理进程，所以，PCB是系统感知进程存在的唯一标志，进程与PCB是一一对应的。

PCB的内容

记录了管理进程所必需的信息

• 标识信息：进程标识（进程名字，进程的内部标识）；用户名
• 说明信息：进程状态；等待原因；进程程序和数据的存储信息（起始地址，长度）。
• 现场信息：记录保存了重要寄存器（通用寄存器、控制寄存器、程序状态字寄存器）内容（也就是寄存器的值）以及程序计数器（下条要执行的指令的地址），用于恢复断点，让进程继续执行。
• 管理调度信息：进程优先数；进程队列指针；消息队列指针；进程使用的资源清单；进程家族关系；进程当前打开的文件。

系统并发度（PCB表）

​ 为便于管理，系统把所有PCB组织在一起，并把它们放在内存的固定区域，就构成了PCB表。PCB表的大小决定了系统中最多可同时存在的进程个数，个数也叫系统的并发度。
​ 注：多道程序中的多道与系统并发度中的PCB个数不同。如有十个用户（多道）在上机，而每个用户有>=1个进程。系统并发度>多道。

进程的组成：程序 + 数据 + PCB（构成进程三要素）

进程的状态及其转换

五个状态，new（新建），ready（就绪），running（运行），waiting（等待/阻塞），terminated（终止）。

• ready：一个进程已经具备运行条件，但由于无CPU暂时不能运行的状态。（进程已得到除CPU以外的所有资源，一旦获得CPU时，立即可以运行。）

• waiting：进程因等待某种事件的发生而暂时不能运行的状态。如等待I/O结束，即使CPU空闲，该进程也不能运行。

进程的创建

系统为一个程序分配一个工作区（存放程序处理的数据），并为该程序建立一个进程控制块后，进程创建完成。
完成以下工作：

• 建立一个PCB（找一个空PCB）。
• 为进程分配内存等必要资源（进程的工作区，存放程序处理的数据集）。
• 填写PCB中各项目,例如，初始状态为 “就绪态”。
• 把PCB插入进程就绪队列。

（至于什么是就绪队列，后文会讲）

就绪 -> 运行

被调度程序选中。

运行 -> 就绪

分配给进程的进间片执行完成（轮转调度算法）、高优先级的进程到达（抢占式调度）。

运行 -> 等待/阻塞

当进程请求资源的使用权(如外设)或等待事件发生(如I/O完成)。

一个进程从运行到阻塞，就会调度一个进程从就绪到运行。

操作系统会将该进程的PCB放入阻塞队列中，队列根据不同的事件进行划分。所以会有多个阻塞队列，原因如下：

如果所有阻塞进程放在同一个阻塞队列中，当一个事件完成后操作系统不得不扫描整个队列找到那些等待该事件的进程然后将其放进就绪队列中，这样的效率十分低下，因此通常是为每一个事件创建一个阻塞队列。

等待/阻塞 -> 就绪

当进程已经获取所需资源的使用权或者等待事件已完成。

当按照优先级进行调度时，操作系统会将优先级相同的进程PCB从阻塞队列放进一个就绪队列，避免扫描等低效的做法，这是典型的用空间换时间的做法。

所以只会有一个就绪队列。

阻塞/唤醒进程

正在执行的进程，由于需要的某些事件未发生，如请求系统资源失败、等待某种操作的完成、新数据尚未到达或等待新任务的到达等，则由系统自动执行阻塞原语，使自己由运行状态变为阻塞状态。进程的阻塞是进程自身的一种主动行为，只有处于运行状态的进程，才可能将其转为阻塞状态。

阻塞原语（Block）的执行过程如下：

• 找到将要被阻塞进程的标识号对应的 PCB；
• 若该进程为运行状态，则保护其现场，将其状态转为阻塞状态，停止运行；
• 将该 PCB 插入到相应事件的等待队列中去。
• 当被阻塞进程所需要的事件发生时，如 I/O 操作已完成或其所需要的数据已到达，则由相关进程（例如，提供数据的进程）执行唤醒原语，将等待该事件的进程唤醒。进程的唤醒是一种被动行为，需要其他进程触发。

唤醒原语（Wakeup）的执行过程如下：

• 在该事件的等待队列中找到相应进程的 PCB；
• 将其从等待队列中移出，并置为就绪状态；
• 把该 PCB 插入就绪队列中，等待调度程序调度。

阻塞/唤醒是一对作用刚好相反的原语，必须成对使用。阻塞原语是由被阻塞进程自我调用实现的，而唤醒原语则是由一个与被唤醒进程相合作或被其他相关的进程调用实现的。

挂起与激活

出于用户观察需要，进程可以执行挂起和激活两种操作。挂起是将活跃状态转为挂起状态，使进程不再被系统调用；激活是将挂起状态转为活跃状态。

进程挂起的几种情况：

• 终端用户的需要：当终端用户在运行程序期间发现有可疑问题，希望暂停程序的运行以便研究其执行情况或做一定的修改；
• 父进程请求；
• 符合调节的需要；
• 操作系统的需要：有时希望挂起某些进程以便检查运行中的资源使用情况或进行记账。

挂起原语（Suspend）的执行过程如下：

• 检查被挂起的进程的状态；
• 若是活动就绪状态，便将其改成挂起就绪；若是活动阻塞状态，便将其改成挂起阻塞；
• 为方便用户或父进程考察该进程的运行情况，把该进程的 PCB 复制到某指定的内存区域；
• 若被挂起的进程正在执行，则转向调度程序重新调度。

激活原语（Active）的执行过程如下：

• 将进程从外存调入内存，检查该进程的现行状态；
• 若是挂起就绪，便将其改为活动就绪；若是挂起阻塞，便将其改为活跃阻塞；
• 假如采用的是抢占调度策略，则每当有挂起就绪进程被激活而加入就绪队列时，便检查是否需要重新调度，即
• 由调度程序将被激活的进程和当前进程两者优先级进行比较；
  • 若被激活进程优先级低，则不必重新调度；若当前进程优先级低，则把处理机分配给被激活的进程。

进程切换

进程切换在什么时候发生呢？理论上在任何时刻只要操作系统拿到控制权就可以进行进程切换，那么什么时候操作系统会重新拿到控制权呢？
  这里首先考虑中断的情况，而中断又可分为两种：中断和陷阱。中断一般是与当前正运行进程无关的某种外部事件相关，例如完成了一次I/O操作，中断处理器完成一些基本的辅助操作后将控制权转给与已发生的终端相关的操作系统历程，简单来说中断的发生属于正常的事件，不过是操作系统暂时停止执行当前进程转为处理另外一件更加紧急的事情。例如以下三种中断：
  1、时钟中断。当前进程时间片到期，转为从就绪队列中调度新的进程开始运行。
  2、I/O中断。某一I/O完成，操作系统判断是否有正在等待该I/O的进程，如果有将其放回就绪态，随后操作系统根据调度算法调度合适的进程继续运行。
  3、缺页中断。处理器遇到一个引用不存在内存中的虚存地址时，此时会发生缺页中断，然后操作系统要根据算法将访问的页调入内存，这块的处理与操作系统对内存管理有很大关系。
  除了中断，陷阱也有可能会导致进程状态的切换。所谓陷阱就是异常或者错误。即发生在程序内部的不可预期的非法错误。如果错误致命则将当前进程改为退出态，不致命时操作系统的行为决定于操作系统的设计，有可能是简单的通知用户，也有可能是尝试恢复。
  还有一种可能会导致进程切换的事件，就是系统调用。当用户进程发起一个特权指令（系统调用）时，操作系统会将当前用户进程设置为阻塞态，然后会调用系统例程执行系统调用指令，当执行完毕会在此调度用户进程开始执行。
  综上所述，可能造成进程状态切换的事件有三种中断，陷阱(异常)，系统调用。

切换过程

进程切换的过程如下：

1. 保存处理机上下文，包括程序计数器和其他寄存器；
2. 更新PCB信息（记住PCB状态）；
3. 把进程的 PCB 移入相应的队列，如就绪、在某事件阻塞等队列；
4. 选择另一个进程执行，并更新其 PCB；
5. 更新内存管理的数据结构；
6. 恢复处理机上下文。

进程的终止

由以下14种事件触发：
1、正常完成。正常结束运行。
2、超过时限。进程运行超过规定的时限。
3、无内存可用。系统无法满足进程需要的内存。
4、超出范围。进程试图访问非法的内存单元。
5、保护错误。进程试图使用不允许使用的资源或文件。
6、算术错误。进程试图进行被禁止的运算。
7、时间超出。进程等待某一事件发生的时间超过了规定的时间。
8、I/O失败。在输入输出期间发生错误。
9、无效指令。进程试图执行一个不存在的指令。
10、特权指令。进程试图使用为操作系统保留的指令。
11、数据误用。错误类型或未初始化的一块数据。
12、操作员或操作系统干涉。操作员或操作系统终止进程。
13、父进程终止。在某些操作系统中，父进程终止时操作系统会自动终止该进程的所有子进程。
14、父进程请求。父进程要求终止其子进程。

进程调度队列

就绪状态的所有进程存在就绪队列。阻塞状态的进程根据事件不同存在不同的阻塞队列。

任务队列：存放系统中的所有进程

处理器的三级调度

进程调度（程序）的职责（任务）是控制协调进程对CPU的竞争，即按选定的调度算法从就绪队列中选择一个进程，让它占用CPU（即把CPU的使用权交给被选中的进程，把CPU分配给被选中进程）执行。

作业调度（长期调度、高级调度）

其主要任务是按照一定的原则从外存上处于后备状态的作业中选择一个或多个，给他们分配内存、输入输出设备等必要资源，并建立相应的进程以使其具有获取竞争处理器的权利。

频率低，通常几分钟一次。

批处理系统或通用操作系统的批处理部分由于新提交的作业先放在磁盘上，所以需要作业调度将其分批装入内存。其他类型操作系统一般不需要作业调度。

执行调度时需要解决两个问题。

第一，调度程序必须决定操作系统可以接纳多少个作业进入内存。这取决于多道程序的并发程度，即允许有多少个作业同时在内存中运行。

第二，调度程序必须决定接纳哪些作业。这主要取决于所采取的调度算法。

这里解释一下作业和进程的区别与联系

作业可分为：编译、链接、装入、和运行这4个作业步。

当一个作业被作业调度（高级调度）选中进入内存并投入运行时，操作系统为此用户作业生成用户进程完成其计算任务。

进程是已提交完毕并选中运行的作业（程序）的执行实体，也是为完成作业任务向系统申请和分配资源的基本单位，它处于运行，就绪，等待等多个状态变化之中。

综上所述：

作业是任务实体，进程是完成任务的执行实体

没有作业任务，进程无事可做；没有进程，作业任务无法完成

作业的概念更多的用于批处理操作系统；进程多用于各种多道程序设计系统

内存调度（中级调度、交换调度）

引入的主要目的是提高内存利用率和系统吞吐率，主要任务是按照给定的原则和策略，将处于外存对换区中的具备运行条件的进程调入内存，并将其状态改为就绪状态，挂在就绪队列；或将处于内存中暂时不能运行的进程交换到外存对换区，此时进程状态为挂起状态。

当内存资源紧缺时，会把暂时不能运行的进程换出内存，此时这个进程处于“挂起”状态，不参与低级调度；当进程具备运行条件且内存资源富裕时，再将进程重新回调内存工作。

起到短期均衡系统负载的作用，充分提高内存利用率和系统吞吐率。

进程调度（低级调度、CPU调度）

主要任务是按照给定的原则和策略从就绪队列中选取一个进程，将处理器分配给它。

运行频率很高，几十毫秒一次。

再议进程创建与终止

创建

大多数操作系统根据-个唯一的进程标识符 (process identifier, pid) 来识别进程，pid 通常是一个整数值。
理解进程创建的几个重要概念，这一项也是本章的重点!

Fork()的两个要点:

• 内核为子进程做一个父进程的上下文拷贝。
  • 拷贝包括: (1) 复制父进程的PCB作为子进程的PCB (2) 在新的地址空间中复制父进程的一个拷贝
• 父进程与子进程在不同的地址空间上运行。

关于①的理解:子进程与父进程共享子进程创建前的所有资源。
关于②的理解:子进程在创建后和父进程是竞争关系，两个进程依据进程调度的规则分别执行。

总结 ： 先继承，后分离。

Fork( )的返回值: Pid=fork();

• 正确执行:
  • 父进程返回子进程号;
  • 子进程返回0。
• 出现错误:返回-1。

int main()
{
pid_t  pid;
	/* fork another process */
	pid = fork();
	if (pid < 0) { /* error occurred */
		fprintf(stderr, "Fork Failed");
		exit(-1);
	}
	else if (pid == 0) { /* child process */
		execlp("/bin/ls", "ls", NULL);
	}
	else { /* parent process */
		/* parent will wait for the child to complete */
        //子进程结束后唤醒父进程
		wait (NULL);
		printf ("Child Complete");
		exit(0);//这也是一个系统调用
	}
}

一些细节问题

子进程复制父进程的内存空间，上面的代码也会复制并继续运行，则会根据不同的pid进入不同的代码块。

execlp()函数会从PATH 环境变量所指的目录中查找符合参数file的文件名，找到后便执行该文件，然后将第二个以后的参数当做该文件的argv[0]、argv[1]……，最后一个参数必须用空指针(NULL)作结束。

fork（）会产生一个和父进程完全相同的子进程，但子进程在此后多会exec系统调用，出于效率考虑，linux中引入了“写时复制“技术，也就是只有进程空间的各段的内容要发生变化时，才会将父进程的内容复制一份给子进程。在fork之后exec之前，两个进程用的是相同的物理空间（内存区），子进程的代码段、数据段、堆栈都是指向父进程的物理空间，也就是说，两者的虚拟空间不同，但其对应的物理空间是同一个。当父子进程中有更改相应段的行为发生时，再为子进程相应的段分配物理空间，如果不是因为exec，内核会给子进程的数据段、堆栈段分配相应的物理空间（至此两者有各自的进程空间，互不影响），而代码段继续共享父进程的物理空间（两者的代码完全相同）。而如果是因为exec，由于两者执行的代码不同，子进程的代码段也会分配单独的物理空间。

fork之后内核会通过将子进程放在队列的前面，以让子进程先执行，以免父进程执行导致写时复制，而后子进程执行exec系统调用，因无意义的复制而造成效率的下降。

fork时子进程获得父进程数据空间、堆和栈的复制，所以变量的地址（当然是虚拟地址）也是一样的。

写出下面程序的运行结果：

int main()
{
       pid_t cld_pid;
       int status;
       int a=1,b=2;
       for(int i = 0; i < 2; i++ ){
              if ((cld_pid = fork()) == 0){
                     a+=1;
                     printf("a=%d\n",a);
              }
              else{
                     b+=1;
                     printf("b=%d\n",b);
              }
       }
       wait(&status);
       return 0;
}

这其实就是考察了如果一个进程在for循环进行fork，会产生什么样的结果，哪些变量的值已经改变，哪些变量的值没有改变。

实际上它的运行一共产生了三个子进程：

首先父进程fork出了子进程1，同时自己执行了b自加和打印，得到b=3。此时在第一轮循环中，子进程1的变量分别为i=0，a=1，b=2。第二轮循环中，创建了子进程2，同时执行b的自加和打印，得到b=4，耗尽循环条件。而子进程2的变量为i=1，a=1，b=3。

对于子进程1，会执行a的自加和打印，得到a=2，完成第一轮循环。在第二轮循环中创建了子子进程1，并对b自加和打印，得到b=3。子子进程1的变量分别为i=1，a=2，b=2。

对于子进程2，会执行a的自加和打印，得到a=2，然后由于i=1，结束。

对于子子进程1，会执行a的自加和打印，得到a=3，而由于i已经为1，再也没有新的循环了。

终止

有了父进程与子进程的概念后，我们来讨论-一下进程结束的问题。正常情况下，子进程结束后会有父进程回收子进程的资源。但是有些时候在子进程结束前，父进程已经结束或是没有wait()语句等待子进程结束，这时子进程就不可能被父进程处理了，需要操作系统出面解决问题。不同的系统有不同的处理方式，有的系统不允许子进程在没有父进程的情况下继续执行，而Linux和UNIX会交由1号进程(init) 作为父进程回收这类子进程。

UNIX:可以通过系统调用exit()来终止进程，父进程可以通过系统调用wait()以等待子进程的终止。系统调用wait()返回了终止子进程的进程标识符，以使父进程能够知道哪个子进程终止了。如果父进程终止，那么其所有子进程会以init进程作为父进程。因此，子进程仍然有一个父进程来收集状态和执行统计。

进程间通信

参考

进程通信 IPC就是进程间的数据交换，通常可以分为低级通信方式和高级通信方式。

• 低级通信方式：进程互斥与同步交换的信息量较少且效率较低，因此称这两种进程通信方式为低级进程通信方式，相应地也将P、V原语称为两条低级进程通信原语。

• 高级通信方式：高级通信方式是指以较高效率传递大量数据的通信方式。高级通信方式主要可分为共享通信（共享存储器系统通信），消息传递（消息传递系统通信）和管道通信（管道通信系统或共享文件系统通信）三大类，这三大类又可以分为管道，命名管道，信号，消息队列，共享内存，信号量，以及套接字七小类。

高级通信方式

共享存储器系统

相互通信的进程共享某些数据结构或共享存储区。

基于共享数据结构的通信方式：诸进程通过公用某些数据结构交换信息。如生产者-消费者问题。

基于共享存储区的通信方式：在存储器中划出一块共享存储区，诸进程可通过对共享存储区进行读或写来实现通信。包括建立共享存储区、附接及断接。

消息传递系统

在消息传递系统中，进程间的数据交换以消息为单位，用户直接利用系统提供的一组通信命令（原语）来实现通信。

消息传递系统因其实现方式不同可分为：

直接通信方式：发送进程将消息发送到接收进程，并将其挂在接收进程的消息队列上；接收进程从消息队列上取消息。

间接通信方式：发送进程将消息发送到信箱，接收进程从信箱中取消息。

消息传递系统是实现进程通信的常用方式，这种通信方式既可以实现进程间的信息交换，也可以实现进程间的同步。

消息缓冲通信

消息缓冲通信是直接通信方式的一种实现。

消息缓冲通信的实现思想:

• 发送进程应先在自己的工作区中设置一个发送区，把欲发送的消息填入其中，然后再用发送原语将其发送出去。

• 接收进程调用接收原语从自己的消息缓冲队列中摘下第一个消息，并将其内容复制到自己的消息接收区内。

信箱通信

信箱通信方式中，进程之间通信需要通过共享数据结构实体——信箱来进行。

信箱是一种数据结构，其中存放信件。信箱逻辑上分成信箱头和信箱体两部分。信箱头中存放有关信箱的描述。信箱体由若干格子组成，每格存放一个信件，格子的数目和大小在创建信箱时确定。

信箱通信通过信箱通信原语实现，信箱通信原语包括：

信箱的创建和撤消：
消息的发送和接收：

Send(mailbox,message);
Receive(mailbox,message);

PS：进程间的消息通信存在同步关系

管道（共享文件）通信

管道（pipe）通过连接读进程和写进程的共享文件来实现读写进程之间通信。

使用管道通信时，基本上采用文件系统的原有机制实现。包括创建、打开、关闭、读写等。

管道机制应提供以下三方面的协调能力：

互斥：诸进程互斥读写管道
同步：管道空、满情况处理
存在：确定对方是否存在

管道是一种半双工的通信方式，数据只能单向流动，上游进程往管道中写入数据，下游进程从管道中接收数据。如果想实现双方通信，那么需要建立两个管道。

管道就是一个文件，是一种只存在于内存中的特殊的文件系统。

管道是由内核管理的一个缓冲区，缓冲区被设计成为环形的数据结构，以便管道可以被循环利用（循环队列）。

Linux系统中的进程间通信的机制（了解）

管道

首先应该就是我们最熟悉的管道了。如果你学过 Linux 命令，那你肯定使用过|这个竖线。

$ ps auxf | grep mysql

上面命令行里的|竖线就是一个管道，它的功能是将前一个命令ps auxf的输出，作为后一个命令grep mysql的输入，从这功能描述，可以看出管道传输数据是单向的，如果想相互通信，我们需要创建两个管道才行。

管道的类型有可以分为无名管道和有名管道两种。有名管道和无名管道的读写方式是相同的。

管道的一个缺点：管道这种通信方式效率低，不适合进程间频繁地交换数据

其实，所谓的管道，就是内核里面的一串缓存。从管道的一段写入的数据，实际上是缓存在内核中的，另一端读取，也就是从内核中读取这段数据。另外，管道传输的数据是无格式的流且大小受限。

管道分为有名管道和无名管道

• 无名管道是一种半双工的通信方式，数据只能单向流动，而且只能在具有亲缘关系的进程间使用。进程的亲缘关系一般指的是父子关系。无名管道一般用于两个不同进程之间的通信。当一个进程创建了一个管道,并调用fork创建自己的一个子进程后，父进程关闭读管道端，子进程关闭写管道端，这样提供了两个进程之间数据流动的一种方式。

• 有名管道也是一种半双工的通信方式，但是它允许无亲缘关系进程间的通信。

• 无名管道：优点：简单方便；缺点：1）局限于单向通信2）只能创建在它的进程以及其有亲缘关系的进程之间;3）缓冲区有限；

• 有名管道：优点：可以实现任意关系的进程间的通信；缺点：1）长期存于系统中，使用不当容易出错；2）缓冲区有限

消息队列

前面提到管道的通信方式效率较低，因此管道不适合进程间频繁地交换数据。

对于这个问题，消息队列的通信模式就可以解决。比如，A 进程要给 B 进程发送消息，A 进程把数据放在对应的消息队列后就可以正常返回了，B 进程需要的时候再去读取数据就可以了。同理，B 进程要给 A 进程发送消息也是如此。

下面我们来了解一下消息机制：

UNIX的消息机制中使用了两种数据结构:

消息首部：消息首部中记录消息的类型、大小、指向消息数据区的指针、消息队列的链接指针等。
消息队列头标：每个消息队列的消息头标中，包含了指向消息队列中第一个消息的指针和指向最后一个消息的指针，队列中消息的数目，队列中消息数据的总字节数，队列所允许的消息数据的最大字节总数，还可以含有最近一次执行发送操作的进程标识号和时间等。

消息队列是保存在内核中的消息链表，在发送数据时，会分成一个一个独立的数据单元，也就是消息体（数据块），消息体是用户自定义的数据类型，消息的发送方和接收方要约定好消息体的数据类型，所以每个消息体都是固定大小的存储块，不像管道是无格式的字节流数据。如果进程从消息队列中读取了消息体，内核就会把这个消息体删除。

消息队列生命周期随内核，如果没有释放消息队列或者没有关闭操作系统，消息队列会一直存在，而前面提到的匿名管道的生命周期，是随进程的创建而建立，随进程的结束而销毁。

消息这种模型，两个进程之间的通信就像平时发邮件一样，你来一封，我回一封，可以频繁沟通了。

但邮件的通信方式存在不足的地方有两点，一是通信不及时，二是附件也有大小限制，这同样也是消息队列通信不足的点。

消息队列不适合比较大数据的传输，因为在内核中每个消息体都有一个最大长度的限制，同时所有队列所包含的全部消息体的总长度也是有上限。在 Linux 内核中，会有两个宏定义 MSGMAX 和 MSGMNB，它们以字节为单位，分别定义了一条消息的最大长度和一个队列的最大长度。

消息队列通信过程中，存在用户态与内核态之间的数据拷贝开销，因为进程写入数据到内核中的消息队列时，会发生从用户态拷贝数据到内核态的过程，同理另一进程读取内核中的消息数据时，会发生从内核态拷贝数据到用户态的过程。

共享内存

消息队列的读取和写入的过程，都会有发生用户态与内核态之间的消息拷贝过程。那共享内存的方式，就很好的解决了系统开销大的问题。

共享内存可使若干进程共享主存中的某一个区域，且使该区域出现在多个进程的虚地址空间中。当进程间欲利用共享内存进行通信时，必须首先在主存中建立一个共享存储区，然后将它附接到自己的虚地址空间上。此后，进程对该区的访问操作，与对其虚地址空间中其他部分的操作完全相同。进程之间以后便可以通过对共享存储区中数据的读/写来进行直接通信。

现代操作系统，对于内存管理，采用的是虚拟内存技术，也就是每个进程都有自己独立的虚拟内存空间，不同进程的虚拟内存映射到不同的物理内存中。所以，即使进程 A 和 进程 B 的虚拟地址是一样的，其实访问的是不同的物理内存地址，对于数据的增删查改互不影响。

共享内存的机制，就是拿出一块虚拟地址空间来，映射到相同的物理内存中。这样这个进程写入的东西，另外一个进程马上就能看到了，都不需要拷贝来拷贝去，传来传去，大大提高了进程间通信的速度。

信号

软中断信号（简称信号）是一种实现进程间简单通信的设施，用于通知对方发生了异常事件。

软中断是对硬件中断的一种模拟，接收进程在收到软中断信号后，将按照事先的规定去执行一个软中断处理程序。

软中断处理程序必须等到接收进程执行时才能生效。

运行在 shell 终端的进程，我们可以通过键盘输入某些组合键的时候，给进程发送信号。例如

• Ctrl+C 产生 SIGINT 信号，表示终止该进程；
• Ctrl+Z 产生 SIGTSTP 信号，表示停止该进程，但还未结束；

信号是进程间通信机制中唯一的异步通信机制，因为可以在任何时候发送信号给某一进程，一旦有信号产生，我们就有下面这几种，用户进程对信号的处理方式。

1. 执行默认操作。Linux 对每种信号都规定了默认操作，例如，上面列表中的 SIGTERM 信号，就是终止进程的意思。Core 的意思是 Core Dump，也即终止进程后，通过 Core Dump 将当前进程的运行状态保存在文件里面，方便程序员事后进行分析问题在哪里。
2. 捕捉信号。我们可以为信号定义一个信号处理函数。当信号发生时，我们就执行相应的信号处理函数。
3. 忽略信号。当我们不希望处理某些信号的时候，就可以忽略该信号，不做任何处理。有两个信号是应用进程无法捕捉和忽略的，即 SIGKILL 和 SEGSTOP，它们用于在任何时候中断或结束某一进程。

Socket

前面提到的管道、消息队列、共享内存、信号量和信号都是在同一台主机上进行进程间通信，那要想跨网络与不同主机上的进程之间通信，就需要 Socket 通信了。

实际上，Socket 通信不仅可以跨网络与不同主机的进程间通信，还可以在同主机上进程间通信。

根据创建 socket 类型的不同，通信的方式也就不同：

实现 TCP 字节流通信： socket 类型是 AF_INET 和 SOCK_STREAM；
实现 UDP 数据报通信：socket 类型是 AF_INET 和 SOCK_DGRAM；
实现本地进程间通信： 「本地字节流 socket 」类型是 AF_LOCAL 和 SOCK_STREAM，「本地数据报 socket 」类型是 AF_LOCAL 和 SOCK_DGRAM。另外，AF_UNIX 和 AF_LOCAL 是等价的，所以 AF_UNIX 也属于本地 socket；

接下来，简单说一下这三种通信的编程模式。

• 针对 TCP 协议通信的 socket 编程模型

• 服务端和客户端初始化 socket，得到文件描述符；
• 服务端调用 bind，将绑定在 IP 地址和端口;
• 服务端调用 listen，进行监听；
• 服务端调用 accept，等待客户端连接；
• 客户端调用 connect，向服务器端的地址和端口发起连接请求；
• 服务端 accept 返回用于传输的 socket 的文件描述符；
• 客户端调用 write 写入数据；服务端调用 read 读取数据；
• 客户端断开连接时，会调用 close，那么服务端 read 读取数据的时候，就会读取到了 EOF，待处理完数据后，服务端调用 close，表示连接关闭。
  这里需要注意的是，服务端调用 accept 时，连接成功了会返回一个已完成连接的 socket，后续用来传输数据。

所以，监听的 socket 和真正用来传送数据的 socket，是「两个」 socket，一个叫作监听 socket，一个叫作已完成连接 socket。

成功连接建立之后，双方开始通过 read 和 write 函数来读写数据，就像往一个文件流里面写东西一样。

• 针对 UDP 协议通信的 socket 编程模型

UDP 是没有连接的，所以不需要三次握手，也就不需要像 TCP 调用 listen 和 connect，但是 UDP 的交互仍然需要 IP 地址和端口号，因此也需要 bind。

对于 UDP 来说，不需要要维护连接，那么也就没有所谓的发送方和接收方，甚至都不存在客户端和服务端的概念，只要有一个 socket 多台机器就可以任意通信，因此每一个 UDP 的 socket 都需要 bind。

另外，每次通信时，调用 sendto 和 recvfrom，都要传入目标主机的 IP 地址和端口。

• 针对本地进程间通信的 socket 编程模型

本地 socket 被用于在同一台主机上进程间通信的场景：

本地 socket 的编程接口和 IPv4 、IPv6 套接字编程接口是一致的，可以支持「字节流」和「数据报」两种协议；

本地 socket 的实现效率大大高于 IPv4 和 IPv6 的字节流、数据报 socket 实现；

对于本地字节流 socket，其 socket 类型是 AF_LOCAL 和 SOCK_STREAM。

对于本地数据报 socket，其 socket 类型是 AF_LOCAL 和 SOCK_DGRAM。

本地字节流 socket 和 本地数据报 socket 在 bind 的时候，不像 TCP 和 UDP 要绑定 IP 地址和端口，而是绑定一个本地文件，这也就是它们之间的最大区别。

第三章习题拾遗

阻塞与唤醒

可能将进程唤醒的是

• IO结束（可能）
• 某进程退出临界区（可能）
• 当前进程时间片用完（不会）

时间片用完会发生时钟中断，从就绪队列调度一个进程进入运行态，而不会唤醒阻塞队列的进程

记住：阻塞与唤醒是互斥操作即可

临界区

什么是临界区？
每个进程中访问临界资源的那段程序称为临界区（临界资源是一次仅允许一个进程使用的共享资源）。每次只准许一个进程进入临界区，进入后不允许其他进程进入。

进程进入临界区的调度原则
①如果有若干进程要求进入空闲的临界区，一次仅允许一个进程进入。

②任何时候，处于临界区内的进程不可多于一个。如已有进程进入自己的临界区，则其它所有试图进入临界区的进程必须等待。

③进入临界区的进程要在有限时间内退出，以便其它进程能及时进入自己的临界区。

④如果进程不能进入自己的临界区，则应让出CPU，避免进程出现“忙等”现象。

互斥对象是一种最简单的内核对象，用它可以方便的实现对某一资源的互斥访问。因为它是内核对象，因此可以产生信号，实际上，程序中就是利用这一点实现互斥的。
临界区并不是内核对象，而是系统提供的一种数据结构，程序中可以声明一个该类型变量，之后用它来实现对资源的互斥访问。当欲访问某一临界资源时，先将该临界区加锁（如果临界区不空闲，等待），用完该资源后，将临界区释放。

一般，将他们用于线程间的同步，而且通常可以互换使用。

如果要实现复杂互斥，应使用其它方法，如信号量内核对象等。临界区对象不能跨越进程，是线程间共享数据区的同步对象；互斥对象可以作为进程间共享数据区的同步对象。

所以一个进程退出临界区可能会唤醒另一个等待访问临界区的进程。

父子进程不能共享虚拟地址空间

fork（）会产生一个和父进程完全相同的子进程，但子进程在此后多会exec系统调用，出于效率考虑，linux中引入了“写时复制“技术，也就是只有进程空间的各段的内容要发生变化时，才会将父进程的内容复制一份给子进程。在fork之后exec之前，两个进程用的是相同的物理空间（内存区），子进程的代码段、数据段、堆栈都是指向父进程的物理空间，也就是说，两者的虚拟空间不同，但其对应的物理空间是同一个。当父子进程中有更改相应段的行为发生时，再为子进程相应的段分配物理空间，如果不是因为exec，内核会给子进程的数据段、堆栈段分配相应的物理空间（至此两者有各自的进程空间，互不影响），而代码段继续共享父进程的物理空间（两者的代码完全相同）。而如果是因为exec，由于两者执行的代码不同，子进程的代码段也会分配单独的物理空间。

fork之后内核会通过将子进程放在队列的前面，以让子进程先执行，以免父进程执行导致写时复制，而后子进程执行exec系统调用，因无意义的复制而造成效率的下降。

fork时子进程获得父进程数据空间、堆和栈的复制，所以变量的地址（当然是虚拟地址）也是一样的。

虚拟地址空间

单片机的 CPU 是直接操作内存的「物理地址」。

在这种情况下，要想在内存中同时运行两个程序是不可能的。如果第一个程序在 2000 的位置写入一个新的值，将会擦掉第二个程序存放在相同位置上的所有内容，所以同时运行两个程序是根本行不通的，这两个程序会立刻崩溃。

操作系统是如何解决这个问题呢？

这里关键的问题是这两个程序都引用了绝对物理地址，而这正是我们最需要避免的。

我们可以把进程所使用的地址「隔离」开来，即让操作系统为每个进程分配独立的一套「虚拟地址」，互不干涉。但是有个前提每个进程都不能访问物理地址，至于虚拟地址最终怎么落到物理内存里，对进程来说是透明的，操作系统已经把这些都安排的明明白白了。

操作系统会提供一种机制，将不同进程的虚拟地址和不同内存的物理地址映射起来。

如果程序要访问虚拟地址的时候，由操作系统转换成不同的物理地址，这样不同的进程运行的时候，写入的是不同的物理地址，这样就不会冲突了。

于是，这里就引出了两种地址的概念：

• 我们程序所使用的内存地址叫做虚拟内存地址（Virtual Memory Address）
• 实际存在硬件里面的空间地址叫物理内存地址（Physical Memory Address）。

操作系统引入了虚拟内存，进程持有的虚拟地址会通过 CPU 芯片中的内存管理单元（MMU）的映射关系，来转换变成物理地址，然后再通过物理地址访问内存，如下图所示：

操作系统是如何管理虚拟地址与物理地址之间的关系？

主要有两种方式，分别是内存分段和内存分页，分段是比较早提出的，我们先来看看内存分段。

---

内存分段

程序是由若干个逻辑分段组成的，如可由代码分段、数据分段、栈段、堆段组成。不同的段是有不同的属性的，所以就用分段（Segmentation）的形式把这些段分离出来。

分段机制下，虚拟地址和物理地址是如何映射的？

分段机制下的虚拟地址由两部分组成，段选择子和段内偏移量。

• 段选择子就保存在段寄存器里面。段选择子里面最重要的是段号，用作段表的索引。段表里面保存的是这个段的基地址、段的界限和特权等级等。
• 虚拟地址中的段内偏移量应该位于 0 和段界限之间，如果段内偏移量是合法的，就将段基地址加上段内偏移量得到物理内存地址。

在上面，知道了虚拟地址是通过段表与物理地址进行映射的，分段机制会把程序的虚拟地址分成 4 个段，每个段在段表中有一个项，在这一项找到段的基地址，再加上偏移量，于是就能找到物理内存中的地址，如下图：

如果要访问段 3 中偏移量 500 的虚拟地址，我们可以计算出物理地址为，段 3 基地址 7000 + 偏移量 500 = 7500。

分段的办法很好，解决了程序本身不需要关心具体的物理内存地址的问题，但它也有一些不足之处：

• 第一个就是内存碎片的问题。
• 第二个就是内存交换的效率低的问题。

接下来，说说为什么会有这两个问题。

我们先来看看，分段为什么会产生内存碎片的问题？

我们来看看这样一个例子。假设有 1G 的物理内存，用户执行了多个程序，其中：

• 游戏占用了 512MB 内存
• 浏览器占用了 128MB 内存
• 音乐占用了 256 MB 内存。

这个时候，如果我们关闭了浏览器，则空闲内存还有 1024 - 512 - 256 = 256MB。

如果这个 256MB 不是连续的，被分成了两段 128 MB 内存，这就会导致没有空间再打开一个 200MB 的程序。

这里的内存碎片的问题：

• 外部内存碎片，也就是产生了多个不连续的小物理内存，导致新的程序无法被装载；

解决外部内存碎片的问题就是内存交换。

可以把音乐程序占用的那 256MB 内存写到硬盘上，然后再从硬盘上读回来到内存里。不过再读回的时候，我们不能装载回原来的位置，而是紧紧跟着那已经被占用了的 512MB 内存后面。这样就能空缺出连续的 256MB 空间，于是新的 200MB 程序就可以装载进来。

这个内存交换空间，在 Linux 系统里，也就是我们常看到的 Swap 空间，这块空间是从硬盘划分出来的，用于内存与硬盘的空间交换。

再来看看，分段为什么会导致内存交换效率低的问题？

对于多进程的系统来说，用分段的方式，内存碎片是很容易产生的，产生了内存碎片，那不得不重新 Swap 内存区域，这个过程会产生性能瓶颈。

因为硬盘的访问速度要比内存慢太多了，每一次内存交换，我们都需要把一大段连续的内存数据写到硬盘上。

所以，如果内存交换的时候，交换的是一个占内存空间很大的程序，这样整个机器都会显得卡顿。

为了解决内存分段的内存碎片和内存交换效率低的问题，就出现了内存分页。

---

内存分页

分段的好处就是能产生连续的内存空间，但是会出现内存碎片和内存交换的空间太大的问题。

要解决这些问题，那么就要想出能少出现一些内存碎片的办法。另外，当需要进行内存交换的时候，让需要交换写入或者从磁盘装载的数据更少一点，这样就可以解决问题了。这个办法，也就是内存分页（Paging）。

分页是把整个虚拟和物理内存空间切成一段段固定尺寸的大小。这样一个连续并且尺寸固定的内存空间，我们叫页（Page）。在 Linux 下，每一页的大小为 4KB。

虚拟地址与物理地址之间通过页表来映射，如下图：

页是存储在内存力，由 CPU 的内存管理单元 （MMU） 负责映射转换的工作，这样CPU 就可以直接通过 MMU，找出要实际要访问的物理内存地址。

而当进程访问的虚拟地址在页表中查不到时，系统会产生一个缺页异常，进入系统内核空间分配物理内存、更新进程页表，最后再返回用户空间，恢复进程的运行。

分页是怎么解决分段的内存碎片、内存交换效率低的问题？

由于内存空间都是预先划分好的，也就不会像分段会产生间隙非常小的内存，这正是分段会产生内存碎片的原因。而采用了分页，那么释放的内存都是以页为单位释放的，也就不会产生无法给进程使用的小内存。

如果内存空间不够，操作系统会把其他正在运行的进程中的「最近没被使用」的内存页面给释放掉，也就是暂时写在硬盘上，称为换出（Swap Out）。一旦需要的时候，再加载进来，称为换入（Swap In）。所以，一次性写入磁盘的也只有少数的一个页或者几个页，不会花太多时间，内存交换的效率就相对比较高。

更进一步地，分页的方式使得我们在加载程序的时候，不再需要一次性都把程序加载到物理内存中。我们完全可以在进行虚拟内存和物理内存的页之间的映射之后，并不真的把页加载到物理内存里，而是只有在程序运行中，需要用到对应虚拟内存页里面的指令和数据时，再加载到物理内存里面去。

分页机制下，虚拟地址和物理地址是如何映射的？

在分页机制下，虚拟地址分为两部分，页号和页内偏移。页号作为页表的索引，页表包含物理页每页所在物理内存的基地址，这个基地址与页内偏移的组合就形成了物理内存地址，见下图。

总结一下，对于一个内存地址转换，其实就是这样三个步骤：

• 把虚拟内存地址，切分成页号和偏移量；
• 根据页号，从页表里面，查询对应的物理页号；
• 直接拿物理页号，加上前面的偏移量，就得到了物理内存地址。

下面举个例子，虚拟内存中的页通过页表映射为了物理内存中的页，如下图：

这看起来似乎没什么毛病，但是放到实际中操作系统，这种简单的分页是肯定是会有问题的。

简单的分页有什么缺陷吗？

有空间上的缺陷。

因为操作系统是可以同时运行非常多的进程的，那这不就意味着页表会非常的庞大。

在 32 位的环境下，虚拟地址空间共有 4GB，假设一个页的大小是 4KB（2^12），那么就需要大约 100 万 （2^20） 个页，每个「页表项」需要 4 个字节大小来存储，那么整个 4GB 空间的映射就需要有 4MB 的内存来存储页表。

这 4MB 大小的页表，看起来也不是很大。但是要知道每个进程都是有自己的虚拟地址空间的，也就说都有自己的页表。

那么，100 个进程的话，就需要 400MB 的内存来存储页表，这是非常大的内存了，更别说 64 位的环境了。

多级页表

要解决上面的问题，就需要采用的是一种叫作多级页表（Multi-Level Page Table）的解决方案。

在前面我们知道了，对于单页表的实现方式，在 32 位和页大小 4KB 的环境下，一个进程的页表需要装下 100 多万个「页表项」，并且每个页表项是占用 4 字节大小的，于是相当于每个页表需占用 4MB 大小的空间。

我们把这个 100 多万个「页表项」的单级页表再分页，将页表（一级页表）分为 1024 个页表（二级页表），每个表（二级页表）中包含 1024 个「页表项」，形成二级分页。如下图所示：

你可能会问，分了二级表，映射 4GB 地址空间就需要 4KB（一级页表）+ 4MB（二级页表）的内存，这样占用空间不是更大了吗？

当然如果 4GB 的虚拟地址全部都映射到了物理内存上的话，二级分页占用空间确实是更大了，但是，我们往往不会为一个进程分配那么多内存。

其实我们应该换个角度来看问题，还记得计算机组成原理里面无处不在的局部性原理么？

每个进程都有 4GB 的虚拟地址空间，而显然对于大多数程序来说，其使用到的空间远未达到 4GB，因为会存在部分对应的页表项都是空的，根本没有分配，对于已分配的页表项，如果存在最近一定时间未访问的页表，在物理内存紧张的情况下，操作系统会将页面换出到硬盘，也就是说不会占用物理内存。

如果使用了二级分页，一级页表就可以覆盖整个 4GB 虚拟地址空间，但如果某个一级页表的页表项没有被用到，也就不需要创建这个页表项对应的二级页表了，即可以在需要时才创建二级页表。做个简单的计算，假设只有 20% 的一级页表项被用到了，那么页表占用的内存空间就只有 4KB（一级页表） + 20% * 4MB（二级页表）= 0.804MB，这对比单级页表的 4MB 是不是一个巨大的节约？

那么为什么不分级的页表就做不到这样节约内存呢？我们从页表的性质来看，保存在内存中的页表承担的职责是将虚拟地址翻译成物理地址。假如虚拟地址在页表中找不到对应的页表项，计算机系统就不能工作了。所以页表一定要覆盖全部虚拟地址空间，不分级的页表就需要有 100 多万个页表项来映射，而二级分页则只需要 1024 个页表项（此时一级页表覆盖到了全部虚拟地址空间，二级页表在需要时创建）。

我们把二级分页再推广到多级页表，就会发现页表占用的内存空间更少了，这一切都要归功于对局部性原理的充分应用。

对于 64 位的系统，两级分页肯定不够了，就变成了四级目录，分别是：

• 全局页目录项 PGD（Page Global Directory）；
• 上层页目录项 PUD（Page Upper Directory）；
• 中间页目录项 PMD（Page Middle Directory）；
• 页表项 PTE（Page Table Entry）；

TLB

多级页表虽然解决了空间上的问题，但是虚拟地址到物理地址的转换就多了几道转换的工序，这显然就降低了这俩地址转换的速度，也就是带来了时间上的开销。

程序是有局部性的，即在一段时间内，整个程序的执行仅限于程序中的某一部分。相应地，执行所访问的存储空间也局限于某个内存区域。

我们就可以利用这一特性，把最常访问的几个页表项存储到访问速度更快的硬件，于是计算机科学家们，就在 CPU 芯片中，加入了一个专门存放程序最常访问的页表项的 Cache，这个 Cache 就是 TLB（Translation Lookaside Buffer） ，通常称为页表缓存、转址旁路缓存、快表等。

在 CPU 芯片里面，封装了内存管理单元（Memory Management Unit）芯片，它用来完成地址转换和 TLB 的访问与交互。

有了 TLB 后，那么 CPU 在寻址时，会先查 TLB，如果没找到，才会继续查常规的页表。

TLB 的命中率其实是很高的，因为程序最常访问的页就那么几个。

---

段页式内存管理

内存分段和内存分页并不是对立的，它们是可以组合起来在同一个系统中使用的，那么组合起来后，通常称为段页式内存管理。

段页式内存管理实现的方式：

• 先将程序划分为多个有逻辑意义的段，也就是前面提到的分段机制；
• 接着再把每个段划分为多个页，也就是对分段划分出来的连续空间，再划分固定大小的页；

这样，地址结构就由段号、段内页号和页内位移三部分组成。

用于段页式地址变换的数据结构是每一个程序一张段表，每个段又建立一张页表，段表中的地址是页表的起始地址，而页表中的地址则为某页的物理页号，如图所示：

段页式地址变换中要得到物理地址须经过三次内存访问：

• 第一次访问段表，得到页表起始地址；
• 第二次访问页表，得到物理页号；
• 第三次将物理页号与页内位移组合，得到物理地址。

可用软、硬件相结合的方法实现段页式地址变换，这样虽然增加了硬件成本和系统开销，但提高了内存的利用率。

---

Linux 内存管理

那么，Linux 操作系统采用了哪种方式来管理内存呢？

在回答这个问题前，我们得先看看 Intel 处理器的发展历史。

早期 Intel 的处理器从 80286 开始使用的是段式内存管理。但是很快发现，光有段式内存管理而没有页式内存管理是不够的，这会使它的 X86 系列会失去市场的竞争力。因此，在不久以后的 80386 中就实现了对页式内存管理。也就是说，80386 除了完成并完善从 80286 开始的段式内存管理的同时还实现了页式内存管理。

但是这个 80386 的页式内存管理设计时，没有绕开段式内存管理，而是建立在段式内存管理的基础上，这就意味着，页式内存管理的作用是在由段式内存管理所映射而成的地址上再加上一层地址映射。

由于此时由段式内存管理映射而成的地址不再是“物理地址”了，Intel 就称之为“线性地址”（也称虚拟地址）。于是，段式内存管理先将逻辑地址映射成线性地址，然后再由页式内存管理将线性地址映射成物理地址。

这里说明下逻辑地址和线性地址：

• 程序所使用的地址，通常是没被段式内存管理映射的地址，称为逻辑地址；
• 通过段式内存管理映射的地址，称为线性地址，也叫虚拟地址；

逻辑地址是「段式内存管理」转换前的地址，线性地址则是「页式内存管理」转换前的地址。

了解完 Intel 处理器的发展历史后，我们再来说说 Linux 采用了什么方式管理内存？

Linux 内存主要采用的是页式内存管理，但同时也不可避免地涉及了段机制。

这主要是上面 Intel 处理器发展历史导致的，因为 Intel X86 CPU 一律对程序中使用的地址先进行段式映射，然后才能进行页式映射。既然 CPU 的硬件结构是这样，Linux 内核也只好服从 Intel 的选择。

但是事实上，Linux 内核所采取的办法是使段式映射的过程实际上不起什么作用。也就是说，“上有政策，下有对策”，若惹不起就躲着走。

Linux 系统中的每个段都是从 0 地址开始的整个 4GB 虚拟空间（32 位环境下），也就是所有的段的起始地址都是一样的。这意味着，Linux 系统中的代码，包括操作系统本身的代码和应用程序代码，所面对的地址空间都是线性地址空间（虚拟地址），这种做法相当于屏蔽了处理器中的逻辑地址概念，段只被用于访问控制和内存保护。

我们再来瞧一瞧，Linux 的虚拟地址空间是如何分布的？

在 Linux 操作系统中，虚拟地址空间的内部又被分为内核空间和用户空间两部分，不同位数的系统，地址空间的范围也不同。比如最常见的 32 位和 64 位系统，如下所示：

通过这里可以看出：

• 32 位系统的内核空间占用 1G，位于最高处，剩下的 3G 是用户空间；
• 64 位系统的内核空间和用户空间都是 128T，分别占据整个内存空间的最高和最低处，剩下的中间部分是未定义的。

再来说说，内核空间与用户空间的区别：

• 进程在用户态时，只能访问用户空间内存；
• 只有进入内核态后，才可以访问内核空间的内存；

虽然每个进程都各自有独立的虚拟内存，但是每个虚拟内存中的内核地址，其实关联的都是相同的物理内存。这样，进程切换到内核态后，就可以很方便地访问内核空间内存。

接下来，进一步了解虚拟空间的划分情况，用户空间和内核空间划分的方式是不同的，内核空间的分布情况就不多说了。

我们看看用户空间分布的情况，以 32 位系统为例，我画了一张图来表示它们的关系：

通过这张图你可以看到，用户空间内存，从低到高分别是 7 种不同的内存段：

• 程序文件段，包括二进制可执行代码；
• 已初始化数据段，包括静态常量；
• 未初始化数据段，包括未初始化的静态变量；
• 堆段，包括动态分配的内存，从低地址开始向上增长；
• 文件映射段，包括动态库、共享内存等，从低地址开始向上增长（跟硬件和内核版本有关）；
• 栈段，包括局部变量和函数调用的上下文等。栈的大小是固定的，一般是 8 MB。当然系统也提供了参数，以便我们自定义大小；

在这 7 个内存段中，堆和文件映射段的内存是动态分配的。比如说，使用 C 标准库的 malloc()或者 mmap() ，就可以分别在堆和文件映射段动态分配内存。

第四章：线程

单线程与多线程

引入线程后CPU调度进程以进程的线程为单位。

在多线程的模型中，每个线程也有自己的控制块，也会把寄存器内容进行保存，有自己的栈（并不意味着有自己的地址空间/内存空间）。

为什么对于大多数合作性任务，多线程比多个独立的进程更优越呢？这是因为，线程共享相同的内存空间。不同的线程可以存取内存中的同一个变量。所以，程序中的所有线程都可以读或写声明过的全局变量。

如果曾用 fork() 编写过重要代码，就会认识到这个工具的重要性。为什么呢？虽然 fork()允许创建多个进程，但它还会带来以下通信问题: 如何让多个进程相互通信，这里每个进程都有各自独立的内存空间。对这个问题没有一个简单的答案。虽然有许多不同种类的本地 IPC (进程间通信），但它们都遇到两个重要障碍：

• 强加了某种形式的额外内核开销，从而降低性能。

• 对于大多数情形，IPC 不是对于代码的 “自然” 扩展。通常极大地增加了程序的复杂性。

双重坏事: 开销和复杂性都非好事。如果曾经为了支持 IPC 而对程序大动干戈过，那么您就会真正欣赏线程提供的简单共享内存机制。由于所有的线程都驻留在同一内存空间，POSIX 线程无需进行开销大而复杂的长距离调用。只要利用简单的同步机制，程序中所有的线程都可以读取和修改已有的数据结构。而无需将数据经由文件描述符转储或挤入紧窄的共享内存空间。仅此一个原因，就足以让您考虑应该采用单进程/多线程模式而非多进程/单线程模式。

不仅如此，线程同样还是非常快捷的。与标准 fork() 相比，线程带来的开销很小。内核无需单独复制进程的内存空间或文件描述符等等。这就节省了大量的 CPU 时间，使得线程创建比新进程创建快上十到一百倍。因为这一点，可以大量使用线程而无需太过于担心带来的 CPU 或内存不足。使用 fork() 时导致的大量 CPU 占用也不复存在。这表示只要在程序中有意义，通常就可以创建线程。

当然，和进程一样，线程将利用多 CPU。如果软件是针对多处理器系统设计的，这就真的是一大特性（如果软件是开放源码，则最终可能在不少平台上运行）。特定类型线程程序（尤其是 CPU 密集型程序）的性能将随系统中处理器的数目几乎线性地提高。如果正在编写 CPU 非常密集型的程序，则绝对想设法在代码中使用多线程。一旦掌握了线程编码，无需使用繁琐的 IPC 和其它复杂的通信机制，就能够以全新和创造性的方法解决编码难题。所有这些特性配合在一起使得多线程编程更有趣、快速和灵活。

线程概念与实现方式

多线程模型

多对一

一对一

多对多

第四章习题拾遗

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

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

用户级线程切换不需要内核支持（由线程库完成）

第五章：CPU调度

基本概念

CPU/IO burst cycle 理解与图像

进程执行由CPU执行和IO等待周期组成，进程在这两个状态之间切换。

CPU调度程序

何时可能发生调度决策

注意，只是可能发生调度

• Switches from running to waiting state

• Switches from running to ready state

• Switches from waiting to ready

• Terminates

1,4是非抢占式的，也就是说，是由进程自己主动让出CPU使用权。

2,3是抢占式的，由操作系统结束进程对CPU的使用

抢占与非抢占的区别与相应问题

抢占调度对访问共享数据是有代价的。考虑两个进程共享数据的情况。 第一个进程正在更新数据时， 它被抢占以使第二个进程能够运行。第二个进程可能试图读数据，该数据现在处于不一致的状态。这种情况下需要一种新机制来协调对共享数据的访问。

抢占对于操作系统内核的设计也有影响。在处理系统调用时，内核可能忙于进程活动。这些活动可能涉及要改变重要内核数据（如IO队列）。如果个进程在进行这些修改时被抢占，内核（或设备驱动）需要读取或修改同样的结构，肯定会导致混乱。有的操作系统，包括绝大多数 UNIX 系统，通过在上下文切换之前等待系统调用完成或等待发生IO阻塞来处理这一问题。不幸的是，这种内核执行模式对实时计算和多进程的支待较差。 这些问题及其解决方案将在 5.4 和 19.5 节中讨论。

因为根据定义中断能随时发生， 而且不能总是被内核所忽视，所以受中断影响的代码段必须加以保护以避免同时访问。 操作系统需要在任何时候都能接受中断， 否则输入会丢失或输出会被改写。为了这些代码段不被多个进程同时访问，在进入时要禁止中断，而在退出时要重新允许中断。注意到禁止中断代码段发生并不频繁，而且常常只包括很少的指令。

一个问题

进程是否可能在执行系统调用的过程中被抢占？

进程在执行系统调用的过程中不会被抢占。让我们设想进程a正在执行的过程中发生中断，而中断处理程序判断出系统需要被重新调度，它会设置进程a的need_resched标志（need_resched标志的作用参见后面说明），在中断处理程序结束之后（ret_from_intr），系统会检查被中断处理程序中断执行的进程的优先级，如果此时进程a处在用户态，系统会直接激活调度程序完成进程切 换；而如果此时进程a处在内核态，系统会不作调度而恢复进程a的执行，只有进程a完成系统调用之后（ret_from_sys_call），它的 need_resched标志才会被检查，从而完成进程切换。

进程在内核态不会被抢占的特点减少了单CPU系统中内核设计的复杂性，因为不需要考虑不同进程对内核代码和数据结构的竞争。

need_resched 标志位。该位在从中断和系统调用中返回的时候被检查，need_resched为1的时候表示要求启动调度程序，这通常发生在进程的时间片已经用完，或者因为IO事件发生而强行抢占当前进程的时候。

分派程序

分派程序是一个模块，用来将 CPU 的控制交给由短期调度程序选择的进程。 其功能包括：

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

分派程序应尽可能快， 因为在每次进程切换时都要使用。 分派程序停止一个程序而启动另一个进程所花费的时间称为分派延迟。

调度准则与算法

调度准则

准侧有很多，但等待时间为最主要衡量标准。

其余包括CPU使用率，吞吐量，响应时间。

先到先服务（FCFS，First-Come, First-Served ）

先来先服务(FCFS)调度算法是一种最简单的调度算法，该算法既可用于作业调度，也可用于进程调度。

当在作业调度中采用该算法时，每次调度都是从后备作业队列中选择一个或多个最先进入该队列的作业，将它们调入内存，为它们分配资源、创建进程，然后放入就绪队列。

在进程调度中采用FCFS算法时，则每次调度是从就绪队列中选择一个最先进入该队列的进程，为之分配处理机，使之投入运行。

该进程一直运行到完成或发生某事件而阻塞后才放弃处理机。（非抢占式）

出现的问题是如果短时进程排在长时进程后面会导致短时进程等待时间长。甘特图（经常考的图）如下：

最短作业优先调度（SJF）

短作业(进程)优先调度算法，是指对短作业或短进程优先调度的算法。它们可以分别用于作业调度和进程调度。短作业优先(SJF)的调度算法是从后备队列中选择一个或若干个估计运行时间最短的作业，将它们调入内存运行。而短进程优先(SPF)调度算法则是从就绪队列中选出一个估计运行时间最短的进程，将处理机分配给它，使它立即执行并一直执行到完成，或发生某事件而被阻塞放弃处理机时再重新调度。

分为抢占式和非抢占式。

非抢占式SJF

等到进程运行完，再到就绪队列中选取（估计）运行时间最短的进程去运行。

抢占式SJF

某个进程运行时，如果某个进程加到就绪队列，比较新进程运行时间与现在执行进程剩余的运行时间，如果新进程运行时间更短，则优先运行新进程。

甘特图如下：

一个问题

一个进程的运行时长如何确定？显然是无法准确确定的，但我们可以估计。虽然不知道下一个CPU区间的长度，但是可以颈测它。认为下一个CPU区间的长度与以前的相似。因此，通过计算下一个CPU区间长度的近似值，能选择具有最短预测CPU区间的进程来运行。

$\tau_{n+1}=\alpha t_n+(1-\alpha)\alpha t_{n-1}+...+(1-\alpha)^{j}\alpha t_{n-j}+...+(1-\alpha)^{n+1}\tau_0$

$\alpha$和$(1-\alpha)$都小于等于1，那么后面项的权重比前面的项要小。

优缺点

优点是 可以有效降低作业的平均等待时间，提高系统吞吐量。被认为是最佳的算法。

缺点：

• 对长作业不利，周转时间与带权周转时间提升。

• 未考虑作业的紧迫程度。

• 时间长短是估计的，所以不一定会达到真正的短作业调度

SJF调度经常用于长期调度。

优先级调度

为了照顾紧迫型作业，使之在进入系统后便获得优先处理，引入了最高优先权优先(FPF)调度算法。此算法常被用于批处理系统中，作为作业调度算法，也作为多种操作系统中的进程调度算法，还可用于实时系统中。当把该算法用于作业调度时，系统将从后备队列中选择若干个优先权最高的作业装入内存。当用于进程调度时，该算法是把处理机分配给就绪队列中优先权最高的进程。

进程的优先级分为静态优先级和动态优先级：

• 静态优先级：创建进程的时候，就已经确定优先级了，然后整个运行时间优先级都不会变化。
• 动态优先级：根据进程的动态变化调整优先级，如果进程运行时间增加，降低优先级，如果进程等待时间增加，则升高优先级。

进程随等待时间增加升高优先级的过程被称作老化（Aging），其实就是为了避免优先级过低的进程一直得不到执行而被饿死（Starvation）。

非抢占式优先权算法

在这种方式下，系统一旦把处理机分配给就绪队列中优先权最高的进程后，该进程便一直执行下去，直至完成；或因发生某事件使该进程放弃处理机时，系统方可再将处理机重新分配给另一优先权最高的进程。这种调度算法主要用于批处理系统中；也可用于某些对实时性要求不严的实时系统中。

抢占式优先权调度算法

在这种方式下，系统同样是把处理机分配给优先权最高的进程，使之执行。但在其执行期间，只要又出现了另一个其优先权更高的进程，进程调度程序就立即停止当前进程(原优先权最高的进程)的执行，重新将处理机分配给新到的优先权最高的进程。

因此，在采用这种调度算法时，是每当系统中出现一个新的就绪进程i时，就将其优先权Pi与正在执行的进程j的优先权Pj进行比较。如果Pi≤Pj，原进程Pj便继续执行；但如果是Pi>Pj，则立即停止Pj的执行，做进程切换，使i进程投入执行。显然，这种抢占式的优先权调度算法能更好地满足紧迫作业的要求，故而常用于要求比较严格的实时系统中，以及对性能要求较高的批处理和分时系统中。

轮转法调度(RR，Round Robin )

在早期的时间片轮转法中，系统将所有的就绪进程按先来先服务的原则排成一个队列，每次调度时，把CPU分配给队首进程，并令其执行一个时间片。时间片的大小从几ms到几百ms。

当执行的时间片用完时，由一个计时器发出时钟中断请求，调度程序便据此信号来停止该进程的执行，并将它送往就绪队列的末尾；如果该进程在时间片结束之前阻塞或结束，CPU也会立即切换。然后，再把处理机分配给就绪队列中新的队首进程，同时也让它执行一个时间片。这样就可以保证就绪队列中的所有进程在一给定的时间内均能获得一时间片的处理机执行时间。换言之，系统能在给定的时间内响应所有用户的请求。

在该算法中，时间片的长度是一个比较关键的点：

• 如果设置的太短会导致过多的进程上下文切换，降低CPU的效率
• 如果设置的太长有可能会导致短作业的响应时间变长（就变成了FCFS）

一般来说，时间片的设置应为略大于一次交互的响应时间，20ms~50ms是一个折中的值。

多级队列

将就绪队列划分成多个队列，不同队列采用不同的调度方式。同时队列之间也存在优先级，或者给队列划分时间片，高优先级的队列有更多时间片。

多级反馈队列

前面介绍的各种用作进程调度的算法都有一定的局限性。如短进程优先的调度算法，仅照顾了短进程而忽略了长进程，而且如果并未指明进程的长度，则短进程优先和基于进程长度的抢占式调度算法都将无法使用。而多级反馈队列调度算法则不必事先知道各种进程所需的执行时间，而且还可以满足各种类型进程的需要，因而它是目前被公认的一种较好的进程调度算法。

在采用多级反馈队列调度算法的系统中，调度算法的实施过程如下所述：

1）应设置多个就绪队列，并为各个队列赋予不同的优先级。第一个队列的优先级最高，第二个队列次之，其余各队列的优先权逐个降低。该算法赋予各个队列中进程执行时间片的大小也各不相同，在优先权愈高的队列中，为每个进程所规定的执行时间片就愈小。例如，第二个队列的时间片要比第一个队列的时间片长一倍，第i+1个队列的时间片要比第i个队列的时间片长一倍。

2）当一个新进程进入内存后，首先将它放入第一队列的末尾，按FCFS原则排队等待调度。当轮到该进程执行时，如它能在该时间片内完成，便可准备撤离系统；如果它在一个时间片结束时尚未完成，调度程序便将该进程转入第二队列的末尾，再同样地按FCFS原则等待调度执行；如果它在第二队列中运行一个时间片后仍未完成，再依次将它放入第三队列，……，如此下去，当一个长作业(进程)从第一队列依次降到第n队列后，在第n队列便采取按时间片轮转的方式运行。

3）仅当第一队列空闲时，调度程序才调度第二队列中的进程运行；仅当第1～(i-1)队列均空时，才会调度第i队列中的进程运行。如果处理机正在第i队列中为某进程服务时，又有新进程进入优先权较高的队列(第1～(i-1)中的任何一个队列)，则此时新进程将抢占正在运行进程的处理机，即第i队列中某个正在运行的进程的时间片用完后，由调度程序选择优先权较高的队列中的那一个进程，把处理机分配给它。

这种算法对于短作业来说很可能就在第一级队列就被处理完成，对于长作业来说，虽然有可能因为在第一级队列无法执行完成而被被移入到第二级队列运行（等待时间变长），但是获得时间片也会变长（运行时间变长），所以该算法很好的兼顾了长短作业，同时有较好的响应时间。

Unix、Linux与Windows进程调度策略

Linux 从整体上区分实时进程和普通进程，因为实时进程和普通进程度调度是不同的，它们两者之间，实时进程应该先于普通进程而运行，然后，对于同一类型的不同进程，采用不同的标准来选择进程。对普通进程的调度策略是动态优先调度，对于实时进程采用了两种调度策略，FIFO(先来先服务调度)和RR（时间片轮转调度）。

UNIX系统是单纯的分时系统，所以没有设置作业调度。UNIX系统的进程调度采用的算法是，多级反馈队列调度法。其核心思想是先从最高休先级就绪队列中取出排在队列最前面的进程，当进程执行完一个时间片仍未完成则剥夺它的执行，将它放入到相应的队列中，取出下一个就绪进程投入运行，对于同一个队列中的各个进程，按照时间片轮转法调度。多级反馈队列调度算法即能使高优先级的作业得到响应又能使短作业（进程）迅速完成。但是它还是存在某些方面的不足，当不断有新进程到来时，则长进程可能饥饿。

Windows 系统其调度方式比较复杂，它的处理器调度的调度单位是线程而不是进程，是基于优先级的抢占式多处理器调度，依据优先级和分配时间片来调度。而且Windows 2000/XP在单处理器系统和多处理器系统中的线程调度是不同的线程调度机制，Windows操作系统的调度系统总是运行优先级最高的就绪线程。在同一优先级的各线程按时间片轮转算法进行调度。如果一个高优先级的线程进入就绪状态，当前运行的线程可能在用完它的时间片之前就被抢占处理机。

多任务、有线程优先级、多种中断级别这是现代操作系统的共同特点。实时操作系统（Real-time operating system, RTOS）最大的特点是对响应时间有严格的要求，linux尚且不能称为完全的实时操作系统，USA的宇宙飞船常用的操作系统是VxWorks，这才是闻名于世的RTOS。

第五章习题拾遗

• 哪个调度算法是绝对可抢占的？

  • 时间片流转算法
  • 在时间片用完或进程执行完后被其他进程抢占
  • 更详细地说并不算一种抢占而是一种调度（其实对于RR二者并无差别）
  • 那么相对应的，RR一定不会出现饿死。

• 计算(2)问，答案为D：

• 计算，答案为C

首先P1和P2依次进入Q1，执行P110ms后中断P1将其调入Q2，此时Q1非空，继续调度Q1中的进程，即执行P2进程10ms，同样没有执行完，调入Q2，此时Q1为空，开始调度执行Q2的进程，由于P2剩余时间少于P1，先调度执行进程P2，执行完后将P1执行完。

上下文切换

我们都知道，Linux 是一个多任务操作系统，它支持远大于 CPU 数量的任务同时运行。当然，这些任务实际上并不是真的在同时运行，而是因为系统在很短的时间内，将 CPU 轮流分配给它们，造成多任务同时运行的错觉。

而在每个任务运行前，CPU 都需要知道任务从哪里加载、又从哪里开始运行，也就是说，需要系统事先帮它设置好CPU 寄存器和程序计数器

基本概念

什么是 CPU 上下文

CPU 寄存器和程序计数器就是 CPU 上下文，因为它们都是 CPU 在运行任何任务前，必须的依赖环境。

• CPU 寄存器是 CPU 内置的容量小、但速度极快的内存。
• 程序计数器则是用来存储 CPU 正在执行的指令位置、或者即将执行的下一条指令位置。

什么是 CPU 上下文切换

就是先把前一个任务的 CPU 上下文（也就是 CPU 寄存器和程序计数器）保存起来，然后加载新任务的上下文到这些寄存器和程序计数器，最后再跳转到程序计数器所指的新位置，运行新任务。

而这些保存下来的上下文，会存储在系统内核中，并在任务重新调度执行时再次加载进来。这样就能保证任务原来的状态不受影响，让任务看起来还是连续运行。

根据任务的不同，可以分为以下几种类型

• 系统调用上下文切换
• 进程上下文切换
• 线程上下文切换
• 中断上下文切换

系统调用的上下文切换

Linux 按照特权等级，把进程的运行空间分为内核空间和用户空间，分别对应着下图中， CPU 特权等级的 Ring 0 和 Ring 3。

• 内核空间（Ring 0）具有最高权限，可以直接访问所有资源；
• 用户空间（Ring 3）只能访问受限资源，不能直接访问内存等硬件设备，必须通过系统调用陷入到内核中，才能访问这些特权资源。

进程既可以在用户空间运行，又可以在内核空间中运行。进程在用户空间运行时，被称为进程的用户态，而陷入内核空间的时候，被称为进程的内核态。

从用户态到内核态的转变，需要通过系统调用来完成。比如，当我们查看文件内容时，就需要多次系统调用来完成：首先调用 open() 打开文件，然后调用 read() 读取文件内容，并调用 write() 将内容写到标准输出，最后再调用 close() 关闭文件。

在这个过程中就发生了 CPU 上下文切换，整个过程是这样的：

• 保存 CPU 寄存器里原来用户态的指令位
• 为了执行内核态代码，CPU 寄存器需要更新为内核态指令的新位置。
• 跳转到内核态运行内核任务。
• 当系统调用结束后，CPU 寄存器需要恢复原来保存的用户态，然后再切换到用户空间，继续运行进程。

所以，一次系统调用的过程，其实是发生了两次 CPU 上下文切换。（用户态-内核态-用户态）

不过，需要注意的是，系统调用过程中，并不会涉及到虚拟内存等进程用户态的资源，也不会切换进程。这跟我们通常所说的进程上下文切换是不一样的：进程上下文切换，是指从一个进程切换到另一个进程运行；而系统调用过程中一直是同一个进程在运行。

所以，系统调用过程通常称为特权模式切换，而不是上下文切换。系统调用属于同进程内的 CPU 上下文切换。但实际上，系统调用过程中，CPU 的上下文切换还是无法避免的。

进程上下文切换

首先，进程是由内核来管理和调度的，进程的切换只能发生在内核态。所以，进程的上下文不仅包括了虚拟内存、栈、全局变量等用户空间的资源，还包括了内核堆栈、寄存器等内核空间的状态。

因此，进程的上下文切换就比系统调用时多了一步：在保存内核态资源（当前进程的内核状态和 CPU 寄存器）之前，需要先把该进程的用户态资源（虚拟内存、栈等）保存下来；而加载了下一进程的内核态后，还需要刷新进程的虚拟内存和用户栈。

另外，我们知道，现代操作系统通过 TLB（Translation Lookaside Buffer）来管理虚拟内存到物理内存的映射关系。如果发生运行时动态链接（进入系统态）、内存紧缩等情况，即虚拟内存更新后，TLB 也需要刷新，内存的访问也会随之变慢，不过这是进程上下文切换带来的副作用了。

发生进程上下文切换的场景

• 基于时间片的操作系统，CPU 时间被划分为一段段的时间片，这些时间片再被轮流分配给各个进程。这样，当某个进程的时间片耗尽了，就会被系统挂起，切换到其它正在等待 CPU 的进程运行。

• 进程在系统资源不足（比如内存不足）时，要等到资源满足后才可以运行，这个时候进程也会被挂起，并由系统调度其他进程运行。

• 当进程通过睡眠函数 sleep 这样的方法将自己主动挂起时，自然也会重新调度。

• 当有优先级更高的进程运行时，为了保证高优先级进程的运行，当前进程会被挂起，由高优先级进程来运行

• 发生硬件中断时，CPU 上的进程会被中断挂起，转而执行内核中的中断服务程序。

进程上下文切换潜在的性能问题

根据 Tsuna 的测试报告，每次上下文切换都需要几十纳秒到数微秒的 CPU 时间。这个时间还是相当可观的，特别是在进程上下文切换次数较多的情况下，很容易导致 CPU 将大量时间耗费在寄存器、内核栈以及虚拟内存等资源的保存和恢复上，进而大大缩短了真正运行进程的时间。这也正是导致平均负载升高的一个重要因素。

另外，我们知道， Linux 通过 TLB（Translation Lookaside Buffer）来管理虚拟内存到物理内存的映射关系。当虚拟内存更新后，TLB 也需要刷新，内存的访问也会随之变慢。特别是在多处理器系统上，缓存是被多个处理器共享的，刷新缓存不仅会影响当前处理器的进程，还会影响共享缓存的其他处理器的进程。

线程上下文切换

线程与进程最大的区别在于：线程是调度的基本单位，而进程则是资源拥有的基本单位。说白了，所谓内核中的任务调度，实际上的调度对象是线程；而进程只是给线程提供了虚拟内存、全局变量等资源。

所以，对于线程和进程，我们可以这么理解： - 当进程只有一个线程时，可以认为进程就等于线程。 - 当进程拥有多个线程时，这些线程会共享相同的虚拟内存和全局变量等资源。这些资源在上下文切换时是不需要修改的。 - 另外，线程也有自己的私有数据，比如栈和寄存器等，这些在上下文切换时也是需要保存的。

发生线程上下文切换的场景

• 前后两个线程属于不同进程。此时，因为资源不共享，所以切换过程就跟进程上下文切换是一样。此时切换线程，CPU 的各种寄存器都要重新刷一遍，从这个角度而言，你可以把进程和线程当作一种东西，只是共享度不同，其他没区别的。

• 前后两个线程属于同一个进程。此时，因为虚拟内存是共享的，所以在切换时，虚拟内存这些资源就保持不动，只需要切换线程的私有数据、寄存器等不共享的数据

虽然同为上下文切换，但同进程内的线程切换，要比多进程间的切换消耗更少的资源，这也正是多线程代替多进程的一个优势。

中断上下文切换

为了快速响应硬件的事件，中断处理会打断进程的正常调度和执行，转而调用中断处理程序，响应设备事件。而在打断其他进程时，就需要将进程当前的状态保存下来，这样在中断结束后，进程仍然可以从原来的状态恢复运行。

中断处理程序运行于内核态。中断发生时CPU可能处于内核态（如执行系统调用的过程中）也可能处于用户态（执行应用空间代码）。所以前者不涉及特权级转换，后者涉及。

不涉及特权级转换的情况：

• 压入寄存器现场、错误代码等
• 执行中断处理程序
• 恢复寄存器现场

可以看到这里并没有发生堆栈的切换——因为本来就运行在内核栈上嘛！中断处理程序借用了应用程序的内核栈。说『借用』是因为进程的内核栈是给进程执行内核空间代码使用的（通常就是系统调用），由于中断并不一定和正在运行的进程有什么关联。

但是对于后者，也就是用户态中被中断，有一个用户 -> 内核 -> 用户的切换过程，伴随着相关栈的切换。具体过程：

• 找到内核栈
• 压入寄存器现场、错误代码
• 转入中断处理程序
• 恢复第二步保存的现场
• 切换换回用户栈

为了快速响应硬件的事件，中断处理会打断进程的正常调度和执行，转而调用中断处理程序，响应设备事件，如断电和设备损坏等。而在打断其他进程时，就需要将进程当前的状态保存下来，这样在中断结束后，进程仍然可以从原来的状态恢复运行。

跟进程上下文不同，中断上下文切换并不涉及到进程的用户态。所以，即便中断过程打断了一个正处在用户态的进程，也不需要保存和恢复这个进程的虚拟内存、全局变量等用户态资源。中断上下文，其实只包括内核态中断服务程序执行所必需的状态，包括 CPU 寄存器、内核堆栈、硬件中断参数等。

对同一个 CPU 来说，中断处理比进程拥有更高的优先级，所以中断上下文切换并不会与进程上下文切换同时发生。同样道理，由于中断会打断正常进程的调度和执行，所以大部分中断处理程序都短小精悍，以便尽可能快的执行结束。

另外，跟进程上下文切换一样，中断上下文切换也需要消耗 CPU，切换次数过多也会耗费大量的 CPU，甚至严重降低系统的整体性能。所以，当你发现中断次数过多时，就需要注意去排查它是否会给你的系统带来严重的性能问题。

一些讨论

• CPU 上下文切换，是保证现代系统正常工作的核心功能之一，一般情况下不需要我们特别关注。根据 Tsuna 的测试报告，每次上下文切换都需要几十纳秒到数微秒的 CPU 时间。这个时间还是相当可观的，特别是在进程上下文切换次数较多的情况下，会把 CPU 时间消耗在寄存器、内核栈以及虚拟内存等数据的保存和恢复上，从而缩短进程真正运行的时间，导致系统的整体性能大幅下降。
• CPU 执行的最小逻辑单元是线程，并不是一个 CPU 核心。所以切换进程，只是切换一个进程里的一个线程到另一个进程里的一个线程，说白了还是线程切换。如果对比的是单个进程和进程内线程的切换，线程共享资源，cache命中率会高很多；进程切换，不共享资源，cache命中率低。
• 上下文切换说的是 CPU 寄存器的切换，跟 cache 和内存没啥关系，后者只是上下文切换带来的副作用。也许你会有疑问，当切换到新的进程，进程所需的资源不在内存里，这不就开始调度了，调度的开销呢？但实际是，新建进程不会分配 CPU，进程就绪后等等待分配处理器，此时资源已经进内存了。
• 切换进程可能要刷 TLB，进程内线程切换不需要。进程切换要切页表，所以可能同时要刷 TLB，这个根据实现定。

第六章：进程同步

问题引入

生产 - 消费模型，用count记录当前产品数量，生产一件则count加一，消费一件则减一，生产与消费同时进行，那么在改变count时就会出现如下问题。

这就出现了由于CPU调度导致的数据问题。那么我们将讨论如何解决这个问题。也就是说，保证操作的原子性。换言之，保证生产与消费的进程同步（同步指两个或两个以上随时间变化的量在变化过程中保持一定的相对关系），即两个进程不会同时访问共享变量（也就是互斥）

问题解决：临界区问题

临界区 (Critical Sections) 是访问共享数据的代码，生产者消费者代码中的count++\count--就是临界区。

考虑一个由n个进程$\{P _0 , P_1 ,..., P_{n−1} \}$ 组成的系统。每个进程都有一段称为临界区（critical section）的代码，进程会在其中更改公共变量、更新表、编写文件等等。该系统的重要特性是，当一个进程在其临界区执行时，不允许其他进程在其临界区执行。也就是说，没有两个进程可以同时在它们的临界区执行。临界区问题（critical-section problem）是设计一个进程可以用来进行协作的协议。每个进程必须请求允许进入其临界区。实现此请求的代码段是入口区（entry section）。临界区（critical section）之后则是出口区（exit section）。其余的代码是剩余区（remainder section）。入口区和出口区被封闭在方框中，以突出这些重要的代码段。如图。

临界区问题的解决方案必须满足以下三个要求:

1. 互斥锁（Mutual exclusion）：如果进程P在它的临界区执行，那么没有其他进程可以在它们的临界区没中执行。

2. 空闲让进/前进（Progress）：如果一个进程正在它的临界区中执行，并且有很多其他的进程也希望进入他们的临界区。然后，只有那些没有在其剩余区中执行的进程才能参与决定哪一个将进入它的临界区，而这个选择不能被无限期延迟。

   即，没有进程处于临界区时，可允许一个请求进入临界区的进程立即进入。

3. 有限等待（Bounded waiting）：在一个进程发出请求进入其临界区并在该请求被确认之前，其他进程被允许进入其临界区的次数有一个范围或限制。

我们假设每个进程都以非零的速度执行。然而，我们不能对n个进程的相对速度做任何假设。

在一个给定的时间点上，可能会有许多内核模式的进程在操作系统中处于活动状态。因此，实现操作系统(内核代码)的代码会受到多个可能的竞态条件（race condition）的影响。以一个内核数据结构为例，它维护系统中所有打开的文件的列表。当打开或关闭新文件时，必须修改此列表(将文件添加到列表中或将其从列表中删除)。如果两个进程同时打开文件，则该列表的单独更新可能导致竞态条件。其他可能出现竞态条件的内核数据结构包括维护内存分配、维护进程列表和中断处理的结构。这取决于内核开发人员，以确保操作系统不受这种竞争条件的影响。

有两种通用方法用于处理操作系统中的临界区：抢占式内核（preemptive kernels）和非抢占式内核（nonpreemptive kernels）。抢占式内核允许进程在内核模式运行时被抢占。非抢占内核不允许在内核模式中运行的进程被抢占;内核模式下，进程将一直运行，直到它退出内核模式、阻塞或自愿让出CPU控制。

显然，一个非抢占式的内核基本上不受内核数据结构的竞争条件的影响，因为只有一个进程在内核中处于活动状态。但是对于抢占内核，则是不同的，所以必须仔细设计，以确保共享的内核数据不受竞态条件的影响。对于SMP（“对称多处理”（Symmetrical Multi-Processing））架构来说，抢占式内核尤其困难，因为在这些环境中，两个内核模式进程可以同时在不同的处理器上运行。

那么，为什么有人会赞成抢占式内核而不是非抢占式内核呢？抢占式内核会更有响应性，因为在将处理器交付给其他waiting状态的进程之前，内核模式下的进程运行任意周期长的的风险更小[注：这是原文翻译，意思就是在处理器叫控制权交给下一个进程之前，当前内核模式运行的进程一般不会占用很久]。(当然，通过设计不以这种方式运行的内核代码，这种风险也可以最小化。)此外，抢占式内核更适合于实时编程，因为它将允许实时进程抢占当前内核中正在运行的进程。

Peterson算法

Peterson 算法完美地用软件实现了双线程互斥问题。

算法使用两个控制变量flag与turn。 其中flag[n]的值为真，表示ID号为n的进程希望进入该临界区.。变量turn保存有权访问共享资源的进程的ID号.

//flag[] is boolean array; and turn is an integer 
flag[i] = false; 
flag[j] = false; 
int turn;

Pi: flag[i] = true;
    turn = j;
    while (flag[j] == true && turn == j)
    {
        // busy wait
    }
    // critical section
    ...
    // end of critical section
    flag[i] = false;

Pj: flag[j] = true;
    turn = i;
    while (flag[i] == true && turn == i)
    {
        // busy wait
    }
    // critical section
    ...
    // end of critical section
    flag[j] = false;

我们现在证明这个算法是正确的。我们需要证明:

• 互斥锁（Mutual exclusion）

• 空闲让进/前进（Progress）

• 有限等待（Bounded waiting）

---

证明1：

Pi进程只有在flag[j] == false或者turn == i时候才会进入临界区。

如果两个进程同时在其临界区内执行，那么flag[0] = flag[1] = true 。

但是turn的值只能是i或者j,所以Pi和Pj同一时间不能成功地执行它们的while语句。因此只能有一个进程（如Pj）能成功的执行完while语句，而另一个进程（Pi）则至少必须执行一个附加的语句(turn = j)。

而且，由于只要Pj在其临界区内，flag[j] = true和turn = j就会同时成立。

互斥成立

---

证明2：

只要flag[j] = true && turn = j成立，进程Pi陷入while循环语句。

如果Pj不准备进入临界区，那么flag[j] = false，Pi就可以进入临界区。

如果Pj已经设置flag[j] = true，且也在其while语句中执行，那么turn = j 或者turn = i。如果turn = i，那么Pi进入临界区；如果turn = j，那么Pj进入临界区。然而当Pj退出临界区，它会设置flag[j] = false，以允许Pi进入其临界区

如果Pj重新设置flag[j] = true，那么它也必须设置turn为i。

因此由于进程Pi执行while语句时并不改变turn的值，所以Pi会进入临界区（证明2成立），并且Pi最多在Pj进入临界区一次后就能进入（证明3成立）。

硬件同步

硬件支持进程同步的方法：

• 单处理器：关中断
• 多处理器：利用原子指令（不会被打断）

利用原子指令进行进程同步

TestAndSet

返回target的值并将其设置为true

boolean TestAndSet (boolean *target)
{
   boolean rv = *target;
   *target = TRUE;
   return rv:
}

使用一个初始化为false的布尔值lock，代码如下：

while (true) {
   while (TestAndSet (&lock)){
   }  // do nothing
    
      //critical section
      lock = FALSE;
      //remainder section 
}

第一个进程由于lock为false，将lock置为true后直接进入临界区。第二个进程尝试进入临界区时会在while循环内等待，第一个进程执行完临界区后lock为false，第二个进程进入临界区，由此实现互斥锁。

Swap

void Swap (boolean *a, boolean *b)
{
    boolean temp = *a;
    *a = *b;
    *b = temp:
}

while (true)  {
     key = TRUE;
     while ( key == TRUE)
       Swap (&lock, &key);
    
     //critical section
     lock = FALSE;
     //remainder section 
}               

同样地，lock初始化为false，第一个进程会将lock置为true，key置为false，然后跳出循环执行临界区代码。这里要注意，lock是共享变量，key则是每个进程的变量，也就是说，只有一个lock，但每个进程都有一个key。第二个进程进入while循环后，两个变量都是true，会一直执行循环。第一个进程执行完临界区后，lock变为false，此时第二个进程完成变量互换后执行临界区。

存在的问题

我们需要在代码中嵌入硬件指令。解决方案：信号量（semaphore）

信号量（semaphore）

信号量核心：一个用于控制的整型变量。

两个基础操作（PV操作）（原子操作）：P：wait()，V：signal()

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

signal (S) { S++; }

运作方式：

• 初始化，给与它一个非负数的整数值。

• 执行P（wait(S)），信号标S的值将被减少。企图进入临界区段的进程，需要先执行P（wait(S)）。当信号标S减为负值时，进程会被挡住，不能继续；当信号标S不为负值时，进程可以获准进入临界区段。

• 执行V（signal(S)），信号标S的值会被增加。结束离开临界区段的进程，将会执行V（signal(S)）。当信号标S不为负值时，先前被挡住的其他进程，将可获准进入临界区段。

• 每执行一次P操作，意味着请求的进程分配到一个资源；每执行一次V操作，意味着进程释放了一个资源。

特别的，如二元信号量（互斥锁）：信号量只能是0或1。

一般的，使用计数信号量：

• 初始值一般是资源的数量。

• 当S>0时，S值的大小表示某类可用资源的数量，即表示有该类资源可以分配。

• 当S<0时，表示没有可分配的资源数量，其S的绝对值表示排在S信号量的等待队列中进程的数目（等待的进程数）。

使用PV操作注意事项：

• 每个程序中用户实现互斥的P、V操作必须成对出现，先做P操作，进临界区，后做V操作，出临界区。若有多个分支，要认真检查其成对性。

• P、V操作应分别紧靠临界区的头尾部，临界区的代码应尽可能短，不能有死循环。

问题

忙等

如果一个进程占用资源时间较长而不释放锁，导致其他进程一直等待获取该资源并在执行时只能执行空循环（被分配到CPU时）造成处理器资源浪费。

解决方式：阻塞与唤醒。每个信号量对应一个阻塞队列，当发现某进程无法进入临界区，就将其放入阻塞队列而不分配CPU，等待允许进入临界区时由调度程序进行唤醒。

//Implementation of wait:
                      wait (S){ 
	                        value- -;
	                        if (value < 0) { 
			          add this process to waiting queue
			          block();  
                                    }
                       }
//Implementation of signal:
                      signal (S){ 
	                           value++;
	                            if (value <= 0) { 
			              remove a process P from the waiting queue
			              wakeup(P);  
                                }
                      }

共享变量问题

不同进程共享信号量S这个变量，则对S的操作又形成了临界区。

单处理器就可以通过关中断或者硬件指令。多处理机环境中情况有所不同，例如test_and­_set指令包括“取”、“送”两个机器周期，两个CPU执行test_and_set(lock)可能发生指令周期上的交叉，假如lock初始为0, CPU1和CPU2可能分别执行完前一个机器周期并通过检测(均为0)，然后分别执行后一个机器周期将lock设置为1，结果都取回0作为判断临界区空闲的依据，从而不能实现互斥。

为在多CPU环境中利用test_and_set指令实现进程互斥，硬件需要提供进一步的支持，以保证test_and_set指令执行的原子性. 这种支持目前多以“锁总线”(bus locking)的形式提供的，由于test_and_set指令对内存的两次操作都需要经过总线，在执行test_and_set指令之前锁住总线，在执行test_and_set指令后开放总线，即可保证test­_and_set指令执行的原子性，用法如下：

算法4-6：多处理机互斥算法（自旋锁算法）

do{
  b=1;
  while(b){ 
      lock(bus);
      b = test_and_set(&lock);
      unlock(bus);
  } 
//临界区 
  lock = 0;
//其余部分
}while(1)

死锁（Deadlock）与饿死（Starvation）

信号量很容易出现死锁

经典问题

生产者消费者问题

假定生产者和消费者之间的公用缓冲池有n个缓冲区，生产者可以向缓冲区生产一个产品，消费者可以从缓冲区消耗一个产品，注意：生产者不能同时生产，消费者也不能同时消费，也不能同时生产和消费，当缓冲区空时无法消费，当缓冲区满时无法生产。

互斥锁 mutex，计数信号量full、empty

semaphore mutex = 1;  //实现生产与消费、生产与生产、消费与消费,
semaphore full = 0, empty = n;  //full表示已用缓冲区数，empty表示空缓冲区数
void producer() {
	while(1) {
		wait(empty);  //每次生产会减少一个空缓冲区，如果没有空缓存区了就阻塞
	    wait(mutex);  //保证互斥
	    //生产一个产品;
	    signal(mutex);  //保证互斥
	    signal(full);  //每次生产增加一个已用缓冲区
	}
}
void consumer() {
	while(1) {
		wait(full);  //每次消费会减少一个已用缓冲区，如果没有已用缓存区了就阻塞
	    wait(mutex);
	    //消耗一个产品;
	    signal(mutex);
	    signal(empty);  //每次生产增加一个空缓冲区
	}
}

读者写者问题

假设一个文件可被多个进程共享，我们允许多个进程同时读这个共享对象，但是不允许一个进程写这个共享对象的同时，别的进程进行读或写。换句话说：读和读不互斥，读和写互斥，写和写互斥。

semaphore rmutex, wmutex = 1; //wmutex用以实现写进程与其它进程的互斥
int readcount = 0;  //记录读进程的数量
void reader() {
	while(1) {
		wait(rmutex);  //见下文解释
		if(readcount == 0) wait(wmutex);  //第一个读进程去把写进程上锁
		readcount++;  
		signal(rmutex);  //见下文解释
		//读者读;
		wait(rmutex);  //见下文解释
		readcount--;
		if(readcount == 0) signal(wmutex);  //解锁
		signal(rmutex);  //见下文解释
	}
}
void writer() {
	while(1) {
		wait(wmutex);  //实现写进程与其他进程都互斥
		//写者写;
		signal(wmutex);
	}
}

这个问题的程序中有个关键点，就是明明读进程是不互斥的，为什么还需要rmutex来实现if判断的互斥呢。原因如下：当我们在进程互斥中使用条件语句和数值变化的时候，如果不把那一段也实现互斥的话，很有可能出问题，比如在这段代码中，要是不加第5行和第8行的话：如果一个读进程执行完了第6行，还没有执行第7行的readcount++操作之前，这个读进程被剥夺了处理机，换另一个读进程上处理机运行了，那么另一个读进程就会阻塞在第6行的wait操作上，就无法实现多个读者一起读了(因为此时wmutex这个互斥锁已经加锁了，不能再进行wait）；10行和13行同理，如果一个读进程执行完了第11行就被剥夺处理机，换上另一个读进程也执行了11行，这样readcount被连减两次，那么这两个进程都能通过12行的if判断，会执行两次signal操作，产生错误。

哲学家进餐问题

五个哲学家共用一张圆桌，分别坐在周围的五张椅子上，在桌子上有五只碗和五只筷子，他们的生活方式是交替地进行思考和进餐。平时，一个哲学家进行思考，饥饿时便试图取用其左右最靠近他的筷子，只有在他拿到两只筷子时才能进餐。进餐毕，放下筷子继续思考。

这是一个讲解死锁的时候的经典例子，解决这道题的直接思路如下：

semaphore chopstick[5] = {1,1,1,1,1};
void philosopher() {
	while(1) {
	/*当哲学家饥饿时，总是先拿左边的筷子，再拿右边的筷子*/
	wait(chopstick[i]);
	wait(chopstick[(i+1)%5]);
	//吃饭;
	signal(chopstick[i]);
	signal(chopstick[(i+1)%5]);
	}
}

但是这样可能会出现死锁问题：如果所有哲学家都拿起了左手边筷子，五个进程就会死锁。对于避免哲学家进餐问题发生死锁的方法有很多，这里讲一种：只有当同时一个哲学家能同时拿起左右两只筷子时，才允许拿筷子，解法如下：

semaphore chopstick[5] = {1,1,1,1,1};
semaphore mutex = 1;
void philosopher() {
	while(1) {
		wait(mutex);
        wait(chopstick[i]);
		wait(chopstick[(i+1)%5]);
		signal(mutex);
		//吃饭;
		signal(chopstick[i]);
		signal(chopstick[(i+1)%5]);
	}
}

但仅仅这样做还是有问题，如果一个哲学家获得了两只筷子，开始进餐，此时他左边或者右边的哲学家进入了临界区后，被阻塞在第6行或者第7行，那么其他的哲学家就无法进入临界区了，也就是说这个时间只能有一个哲学家进餐，但显然同一时间是可以有不相邻的两个哲学家同时进餐的。

另一种解法：对编号偶数哲学家来说先取左边的筷子，而对于编号奇数哲学家来说先取右边的筷子，这样也会避免死锁。

semaphore chopstick[5] = {1, 1, 1, 1, 1};	// 筷子的互斥信号量
 
// 哲学家i进程
P_Philosopher_i(){
    while(1){        
        if(i%2 == 0){    // 编号为偶数哲学家
	    P(chopstick[i]);          // 取左边筷子的互斥性
	    P(chopstick[(i+1)%5]);    // 取右边筷子的互斥性
        }
        else{        // 编号为奇数哲学家
            P(chopstick[(i+1)%5]);    // 取右边边筷子的互斥性
	    P(chopstick[i]);          // 取左边筷子的互斥性
        }
 
        //吃饭;
 
	V(chopstick[i]);
	V(chopstick[(i+1)%5]);
	
        //思考;
    }
}

另外：对哲学家同时进餐的进程加以限制，可以让最大4个哲学家进程同时拿去筷子。

semaphore chopstick[5] = {1, 1, 1, 1, 1};	// 筷子的互斥信号量
semaphore mutex = 4;    // 哲学家同时进餐互斥量
 
// 哲学家i进程
P_Philosopher_i(){
    while(1){
        P(mutex);    // 保证最多4个哲学家同时取筷子
	P(chopstick[i]);          // 取左边筷子的互斥性
	P(chopstick[(i+1)%5]);    // 取右边筷子的互斥性
        V(mutex);
 
        //吃饭;
 
	V(chopstick[i]);
	V(chopstick[(i+1)%5]);
	
        //思考;
    }
}

其他问题

狒狒过桥问题

一个主修人类学、辅修计算机科学的学生参加了一个课题，调查非洲狒狒是否能被教会理解死锁。他找到一处很深的峡谷，在上边固定了一根横跨峡谷的绳索，这样狒狒就可以攀住绳索越过峡谷。同一时刻可以有几只狒狒通过，只要它们朝着相同的方向。但如果向东和向西的狒狒同时攀在绳索上则将发生死锁（狒狒将被卡在中间），因为它们无法在吊在峡谷上时从另一只的背上翻过去。如果一只狒狒想越过峡谷，它必须看当前是否有别的狒狒正在逆向通过。使用信号量写一个避免死锁的程序来解决该问题。
解法如下：

semaphore wmutex, emutex, mutex = 1; 
int wcount, ecount = 0;  //分别记录东西狒狒上绳索的个数
void west_monkey {
	while(1) {
		wait(wmutex);  //使if语句互斥
		if(wcount == 0) wait(mutex);  //第一个西狒狒给东狒狒上锁
		wcount++;
		signal(wmutex);  //使if语句互斥
		//西狒狒过桥；
		wait(wmutex);
		wcount--;
		if(wcount == 0) signal(mutex);
		signal(wmutex);
	}
}
void east_monkey {  //和上面的一样
	while(1) {
		wait(emutex);
		if(ecount == 0) wait(mutex);
		ecount++;
		signal(emutex);
		//东狒狒过桥；
		wait(emutex);
		ecount--;
		if(ecount == 0) signal(mutex);
		signal(emutex);
	}
}

该问题属于读者写者问题的改进，如果完全理解了读者写者问题的解法，那么这个问题也能很快解决。东狒狒之间不互斥，西狒狒之间不互斥，东西狒狒之间互斥，思路是第一个东狒狒给西狒狒上锁，第一个西狒狒给东狒狒上锁，注意if判断也要实现互斥。

理发师理发问题

理发店里有一位理发师、一把理发椅和n把供等候理发的顾客坐的椅子。如果没有顾客，则理发师便在理发椅上睡觉。当一个顾客到来时，他必须先叫醒理发师，如果理发师正在理发时又有顾客来到，则如果有空椅子可坐，他们就坐下来等。如果没有空椅子，他就离开。这里的问题是为理发师和顾客各编写一段程序来描述他们的行为，要求不能带有竞争条件。
解法如下：

semaphore customer, barber = 0;  //一开始没有顾客，理发师也是睡着的
semaphore mutex = 1;  //互斥信号量
int empty = N;  //空椅子数量为N
void Barber() {
	while(1) {
		wait(customer);  //只有顾客进程的V执行后才能执行，没有顾客就阻塞（睡觉）
		wait(mutex);  //把数量的变化实现互斥，以免影响到顾客进程的if判断语句
		empty++;  //椅子上的顾客起身
		signal(barber);  //有了一个理发师可以理发
		signal(mutex);
		//理发;
	}
}
void Customer() {
	wait(mutex);
	if(empty > 0) {
		empty--;  //不管是不是第一个顾客，来了先得坐凳子上，因为理发师在理发椅上睡觉呢
		signal(customer);  //增加一个顾客，唤醒沉睡的理发师
		signal(mutex); 
		wait(barber);  //消耗一个理发师，没有理发师就阻塞
		//理发;
	} else {
		signal(mutex);
		//离开;
	}
}

这道题本身不难，但其中很多细节的实现需要实现，比如座位是有上限的，这样就不得不设置判断条件和计数，来使超过N个的顾客离开，而加入计数和判断条件后就又要实现其互斥，增加了问题的复杂性。

其他一些题https://zhuanlan.zhihu.com/p/61326272

管程(monitor)

所谓管程，指的是管理共享变量以及对共享变量的操作过程，让他们支持并发。翻译为 Java 的语言，就是管理类的成员变量和成员方法，让这个类是线程安全的。

可以有多个进程处于管程之中，但同一时间只能有一个处于活跃（active）状态。（这其实实现了最基本的互斥）

（管程如何实现有限等待？）

条件变量(Condition Variable)

注意条件变量的wait()和signal()与信号量之间进行区分，二者并不相同！

• 管程内部可定义 condition 类型的变量以提供同步机制，称其为条件变量。条件变量可执行操作 wait() 和 signal()。
• 条件变量相当于一个阻塞队列，一般来说条件变量对应一个进程运行时所必须的条件。
• 条件变量存在于管程内部，对同一个条件变量调用操作的进程将和条件变量建立一定的联系，或者称之为绑定。
  • 对于管程内的条件变量 x，进程 P 调用 x.wait() 将时自身挂起到条件变量 x 上；
  • 当另一个进程调用 x.signal()时，在 x 上悬挂的进程会被重启，如果此时没有进程悬挂在 x 上，则 x.signal() 操作将被忽略。
• 管程模式下的 x.signal() 和信号量的 signal() 区别在于：信号量操作 signal() 会影响信号量的状态，而管程下的 x.signal() 在 x 不存在挂起进程的情况下没有任何影响。
• 举例：进程 P 调用x.signal()，且存在悬挂进程 Q 与条件变量 x 关联。根据管程的性质，若进程 Q 开始执行，则进程 P 必须等待。此时可能存在两种可能性，且两种可能性均有合理解释：
  • 进程 Q 重启且进程 P 等待(Hoare semantics)：进程 P 将等待，直到进程 Q 离开管程或者等待另一个进程调用 x.signal()
  • 进程 P 唤醒进程 Q 且进程 P 继续执行(Mesa semantics)：进程 Q 被唤醒，但仍然会等待，直到进程 P 离开管程，或者另一个触发条件。因为 P 已经在管程中执行，看起来此种方案更合理，但这破坏了进程 Q 正在等待的逻辑条件，进程 Q 已被触发但又未执行，因此状态难以描述
  • Pascal 语言采用折中方式，当进程 P 执行 x.signal() 时，它会立刻离开管程，且进程 Q 会立刻重新执行

管程模型

注意这个管程与外部的入管进程队列之间有一个互斥锁。在管程的简单实现中，编译器为每个管程对象自动加入一把私有的互斥锁。该互斥锁初始状态为解锁，在管程的每个公共子程序的入口给该互斥锁加锁，在管程的每个公共子程序的出口给该互斥锁解锁（或者将自身挂起时）。

哲学家进餐问题的管程解法

• 使用 进程同步 中的一种策略：当哲学家在两只筷子均可用的情况下才拿起筷子，且拿起两只筷子的动作是非抢占的。
• 为哲学家设置三种状态：enum {THINKING, HUNGRY, EATING} state[5]
• 哲学家 i 只有在两个邻居都不进餐时才能将变量 state[i] 设置为 EATING，当他处在饥饿状态又无法进餐时可以使自己忍耐一段时间：(state[(i-1)%5] != EATING) && (state[i] == HUNGRY) && (state[(i+1)%5] != EATING)

下面给出用管程解决的哲学家进餐问题，只解决了互斥问题，不会导致死锁，但可能导致某个哲学家过度饥饿而死。(没有解决有限边界，且同时只能有一个哲学家在进餐)

monitor dp{
    enum {THINKING, HUNGRY, EATING} state[5];
    condition self[5];//每个哲学家对应一个条件变量
    void pickup(int i){
        state[i] = HUNGRY;
        test(i);
        if (state[i] != EATING)//test函数不成功，将自己阻塞
            self[i].wait();
    }
    void putdown(int i){
        state[i] = THINKING;
        //唤醒被阻塞的哲学家
        test((i-1) % 5);
        test((i+1) % 5);
    }
    void test(int i){
        if ((state[(i-1)%5] != EATING) && 
            (state[i] == HUNGRY) &&
            (state[(i+1)%5] != EATING)){
            state[i] = EATING;
            self[i].signal();
        }
    }
    initialization_code(){
        for (int i = 0; i < 5; i++)
            state[i] = THINKING;
    }
}

一个改进版的 Monitor 解决方案如下。筷子本身并不属于 monitor 的一部分，否则同时只能有一个哲学家在进餐。代码中 NUM_PHILS 是哲学家数目。此代码解决了哲学家饥饿问题，来自西弗吉尼亚大学。

monitor dp{
    condition self[NUM_PHILS];
    enum states {THINKING, HUNGRY, EATING} state[NUM_PHILS-1];
    int index;
    initialization_code(){
        for (index=0; index<NUM_PHILS; index++)
            flags[index] = THINKING;
    }
    void pickup(int i) {
        state[i] = HUNGRY;
        if ((state[(i-1)%NUM_PHILS] != EATING) &&
            (state[(i+1)%NUM_PHILS] != EATING))
            state[i] = EATING;
        else {
            // 挂起，等待相邻哲学家改变状态时唤醒
            self[i].wait;
            // wait 操作被唤醒后可以改变状态为 EATING
            state[i] = EATING;
        }
    }
    void putdown(int i) {
        state[i] = THINKING;
        // 唤醒左侧哲学家
        if ((state [(i-1)%NUM_PHILS] == HUNGRY) &&
            (state [(i-2)%NUM_PHILS] != EATING))
            self[(i-1)%NUM_PHILS].signal;
        // 唤醒右侧哲学家
        if ((state [(i+1)%NUM_PHILS] == HUNGRY) &&
            (state [(i+2)%NUM_PHILS] != EATING))
            self[(i+1)%NUM_PHILS].signal;
    }
}

使用信号量实现管程

• 要实现的管程对于重启进程采用的策略是： 调用 x.signal() 的进程挂起自己，直到重新启动的进程离开或者等待 。
• 每个管程都有一个信号量 mutex 初始化为 1（互斥锁），进程进入管程之前必须通过 wait() 获得允许，离开时需要调用 signal() 释放权限。
• 信号量 next 初始化为 0，供线程在唤醒重启进程时挂起自己，整数变量 next_count 用于对挂起在 next 上的进程数量计数。

进入管程的外部子程序结构 F 如下：

void F(){
    wait(mutex);
    // 子程序执行
    // ...
    // 子程序执行结束
    if (next_count > 0)
        signal(next);    //     此前有进程挂起，重启该进程
    else
        signal(mutex);   //     管程内无进程挂起，释放互斥锁控制权
}

对每个管程内的条件变量 x，引入信号量 x_sem 和整数变量 x_count 记录信号量 x 上挂起的进程数量，均初始化为 0。x.wait() 和 x.signal() 实现如下：

void x.wait(){
    x_count++;            // 将进程挂起到 x 上，让计数加一
    if (next_count > 0)   // 当前仍有进程挂起在管程中
        signal(next);     //说明这个进程此前让出了控制权，现在优先将其唤醒
    else
        signal(mutex);    // 无进程在等待，释放管程控制权
    wait(x_sem);          // 等待信号量 x_sem，由信号量决定唤醒哪个挂起进程
    //等待被唤醒
    x_count--;            // 等待结束，进程被唤醒
}

void x.signal(){
    if (x_count > 0){     // 当前有程序挂起在条件变量 x
        next_count ++;    // 自己将要被阻塞，故管程挂起数增加
        signal(x_sem);    // 释放信号量，唤醒一个挂起进程
        wait(next);       // 将自身阻塞到管程中（将next的资源数减一）
        //等待被唤醒
        next_count--;     // 被唤醒，继续执行
    }
    // 没有程序挂起在条件变量 x，不产生任何影响
}

注意这里对挂起和阻塞的区分不是很严谨，实际上挂起跟阻塞是不一样的。

管程VS信号量

管程和信号量都能解决并发问题，它们是等价的。所谓等价指的是用管程能够实现信号量，也能用信号量实现管程。但是管程在信号量的基础上提供条件同步，使用更容易，所以 Java 采用的是管程技术。synchronized 关键字及 wait()、notify()、notifyAll() 这三个方法都是管程的组成部分。

• 信号量(Semaphere)：操作系统提供的一种协调共享资源访问的方法。和用软件实现的同步比较，软件同步是平等线程间的的一种同步协商机制，不能保证原子性。而信号量则由操作系统进行管理，地位高于进程，操作系统保证信号量的原子性。
• 管程(Monitor)：解决信号量在临界区的 PV 操作上的配对的麻烦，把配对的 PV 操作集中在一起，生成的一种并发编程方法。其中使用了条件变量这种同步机制。

说明： 信号量将共享变量 S 封装起来，对共享变量 S 的所有操作都只能通过 PV 进行，这是不是和面向对象的思想是不是很像呢？事实上，封装共享变量是并发编程的常用手段。

在信号量中，当 P 操作无法获取到锁时，将当前线程添加到同步队列(syncQueue)中。当其余线程 V 释放锁时，从同步队列中唤醒等待线程。但当有多个线程通过信号量 PV 配对时会异常复杂，所以管程中引入了等待队列(waitQueue)的概念，进一步封装这些复杂的操作。

PS.

java管程模型中，阻塞队列有两个操作分别是入队和出队，这两个方法都是先获取互斥锁，类比管程模型中的入口。

1. 对于入队操作，如果队列已满，就需要等待直到队列不满，即 notFull.await()。
2. 对于出队操作，如果队列为空，就需要等待直到队列不空，即 notEmpty.await()。
3. 如果入队成功，那么队列就不空了，就需要通知条件变量：队列不空 notEmpty 对应的等待队列。
4. 如果出队成功，那就队列就不满了，就需要通知条件变量：队列不满 notFull 对应的等待队列。

public class BlockedQueue<T> {
    final Lock lock = new ReentrantLock();
    // 条件变量：队列不满
    final Condition notFull = lock.newCondition();
    // 条件变量：队列不空
    final Condition notEmpty = lock.newCondition();

    // 入队
    void enq(T x) {
        lock.lock();
        try {
            while (队列已满) {
                // 等待队列不满
                notFull.await();
            }
            // add x to queue
            // 入队后,通知可出队
            notEmpty.signal();
        } finally {
            lock.unlock();
        }
    }

    // 出队
    void deq() {
        lock.lock();
        try {
            while (队列已空) {
                // 等待队列不空
                notEmpty.await();
            }
            // remove the first element from queue
            // 出队后，通知可入队
            notFull.signal();
        } finally {
            lock.unlock();
        }
    }
}

第六章习题拾遗

• 首先，局部变量不涉及互斥问题。所以两个进程的a和b不需要互斥。
• 其次，两进程的x并不是共享变量，所以两进程各自的x不需要互斥。

• 首先，A肯定错误，显然，并没有进行唤醒。
• B是正确的
• C错误，因为lock置为false后可能又会被同一进程的while捕获，导致没有实现有限等待

设计的一般流程

• 写伪代码

• 找出那些地方可能需要等待

• 看是否要加互斥锁

论述类习题

There are two different ways that commands can be processed by a command interpreter. One way is to allow the command interpreter to contain the code needed to execute the command. The other way is to implement the commands through system programs. Compare and contrast the two approaches.

Ans: In the first approach, upon the user issuing a command, the interpreter jumps to the appropriate section of code, executes the command, and returns control back to the user. In the second approach, the interpreter loads the appropriate program into memory along with the appropriate arguments. The advantage of the first method is speed and overall simplicity. The disadvantage to this technique is that new commands require rewriting the interpreter program which, after a number of modifications, may get complicated, messy, or too large. The advantage to the second method is that new commands can be added without altering the command interpreter. The disadvantage is reduced speed and the clumsiness of passing parameters from the interpreter to the system program.

Explain why a modular kernel may be the best of the current operating system design techniques.

Ans: The modular approach combines the benefits of both the layered and microkernel design techniques. In a modular design, the kernel needs only to have the capability to perform the required functions and know how to communicate between modules. However, if more functionality is required in the kernel, then the user can dynamically load modules into the kernel. The kernel can have sections with well-defined, protected interfaces, a desirable property found in layered systems. More flexibility can be achieved by allowing the modules to communicate with one another.

参考

https://www.zhihu.com/question/290504400

http://blog.forec.cn作者Forec

https://www.cnblogs.com/binarylei/p/12544002.html