操作系统

本文尚未完结，博主正在努力更新ヾ(≧∇≦*)ゝ

操作系统概述

什么是操作系统

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

操作系统的作用

1. 作为计算机系统资源的管理者

   • 处理机管理：分配和控制处理机。
   • 存储器管理：负责内存的分配和回收。
   • 文件管理：实现对文件的存取、共享和保护。
   • 设备管理：负责I/O设备的分配（回收）与操纵。

2. 作为用户与计算机硬件系统之间的接口

   • 用户接口（命令接口，用户可以直接调用）

     • 联机用户接口，也叫交互式命令接口，用户输入一条，操作系统执行一条

     • 脱机用户接口，也叫批处理命令接口，由一组作业控制命令组成，直到遇到作业结束语句时，系统才停止该作业的运行

     • GUI

   • 程序接口

     程序接口是为用户程序在执行中访问系统资源而设置的。

     由一组系统调用组成，用户通过在程序中使用这些系统调用来请求操作系统为其提供服务。

3. 实现了对计算机资源的扩充（作为扩充机器，即虚拟机）

补充：

什么是系统调用（也称广义指令）？

1. 操作系统提供给应用程序使用的接口。
2. 应用程序通过系统调用来请求获得操作系统的服务。
3. 系统调用会使处理器从用户态进入核心态。

什么功能要用到系统调用？

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

设备管理：完成设备的 请求/释放/启动 等功能

文件管理：完成文件的 读/写/创建/删除 等功能

进程控制：完成进程的 创建/撤销/阻塞/唤醒 等功能

进程通信：完成进程之间的 消息传递/信号传递 等功能

内存管理：完成内存的 分配/回收 等功能

系统调用与库函数的区别？

1. 系统调用时操作系统向上提供接口
2. 有的库函数式系统调用的进一步封装
3. 当前编写的应用程序大多通过库函数进行系统调用

系统调用的过程？

1. 传递系统调用参数
2. 执行陷入指令（用户态），引发内中断
3. 执行系统调用相应服务程序（内核态）
4. 返回用户程序

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

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

操作系统的发展历程

手工操作阶段（无操作系统）

1. 用户独占全机
2. CPU等待手工操作，CPU利用不重复

人工操作方式严重降低了计算机资源的利用率，人机矛盾

批处理阶段（操作系统开始出现，旨在提高系统资源的利用率和系统吞吐量）

1. 单道批处理系统

   解决人机矛盾及CPU和I/O设备速率不匹配的矛盾中形成。

   引入脱机输入/输出技术，并由监督程序负责控制作业的输入、输出。

   特征：自动性、顺序性、单道性

   缺点：

   • 内存中仅能有一道程序运行，只有该程序运行结束之后才能调入下一道程序
   • CPU有大量时间在空闲等待I/O完成，资源利用率依然很低，无法充分利用系统中的资源。

2. 多道批处理系统

   操作系统正式诞生。

   为进一步提高资源的利用率和系统吞吐量。

   优点：

   • 资源利用率高，多道程序共享计算机资源，从而使各种资源得到充分的利用。
   • 系统吞吐量大。

   缺点：

   • 平均周转周期长
   • 无人机交互能力

分时操作系统

解决人机交互问题。

允许多个用户同时通过自己的终端，以交互方式使用计算机，共享主机中的资源

特征：多路性（同时性）、交互性、独立性、及时性

实时操作系统

为了能在某个时间限制内完成某些紧急任务而不需时间片排队。

硬实时：系统必须满足任务对截止时间的要求，否则可能出现难以预测的后果。

软实时：能够接受偶尔违反时间规定且不会引起任何永久性的损害。

特征：多路性、独立性、及时性、交互性、可靠性。

网络操作系统和分布式计算机系统

个人计算机操作系统

操作系统的特征

操作系统的基本特征包括并发、共享、虚拟和异步。

并发性是指计算机系统中同时存在着多个运行的程序。

共享性是指系统中的资源可供内存中多个并发执行的程序共同使用。

