0 前言

个人学习、整理和记录操作系统相关知识点用。其中大部分内容来自以下地址，表示感谢。
5万字、97 张图总结操作系统核心知识点
 cyc-计算机操作系统
 2.5w字 + 36 张图爆肝操作系统面试题，太牛逼了！
进程间通信IPC (InterProcess Communication)

1 概览

1.1 什么是操作系统

操作系统是管理硬件和软件资源的一种应用程序。它是运行在计算机上最重要的一种软件，它管理计算机的资源和进程以及所有的硬件和软件。为计算机硬件和软件提供了一种中间层，使应用软件和硬件进行分离，让我们无需关注硬件的实现，把关注点更多放在软件应用上。

通常情况下，计算机上会运行着许多应用程序，它们都需要内存和CPU进行交互，操作系统的目的就是为了保证这些访问和交互能够准确无误的进行。

1.2 操作系统的主要功能

一般来说，现代操作系统主要提供下面几种功能：
1.进程管理：进程管理的主要作用就是任务调度，在单核处理器下，操作系统会为每个进程分配一个任务，进程管理的工作十分简单；而在多核处理器下，操作系统除了要为进程分配任务外，还要解决处理器的调度、分配和回收等问题。
2.内存管理：内存管理主要是操作系统负责管理内存的分配、回收，在进程需要内存时分配内存，以及进程完成时回收内存，协调内存资源，通过合理的页面置换算法进行页面的换入换出。
3.设备管理：根据确定的设备分配原则对设备进行分配，使设备与主机能够并行工作，为用户提供良好的设备使用界面。
4.文件管理：有效地管理文件的存储空间，合理地组织管理文件系统，为文件访问和文件保护提供更有效的方法及手段。
5.提供用户接口：操作系统提供了访问应用程序和硬件的接口，使用户能够通过应用程序发起系统调用，从而操纵硬件，实现想要的功能。
以上是操作系统主要功能的大意，后文会对部分功能展开讲解。

1.3 相关概念

操作系统有四个相关概念需要重点理解：并发性、共享性、虚拟性、异步性。

1.3.1 并发

并发是指宏观上在一段时间内能同时运行多个程序，而并行是指同一时刻能运行多个指令。并行需要硬件支持，比如流水线、多核处理器或者分布式计算系统。
再次理解并发和并行：
并发是指两个或多个事件可以在同一时间间隔发生；
并行是指两个或多个事件可以在同一时刻发生；

1.3.2 共享

共享是指系统中的资源可以被多个并发进程共同使用，这种共同使用的形式称之为资源共享。
资源共享根据属性，可以分为两种方式：
1.互斥共享：互斥共享的资源称为临界资源，在同一时刻，只允许一个进程访问，需要用同步机制来实现互斥访问。比如打印机被某一个进程A使用了，那么其他想打印的进程，只能等待A使用完成之后，才能使用打印机功能。
2.同时访问：某一个资源在一段时间内并发地被多个进程访问，这种“同时”是宏观的，从宏观的角度去看，该资源可以被同时访问，比如说我们在使用硬盘的时候，进程A和进程B都想写入数据，因为悬臂只有一个，那么当A写数据时，B不能写，但是由于写数据比较快，且A和B并发，所以我们在一段时间内去观察它，可以认为它可以被同时访问。如果我们强调一段时间内并发的去使用，那么其实就是共享性的同时访问形式。

1.3.3 虚拟

虚拟性表现在把一个物理实体转变为若干个逻辑实体，物理实体是真实存在的（可能是计算机中的某一个设备），逻辑实体是虚拟的。
虚拟的实现技术有两种，时（时间）分复用技术和空（空间）分复用技术。
1.时分复用技术
多个进程能同时在同一个处理器上并发执行使用了时分复用技术，让每个进程轮流占用处理器，每次只执行一小个时间片并快速切换
2.空分复用技术
虚拟内存使用了空分复用技术，它将物理内存抽象为地址空间，每个进程都有各自的地址空间。地址空间的页被映射到物理内存，地址空间的页并不需要全部在物理内存中，当使用到一个没有在物理内存的页时，执行页面置换算法，将页面换到内存中。

1.3.4 异步

异步表现为在多道程序环境下，允许多个程序并发的执行，进程在使用资源时可能需要等待或放弃，进程的执行不是一气呵成的，而是以走走停停的形式推进（假设某一个进程在运行到某一时刻时，需要使用某一个资源，如果这个资源被占用的话，可能这个进程就会停止或者是等待资源被释放）。

上图的红线为一个时间推进的时间轴，有A、B、C三个程序在交替运行，假如某一时刻，A释放了打印机资源，同时B和C都需要使用这个打印机资源，那么B和C就会发生竞争，但是谁先抢占到资源是不可知的，所以，进程是以不可预知的速度向前推进的，不知道何时执行、何时暂停、何时完成，这么多不可预知的事，导致了程序的异步性。

1.4 计算机硬件

计算机硬件是计算机的重要组成部分，其中包含了5个部分：运算器、控制器、存储器、输入设备、输出设备。

1.4.1 组成部分

运算器：运算器最主要的功能是对数据和信息进行加工运算。它是计算机中执行算数和各种逻辑运算的部件。运算器的基本运算包括加、减、乘、除、位移等操作，这些是由算数逻辑单元实现的。而运算器主要由算数逻辑单元和寄存器构成。
控制器：指按照指定顺序改变主电路或控制电路的部件，它主要起到了控制命令执行的作用，完成协调和指挥整个计算机系统的操作。控制器是由程序计数器、指令寄存器、解码译码器等构成。
（运算器和控制器共同组成了CPU）
存储器：存储器就是计算机的记忆设备，顾名思义，存储器可以保存信息，存储器分为两种，一种是主存，也就是内存，它是CPU主要交互对象，还有一种是外存，比如硬盘软盘等。
输入设备：输入设备是给计算机获取外部信息的设备，主要包括鼠标键盘。
输出设备：输出设备是给用户呈现根据输入设备获取的信息经过一系列的计算后得到显示的设备，主要包括显示器、打印机等。

1.4.2 冯·诺依曼体系结构

上述的五部分也是冯·诺依曼体系结构，它认为计算机应该具有如下功能：
把需要的程序和数据送至计算机中。必须具有长期记忆程序、数据、中间结果及最终运算结果的能力。能够完成各种算术、逻辑运算和数据传送等数据加工处理的能力。能够根据需要控制程序走向，并能根据指令控制机器的各部件协调操作。能够按照要求将处理结果输出给用户。

1.4.3 详细硬件分类

下面是一张intel家族产品图，是一个详细的计算机硬件分类

总线（Buses）：在整个系统中运行的是称为总线的电气管道的集合，这些总线在组件之间来回传输字节信息。通常总线被设计成传送定长的字节块，也就是字（word）。字中的字节数（字长）是一个基本的系统参数，各个系统中都不尽相同。现在大部分的字都是4个字节（32位）或者8个字节（64位）。

