操作系统

本文发布于：2021年11月30日

字数：37.9k字

时长：131分钟

操作系统（OS）是管理和控制计算机硬件与软件资源，是计算机上直接运行的最基本的系统软件，任何其他软件都必须在操作系统的支持下才能运行。操作系统是用户和计算机的接口，同时也是计算机硬件和其他软件的接口。操作系统的功能包括管理计算机系统的硬件、软件及数据资源，控制程序运行，提供人机交互界面，为其它应用软件提供支持等。以下为我在学习过程中所做的笔记，可供参考。

一、计算机系统概述

操作系统的概念、功能和特征

操作系统（Operating System，OS）是指控制和管理整个计算机系统的硬件和软件资源，并合理地组织调度计算机的工作和资源的分配：以提供给用户和其他软件方便的接口和环境：它是计算机系统中最基本的系统软件。

系统资源的管理者：提供处理器管理、存储器管理、文件管理、设备管理的功能。
向上层提供方便易用的服务：操作系统把一些丑陋的硬件功能封装成简单易用的服务（如：GUI、命令接口、程序接口），使用户能更方便地使用计算机，用户无需关心底层硬件的原理，只需要对操作系统发出命令即可（封裝思想）。
作为最接近硬件的层次：实现对硬件机器的拓展，没有任何软件支持的计算机成为裸机。在裸机上安装的操作系统，可以提供资源管理功能和方便用户的服务功能，将裸机改造成功能更强、使用更方便的机器。通常把覆盖了软件的机器成为书充机器，又称之为虚拟机。

操作系统的四个特征：并发、共享、虛拟、异步，其中并发和共享两个最基本的特征，二者互为存在条件。

并发：指两个或多个事件在同一时间间隔内发生。这些事件宏观上是同时发生的，但微观上是交替发生的。并行：指两个或多个事件在同一时刻同时发生。

操作系统的并发性指计算机系统中“同时”运行着多个程序，这些程序宏观上看是同时运行着的，而徽观上看是交替运行的。操作系统就是伴随着 “多道程序技术” 而出现的。因此，操作系统和程序并发是一起诞生的。

单核 CPU 同一时刻只能执行一个程序，各个程序只能并发地执行，多核 CPU 同一时刻可以同时执行多个程序，多个程序可以并行地执行。

共享即资源共享，是指系统中的资源可供内存中多个并发执行的进程共同使用。所谓的同时，往往是宏观上的，而在微观上，这些进程可能是交替地对该资源进行访问的（即分时共享）。

两种资源共享方式：

互斥共享方式：系统中的某些资源，虽然可以提供给多个进程使用，但一个时间段内只允许一个进程访问该资源（如：摄像头）。
同时共享方式：系统中的某些资源，允许一个时间段内由多个进程 “同时〞对它们进行访问（如：硬盘）。

虚拟是指把一个物理上的实体变为若干个逻辑上的对应物。物理实体（前者）是实际存在的，而逻辑上对应物（后者）是用户感受到的（如：虚拟处理器的时分复用技术、虚拟存储器的空分复用技术）。

异步是指，在多道程序环境下，允许多个程序并发执行，但由于资源有限，进程的执行不是一贯到底的，而是走走停停，以不可预知的速度向前推进，这就是进程的异步性。

如果失去了并发性，即系统只能串行地运行各个程序，那么每个程序的执行会一贯到底。只有系统拥有并发性，才有可能导致异步性。

操作系统的发展与分类

手工操作阶段：用户独占全机、人机速度不盾导致资源利用率极低。

单道批处理系统：引入脱机输入/输出技术（用外围机＋磁带完成），并由监督程序负责控制作业的输入、输出。缓解了一定程度的人机速度矛盾，资源利用率有所提升。但内存中仅能有一道程序运行，只有该程序运行结束之后才能调入下一道程序。CPU 有大量的时间是在空闲等待 I/O 完成，资源利用率依然很低。

多道批处理系统：每次往内存中读入多道程序，操作系统正式诞生，用于支持多道程序并发运行。

分时操作系统：计算机以时间片为单位轮流为各个用户/作业服务，各个用户可通过终端与计算机进行交互。用户请求可以被即时响应，解决了人机交互问题。允许多个用户同时使用一台计算机，并且用户对计算机的操作相互独立，感受不到别人的存在。但是不能优先处理一些紧急任务。操作系统对各个用户/作业都是完全公平的，循环地为每个用户/作业服务一个时间片。

实时操作系统：能够优先响应一些紧急任务，某些紧急任务不需时间片排队。在实时操作系统的控制下，计算机系统接收到外部信号后及时进行处理，并且要在严格的时限内处理完事件。实时操作系统的主要特点是及时性和可靠性，分为硬实时系统（必须在绝对严格的规定时间内完成处理，如：导弹控制系统、自动驾驶系统）和软实时系统（能接受偶尔违反时间规定，如 12306）。

网络操作系统：是伴随着计算机网络的发展而诞生的，能把网络中各个计算机有机地结合起来，实现数据传送等功能，实现网络中各种资源的共享（如文件共享）和各台计算机之间的通信。（如：Windows NT 就是一种典型的网络操作系统，网站服务器就可以使用）

分布式操作系统：主要特点是分布性和并行性。系统中的各台计算机地位相同，任何工作都可以分布在这些计算机上，由它们并行、协同完成这个任务。

个人计算机操作系统：如 Windows XP、MacOS，方便个人使用。

操作系统的运行机制

程序运行的过程其实就是 CPU 执行一条一条的机器指令的过程，指令就是处理器（CPU）能识别、执行的最基本命令。

应用程序 v.s. 内核程序：由很多内核程序组成了操作系统内核，或简称内核（Kernel），内核是操作系统最重要最核心的部分，也是最接近硬件的部分。

特权指令 v.s. 非特权指令：操作系统内核作为管理者，有时会让 CPU 执行一些特权指令，如：I/O 指令、时钟管理、设置中断屏蔽指令、内存清零指令。这些指令影响重大，只允许操作系统内核来使用，应用程序只能使用非特权指令，如：加减法指令等。在 CPU 设计和生产的时候就划分了特权指令和非特权指令，因此 CPU 执行一条指令前就能判断出其类型。

处理器的执行状态分为核心态与用户态：处于内核态时，说明此时正在运行的是内核程序，此时可以执行特权指令。处于用户态时，说明此时正在运行的是应用程序，此时只能执行非特权指令。

CPU 中有一个奇存器叫程序状态字寄存器（PSW），其中有个二进制位，1 表示内核态（管态），0 表示用户态（目态）。

内核态 -> 用户态：执行一条特权指令，修改 PSW 的标志位为用户态，这个动作意味着操作系统将主动让出 CPU 使用权。
用户态 -> 内核态：由中断引发，硬件自动完成变态过程，触发中断信号意味着操作系统将强行夺回 CPU 的使用权。

中断和异常

中断是让操作系统内核夺回 CPU 使用权的唯一途径，使 CPU 由用户态变为内核态，使操作系统夺回对 CPU 的控制权。

中断的类型分为：内中断（与当前执行的指令有关，中断信号来源于 CPU 内部）和外中断（与当前执行的指令无关，中断信号来源于 CPU 外部）。

异常，也称内中断，是由故障、终止（致命错误）引起的。有时候应用程序想请求操作系统内核的服务，此时会执行一条陷入指令，该指令会引发一个内部中断信号，但陷入指令不是特权指令。

通常异常会引起中断，而中断未必是由异常引起的。每一条指令执行结束时，CPU 都会例行检查是否有外中断信号（如：时钟中断、I/O 中断请求）。

不同的中断信号，需要用不同的中断处理程序来处理。当 CPU 检测到中断信号后，会根据中断信号的类型去查询中断向量表，以此来找到相应的中断处理程序在内存中的存放位置。

系统调用

系统调用是操作系统提供给应用程序（程序员/编程人员）使用的接口，可以理解为一种可供应用程序调用的特殊函数，应用程序可以通过系统调用来请求获得操作系统内核的服务。

编程语言有时会将系统调用封装成库函数，以隐藏系统调用的一些细节，使程序员编程更加方便。普通应用程序可直接进行系统调用，也可使用库函数。有的库函数涉及系统调用，有的不涉及。

应用程序通过系统调用请求操作系统的服务。而系统中的各种共享资源都由操作系统内核统一掌管，因此凡是与共享资源有关的操作（如存储分配、I/O 操作、文件管理等），都必须通过系统调用的方式向操作系统内核提出服务请求，由操作系统内核代为完成。这样可以保证系统的稳定性和安全性，防止用户进行非法操作。

系统调用的过程：传递系统调用参数 -> 执行陷入指令（用户态）-> 执行相应的内请求核程序处理系统调用（核心态）-> 返回应用程序。

陷入指令（访管指令）是在用户态执行的，执行陷入指令之后立即引发一个内中断，使 CPU 进入核心态。

发出系统调用请求是在用户态，而对系统调用的相应处理在核心态下进行。

系统调用分为：进程控制、文件系统控制、系统控制、内存管理、网络管理、socket 管控以及进程间通信等。

操作系统的体系结构

内核是操作系统最基本、最核心的部分。实现操作系统内核功能的那些程序就是内核程序。

时钟管理：实现计时功能。
中断处理：负责实现中断机制。
原语：是一种特殊的程序，处于操作系统最底层，是最接近硬件的部分，这种程序的运行具有原子性，其运行只能一气呵成，不可中断，运行时间较短、调用频繁。
其他对系统资源进行管理的功能：迸程管理，存储器管理，设备管理，这些管理工作更多的是对数据结构的操作，不会直接涉及硬件。

分层结构：内核分多层，每层可单向调用更低一层提供的接口。

优点是便于调试和验证，自底向上逐层调试验证，易扩充和易维护，各层之间调用接口清晰固定。
缺点是仅可调用相邻低层，难以合理定义各层的边界，效率低，不可跨层调用，系统调用执行时间长。

模块化：将内核划分为多个模块，各模块之问相互协作。内核 = 主模块 + 可加载内核模块。

主模块：只负责核心功能，如进程调度、内存管理。可加载内核模块：可以动态加载新模块到内核，而无需重新编译整个内核。
模块间逻辑清晰易于维护，确定模块间接口后即可多模块同时开发。
支持动态加载新的内核模块（如：安装设备驱动程序、安装新的文件系统模块到内核），增强 OS 适应性。
任何模块都可以直接调用其他模块，无需采用消息传递进行通信，效率高。
但模块问的接口定义未必合理、实用，且模块间相互依赖，更难调试和验证。

宏内核（大内核）：所有的系统功能都放在内核里，大内核结构的 OS 通常也采用了模块化的设计思想。例如：Linux、UNIX。

内核功能少，结构清晰，方便维护，性能高，内核内部各种功能都可以直接相互调用。
内核代码庞大，结构混乱，难以维护，大内核中某个功能模块出错，就可能导致整个系统崩溃。

微内核：只把中断、原语、进程通信等最核心的功能放入内核。进程管理、文件管理、设备管理等功能以用户进程的形式运行在用户态。例如：Windows NT。

内核小功能少、易于维护，内核可靠性高，内核外的某个功能模块出错不会导致整个系统崩溃。
性能低，需要频繁地在核心态和用户态之间切换，用户态下的各功能模块不可以直接相互调用，只能通过内核的消息传递来间接通信。

外核（exokernel）：内核负责进程调度、进程通信等功能，外核负责为用户进程分配未经抽象的硬件资源，且由外核负责保证资源使用安全。

外核可直接给用户进程分配不虚拟、不抽象的硬件资源，使用户进程可以更灵活的使用硬件资源，减少了虚拟硬件资源的映射层，提升效率。
但降低了系统的一致性，使系统变得更复杂。

操作系统的引导（Boot）

CPU 从一个特定主存地址开始，取指令，执行 ROM（BIOS）中的引导程序，即自举程序（先进行硬件自检，再开机）；
将磁盘的主引导记录（MBR）读入内存，执行磁盘引导程序，扫描分区表；
从活动分区（又称主分区，即安装了操作系统的分区）读入分区引导记录（PBR），执行其中的程序；
从根目录下找到完整的操作系统初始化程序（即启动管理器）并执行，完成开机的一系列动作。

虚拟机

虚拟机：使用虚拟化技术，将一台物理机器虚拟化为多台虚拟机器（Virtual Machine，VM），每个虚拟机器都可以独立运行一个操作系统（虚拟机管理程序/虚拟机监控程序/Virtual Machine Monitor/Hypervisor）。

两类虚拟机管理程序（VMM）的对比：

第一类 VMM：直接运行在硬件之上，能直接控制和分配物理资源。在安装 Guest OS 时，VMM 要在原本的硬盘上自行分配存储空间，类似于外核的分配方式，分配未经抽象的物理硬件。性能更好，可迁移性更差。可支持的虚拟机数量更多，不需要和 Host OS 竞争资源，相同的硬件资源可以支持更多的虛拟机。第一类 VMM 运行在最高特权级（Ring 0），可以执行最高特权的指令。
第二类 VMM：运行在宿主操作系统（Host OS）之上，依赖于 Host OS 为其分配物理资源。Guest OS 拥有自己的虛拟磁盘，该盘实际上是 Host OS 文件系统中的一个大文件。Guest OS 分配到的内存是虚拟内存。性能更差，需要 Host OS 作为中介。可支持的虚拟机数量更少，Host OS 本身需要使用物理资源，Host OS 上运行的其他进程也需要物理资源。可迁移性更好，只需导出虛拟机镜像文件即可迁移到另一台 Host OS 上，商业化应用更广泛。第二类 VMM 部分运行在用户态、部分运行在内核态。Guest OS 发出的系统调用会被 VMM 截获，并转化为 VMM 对Host OS 的系统调用。

二、进程与线程

进程的概念、组成、特征

程序是静态的，就是个存放在磁盘里的可执行文件，就是一系列的指令集合。进程（Process）是动态的，是程序的一次执行过程，同一个程序多次执行会对应多个进程。

进程是进程实体的运行过程，是系统进行资源分配和调度的一个独应单位，进程是资源分配的基本单位，也是独立运行的基本单位。当进程被创建时，操作系统会为该进程分配一个唯一的、不重复的身份证号，进程标识符 PID（Process ID，进程 ID）。

进程控制块（PCB）：标识进程的存在，刻画执行瞬间特征的数据机构，操作系统需要对各个并发运行的进程进行管理，但凡管理时所需要的信息，都会被放在 PCB 中。PCB 是进程存在的唯一标志，当进程被创建时，操作系统为其创建 PCB，当进程结束时，会回收其 PCB。

一个进程实体（进程映像）由 PCB、程序段、数据段组成。进程是动态的，进程实体（进程映像）是静态的。PCB 包含进程描述信息、迸程控制和管理信息、资源分配清单、处理机相关信息。程序段包括程序的代码（指令序列），数据段包括运行过程中产生的各种数据（如：程序中定义的变量）。PCB 是给操作系统用的。程序段、数据段是给进程自己用的。

