操作系统

操作系统是什么

操作系统是计算机系统中的一个系统软件，是一些程序模块的集合。它们能以尽量有效、合理的方式组织和管理计算机的软硬件资源。合理的组织计算机的工作流程，控制程序的执行并向用户提供各种服务功能。使得用户能够灵活、方便的使用计算机，使整个计算机系统高效率运行。

操作系统的三个作用

资源的管理者

硬件资源：CPU，内存，设备（IO设备，磁盘，时钟，网卡）
软件资源：磁盘文件，各类管理信息等

向用户提供各种服务

进程创建，执行、文件和目录的操作、I/O设备的使用；各类统计信息；

对硬件机器的扩展

与硬件相关的工作复杂、繁琐（软盘I/O操作）

资源管理者

跟踪记录资源的使用状况，如：那些资源空闲，分配给谁，允许使用多长
确定资源分配策略--算法

静态分配策略
动态分配策略

实施资源的分配和回收
提高资源的利用率
保护资源的使用
协调多个进程对资源请求的冲突

从资源管理的角度-五大基本功能

进程/线程管理（CPU管理）：进程线程状态、控制、同步互斥、通信、调度等
存储管理：分配回收、地址转换、存储保护、内存扩充等
文件管理：文件目录、文件操作、磁盘空间、文件存取控制等
设备管理：设备驱动，分配回收、缓冲技术
用户接口：系统命令、编程接口

操作系统的主要特征

并发：处理多个同时性活动的能力
共享：操作系统与多个应用程序共同使用计算机系统的资源（共享有限的系统资源）。操作系统要对系统资源进行合理分配和使用，资源在一个时间段内交替被多个进程使用。

互斥共享（打印机）
同时共享（磁盘文件，可重入代码）

虚拟：一个物理实体映射为若干个对应的逻辑实体--分时或分空间。虚拟是操作系统管理系统资源的重要手段，可提高资源利用率。CPU--每个进程的虚处理机、存储器==每个进程都有独立的虚拟地址空间（代码+数据+堆栈）、显示设备--多窗口或虚拟终端
随机：操作系统必须随时对以不可预测的次序发生的事件进行响应并处理，进程的运行速度不可预知：多个进程并执行，“走走停停，无法预知每个进程的运行推进快慢。难以重现系统在某个时刻的状态（包括重新运行中的错误）

操作系统分类

大型机操作系统
服务器操作系统
多处理机操作系统
个人计算机操作系统
掌上计算机操作系统
传感器节点操作系统
实时操作操作系统
嵌入式操作系统
智能卡操作系统

操作系统硬件

处理器（CPU）

CPU由运算器、控制器、一系列的寄存器以及高速缓存构成。

寄存器：

用户可见寄存器：高级语言编译器通过优化算法分配并使用之，以减少程序访问内存次数
控制和状态寄存器：用于控制处理器的操作，通常由操作系统代码使用

程序计数器（PC：Program Counter）记录将要取出的指令地址
指令寄存器（IR：Instruction Register）：记录最近取出的指令
程序状态字（PSW：Program Status Word）：记录处理器的运行状态如条件码、模式、控制位等信息

　　CPU从内存中取出指令并执行。在每个CPU基本周期中，首先从内存中取出指令，解码以确定其类型和操作数，接着执行，然后继续取指，解码并执行。由于用来访问内存以得到指令或数据的时间要比执行指令花费的时间长得多，因此，所有的CPU内都有一些用来保存关键变量和临时数据的寄存器。这样，通常在指令集中提供一些指令，用以将一个字从内存调入寄存器，以及将一个字从寄存器存入内存。其他的指令可以把来自寄存器、内存的操作数组合，或者用两者产生一个结果，诸如将两个字相加并把结果存在寄存器或内存中。

　　除了用来保存变量和临时结果的通用寄存器之外，多数计算机还有一些对程序员可见的专门寄存器。其中之一是程序计数器，它保存了将要取出的下一条指令的内存地址。在指令取出之后，程序计数器就被更新以便指向后继的指令。

另一个寄存器是堆栈指针，它指向内存中当前栈的顶端。该栈含有已经进入但是还没有退出的每个过程的一个框架。在一个过程的堆栈框架中保存了有关的输入参数、局部变量以及那些没有保存在寄存器中的临时变量。

当然还有程序状态字（Program Status Word， PSW）寄存器。这个寄存器包含了条件码位（由比较指令设置）、 CPU优先级、模式（用户态或内核态），以及各种其他控制位。用户程序通常读入整个PSW，但是，只对其中的少量字段写入。在系统调用和I/O中， PSW的作用很重要。

　　操作系统必须知晓所有的寄存器。在时间多路复用（time multiplexing） CPU中，操作系统经常会中止正在运行的某个程序并启动（或再启动）另一个程序。每次停止一个运行着的程序时，操作系统必须保存所有的寄存器，这样在稍后该程序被再次运行时，可以把这些寄存器重新装入。

　　为了改善性能， CPU设计师早就放弃了同时读取、解码和执行一条指令的简单模型。许多现代CPU具有同时取出多条指令的机制。例如，一个CPU可以有分开的取指单元、解码单元和执行单元，于是当它执行指令n时，它还可以对指令n+1解码，并且读取指令n+2。这样一种机制称为流水线（pipeline）。在多数的流水线设计中，一旦一条指令被取进流水线中，它就必须被执行完毕，即便前一条取出的指令是条件转移，它也必须被执行完毕。流水线使得编译器和操作系统的编写者很头疼，因为它造成了在机器中实现这些软件的复杂性问题。

　　比流水线更先进的设计是一种超标量CPU，如图1-7b所示。在这种设计中，有多个执行单元，例如，一个CPU用于整数算术运算，一个CPU用于浮点算术运算，而另一个用于布尔运算。两个或更多的指令被同时取出、解码并装入一个保持缓冲区中，直至它们执行完毕。只要有一个执行单元空闲，就检查保持缓冲区中是否还有可处理的指令，如果有，就把指令从缓冲区中移出并执行之。这种设计存在一种隐含的作用，即程序的指令经常不按顺序执行。在多数情况下，硬件负责保证这种运算的结果与顺序执行指令时的结果相同，但是，仍然有部分令人烦恼的复杂情形被强加给操作系统处理。

