命令接口： 允许用户直接使用

• 联机命令接口：用户说一句，系统做一句 = 互动命令界面
• 脱机命令接口:用户说一堆，系统做一堆 = 批处理命令界面

程序接口： 允许用户通过程序间接使用

由一组系统调用组成(程序接口=系统调用）

系统调用 = 系统调用命令 = 广义指令

GUI： 图形用户界面是现代操作系统中最流行的

所需的功能和目标：实现硬件机扩展

没有软件支持的计算机被称为裸机。安装在裸机上的操作系统可以提供资源管理功能和方便用户的服务功能，将裸机改造成功能更强、使用更方便的机器。

覆盖软件的机器通常被称为扩充机器，又称之为虚拟机。

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

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

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

单核处理机（CPU）一个程序只能在同一时间执行，因此操作系统负责协调多个程序的交替执行（这些程序在微观上交替执行，但在宏观上似乎同时执行）

事实上，操作系统是伴随着多程序技术而出现的。因此，操作系统和程序并发是一起诞生的。

共享：即资源共享，是指系统中的资源可以用于内存中多个并发执行的过程。

所谓的同时往往是宏观的，在微观上，这些过程可能会交替访问资源（即分时共享）

• 互斥共享方式
• 共享方式

并发和共享的关系（互为存在条件）

并发与共享的关系通过上述例子来看:

使用QQ发送文件A，同时，使用微信发送文件B。

1.两个过程并发执行(并发性)

如果失去并发性，系统中只有一个程序在运行，那么共享就失去了存在的意义

2.需要共享访问硬盘资源(共享)

若失去共享性，则QQ如果不能同时访问硬盘资源，就不能同时发送文件，也不能并发。

虚拟：它是指将一个物理实体转化为几个逻辑对应物。物理实体(前者)实际存在，逻辑上是用户感受到的。

虚拟技术：用于实现虚拟技术

虚拟处理器（CPU）：通过多个程序设计技术，分时使用多个程序并发执行的方法CPU，实际上物理上只有一个CPU，但是用户觉得有很多CPU

虚拟存储器：在逻辑上扩展存储容量，用户感觉到但实际上不存在

虚拟设备：将物理设备虚拟化为逻辑上的多个设备，使多个用户同时访问同一设备，即同时共享，用户的宏观感觉是同时的，但实际上是微观的

观察交替访问同一设备

虚拟技术

• 时间复用技术：例如，分时共享处理器
• 空分复用技术：如虚拟存储器

没有并发，就无法探索虚拟性

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

显然，如果失去并发性，系统只能串行处理每个过程，每个过程的执行将一直持续到底。只有系统具有并发性，才能导致异步。

没有并发和共享，就没有虚拟和异步，所以并发和共享是操作系统的两个基本特征。

过程： 用户将程序写在纸带上（实际上是在纸带上打孔），然后输入到计算机中，计算机将处理程序，将输出结果放在纸带中（实际上是打孔），并向用户显示。

由于用户在纸带上编写程序速度慢，纸带输入输出速度慢，计算机处理速度快，系统资源利用率极低。

主要缺点：用户独占全机、人机速度矛盾导致资源利用率极低

引入脱机输入/输出技术(用磁带完成)并使用监督程序(操作系统的雏形)负责控制操作的输入和输出。

由于磁带进入处理器的速度远快于纸带，单道批处理系统在一定程序上缓解了人机速度矛盾，提高了资源利用率。

主要优点： 缓解了一定程度的人机速度矛盾，提高了资源利用率。

主要缺点： 内存中仅能有一道程序运行，只有在程序运行结束后才能转移到下一个程序。CPU有很多空闲时间等待I/O完成。资源利用率仍然很低。

多个程序每次输入内存，操作系统正式诞生，并引入了中断技术，这些程序的运行由操作系统管理。每个程序并发执行。

主要优点： 并发执行多个程序，共享计算机资源。资源利用率显著提高，CPU与其他资源保持忙碌，系统吞吐量增加。

主要缺点： 用户响应时间长，没有人机交互功能(提交作业后，用户只能等待计算机处理，中间无法控制作业执行)

计算机以时间片为单位轮流每个用户/作业务，各个用户可通过终端与计算机进行交互。

主要优点： 用户请求可以被即时响应，解决了人机交互问题。允许多个用户同时使用一台计算机，并且用户对计算机的操作相互独立，感受不到别人的存在。

主要缺点： 不能优先处理一些紧急任务。操作系统对各个用户/作业都是完全公平的，循环地为每个用户/作业服务一个时间片，不区分任务的紧急性。

在实时操作系统的控制下，计算机系统接收到外部信号后及时进行处理，并且要在严格的时限内处理完事件。实时操作系统的主要特点是及时性和可靠性。

主要优点： 能够优先响应一些紧急任务，某些紧急任务不需时间片排队。

• 硬实时系统：必须在绝对严格的规定时间内完成处理（导弹系统）
• 软实时系统：能接受偶尔违反时间规定（12306火车票）

网络操作系统

工作方式：把计算机网络中的各台计算机有机的结合起来，提供统一、经济而有效的使用各台计算机的方法、实现各台计算机之间的数据互相传送

特点：有主从关系、网络中资源共亨、网络中的计算机通过协议通信

分布式操作系统

工作方式︰系统中的各计算机相互协同并行完成同一任务

特征

• 系统中任意两台计算机通过通信方式交换信息

• 系统中的计算机都具有同等地位，无主从关系

• 每台计算机上的资源为所有用户共享

• 系统中的任意台计算机都可以构成一个子系统，并且还能重构

• 任何工作都可以分布在几台计算机上、由他们并行工作、协同完成

特点：分布性和并行性

嵌入式操作系统

固话在硬件里面的系统、比如手机、路由器等

特点

• 完成某一项特定的功能、不具有通用性
• 广泛用于文字处理、电子表格、游戏中等

个人计算机操作系统

常见的有Windows、Linux、Macintosh等

指令：就是处理器（CPU）能识别、执行的最基本命令

• 特权指令： 如内存清零指令 --> 不允许用户程序使用。
• 非特权指令： 如普通的运算指令

CPU如何判断当前是否可以执行特权指令？

用程序状态寄存器（PSW）中的某标志位来标识当前处理器处于什么状态，如0为用户态，1为核心态。

• 用户态（目态）： 此时CPU只能执行非特权指令
• 核心态（管态）：特权指令、非特权指令都可以执行

• 内核程序： 操作系统的内核程序是系统的管理者，既可以执行特权指令，也可以执行非特权指令，运行在核心态。
• 应用程序： 为了保证系统能安全运行，普通应用程序只能执行非特权指令，运行在用户态。

内核：计算机上配置的底层软件，是操作系统最基本、最核心的部分。

实现操作系统内核功能的那些程序就是内核程序。

时钟管理： 实现计时功能

中断处理： 负责实现中断机制

原语

• 是一种特殊的程序
• 处于操作系统最底层，是最接近硬件的部分
• 这种程序的运行具有原子性 —— 其运行只能一气呵成，不可中断
• 运行时间较短，调用频繁

对系统资源进行管理的功能 （有的操作系统不把这部分功能归为 “ 内核功能 ”。也就是说不同的操作系统，对内核功能的划分可能并不一样）

• 进程管理
• 存储器管理
• 设备管理

• 大内核
  • 将操作系统的主要功能模块都作为系统内核，运行在核心态
  • 优点：高性能
  • 缺点：内核代码庞大，结构混乱，难以维护
• 微内核
  • 只把最基本的功能保留在内核
  • 优点：内核功能少，结构清晰，方便维护
  • 缺点：需要频繁地在核心态和用户态之间切换，性能低

早期的计算机：各程序只能串行执行，系统资源利用率低

为了解决上述问题，人们发明了操作系统（作为计算机的管理者），引入中断机制，实现了多道程序并发执行。

本质：发生中断就意味着需要操作系统介入，开展工作。

1、当中断发生时，CPU立即进入核心态

2、当中断发生后，当前运行的进程暂停运行，并由操作系统内核对中断进行处理

3、对于不同的中断信号，会进行不同的处理

由于操作系统的管理工作（比如进程切换、分配I/O设备等）需要使用特权指令，因此CPU要从用户态转为核心态。中断可以使CPU从用户态切换为核心态，使操作系统获得计算机的控制权。有了中断，才能实现多道程序并发执行。

用户态、核心态之间的切换是怎么实现的？

• “ 用户态 --> 核心态 ” 是通过中断实现，并且中断是唯一途径。
• “ 核心态 --> 用户态 ” 的切换是通过执行一个特权指令，将程序状态字（PSW）的标志位设置为用户态。

用户态和核心态就是程序状态寄存器0或1标志的，因此核心态到用户态可以通过特权指令进行设置！

• 内中断
• 外中断

分类二

外中断处理过程

1. 执行完每个指令之后，CPU都要检查当前是否有外部中断信号
2. 如果检测到外部中断信号，则需要保护被中断进程的CPU环境（如程序状态字PSW、程序计数器PC、各种通用寄存器）
3. 根据中断信号类型转入相应的中断处理程序
4. 恢复原进程的CPU环境并退出中断，返回原进程继续往下执行

更详细过程

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

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

系统调用相关处理涉及到对系统资源的管理、对进程的控制，这些功能需要执行一些特权指令才能完成，因此系统调用的线管处理需要在核心态下进行。

• 设备管理：完成设备的请求/释放/启动等功能
• 文件管理：完成文件的读/写/创建/删除等功能
• 进程控制：完成进程的创建/撤销/阻塞/唤醒等功能
• 进程通信：完成进程之间的消息传递/信号传递等功能
• 内存管理：完成内存的分配/回收等功能

1. 陷入指令是在用户态执行的，执行陷入指令之后立即引发一个内中断，从而CPU进入核心态。
2. 发出系统调用请求是在用户态，而对系统调用的相应处理在核心态下进行。
3. 陷入指令是唯一一个只能在用户态执行的内中断指令（特权指令），而不可在核心态执行的指令。

• 进程与线程
• 处理机调度及调度算法
• 进程同步与互斥
• 死锁

程序：就是一个指令序列

• 早期的计算机（只支持单道程序）
• 引入多道程序技术之后：为了方便操作系统管理，完成各程序并发执行，引入了进程、进程实体的概念。

PCB： 系统为每个运行的程序配置一个数据结构，称为进程控制块（PCB），用来描述进程的各种信息（如代码存放位置）

PCB、程序段、数据段三部分构成了进程实体（进程映像）。一般情况下，我们把进程实体简称为进程，例如，所谓创建进程，实质上是创建进程实体中的PCB；而撤销进程，实质上是撤销进程实体中的PCB。PCB是进程存在的唯一标志！

定义： 强调动态性

1. 进程是程序的一次执行过程。
2. 进程是一个程序及其数据在处理机上顺序执行时所发生的活动。
3. 进程是具有独立功能的程序在数据集合上运行的过程，它是系统进行资源分配和调度的一个独立单位。

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

严格来说，进程实体和进程不一样，进程实体是静态的，进程则是动态的。

进程（进程实体）由程序段、数据段、PCB三部分组成。

• 数据段：程序运行时使用、产生的运算数据。如全局变量
• 程序段：程序代码即存放在此
• PCB：操作系统通过PCB来管理进程，因此PCB中应该包含操作系统对其进行管理所需的各种信息。

进程的组成讨论的是一个进程内部由哪些部分构成的问题，而进程的组织讨论的是多个进程之间的组织方式问题。

进程的组织方式：

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

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

进程是程序的一次执行过程。在这个执行过从中，有时进程正在被CPU处理，有时又需要等待CPU服务，可见 ，进程的状态是会有各种变化。为了方便对各个进程的管理，操作系统需要将进程合理地划分为几种状态。

三种基本状态

运行态（Running）：

• 占有CPU，并在CPU上运行
• 注意：单核处理机环境下，每一个时刻最多只有一个进程处于运行态。双核环境下可以同时有两个进程处于运行态

就绪态（Ready）：

• 已经具备运行条件，但由于没有空闲CPU，而暂时不能运行。
• 进程已经拥有了除处理机之外所有需要的资源，一旦获得处理机，即可立即进入运行态开始运行。

阻塞态（Waiting/Blocked，又称：等待态）：

• 因等待某一事件而暂时不能运行
• 如：等待操作系统分配打印机、等待读磁盘操作的结果。CPU是计算机中最昂贵的部件，为了提高CPU的利用率，需要先将其他进程需要的资源分配到位，才能得到CPU的服务

另外两种状态：

创建态（New，又称：新建态）

• 进程正在被创建，操作系统为进程分配资源、初始化PCB

终止态（Terminated，又称：结束态）

• 进程正在从系统中撤销，操作系统会回收进程拥有的资源、撤销PCB

• 处理机是否占用
• 其他是否拥有

根据以上即可知道处于哪个状态！

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

如何实现进程控制？

用原语实现进程控制。原语的特点是执行期间不允许中断，只能一气呵成。

这种不可被中断的操作即原子操作。

原语采用“关中断指令”和“开中断指令”实现

显然，关/开中断指令的权限非常大，必然只允许在核心态下执行的特权指令。

• 更新PCB中的信息（如修改进程状态，将运行环境保存到PCB、从PCB恢复运行环境）
  • 所有的进程控制原语一定都会修改进程状态标志
  • 剥夺当前运行进程的CPU使用权必然需要保存其运行环境
  • 某进程开始运行前必然要恢复其运行环境
• 将PCB插入合适的队列
• 分配/回收资源

进程通信是指进程之间的信息交换。PV操作是低级通信方式，高级通信方式是指以较高的程效率传输大量数据的通信方式。

进程是分配系统资源的单位（包括内存地址空间)，因此各进程拥有的内存地址空间相互独立。