I/O设备（I/O Devices）：Input/Output设备是系统和外部世界的连接。用于用户输入的键盘鼠标，用于用户输出的显示器，一个磁盘驱动用来长时间的保存数据和程序。每个IO设备连接IO总线都被称为控制器（controller）或者适配器（Adapter）。控制器和适配器之间的主要区别在于封装方式。控制器是IO设备本身或者系统的主印制板电路（主板）上的芯片组。而适配器则是一块插在主板插槽上的卡。无论组织形式如何，他们的目的都是彼此交换信息。

主存（Main Memory）：是一个临时存储设备，而不是永久性存储，磁盘是永久性存储的设备。主存既保存程序，又保存处理器执行流程所处理的数据。从物理组成上说，主存是由一系列DRAM（dynamic randon access memory）动态随机存储构成的集合。逻辑上说，内存就是一个线性的字节数组，有它唯一的地址编号，从0开始。一般来说，组成程序的每条机器指令都由不同数量的字节构成，C程序变量相对应的数据项的大小根据类型进行变化。比如在Linux的X86-64机器上，short类型的数据需要2个字节，int和float需要4个字节，而long和double需要8字节。

处理器（Processor）：CPU（Central Processing Unit）或者简单的处理器，是解释执行存储在主存储器中的指令的引擎。处理器的核心大小为一个字的存储设备（或寄存器），称为程序计数器（PC）。在任何时刻，PC都指向主存中的某条机器语言指令（即含有该条指令的地址）。从系统通电开始，直到系统断电，处理器一直在不断地执行程序计数器指向的指令，再更新程序计数器，使其指向下一条指令。处理器根据其指令集体系结构定义的指令模型进行操作。在这个模型中，指令按照严格的顺序执行，执行一条指令涉及一系列的步骤。处理器从程序计数器指向的内存中读取指令，解释指令中的位，执行该指令指示的一些简单操作，然后更新程序计数器以指向下一条指令。指令与指令之间可能连续，可能不连续（不如jump指令就不会顺序读取）。

几个CPU执行简单操作的步骤
1.加载（Load）：从主存中拷贝一个字节或者一个字到内存中，覆盖寄存器先前的内容。
2.存储（Store）：将寄存器中的字节或字复制到主存储器中的某个位置，从而覆盖该位置的先前内容
3.操作（Operate）：把两个寄存器的内容复制到ALU（Arithmetic Logic Unit，算术逻辑单元，是对数字二进制数执行算术和按位运算的组合数字电子电路）。把两个字进行算术运算，并把结果存储在寄存器中，重写寄存器先前的内容。

1.5 宏内核和微内核

1.5.1 宏内核

是将操作系统功能作为一个紧密结合的整体放到内核。由于各模块共享信息，因此有很高的性能。

1.5.2 微内核

由于操作系统不断复杂，因此将一部分操作系统功能移出内核，从而降低内核的复杂性。移出的部分根据分层的原则划分成若干服务，相互独立。
在微内核结构下，操作系统被划分成小的、定义良好的模块，只有微内核这一个模块运行在内核态，其余模块运行在用户态。因此需要频繁地在用户态和内核态之间进行切换，所以有一定的性能损失。

2 进程管理

2.1 进程

进程是操作系统最核心的概念，是对正在运行的程序的一个抽象，是系统进行资源分配和调度的基本单位。一个进程就是一个正在执行的程序的实例，进程也包括程序计数器。寄存器和变量的当前值，从概念上来说，每个进程都有各自的虚拟CPU，但是实际情况是CPU会在各个进程之间进行来回切换。

2.1.1 进程控制块

在主存里边，进程也是一段连续的存储空间，这个空间称作进程控制块（Process Control Block，PCB），描述进程的基本信息和运行状态，所谓的创建进程和撤销，都是指对PCB的操作。在PCB中有一些重要的信息，比如标识符、状态、优先级、程序计数器、内存指针、上下文数据、IO状态信息、记账信息等等。

标识符：唯一标记一个进程的符号，用于区别其他进程。比如我们常见的进程ID，就是这个唯一的标识符；
状态：标记进程的进程状态。如运行状态或者阻塞状态；
程序计数器：进程即将被执行的下一条指令的地址；
内存指针：程序代码或者进程数据相关指针。内存指针可能有多个，分别指向程序具体的逻辑代码，或者执行进程数据相关的地址；
上下文数据：这个是PCB中比较重要的区域，这个区域存储的是进程执行时处理器存储的数据（在处理器中有寄存器以及高速缓存，这些数据就是进程的上下文数据）；
IO状态信息：被进程IO操作所占用的文件列表（在Linux中，所有的信息都是以文件的形式存在的，比如操作磁盘、文件或者内存，都是以文件的形式存储在IO状态信息中）；
记账信息：进程所使用的CPU时间，或者时钟总和。

以上的PCB信息，可以分为四类：

进程控制块PCB的详细定义：
1.用于描述和控制进程运行的通用数据结构（每一个进程都有PCB）；
2.记录进程当前的状态和控制进程运行的全部信息；
3.是使得进程能够独立运行的基本单位（也就是说，每一个进程都依赖PCB去被操作系统调度，或者说被控制）；
4.是操作系统进行调度经常会被读取的信息，所以PCB是常驻内存的，存放在系统专门开辟的PCB区域内。

2.1.2 进程状态

1.三态模型
当一个进程开始运行时，会经历三种状态

三种状态：
运行态：运行态指的是进程实际占用CPU时间片运行时；
就绪态：就绪态指的是可运行，但因为其他进程正在运行而处于就绪状态；
阻塞态：阻塞态有称为睡眠态，它指的是进程不具备运行条件，正在等待被CPU调度。

逻辑上来说，运行态和就绪态是很相似的，这两种情况下都表示进程可运行，但是就绪态没有获得CPU时间分片。阻塞态与前两种状态的不同是这个进程不能运行，哪怕CPU空闲也不能运行。

三种状态会涉及四种状态间转换，在操作系统发现进程不能继续执行时，会发生状态1的轮转，在某些系统中进程执行系统调用（如pause），来获取一个阻塞的状态。一些其他系统中包括UNIX，当进程从管道或特殊文件（如终端）中读取没有可用的输入时，该进程会自动终止。转换2和3都是由进程调度程序（操作系统的一部分）引起的，进程本身不知道调度程序的存在。转换2的出现说明进程调度器认定当前进程已经运行了足够长的时间，是时候让其他进程运行CPU时间片了。当所有其他进程都运行过后，这时候该让第一个进程重新获得CPU时间片，就会发生转换3。当进程等待的一个外部事件发生时，则发生转换4.如果此时没有其他进程运行，则立即触发转换3。

2.进程的五态模型
在三态的基础上增加了两个状态，新建和终止。

新建态：进程的新建态就是进程刚创建出来的时候。创建进程需要两个步骤，即为新进程分配所需要的资源和空间，设置进程为就绪态，并等待调度执行。
终止态：指进程执行完毕，到达结束点，或者因为错误而不得不终止进程。终止一个进程需要两个步骤：1.等待操作系统或相关的进程进行善后处理；2.回收占用的资源并被系统删除。

2.1.3 进程的实现