　　除了用在嵌入式系统中的非常简单的CPU之外，多数CPU都有两种模式，即前面已经提及的内核态和用户态。通常，在PSW中有一个二进制位控制这两种模式。当在内核态运行时， CPU可以执行指令集中的每一条指令，并且使用硬件的每种功能。操作系统在内核态下运行，从而可以访问整个硬件。

　　相反，用户程序在用户态下运行，仅允许执行整个指令集的一个子集和访问所有功能的一个子集。一般而言，在用户态中有关I/O和内存保护的所有指令是禁止的。当然，将PSW中的模式位设置成内核态也是禁止的。

为了从操作系统中获得服务，用户程序必须使用系统调用（system call）系统调用陷入内核并调用操作系统。 TRAP指令把用户态切换成内核态，并启用操作系统。当有关工作完成之后，在系统调用后面的指令把控制权返回给用户程序。

操作系统的CPU状态

内核态：运行操作系统程序

用户态：运行用户程序

CPU状态之间的转换：

用户态-->内核态：中断、异常、陷入机制

内核态-->用户态：设置程序状态字PSW

特殊指令：陷入指令（访管指令）提供给用户程序的接口，用于调用操作系统的功能（服务）如：int，trap，syscall，sysenter、sysexit

中断/异常机制

中断/异常机制是CPU对系统发生的某个时间作出的一种反应。对于操作系统的重要性就好比：汽车的发动机，飞机的引擎。中断即为CPU暂停正在执行的程序，保留现场后自动转去执行相应事件的处理程序，处理完成后返回断点继续执行被打断的程序。

主要作用：

及时处理设备发来的中断请求
可使OS捕获用户程序提出的服务请求
防止用户程序执行破坏行动

中断的引入：为了支持CPU和设备之间的并行操作

异常的引入：表示CPU执行指令时本身出现的问题

事件：

中断（外中断）

I/O中断
时钟中断
硬件故障

异常（内中断）

系统调用
页故障、页错误
保护性异常
断点指令
其他程序性异常（算数溢出）

外部中断（由硬件信号引发）

1、可屏蔽中断：通过INTR线向CPU请求的中断，主要来自外部设备如硬盘，打印机，网卡等。此类中断并不会影响系统运行，可随时处理，甚至不处理，所以名为可屏蔽中断。

2、不可屏蔽中断：通过NMI线向CPU请求的中断，如电源掉电，硬件线路故障等。这里不可屏蔽的意思不是不可以屏蔽，不建议屏蔽，而是问题太大，屏蔽不了，不能屏蔽的意思。

注：INTR和NMI都是CPU的引脚

内部中断(由指令执行引发)

1、陷阱：是一种有意的，预先安排的异常事件，一般是在编写程序时故意设下的陷阱指令，而后执行到陷阱指令后，CPU将会调用特定程序进行相应的处理，处理结束后返回到陷阱指令的下一条指令。如系统调用，程序调试功能等。

尽管我们平时写程序时似乎并没有设下陷阱，那是因为平常所用的高级语言对底层的指令进行了太多层的抽象封装，已看不到底层的实现，但其实是存在的。例如printf函数，最底层的实现中会有一条int 0x80指令，这就是一条陷阱指令，使用0x80号中断进行系统调用。

2、故障：故障是在引起故障的指令被执行，但还没有执行结束时，CPU检测到的一类的意外事件。出错时交由故障处理程序处理，如果能处理修正这个错误，就将控制返回到引起故障的指令即CPU重新执这条指令。如果不能处理就报错。

常见的故障为缺页，当CPU引用的虚拟地址对应的物理页不存在时就会发生故障。缺页异常是能够修正的，有着专门的缺页处理程序，它会将缺失的物理页从磁盘中重新调进主存。而后再次执行引起故障的指令时便能够顺利执行了。

3、终止：执行指令的过程中发生了致命错误，不可修复，程序无法继续运行，只能终止，通常会是一些硬件的错误。终止处理程序不会将控制返回给原程序，而是直接终止原程序。

中断控制器

每个独立运行的外设都可以是一个中断源，能够向CPU发送中断请求，负责将硬件的中断信号转换为中断向量，并引发CPU中断。为了方便管理和减少引脚数目，设立了中断控制器，让所有的可屏蔽中断都通过INTR信号线与CPU进行交流。

实模式：中断向量表

存放中断处理程序的入口地址

入口地址=段地址左移4位+偏移地址
不支持CPU运行状态切换
中断处理与一般的过程调用相似

保护模式：中断描述符表

采用门（gate）描述符数据结构表示中断向量

中断向量表/中断描述符表

四种类型门描述符

任务门
中断门

给出段选择符、中断/异常程序的段内偏移量
通过中断门后系统会自动禁止中断

陷阱门

与中断门类似，但通过陷阱门后系统不会自动禁止中断

调用门

中断/异常机制工作原理

硬件（中断/异常响应）：捕获中断源发出的中断/异常请求，以一定方式响应，将处理器控制权交给特定的处理程序

软件（中断/异常处理程序）：识别中断/异常类型并完成相应的处理

中断响应：发现中断，接收中断的过程，由中断硬件部件完成。由中断寄存器处理。

1 中断响应过程

开始--------------->取下一条指令------------>执行指令------（在每条指令执行周期的最后时刻扫描中断寄存器，查看是否有中断信号）------>检查指令处理中断（若有中断，中断硬件将该中断触发器内容按规定编码送入PSW的相应位，称为中断码，通过查中断向量表引出中断处理程序，若无中断信号，继续取指令并执行）

中断向量：一个内存单元，存放中断处理程序入口地址和程序运行时所需的处理机状态字。

中断向量表：存放中断向量

2 中断处理程序

由于CPU随时都可能检测到中断信息，也就是说，CPU随时都可能执行中断处理程序，所以中断处理程序必须一直存储在内存某段空间中. 而中断处理程序的入口地址，即中断向量，必须存储在对应的中断向量表表项中.

实例

以设备输入输出中断为例：

打印机给CPU发中断信息
CPU处理完当前指令后检测到中断，判断出中断来源并向相关设备发确认信号
CPU开始为软件处理中断做准备

处理器状态切换到内核态
在系统栈中保存被中断程序的重要上下文环境，主要是程序计数器PC，程序状态字PSW