并发和共享是操作系统两个最基本的特征，两者互为存在的条件。并发执行是资源共享的条件，资源共享是并发执行的基础。

并发与并行

并行性：指两个或多个事件在同一时刻发生。

并发性：值两个或多个事件在同一时间间隔内发生。

共享

资源共享即共享，指系统中的资源可供内存中多个并发执行的进程共同使用。

资源共享方式：

1. 互斥共享方式

   系统中的某些资源可以提供给多个进程（线程）使用，但规定在一段时间内只允许一个进程访问该资源，以防引起混淆。

2. 同时访问方式

   也称同时共享方式，允许一段时间内由多个进程“同时”对它们进行访问。宏观上“同时”，微观上，这些进程可能是交替对该资源进行访问，即“分时共享”的。

虚拟

虚拟是指把一个物理上的实体变为若干逻辑上的对应物。

异步

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

处理器运行模式

在计算机系统中，通常CPU会执行两种不同性质的程序：操作系统内核程序 和 用户自编程序（应用程序），前者是后者的管理者。出于安全考虑，前者的执行要一些特权指令，后者则不能执行这些指令。

特权指令：不允许用户直接使用的指令，如I/O指令、置中断指令，存取用于内存保护的寄存器、送程序状态字到程序状态字寄存器等的指令。

非特权指令：允许用户直接使用的指令，不能直接访问系统中的软硬件资源，仅限于访问用户的地址空间，防止用户程序对系统造成破坏。

处于内核态时，说明此时正在运行的是内核程序，此时可以执行特权指令。

处于用户态时，说明此时正在运行的是应用程序，此时只能执行非特权指令。

CPU中的程序状态字寄存器（PSW），其中有一个二进制标志位，1表示“内核态”，0表示用户态

内核态 = 核心态 = 管态；用户态 = 目态

内核态 --> 用户态：一条修改PSW的特权指令

用户态 --> 内核态：由中断引起，硬件自动完成

中断和异常

中断会使CPU由用户态变为内核态，是操作系统重新获得对CPU的控制权

中断类型：

1. 内中断

   与当前执行指令有关，中断信号来源于CPU内部

2. 外中断

   与当前执行的指令无关，中断信号来源于CPU外部

陷入（trap）：由陷入指令引发，是应用程序故意引发的。

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

陷入指令 = trap指令 = 访管指令

故障（fault）：由错误条件引起的，可能被内核程序修复。内核程序修复故障后会把CPU使用权还给应用程序，让它继续执行下去。如：缺页故障。

终止（abort）：由致命错误引起，内核程序无法修复改错误，因此一般不再将CPU使用权还给引发终止条件的应用程序，而是直接终止该应用程序。如：非法使用特权指令。

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

中断处理程序是一种内核程序，运行在“内核态”。

操作系统的体系结构

原语：一种特殊的程序，具有原子性。必须一口气全部执行完毕，不可被中断。

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

操作系统的内核需要运行在内核态，操作系统的非内核功能运行在用户态。

大内核（宏内核）：将系统的主要功能模块都作为系统内核，运行在核心态。高性能；但内核代码庞大，结构混乱，难以维护。

微内核：将内核中最基本的功能保留在内核，而将不需要在核心态执行的功能移到用户态执行。内核功能少，结构清晰，方便维护；但需要频繁地在核心态和用户态直接切换，性能低。

操作系统的引导

1. 激活CPU
2. 硬件自检
3. 加载带有操作系统的硬盘
4. 加载主引导记录MBR
5. 扫描硬盘分区表
6. 加载分区引导记录PBR
7. 加载启动管理器
8. 加载操作系统

虚拟机

虚拟机：使用虚拟化技术，将一台物理机器虚拟化为多台虚拟机器（virtual Machine，VM），每个虚拟机器都可以独立运行一个操作系统。

同义术语：虚拟机管理程序/虚拟机监控程序/Virtual Machine Monitor/Hypervisor

第一类虚拟机管理程序：