进程的特征：

动态性：进程是程序的一次执行过程，是动态地产生、变化和消亡的，动态性是进程最基本的特征
并发性：内存中有多个进程实体，各进程可并发执行。
独立性：进程是能独立运行、独立获得资源、独立接受调度的基本单位。
异步性：各进程按各自独立的、不可预知的速度向前推进，异步性会导致并发程序执行结果的不确定性，操作系统要提供进程同步机制来解决异步问题。
结构性：每个进程都会配置一个 PCB。结构上看，进程由程序段、数据段、PCB 组成。

进程的状态和转换

进程正在被创建时，它的状态是创建态，在这个阶段操作系统会为进程分配资源、初始化 PCB。当进程创建完成后，便进入就绪态，处于就绪态的进程己经具备运行条件，但由于没有空闲 CPU，就暂时不能运行。系统中可能会有很多个进程都处于就绪态。

当 CPU 空闲时，操作系统就会选择一个就绪进程，让它上处理机运行，如果一个进程此时在 CPU 上运行，那么这个进程处于运行态。CPU 会执行该进程对应的程序（执行指令序列）。

在进程运行的过程中，可能会请求等待某个事件的发生（如等待某种系统资源的分配，或者等待其他进程的响应）。在这个事件发生之前，进程无法继续往下执行，此时操作系统会让这个进程下 CPU，并让它进入阻塞态。当 CPU 空闲时，又会选择另一个就绪态进程上 CPU 运行。

一个进程可以执行 exit 系统调用，请求操作系统终止该进程。此时该进程会进入终止态，操作系统会让该进程下 CPU，并回收内存空问等资源，最后还要回收该进程的 PCB。当终止进程的工作完成之后，这个进程就彻底消失了。

进程状态是唯一的，阻塞态 -> 就绪态不是进程自身能控制的，是一种被动行为。运行态 -> 阻塞态是一种进程自身做出的主动行为。不能由阻塞态直接转换为运行态，也不能由就绪态直接转换为阻塞态（因为进入阻塞态是进程主动请求的，必然需要进程在运行时才能发出这种请求）。

时间片到，或处理机被抢占时，进程从运行态 -> 就绪态。

除三大基本状态外进程另外两种状态：

创建态（New，又称：新建态）：进程正在被创建，操作系统为进程分配资源、初始化 PCB。
终止态（Terminated，又称：结束态）：进程正在从系统中撒销，操作系统会回收进程拥有的资源、撒销 PCB。

进程 PCB 中，会有一个变量 state 来表示进程的当前状态。如：1 表示创建态、2 表示就绪态、3 表示运行态…。为了对同一个状态下的各个进程进行统一的管理，操作系统会将各个进程的 PCB 组织起来。进程间的关系是树形结构。

迸程的组织方式：

链接方式：按照进程状态将 PCB 分为多个队列，操作系统持有指向各个队列的指针。
索引方式：根据进程状态的不同，建立几张索引表，操作系统持有指向各个索引表的指针。

进程控制

进程控制的主要功能是对系统中的所有进程实施有效的管理，它具有创建新进程、撤销己有进程、实现进程状态转换等功能。

进程创建是通过创建原语实现的。原语是一种特殊的程序，原语的执行具有原子性，即执行过程只能一气呵成，期间不允许被中断。可以用关中断指令和开中断指令这两个特权指令（运行在内核态）实现原子性。CPU 执行了关中断指令之后，就不再例行检查中断信号，直到执行开中断指令之后才会恢复检查。

创建原语（操作系统创建一个进程时使用的原语）：申请一个空闲 PCB，并指定唯一的 PID -> 为新进程分配必要的资源 -> 将新进程的 PCB 初始化 -> 将 PCB 插入到就绪队列（创建态 -> 就绪态）。

引起进程创建的事件：

用户登录：分时系统中，用户登录成功，系统会建立为其建立一个新的进程。
作业调度：多道批处理系统中，有新的作业放入内存时，会为其建立一个新的进程。
提供服务：用户向操作系统提出某些请求时，会新建一个进程处理该请求。
应用请求：由用户进程主动请求创建一个子进程。

进程的终止（就绪态/阻塞态/运行态 -> 终止态 -> 无）使用撤销原语：从 PCB 集合中找到终止进程的 PCB -> 若进程正在运行，立即剥夺 CPU，将 CPU 分配给其他进程 -> 终止其所有子进程 -> 将该进程拥有的所有资源归还给父进程或操作系统 -> 刪除 PCB。

引起进程终止的事件：正常结束（exit 系统调用）、异常结束、外界干预（ctrl alt del）。

进程的阻塞与唤醒：两条低级进程通讯原语，阻塞原语（P 原语）的功能是将进行进程由执行状态转为阻塞状态，唤醒原语（V 原语）的功能是将进程由阻塞状态变为就绪状态。

（运行态 -> 阻塞态）使用阻塞原语：找到要阻塞的进程对应的 PCB -> 保护进程运行现场，将 PCB 状态信息设置为阻塞态，暂时停止进程运行 -> 将 PCB 插入相应事件的等待队列。

引起进程阻塞的事件：需要等待系统分配某种资源、需要等待相互合作的其他进程完成工作。

（阻塞态 -> 就绪态）使用唤醒原语：在事件等待队列中找到 PCB -> 将 PCB 从等待队列移除，设置进程为就绪态 -> 将 PCB 插入就绪队列，等待被调度。

引起迸程唤醒的事件：等待的事件发生。

阻塞原语、唤醒原语必须成对使用。

进程的切换（运行态 -> 就绪态、就绪态 -> 运行态）使用切换原语：将运行环境信息存入 PCB -> PCB 移入相应队列 -> 选择另一个进程执行，并更新其 PCB -> 根据 PCB 恢复新进程所需的运行环境。

引起进程切换的事件：当前进程时间片到、有更高优先级的进程到达、当前进程主动阻塞、当前进程终止。

无论哪个进程控制原语，要做的无非三类事情：更新 PCB 中的信息（修改进程状态 state 或是保存/恢复运行环境）、将 PCB 插入合适的队列、分配/回收资源。

进程通信（IPC）

进程间通信（lnter-Process Communication，IPC）是指两个进程之间产生数据交互。

进程是分配系统资源的单位（包括内存地址空间），因此各进程拥有的内存地址空问相互独立。为了保证安全，一个进程不能直接访问另一个进程的地址空间。

迸程通信的分类：共享存储、消息传递、管道通信。

共享存储：通过增加页表项/段表项即可将同一片共享内存区映射到各个进程的地址空间中。

为避免出错，各个进程对共享空间的访问应该是互斥的。各个进程可使用操作系统内核提供的同步互斥工具（如 P、V 操作）。
基于数据结构的共享：比如共享空间里只能放一个长度为 10 的数组。这种共享方式速度慢、限制多，是一种低级通信方式。
基于存储区的共享：操作系统在内存中划出一块共享存储区，数据的形式、存放位置都由通信进程控制，而不是操作系统。这种共享方式速度很快，是一种高级通信方式。

消息传递：进程间的数据交换以格式化的消息（Message）为单位。进程通过操作系统提供的发送消息/接收消息两个原语进行数据交换。

格式化的消息包括消息头和消息体，消息头包括：发送进程 ID、接受进程 ID、消息长度等格式化的信息。
直接通信方式：消息发送进程要指明接收进程的 ID。
间接通信方式：通过信箱作为中间实体间按地通信，因此又称信箱通信方式。可以名个进程往同一个信箱 send 消息，也可以多个进程从同一个信箱中 receive 消息。
管道（共享文件）通信方式：管道是一个特殊的共享文件，又名 pipe 文件。其实就是在内存中开辟一个大小固定的内存缓冲区（循环队列结构）。管道只能采用半双工通信，某一时间段内只能实现单向的传输。如果要实现双向同时通信，则需要设置两个管道。各进程要互斥地访问管道（由操作系统实现）。当管道写满时，写进程将阻塞，直到读进程将管道中的数据取走，即可唤醒写进程。当管道读空时，读进程将阻塞，直到写进程往管道中写入数据，即可唤醒读进程。管道中的数据一旦被读出，就彻底消失。因此，当多个进程读同一个管道时，可能会错乱。对此，通常有两种解决方案：①一个管道允许多个写进程，一个读进程；②允许有多个写进程，多个读进程，但系统会让各个读进程轮流从管道中读数据（Linux 的方案）。

写进程往管道写数据，即便管道没被写满，只要管道没空，读进程就可以从管道读数据。读进程从管道读数据，即便管道没被读空，只要管道没满，写进程就可以往管道写数据。

线程的概念

有的进程可能需要同时做很多事（如 QQ 视频聊天和文件处理），而传统的进程只能串行地执行一系列程序。为此，引入了线程，来增加并发度。线程是进程内一个相对独立的可调度的执行单元。引入线程后，线程成为了程序执行流的最小单位，进程只作为除 CPU 之外的系统资源的分配单元（如打印机、内存地址空间等都是分配给进程的）。

线程是独立调度的基本单位，进程是拥有资源的基本单位。线程不拥有资源，但线程可以访问其隶属进程的系统资源。进程之间可以并发执行，同一进程内的多个线程之间也可以并发执行。线程间并发，如果是同一进程内的线程切换，则不需要切换进程环境，引入线程后，并发所带来的系统开销减小，多线程之间的同步与通信非常容易实现。

线程的属性：线程是处理机调度的单位；多 CPU 计算机中，各个线程可占用不同的 CPU；每个线程都有一个线程 ID、线程控制块（TCB）；线程也有就绪、阻塞、运行三种基本状态；线程几乎不拥有系统资源；同一进程的不同线程间共享进程的资源；由于共享内存地址空间，同一进程中的线程间通信甚至无需系统干预；同一进程中的线程切换，不会引起进程切换；不同进程中的线程切换，会引起进程切换；切换同进程内的线程，系统开销很小，切换进程，系统开销较大。

线程的实现方式和多线程模型

用户级线程（User-Level Thread, ULT）：早期的操作系统（如：早期 Unix）只支持进程，不支持线程。当时的线程是由线程库实现的。很多编程语言提供了强大的线程库，可以实现线程的创建、销毁、调度等功能。

用户级线程由应用程序通过线程库实现，所有的线程管理工作都由应用程序负责（包括线程切换）。
用户级线程中，线程切换可以在用户态下即可完成，无需操作系统干预。在用户看来，是有多个线程。但是在操作系统内核看来，并意识不到线程的存在。用户级线程就是从用户视角看能看到的线程。
优点：用户级线程的切换在用户空间即可完成，不需要切换到核心态，线程管理的系统开销小，效率高。
缺点：用户级线程不依赖于操作系统核心，由于操作系统内核不了解用户线程的存在，当一个用户级线程被阻塞后，整个进程都会被阻塞，并发度不高。多个线程不可在多核处理机上并行运行。

内核级线程（Kernel-Level Thread，KLT）又称内核支持的线程：由操作系统支持的线程，大多数现代操作系统都实现了内核级线程，如 Windows、Linux。

内核级线程的管理工作由操作系统内核完成。线程调度、切换等工作都由内核负责，因此内核级线程的切换必然需要在核心态下才能完成。
操作系统会为每个内核级线程建立相应的 TCB（Thread Control Block，线程控制块），通过 TCB 对线程进行管理。内核级线程就是从操作系统内核视角看能看到的线程。
优点：内核级线程依赖于内核，一个内核级线程由于 I/O 操作而阻塞时，别的线程还可以继续执行，并发能力强。多线程可在多核处理机上并行执行。
缺点：一个用户进程会占用多个内核级线程，线程切换由操作系统内核完成，需要切换到核心态，因此线程管理的成本高，开销大。

多线程模型：在支持内核级线程的操作系统中，根据用户级线程和内核级线程的映射关系，可以划分为几种多线程模型。

一对一模型：一个用户级线程映射到一个内核级线程。每个用户进程有与用户级线程同数量的内核级线程。优点：当一个线程被阻塞后，别的线程还可以继续执行，并发能力强。多线程可在多核处理机上并行执行。缺点：一个用户进程会占用多个内核级线程，线程切换由操作系统内核完成，需要切换到核心态，因此线程管理的成本高，开销大。
多对一模型：多个用户级线程映射到一个内核级线程。且一个进程只被分配一个内核级线程。优点：用户级线程的切换在用户空间即可完成，不需要切换到核心态，线程管理的系统开销小，效率高。缺点：当一个用户级线程被阻塞后，整个进程都会被阻塞，并发度不高。多个线程不可在多核处理机上并行运行。
多对多模型：n 用户及线程映射到 m 个内核级线程（n >= m）。每个用户进程对应 m 个内核级线程。克服了多对一模型并发度不高的缺点（一个阻塞全体阻塞），又克服了一对一模型中一个用户进程占用太多内核级线程，开销太大的缺点。

操作系统只看得见内核级线程，因此只有内核级线程才是处理机分配的单位。用户级线程是代码逻辑的载体，内核级线程是运行机会的载体。一段代码逻辑只有获得了运行机会才能被 CPU 执行。内核级线程中可以运行任意一个有映射关系的用户级线程代码，只有两个内核级线程中正在运行的代码逻辑都阻塞时，这个进程才会阻塞。

线程的状态与转换

TCB（线程控制块）：

线程标识符：TID，与 PID 类似。
程序计数器 PC：线程目前执行到哪里。
其他寄存器：线程运行的中间结果。
堆栈指针：堆栈保存函数调用信息、局部变量等。
线程运行状态：运行/就绪/阻塞。
优先级：线程调度、资源分配的参考。

线程切换时要保存/恢复程序计数器、其他寄存器和堆栈指针。

可将多个 TCB 组织成一张线程表（Thread table）。

处理机调度的概念、层次

高级调度（作业调度）：按一定的原则从外存的作业后备队列中挑选一个或多个作业调入内存，并创建进程，以便该作业具有获得竞争处理器的权利。每个作业只调入一次，调出一次。作业调入时会建立 PCB，调出时才撤销 PCB。作业调度每次要接纳多少个作业进入内存取决于多道程序的并发程度。多道程序的并发程度应根据系统的规模和运算速度来决定。应将哪些作业从外存调入内存取决于所采取的调度算法。

要做什么：按照某种规则，从后备队列中选择合适的作业将其调入内存，并为其创建进程。
调度发生在：外存 -> 内存（面向作业)。发生频率最低。
对进程状态的影响：无 -> 创建态 -> 就绪态。

中级调度（交换调度）：内存不够时，可将某些进程的数据调出外存。等内存空闲或者进程需要运行时再重新调入内存。暂时调到外存等待的进程状态为挂起状态。被挂起的进程 PCB 会被组织成挂起队列，中级调度按照某种策略决定将哪个处于挂起状态的进程重新调入内存，并将其状态修改为就绪状态，挂在就绪队列上等待。一个进程可能会被多次调出、调入内存，因此中级调度发生的频率要比高级调度更高。