CPU根据中断码查询中断向量表，获得与该中断相关的处理程序的入口地址，并将PC设置成该地址，新的指令周期开始时，CPU控制转移到中断处理程序
中断处理程序开始工作

在系统栈中保存现场信息
检查I/O设备的状态信息，操纵I/O设备或者在设备和内存之间传送数据等等

中断处理结束时，CPU检测到中断返回指令，从系统栈中恢复被中断程序的上下文环境，CPU状态恢复成原来状态，PSW和PC恢复成中断前的值，CPU开始一个新的指令周期

多线程和多核芯片

　　多线程允许CPU保持两个不同的线程状态，然后在纳秒级的时间尺度内来回切换。（线程是一种轻量级进程，也即一个运行中的程序。）。例如，如果某个进程需要从内存中读出一个字（需要花费多个时钟周期），多线程CPU则可以切换至另一个线程。多线程不提供真正的并行处理。在一个时刻只有一个进程在运行，但是线程的切换时间则减少到纳秒数量级。

　　多线程对操作系统而言是有意义的，因为每个线程在操作系统看来就像是单个的CPU。考虑一个实际有两个CPU的系统，每个CPU有两个线程。这样操作系统将把它看成是4个CPU。如果在某个时间的特定点上，只有能够维持两个CPU忙碌的工作量，那么在同一个CPU上调度两个线程，而让另一个CPU完全空转，就没有优势了。这种选择远远不如在每个CPU上运行一个线程的效率高。

　　除了多线程，还出现了包含2个或4个完整处理器或内核的CPU芯片。图1-8中的多核芯片上有效地装有4个小芯片，每个小芯片都是一个独立的CPU。要使用这类多核芯片肯定需要多处理器操作系统。

存储器

CPU执行指令，而存储器系统为CPU存放指令和数据。

随机访问存储器（RAM）分为两类：静态和动态。静态RAM（SRAM）比动态RAM（DRAM）更快，但也贵的多。SRAM作为高速缓存存储器，既可以在CPU芯片上，也可以在片下。

　　多核芯片情况：在图1-8a中，一个L2缓存被所有的核共享。 Intel多核芯片采用了这个方法。相反，在图1-8b中，每个核有其自己的L2缓存。 AMD采用这个方法。不过每种策略都有自己的优缺点。例如， Intel的共享L2缓存需要有一种更复杂的缓存控制器，而AMD的方式在设法保持L2缓存一致性上存在困难。

磁盘

　　在一个磁盘中有一个或多个金属盘片，它们以5400， 7200或10 800rpm的速度旋转。从边缘开始有一个机械臂悬横在盘面上，这类似于老式播放塑料唱片33转唱机上的拾音臂。信息写在磁盘上的一系列同心圆上。在任意一个给定臂的位置，每个磁头可以读取一段环形区域，称为磁道（track）。把一个给定臂的位置上的所有磁道合并起来，组成了一个柱面（cylinder）。每个磁道划分为若干扇区，扇区的典型值是512字节。扇区之间由一些间隙分隔开，这些间隙不存储数据位。间隙存储用来标识扇区的格式化位。在现代磁盘中，较外面的柱面比较内部的柱面有更多的扇区。机械臂从一个柱面移到相邻的柱面大约需要1ms。而随机移到一个柱面的典型时间为5ms至10ms，其具体时间取决于驱动器。一旦磁臂到达正确的磁道上，驱动器必须等待所需的扇区旋转到磁头之下，这就增加了5ms至10ms的时延，其具体延时取决于驱动器的转速。一旦所需要的扇区移到磁头之下，就开始读写，低端硬盘的速率是5MB/s，而高速磁盘的速率是160 MB/s。此类磁盘为选择磁盘，也叫作机械硬盘，以区别于基于闪存的固态硬盘（SSD），SSD没有移动部分。

　　许多计算机支持一种著名的虚拟内存机制。这种机制使得期望运行大于物理内存的程序成为可能，其方法是将程序放在磁盘上，而将主存作为一种缓存，用来保存最频繁使用的部分程序。这种机制需要快速地映像内存地址，以便把程序生成的地址转换为有关字节在RAM中的物理地址。这种映像由CPU中的一个部件，称为存储器管理单元（Memory Management Unit， MMU）来完成。缓存和MMU的出现对系统的性能有着重要的影响。在多道程序系统中，从一个程序切换到另一个程序，有时称为上下文切换（context switch），有必要对缓存中来的所有修改过的块进行写回磁盘操作，并修改MMU中的映像寄存器。但是这两种操作的代价很昂贵，所以程序员们努力避免使用这些操作。我们稍后将看到这些操作产生的影响。

系统调用

系统调用：用户在编程时可以调用的操作系统功能，是操作系统提供给编程人员的唯一接口，能够使CPU状态从用户态陷入内核态。每个操作系统都提供几百种系统调用（进程控制，进程通信，文件使用，目录操作，设备管理，信息维护等）

系统调用机制的设计

中断/异常机制：支持系统调用服务的实现

选择一条特殊指令：陷入指令（访管指令），引发异常，完成用户态到内核态的切换

系统调用号和参数：每个系统调用都是先给定一个编号（功能号）

系统调用表：存放系统调用服务程序的入口地址

参数传递问题

实现用户程序的参数传递给内核

由陷入指令自带参数：陷入指令的长度有限，且还要携带系统调用功能号，只能自带有限的参数
通过通用寄存器传递参数：这些寄存器是操作系统和用户程序都能访问的，但寄存器的个数会限制传递参数的数量
在内存中开辟专用堆栈区来传递参数

系统调用的执行过程

当CPU执行到特殊的陷入指令时：

中断/异常机制：硬件保护现场；通过查中断向量表把控制权转给系统调用总入口程序
系统调用总入口程序：保存现场；将参数保存在内核的堆栈里；通过查系统调用表吧控制权转给相应的系统调用处理例程或内核函数
执行系统调用例程
恢复现场，返回用户程序

　　用户态调用C库的库函数，write函数，封装的write函数先做好参数传递工作，然后使用int 0X80指令产生一次异常，CPU通过0X80号在IDT中找到对应的服务例程system_call（），并调用，system_call（）将参数保存在内核栈，根据系统调用号索引系统调用表，找到系统调用程序入口，比如sys_write（）。sys_write（）执行完后，经过ret_from_sys_call（）例程返回用户程序。