虚拟机管理程序向上层提供若干态虚拟机，这些虚拟机都是裸机硬件的精确复制品，每台虚拟机都与裸机相同，在不同的虚拟机上可以运行任何不同的操作系统，类似操作系统。直接运行在硬件上

只有虚拟机管理程序是允许在内核态，上层操作系统和应用程序，都运行在用户态。

第二类虚拟机管理程序：

在 宿主操作系统 上安装 客户操作系统，并不是直接运行在硬件上，而是运行在 宿主操作系统 上。

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

处理机管理

进程

进程的概念

程序：是静态的，存在在磁盘里的可执行文件，是一系列指令的集合。

进程：是动态的，程序的一次执行过程。

同一个程序多次执行会对应多个进程。

当进程被创建时，操作系统会为该进程分配一个唯一的、不重复的——PID（Process ID，进程ID）

为了使参与并发执行的每个程序（含数据）都能独立的运行，必须唯一配置一个专门的数据结构PCB（Process Control Block），即进程控制块。系统利用PCB来描述进程的基本情况和运行状态，进而控制和管理进程，但凡管理时所需要的信息，都会被放入PCB中。

PCB是进程存在的唯一标志，当进程被创建时，操作系统为其创建PCB，当进程结束时，会回收其PCB。

程序段——包含程序指令；数据段——包含运行过程中产生的各种数据。

进程实体（又称进程映像）由程序段、相关数据段和PCB三部分构成。PCB是给操作系统使用的；程序段和数据段是给进程自己使用的，与进程自身的运行逻辑有关。所谓创建进程，就是创建进程实体中的PCB；撤销进程，实质上就是撤销进程的PCB。

**进程映像是静态的，进程则是动态的！**进程实体反映了进程在某一时刻的状态。

进程是进程实体的运行过程，是系统进行资源分配和调度的一个独立单位。

进程的特征：

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

动态性是进程最基本的特征。

进程的状态与转换

创建态：又称新建态，进程正在被创建时，操作系统会为进程分配资源、初始化PCB

就绪态：进程完成创建后，就会进入“就绪态”，处于就绪态的进程已具备运行条件，但由于没有空闲CPU，暂时不能运行

运行态：如果一个进程正在CPU上运行，那么这个进程就处于“运行态”

阻塞态：又称等待态，进程正在等待某一事件而暂停运行，如等待某资源（不包括处理机）为可用或等待输入/输出完成。即使处理机空闲，该进程也无法运行。

终止态：又称结束态，一个进程可用执行exit系统调用，请求操作系统终止该进程，此时进入“终止态”，此时系统先将该进程置为终止态，然后进一步处理资源释放和回收工作，最后还要回收该进程的PCB。当终止进程的工作完成之后，这个进程就消失了。

一个进程从运行态 --> 阻塞态是主动的行为，从阻塞态 --> 就绪态是被动的行为，需要其他相关进程的协助。

进程PCB中，会有一个变量state来表示进程的当前状态。

为了对同一个状态下的各个进程进行统一的管理，操作系统会将各个进程的PCB组织起来。

补充：

进程的组织方式：

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

进程控制

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

如何实现进程控制？用原语实现。

原语的执行具有原子性，即执行过程只能一气呵成，期间不允许被中断。可利用“关中断指令”和“开中断指令”这两个特权指令实现原子性。

CPU每执行完一条指令，都会检查是否有中断信号需要处理，如果有，则暂停运行当前这段程序，转而执行相应的中断处理程序。CPU执行了关中断指令后，就不再例行检查中断信号，直到执行了开中断指令之后才会恢复检查。

进程的创建

创建原语：

1. 申请空白PCB
2. 为进程分配运行所需资源
3. 初始化PCB
4. 将PCB插入就绪队列，等待被调度运行

引起进程创建的事件：终端用户登录系统、作业调度、系统提供服务、用户程序的应用请求等

进程的终止

终止原语：

1. 从PCB集合中找到终止进程的PCB
2. 终止该进程的执行，将处理机资源分配给其他进程
3. 终止其所有的子进程
4. 将该进程所拥有的所有资源归还给父进程或操作系统
5. 删出PCB