操作系统为了执行进程间的切换，会维护一张表，这张表就是进程表（Process Table）。每个进程占用一个进程表项，该表项保护了进程状态的重要信息，包括程序计数器、堆栈指针、内存分配状况、所打开文件的状态、账号和调度信息、以及其他在进程由运行态转换到就绪态和阻塞态时所必须保存的信息。
下面展示了一个典型系统中的关键字段

其中第一列与进程管理有关，第二列与存储管理有关，第三列与文件管理有关。
与每一IO类相关联的是一个称作中断向量（Interrupt Vector）的位置，它包含中断服务程序的入口地址。假设当一个磁盘中断发生时，用户进程3正在运行，则中断硬件将持续计数器、程序状态字、寄存器压入堆栈，计算机随即跳转到中断向量所指示的地址，这就是硬件所做的事，然后软件接管剩余工作。
当中断结束后，操作系统会调用一个C程序来处理中断剩下的工作。在完成剩下的工作后，会使某进程就绪，接着调用调度程序，决定随后运行哪个进程。然后将控制权转移给一段汇编语言代码，为当前的进程装入寄存器值以及内存映射，并启动该进程运行，具体过程如下：
1.硬件压入堆栈程序计数器等；
2.硬件从中断向量装入新的程序计数器；
3.汇编语言过程保存寄存器的值；
4.汇编语言过程设置新的堆栈；
5.C中断服务器运行（典型的读和缓存写入）；
6.调度器决定下面哪个程序先运行；
7.C过程返回至汇编代码；
8.汇编语言过程开始运行新的当前进程。
一个进程在执行过程中可能被中断数千次，但关键每次中断后，被中断的进程都返回到与中断发生前完全相同的状态。

2.2 线程

线程是进程中的一个执行任务（控制单元），负责当前进程中程序的执行。一个进程至少有一个线程，或者多个线程，多个线程可以共享数据。与进程不同的是，同一个进程下的多个线程共享堆和方法区资源，但每个线程有自己的程序计数器、虚拟机栈和本地方法栈，所以系统在产生一个线程，或是各个线程切换工作时，负担要比进程小。

2.2.1 经典线程模型

进程中拥有一个执行的线程，通常简写为线程（Thread）。线程会有程序计数器，用来记录接着要执行哪一条指令；线程实际上是CPU调度执行的实体。

下图为三个进程，每个进程有自己的地址空间和单个控制线程，每个线程都在不同的地址空间中运行

下图是一个进程中有三个线程的情况，每个线程都在相同的地址空间中运行

线程不像是进程那样具备较强的独立性。同一个进程中的所有线程都会有完全一样的地址空间，这意味着他们共享同样的全局变量。由于每个线程都可以访问进程地址空间内每个内存地址，因此一个线程可以读取、写入和擦除另一个线程的堆栈。线程之间除了共享同一内存空间外，还具有如下不同内容

上图左边是同一个进程中，每个线程共享的内容，右边是每个线程中的内容。也就是说左边的列表是进程的属性，右边的列表是线程的属性。

2.2.2 线程状态

线程之间的状态转换和进程之间的状态转换是一样的。
进程通常会从当前的某个单线程开始，然后这个线程通过调用库函数（如thread_create）创建新的线程。线程创建的函数会要求指定新创建线程的名称。创建的线程通常都返回一个线程标识符，该标识符就是新线程的名字。当一个线程完成工作后，可以通过调用函数（如thread_exit）来退出。紧接着线程消失，状态变为终止，不能再进行调度。在某线程的运行过程中，可以通过函数thead_join，来表示一个线程可以等待另一个线程退出。这个过程阻塞调用线程直到等待特定的线程退出。这种情况下，线程的创建和终止非常类似于进程的创建和终止。另一个常见的调用是thread_yield，它允许线程自动放弃CPU从而让另一个线程运行。这个调用还是很重要的，因为不同于进程，线程是无法利用时钟中断强制让线程让出CPU的。

2.2.3 线程实现

主要有三种实现方式：在用户空间中实现线程、在内核空间中实现线程、两种混合实现线程。

1.在用户空间中实现线程
是把整个线程包放在用户空间中，内核对线程一无所知，设置都不知道线程的存在，所有的这类实现都有同样的通用结构

线程在运行时系统之上运行，运行时系统是管理线程过程的集合，包括前面提到的四个过程：pthread_create,pthread_exit,pthread_join,pthread_yield。

2.在内核中实现线程
当某个线程希望创建一个新线程或撤销一个已有线程时，它会进行一个系统调用，这个系统调用通过对线程表的更新来完成线程创建或销毁工作。

内核中的线程表持有每个线程的寄存器、状态和其他信息，这些信息和用户空间中的线程信息相同，但是位置却被放在内核中而不是用户空间中。另外，内核还维护了一张进程表用来跟踪系统状态。
所有能够阻塞的调用都会通过系统调用的方式来实现，当一个线程阻塞时，内核可以进行选择，是运行在同一个进程中的另一个线程（如果有就绪线程的话）还是运行一个另一个进程中的线程。但是在用户实现中，运行时系统始终运行自己的线程，直到内核剥夺它的 CPU 时间片（或者没有可运行的线程存在了）为止。

3.混合实现
结合了用户空间和内核空间的优点，设计人员采用一种内核级线程的方式，然后将用户级线程与某些内核线程多路复用起来

在这种模型中，编程人员可以自由控制用户线程和内核线程的数量，具有很大的灵活度。采用这种方法，内核只识别内核级线程，并对其进行调度。其中一些内核级线程会被多个用户级线程复用。

2.2.4 进程和线程的区别

1.拥有资源。进程是资源分配的基本单位，但是线程不拥有资源，线程可以访问隶属进程的资源。
2.调度。线程是独立调度的基本单位，在同一个进程中，线程的切换不会引起进程切换，从一个进程中的线程切换到另一个进程的线程时，会引起进程切换。
3.系统开销。由于创建或撤销进程时，系统都要为之分配回收资源（如内存空间、IO设备等），所付出的开销远大于创建或撤销线程时的开销。类似地，在进行进程切换时，涉及当前执行进程CPU环境的保存及新调度进程CPU环境的设置，而线程切换只需要保存少量寄存器内容，开销很小。
4.通信方面。线程间可以通过直接读写同一进程中的数据进行通信，但是进程间通信需要借助IPC。

2.3 进程间通信

2.3.1 基本概念

进程间通信（Inter-Process Communication，IPC）方式比较多，在此之前，先了解几个概念：
1.竞态条件（Race Confition）：即两个或多个线程同时对一共享数据进行修改，从而影响程序运行的正确性时，这种就被称为竞态条件。
2.临界区：不仅共享资源会造成竞态条件，共享文件、共享内存也会造成竞态条件。那么应该怎么避免呢？一句话概括：禁止一个或多个进程在同一时刻对共享资源（包括共享文件、共享内存）进行读写。也就是说，需要一种互斥（Mutual Exclusion）条件，即如果一个进程在某种方式下使用共享变量和文件，除该进程之外的其他进程就禁止再访问（访问统一资源）。这就是临界区。
一个好的临界区解决方案，应该包含下面四种条件：
a.任何时候两个进程不能同时处于临界区；
b.不应对CPU的速度和数量做任何假设；
c.位于临界区的进程不得阻塞其他进程；
d.不能使任何进程无限等待进入临界区。