要做什么：按照某种规则，从挂起队列中选择合适的进程将其数据调回内存。
调度发生在：外存 -> 内存（面向进程）。发生频率中等。
对进程状态的影响：挂起态 -> 就绪态（阻塞挂起 -> 阻塞态）。

低级调度（进程调度）：按照某种策略和方法，从就绪队列中选取一个进程，将处理器先分配给他。进程调度是操作系统中最基本的一种调度，在一般的操作系统中都必须配置进程调度。进程调度的频率很高，一般几十毫秒一次。作业调度的结果是为作业创造进程，而进程调度的结果是进程被执行。

要做什么：按照某种规则，从就绪队列中选择一个进程为其分配处理机。
调度发生在：内存 -> CPU。发生频率最高。
对进程状态的影响：就绪态 -> 运行态。

进程的五状态模型 -> 七状态模型：暂时调到外存等待的进程状态为挂起状态（挂起态，suspend），挂起态又可以进一步细分为就绪挂起、阻塞挂起两种状态。创建态、就绪态、运行态、阻塞态、终止态。

注意挂起和阻塞的区别，两种状态都是暂时不能获得 CPU 的服务，但挂起态是将进程映像调到外存去了，而阻塞态下进程映像还在内存中。

进程调度的时机、切换与过程、方式

进程调度（低级调度），记录系统中所有进程的有关情况以及状态特征，选择获得处理器的进程和处理器分配，就是按照某种算法从就绪队列中选择一个进程为其分配处理机。处理器分配的任务由进程调度程序完成。

需要进行进程调度与切换的情况：

当前运行的进程主动放弃处理机：进程正常终止、运行过程中发生异常而终止、进程主动请求阻塞（如等待 I/O）。
当前运行的进程被动放弃处理机：分给进程的时间片用完、有更紧急的事需要处理（如 I/O 中断）、有更高优先级的进程进入就绪队列。

不能进行进程调度与切换的情况：

在处理中断的过程中。中断处理过程复杂，与硬件密切相关，很难做到在中断处理过程中进行进程切换。
进程在操作系统内核程序临界区中。
在原子操作过程中（原语）。原子操作不可中断，要一气呵成（如修改 PCB 中进程状态标志，并把 PCB 放到相应队列）。

进程在操作系统内核程序临界区中不能进行调度与切换。临界资源是一个时问段内只允许一个进程使用的资源。各进程需要互斥地访问临界资源。临界区是访问临界资源的那段代码。内核程序临界区一般是用来访问某种内核数据结构的，比如进程的就绪队列（由各就绪进程的 PCB 组成）。

内核程序临界区访问的临界资源如果不尽快释放的话，极有可能影响到操作系统内核的其他管理工作。因此在访问肉核程序临界区期间不能讲行调度与切换。
普通临界区访问的临界资源不会直接影响操作系统内核的管理工作。因此在访问普通临界区时可以进行调度与切换。

进程调度、切换是有代价的，并不是调度越频繁，并发度就越高。

进程调度的方式：

非剥夺调度方式，又称非抢占方式。即，只允许进程主动放弃处理机。在运行过程中即便有更紧迫的任务到达，当前进程依然会继续使用处理机，直到该进程终止或主动要求进入阻塞态。实现简单，系统开销小但是无法及时处理紧急任务，适合于早期的批处理系统。
剥夺调度方式，又称抢占方式。当一个进程正在处理机上执行时，如果有一个更重要或更紧迫的进程需要使用处理机，则立即暂停正在执行的进程，将处理机分配给更重要紧迫的那个进程。可以优先处理更紧急的进程，也可实现让各进程按时间片轮流执行的功能（通过时钟中断）。适合于分时操作系统、实时操作系统。

调度器和闲逛进程

调度程序决定：调度算法（让谁运行）和时间片大小（运行多长时间）。

什么事件会触发调度程序（调度时机）：创建新进程、进程退出、运行进程阻塞、I/O 中断发生（可能唤醒某些阻塞进程）。

非抢占式调度策略，只有运行进程阻塞或退出才触发调度程序工作。抢占式调度策略，每个时钟中断或 k 个时钟中断会触发调度程序工作。

不支持内核级线程的操作系统，调度程序（scheduler）的处理对象是进程。支持内校级线程的操作系统，调度程序的处理对象是内核线程。

闲逛进程：调度程序永远的备胎，没有其他就绪进程时，运行闲逛进程（idle）。闲逛进程的特性：优先级最低、能耗低、可以是 0 地址指令，占一个完整的指令周期（指令周期末尾例行检查中断）。

调度算法的评价指标

衡量调度算法的性能： CPU 利用率、系统吞吐量、响应时间、周转时间。

CPU 利用率 = 忙碌的时间 / 总时间。系统吞吐量 = 总共完成了多少道作业 / 总共花了多少时间。

作业的周转时间 = 作业的完成时间 - 作业的提交时间。平均周转时间 = 多个作业周转时间的平均值。带权周转时间 = 作业周转时间 / 作业实际运行时间。

带权周转时间必然 ≥ 1。带权周转时间与周转时间都是越小越好。

等待时间，指进程/作业处于等待处理机状态时间之和，等待时问越长，用户满意度越低。

对于进程来说，等待时间就是指进程建立后等待被服务的时间之和，在等待 I/O 完成的期问其实进程也是在被服务的，所以不计入等待时间。对于作业来说，不仅要考虑建立进程后的等待时间，还要加上作业在外存后备队列中等待的时间。

响应时间，指从用户提交请求到首次产生响应所用的时间。

调度算法

先来先服务调度算法（作业调度、进程调度）

先来先服务（First Come First Serve，FCFS）：非抢占式的算法，按照作业或进程进入就绪队列的先后次序来分配处理器，用于作业调度时，考虑的是哪个作业先到达后备队列，用于进程调度时，考虑的是哪个进程先到达就绪队列。

优点：公平、算法实现简单。
缺点：排在长作业（进程）后面的短作业需要等待很长时间，带权周转时间很大，对短作业来说用户体验不好。即，FCFS 算法对长作业有利，对短作业不利。
不会导致饥饿（某进程或作业长期得不到服务）。

短作业优先调度算法（作业调度、进程调度）（SJF，Shortest Job First）：当前已到达的最短的作业或进程优先得到服务（所谓最短，是指要求服务时间最短）。既可用于作业调度，也可用于进程调度。用于进程调度时称为短进程优先（SPF, Shortest Process First）算法。

SJF 和 SPF 是非抢占式的算法。但是也有抢占式的版本：最短剩余时间优先算法（SRTN, Shortest Remaining Time Next）。
最短剩余时间优先算法：每当有进程加入就绪队列改变时就需要调度，如果新到达的进程剩余时间比当前运行的进程剩余时间更短，则由新进程抢占处理机，当前运行进程重新回到就绪队列。另外，当一个进程完成时也需要调度。
优点：在所有进程都几乎同时到达时，采用 SJF 调度算法的平均等待时间、平均周转时间最少。抢占式的短作业或进程优先调度算法（SRNT 算法）的平均等待时间、平均周转时间最少。
缺点：不公平。对短作业有利，对长作业不利。可能产生饥饿现象。另外，作业/进程的运行时间是由用户提供的，并不一定真实，不一定能做到真正的短作业优先。

高响应比优先调度算法（作业调度）（HRRN，Highest Response Ratio Next）：在每次调度时先计算各个作业/进程的响应比，选择响应比最高的作业/进程为其服务，响应比 = 作业响应时间 / 估计运行时间 = (等待时间 + 要求服务时间) / 要求服务时间。要求服务时间 = 估计运行时间。

非抢占式的调度算法，只有当前运行的进程主动放弃 CPU 时（正常/异常完成，或主动阻塞），才需要进行调度，调度时计算所有就绪进程的响应比，选响应比最高的进程上处理机。
综合考虑了等待时间和运行时间（要求服务时间），对于长作业来说，随着等待时间越来越久，其响应比也会越来越大，从而避免了长作业饥饿的问题。

FCFS、SJF、HRRN 算法主要关心对用户的公平性、平均周转时间、平均等待时间等评价系统整体性能的指标，但是不关心响应时间，也并不区分任务的紧急程度，因此对于用户来说，交互性很糟糕。因此这三种算法一般适合用于早期的批处理系统，当然，FCFS 算法结合其他的算法使用也能在交互式系统中扮演着很重要的角色。

时间片轮转调度算法（进程调度）（RR，Round-Robin）：按照各进程到达就绪队列的顺序，轮流让各个进程执行一个时间片（如 100ms）。若进程末在一个时间片内执行完，则剥夺处理机，将进程重新放到就绪队列队尾重新排队，默认新到达的进程先进入就绪队列。

用于进程调度（只有作业放入内存建立了相应的进程后，才能被分配处理机时间片），若进程未能在时间片内运行完，将被强行剥夺处理机使用权，因此时问片轮转调度算法属于抢占式的算法。由时钟装置发出时钟中断来通知 CPU 时间片已到。
如果时间片太大，使得每个进程都可以在一个时问片内就完成，则时间片轮转调度算法退化为先来先服务调度算法，并且会增大进程响应时问。因此时间片不能太大。
另一方面，进程调度、切换是有时间代价的（保存、恢复运行环境），因此如果时间片太小，会导致进程切换过于频繁，系统会花大量的时问来处理进程切換，从而导致实际用于进程执行的时间比例减少。可见时间片也不能太小。
优点：公平，响应快，适用于分时操作系统；缺点：由于高频率的进程切换，因此有一定开销，不区分任务的紧急程度。
系统的处理能力决定时间片的大小，就绪队列中的进程数与时间片的大小成反比。

优先级调度算法（作业调度、进程调度）：每个作业/进程有各自的优先级，调度时选择优先级最高的作业/进程，既可用于作业调度，也可用于进程调度。甚至，还会用于 I/O 调度中。

基于优先级的调度算法还可按调度方式的不同，分为非抢占优先级调度算法和抢占优先级调度算法，区别在于非抢占式只需在进程主动放弃处理机时进行调度即可，而抢占式还需在就绪队列变化时，检查是否会发生抢占。
根据优先级是否可以动态改变，可将优先级分为静态优先级和动态优先级两种。静态优先级是在创建进程时确定的，确定之后整个进程运行期间不再改变。动态优先级是指在创建进程时根据进程的特点及相关情况确定一个优先级。
按进程类、作业的资源要求、用户类型和要求确定静态优先级。根据进程占有 CPU 时间的长短和就绪进程等待 CPU 时间的长短确定动态优先级。
在优先级相同的情况下，通常按照先来先服务或者短作业优先的顺序执行。
优先级调度算法优点：用优先级区分紧急程度、重要程度，适用于实时操作系统。可灵活地调整对各种作业/进程的偏好程度。缺点：若源源不断地有高优先级进程到来，则可能导致饥饿。

多级反馈队列调度算法（作业调度）：对其他调度算法的折中权衡，是时间片轮转调度算法和优先级调度算法的综合与发展，用于进程调度。

设置多级就绪队列，各级队列优先级从高到低，时间片从小到大。
新进程到达时先进入第 1 级队列，按 FCFS 原则排队等待被分配时间片，若用完时间片进程还未结束，则进程进入下一级队列队尾。如果此时已经是在最下级的队列，则重新放回该队列队尾。
只有第 k 级队（更高级别）列为空时，才会为 k+1 级队头的进程分配时间片。

多级反馈队列调度算法是抢占式的算法。在 k 级队列的进程运行过程中，若更上级的队列（1~k1级）中进入了一个新进程，则由于新进程处于优先级更高的队列中，因此新进程会抢占处理机，原来运行的进程放回 k 级（原来）队列队尾。
对各类型进程相对公平（FCFS 的优点）；每个新到达的进程都可以很快就得到响应（RR 的优点）；短进程只用较少的时间就可完成（SPF 的优点），不必实现估计进程的运行时间（避免用户作假），可灵活地调整对各类进程的偏好程度，比如 CPU 密集型进程、I/O 密集型进程（可以将因 I/O 而阻塞的进程重新放回原队列，这样 I/O 型进程就可以保持较高优先级）。
一般不说它有缺点，不过可能导致饥饿。

多级队列调度算法：系统中按进程类型设置多个队列，进程创建成功后插入某个队列。

队列之问可采取固定优先级，或时间片划分固定优先级：高优先级空时低优先级进程才能被调度时间片划分（如三个队列分配时间 50%、40%、10%）。
各队列可采用不同的调度策略，如：系统进程队列（内存管理进程）采用优先级调度、交互式队列（应用软件）采用 RR、批处理队列（训练 AI）采用 FCFS。

进程同步与互斥

进程具有异步性的特征。异步性是指，各并发执行的进程以各自独立的、不可预知的速度向前推进。同步亦称直接制约关系，它是指为完成某种任务而建立的两个或多个进程，这些进程因为需要在某些位置上协调它们的工作次序而产生的制约关系。进程间的直接制约关系就是源于它们之问的相互合作。

进程的并发又需要共享的支持。各个并发执行的进程不可避免的需要共享一些系统资源（比如内存，又比如打印机、摄像头这样的 I/O 设备）。互斥共享方式指的是系统中的某些资源，虽然可以提供给多个进程使用，但一个时间段内只允许一个进程访问该资源。

一个时间段内只允许一个进程使用的资源称为临界资源。许多物理设备（比如摄像头、打印机）都属于临界资源。此外还有许多变量、数据、内存缓冲区等都属于临界资源。

对临界资源的访问，必须互斥地进行。互斥，亦称间接制约关系。进程互斥指当一个进程访问某临界资源时，另一个想要访问该临界资源的进程必须等待。当前访问临界资源的进程访问结束，释放该资源之后，另一个进程才能去访问临界资源。

互斥是间接相互制约关系，而同步是直接相互制约关系，只要是同类进程即为互斥关系，不同类进程即为同步关系。

对临界资源的互斥访问，可以在逻辑上分为进入区（检查是否可进入临界区，若可进入，需要上锁）、临界区（访问临界资源的那段代码）、退出区（负责解锁）、剩余区（其余代码部分）。临界区是进程中访问临界资源的代码段。进入区和退出区是负责实现互斥的代码段。临界区也可称为临界段。每个进程的临界区代码可以不相同。

为了实现对临界资源的互斥访问，同时保证系统整体性能，需要遵循以下原则：空闲让进（临界区空闲时，应允许一个进程访问），忙则等待（临界区正在被访问时，其他试图访问的进程需要等待），有限等待（要在有限时间内进入临界区，保证不会饥饿），让权等待（进不了临界区的进程，要释放处理机，防止忙等）。

进程互斥的软件实现方法