引起进程终止的事件：正常结束、异常结束、外界干预

进程的阻塞

阻塞原语：

1. 找到要阻塞进程对应的PCB
2. 保护进程运行现场，将PCB状态信息设置为阻塞态，暂停进程运行
3. 将PCB插入相应事件的等待队列，将处理机资源调度给其他就行进程

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

进程的唤醒

唤醒原语：

1. 在事件等待队列中找到PCB
2. 将其从等待队列中移除，并设置其状态为就绪态
3. 将PCB插入就绪队列，等待调度程序调度

引起进程唤醒的事件：等待的事情发生

进程的切换

切换原语：

1. 将运行环境信息存入PCB
2. PCB移入相应队列
3. 选择另一个进程执行，并更新其PCB
4. 根据PCB恢复新进程所需的运行环境

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

进程通信

进程通信是指进程之间的信息交换。

进程通信需要操作系统的支持。

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

共享存储：

在通信的进程之间存在一块可直接访问的共享空间，通过对这片共享空间进行读/写操作实现进程之间的信息交换。

设置一个共享内存区域，并映射到进程的虚拟地址空间。

为避免出错，各个进程对共享空间的访问应该是互斥的。各个进程可使用操作系统提供的同步互斥工具（如P、V操作）

基于数据结构的共享：如共享空间里只能放一个长度为10的数组，共享速度慢、限制多，是一种低级通信方式。

基于存储区的共享：操作系统在内存中划出一块共享存储区，数据的形式、存放位置都由通信进程控制，而不是操作系统。共享速度快，是一种高级通信方式。

消息传递：

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

直接通信方式：发送进程之间把消息发送给接收进程，并将它挂在接收进程的消息缓冲队列上，接收进程从消息缓冲队列中取得消息。消息发送进程要指明接收进程的ID。

间接通信方式：发送进程将消息发送到某个中间实体（信箱），接收进程从中间实体取得消息。

管道通信：

管道通信允许两个进程按生产者 - 消费者方式进行通信。

生产者向管道的一端写，消费者从管道的另一端读，数据的流向只能是单向的。

“管道”是一个特殊的共享文件，又名pipe文件。其实就是在内存中开辟一个大小固定的内存缓冲区。

1. 管道只能采用半双工通信，某一段时间内只能实现单向传输。如果要实现双向同时通信，则需要设置两个管道。

2. 各进程要互斥地访问管道（由操作系统实现）

3. 当管道写满时，写进程将阻塞，直到读进程将管道中的数据取走，即可唤醒写进程。

4. 当管道读空时，读进程将阻塞，直到写进程往管道内写入数据，即可唤醒读进程。

5. 管道中的数据一旦读出，就彻底消失。当多个进程读同一个管道时，可能导致错乱。

   • 一个管道运行多个写进程，一个读进程
   • 运行有多个写进程，多个读进程，但系统会让各个进程轮流从管道中读数据

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

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

线程

线程的概念

传统的进程只能串行的执行一系列程序。

引入进程：为了更好的使多道程序并发执行，提供系统资源利用率和吞吐量。

引入线程：减小程序在并发执行时所付出的时空开销，提高系统操作的并发性能。

线程，一个基本的CPU执行单位，也是程序执行流的最小单位.

资源分配：

传统进程机制中，进程是资源分配、调度的基本单位；

引入线程后，进程是资源分配的基本单位，线程是调度的基本单位

并发性：

传统进程机制中，只能进程间并发；

引入线程后，各线程间也能并发，提高了并发度

系统开销：

传统的进程间并发，需要切换进程的运行环境，系统开销大；

线程间并发，如果是同一进程内的线程切换，则不需要切换进程环境，系统开销小；

引入线程后，并发所带来的系统开销减小

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

线程的实现方式

用户级线程——早期的操作系统只支持进程，不支持线程。线程由线程库实现。

有关线程管理的所有工作都由应用程序在用户空间中完成，在用户态即可完成，内核意识不到线程的存在。