3.忙等互斥：当一个进程对资源进行修改时，其他进程必须进行等待，进程之间具有互斥性，一下方案都是基于忙等互斥提出的。

2.3.2 IPC方式

信号

信号是UNIX系统最先开始使用的进程间通信机制，因为Linux继承于UNIX，所以Linux也支持信号机制，通过想一个或多个进程发送异步事件信号来实现，信号可以从键盘或者访问不存在的位置等地方产生；信号通过shell将任务发送给子进程。在Linux系统上输入kill -l可以列出系统使用的信号，如下图：

进程可以选择忽略发送过来的信号，但是有两个不能忽略，SIGSTOP和SIGKILL。SIGSTOP信号会通知当前正在运行的进程执行关闭操作，SIGKILL信号会通知当前进程应该被杀死。除此之外，进程可以选择它要处理的信号，进程也可以选择阻止信号，如果不阻止，可以选择自行处理，或者是交给内核处理，如果是内核处理，那么会执行默认处理。
操作系统会中断目标程序的进程来向其发送信号，在任何非原子指令中，执行都可以中断，如果进程已经注册信号处理程序，那么就会执行进程，如果没有，将采用默认处理的方式。

管道pipe

Linux系统中的进程可以通过管道pipe进行通信，在两个进程之间，建立一个通道，一个进程向通道写入字节流，另一个进程从这个管道中读取字节流。管道是同步的，当进程尝试从管道读取数据时，该进程会被阻塞，直到有可用数据为止。shell中的管道pipelines就是通过管道实现的，当shell发现输出

sort <f | head

他会创建两个进程，一个是sort，一个是head，且会在这两个进程之间建立一个管道使sort进程的标准输出作为head的标准输入。sort进程产生的输出不会写到文件中，如果管道满了，系统会停止sort，以等待head读出数据。

管道是半双工通信，数据只能单向交替传输，且只能用于父子进程或者兄弟进程。管道单独构成一种独立的文件系统，它对于两端的进程而言，就是一个文件，但是这个文件比较特殊，只存在于内存中。一个进程向管道写入数据，写入内容每次都添加在管道缓冲区末尾，另外一个进程从缓冲区头部读出数据。

先入先出队列FIFO

通常也被称为命名管道（Named Pipes），工作方式与常规的管道相似。有名管道不同于匿名管道之处在于，它提供了一个路劲名与之关联，以有名管道的文件形式存在于文件系统中，这样，即使与有名管道的创建进程不存在亲缘关系的进程，只要可以访问该路径，就能够彼此通过有名管道相互通信，解决了匿名管道只能在亲缘进程间通信的限制。

共享内存

允许多个进程共享一个给定的存储区（类似线程间通信），因为数据不需要在进程之间复制，是最快的IPC方式。但由于多个进程共享一段内存，因此需要依靠某种同步机制来达到进程间的同步和互斥，通常使用信号量机制。
信号量（Semaphore）：是一个计数器，可以用来控制多个进程对共享资源的访问，常作为一种锁机制，防止某进程正在访问资源时，其他进程也在访问。主要作为进程间以及线程间的同步手段。
mmap，是一种内存映射文件的方法，即将一个文件或者其他对象映射到进程的地址空间，实现文件磁盘地址和进程虚拟地址空间中一段虚拟地址的一一对应关系。实现这样的映射之后，进程就可以采用指针的方式读写这一段内存，而系统会自动回写脏页面到对应的文件磁盘上，即完成了对文件的操作而不必再调用read。write等系统调用函数。相反，内核空间对这段区域的修改也直接放映用户空间，从而可以实现不同进程的文件共享。是Linux系统中常用共享内存的实现方式，android开源库MMKV也是基于此原理实现。

消息队列Message Queue

消息队列是存放在内核的消息链表，每个消息队列由消息队列标识符表示。
消息队列的特点：
1.消息队列是消息的链表，具有特定的格式，存放在内存中，并由消息队列标识符标识；
2.允许一个或多个进程向他写入与读取消息；
3.管道和消息队列的通信数据都是先进先出；
4.消息队列可以实现消息的随机查询，消息不一定要以先进先出的顺序读取，也可以按消息的类型读取，比FIFO更有优势。
5.消息队列克服了信号承载信息量少，管道只能承载无格式字节流以及缓冲区大小受限等缺陷；
6.目前主要有两种类型的消息队列：POSIX消息队列以及System V消息队列，后者被大量使用。Ststem V（系统V）消息队列是随内核持续的，只有在内核重启或者人工删除时，该消息队列在会被删除。

相比与FIFO，消息队列有以下优点：
1.消息队列可以独立于读写进程存在，从而避免了FIFO中同步管道的打开和关闭时可能产生的困难；
2.避免了FIFO的同步阻塞问题，不需要进程自己提供同步方法；
3.读进程可以根据消息类型有选择地接收消息，而不像FIFO那样只能默认地接收。

套接字 Socket

套接字是常用的网络通信机制，可以实现不同主机之间，通过网络进行通信，也可以实现同一主机的不同进程通信。

2.4 进程调度

当一个计算机是多道程序设计系统时，会频繁的有很多进程或者线程来同时竞争CPU时间片。这时就需要一个调度程序（Scheduler）的角色，来选择哪个进程/线程可以使用CPU，该程序的算法叫做调度算法（Scheduling Algorithm）。

2.4.1 调度算法分类

在不同的环境下，调度算法的目标不同，因此需要的算法也不同。主要有以下三种环境：
1.批处理（Batch）：商业领域；
2.交互式（Interactive）：交互式用户环境；
3.实时（Real time）。
下面会讨论不同环境下的调度算法。

2.4.2 批处理中的调度

批处理系统没有太多的用户操作，在该系统中，调度算法的目标是保证吞吐量和周转时间（从提交到终止的时间）。

1.先来先服务
先来先服务（first-come first-serverd，FCFS），非抢占式的调度算法，按照请求的顺序进行调度，是最简单的调度算法。当一个任务从外部进入系统时，将会立即启动并允许运行任意长的时间。它不会因为运行时间太长而中断。当其他作业进入时，他们会排到就绪队列尾部。当正在运行的进程阻塞，处于等待队列的第一个进程就开始运行。当一个阻塞的进程重新处于就绪态时，它就会像一个新到达的任务一样，排在队列末尾，即所有进程最后。

这个算法的优点是易于理解和编程。在这个算法中，一个单链表记录了所有就绪进程，要选取一个进程运行，只要从该对列的头部移走一个进程即可。要添加一个新的作业或者阻塞一个进程，只要把进程附加在队列的末尾即可。
特点：有利于长作业，不利于短作业。因为短作业必须等待前面的长作业执行完才能执行，而长作业又需要很长的时间，造成短作业等待时间过长。

2.最短作业优先
最短作业优先（Shortest Job Firsr，SJF），非抢占式的调度算法，按估计运行时间最短的顺序进行调度。