单标志法：两个进程在访问完临界区后会把使用临界区的权限转交给另一个进程。也就是说每个进程进入临界区的权限只能被另一个进程赋予。该算法可以实现同一时刻最多只允许一个进程访问临界区。单标志法存在的主要问题是：违背空闲让进原则。

int turn = 0; // turn 表示当前允许进入临界区的进程号
// P0 进程
while (turn != 0);  //进入区
critical section;   //临界区
turn = 1;      //退出区
remainder section;  //剩余区
// P1 进程
while (turn != 1);  //进入区
critical section;   //临界区
turn = 0;      //退出区
remainder section;  //剩余区

双标志先检查法：设置一个布尔型数组 flag[]，数组中各个元素用来标记各进程想进入临界区的意愿，比如 flag[0]=ture 意味着 0 号进程 P0 现在想要进入临界区。每个进程在进入临界区之前先检查当前有没有别的进程想进入临界区，如果没有，则把自身对应的标志 flag[i] 设为 true，之后开始访问临界区。双标志先检查法的主要问题是：违反忙则等待原则。

bool flag[2];  //表示进入临界区意愿的数组
flag[0] = false;
flag[1] = false;  //刚开始设置为两个进程都不想进入临界区
// P0 进程
while (flag[1]);  //如果此时 P1 想进入临界区，P0 就一直循环等待
flag [0] = true;  //标记为 P0 进程想要进入临界区
critical section;   //临界区
flag [0] = false;  //访问完临界区，修改标记为 P0  不想使用临界区
remainder section;  //剩余区
// P1 进程
while (flag[0]);  //如果此时 P0 想进入临界区，P1 就一直循环等待
flag [1] = true;  //标记为 P1 进程想要进入临界区
critical section;   //临界区
flag [1] = false;  //访问完临界区，修改标记为 P1 不想使用临界区
remainder section;  //剩余区

双标志后检查法：双标志先检查法的改良，先上锁，后检查。双标志后检查法虽然解决了忙则等待的问题，但是又违背了空闲让进和有限等待原则，会因各进程都长期无法访问临界资源而产生饥饿现象。两个进程都争着想进入临界区，但是谁也不让谁，最后谁都无法进入临界区。

bool flag[2];  //表示进入临界区意愿的数组
flag[0] = false;
flag[1] = false;  //刚开始设置为两个进程都不想进入临界区
// P0 进程
flag [0] = true;  //标记为 P0 进程想要进入临界区
while (flag[1]);  //如果此时 P1 也想进入临界区，P0 就一直循环等待
critical section;   //临界区
flag [0] = false;  //访问完临界区，修改标记为 P0  不想使用临界区
remainder section;  //剩余区
// P1 进程
flag [1] = true;  //标记为 P1 进程想要进入临界区
while (flag[0]);  //如果此时 P0 也想进入临界区，P1 就一直循环等待
critical section;   //临界区
flag [1] = false;  //访问完临界区，修改标记为 P1 不想使用临界区
remainder section;  //剩余区

Peterson 算法：结合双标志法、单标志法的思想。如果双方都争着想进入临界区，那可以让进程尝试谦让，做一个有礼貌的进程。Peterson 算法用软件方法解决了进程互斥问题，遵循了空闲让进、忙则等待、有限等待三个原则，但是依然末遵循让权等待的原则，会发生忙等。

bool flag [2];  //表示进入临界区意愿的数组，初始值都是false
int turn = 0;  //turn 表示优先让哪个进程进入临界区
// P0 进程
flag[0] = true;  //表示自己想进入临界区
turn = 1;   //可以优先让对方进入临界区
while (flag[1] && turn==1); //对方想进，且最后一次是自己“让梨”，那自己就循环等待
critical section;
flag[0] = false;  //访问完临界区，表示自己已经不想访问临界区了
remainder section;
// P1 进程
flag[1] = true;  //表示自己想进入临界区
turn = 0;   //可以优先让对方进入临界区
while (flag[0] && turn==0) ;  //对方想进，且最后一次是自己“让梨”，那自己就循环等待
critical section;
flag[1] = false;  //访问完临界区，表示自己已经不想访问临界区了
remainder section;

进程互斥的硬件实现方法

中断屏蔽方法：利用开/关中断指令实现（与原语的实现思想相同，即在某进程开始访问临界区到结束访问为止都不允许被中断，也就不能发生进程切换，因此也不可能发生两个同时访问临界区的情况）。

关中断后即不允许当前进程被中断，也必然不会发生进程切换，直到当前进程访问完临界区，再执行开中断指令，才有可能有别的进程上处理机并访问临界区。
优点：简单高效。缺点：不适用于多处理机、只适用于操作系统内核进程，不适用于用户进程（因为开/关中断指令只能运行在内核态，这组指令如果能让用户随意使用会很危险）

TestAndSet 指令：简称 TS 指令，也有地方称为 TestAndSetLock 指令，或 TSL 指令。TSL 指令是用硬件实现的，执行的过程不允许被中断，只能一气呵成。

//布尔型共享变量 lock 表示当前临界区是否被加锁
//true 表示已加锁，false 表示未加锁
bool TestAndSet (bool *lock) {
    bool old;
    old = *lock;  //old 用来存放 lock 原来的值
    *lock = true;  //无论之前是否已加锁，都将 lock 设为 true
    return old;  //返回 lock 原来的值
}
//以下是使用 TSL 指令实现互斥的算法逻辑
while (TestAndset (&lock));  //上锁并检查
临界区代码段。。。
lock = false;  //解锁
剩余区代码段。。。

若刚开始 lock 是 false，则 TSL 返回的 old 值为 false，while 循环条件不满足，直接跳过循环，进入临界区。若刚开始 lock 是 true，则执行 TLS 后 old 返回的值为 true，while 循环条件满足，会一直循环，直到当前访问临界区的进程在退出区进行解锁。
相比软件实现方法，TSL 指令把上锁和检查操作用硬件的方式变成了一气呵成的原子操作。优点：实现简单，无需像软件实现方法那样严格检查是否会有逻辑漏洞；适用于多处理机环境。缺点：不满足让权等待原则，暂时无法进入临界区的进程会占用 CPU 并循环执行 TSL 指令，从而导致忙等。

Swap 指令：有的地方也叫 Exchange 指令，或简称 XCHG 指令。Swap 指令是用硬件实现的，执行的过程不允许被中断，只能一气呵成。

逻辑上来看 Swap 和 TSL 并无太大区别，都是先记录下此时临界区是否已经被上锁（记录在 old 变量上），再将上锁标记 lock 设置为 true，最后检查 old，如果 old 为 false 则说明之前没有别的进程对临界区上锁，则可跳出循环，进入临界区。
优点：实现简单，无需像软件实现方法那样严格检查是否会有逻辑漏洞;适用于多处理机环境。
缺点：不满足让权等原则，暂时无法进入临界区的进程会占用 CPU 并循环执行 TSL 指令，从而导致忙等。

//Swap 指令的作用是交换两个变量的值
Swap (bool *a，bool *b){
    bool temp;
   	temp = *a;
  	*а = *b;
  	*b = temp;
}
//以下是用 Swap 指令实现互斥的算法逻辑
//lock 表示当前临界区是否被加锁
bool old = true;
while (old == true)
		Swap (&lock, &old);
临界区代码段。。。
lock = false;
剩余区代码段。。。

互斥锁

解决临界区最简单的工具就是互斥锁（mutex lock）。一个进程在进入临界区时应获得锁；在退出临界区时释放锁。函数 acquire() 获得锁，而函数 release() 释放锁。

每个互斥锁有一个布尔变量 available，表示锁是否可用。如果锁是可用的，调用 acqiure() 会成功，且锁不再可用。当一个进程试图获取不可用的锁时，会被阻塞，直到锁被释放。

//进入区执行
acquire (){
  	while (!available)
				;    //忙等待
    available = false;  //获得锁
}
//退出区执行
release() {
		available = true;  //释放锁
}

acquire() 或 release() 的执行必须是原子操作，因此互斥锁通常采用硬件机制来实现。

互斥锁的主要缺点是忙等待，当有一个进程在临界区中，任何其他进程在进入临界区时必须连续循环调用 acquire()。当多个进程共享同一 CPU 时，就浪费了 CPU 周期。因此，互斥锁通常用于多处理器系统，一个线程可以在一个处理器上等待，不影响其他线程的执行。

需要连续循环忙等的互斥锁，都可称为自旋锁（spin lock），如 TSL 指令、swap 指令、单标志法。

特性：

需忙等，进程时间片用完才下处理机，违反让权等待。
优点：等待期间不用切换进程上下文，多处理器系统中，若上锁的时间短，则等待代价很低。
常用于多处理器系统，一个核忙等，其他核照常工作，并快速释放临界区。
不太适用于单处理机系统，忙等的过程中不可能解锁。

信号量机制

1965年，荷兰学者 Dikstra 提出了一种卓有成效的实现进程互斥、同步的方法：信号量机制。

用户进程可以通过使用操作系统提供的一对原语来对信号量进行操作，从而很方便的实现了进程互斥、进程同步。

信号量其实就是一个变量（可以是一个整数，也可以是更复杂的记录型变量），可以用一个信号量来表示系统中某种资源的数量，比如：系统中只有一台打印机，就可以设置一个初值为 1 的信号量。

原语是一种特殊的程序段，其执行只能一气呵成，不可被中断。原语是由关中断/开中断指令实现的。软件解决方案的主要问题是由进入区的各种操作无法一气呵成，因此如果能把进入区、退出区的操作都用原语实现，使这些操作能一气呵成就能避免问题。

一对原语：wait(S) 原语和 signal(S) 原语，可以把原语理解为我们自己写的函数，函数名分别为 wait 和 signal，括号里的信号量 S 其实就是函数调用时传入的一个参数。wait、signal 原语常简称为 P、V 操作（来自荷兰语 proberen 和 verhogen）。因此，做题的时候常把 wait(S)、signal(S) 两个操作分别写为 P(S)、V(S)。

整型信号量：用一个整数型的变量作为信号量，用来表示系统中某种资源的数量。与普通整数变量的区别：对信号量的操作只有三种，即初始化、P 操作、V 操作。

检查和上锁一气呵成，避免了并发、异步导致的问题。
存在的问题：不满足让权等待原则，会发生忙等。

//某计算机系统中有一台打印机
int S = 1; //初始化整型信号量 s，表示当前系统中可用的打印机资源数
void wait (int S) {  //wait 原语，相当于进入区
    while (S <= 0);    //如果资源数不够，就一直循环等待
    S = S - 1;        //如果资源数够，则占用一个资源
}
void signal (int S) {  //signal 原语，相当于退出区
		S = S + 1;        //使用完资源后，在退出区釋放资源
}
// 进程 P0, P1 ... Pn
...
wait(S);    // 进入区，申请资源
使用打印机资源。。。 //临界区，访问资源
signal(S);    //退出区，释放资源
...

记录型信号量：整型信号量的缺陷是存在忙等问题，因此人们又提出了记录型信号量，即用记录型数据结构表示的信号量。

S.value 的初值表示系统中某种资源的数目。
对信号量 S 的一次 P 操作意味着进程请求一个单位的该类资源，因此需要执行 S.value--，表示资源数减 1，当 S.value < 0 时表示该类资源己分配完毕，因此进程应调用 block 原语进行自我阻塞（当前运行的进程从运行态变为阻塞态），主动放弃处理机，并插入该类资源的等待队列 S.L 中。可见，该机制遵循了让权等待原则，不会出现忙等现象。
对信号量 S 的一次 V 操作意味着进程释放一个单位的该类资源，因此需要执行 S.value++，表示资源数加 1，若加 1 后仍是 S.value <= 0，表示依然有进程在等待该类资源，因此应调用 wakeup 原语唤醒等待队列中的第一个进程（被唤醒进程从阻塞态变为就绪态）。

/* 记录型信号量的定义 */
typedef struct {
    int value;  //剩余资源数
    struct process *L;  //等待队列
} semaphore;
/* 某进程需要使用资源时，通过 wait 原语申请 */
void wait (semaphore S) {
    S.value--;
    if (S.value < 0 ) {
    		block (S.L);
    }
}
/*进程使用完资源后，通过 signal 原语释放*/
void signal (semaphore S) {
    S.value++;
    if (S.value <= 0) {    //S.value == -n 表示有 n 个进程在等待
				wakeup(S.L);
    } 
}

用信号量实现进程互斥、同步、前驱关系

一个信号量对应一种资源。信号量的值 = 这种资源的剩余数量（信号量的值如果小于 0，说明此时有进程在等待这种资源）。P(S)：申请一个资源 S，如果资源不够就阻塞等待。V(S)：释放一个资源 S，如果有进程在等待该资源，则唤醒一个进程。

信号量机制实现进程互斥：

分析并发进程的关键活动，划定临界区（如：对临界资源打印机的访问就应放在临界区）。
设置互斥信号量 mutex，初值为 1。信号量 mutex 表示进入临界区的名额。
在进入区 P(mutex) 申请资源。在退出区 V(mutex) 释放资源。

/* 信号量机制实现互斥 */
semaphore mutex = 1;  //初始化记录型信号量
P1() {
    。。。
    P(mutex);  //使用临界资源前需要加锁
    临界区代码段。。。
    V(mutex);  //使用临界资源后需要解锁
    。。。
}

对不同的临界资源需要设置不同的互斥信号量。P、V 操作必须成对出现。缺少 P(mutex) 就不能保证临界资源的互斥访问。缺少 V(mutex) 会导致资源永不被释放，等待进程永不被唤醒。

信号量机制实现进程同步（让各并发进程按要求有序地推进）：

分析什么地方需要实现同步关系，即必须保证—前一后执行的两个操作（或两句代码）。
设置同步信号量 S，初始为 0。
在每个前操作之后执行 V(S)。在每个后操作之前执行 P(S)。前 V 后 P。

//信号量S代表某种资源，刚开始是没有这种资源的。P2需要使用这种资源，而又只能由P1中的代码2产生这种资源。
/* 信号量机制实现同步 */
semaphore S = 0;  //初始化记录型信号量为 0
P1 () {
  	代码1; 代码2;
  	V(S);
  	代码3;
}
P2 () {
  	P(S);
  	代码4; 代码5; 代码6;
} // 保证了代码4一定是在代码2之后执行

若先执行到 V(S) 操作，则 S++ 后 S==1。之后当执行到 P(S) 操作时，由于 S==1，表示有可用资源，会执行 S--，S 的值变回 0，P2 进程不会执行 block 原语，而是继续往下执行代码4。
若先执行到 P(S) 操作，由于 S==0，S-- 后 S==-1，表示此时没有可用资源，因此 P 操作中会执行 block 原语，主动请求阻塞。之后当执行完代码2，继而执行 V(S) 操作，S++，使 S 变回 0，由于此时有进程在该信号量对应的阻塞队列中，因此会在 V 操作中执行 wakeup 原语，唤醒 P2进程。这样 P2 就可以继续执行代码4了。