实例（read系统调用）

　　我们简要地考察read系统调用。它有三个参数：第一个参数指定文件，第二个指向缓冲区，第三个说明要读出的字节数。几乎与所有的系统调用一样，它的调用由C程序完成，方法是调用一个与该系统调用名称相同的库过程： read。由C程序进行的调用可有如下形式：count=read(fd,buffer,nbytes);系统调用（以及库过程）在count中返回实际读出的字节数。这个值通常和nbytes相同，但也可能更小，例如，如果在读过程中遇到了文件尾的情形就是如此。如果系统调用不能执行，不论是因为无效的参数还是磁盘错误， count都会被置为-1，而在全局变量errno中放入错误号。程序应该经常检查系统调用的结果，以了解是否出错。系统调用是通过一系列的步骤实现的。在准备调用这个实际用来进行read系统调用的read库过程时，调用程序首先把参数压进堆栈，如图1-17中步骤1～步骤3所示。

　　由于历史的原因， C以及C++编译器使用逆序（必须把第一个参数赋给printf（格式字串），放在堆栈的顶部）。第一个和第三个参数是值调用，但是第二个参数通过引用传递，即传递的是缓冲区的地址（由＆指示），而不是缓冲区的内容。接着是对库过程的实际调用（第4步）。这个指令是用来调用所有过程的正常过程调用指令。在可能是由汇编语言写成的库过程中，一般把系统调用的编号放在操作系统所期望的地方，如寄存器中（第5步）。然后执行一个TRAP指令，将用户态切换到内核态，并在内核中的一个固定地址开始执行（第6步）。 TRAP指令实际上与过程调用指令相当类似，它们后面都跟随一个来自远地位置的指令，以及供以后使用的一个保存在栈中的返回地址。

　　然而， TRAP指令与过程指令存在两个方面的差别。首先，它的副作用是，切换到内核态。而过程调用指令并不改变模式。其次，不像给定过程所在的相对或绝对地址那样， TRAP指令不能跳转到任意地址上。根据机器的体系结构，或者跳转到一个单固定地址上，或者指令中有一8位长的字段，它给定了内存中一张表格的索引，这张表格中含有跳转地址。跟随在TRAP指令后的内核代码开始检查系统调用编号，然后发出正确的系统调用处理命令，这通常是通过一张由系统调用编号所引用的、指向系统调用处理器的指针表来完成（第7步）。此时，系统调用句柄运行（第8步）。一旦系统调用句柄完成其工作，控制可能会在跟随TRAP指令后面的指令中返回给用户空间库过程（第9步）。这个过程接着以通常的过程调用返回的方式，返回到用户程序（第10步）。

　　为了完成整个工作，用户程序还必须清除堆栈，如同它在进行任何过程调用之后一样（第11步）。假设堆栈向下增长，如经常所做的那样，编译后的代码准确地增加堆栈指针值，以便清除调用read之前压入的参数。在这之后，原来的程序就可以随意执行了。在前面第9步中，我们提到“控制可能会在跟随TRAP指令后面的指令中返回给用户空间库过程”，这是有原因的。系统调用可能堵塞调用者，避免它继续执行。例如，如果试图读键盘，但是并没有任何键入，那么调用者就必须被阻塞。在这种情形下，操作系统会查看是否有其他可以运行的进程。稍后，当需要的输入出现时，进程会提醒系统注意，然后步骤9～步骤11会接着进行。

进程（process）

进程是具有独立功能的程序关于某个数据集合上的一次运行活动，是系统进行资源分配和调度的独立单位，又称任务（Task or Job）。程序的一次执行过程，如果是多次执行，就是多个进程。操作系统将CPU调度给需要的进程。

分类：

系统进程和用户进程

前台进程和后台进程

CPU密集型进程和I/O密集型进程

进程控制块（PCB）

PCB：Process Control Block，又称进程描述符，进程属性。操作系统用于管理控制进程的一个专门数据结构，记录进程的各种属性，描述进程的动态变化过程。PCB是系统感知进程存在的唯一标志，进程与PCB一一对应。

进程表：所有进程的PCB集合。

进程描述信息

进程标识符：通常是一个整数，唯一
进程名：通常基于可执行文件名，不唯一
用户标识符
进程组关系

进程控制信息

当前状态
优先级
代码执行入口地址
程序的磁盘地址
运行统计信息（执行时间、页面调度）
进程间同步和通信
进程的队列指针
进程的消息队列指针

所拥有的资源和使用情况

虚拟地址空间的状况
打开文件列表

CPU现场信息（进程不运行时，操作系统要保存的硬件执行状态）

寄存器值（通用寄存器、程序计数器PC、程序状态字PSW、栈指针）
指向该进程页表的指针

进程的状态

三种基本状态：运行态、就绪态、等待态

运行态：占有CPU，并在CPU上运行

就绪态：已经具备运行条件，但由于没有空闲CPU，而暂时不能运行

阻塞态：因等待某一事件而暂时不能运行（如：等待磁盘的读取结果）

其他状态

创建：已完成创建一进程所必要的工作（PID，PCB），但尚未同意执行该进程，CPU资源不足

终止：终止执行后，进程进入该状态，可完成一些数据统计工作，资源回收

挂起：用于调节负载，进程不占用内存空间，其进程映像交换到磁盘上

进程队列

操作系统为每一类进程建立一个或多个队列，队列元素为PCB，伴随进程状态的改变，其PCB从一个队列进入另一个队列，多个等待队列等待的事件不同，就绪队列也可以多个，单CPU情况下，运行队列只有一个进程。

进程控制

进程控制操作完成进程各状态之间的转换，由具有特定功能的原语完成。

原语：完成某种特定功能的一段程序，具有不可分割或不可中断性质。即原语执行必须是连续的，即原子操作。

进程创建

给新进程分配一个唯一标识以及进程控制块（PCB）

为进程分配地址空间

初始化进程控制块，设置默认值（如：状态为NEW ..）

设置相应的队列指针，如吧新进程加到就绪队列中

进程的撤销

结束进程：