“用户级线程”就是“从用户视角看能看到的线程”

优点：

1. 线程切换不需要转换到内核空间，节省了模式切换的开销
2. 调度算法可以使进程专用的，不同的进程可根据自身的需要，对自己的线程选择不同的调度算法
3. 用户级线程的实现和操作系统平台无关，对线程管理的代码是属于用户程序的一部分

缺点：

1. 系统调用的阻塞问题，当线程执行一个系统调用时，如果一个用户级线程被阻塞，当前进程内的所有线程都被阻塞，并发度不高。
2. 多个线程不可在多核处理机上并行运行，内核每次分配给一个进程的仅有一个CPU，进程中仅有一个线程能执行。

内核级线程

内核级线程的管理工作由操作系统内核完成，内核级线程的切换必须在核心态下才能完成，操作系统会为每个内核级线程建立相应的线程控制块TCB，通过TCB对线程进行管理。

“内核级线程”就是“从操作系统内核视角能看到的线程”

优点：

1. 能发挥多处理机的优势，内核能发挥多处理机的优势，内核能同时调度同一进程中的多个线程并行执行。
2. 如果进程中的一个线程被阻塞，内核可以调度该进程中的其他线程占用处理机，也可以运行其他进程中的线程。（并发性强）
3. 内核支持线程具有很小的数据结构和堆栈，线程切换比较快、开销小。
4. 内核本身也可采用多线程技术，可以提高系统的执行速度和效率。

缺点：

同一进程中的线程切换需要从用户态到核心态进行，系统开销比较大——线程调度和管理在内核实现的

组合方式——多线程模型

多对一模型：

将多个用户级线程映射到一个内核级线程，线程的调度和管理在用户空间完成，仅当用户线程需要访问内核时，才将其映射到一个内核级线程，但每次只允许一个线程进程映射

优点：

• 线程管理在用户空间进行，效率比较高

缺点：

• 如果一个线程在访问内核时发生阻塞，则整个进程都会被阻塞
• 只有一个线程能访问内核，多个线程不能同时在多个处理机上运行

一对一模型：

将每个用户级线程映射到一个内核级线程

优点：

• 当一个线程被阻塞后，运行调度另一个线程运行，并发能力强

缺点：

• 每创建一个用户线程，就需要创建一个内核线程，开销大

多对多模型：

将n个用户线程映射到m个内核级线程上，要求n≥m

克服了多对应模型并发度不高（如果一个线程在访问内核时发生阻塞，则整个进程都会被阻塞）的缺点，又克服了一对一模型中开销太大（一个用户进程占用太多内核级线程）的缺点，同时用于以上两种模型的优点

内核级线程是处理机分配的单位

一个进程引入多个内核级线程，只有当所有的内核级线程都被阻塞，整个进程才会被阻塞。

线程的状态与切换

线程的组织与控制

处理机调度

调度的概念

在多道程序中，进程的数量往往多于处理机的个数，由于资源有限，就会产生进程争用处理机的情况

处理机调度是对处理机进行分配，即从就绪队列按照一定的算法（公平、高效的原则）选择一个进程并将处理机分配给它运行，以实现进程并发的执行

调度的层次

高级调度（作业调度）：按一定的原则从外存的作业后备队列中挑选一个（或多个）作业，给它（它们）分配内存、输入/输出设备等必要资源，并创建相应的进程，使它（它们）获得竞争处理机的权利。外存 --> 内存（面向作业）。

每个作业只调入一次，调出一次。作业调入时建立PCB，调出时才撤销PCB。作业调度就是内存与辅存之间的调度。

低级调度（进程调度/处理机调度）：按某种算法从就绪队列中选取一个进程，将处理机分配给它。内存 --> CPU

进程调度是操作系统中最基本的一种调度，在一般的操作系统中都必须配置进程调度。进程调度频率很高，一般几十毫秒一次。