生产者-消费者问题

系统中有一组生产者进程和一组消费者进程，生产者进程每次生产一个产品放入缓冲区，消费者进程每次从缓冲区中取出一个产品并使用。（这里的产品理解为某种数据）。

生产者、消费者共享一个初始为空、大小为 n 的缓冲区。缓冲区是临界资源，各进程必须互斥地访问。

只有缓冲区没满时，生产者才能把产品放入缓冲区，否则必须等待。只有缓冲区不空时，消费者才能从中取出产品，否则必须等待。

有产品（缓冲区没空）V - full - P 消费者消费。生产者生产 P - empty - V 缓冲区没满。

semaphore mutex = 1;  //互斥信号量，实现对缓冲区的互斥访问
semaphore empty = n;  //同步信号量，表示空闲缓冲区的数量
semaphore full = 0;  //同步信号量，表示产品的数量，也即非空缓冲区的数量
producer() {
    while(1) {
        生产一个产品;
        P(empty);  //消耗一个空闲缓冲区
        P(mutex);  
        把产品放入缓冲区;
        V(mutex);  //实现互斥是在同一进程中进行一对 PV 操作
        V(full);  //增加一个产品
    }  //实现两进程的同步关系，是在其中一个进程中执行 P，另一进程中执行 V
}
consumer() {
    while(1) {
        P(full); //消耗一个产品
        P(mutex);  
        从缓冲区取出一个产品;
        V(mutex);
        V(empty);  //增加一个空闲缓冲区
        使用产品; 
    }
}

实现互斥的 P 操作一定要在实现同步的 P 操作之后，否则会导致死锁。V 操作不会导致进程阻塞，因此两个 V 操作顺序可以交换。

PV 操作题目分析步骤：

关系分析。找出题目中描述的各个进程，分析它们之间的同步、互斥关系。
整理思路。根据各进程的操作流程确定 P、V 操作的大致顺序。
设置信号量。并根据题目条件确定信号量初值。（互斥信号量初值一般为 1，同步信号量的初始值要看对应资源的初始值是多少）。

多生产者-多消费者问题

桌子上有一只盘子，每次只能向其中放入一个水果。爸爸专向盘子中放苹果，妈妈专向盘子中放橘子，儿子专等着吃盘子中的橘子，女儿专等着吃盘子中的苹果。只有盘子空时，爸爸或妈妈才可向盘子中放一个水果。仅当盘子中有自己需要的水果时，儿子或女儿可以从盘子中取出水果。用 PV 操作实现上述过程（缓冲区大小为 1，初始为空）。

semaphore mutex = 1;  //实现互斥访问盘子（缓冲区）
semaphore apple = 0;  //盘子中有几个苹果
semaphore orange = 0;  //盘子中有几个橘子
semaphore plate = 1;  //盘子中还可以放多少个水果
dad () {
	while (1){
			准备一个苹果;
			P(plate);
    	P(mutex);
			把苹果放入盘子;
    	V(mutex);
			V(apple);
  }
}
mom () {
	while(1){
			准备一个橘子;
			P(plate);
    	P(mutex);	
			把橘子放人盘子;
    	V(mutex);
			V(orange);
  }
}
doughter () {
	while (1) {
			P(apple);
    	P(mutex);
			从盘中取出苹果;
    	V(mutex);
			V(plate);
			吃掉苹果;
  }
}
son () {
	while (1) {
			P (orange);
    	P(mutex);
			从盘中取出橘子;
    	V(mutex);
			V(plate);
			吃掉橘子;
  }
}

本题中的缓冲区大小为 1，在任何時刻，apple、orange、plate 三个同步信号量中最多只有一个是 1，因此在任何时刻，最多只有一个进程的 P 操作不会被阻塞，并顺利进入临界区。所以即使不设置专门的互斥变量 mutex，也不会出现多个进程同时访问盘子的现象。如果缓冲区大小大于 1，就必须专门设置一个互斥信号量 mutex 来保证互斥访问缓冲区。

实现互斥的 P 操作一定要在实现同步的 P 操作之后，否则可能列起死锁。

在分析同步问题（一前一后问题）的时候不能从单个进程行为的角度来分析，要把一前一后发生的事看做是两种事件的前后关系。

吸烟者问题

假设一个系统有三个抽烟者进程和一个供应者进程。每个抽烟者不停地卷烟并抽掉它，但是要卷起并抽掉一支烟，抽烟者需要有三种材料：烟草、纸和胶水。三个抽烟者中，第一个拥有烟草、第二个拥有纸、第三个拥有胶水。供应者进程无限地提供三种材料，供应者每次将两种材料放桌子上，拥有剩下那种材料的抽烟者卷一根烟并抽掉它，并给供应者进程一个信号告诉完成了，供应者就会放另外两种材料再桌上，这个过程一直重复（让三个抽烟者轮流地抽烟）。

semaphore offer = 0;  //桌上组合一的数量
semaphore offer2 = 0;  //桌上组合二的数量
semaphore offer3 = 0;  //桌上组合三的数量
semaphore finish = 0;  //抽烟是否完成
int i = 0;  //用于实现三个抽烟者轮流抽烟
provider () {
  while (1) {
    	if (i==0) {
        	将组合一放桌上;
        	V(offer1);
      } else if (i==1) {
        	将组合二放桌上;
					V(offer2);
			} else if (i==2) {
        	将组合三放桌上;
          V(offer3);
      }
			i = (i+1) % 3;
			P(finish);
  }
}
smoker1 () {
  while (1) {
      P(offer1);
      从桌上拿走组合一; 卷烟; 抽掉;
      V(finish);
  }
}
smoker2 () {
  while (1) {
      P(offer2);
      从桌上拿走组合二; 卷烟; 抽掉;
      V(finish);
  }
}
smoker3 () {
  while (1) {
      P(offer3);
      从桌上拿走组合三; 卷烟; 抽掉;
      V(finish);
  }
}

缓沖区大小为 1，同一时刻，四个同步信号量中至少有一个的值为 1，不需要设置一个专门的互斥信号量。

若一个生产者要生产多种产品（或者说会引发多种前驱事件），那么各个 V 操作应该放在各自对应的事件发生之后的位置。

读者写者问题

有读者和写者两组并发进程，共享一个文件，当两个或两个以上的读进程同时访问共享数据时不会产生副作用，但若某个写进程和其他进程（读进程或写进程）同时访问共享数据时则可能导致数据不一致的错误。因此要求：①允许多个读者可以同时对文件执行读操作；②只允许一个写者往文件中写信息；③任一写者在完成写操作之前不允许其他读者或写者工作；④写者执行写操作前，应让已有的读者和写者全部退出。

与消费者进程不同，读者进程在读数据后并不会将数据清空，并不会改变数据。因此多个读者可同时访问共享数据。读进程与写进程同时共享数据，可能导致读出的数据不一致的问题。两个写进程同时共享数据，可能导致数据错误覆盖的问题。读者进程和读者进程不互斥。写者进程和读者进程或写者进程都互斥。

//读者优先算法
semaphore rw=1;  //用于实现对共享文件的互斥访问
int count = 0;  //记录当前有几个读进程在访问文件
semaphore mutex = 1;  //用于保证对count变量的互斥访问
writer () {
  while (1) {
      P(rw)；//写之前加锁
      写文件。。。
      V(rw)；//写完了解锁
  }
}
reader () {
  while (1) {
      P(mutex);  //各读进程互斥访问count
      if (count==0)  //由第一个读进程负责
      		P(rw);    //读之前加锁
      count++;    //访问文件的读进程数+1
      V(mutex);
      读文件。。。
      P(mutex);  //各读进程互斥访问count
      count--;   //访问文件的读进程数-1
      if (count==0)  //由最后一个读进程负责
      		V(rw);    //读完了解锁
      V(mutex);
  }
}

//连续进入的多个读者可以同时读文件：写者和其他进程不能同时访问文件：写者不会饥饿，是相对公平的先来先服务原则。
semaphore rw=1;  //用于实现对共享文件的互斥访问
int count = 0;  //记录当前有几个读进程在访问文件
semaphore mutex = 1;  //用于保证对count变量的互斥访问
semaphore w = 1;  //用于实现写优先
writer () {
  while (1) {
      P(w);
      P(rw);
      写文件。。。
      V(rw);
      V(w);
	}
}
reader () {
  while (1) {
  		P(w);
      P(mutex);
      if (count==0)
      		P(rw);
      count++;
      V(mutex);
      V(w);
      读文件。。。
      P(mutex);
      count--;
      if (count==0)
      		V(rw);
      V(mutex);
	}
}

读者-写者问题为我们解决复杂的互斥问题提供了一个参考思路。其核心思想在于设置了一个计数器 count 用来记录当前正在访问共享文件的读进程数。我们可以用 count 的值来判断当前进入的进程是否是第一个/最后一个读进程，从而做出不同的处理。

另外，对 count 变量的检查和赋值不能一气呵成导致了一些错误，如果需要实现一气呵成，自然应该想到用互斥信号量。

最后，还要认真体会我们是如何解决写进程饥饿问题的。

哲学家进餐问题

一张圆桌上坐着 5 名哲学家，每两个哲学家之间的桌上摆一根筷子，桌子的中间是一碗米饭。哲学家们倾注毕生的精力用于思考和进餐，哲学家在思考时，并不影响他人。只有当哲学家饥饿时，才试图拿起左、右两根筷子（一根一根地拿起）。如果筷子已在他人手上，则需等待。饥饿的哲学家只有同时拿起两根筷子才可以开始进餐，当进餐完毕后，放下筷子继续思考。

最多允许4个哲学家同时进餐，仅当一个哲学家左右两边的筷子同时可用时，他才可以拿起筷子，将哲学家编号要求奇数号的哲学家先拿左边筷子，偶数号的哲学家先拿右边筷子。

定义互斥信号量数组 chopstick[5]={1,1,1,1,1} 用于实现对 5 个筷子的互斥访问。并对哲学家按 0 ~ 4 编号，哲学家 i 左边的筷子编号为 i，右边的筷子编号为 (i+1)%5。

semaphore chopstick[5] = {1,1,1,1,1};
semaphore mutex = 1;  //互斥地取筷子
Pi () {  //i号哲学家的进程
  while (1) {
      P(mutex);
      P(chopstick[i]);  //拿左
      P(chopstick[(i+1)%5]); //拿右
      V(mutex);
      吃饭。。。
      V(chopstick[i]); //放左
      V(chopstick[(i+1)%5]); //放右
      思考。。。
  }
}

更准确的说法应该是：各哲学家拿筷子这件事必须互斥的执行。这就保证了即使一个哲学家在拿筷子拿到一半时被阻塞，也不会有别的哲学家会继续尝试拿筷子。这样的话，当前正在吃饭的哲学家放下筷子后，被阻塞的哲学家就可以获得等待的筷子了。

哲学家进餐问题的关键在于解决进程死锁。这些进程之间只存在互斥关系，但是与之前接触到的互斥关系不同的是，每个进程都需要同时持有两个临界资源，因此就有死锁问题的隐患。

如果在考试中遇到了一个进程需要同时持有多个临界资源的情况，应该参考哲学家问题的思想，分析题中给出的进程之间是否会发生循环等待，是否会发生死锁。可以参考哲学家就餐问题解决死锁的三种思路。

管程

信号量机制存在的问题：编写程序困难、易出错。1973年，Brinch Hansen 首次在程序设计语言（Pascal）中引入了管程成分，是一种高级同步机制。

管程是一种特殊的软件模块，定义了一个数据结构和能为并发进程所执行的一组操作，有这些部分组成：

局部于管程的共享数据结构说明；
对该数据结构进行操作的一组过程（函数）：
对局部于管程的共享数据设置初始值的语句；
管程有一个名字。

管程的基本特征：

局部于管程的数据只能被局部于管程内的过程所访问；
一个进程只有通过调用管程内的过程才能进入管程访问共享数据；
每次仅允许一个进程在管程内执行某个内部过程，即进程互斥地通过调用内部过程进入管程。

引入管程的目的无非就是要更方便地实现进程互斥和同步。

需要在管程中定义共享数据（如生产者消费者问题的缓冲区）。
需要在管程中定义用于访问这些共享数据的入口，其实就是一些函数（如生产者消费者问题中，可以定义一个函数用于将产品放入缓冲区，再定义一个函数用于从缓冲区取出产品）。
只有通过这些特定的入口才能访问共享数据。
管程中有很多入口，但是每次只能开放其中一个入口，并且只能让一个进程或线程进入（如生产者消费者问题中，各进程需要互斥地访问共享缓冲区。管程的这种特性即可保证一个时间段内最多只会有一个进程在访问缓冲区。这种互斥特性是由编译器负责实现的）。
可在管程中设置条件变量及等待/唤醒操作以解决同步问题。可以让一个进程或线程在条件变量上等待（此时，该进程应先释放管程的使用权，也就是让出入口）；可以通过唤醒操作将等待在条件变量上的进程或线程唤醒。

程序员可以用某种特殊的语法定义一个管程（比如：monitor ProducerConsumer … end monitor; ），之后其他程序员就可以使用这个管程提供的特定入口很方便地使用实现进程同步/互斥了。

Java 中类似管程的概念：如果用关键字 synchronized 来描述一个函数，那么这个函数同一时间段内只能被一个线程调用。

static class Monitor {
    private Item buffer[] = new Item[N];
    private int count = 0;
    public synchronized void insert (Item item) {
      	...
    }
}

死锁的概念

死锁：在并发环境下，各进程因竞争资源而造成的一种互相等待对方手里的资源，导致各进程都阻塞，都无法向前推进的现象，就是死锁。发生死锁后若无外力干涉，这些进程都将无法向前推进。参死锁的进程至少有两个，发生死锁的进程一定处于阻塞态。

饥饿：由于长期得不到想要的资源，某进程无法向前推进的现象。比如：在短进程优先（SPF）算法中，若有源源不断的短进程到来，则长进程将一直得不到处理机，从而发生长进程饥饿。可能只有一个进程发生饥饿。发生饥饿的进程既可能是阻塞态（如长期得不到需要的 I/O 设备），也可能是就绪态（长期得不到处理机）。

死循环：某进程执行过程中一直跳不出某个循环的现象。有时是因为程序逻辑 bug 导致的，有时是程序员故意设计的。死循环可以是运行态。死锁和饥饿是管理者（操作系统）的问题，死循环是被管理者的问题。

产生死锁必须同时满足一下四个条件，只要其中任一条件不成立，死锁就不会发生。

互斥条件：只有对必须互斥使用的资源的争抢才会导致死锁（如哲学家的筷子、打印机设备）。像内存、扬声器这样可以同时让多个进程使用的资源是不会导致死锁的（因为进程不用阻塞等待这种资源）。
不剥夺条件：进程所获得的资源在未使用完之前，不能由其他进程强行夺走，只能主动释放。
请求和保持条件：进程已经保持了至少一个资源，但又提出了新的资源请求，而该资源又被其他进程占有，此时请求进程被阻塞，但又对自己已有的资源保持不放。
循环等待条件：存在一种进程资源的循环等待链，链中的每一个进程己获得的资源同时被下一个进程所请求。