特点：长作业有可能会被饿死，处于一直等待短作业执行完毕的状态，因为如果一直有短作业到来，那么长作业就永远得不到调度。

3.最短剩余时间优先
最短剩余时间优先（Shortest Remaining Time Next，SRTN），是最短作业时间的抢占式版本，按剩余运行时间的顺序进行调度。当一个新的作业到达时，其整个运行时间与当前进程的剩余时间做比较，如果新的进程同时更少，则挂起当前进程，运行新进程，否则新进程等待。

2.4.3 交互式中的调度

交互式系统有大量的用户交互操作，该系统中调度算法的目标是快速进行响应。
1.轮询调度
也称为时间片轮转，是一种最古老、最简单、最公平并且最广泛使用的算法。
系统先将就绪进程按FCFS的原则排成一个队列，每次调度时，把CPU时间分配给队首进程，该进程可以执行一个时间片。当时间片用完时，由计时器发出时钟中断，调度程序便停止该进程的执行，并将它送往就绪队列的末尾，同时继续把CPU时间分配给队首的进程。

其中时间片的大小和算法的效率有很大关系，因为进程切换都要保存进程的信息并且载入新进程信息，如果时间片太小，会导致进程切换得太频繁，反而在进程切换上面花过多时间；而如果时间片太长，那我实时性就得不到保证。

2.优先级调度
轮询调度假设了所有的进程是同等重要的，但事实情况可能不是。优先级调度就是考虑到这种情况，给每个进程分配一个优先级，然后按照优先级进行调度。为了防止低优先级的进程永远得不到调度，可以随着时间的推移增加等待进程的优先级。

3.多级反馈队列
一个进程需要执行100个时间片，如果采用时间片轮转调度算法，那么就需要交换100次。多级队列就是为这种需要执行多个时间片的进程考虑，它设置了多个队列，每个队列时间片大小都不同，例如1、2、4、8这样的。进程在第一个队列没执行完，就会被移到下一个队列，可以大幅减少大作业的进程交换次数。
每个队列优先权也不同，最上面的优先权最高，因此只有上一个队列没有进程在排队，才能调度当前队列上的进程，这种算法可以看作是时间片轮转调度和优先级调度的结合。

4.最短进程优先
是根据进程过去行为进行推测，并执行估计运行时间最短的那个进程。

5.保证调度
一种完全不同的调度方法是对用户做出明确的性能保证。一种实际而且容易实现的保证是：若用户工作时有n个用户登录，则每个用户将获得CPU处理能力的1/n。类似地，在一个有n个进程运行的单用户系统中，若所有的进程都等价，则每个进程将获得1/n的CPU时间。

6.彩票调度
基本思想是为进程提供各种系统资源（如CPU时间）的彩票，当做出一个调度决策的时候，随机抽出一张彩票，拥有该彩票的进程获得资源。

7.公平分享调度
目前为止，我们假设被调度的都是各个进程自身，而不用考虑该进程的拥有者是谁。存在一种情况，如果用户1启动了9个进程，而用户2启动了一个进程，使用轮转或相同优先级调度算法，那么用户1将得到90%的CPU时间，而用户2只能得到10%。为了防止这种情况的出现，一些系统在调度前会把进程拥有者考虑在内。这种模型下，每个用户都分配一些CPU时间，然后再用分配得的时间进行调度。假如两个用户都有50%的时间片，那么不管用户有多少进程，都可以获得相同的CPU份额。

2.4.4 实时系统中的调度

实时系统要求一个请求在一个确定时间内得到响应。又分为硬实时和软实时，前者必须满足绝对的截止时间，后者可以容忍一定的超时。

2.5 进程同步

同步是指多个进程因为合作产生的直接制约关系，使得进程有一定的先后执行关系。

信号量

上文有简单提到信号量，下面详细说说。信号量（Semaphore）是一个整型变量，可以对其执行down和up操作，也就是常见的P和V操作。
down：如果信号量大于0，执行-1操作；如果信号量等于0，进程睡眠，等待信号量大于0；
up：对信号量执行+1操作，唤醒睡眠的进程让其完成down操作。
如果信号量的取值只能是0或者1，那么就成为了互斥量（Mutex），0表示临界区已经加锁，1表示临界区解锁。

用信号量实现生产者-消费者问题
问题描述：使用一个缓冲区来保存物品，只有缓冲区没有满，生产者才可以放入物品；只有缓冲区不为空，消费者才可以拿走物品。
因为缓冲区属于临界资源，因此需要使用一个互斥量mutex来控制对缓冲区的互斥访问。
为了同步生产者和消费者的行为，需要记录缓冲区中物品的数量。数量可以使用信号量来进行统计，这里需要使用两个信号量，empty记录空缓冲区的数量，full记录满缓冲区的数量。其中，empty信号量是在生产者进程中使用，当empty不为0时，生产者才可以放入物品；full信号量是在消费者进程中使用，当full不为0时，消费者才可以取走物品。
伪代码如下

#define N 100
typedef int semaphore;
semaphore mutex = 1;
semaphore empty = N;
semaphore full = 0;

void producer() {
    while(TRUE) {
        int item = produce_item();
        down(&empty);
        down(&mutex);
        insert_item(item);
        up(&mutex);
        up(&full);
    }
}

void consumer() {
    while(TRUE) {
        down(&full);
        down(&mutex);
        int item = remove_item();
        consume_item(item);
        up(&mutex);
        up(&empty);
    }
}

注意，不能先对缓冲区进行加锁，再测试信号量。也就是不能先执行down(mutex)再执行down(empty)。这样做会出现这种情况，生产者对缓冲区加锁后，执行down(empty)操作，发现empty=0，此时生产者在对缓冲区加锁的情况下睡眠。消费者也不能进去临界区，因为生产者已经对缓冲区加锁。结果就是生产者持有锁且永远等待，消费者也永远等待，形成死循环。

管程

使用信号量机制实现的生产者消费者问题，需要客户端代码做很多控制，而管程把控制的代码独立出来，不仅不容易出错，也使得客户端代码调用更容易。
管程有一个重要特性：在一个时刻只能有一个进程使用管程。进程在无法继续执行的时候不能一直占用管程，否则其他进程永远不能使用管程。
管程引入了条件变量以及相关的操作：wait()和signal()来实现同步操作。对条件变量执行wait()操作会导致调用进程阻塞，把管程让出来给另一个进程持有。signal()操作用于唤醒被阻塞的进程。

使用管程实现生产者-消费者问题

// 管程
monitor ProducerConsumer
    condition full, empty;
    integer count := 0;
    condition c;

    procedure insert(item: integer);
    begin
        if count = N then wait(full);
        insert_item(item);
        count := count + 1;
        if count = 1 then signal(empty);
    end;

    function remove: integer;
    begin
        if count = 0 then wait(empty);
        remove = remove_item;
        count := count - 1;
        if count = N -1 then signal(full);
    end;
end monitor;

// 生产者客户端
procedure producer
begin
    while true do
    begin
        item = produce_item;
        ProducerConsumer.insert(item);
    end