收回进程占有的资源（关闭打开的文件，断开网络连接，回收分配的内存等）

撤销进程的PCB

进程阻塞

处于运行状态的进程，在其运行过程中期待某一事件发生，如等待键盘输入、等待磁盘数据传输、等待其他进程发送消息。当被等待的事件未发生时，由进程自己执行阻塞原语，使自己由运行态转为阻塞态。

UNIX的几个进程控制操作

fork（）：通过复制调用进程来建立新的进程，是最基本的进程建立过程

exec（）：包括一系列系统调用，他们都是通过用一段新的程序代码覆盖原来的地址空间，实现进程执行代码的转换

wait（）：提供初级进程同步操作，使一个进程等待另一个进程的结束

exit（）：用来终止一个进程的运行

fork（）实现

为子进程分配一个空闲的进程描述符（PCB）,UNIX称为proc结构
分配给子进程唯一标识pid
以一次一页的方式复制父进程地址空间（linux采用了写时复制技术（cow：copy-on-write）加快创建进程）
从父进程处继承共享资源，如打开的文件和当前工作目录等
将子进程的状态设为就绪，插入到就绪队列
对子进程返回标识符0
向父进程饭后子进程pid

进程地址空间

进程映像

对进程执行活动全过程的静态描述，由进程地址空间内容、硬件寄存器内容及与该进程相关的内核数据结构、内核栈组成

用户相关：进程地址空间（包括代码段，数据段。堆和栈、共享库等）
寄存器相关：程序计数器、指令寄存器、程序状态寄存器、栈指针、通用寄存器等的值
内核相关：

静态部分：PCB及各种资源数据结构
动态部分：内核栈（不同进程在进入内核后使用不同的内核栈）

上下文切换

将CPU硬件状态从一个进程换到另一个进程的过程叫做上下文切换。

进程运行时，其硬件状态保存在CPU上的寄存器中。寄存器：程序计数器、程序状态寄存器、栈指针、通用寄存器、其他控制寄存器的值

进程不运行时，这些寄存器的值保存在进程控制块（PCB）中；当操作系统要运行一个新的进程时，将PCB中的相关值送到对应的寄存器中。

线程

引入线程的原因：

应用的需要：
开销的考虑：线程创建花费时间少，线程切换花费时间也少，线程间通信无须调用内核（同一进程内的线程共享内存和文件）
性能的考虑：多线程处理一个进程

线程属性

标识符ID
状态
上下文环境：程序计数器等寄存器
栈和栈指针
共享所在进程的地址空间和其他资源

用户级线程（UNIX支持）

在用户空间建立线程库：提供一组管理线程的过程

运行时系统完成线程的管理工作（操作、线程表）

内核管理的还是进程，不知道线程的存在，线程切换不需要内核态特权。

优点：

线程切换快
调度算法是应用程序特定的
用户级线程可运行在任何操作系统上（只需要实现线程库）

缺点：

内核只将处理器分配给进程，同一进程中的两个线程不能同时运行于两个处理器上
大多数系统调用是阻塞的，因此，由于内核阻塞进程，故进程中所有线程也被阻塞

核心级线程（window支持）

内核管理所有线程，并向应用程序提供API接口

内核维护进程和线程的上下文切换

线程的切换需要内核支持

以线程为基础进行调度

混合模式（Solaris）

线程创建在用户空间

线程调度在内核态

CPU调度

CPU调度是控制、协调进程对CPU的竞争。即按一定的调度算法从就绪队列中选择一个进程，吧CPU的使用权交给被选中的进程。如果没有就绪线程。系统会安排一个空闲进程或idle进程。

CPU调度时机

事件发生->当前运行的进程暂停运行->硬件机制响应后->进入操作系统，处理相应的事件->结束处理后：某些进程的状态发生变化，也可能创建了一些新的进程->就绪队列发生改变->需要进程调度根据预设的调度算法从就绪队列选择一个进程

事件案例：

创建、唤醒、退出等进程控制操作
进程等待I/O、I/O中断
时钟中断，如：时间片用完、计时器到时
进程执行过程中出现abort异常

进程切换：是指一个进程让出处理器，由另一个进程占用处理器的过程。切换过程包括了对原来运行进程各种状态的保存和对新的进程各种状态的恢复。

进程切换主要包括以下工作：

切换全局页目录以加载一个新的地址空间
切换内核栈和硬件上下文，其中硬件上下文包括内核执行新进程需要的全部信息，如CPU相关寄存器

场景：进程A下CPU，进程B上CPU

保存进程A的上下文环境（程序计数器，程序状态字，其他寄存器。。。。）
用新状态和其他相关信息更新进程A的PCB
吧进程A移至合适的队列（就绪、阻塞。。。）
将进程B的状态设置为运行态
从进程B的PCB中恢复上下文（程序计数器、程序状态字、其他寄存器）

上下文切换开销

直接开销：内核完成切换所用的CPU时间

保存和恢复寄存器。。
切换地址空间（相关指令比较昂贵）

间接开销

高速缓存（Cache）、缓冲区缓存（Buffer Cache）和TLB（Translation Lookup Buffer）失效

调度算法衡量指标

吞吐量--每单位时间完成的进程数目
周转时间--每个进程从提出请求到运行完成的时间
响应时间--从提出请求到第一次回应的时间
其他

CPU利用率--CPU做有效工作的时间比例
等待时间--每个进程在就绪队列中等待的时间

调度算法要考虑的问题

进程控制块PCB中需要记录那些与CPU调度有关的信息
进程优先级及就绪队列的组织
抢占式调度和非抢占式调度
I/O密集型与CPU密集型
时间片

进程优先级（数）

静态优先级：进程创建时指定，运行过程中不再改变

动态优先级：进程创建时指定一个优先级，运行过程中可以动态变化

抢占和非抢占

可抢占式：当有比正在运行的进程优先级更高的进程就绪时，系统可强行剥夺正在运行进程的CPU，提供给具有更高优先级的进程使用

不可抢占：某一进程被调度运行后，除非由于它自身的原因不能运行，否则一直运行下去

I/O密集型和CPU密集型

I/O密集型：频繁的进行I/O，通常会花费很多时间等待I/O操作的完成

CPU密集型：需要大量的CPU时间进行运算

时间片