为了保证安全，一个进程不能直接访问另一个进程的地址空间。

但是进程之间的信息交换又是必须实现的。为了保证进程间的安全通信，操作系统提供了一些方法。

两个进程对共享空间的访问必须是互斥的（互斥访问通过操作系统提供的工具实现）。

操作系统只负责提供共享空间和同步互斥工具（如P、v操作)

共享存储

• 基于数据结构共享：比如共享空间里只能放一个长度为10的数组。这种共享方式速度慢、限制多，是一种低级通信方式
• 基于存储区共享：基于在内存中画出一块共享存储区，数据的形式、存放位置都由进程控制，而不是操作系统。相比之下，这种共享方式速度更快，是一种高级通信方式。

“管道”是指用于连接读写进程的一个共享文件，又名pipe文件。其实就是在内存中开辟一个大小固定的缓冲区

• 管道只能采用半双工通信，某一时间段内只能实现单向的传输。如果要实现双向同时通信，则需要设置两个管道。
• 各进程要互斥地访问管道。
• 数据以字符流的形式写入管道，当管道写满时，写进程的write() 系统调用将被阻塞，等待读进程将数据取走。当读进程将数据全部取走后，管道变空，此时读进程的read() 系统调用将被阻塞。（缓冲区的特性）
• 如果没写满，就不允许读。如果没读空，就不允许写。（缓冲区的特性）
• 数据一旦被读出，就从管道中被抛弃，这就意味着读进程最多只能有一个，否则可能会有读错数据的情况。

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