end;

// 消费者客户端
procedure consumer
begin
    while true do
    begin
        item = ProducerConsumer.remove;
        consume_item(item);
    end
end;

经典同步问题

1.哲学家进餐问题

五个哲学家围着一张圆桌，每个哲学家面前放着食物。哲学家的生活有两种交替活动：吃饭和思考。当一个哲学家吃饭时，需要先拿起自己左右两边的两根筷子，并且一次只能拿起一根筷子。
下面是一种错误解法，如果所有哲学家同时拿起左手边的筷子，那么所有的哲学家都要等待其他人吃完并释放筷子，从而导致死锁。

#define N 5

void philosopher(int i) {
    while(TRUE) {
        think();
        take(i);       // 拿起左边的筷子
        take((i+1)%N); // 拿起右边的筷子
        eat();
        put(i);
        put((i+1)%N);
    }
}

为了防止死锁的发生，可以设置两个条件：
必须同时拿起左右两根筷子；
只有在两个领居都没有进餐的情况下才允许进餐。

#define N 5
#define LEFT (i + N - 1) % N // 左邻居
#define RIGHT (i + 1) % N    // 右邻居
#define THINKING 0
#define HUNGRY   1
#define EATING   2
typedef int semaphore;
int state[N];                // 跟踪每个哲学家的状态
semaphore mutex = 1;         // 临界区的互斥，临界区是 state 数组，对其修改需要互斥
semaphore s[N];              // 每个哲学家一个信号量

void philosopher(int i) {
    while(TRUE) {
        think(i);
        take_two(i);
        eat(i);
        put_two(i);
    }
}

void take_two(int i) {
    down(&mutex);
    state[i] = HUNGRY;
    check(i);
    up(&mutex);
    down(&s[i]); // 只有收到通知之后才可以开始吃，否则会一直等下去
}

void put_two(i) {
    down(&mutex);
    state[i] = THINKING;
    check(LEFT); // 尝试通知左右邻居，自己吃完了，你们可以开始吃了
    check(RIGHT);
    up(&mutex);
}

void eat(int i) {
    down(&mutex);
    state[i] = EATING;
    up(&mutex);
}

// 检查两个邻居是否都没有用餐，如果是的话，就 up(&s[i])，使得 down(&s[i]) 能够得到通知并继续执行
void check(i) {         
    if(state[i] == HUNGRY && state[LEFT] != EATING && state[RIGHT] !=EATING) {
        state[i] = EATING;
        up(&s[i]);
    }
}

2.读者-写者问题
允许多个进程同时对数据进行读操作，但是不允许读和写以及写和写操作同时发生。
一个整型变量count记录在对数据进行读操作的进程数量，一个互斥量count_mutex用于对count加锁，一个互斥量data_mutex用于对读写的数据加锁。

typedef int semaphore;
semaphore count_mutex = 1;
semaphore data_mutex = 1;
int count = 0;

void reader() {
    while(TRUE) {
        down(&count_mutex);
        count++;
        if(count == 1) down(&data_mutex); // 第一个读者需要对数据进行加锁，防止写进程访问
        up(&count_mutex);
        read();
        down(&count_mutex);
        count--;
        if(count == 0) up(&data_mutex);
        up(&count_mutex);
    }
}

void writer() {
    while(TRUE) {
        down(&data_mutex);
        write();
        up(&data_mutex);
    }
}

3 内存管理

3.1 虚拟内存

虚拟内存的目的是为了让物理内存扩充成更大的逻辑内存，从而让程序获得更多的可用内存。
为了更好的管理内存，操作系统将内存抽象成地址空间。每个程序拥有自己的地址空间，这个地址空间被分割成多个块，每一块称为一页。这些页被映射到物理内存中，但不需要映射到连续的物理内存，也不需要所有页都必须在物理内存中。当程序引用到不在物理内存中的页时，由硬件执行必要的映射，将缺失的部分装入物理内存并重新执行失败的指令。
从上面的描述可以看出，虚拟内存允许程序不用将地址空间中的每一页都映射到物理内存，也就是说一个程序不需要全部调入内存就可以运行，这使得有限的内存运行大程序成为可能。例如有一台计算机可以产生16位地址，那么一个程序的地址空间范围是0~64K。该计算机只有32kb的物理内存，虚拟内存技术允许该计算机运行一个64k大小的程序。

虚拟内存的实现
虚拟内存中，允许将一个作业分多次调入内存。采用连续分配方式时，会使相当一部分内存空间都处于暂时或永久的空闲状态，造成内存资源的严重浪费，而且也无法从逻辑上扩大内存容量。因此虚拟内存需要建立在离散分配的内存管理方式的基础上。有以下三种实现方式：
请求分页存储管理；
请求分段存储管理；
请求段页式存储管理。

不管哪种方式，都需要一定的硬件支持。一般需要的支持有以下几个方面：
一定容量的内存和外存；
页表机制（或段表机制）作为主要的数据结构；
中断机构，当用户程序要访问的部分尚未调入内存，则产生中断；
地址变换机构，逻辑地址到物理地址的变换。

3.2 地址空间

如果要使多个应用程序同时运行在内存中，必须解决两个问题，保护和重定位。创造一个存储器抽象：地址空间，就像进程的概念创建了一种抽象的CPU来运行程序，地址空间也创建了一种抽象内存供程序使用。

基址寄存器和变址寄存器

最简单的办法是使用动态重定位技术，它就是通过一种简单的方式将每个进程的地址空间映射到物理空间的不同区域。还有一种方式是使用基址寄存器和变址寄存器。基址寄存器存储内存的起始位置，变址寄存器存储应用程序的长度。每当进程引用内存获取指令或者读写数据时，CPU都会自动将基址值添加到进程生成的地址中，然后再将其发送到内存总线上。同时，它检查程序提供的地址是否大于等于变址寄存器中的值，如果程序提供的地址要超过变址寄存器的范围，那么会产生错误并终止访问。

3.3 分页系统地址映射

内存管理单元（MMU）管理着地址空间和物理内存的转换，其中的页表（Page table）存储着页（程序地址空间）和页框（物理内存空间）的映射表。
一个虚拟地址分为两个部分，一部分存储页面号，一部分存储偏移量。
下图的页表存放者16个页，者16个页需要用4个比特位来进行索引定位。例如对于虚拟空间地址（0010 000000000100），前4位是存储页面号2，读取表项内容为（1101），页表项最后一位表示是否存在于内存中，1表示存在。后12为存储偏移量。这个页对应的页框的地址为（110 000000000100）。

3.4 页面置换算法

在程序运行过程中，如果访问的页面不在内存中，就发生缺页中断从而将该页调入内存中。此时如果内存已无空闲空间，系统必须从内存中调出一个页面到磁盘对换区中来腾出空间。
页面置换算法和缓存淘汰策略类似，可以将内存看成磁盘的缓存。在缓存系统中，缓存的大小有限，当有新的缓存到达时，需要淘汰一部分已经存在的缓存，这样才有空间存放新的缓存数据。页面置换算法的主要目标是使页面置换频率最低（也就是说缺页率最低）。