在系统内存不足时，可将某些进程的数据调入外存，等内存空闲或进程需要重新运行时再重新调入内存。暂时调到外存等待的状态被称为挂起态，被挂起的进程PCB会被组织成挂起队列。当他们已经具有运行条件且内存又稍有空闲时，由中级调度来决定把外存上的那些已具备运行条件的就绪进程重新调入内存，并修改其状态为就绪态。

中级调度（内存调度）：按某种策略决定将哪个处于挂起状态的进程重新调入内存。外存 --> 内存（面向进程）。

中级调度发生的频率要比高级调度更高。

引入中级调度的目的是提高内存利用率和系统吞吐量。

暂时调到外存等待的进程状态为挂起态，挂起态可进一步分为就绪挂起和阻塞挂起。

挂起与阻塞——两种状态都是暂时不能获得CPU的服务，但挂机状态是将进程调到外存，而阻塞态下进程映像还在内存中。

调度的实现

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

• 在处理中断的过程中。中断处理过程复杂，与硬件密切相关，很难做到在中断处理过程中进行进程切换。
• 进程在操作系统内核临界区。进入临界区后，需要独占式的访问，理论上必须加锁，以防其他并行进程进入，解锁前不应切换到其他进程，以加快临界区的释放。
• 其他需要完全屏蔽中断的原子操作过程中。原子操作不可中断。

进程在操作系统内核程序临界区中不能进行调度和切换。√

进程在处于临界区时不能进行处理机调度。×

临界资源——一段时间内只允许一个进程使用的资源。各进程需要互斥地访问临界资源。

临界区——访问临界资源的代码。

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

普通临界区访问的临界资源不会直接影响操作系统内核的管理工作。因此在访问普通临界区时可以进行调度与切换。

进程调度的方式

• 非抢占调度方式，非剥夺方式。只允许进程主动放弃处理机。在运行过程中即便有更紧迫的任务到达，当前进程依然会继续使用处理机，直到该进程运行完成或发生某种事件而进入阻塞态，才把处理机分配给其他进程。

  实现简单、系统开销小，适用于早期的批处理系统，但无法及时处理紧急任务，不能用于分时系统和大多数的实时系统。

• 抢占调度方式，剥夺方式。当一个进程正在处理机上执行时，若有某个更为重要或紧迫的进程需要使用处理机，则允许调度程序根据某种原则去暂停正在执行的进程，将处理机分配给这个更为重要或紧迫的进程。

  可以优先处理更紧急的进程，也可以实现让各进程按时间片轮流执行的功能（通过时钟中断）。适合分时操作系统、实时操作系统

“进程调度”与进程切换的区别？

狭义的进程调度指的是从就绪队列中选出一个要运行的进程。（可以使刚刚被暂停执行的进程，也可能是另一个进程，后者需要进程切换。）

进程切换是指一个进程让出处理机，由另一个进程占用处理机的过程。

广义的进程调度包含了选择一个进程和进程切换两个步骤。

进程切换的过程：

1. 对原来进程的各种数据的保存
2. 对新的进程数据的恢复

进程切换是有代价的，如果过于频繁的进行进程调度、切换，必然会使整个系统的效率降低，使系统大部分时间花费在进程切换上，而真正用于执行进程的时间减少。

调度程序（调度器）——用于调度和分派CPU的组件称为调度程序

调度时机：

• 创建新进程
• 进程退出
• 运行进程阻塞
• I/O中断发生
• 非抢占式调度策略，只有运行进程阻塞或退出才触发调度程序工作
• 抢占式调度策略，每个时钟中断或k个时钟中断会触发调度程序工作

不支持内核级线程的操作系统，调度程序的处理对象是进程；

支持内核级线程的操作系统，调度程序的处理对象是内核线程。

闲逛进程——没有其他就绪进程时，运行闲逛进程（idle）

特性：

• 优先级最低
• 可以是0地址指令，占一个完整的指令周期（指令周期末尾例行检查中断）
• 能耗低

调度算法

饥饿：某进程/作业长期得不到服务

先来先服务（FCFS）

按照作业/进程 到达的先后顺序进行服务，非抢占调度方式。可用于作业、进程调度。