消息

• 消息头：包括发送进程ID、接受进程ID、消息类型、消息长度等格式化的信息（计算机网络中发送的“报文”其实就是一种格式化的消息)
• 消息体

消息传递方式

• 直接消息传递：消息直接挂到接收进程的消息缓冲队列上
• 间接消息传递：消息要先发送到中间实体（信箱）中，因此也称“信箱通信方式”。Eg：计网中的电子邮件系统

有的进程可能需要“同时”做很多事，而传统的进程只能串行地执行一系列程序。为此，引入了“线程”，来增加并发度。

• 传统的进程是程执行流的最小单位
• 引入线程后，线程成为了程序执行流的最小单位

可以把线程理解为“轻量级进程”。
线程是一个基本的CPU执行单元，也是程序执行流的最小单位。

引入线程之后，不仅是进程之间可以并发，进程内的各线程之间也可以并发，从而进一步提升了系统的并发度，使得一个进程内也可以并发处理各种任务（如QQ视频、文字聊天、传文件)
引入线程后，进程只作为除CPU之外的系统资源的分配单元（如打印机、内存地址空间等都是分配给进程的）。

引入线程带来的变化

资源分配、调度

• 传统进程机制中，进程是资源分配、调度的基本单位
• 引入线程后，进程是资源分配的基本单位，线程是调度的基本单位