最优

Optimal replacement algorthm，OPT。当缺页中断发生时，把最长时间内不再访问的页面置换出来。但是这只是种理论上存在的算法，并不能真正实现，因为发生缺页中断时，操作系统并不能知道每个页面什么时候会被访问。

先进先出

First In First Out，FIFO。置换最先进入的页面。
该算法会将那些经常被访问的页面换出，导致缺页率升高。

第二次机会算法

FIFO算法可能会将经常使用的页面置换出去，为了避免这一问题，对该算法做下修改：当页面被访问（读或写）时设置该页面的R为1.需要替换的时候，检查最老页面的R，如果R是0，那么这个页面既老，又没有被使用，可以立即置换；如果是1，将R置为0，并把该页面放到链表尾，修改它的装入时间，使它想刚装入一样，然后继续从表头开始搜索。

时钟

Clock。第二次机会算法需要在链表中移动页面，降低了效率。时钟算法使用环形链表将页面连接起来，再使用一个指针指向最老的页面。

3.5分段

虚拟内存采用的是分页技术，也就是将地址空间划分成固定大小大小的也，每一页再与内存进行映射。
下图为一个编译器在编译过程中建立的多个表，有四个表示动态增长的，如果使用分页系统的一维地址空间，动态增长的特点会导致覆盖问题的出现。

分段的做法是把每个表分段，一个段构成一个独立的地址空间。每个段的长度可以不同，并且可以动态增长。

段页式
程序的地址空间划分成多个拥有独立地址空间的段，每个段上的地址空间划分成大小相同的页。这样既拥有分段系统的共享和保护，又拥有分页系统的虚拟内存功能。

分页与分段的比较
1.对程序员的透明性：分页透明，但是分段需要程序员显示划分每个段。
2.地址空间的维度：分页是一维地址空间，分段是二维。
3.大小是否可以改变：页的大小不可变，段的大小可以动态改变。
4.出现的原因：分页主要用于实现虚拟内存，从而获得更大的地址空间；分段主要是为了使程序和数据可以被划分为逻辑上独立的地址空间，并且有助于共享和保护。

4 设备管理

4.1 IO设备

IO设备又叫输入输出设备，是用来人和计算机通信的外部硬件。
分成两种，块设备（block devices）和字符设备（character devices）。

块设备

块设备是一个能储存固定大小块信息的设备，它支持以固定大小的块，扇区或群集读取和写入数据。每个块都有自己的物理地址，通常块的大小在512~65535之间。所有传输的信息都会以连续的块作为单位。块设备的基本特征是每个块都较为独立，能够独立的进行读写。常见的块设备有硬盘、蓝光光盘、usb盘等。与字符设备相比，块设备需要较少的引脚。

块设备的缺点
基于给定固态存储器的块设备比基于相同类型的存储器的字节寻址要慢一些，因为必须在块的开头开始读取或者写入。要读取该块的任何部分，必须寻找到该块的开始，读取这个块，如果不使用该块，则将其丢弃。要写入块的一部分，必须寻找到块的开始，讲整个块读入内存，修改数据，再次寻找块的开头处，然后将整个块写回设备。

字符设备

字符设备以字符为单位发送或接收一个字符流，而不考虑任何块结构。字符设备是不可寻址的，也没有任何寻道操作。常见的字符设备有打印机、网络设备、鼠标等。

4.2 盘

磁盘结构

盘面（Platter）：一个磁盘有多个盘面；
磁道（Track）：盘面上的圆形带状区域，一个盘面可以有多个磁道；
扇区（Track Sector）：磁道上的一个弧度按，一个磁道可以有多个扇区，它是最小的物理存储单位，目前主要有512bytes与4k两种大小；
磁头（Head）：与盘面非常接近，能够将盘面上的磁场装换为电信号（读），以及将点信号装换为盘面的磁场（写）；
制动手臂（Actuator arm）：用于在磁道之间移动磁头；
主轴（Spindle）：使整个盘面转动。

磁盘调度算法

读写一个磁盘块的时间的影响因素有：
1.旋转时间，主轴转动盘面，使磁头移动到适当的扇区上
2.寻道时间，制动手臂移动，使磁头移动到适当的磁道上
3.实际的数据传输时间
其中，寻道时间最长，因此磁盘调度的主要目标是使磁盘的平均寻道时间最短。

先来先服务

FCFS，First Come First Served。按照磁盘请求的顺序进行调度。优点是公平简单，缺点是未对寻道做任何优化，使平均寻道时间可能较长。

最短寻道时间优先

SSTF，Shortest Seek Time First。优先调度与当前磁头所在磁道距离最近的磁道。
虽然平均寻道时间比较低，但是不够公平。如果新到达的磁道请求总是比一个在等待的磁道请求近，那么在等待的磁道请求会一直等待下去，也就是出现饥饿现象。具体来说，两端的磁道请求更容易出现饥饿现象。

电梯算法

SCAN，也叫扫描算法。电梯总是保持一个方向运行，直到该方向没有请求为止，然后改变运行方向。
该算法和电梯的运行过程类似，总是按一个方向来进行磁道调度，直到该方向上没有未完成的磁道请求，然后改变方向。
因为考虑了移动方向，因此所有的磁盘请求都会被满足，解决了SSTF的饥饿问题。

4.3 时钟

时钟也被称为定时器，负责维护时间、防止一个进程长期占用CPU时间等功能。

时钟硬件

在计算机中有两种类型的时钟，这些时钟与现实生活中的时钟完全不一样。
1.比较简单的一种时钟被连接到110V或者220V的电源上，这样每个电压周期会产生一个中断，大概是50-60HZ。
2.另外一种时钟由晶体振荡器、计数器和寄存器组成，如下图所示

这种时钟被称为可编程时钟，可编程时钟有两种模式，一种是一键式（one-shot mode），当时钟启动时，会把存储器中的值复制到计数器中，然后，每次晶体的振荡器的脉冲都会使计数器-1.当计数器变为0时，会产生一个中断，并停止工作，直到软件再一次显示启动。还有一种模式是方波（square-wave mode）模式，这这种模式下，当计数器变为0并产生中断后，存储寄存器的值会自动复制到计数器中，这种周期性的中断称为一个时钟周期。

时钟软件

时钟硬件所做的工作只是根据已知的时间间隔产生中断，而其他的工作都是由时钟软件完成，一般操作系统的不同，时钟软件的具体实现也不同，但是一般都会包括以下几点：
维护一天的时间；
阻止进程运行的时间超过其指定时间；
统计CPU的使用情况；
处理用户进程的警告系统调用；
为系统各个部分提供看门狗定时器；
完成概要剖析、监视和信息收集。

软定时器

时钟软件也被称为可编程时钟，可以设置它以程序需要的任何速率引发中断。时钟软件触发的中断是一种硬中断，但是某些应用程序对于硬中断是不可接受的。这时就需要一种软定时器避免中断，无论内核因为什么原因在运行，它返回用户态之前都会检查时钟来了解软定时器是否到期。如果软定时器到期，则执行被调度的事件也无需切换到内核态，因为本身已经处于内核态中。这种方式避免了频繁的内核态和用户态之间的切换，提高了程序运行效率。
软定时器切换到内核态的速率不同，原因主要有：系统调用；TLB未命中；缺页异常；IO中断；CPU变得空闲。