一个时间段，分配给调度上CPU的进程，确定了允许该进程运行的时间长度

如何选择

进程切换的开销
对响应时间的要求
就绪进程个数
CPU能力
进程的行为

批处理系统采用的的调用算法

先来先服务
最短作业优先
最短剩余时间优先
最高相应比优先

先来先服务(first-come,first-serverd)

按照进程就绪的先后顺序使用CPU

非抢占式

优点：公平，实现简单

缺点：长进程后面的短进程需要等待很长时间，不利于用户体验

例子：

三个进程P1，P2，P3，进程P1执行需要24s，P2和P3各需要3s，采用先来先服务算法，周转时间分别为24，27，30，平均周转时间为27s，如果让P2，P3先执行，周转时间为3s，6s，30s，平均周转时间为13s。

最短作业优先(Shortest Job First)

具有最短完成时间的进程优先执行

非抢占式

需要注意的是，在所有的进程都可以运行的情况下，最短作业优先的算法才是最优的。

最短剩余时间优先(Shortest Remaining Time Next)

最短作业优先的抢占式版本，即当一个新就绪的进程比当前运行的进程具有更短的完成时间时，系统抢占当前进程，选择新就绪的进程执行。

进程到达时刻运行时间

P1 0 7

P2 2 4

P3 4 1

P4 5 4

非抢占式

0-7 7-8 8-12 12-16

P1 P3 P2 P4

抢占式

0-2 2-4 4-5 5-7 7-11 11-16

P1 P2 P3 P2 P4 P1

优点：最短的平均周转时间（前提：所有进程同时可运行时，可以得到最短的平均周转时间）

缺点：不公平，后续到来的短任务，使得前面的长任务长时间得不到运行，产生饥饿现象

最高相应比优先（Highest Response Ratio Next）

是一个综合的算法，调度时，首先计算每个进程的响应比R；之后，总是选择R最高的进程执行

响应比R = 周转时间 / 处理时间 = （处理时间+等待时间）/ 处理时间 =1+（等待时间 / 处理时间）

交互式系统采用的的调用算法

轮转调度(round-robin)
最高优先级调度(highest priority first)
多级反馈队列(multiple feedback queue)
最短进程优先(shortest process next)

轮转调度(round-robin)

每个进程都会被分配一个时间片，在这个时间片内允许进程运行。如果时间片结束时进程还在运行的话，则抢占一个 CPU 并将其分配给另一个进程。如果进程在时间片结束前阻塞或结束，则 CPU 立即进行切换。轮询算法比较容易实现。调度程序所做的就是维护一个可运行进程的列表，就像下图中的 a，当一个进程用完时间片后就被移到队列的末尾，就像下图的 b。

如何选择合适的时间片

太长--大于典型的交互时间，降级为先来先服务算法，延长了短进程的响应时间

太短--小于典型的交互时间，频繁的进程切换浪费时间，降低 CPU 效率，延长了响应时间。

最好的切换时间是在 20 - 50 毫秒之间设置。

优点：公平，有利于交互式运算，响应时间快

缺点：进程切换，要花费较高的开销

最高优先级调度算法

选择优先级最高的进程投入运行

通常：

系统进程优先级高于用户进程
前台进程优先级高于后台进程
操作系统更偏好I/O型进程

优先级反转问题

原因：一个低优先级进程持有一个高优先级进程所需要的资源，使得高优先级进程等待低优先级进程运行

影响：高优先级进程停滞不前，导致系统性能降低

解放方案：

设置优先级上限
优先级继承
使用中断禁止

多级反馈队列调度算法

设置多个就绪队列，第一级队列优先级最高
给不同就绪队列中的进程分配长度不同的时间片，第一级队列时间片最小，随着队列优先级别的降低，时间片增大
当第一级队列为空时，在第二级队列调度，以此类推
各级队列按照时间片轮转方式进行调度
当一个新创建进程就绪后，进入第一级队列
进程用完时间片而放弃CPU，进入下一级队列
由于阻塞而放弃CPU的进程进入相应的等待队列，一旦等待的事件发生，该进程回到原来一级就绪队列，可能是队首也可能是队尾，

典型系统采用的调度算法

UNIX：动态优先算法

5.3BSD：多级反馈队列算法

linux：抢占式调度

windows：基于优先级的抢占式多任务调度

Solaris：综合调度算法

windows线程调度

调度单位是线程，采用基于动态优先级、抢占式调度，结合时间配额的调整

就绪线程按优先级进入相应的队列
系统总是选择优先级最高的就绪线程运行
同一优先级的各线程按时间片轮转进行调度
多CPU系统中允许多个线程并行运行

引发线程调度的条件：

一个线程的优先级改变
一个线程改变了它的亲和（affinity）处理机集合（多CPU系统）
线程正常终止或因错误而终止
新线程创建或一个等待线程变成就绪
当一个线程从运行态进入阻塞态
当一个线程从运行态变为就绪态

线程优先级

windows使用32个线程优先级，分成三类

系统线程0，可变优先级1-15，实时优先级16-31

实时优先级线程不改变其优先级

可变优先级线程：其优先级可以在一定范围内升高或降低，会存在两个优先级（基本优先级和当前优先级）

系统线程也叫零页线程，用于对系统中空闲物理页面清零

线程的时间配额

时间配额不是一个时间长度值，而是一个称为配额单位的整数。一个线程用完了自己的时间配额时，如果没有其他相同优先级的线程，windows将重新给该线程分配一个新的时间配额，让他继续运行

时间配额的一个特殊作用

假设用户先启动了一个运行时间很长的电子表格计算程序，然后切换到一个游戏程序（需要复杂图形计算并显示，CPU型），如果前台的优先进程提高了它的优先级，则后台的电子表格计算进程就几乎得不到CPU时间了，但增加游戏进程的时间配额，则不会停止执行电子表格计算，只是给游戏进程的CPU时间多一些而已

1.主动切换

2.抢占

当线程被抢占时，它被放回相应优先级的就绪队列的队首

处于实时优先级的线程在被抢占时，时间配额被重置为一个完整的时间配额

处于可变优先级的线程在被抢占时，时间配额不变，重新得到CPU后将运行剩余的时间配额

2.时间配额用完

线程A的时间配额用完

A的优先级没有降低