并发性

• 传统进程机制中，只能进程间并发
• 引入线程后，各线程间也能并发，提升了并发度

系统开销

• 传统的进程间并发，需要切换进程的运行环境，系统开销很大
• 线程间并发，如果是同一进程内的线程切换，则不需要切换进程环境，系统开销小
• 引入线程后，并发所带来的系统开销减小

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

用户级线程

• 用户级线程由应用程序通过线程库实现。所有的线程管理工作都由应用程序负责（包括线程切换)
• 用户级线程中，线程切换可以在用户态下即可完成，无需操作系统干预。
• 在用户看来，是有多个线程。但是在操作系统内核看来，并意识不到线程的存在。（用户级线程对用户不透明，对操作系统透明)
• 可以这样理解，“用户级线程”就是“从用户视角看能看到的线程”

内核级线程

• 内核级线程的管理工作由操作系统内核完成。线程调度、切换等工作都由内核负责，因此内核级线程的切换必然需要在核心态下才能完成。
• 可以这样理解，“内核级线程”就是“从操作系统内核视角看能看到的线程”

在同时支持用户级线程和内核级线程的系统中，可采用二者组合的方式:将n个用户级线程映射到m个内核级线程上 ( n >= m)

• 操作系统只“看得见”内核级线程，因此只有内核级线程才是处理机分配的单位。
• 例如：该进程由两个内核级线程，三个用户级线程，在用户看来，这个进程中有三个线程。但即使该进程在一个4核处理机的计算机上运行，也最多只能被分配到两个核，最多只能有两个用户线程并行执行（只能分配到有限的两个内核级线程）。