5 文件管理

5.1 文件命名

文件是一种抽象机制，它提供了一种方式用来读写信息。在创建一个文件后，会给文件一个命名。当进程终止时，文件会继续存在，并且其他进程可以使用名称访问该文件。
不同的OS会有不一样的命名规则，比如某些OS区分大小写，某些不区分。大多数都支持量部分的文件名，它们之间用 . 隔开，比如文件名 pr.c 。原点后面的文件称为文件扩展名（file extension），通常表示文件的一些信息。下图列举了一些常用文件拓展名及其含义

5.2 文件结构

文件的构造有多种方式：字节序列、记录序列、树。
字节序列，操作系统不关心序列的内容是什么，它能看到的就是字节（bytes）。其文件内容的任何含义只在用户程序中进行解释。UNIX和Windows用次方式；
记录序列，文件是具有固定长度记录的序列，每个记录都有其内部结构。核心思想是：读操作返回一个记录，而写操作重写或者追加一个记录。
数结构，文件由一棵记录树构成，记录树的长度不一定相同，每个记录树都在记录中的固定位置包含一个key字段，这棵树按key进行排序，从而可以对特定的key进行快速查找。

5.3 文件操作

使用文件的目的是用来存储信息并方便检索，为此OS提供了一些常用调用：
1.create，创建不包含任何数据的文件。调用的目的是表示文件即将建立，并对文件设置一些属性；
2.delete，删除文件，以释放内存空间；
3.open，使用文件前先打开文件，这个调用的目的是允许系统将属性和磁盘地址列表保存到主存中，以便后续的快速访问；
4.close，文件使用完成后，应该释放关闭文件以释放表空间；
5.read，从文件中读取数据；
6.write，写入数据到文件；
7.append，向文件末尾添加数据；
8.rename，文件重命名；

更多文件管理相关内容，查阅文件管理部分

6 死锁

6.1 出现死锁的必要条件

1.互斥：每个资源都被分配给了一个进程，或者资源是可用的；
2.占有和等待：已经得到了某个资源的进程，可以再请求新的资源；
3.不可抢占：已经分配给一个进程的资源不能强制性地被抢占，只能被占有它的进程显示地释放；
4.环路等待：有两个或者以上的进程组成一条环路，该环路中的每个进程都在等待下一个进程所占有的资源。

6.2 死锁的处理方法

主要有以下四种：鸵鸟策略、死锁检测与死锁恢复、死锁预防、死锁避免。

6.2.1 鸵鸟策略

像鸵鸟一样，遇到问题把头埋进沙子，假装根本没有发生问题。
因为解决死锁问题的代价很高，所以对死锁置之不理。一般是在死锁发生概率比较低，或者发生死锁造成的影响比较小的情况下。大多数OS都使用这个不处理的方法，包括Unix、Linux和Windows。

6.2.2 死锁检测与死锁恢复

不试图阻止死锁的发生，而是当检测到死锁时，采取措施进行恢复。

1.每种类型一个资源的死锁检测

上图为资源分配图，其中方框表示资源，圆圈表示进程。资源指向进程表示该资源分配给该进程，进程指向资源表示进程请求获取该资源。
图a可以抽取出环，如图b，它满足了环路等待条件，发生死锁。
每种类型一个资源的死锁检测算法是通过检测有向图是否存在环来实现，从一个节点出发进行深度优先搜索，对访问过的节点进行标记，如果访问了已经标记的节点，就表示有向图存在环，也就是检测到死锁的发生。

2.每种类型多个资源的死锁检测

上图中，有三个进程四个资源，每个数据代表的含义如下：
E向量，资源向量；A向量，资源剩余量；C矩阵，每个进程所拥有的资源数量，每一行都代表一个进程拥有资源的数量；R矩阵，每个进程请求的资源数量。
进程P1和P2所请求的资源都得不到满足，只有进程P3可以，让P3执行，之后释放P3 的资源，此时A=（2 2 2 0）。P2可以执行，执行后释放P2拥有的资源，A=（4 2 2 1）。P1也可以执行，所有进程都可以顺利执行，没有死锁。
算法总结：每个进程最开始都不被标记，执行过程有可能被标记。当算法结束时，任何没有被标记的进程都是死锁进程。
1.寻找一个没有标记的进程Pi，它所请求的资源小于等于A；
2.如果找到了这样的进程，那么将C矩阵的di行向量加到A，标记该进程，并转回1.
如果没有这样的进程，算法终止。

3.死锁恢复
利用抢占恢复
利用回滚恢复
通过杀死进程恢复

6.2.3 死锁预防

在程序运行之前预防发生死锁。破坏死锁发生的必要条件
1.破坏互斥条件
例如假脱机打印机技术，允许若干个进程同时输出，唯一真正请求物理打印机的进程是打印机守护进程。
2.破坏占有和等待条件
一种实现方式是规定所有的进程在开始执行前请求所需要的全部资源。
3.破坏不可抢占条件
4.破坏环路等待
给资源统一编号，进程只能按编号顺序来请求资源。

6.2.4 死锁避免

在程序运行时避免发生死锁。

1.安全状态

图a的第二列Has表示已拥有的资源数，第三列Max表示总共需要的资源数，Free表示还可以使用的资源数。从图a开始出发，先让B拥有所需的所有资源（图b），运行结束后释放B，此时Free变为5（图c）；接着以同样的方式运行C和A，使得所有进程都能成功运行，因此可以称图a所示的状态是安全状态。
定义，如果没有死锁发生，并且即使所有进程突然请求对资源的最大需求，也仍然存在某种调度次序能够使得每一个进程运行完毕，则称该状态是安全的。
安全状态的检测与死锁的检测类似，因为安全状态必须要求不能发生死锁，下面的银行家算法与死锁检测算法非常类似。

2.单个资源的银行家算法
一个小城镇的银行家，他向一群客户分别承诺了一定的贷款额度，算法要做的是判断对请求的满足是否会进入不安全状态，如果是，就拒绝请求，否则予以分配。

上图c为不安全状态，因此算法会拒绝之前的请求，从而避免进入图c的状态。

3.多个资源的银行家算法

上图中有五个进程，四个资源。左边的图表示已经分配的资源，右边的图表示还需要分配的资源。最右边的E、P以及A分别表示：总资源、已分配资源、可用资源，注意这三个为向量，而不是具体数值，例如A=（1 0 2 0），表示四个资源分别剩下1/0/2/0。
检查一个状态是否安全的算法如下：
查找右边的矩阵是否存在一行小于等于向量A。如果不存在这样的行，那么系统会发生死锁，状态是不安全的；
假若找到这样一行，将该进程标记为终止，并将其已分配资源加到A中；
重复以上两步，直到所有进程都标记为终止，则状态是安全的。
如果一个状态是不安全的，需要拒绝进入这个状态。

Payne的小站

操作系统相关基础

目录