优点：公平、算法实现简单

缺点：排在长作业（进程）后面的短作业（进程）需要等待很长时间，带权周转时间很大

对长作业有利，对短作业不利。不会导致饥饿

短作业优先（SJF，Shortest Job First）

思想：追求最少的平均等待时间，最少的平均周转时间，最少的平均带权周转时间

最短的作业/进程优先得到服务。每次调度选择当前已到达且运行时间最短的作业/进程。

可用于作业、进程调度，用于进程调度时称为“短进程（SPF，Shortest Process First）优先算法”

SJF和SPF是非抢占式的算法，也有抢占式的版本——最短剩余时间优先算法（SRTN，Shortest Remaining Time Next）

最短剩余时间优先算法：每当有进程加入，就绪队列改变时就需要调度，如果新到达的进程剩余时间比当前运行的进程剩余时间更短，则由新进程抢占处理机，当前运行进程重新回到就绪队列。当一个进程完成时也需要调度

短作业/进程优先算法默认是非抢占式的，在所有进程都几乎同时到达时，采用SJF调度算法的平均等待时间、平均周转时间最少。

抢占式的短作业/进程优先算法（最短剩余时间优先算法，SRTN算法）平均等待时间、平均周转时间最少。

优点：“最短的”平均等待时间、平均周转时间

缺点：不公平。对短作业有利，长作业不利。可能产生饥饿现象。作业/进程的运行时间由用户提供，并不一定真实，不一定能做到真正的短作业优先。

高响应比优先（HRRN，Highest Response Ratio Next）

综合考虑作业/进程的等待时间和要求服务的时间，在每次调度时先计算各个作业/进程的响应比，选择响应比最高的作业/进程为其服务。等待时间相同时，要求服务时间短的优先；要求服务时间相同时，等待时间长的优先。

既可用于作业调度，也可用于进程调度。非抢占式的算法。不会导致饥饿。

$响应比 = \frac {等待时间 + 要求服务时间}{要求服务时间}$

时间片轮转调度算法（RR，Round-Robin）

公平地、轮流地为各个进程服务，让每个进程在一定时间间隔内都可以得到响应。按着各个进程到达就绪队列的顺序，轮流让各个进程执行一个时间片。在使用完一个时间片后，即使进程未能运行完成，它也必须被剥夺处理机给下一个就绪进程，被剥夺的进程重新返回就绪队列末尾进行排队，等待再次运行。

用于进程调度。抢占式的算法。不会导致饥饿。由时钟装置发出时钟中断来通知CPU时间已到。常用于分时操作系统。

如果时间片太大，使得每一个进程都可以在一个时间片内完成，则时间片轮转调度算法退化为先来先服务调度算法，并增大进程响应时间。时间片不能太大。进程调度、切换是有时间代价的，如果时间片太小，会导致进程切换过于频繁，系统会花大量时来处理进程切换，从而导致实际用于进程执行的时间比例减少吗。时间片不能太小。一般来说，设计时间片要让切换进程的开销占比不超过1%。

优点：公平、响应快，适用于分时操作系统。

缺点：高频率的进程切换会产生一定的开销；不区分任务的紧急程度。

优先级调度算法

每个作业/进程有各自的优先级，调度时选择当前已到达且优先级最高的进程/作业。

既可用于作业调度，也可用于进程调度，甚至还会用于I/O调度中。抢占式、非抢占式都有。会导致饥饿。

根据优先级是否可以动态改变，可以将优先级分为静态优先级和动态优先级。

静态优先级——创建进程时确定，且在进程的整个运行期间保持不变。确定静态优先级的主要依据有进程类型、进程对资源的要求、用户要求。

动态优先级——创建进程有一个初始值，在进程运行的过程中，根据进程情况变化动态调整优先级。动态调整优先级的主要依据有进程占CPU时间的长短、就绪进程等待CPU时间的长短。

一般来说，系统进程 优先级 高于用户进程；交互型进程 高于 非交互型进程（前台进程 高于 后台进程）；I/O型进程 高于 计算型进程。