在同时支持用户级线程和内核级线程的系统中，由几个用户级线程映射到几个内核级线程的问题引出了“多线程模型”问题。

多对一模型：多个用户及线程映射到一个内核级线程。每个用户进程只对应一个内核级线程。

• 优点:用户级线程的切换在用户空间用户态即可完成，不需要切换到核心态，线程管理的系统开销小，效率高
• 缺点:当一个用户级线程被阻塞后，整个进程都会被阻塞，并发度不高。多个线程不可在多核处理机上并行运行（只有一个内核级线程）

一对一模型：一个用户及线程映射到一个内核级线程。每个用户进程有与用户级线程同数量的内核级线程。

• 优点:当一个线程被阻塞后，别的线程还可以继续执行，并发能力强。多线程可在多核处理机上并行执行。
• 缺点:一个用户进程会占用多个内核级线程，线程切换由操作系统内核完成，需要切换到核心态，因此线程管理的成本高，开销大。

多对多模型：n用户及线程映射到m个内核级线程(n >= m） 。每个用户进程对应m个内核级线程。

• 克服了多对一模型并发度不高的缺点，又克服了一对一模型中一个用户进程占用太多内核级线程，开销太大的缺点。

当有一堆任务要处理，但由于资源有限，这些事情没法同时处理。这就需要确定某种规则来决定处理这些任务的顺序，这就是“调度”研究的问题。

在多道程序系统中，进程的数量往往是多于处理机的个数的，这样不可能同时并行地处理各个进程。处理机调度，就是从就绪队列中按照一定的算法选择一个进程并将处理机分配给它运行，以实现进程的并发执行。

由于内存空间有限，有时无法将用户提交的作业全部放入内存，因此就需要确定某种规则来决定将作业调入内存的顺序。

高级调度（作业调度）：按一定的原则从外存上处于后备队列的作业中挑选一个（或多个）作业，给他们分配内存等必要资源，并建立相应的进程（建立PCB），以使它（们）获得竞争处理机的权利。

高级调度是辅存（外存）与内存之间的调度。每个作业只调入一次，调出一次。作业调入时会建立相应的PCB，作业调出时才撤销PCB。高级调度主要是指调入的问题，因为只有调入的时机需要操作系统来确定，但调出的时机必然是作业运行结束才调出。

引入了虚拟存储技术之后，可将暂时不能运行的进程调至外存等待。等它重新具备了运行条件且内存又稍有空闲时，再重新调入内存。

这么做的目的是为了提高内存利用率和系统吞吐量。

暂时调到外存等待的进程状态为挂起态。值得注意的是，PCB并不会一起调到外存，而是会常驻内存。PCB中会记录进程数据在外存中的存放位置，进程状态等信息，操作系统通过内存中的PCB来保持对各个进程的监控、管理。被挂起的进程PCB会被放到的挂起队列中。

中级调度（内存调度）：就是要决定将哪个处于挂起状态的进程重新调入内存。

一个进程可能会被多次调出、调入内存，因此中级调度发生的频率要比高级调度更高。

低级调度（进程调度）：其主要任务是按照某种方法和策略从就绪队列中选取一个进程，将处理机分配给它。

进程调度是操作系统中最基本的一种调度，在一般的操作系统中都必须配置进程调度。

进程调度的频率很高，一般几十毫秒一次。

暂时调到外存等待的进程状态为挂起态

挂起态又可以进一步细分为就绪挂起、阻塞挂起两种状态

五状态模型 升级为 七状态模型

注意“挂起”和“阻塞”的区别

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

有的操作系统会把就绪挂起、阻塞挂起分为两个挂起队列，甚至会根据阻塞原因不同再把阻塞挂起进程进一步细分为阻塞挂起 多个队列。

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

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

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

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

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

临界区：访问临界资源的那段代码。

“狭义的进程调度”与“进程切换”的区别：

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

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

过程

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

进程切换的过程主要完成了：

• 对原来运行进程各种数据的保存
• 对新的进程各种数据的恢复（如：程序计数器、程序状态字、各种数据寄存器等处理机现场信息，这些信息一般保存在进程控制块）

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

非剥夺调度方式，又称非抢占方式。即，只允许进程主动放弃处理机。在运行过程中即便有更紧迫的任务到达，当前进程依然会继续使用处理机，直到该进程终止或主动要求进入阻塞态。

• 实现简单，系统开销小但是无法及时处理紧急任务，适合于早期的批处理系统

剥夺调度方式，又称抢占方式。当一个进程正在处理机上执行时，如果有一个更重要或更紧迫的进程需要使用处理机，则立即暂停正在执行的进程，将处理机分配给更重要紧迫的那个进程。

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

CPU利用率：指CPU “忙碌”的时间占总时间的比例。

利用率 = 忙碌的时间 / 总时间

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

系统吞吐量 = 总共完成了多少道作业 / 总共花了多少时间

周转时间，是指从作业被提交给系统开始，到作业完成为止的这段时间间隔。

它包括四个部分：

• 作业在外存后备队列上等待作业调度（高级调度）的时间、
• 进程在就绪队列上等待进程调度（低级调度）的时间、
• 进程在CPU上执行的时间、
• 进程等待I/O操作完成的时间。

后三项在一个作业的整个处理过程中，可能发生多次

• 周转时间=作业完成时间–作业提交时间
• 平均周转时间=各作业周转时间之和/作业数
• 带权周转时间=作业周转时间/作业实际运行的时间=(作业完成时间–作业提交时间)/作业实际运行的时间
• 平均带权周转时间=各作业带权周转时间之和/作业数

带权周转时间与周转时间都是越小越好

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

无I/O处理：等待时间 = 周转时间 - 运行时间

有I/O处理：等待时间 = 周转时间 - 运行时间 - I/O处理时间

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

一个作业总共需要被CPU服务多久，被I/O设备服务多久一般是确定不变的，因此调度算法其实只会影响作业 / 进程的等待时间。当然，与前面指标类似，也有“平均等待时间”来评价整体性能。

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

公平

按照作业 / 进程到达的先后顺序进行服务

用于作业 / 进程调度：用于作业调度时，考虑的是哪个作业先到达后备队列；用于进程调度时，考虑的是哪个进程先到达就绪队列

非抢占式的算法

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

缺点：排在长作业（进程）后面的短作业需要等待很长时间，带权周转时间很大，对短作业来说用户体验不好。即，FCFS算法对长作业有利，对短作业不利

不会产生饥饿现象

算法思想：追求最少的平均等待时间，最少的平均周转时间、最少的平均平均带权周转时间（选择当前已到达的时间最短的执行）

算法规则： 最短的作业 / 进程优先得到服务（所谓“最短”，是指要求服务时间最短）

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

SJF和SPF是非抢占式的算法。但是也有抢占式的版本——最短剩余时间优先算法（SRTN, Shortest Remaining Time Next）（新到达的进程的剩余时间比当前运行的进程剩余时间更短，新进程抢占处理机）

优点:“最短的”平均等待时间、平均周转时间（抢占式的SRTN更短）

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

会产生饥饿。如果源源不断地有短作业/进程到来，可能使长作业/进程长时间得不到服务，产生“饥饿”现象。如果一直得不到服务．川称为“饿死”

算法思想：要综合考虑作业/进程的等待时间和要求服务的时间

算法规则：在每次调度时先计算各个作业/进程的响应比，选择响应比最高的作业/进程为其服务

响应比= 等待时间 + 要求服务时间 / 要求服务时间

即可用于作业调度，也可用于进程调度

非抢占式的算法。因此只有当前运行的作业/进程主动放弃处理机时，才需要调度，才需要计算响应比

优缺点：

• 综合考虑了等待时间和运行时间（要求服务时间)
• 等待时间相同时，要求服务时间短的优先（SJF的优点)
• 要求服务时间相同时，等待时间长的优先(FCFS的优点)
• 对于长作业来说，随着等待时间越来越久，其响应比也会越来越大，从而避免了长作业饥饿的问题