发生死锁时一定有循环等待，但是发生循环等待时未必死锁（循环等待是死锁的必要不充分条件）。

如果同类资源数大于 1，则即使有循环等待，也未必发生死锁。但如果系统中每类资源都只有一个，那循环等待就是死锁的充分必要条件了。

什么时候会发生死锁？

对系统资源的竞争。各进程对不可剥夺的资源（如打印机）的竞争可能引起死锁，对可剥夺的资源（CPU）的竞争是不会引起死锁的。
进程推进顺序非法。请求和释放资源的顺序不当，也同样会导致死锁。例如，并发执行的进程 P1、P2 分别申请并占有了资源 R1、R2，之后进程 P1 又紧接着申请资源 R2，而进程 P2 又申请资源R1，两者会因为申请的资源被对方占有而阻塞，从而发生死锁。
信号量的使用不当也会造成死锁。如生产者-消费者问题中，如果实现互斥的 P 操作在实现同步的 P 操作之前，就有可能导致死锁。（可以把互斥信号量、同步信号量也看做是一种抽象的系统资源）。
总之，对不可剥夺资源的不合理分配，可能导致死锁。

预防死锁

死锁的产生必须满足四个必要条件，只要其中一个或者几个条件不满足，死锁就不会发生。

破坏互斥条件：如果把只能互斥使用的资源改造为允许共享使用，则系统不会进入死锁状态。比如：操作系统可以采用 SPOOLing 技术把独占设备在逻辑上改造成共享设备。该策略的缺点：并不是所有的资源都可以改造成可共享使用的资源。并且为了系统安全，很多地方还必须保护这种互斥性。因此，很多时候都无法破坏互斥条件。

破坏不剥夺条件：

方案一：当某个进程请求新的资源得不到满足时，它必须立即释放保持的所有资源，待以后需要时再重新申请。也就是说，即使某些资源尚未使用完，也需要主动释放，从而破坏了不可剥夺条件。
方案二：当某个进程需要的资源被其他进程所占有的时候，可以由操作系统协助，将想要的资源强行剥夺。这种方式一般需要考虑各进程的优先级（比如：剥夺调度方式，就是将处理机资源强行剥夺给优先级更高的进程使用）。
该策略的缺点：实现起来比较复杂。释放已获得的资源可能造成前一阶段工作的失效。因此这种方法一般只适用于易保存和恢复状态的资源，如 CPU。反复地申请和释放资源会增加系统开销，降低系统吞吐量。若采用方案一，意味着只要暂时得不到某个资源，之前获得的那些资源就都需要放弃，以后再重新申请。如果一直发生这样的情况，就会导致进程饥饿。

破坏请求和保持条件：可以采用静态分配方法，即进程在运行前一次申请完它所需要的全部资源，在它的资源未满足前，不让它投入运行。一旦投入运行后，这些资源就一直归它所有，该进程就不会再请求别的任何资源了。该策略实现起来简单，但也有明显的缺点：有些资源可能只需要用很短的时间，因此如果进程的整个运行期间都一直保持着所有资源，就会造成严重的资源浪费，资源利用率极低。另外，该策略也有可能导致某些进程饥饿。

破坏循环等待条件：可采用顺序资源分配法。首先给系统中的资源编号，规定每个进程必须按编号递增的顺序请求资源，同类资源（即编号相同的资源）一次申请完。在任何一个时刻，总有一个进程拥有的资源编号是最大的，那这个进程申请之后的资源必然畅通无阻。因此，不可能出现所有进程都阻塞的死锁现象。

该策略的缺点：不方便增加新的设备，因为可能需要重新分配所有的编号，进程实际使用资源的顺序可能和编号递增顺序不一致，会导致资源浪费，必须按规定次序申请资源，用户编程麻烦。

避免死锁（银行家算法）

安全序列：如果系统按照这种序列分配资源，则每个进程都能顺利完成。只要能找出一个安全序列，系统就是安全状态。当然，安全序列可能有多个。如果分配了资源之后，系统中找不出任何一个安全序列，系统就进入了不安全状态。这就意味着之后可能所有进程都无法顺利的执行下去。当然，如果有进程提前归还了一些资源，那系统也有可能重新回到安全状态，不过我们在分配资源之前总是要考虑到最坏的情况。

如果系统处于安全状态，就一定不会发生死锁。如果系统进入不安全状态，就可能发生死锁（处于不安全状态未必就是发生了死锁，但发生死锁时一定是在不安全状态）。因此可以在资源分配之前预先判断这次分配是否会导致系统进入不安全状态，以此决定是否答应资源分配请求。这也是银行家算法的核心思想。

银行家算法是荷兰学者 Djkstra 为银行系统设计的，以确保银行在发放现金贷款时，不会发生不能满足所有客户需要的情况。后来该算法被用在操作系统中，用于避免死锁。核心思想：在进程提出资源中请时，先预判此次分配是否会导致系统进入不安全状态。如果会进入不安全状念，就暂时不答应这次请求，让该进程先阻塞等待。

银行家算法：

假设系统中有 n 个进程，m 种资源。每个进程在运行前先声明对各种资源的最大需求数，则可用一个 n*m 的矩阵（可用二维数组实现）表示所有进程对各种资源的最大需求数。不妨称为最大需求矩阵 Max，Max[i,j] = K 表示进程 Pi 最多需要 K 个资源 Rj。同理，系统可以用一个 n*m 的分配矩阵 Allocation 表示对所有进程的资源分配情況。Max - Allocation = Need 矩阵，表示各进程最多还需要多少各类资源。另外，还要用一个长度为 m 的一维数组 Available 表示当前系统中还有多少可用资源。
某进程 Pi 向系统申请资源，可用一个长度为 m 的一维数组 Requesti 表示本次申请的各种资源量。
可用银行家算法预判本次分配是否会导致系统进入不安全状态：

① 如果 Requesti[j] ≤ Need[i, j]（0≤j≤m）便转向②，否则认为出错，因为它所需要的资源数已超过它所宣布的最大值。

② 如果 Requesti[j] ≤ Available[j]（0≤j≤m）便转向③，否则表示尚无足够资源，Pi 必须等待。

③ 系统试探着把资源分配给进程 Pi，并修改相应的数据（并非真的分配，修改数值只是为了做预判）：Available = Available - Request; Allocation[i, j] = Allocation[i, j] + Requesti[j];``Need[i, j] = Need[i, j] - Requesti[j]。

④操作系统执行安全性算法，检查此次资源分配后，系统是否处于安全状态。若安全，才正式分配；否则，恢复相应数据，让进程阻塞等待。

不断重复上述过程，看最终是否能让所有进程都加入安全序列。系统处于不安全状态末必死锁，但死锁时一定处于不安全状态。系统处于安全状态一定不会死锁。

死锁的检测和解除

检测死锁的算法：依次消除与不阻塞进程相连的边，直到无边可消（所谓不阻塞进程是指其申请的资源数还足够的进程）。

在资源分配图中，找出既不阻塞又不是孤点的进程 Pi（即找出一条有向边与它相连，且该有向边对应资源的申请数量小于等于系统中已有空闲资源数量。若所有的连接该进程的边均满足上述条件，则这个进程能继续运行直至完成，然后释放它所占有的所有资源）。消去它所有的请求边和分配变，使之称为孤立的结点。
进程 Pi 所释放的资源，可以唤醒某些因等待这些资源而阻塞的进程，原来的阻塞进程可能变为非阻塞进程。根据 1 中的方法进行一系列简化后，若能消去途中所有的边，则称该图是可完全简化的。
死锁定理：如果某时刻系统的资源分配图是不可完全简化的，那么此时系统死锁。

解除死锁的主要方法有：

资源剥夺法。挂起（暂时放到外存上）某些死锁进程，并抢占它的资源，将这些资源分配给其他的死锁进程。但是应防止被挂起的进程长时间得不到资源而饥饿。
撤销进程法（或称终止进程法）。强制撤销部分、甚至全部死锁进程，并剥夺这些进程的资源。这种方式的优点是实现简单，但所付出的代价可能会很大。因为有些进程可能己经运行了很长时间，已经接近结束了，一旦被终止可谓功亏一篑，以后还得从头再来。
进程回退法。让一个或多个死锁进程回退到足以避免死锁的地步。这就要求系统要记录进程的历史信息，设置还原点。

三、内存管理

内存的基础知识

内存可存放数据。程序执行前需要先放到内存中才能被 CPU 处理以缓和 CPU 与硬盘之间的速度矛盾。内存中也有一个一个的小房间，每个小房间就是一个存储单元。内存地址从 0 开始，每个地址对应一个存储单元。

如果计算机按字节编址，则每个存储单元大小为 1 字节，即 1 B，即 8 个二进制位。
如果字长为 16 位的计算机按字编址，则每个存储单元大小为 1 个字，每个字的大小为 16 个二进制位。

我们写的代码要翻译成 CPU 能识别的指令，这些指令会告诉 CPU 应该去内存的哪个地址读/写数据，这个数据应该做什么样的处理。指令的工作基于地址，每个地址对应一个数据的存储单元。程序经过编译、链接后生成的指令中指明的是逻辑地址（相对地址），即相对于进程的起始地址而言的地址。

应用程序的编译、链接与装入：

编译：经过编译程序将源代码编译为若干个目标模块。（高级语言翻译为机器语言）
链接：通过链接程序将编译好的目标模块以及所需的库函数链接在一起，生成完整的装入模块，链接后形成完整的逻辑地址。
装入：通过装入程序将这些装入模块装入内存并执行，装入后形成物理地址。

装入的三种方式：

绝对装入：在编译时，如果知道程序将放到内存中的哪个位置，编译程序将产生绝对地址的目标代码。编译、链接后得到的装入模块的指令直接就使用了绝对地址（物理地址）。装入程序按照装入模块中的地址，将程序和数据装入内存。绝对装入只适用于单道程序环境。
静态重定位：又称可重定位装入。编译、链接后的装入模块的地址都是从 0 开始的，指令中使用的地址、数据存放的地址都是相对于起始地址而言的逻辑地址。可根据内存的当前情况，将装入模块装入到内存的适当位置。在装入时对地址进行重定位，将逻辑地址变换为物理地址（地址变换是在装入时一次完成的）。
- 静态重定位的特点是在一个作业装入内存时，必须分配其要求的全部内存空间，如果没有足够的内存，就不能装入该作业。
- 作业一旦进入内存后，在运行期间就不能再移动，也不能再申请内存空间。
动态重定位：又称动态运行时装入。编译、链接后的装入模块的地址都是从 0 开始的。装入程序把装入模块装入内存后，并不会立即把逻辑地址转换为物理地址，而是把地址转换推迟到程序真正要执行时才进行。因此装入内存后所有的地址依然是逻辑地址。这种方式需要一个重定位寄存器的支持。
- 重定位寄存器：存放装入模块存放的起始位置。并且可将程序分配到不连续的存储区中；在程序运行前只需装入它的部分代码即可投入运行，然后在程序运行期间，根据需要动态申请分配内存；便于程序段的共享，可以向用户提供一个比存储空间大得多的地址空间。
- 物理地址 = 基址计算器内容 + 逻辑地址。
- 采用动态重定位时允许程序在内存中发生移动。

链接的三种方式：

静态链接：在程序运行之前，先将各目标模块及它们所需的库函数连接成一个完整的可执行文件（装入模块），之后不再拆开。
装入时动态链接：将各目标模块装入内存时，边装入边链接的链接方式。
运行时动态链接：在程序执行中需要该目标模块时，才对它进行链接。其优点是便于修改和更新，便于实现对目标模块的共享。

内存管理的概念

内存管理的功能是为多道程序的运行提供良好的环境：

操作系统负责内存的分配和回收：记住内存空间的使用情况、实施内存的分配、回收系统或用户释放的内存空间。
操作系统需要提供某种技术从逻辑上对内存空间进行扩充：虚拟存储技术或其他自动覆盖技术。
操作系统需要提供地址转换功能，负责程序的逻辑地址与物理地址的转换（三种装入方式）。
操作系统需要提供内存保护功能。保证各进程在各自存储空间内运行，互不干扰：由硬件和软件配合完成。
- 方法一：在 CPU 中设置一对上、下限寄存器，存放进程的上、下限地址。进程的指令要访问某个地址时，CPU 检查是否越界。
- 方法二：采用重定位寄存器（又称基址奇存器）和界地址寄存器（又称限长寄存器）进行越界检查。重定位寄存器中存放的是进程的起始物理地址。界地址寄存器中存放的是进程的最大逻辑地址。

覆盖与交换

内存空间的扩充可分为覆盖技术、交换技术与虚拟存储技术。

覆盖技术：用来解决程序大小超过物理内存总和的问题，将程序分为多个段（多个模块）。常用的段常驻内存，不常用的段在需要时调入内存。内存中分为一个固定区和若干个覆盖区。需要常驻内存的段放在固定区中，调入后就不再调出（除非运行结束），不常用的段放在覆盖区，需要用到时调入内存，用不到时调出内存。

按照自身逻辑结构，让那些不可能同时被访问的程序段共享同一个覆盖区。
必须由程序员声明覆盖结构，操作系统完成自动覆盖。缺点：对用户不透明，增加了用户编程负担。只用于早期操作系统。

交换（对换）技术：内存空间紧张时，系统将内存中某些进程暂时换出外存，把外存中某些已具备运行条件的进程换入内存（进程在内存与磁盘间动态调度）。中级调度（内存调度），就是要决定将哪个处于挂起状态的进程重新调入内存。

具有对换功能的操作系统中，通常把磁盘空间分为文件区和对换区两部分。文件区主要用于存放文件，主要追求存储空间的利用率，因此对文件区空间的管理采用离散分配方式，对换区空间只占磁盘空间的小部分，被换出的进程数据就存放在对换区。由于对换的速度直接影响到系统的整体速度，因此对换区空间的管理主要追求换入换出速度，因此通常对换区采用连续分配方式，对换区的 I/O 速度比文件区的更快。
交换通常在许多进程运行且内存吃紧时进行，而系统负荷降低就暂停。例如：在发现许多进程运行时经常发生缺页，就说明内存紧张，此时可以换出一些进程，如果缺页率明显下降，就可以暂停换出。
可优先换出阻塞进程，也可换出优先级低的进程，为了防止优先级低的进程在被调入内存后很快又被换出，有的系统还会考虑进程在内存的驻留时间。PCB 会常驻内存，不会被换出外存。

连续分配管理方式

连续分配：指为用户进程分配的必须是一个连续的内存空间。