如果队列中有其他就绪队列，选择下一个线程执行，A回到原来就绪队列末尾
如果队列没有其他就绪队列。系统会给线程A分配一个新的时间配额，让他进行运行

A的优先级降低了。windows将选择一个更高优先级的线程

windows的调度策略

如何体现对某类线程具有倾向性
如何解决由于调度策略中潜在的不公平性而带来饥饿现象
如何改善系统吞吐量、响应时间等整体特征

解决方案

提升线程的优先级
给线程分配一个很大的时间配额

下列情况，windows会提升线程的当前优先级：

I/O操作完成
信号量或事件等待结束
前台进程中的线程完成一个等待操作
由于窗口活动而唤醒窗口进程
线程处于就绪态超过了一定时间还没有运行即出现了饥饿现象

针对可变优先级范围内（1-15）的线程优先级

例子

I/O操作完成后的线程优先级提升

在完成I/O操作后，windows将临时提升等待该操作线程的优先级，保证该线程能更快上CPU运行进行数据处理
优先级的提升值由设备驱动程序决定，提升建议值保存在系统文件“Wdm.h”或“Ntddk.h”中
优先级的提升幅度与对I/O请求的响应时间要求是一致的，响应时间要求越高，优先级提升幅度越大
设备驱动程序在完成I/O请求时通过内核函数IoCompleteRequest来指定优先级提升的幅度
为避免不公平，在I/O操作完成唤醒等待线程时会将该线程的时间配额减1

饥饿线程的优先级提升

系统线程“平衡集管理器”每秒钟扫描一次就绪队列，发现是否存在等待时间超过300个时钟中断间隔的线程
平衡集管理器将这些线程的优先级提升到15，并分配给它一个长度为正常值4倍的时间配额
当被提升的线程用完它的时间配额后，立即衰减到它原来的基本优先级

进程互斥

由于各进程要求使用共享资源（变量，文件等），而这些资源需要排他性使用，各进程之间竞争使用这些资源。

临界资源：系统中某些资源一次只允许一个进程使用，称这样的资源为临界资源或互斥资源或共享变量。

临界区（互斥区）：各个进程中对某个临界资源（共享变量）实施操作的程序片段。

临界区使用原则

任何时候两个进程不能同时处于临界区
没有进程在临界区时，想进入临界区的进程可进入
位于临界区外的进程不得阻塞其他进程进入临界区
不能使任何进程无限等待进入临界区

实现进程互斥的方案

软件：Dekker解法，Peterson解法

硬件：屏蔽中断，TSL（XCHG）指令

Peterson解法：

 1 #define FALSE 0
 2 #define TRUE  1
 3 /* 进程数量 */
 4 #define N     2                                                    
 5 
 6 /* 现在轮到谁 */
 7 int turn;                    
 8 
 9 /* 所有值初始化为 0 (FALSE) */
10 int interested[N];                                            
11 
12 /* 进程是 0 或 1 */
13 void enter_region(int process){                    
14 
15   /* 另一个进程号 */
16   int other;                                                        
17 
18   /* 另一个进程 */
19   other = 1 - process;                
20 
21   /* 表示愿意进入临界区 */
22   interested[process] = TRUE;                        
23   turn = process;
24 
25   /* 空循环 */
26   while(turn == process 
27         && interested[other] == true){} 
28 }
29 
30 void leave_region(int process){
31   /* 表示离开临界区 */
32   interested[process] == FALSE;                 
33 }

硬件解法

1.中断屏蔽方法

开关中断指令

执行"关中断"指令

临界区操作

执行"开中断"指令

特点：

简单，高效

代价高，限制CPU并发能力

不适用于多处理器

适用于操作系统本身，不适用于用户进程

2.测试并加锁指令

TSL指令：TEST AND SET LOCK

　　它将一个内存字 lock 读到寄存器 RX 中，然后在该内存地址上存储一个非零值。读写指令能保证是一体的，不可分割的，一同执行的。在这个指令结束之前其他处理器均不允许访问内存。执行 TSL 指令的 CPU 将会锁住内存总线，用来禁止其他 CPU 在这个指令结束之前访问内存。很重要的一点是锁住内存总线和禁用中断不一样。禁用中断并不能保证一个处理器在读写操作之间另一个处理器对内存的读写。也就是说，在处理器 1 上屏蔽中断对处理器 2 没有影响。让处理器 2 远离内存直到处理器 1 完成读写的最好的方式就是锁住总线。这需要一个特殊的硬件（基本上，一根总线就可以确保总线由锁住它的处理器使用，而其他的处理器不能使用）为了使用 TSL 指令，要使用一个共享变量 lock 来协调对共享内存的访问。当 lock 为 0 时，任何进程都可以使用 TSL 指令将其设置为 1，并读写共享内存。当操作结束时，进程使用 move 指令将 lock 的值重新设置为 0 。

 1 enter_region:
 2 | 复制锁到寄存器并将锁设为1
 3 TSL REGISTER,LOCK              
 4 | 锁是 0 吗？
 5 CMP REGISTER,#0                             
 6 | 若不是零，说明锁已被设置，所以循环
 7 JNE enter_region                            
 8 | 返回调用者，进入临界区
 9 RET                                              
10 
11 leave_region:
12 
13 | 在锁中存入 0
14 MOVE LOCK,#0                  
15 | 返回调用者
16 RET

3.交换指令

XCHG指令：EXCHANGE

 1 enter_region:
 2 | 把 1 放在内存器中
 3 MOVE REGISTER,#1    
 4 | 交换寄存器和锁变量的内容
 5 XCHG REGISTER,LOCK          
 6 | 锁是 0 吗？
 7  CMP REGISTER,#0     
 8 | 若不是 0 ，锁已被设置，进行循环
 9 JNE enter_region                    
10 | 返回调用者，进入临界区
11 RET                                                     
12 
13 leave_region:                
14 | 在锁中存入 0 
15 MOVE LOCK,#0    
16 | 返回调用者
17 RET

XCHG 的本质上与 TSL 的解决办法一样。所有的 Intel x86 CPU 在底层同步中使用 XCHG 指令。

进程同步

进程同步：系统中多个进程中发生的事件存在某种时序关系，需要相互合作，共同完成一项任务。