优点：用优先级区分紧急程度、重要程度，适用于实时操作系统；可灵活调整作业/进程的优先级。

缺点：若不断有高优先级进程到来，可能会导致饥饿。

多级反馈队列调度算法

用于进程调度。抢占式的算法。会导致饥饿。

设置多级就绪队列，各级队列优先级从高到低，时间片从小到大。

新进程到达时进入第1级队列，按FCFS原则进程排队等待被分配时间片。当轮到该进程执行时，如果它能在该时间片内完成，可撤离系统；若在一个时间片内未能完成，则调度程序将其转入第2级队列末尾等待调度；以此类推，当进程处于第n级（最下级）队列时，在第n级队列中采用时间片轮转调度算法运行。

按队列优先级调度，只有第k级队列为空，才会调度第k+1级队列中的进程运行。

若处理机此时正在运行某进程，又有新进程进入一个优先级较高的队列，此时必须将处理机分配给优先级较高队列中的进程，被抢占处理机的进程重新回到原队列的末尾。

多级队列调度算法

系统按照进程类型设置多个队列，不同队列设置不同优先级

调度算法的评价指标

CPU利用率：CPU处于“忙碌”的时间栈总时间的比例。

$利用率=\frac {CPU有效工作时间}{总时间}$

系统吞吐量：单位时间内CPU完成作业的数量

$系统吞吐量=\frac {总共完成了多少道作业}{总花费时间}$

周转时间：从作业提交到作业完成所经历的时间，包括作业在外存后备队列等待作业调度（高级调度）的时间、进程在就绪队列上等待进程调度（低级调度）的时间、进程在CPU上执行的时间、进程等待I/O操作完成的时间。

$周转时间 = 作业完成时间 - 作业提交时间$

$平均周转时间 = \frac {作业周转时间和}{作业数}$

$带权周转时间 = \frac {作业周转时间}{作业实际运行时间}= \frac {作业完成时间 - 作业提交时间}{作业实际运行时间}$

$平均带权周转时间 = \frac {作业带权周转时间和}{作业数}$

带权周转时间必然≥1，带权周转时间与周转时间越小越好

等待时间：进程/作业等待处理机的时间之和，等待事件越长，用户满意度越低。

对于进程来说，等待事件就是进程建立后等待被服务的时间之和，在等待I/O完成的期间其实进程也是在被服务的，所以不计入等待时间。

对于作业来说，不仅要考虑建立进程后的等待时间，还要加上作业在外存后备队列中等待的时间。

调度算法实际上并不影响作业执行或I/O操作的时间，只影响作业在就绪队列中的等待时间。

$平均等待时间 = \frac {作业等待时间之和}{作业数}$

响应时间：用户从提交请求到系统首次产生响应所用的时间

同步与互斥

基本概念

异步：各并发执行的进程以各自独立、不可预知的速度向前推进。

同步亦称直接制约关系，它是为了完成某种任务而建立的两个或多个进程，这些进程因为需要在某些位置上协调它们的工作次序而等待、传递信息所产生的制约关系。进程间的直接制约关系就是源于它们之间的相互合作。

进程的“并发”需要“共享”的支持。对临界资源（一个时间段内只允许一个进程使用的资源）的访问必须互斥地进行。

互斥亦称间接制约关系。进程互斥是指当一个进程访问某临界资源时，另一个进程必须等待，当占用临界资源的进程退出临界区后，另一进程才允许去访问此临界资源。

do {
	entry section;		// 进入区:负责检查是否可进入临界区,可进入则设置正在访问临界资源的标志,防止其他进程进入临界区
	critical section;	// 临界区:访问临界资源的代码
	exit section;		// 负责解除正在访问临界资源的标志
	remainder section;	// 做其他处理
} while(true)

临界区是进程中访问临界资源的代码段。进入区和退出区是负责实现互斥的代码段。临界区也可称为“临界段”。

同步机制遵循原则：空则让进、忙则等待、有限等待、让权等待。