在单一连续分配方式中，内存被分为系统区和用户区。系统区通常位于内存的低地址部分，用于存放操作系统相关数据，用户区用于存放用户进程相关数据。内存中只能有一道用户程序，用户程序独占整个用户区空间。

优点：实现简单，无外部碎片：可以采用覆盖技术扩充内存，不一定需要采取内存保护（如早期的 PC 操作系统 MS-DOS）。
缺点：只能用于单用户、单任务的操作系统中，有内部碎片（分配给某进程的内存区域中，有些部分没有用上就叫内部碎片），存储器利用率极低。

固定分区分配：1960 年代出现了支持多道程序的系统，为了能在内存中装入多道程序，且这些程序之间又不会相互干扰，于是将整个用户空间划分为若干个固定大小的分区，在每个分区中只装入一道作业，这样就形成了最早的、最简单的一种可运行多道程序的内存管理方式。

分区大小相等：缺乏灵活性，但是很适合用于用一台计算机控制多个相同对象的场合（比如：钢铁厂有 n 个相同的炼钢炉，就可把内存分为 n 个大小相等的区域存放 n 个炼钢炉控制程序）。
分区大小不等：增加了灵活性，可以满足不同大小的进程需求。根据常在系统中运行的作业大小情况进行划分（比如：划分多个小分区、适量中等分区、少量大分区）。
操作系统需要建立一个数据结构：分区说明表，来实现各个分区的分配与回收。每个表项对应一个分区，通常按分区大小排列。每个表项包括对应分区的大小、起始地址、状态（是否已分配）。用数据结构的数组（或链表）即可表示这个表。当某用户程序要装入内存时，由操作系统内核程序根据用户程序大小检索该表，从中找到一个能满足大小的、未分配的分区，将之分配给该程序，然后修改状态为已分配。
优点：实现简单，无外部碎片。
缺点：当用户程序太大时，可能所有的分区都不能满足需求，此时不得不采用覆盖技术来解决，但这又会降低性能。而且会产生内部碎片，内存利用率低。

动态分区分配：又称为可变分区分配。这种分配方式不会预先划分内存分区，而是在进程装入内存时，根据进程的大小动态地建立分区，并使分区的大小正好适合进程的需要。因此系统分区的大小和数目是可变的。

空闲分区表：每个空闲分区对应一个表项。表项中包含分区号、分区大小、分区起始地址等信息。
空闲分区链：每个分区的起始部分和末尾部分分别设置前向指针和后向指针。起始部分处还可记录分区大小等信息。
把一个新作业装入内存时，须按照一定的动态分区分配算法，从空闲分区表（或空闲分区链）中选出一个分区分配给该作业。
动态分区分配没有内部碎片，但是有外部碎片。

内部碎片：分配给某进程的内存区域中，如果有些部分没有用上。外部碎片：是指内存中的某些空闲分区由于太小而难以利用。

如果内存中空闲空间的总和本来可以满足某进程的要求，但由于进程需要的是一整块连续的内存空间，因此这些碎片不能满足进程的需求。可以通过紧凑（拼凑，Compaction）技术来解决外部碎片。

动态分区分配算法

首次适应算法（First Fit）：每次都从低地址开始查找，找到第一个能满足大小的空闲分区。空闲分区以地址递增的次序排列。每次分配内存时顺序查找空闲分区链（或空闲分区表），找到大小能满足要求的第一个空闲分区。

最佳适应算法（Best Fit）：由于动态分区分配是一种连续分配方式，为各进程分配的空间必须是连续的一整片区域。因此为了保证当大进程到来时能有连续的大片空间，可以尽可能多地留下大片的空闲区，即优先使用更小的空闲区。空闲分区按容量递增次序链接。每次分配内存时顺序查找空闲分区链（或空闲分区表），找到大小能满足要求的第一个空闲分区。缺点：每次都选最小的分区进行分配，会留下越来越多的、很小的、难以利用的内存块。因此这种方法会产生很多的外部碎片。

最坏适应算法（Worst Fit）：又称最大适应算法（Largest Fit），为了解决最佳适应算法的问题（即留下太多难以利用的小碎片），可以在每次分配时优先使用最大的连续空闲区，这样分配后剩余的空闲区就不会太小，更方便使用。空闲分区按容量递减次序链接。每次分配内存时顺序查找空闲分区链（或空闲分区表），找到大小能满足要求的第一个空闲分区。缺点：每次都选最大的分区进行分配，虽然可以让分配后留下的空闲区更大，更可用，但是这种方式会导致较大的连续空闲区被迅速用完。如果之后有大进程到达，就没有内存分区可用了。

邻近适应算法（Next Fit）：：首次适应算法每次都从链头开始查找的。这可能会导致低地址部分出现很多小的空闲分区，而每次分配查找时，都要经过这些分区，因此也增加了查找的开销。如果每次都从上次查找结束的位置开始检索，就能解决上述问题。空闲分区以地址递增的顺序排列（可排成一个循环链表）。每次分配内存时从上次查找结束的位置开始查找空闲分区链（或空闲分区表），找到大小能满足要求的第一个空闲分区。

首次适应算法每次都要从头查找，每次都需要检索低地址的小分区。但是这种规则也决定了当低地址部分有更小的分区可以满足需求时，会更有可能用到低地址部分的小分区，也会更有可能把高地址部分的大分区保留下来（最佳适应算法的优点）。
邻近适应算法的规则可能会导致无论低地址、高地址部分的空闲分区都有相同的概率被使用，也就导致了高地址部分的大分区更可能被使用，划分为小分区，最后导致无大分区可用（最大适应算法的缺点）。

综合来看，四种算法中，首次适应算法的效果反而更好

基本分页存储管理的概念

分页存储：将内存空间分为一个个大小相等的分区（比如：每个分区 4 KB），每个分区就是一个页框（页框 = 页帧 = 内存块 = 物理块 = 物理页面）。每个页框有一个编号，即页框号（页框号 = 页帧号 = 内存块号 = 物理块号= 物理页号），页框号从 0 开始。

将进程的逻辑地址空间也分为与页框大小相等的一个个部分，每个部分称为一个页（或页面）。每个页面也有一个编号，即页号，页号也是从 0 开始。

操作系统以页框为单位为各个进程分配内存空间。进程的每个页面分别放入一个页框中。也就是说，进程的页面与内存的页框有一一对应的关系。各个页面不必连续存放，可以放到不相邻的各个页框中。

为了能知道进程的每个页面在内存中存放的位置，操作系统要为每个进程建立一张页表。页表通常存在 PCB（进程控制块）中。

一个进程对应一张页表。
进程的每个页面对应一个页表项。
每个页表项由页号和块号组成。
页表记录进程页面和实际存放的内存块之间的映射关系。
每个页表项的长度是相同的。
页表项连续存放，页号是隐含的，不占存储空间（类似数组）。

将进程地址空间分页之后，虽然进程的各个页面是离散存放的，但是页面内部是连续存放的。操作系统如果要访问逻辑地址 A（实现逻辑地址到物理地址的转换），则：

确定逻辑地址 A 对应的页号 P。页号 = 逻辑地址 / 页面长度（取除法的整数部分）。
找到 P 号页面在内存中的起始地址（需要查页表）。
确定逻辑地址 A 的页内偏移量 W。页内偏移量 = 逻辑地址 % 页面长度（取除法的余数部分）。
逻辑地址 A 对应的物理地址 = P 号页面在内存中的起始地址＋页内偏移量 W。

在计算机内部，地址是用二进制表示的，如果页面大小刚好是 2 的整数幂，则计算机硬件可以很快速的把逻辑地址拆分成（页号，页内偏移量）。结论：如果每个页面大小为 2^k B，用二进制数表示逻辑地址，则末尾 K 位即为页内偏移量，其余部分就是页号。

如果页面大小刚好是 2 的整数幂，则只需把页表中记录的物理块号拼接上页内偏移量就能得到对应的物理地址。

基本地址变换机构

基本地址变换机构可以借助进程的页表将逻辑地址转换为物理地址。通常会在系统中设置一个页表寄存器（PTR Page-Table Register），存放页表在内存中的起始地址 F 和页表长度 M。进程末执行时，页表的始址和页表长度放在进程控制块（PCB）中，当进程被调度时，操作系统内核会把它们放到页表寄存器中。页面大小是 2 的整数幂。

逻辑地址到物理地址变换的过程：

计算页号 P 和页内偏移量 W（如果用手算，P=A/L，W=A%L，但是在计算机实际运行中，逻辑地址结构是固定不变的，因此计算机硬件可以更快地得到二进制表示的页号、页内偏移量）。
比较页号 P 和页表长度 M，如果 P >= M，则会产生越界中断，否则继续执行（注意：页号是从 0 开始的，则页表长度至少是 1，因此 P = M 时也会越界）。
页表中页号 P 对应的页表项地址 = 页表始址 F + 页号 P * 页表项长度，取出该页表项内容 b，即内存块号。
计算实际物理地址 E = b * L + W，用得到的物理地址 E 去访存。
注意页表项长度、页表长度、页面大小的区别：页表长度是指页表最多能有多少个页表项，即总共有几个页。页表项长度指每个页表项所占用的内存大小。页面大小指一个页面占多大的内存空间。页面大小是 2 的整数幂。

在分页存储管理（页式管理）系统中，只要确定每个页面的大小，逻辑地址结构就可以确定。

因此，页式管理中地址是一维的。即，只要给出一个逻辑地址，系统就可以自动算出页号、页内偏移量。

基本地址变换结构需要访问两次内存：第一次访问内存查找页表，第二次访问物理内存对应的内存单元。

页表寄存器的作用：存放页表起始地址、存放页表长度。

地址变换过程简单表述：

根据逻辑地址算出页号、页内偏移量，
页号的合法性检查（与页表长度对比），
若页号合法，再根据页表起始地址、页号找到对应页表项（第一次访问内存：查页表），
根据页表项中记录的内存块号、页内偏移量得到最终的物理地址，
访问物理内存对应的内存单元（第二次访问内存：访问目标内存单元）。

具有快表（TLB）的地址变换机构

具有快表的地址变换机构是基本地址变换机构的改进版本。

快表，又称联想寄存器（TLB, translation lookaside buffer），是一种访问速度比内存快很多的高速缓存（TLB 不是内存），用来存放最近访问的页表项的副本，可以加速地址变换的速度。与此对应，内存中的页表常称为慢表。

引入快表后，地址的变换过程：

CPU 给出逻辑地址，由某个硬件算得页号、页内偏移量，将页号与快表中的所有页号进行比较。
如果找到匹配的页号，说明要访问的页表项在快表中有副本，则直接从中取出该页对应的内存块号，再将内存块号与页内偏移量拼接形成物理地址，最后，访问该物理地址对应的内存单元。因此，若快表命中，则访问某个逻辑地址仅需一次访存即可。
如果没有找到匹配的页号，则需要访问内存中的页表，找到对应页表项，得到页面存放的内存块号，再将内存块号与页内偏移量拼接形成物理地址，最后，访问该物理地址对应的内存单元。因此，若快表未命中，则访问某个逻辑地址需要两次访存（注意：在找到页表项后，应同时将其存入快表，以便后面可能的再次访问。但若快表己满，则必须按照一定的算法对旧的页表项进行替换）。

由于查询快表的速度比查询页表的速度快很多，因此只要快表命中，就可以节省很多时间。因为局部性原理，一般来说快表的命中率可以达到 90% 以上。

	地址变换过程	访问一个逻辑地址的访存次数
基本地址变换机构	1. 算页号、页内偏移量。2. 检查页号合法性。3. 查页表，找到页面存放的内存块号。4. 根据内存块号与页内偏移量得到物理地址。5. 访问目标内存单元。	两次访存
具有快表的地址变换机构	1. 算页号、页内偏移量。2. 检查页号合法性。3. 查快表，若命中，即可知道页面存放的内存块号，可直接进行 5，若未命中则进行 4。4. 查页表，找到页面存放的内存块号，并且将页表项复制到快表中。5. 根据内存块号与页内偏移量得到物理地址。6. 访问目标内存单元	快表命中，只需一次访存，快表未命中，需要两次访存。

局部性原理：

时间局部性：如果执行了程序中的某条指令，那么不久后这条指令很有可能再次执行，如果某个数据被访问过，不久之后该数据很可能再次被访问（因为程序中存在大量的循环）。
空间局部性：一旦程序访问了某个存储单元，在不久之后，其附近的存储单元也很有可能被访问（因为很多数据在内存中都是连续存放）。
基本地址变换机构中，每次要访问一个逻辑地址，都需要查询内存中的页表。由于局部性原理，可能连续很多次查到的都是同一个页表项。

TLB 和普通 Cache 的区别：TLB 中只有页表项的副本，而普通 Cache 中可能会有其他各种数据的副本。

两级页表

单级页表存在的问题：1. 页表必须连续存放，因此当页表很大时，需要占用很多个连续的页框。2. 根据局部性原理可知，很多时候，进程在一段时间内只需要访问某几个页面就可以正常运行了。因此没有必要让整个页表都常驻内存。

页表必须连续存放问题的解决：把必须连续存放的页表再分页。

要为离敢分配的页表再建立一张页表，称为页目录表，或称外层顶表，或称顶层页装。页目录表在 PCB 中。

两级页表的地址结构：一级页号 + 二级页号 + 页内偏移量。

两级页表的原理：

根据一级页号查页目录表，找到二级页表在内存中的存放位置。
根据二级页号查表，找到最终想访问的内存块号。
结合页内偏移量得到物理地址。

整个页表常驻内存问题的解决：在需要访问页面时才把页面调入内存（虚拟存储技术）。在页表项中增加一个标志位，用于表示该页面是否己经调入内存。若想访问的页面不在内存中，则产生缺页中断（内中断），然后将目标页面从外存调入内存。

在多级页表机制中，各级页表的大小有何要求：不能超过一个页面。若两级页表不够，可以分更多级。

两级页表的访存次数分析（假设没有快表机构）：N 级页表访问一个逻辑地址需要 N+1 次访存。第一次访存：访问内存中的页目录表。第二次访存：访问内存中的二级页表。第三次访存：访问目标内存单元。

基本分段存储管理

基本分段存储管理与分页最大的区别就是：离散分配时所分配地址空间的基本单位不同。

分段：按照程序自身的逻辑关系划分为若干个段，每个段都有一个段名（在低级语言中，程序员使用段名来编程），每段从 0 开始编址。以段为单位进行分配，每个段在内存中占据连续空间，但各段之间可以不相邻。由于是按逻辑功能模块划分，用户编程更方便，程序的可读性更高。

分段系统的逻辑地址结构由段号 S（段名）和段内地址 W（段内偏移量）所组成。段号的位数决定了每个进程最多可以分几个段。段内地址位数决定了每个段的最大长度是多少。

程序分多个段，各段孩散地装入内存，为了保证程序能正常运行，就必须能从物理内存中找到各个逻辑段的存放位置。为此，需为每个进程建立一张段映射表，简称段表。