具体说，一个进程运行到某个点时，需要另一个伙伴进程为它提供消息，在未获得消息之前，该进程进入阻塞态，获得消息后被唤醒进入就绪态。

信号量

　　信号量是 E.W.Dijkstra 在 1965 年提出的一种方法，它使用一个整形变量来累计唤醒次数，以供之后使用。一个信号量的取值可以是 0 ，或任意正数。0 表示的是不需要任何唤醒，任意的正数表示的就是唤醒次数。Dijkstra 提出了信号量有两个操作，现在通常使用 down 和 up（分别可以用 sleep 和 wakeup 来表示）。down 这个指令的操作会检查值是否大于 0 。如果大于 0 ，则将其值减 1 ；若该值为 0 ，则进程将睡眠，而且此时 down 操作将会继续执行。检查数值、修改变量值以及可能发生的睡眠操作均为一个单一的、不可分割的原子操作(atomic action) 完成。这会保证一旦信号量操作开始，没有其他的进程能够访问信号量，直到操作完成或者阻塞。这种原子性对于解决同步问题和避免竞争绝对必不可少。原子性操作指的是在计算机科学的许多其他领域中，一组相关操作全部执行而没有中断或根本不执行。up 操作会使信号量的值 + 1。如果一个或者多个进程在信号量上睡眠，无法完成一个先前的 down 操作，则由系统选择其中一个并允许该程完成 down 操作。因此，对一个进程在其上睡眠的信号量执行一次 up 操作之后，该信号量的值仍然是 0 ，但在其上睡眠的进程却少了一个。信号量的值增 1 和唤醒一个进程同样也是不可分割的。不会有某个进程因执行 up 而阻塞，正如在前面的模型中不会有进程因执行 wakeup 而阻塞是一样的道理。

用信号量解决进程间互斥问题

分析并发进程的关键活动，划定临界区

设置信号量mutex，初值为1

在临界区前实施down

在临界区后实施up

管程

管程是程序、变量和数据结构等组成的一个集合，它们组成一个特殊的模块或者包。进程可以在任何需要的时候调用管程中的程序，间接访问管程中的数据结构，但是它们不能从管程外部访问数据结构和程序。

管程是互斥进入的，为了保证管程中数据结构的数据完整性，管程的互斥性是由编译器负责保证的。

管程中设置条件变量及等待唤醒操作以解决同步问题。具体为让一个进程或线程在条件变量上等待（此时，应先释放管程的使用权），也可以通过发送信号将等待在条件变量上的进程或线程唤醒。

HOARE管程

当一个进程试图进入一个已被占有的管程时，应当在管程的入口处等待。为此，管程的入口处设置一个进程等待队列，称作入口等待队列

如果进程P唤醒进程Q，则P等待Q执行；如果进程Q执行中又唤醒进程R，则Q等待R执行；。。。如此，在管程内需设置一个进程等待队列，称为紧急等待队列，紧急等待队列的优先级高于入口等待队列的优先级。

条件变量--在管程内部说明和使用的一种特殊类型的变量

对于条件变量，可以执行wait和signal操作

wait（c）：如果紧急等待队列非空，则唤醒第一个等待者；否则释放管程的互斥权，执行此操作的进程进入条件变量链末尾

signal（c）：如果条件变量链为空，则相当于空操作，执行此操作的进程继续执行，否则唤醒第一个等待者，执行此操作的进程进入紧急等待队列。

MESA管程

HOARE管程存在缺点：两次额外的进程切换

解决：signal ------> notify

notify：当一个正在管程中的进程执行notify（x）时，它使得x条件队列得到通知，发信号的进程继续执行，

notify结果：位于条件队列头的进程在将来合适的时候且当处理器可用时恢复执行。

改进：增加超时时间，防止出现饥饿现象。引入broadcast，所有等待进程都被唤醒并进入就绪队列

PTHREAD中的同步机制

互斥量（保护临界区）

线程调用	描述
Phread_mutex_init	创建一个互斥量
Pthread_mutex_destroy	撤销一个已存在的互斥量
Pthread_mutex_lock	获得一个锁或堵塞
Pthread_mutex_trylock	获得一个锁或失败
Pthread_mutex_unlock	释放一个锁

条件变量（解决同步）

线程调用	描述
Pthread_cond_init	创建一个条件变量
Pthread_cond_destroy	销毁一个条件变量
Pthread_cond_wait	阻塞并等待一个信号
Pthread_cond_signal	向另一个线程发信号来唤醒它
Pthread_cond_broadcast	向多个线程发信号来唤醒他们

进程间通信(Inter Process Communication, IPC)

信号量及管程只能传递简单信息，不能传递大量信息，管程也不适用于多处理器情况，所以需要引入通信机制。

进程通信机制

消息传递（使用两个原语 send 和 receive），适用于：分布式系统、基于共享内存的多处理机系统、单处理机系统可以解决进程间的同步问题、通信问题。

基本通信方式

消息传递
共享内存
管道
套接字
远程过程调用

消息传递：

操作系统空间存在一组消息缓冲区，消息缓冲区结构：消息头（消息类型、接收进程ID、发送进程ID、消息长度、控制信息），消息体（消息内容）。首先，发送线程S，陷入内核，操作系统复制消息到缓冲区，然后把消息的地址挂接到接收进程的PCB中消息队列末尾，消息队列会有指针指向消息缓冲区的地址。等到接收进程拿到CPU的执行权后，执行到receive原语时，接收进程R陷入内核，操作系统把消息复制接收进程的地址空间。

共享内存：

管道：

利用一个缓冲传输介质--内存或文件连接两个相互通信的进程

典型操作系统的IPC机制

unix

管道、消息队列、共享内存、信号量、信号、套接字

linux

管道、消息队列、共享内存、信号量、信号、套接字

内核同步机制：

原子操作、自旋锁、读写锁、信号量、屏障、BKL

windows

套接字、文件映射、管道、命名管道、邮件槽、剪贴板、动态数据交换、对象接连和嵌入、动态链接库、远程过程调用

同步对象：

互斥对象、事件对象、信号量对象、临界区对象、互锁变量

屏障

一种同步机制（又称栅栏、关卡）

用于对一组线程进行协调

应用场景：

一组线程协同完成一项任务，需要所有线程到达一个汇合点在一起向前推进