不会产生饥饿

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

算法思想：公平地、轮流地为各个进程服务，让每个进程在一定时间间隔内都可以得到响应

算法规则：按照各进程到达就绪队列的顺序，轮流让各个进程执行一个时间片（如100ms）。若进程未在一个时间片内执行完，则剥夺处理机，将进程重新放到就绪队列队尾重新排队。

用于进程调度(只有作业放入内存建立了相应的进程后，才能被分配处理机时间片）

若进程未能在时间片内运行完，将被强行剥夺处理机使用权，因此时间片轮转调度算法属于抢占式的算法。由时钟装置发出时钟中断来通知CPU时间片已到

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

缺点：由于高频率的进程切换，因此有一定开销，不区分任务的紧急程度。时间片太大会退化为FCFS算法，太小进程切换开销太大！

不会产生饥饿

算法思想：随着计算机的发展，特别是实时操作系统的出现，越来越多的应用场景需要根据任务的紧急程度来决定处理顺序

算法规则：每个作业/进程有各自的优先级，调度时选择优先级最高的作业/进程

既可用于作业调度，也可用于进程调度。甚至，还会用于在之后会学习的I/O调度中

抢占式、非抢占式都有。做题时的区别在于:非抢占式只需在进程主动放弃处理机时进行调度即可，而抢占式还需在就绪队列变化时，检查是否会发生抢占。（即新到达的是否比正在运行的优先级要高，高则抢占处理机）

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

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

会产生饥饿

• 就绪队列未必只有一个，可以按照不同优先级来组织。另外，也可以把优先级高的进程排在更靠近队头的位置
• 根据优先级是否可以动态改变，可将优先级分为静态优先级和动态优先级两种。
  • 静态优先级:创建进程时确定，之后一直不变。
  • 动态优先级:创建进程时有一个初始值，之后会根据情况动态地调整优先级。

合理设置优先级

• 合理高于用户进程
• 前台进程优先级高于后台进程
• 操作系统更偏好l/O型进程（或称IO繁忙型进程）

注：与I/O型进程相对的是计算型进程（或称CPU繁忙型进程）

什么时候跳转优先级？

• 可以从追求公平、提升资源利用率等角度考虑
• 如果某进程在就绪队列中等待了很长时间，则可以适当提升其优先级，如果某进程占用处理机运行了很长时间，则可适当降低其优先级如果发现一个进程
• 频繁地进行l/O操作，则可适当提升其优先级

**算法思想：**对其他调度算法的折中权衡

算法规则：

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

抢占式的算法。在k级队列的进程运行过程中，若更上级的队列(1~k-1级）中进入了一个新进程，则由于新进程处于优先级更高的队列中，因此新进程会抢占处理机，原来运行的进程放回k级队列队尾。

优缺点：

对各类型进程相对公平(FCFS的优点），每个新到达的进程都可以很快就得到响应（RR的优点），短进程只用较少的时间就可完成(SPF的优点），不必实现估计进程的运行时间（避免用户作假），可灵活地调整对各类进程的偏好程度，比如CPU密集型进程、I/O密集型进程（拓展:可以将因I/O而阻塞的进程重新放回原队列，这样/o型进程就可以保持较高优先级)

会产生饥饿 （连续新进程到达，则会导致当前进程饿死）

例子

比起早期的批处理操作系统来说，由于计算机造价大幅降低，因此之后出现的交互式操作系统（包括分时操作系统、实时操作系统等）更注重系统的响应时间、公平性、平衡性等指标。而这几种算法恰好也能较好地满足交互式系统的需求。因此这三种算法适合用于交互式系统。(比如UNIX使用的就是多级反馈队列调度算法)

进程同步：同步亦称直接制约关系，它是指为完成某种任务而建立的两个或多个进程，这些进程因为需要在某些位置上协调它们的工作次序而产生的制约关系。进程间的直接制约关系就是源于它们之间的相互合作。（解决异步的不可预知性）

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

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

临界资源互斥访问，可划分为四个部分：

• 进入区：负责检查是否可进入临界区,若可进入，则应设置正在访问临界资源的标志（可理解为“上锁”)，以阻止其他进程同时进入临界区
• 临界区：访问临界资源的那段代码
• 退出区：负责解除正在访间临界资源的标志（可理解为“解锁”)
• 剩余区：做其他处理

临界资源的互斥访问原则

• 空闲让进。临界区空闲时，可以允许一个请求进入临界区的进程立即进入临界区;
• 忙则等待。当已有进程进入临界区时，其他试图进入临界区的进程必须等待;
• 有限等待。对请求访问的进程，应保证能在有限时间内进入临界区（保证不会饥饿）;
• 让权等待。当进程不能进入临界区时，应立即释放处理机，防止进程忙等待。

算法思想：两个进程在访问完临界区后会把使用临界区的权限转交给另一个进程。也就是说每个进程进入临界区的权限只能被另一个进程赋予

该算法可以实现“同一时刻最多只允许一个进程访问临界区”

单标志法存在的主要问题是：违背“空闲让进”原则。

由于执行顺序一定是P1P2轮流执行，因此P1只要不触发执行，P2一定无法执行！

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

双标志先检查法存在的主要问题是：违背“忙则等待”原则。

第一步和第五步若发生进程切换，则对邻接资源的访问就不互斥了！

原因在于先检查的两句代码不是原子操作！

算法思想：双标志先检查法的改版。前一个算法的问题是先“检查”后“上锁”，但是这两个操作又无法一气呵成，因此导致了两个进程同时进入临界区的问题。因此，人们又想到先“上锁”后“检查”的方法，来避免上述问题。

解决了“忙则等待”的问题，但是又违背了“空闲让进”和“有限等待”

同样第一步和第五步进程切换，就会发生二者都进不去临界区！

算法思想：双标