每个段对应一个段表项，其中记录了该段在内存中的起始位置（又称基址）和段的长度。
各个段表项的长度是相同的。例如：某系统按字节寻址，采用分段存储管理，逻辑地址结构为（段号 16 位，段内地址 16 位），因此用 16 位即可表示最大段长。物理内存大小为 4 GB（可用 32 位表示整个物理内存地址空间）。因此，可以让每个段表项占 16+32=48 位，即 6 B。由于段表项长度相同，因此段号可以是隐含的，不占存储空间。若段表存放的起始地址为 M，则 K 号段对应的段表项存放的地址为 M+K*6。

分段、分页管理的对比：

页是信息的物理单位。分页的主要目的是为了实现离散分配，提高内存利用率。分页仅仅是系统管理上的需要，完全是系统行为，对用户是不可见的。
段是信息的逻辑单位。分段的主要目的是更好地满足用户需求。一个段通常包含着一组属于一个逻辑模块的信息。分段对用户是可见的，用户编程时需要显式地给出段名。
页的大小固定且由系统决定。段的长度却不固定，决定于用户编写的程序。
分页的用户进程地址空间是一维的，程序员只需给出一个记忆符即可表示一个地址。
分段的用户进程地址空间是二维的，程序员在标识一个地址时，既要给出段名，也要给出段内地址。

分段比分页更容易实现信息的共享和保护。但不能被修改的代码称为纯代码或可重入代码（不属于临界资源），这样的代码是可以共享的。可修改的代码是不能共享的（比如，有一个代码段中有很多变量，各进程并发地同时访问可能造成数据不一致）。

分段访问一个逻辑地址：总共需要两次访存。第一次访存：查内存中的段表，第二次访存：访问目标内存单元。与分页系统类似，分段系统中也可以引入快表机构，将近期访问过的段表项放到快表中，这样可以少一次访问，加快地址变换速度。

基本分段存储管理方式优点：便于程序模块化处理和处理变换的数据结构、便于动态链接和共享、无内部碎片。缺点：与分页类似，需要硬件支持、为满足分段的动态增长和减少外部碎片，要采用拼接手段、分段的最大尺寸受到主存可用空间的限制、有外部碎片。

段页式管理方式

	优点	缺点
分页管理	内存空间利用率高，不会产生外部碎片，只会有少量的页内碎片。	不方便按照逻辑模块实现信息的共享和保护。
分段管理	很方便按照逻辑模块实现信息的共享和保护。	如果段长过大，为其分配很大的连续空间会很不方便。另外，段式管理会产生外部碎片。

分段 + 分页 = 段页式管理方式：将进程按逻辑模块分段，再将各段分页（如每个页面4KB），再将内存空间分为大小相同的内存块/页框/页帧/物理块进程前将各页面分别装入各内存块中。

段页式系统的逻辑地址结构由段号、页号、页内地址（页内偏移量）组成。段号的位数决定了每个进程最多可以分几个段。页号位数决定了每个段最大有多少页。页内偏移量决定了页面大小、内存块大小是多少。分页对用户不可见，所以段页式管理的地址结构是二维的。

每个段对应一个段表项，每个段表项由段号、页表长度、页表存放块号（页表起始地址）组成。每个段表项长度相等，段号是隐含的。

每个页面对应一个页表项，每个页表项由页号、页面存放的内存块号组成。每个页表项长度相等，页号是隐含的。

地址变换：

由逻辑地址得到段号、页号、页内偏移量。
段号与段表寄存器中的段长度比较，检查是否越界。
由段表始址、段号找到对应段表项。
根据段表中记录的页表长度，检查页号是否越界。
由段表中的页表地址、页号得到查询页表，找到相应页表项。
由页面存放的内存块号、页内偏移量得到最终的物理地址。
访问目标单元。

访问一个逻辑地址所需访存次数：三次。第一次：查段表、第二次：查页表、第三次：访问目标单元。也可引入快表机构，用段号和页号作为查询快表的关键字。若快表命中则仅需一次访存。

虚拟内存的基本概念

在真实的操作系统中，通常采用段页式存储管理，段面向用户，页面向硬件。

虚拟内存解决的问题

一次性：作业必须一次性全部装入内存后才能开始运行。这会造成两个问题：①作业很大时，不能全部装入内存，导致大作业无法运行；②当大量作业要求运行时，由于内存无法容纳所有作业，因此只有少量作业能运行，导致多道程序并发度下降
驻留性：一旦作业被装入内存，就会一直驻留在内存中，直至作业运行结束。事实上，在一个时间段内，只需要访问作业的一小部分数据即可正常运行，这就导致了内存中会驻留大量的、暂时用不到的数据，浪费了宝贵的内存资源。

虚拟内存的实现：

基于局部性原理，在程序装入时，可以将程序中很快会用到的部分装入内存，暂时用不到的部分留在外存，就可以让程序开始执行
在程序执行过程中，当所访问的信息不在内存时，由操作系统负责将所需信息从外存调入内存，然后继续执行程序
若内存空间不够，由操作系统负责将内存中暂时用不到的信息换出到外存。在操作系统的管理下，在用户看来似乎有一个比实际内存大得多的内存，这就是虚拟内存。

请求分页管理

请求分页管理：在程序执行过程中，当所访问的信息不在内存时，由操作系统负责将所需信息从外存调入内存，然后继续执行程序。若内存空间不够，由操作系统负责将内存中暂时用不到的信息换出到外存
缺页中断：在请求分页系统中，每当要访问的页面不在内存时，便产生一个缺页中断，然后由操作系统的缺页中断处理程序处理中断
缺页的进程阻塞，放入阻塞队列，调页完成后再将其唤醒，放回就绪队列。如果内存中有空闲块，则为进程分配一个空闲块，将所缺页面装入该块，并修改页表中相应的页表项。如果内存中没有空闲块，则由页面置换算法选择一个页面淘汰，同时要注意，若某个页面被换出外存，则快表中的相应表项也要删除，否则可能访问错误的页面
理解缺页，缺页就像货架上缺少了商品，需要从仓库里调取商品，就先暂停这个货架的销售，等商品调取完毕再重新出售。

页面置换算法

置换算法的评价指标是：缺页的次数，某种算法让缺页次数最低，调度效率最高，那就是最优的算法
最佳置换算法：每次淘汰的页面都是以后永久不用或最长时间不使用的页面，保证最低的缺页率。显然，这种需要预测未来的算法不可能实现。
先进先出算法FIFO：缺页时，淘汰最早进入的页面。算法简单，但局限性也明显，例如某些经常使用的页面一直被换进换出，和使用频率低的页面有相同的被换出的机会。
最近最久未使用置换算法LRU：每次淘汰的页面都是最近最久未使用的页面。需要在页面中添加一个记录项，记录上次被访问以来经历的时间t，当需要淘汰页面时，选择时间t最大的淘汰，也就是最久未使用的淘汰。算法设计虽好，但开销很大，实现困难。
时钟置换算法：时钟置换算法也可以称为最近未使用算法。是一种性能和开销均衡的算法。
简单的时钟算法实现方法：为每个页面设置一个访问位，再将内存中的页面都通过链接指针链接成一个循环队列。当某页被访问时，其访问位置为1。当需要淘汰一个页面时，只需检查页的访问位。如果是0，就选择该页换出;如果是1，则将它置为0，暂不换出，继续检查下一个页面，若第一轮扫描中所有页面都是1，则将这些页面的访问位依次置为0后，再进行第二轮扫描（第二轮扫描中一定会有访问位为0的页面，因此简单的CLOCK算法选择一个淘汰页面最多会经过两轮扫描)

I/O原理

文件的逻辑结构

文件可以分为两类：
- 无结构文件：文件内部数据就是一系列二进制流或字符流。最典型的就是txt文件。
- 有结构文件：由一组相似的记录组成，又称记录式文件。典型的excel表、数据库表等。
有结构文件的逻辑结构又分顺序文件、索引文件、索引顺序文件，注意逻辑结构是展示给用户的，是文件的组织形式，例如是一张顺序存储的excel表格，还是一张excel索引表加上excel顺序表，还是多级索引加顺序，而不是在计算机上的存储方式。
顺序文件：文件中的记录一个接一个地顺序排列（逻辑上），记录可以是定长的或可变长的。各个记录在物理上可以顺序存储或链式存储。
顺序存储即逻辑相邻的文件物理上也相邻，链式存储即在末尾添加新的文件。
记录的类型又分为可变长和不可变长记录

索引顺序文件：索引顺序文件是索引文件和顺序文件思想的结合。索引顺序文件中，同样会为文件建立一张索引表，但不同的是：并不是每个记录对应一个索引表项，而是一组记录对应一个索引表项，索引表项的地址直接指向顺序文件所在区域，再顺序查找到所需的文件，从而节省了很大的空间。(例如我们可以通过An Qi找到An Kang、An Jie等，而不用在索引表中存放这么多信息。另外索引项之间不需要有按照逻辑关系排列)
多级索引顺序文件：在索引顺序文件的基础上再增加层次深度，可以减少查找的次数(顺序查找范围缩小了)

文件目录

文件目录可以分为：单级目录结构、两级目录结构、多级目录结构(树形目录结构)
单极目录结构：顾名思义，所有的文件放在一个目录中，类似于一个仓库把所有文件不加整理的堆放在一起，显然效率会很低下
两级目录结构:主要分为主文件目录和用户文件目录。类似于仓库中加了几个员工货架，不同员工的货物放在不同货架，但在一个货架中文件还是采用堆砌式的存储。
多级目录结构，又称树形目录结构:我们当前主流操作系统都是多级目录结构，简而言之就是文件目录可以一级一级的延申，从而文件更有条理。
FCB(文件控制块)，首先来看一张图，如果文件目录都以这种表的形式进行信息查找，会大大降低运行效率，增加系统负担。
提出对策，其实在查找各级目录的过程中，只需要用到文件名这个信息，可以考虑让目录表瘦身来提升效率。
索引结点指针指向索引结点(文件名之外的其他信息就存放在结点中，从而按需读取，提升效率)
每一个文件都有一个FCB，记录了文件的地址、信息、权限等等属性

文件的物理结构

最重要的三种物理结构：顺序、链接、索引，其中最主要使用的是索引文件，可以随机访问，同时增删效率高
文件的物理结构是文件分配在计算机存储上的分配方式。分配的基本单位是物理块,可以构想一下，一个大文件，如一首音乐23MB，难道直接一整个塞入硬盘吗？显然可能会出现一些问题，硬盘的空间也需要不断调整，就像内存分页一样，硬盘也被分为小的物理块号方便进行调度。
连续分配
- 优点：支持顺序访问和直接访问（即随机访问）；连续分配的文件在顺序访问时速度最快
- 缺点：不方便文件拓展；存储空间利用率低，会产生磁盘碎片
链式分配
- 隐式：采用链式分配（隐式链接）方式的文件，只支持顺序访问，不支持随机访问，查找效率低。另外，指向下一个盘块的指针也需要耗费少量的存储空间。

显式：直观理解就是在隐式的基础上添加了一张表，从表上能看出不同物理块号的下一块的地址
结论：采用链式分配（显式链接）方式的文件，支持顺序访问，也支持随机访问（想访问i 号逻辑块时，并不需要依次访问之前的0 ~ i-1号逻辑块），由于块号转换的过程不需要访问磁盘，因此相比于隐式链接来说，访问速度快很多
显式链接也不会产生外部碎片，也可以很方便地对文件进行拓展。

索引分配
- 索引就是文件分成不同的物理块存入磁盘，对每个物理块都有一个索引与之对应，需要读写时就通过索引表查询其物理地址进行相关操作

磁盘结构

磁道：每一圈就是一个磁道，最内侧磁道面积最小，所以数据密度最大
扇区：磁道被划分为小的磁盘块
一个盘片可能有两个盘面;每个盘面对应一个磁头；所有磁头连在一起，共进退；每个盘面的相对位置的磁道组成柱面

磁盘调度算法

磁盘调度算法要解决的核心问题就是寻道时间，即移动磁头的时间，而其他的启动时间、传输时间都很迅速，不是最主要的时间消耗
先来先服务FCFS
- 根据进程请求房屋内磁盘的现后顺序进行调度。符合惯性思维，但在很多时候，效果很差。
最短寻找时间优先(学过数据结构与算法的话，核心思想就是贪心算法)，该算法会优先处理与当前磁头最近的磁道的需求
- 那么很可能磁头就会如图所示的移动，也会存在饥饿问题：磁头只在一个小区域移动，而不能满足需要远距离移动的需求。例如不断有18->38，38->18的需求，那磁头就不会执行18->150的请求，从而产生饥饿
扫描算法
- 核心思想，只有磁头移动到最外侧磁道的时候才能往内侧移动，移动到最内侧的时候才能向外侧移动。这样就不会产生饥饿问题。

文件共享

文件共享分两种链接方式，硬链接和软连接
- 硬链接就是在另一个用户的目录中，索引结点指针直接指向了发送分享的用户的索引节点，从而实现了共享，count的数量代表文件正在被几个用户使用。
- 软连接，类似于快捷方式，记录了原文件的路径，然后层层查找。

文件保护

文件保护有三种方式口令、加密、访问控制
- 口令：为文件设置一串口令，就像打开手机需要先解锁。

加密：使用加密方法对文件加密，只有拥有正确的解密方法才能解密，有点像不同军队之间进行通信，要实现进行加密，要是想窥探敌情，就要对密文进行破解。
访问控制：每个文件的FCB或者索引结点中设置访问控制表，如windows中，设置了很多的访问权限，例如

I/O设备

I/O就是输入输出，I/O设备就是可以将数据输入到计算机或将计算机数据输出的设备，常见的：鼠标、键盘、音响、显示器、打印机、话筒、摄像头等等。
I/O控制器:CPU无法直接控制I/O设备，需要一个电子部件去充当中间人，这个部件就是I/O控制器，CPU控制I/O控制器，I/O控制器控制I/O设备。
假如我们的CPU能够控制I/O设备，那不同的厂商、不同型号的设备，都要对应进行编码，显然是不切实际的，所以CPU要采用通用调度方式调度I/O设备从而需要I/O控制器。
Java语言中，调用System.out.Println()，这本身并不能在显示器上打印，而需要通过操作系统调用write方法，接着调用字符设备接口，命令显示器写

Bezhuang

计算机网络

计算机网络是计算机专业必修的重要课程之一，与现实世界结合得相当紧密，也是考研计算机学科专业基础综合考试中的一门课程。计算机网络就是一些互联的、自治的计算机系统的集合。自治计算机就是能够进行自我...

计算机组成原理

计算机组成原理是计算机专业本科教学中的重要课程，它可以帮助我们系统地理解计算机硬件系统的组织结构和工作原理、掌握计算机硬件系统的基本分析与设计方法以及建立计算机系统的整体概念，为进一步学习计算...