引论1：操作系统的概念

操作系统的目标

方便性

通过OS命令操作计算机，方便用户

有效性

• 提高系统资源的利用率
• 提高系统吞吐量

可扩充性

• OS必须具有很好的可扩充性
• 与OS的机构有紧密的联系

开放性

• 遵循世界标准规范，特别是开放系统互联OSI

操作系统的作用

用户与计算机硬件系统之间的接口

计算机系系统资源的管理者

1. 处理机管理
2. 存储器管理
3. I/O设备管理
4. 文件管理

实现对计算机资源的抽象

• 裸机：无软件的计算机系统
• 虚拟机：覆盖了软件的机器，向用户提供一个对硬件操作的抽象模型

推动操作系统发展的主要动力

1. 不断提高计算机资源利用率
2. 方便用户
3. 器件的不断更新换代
4. 计算机体系结构的不断发展
5. 不断提出新的应用需求

操作系统的发展过程

单道批处理系统

处理过程

• 作业一个接一个地连续处理
• 旨在提高系统资源利用率和系统吞吐量

缺点

系统资源得不到充分的利用

多道批处理系统

多道程序设计概念

1. 提高资源利用率和吞吐量
2. 多道程序的运行情况

优缺点

1. 资源利用率高
2. 系统吞吐量大
3. 平均周转时间长
4. 无交互能力

单道程序和多道程序运行情况图

多道批处理系统需要解决的问题

1. 处理机争用问题
2. 内存分配和保护问题
3. I/O设备分配问题
4. 文件的组织和管理问题
5. 作业管理问题
6. 用户与系统的接口问题

分时系统

分时系统的引入

用户需要表现在以下几个方面

• 人机叫阿虎(批处理系统做不到)
• 共享主机(感觉独占)

定义

• 分时系统：在一台主机上连接了多个带有显示器的键盘的终端，同时允许多个用户共享主机中的资源，每个用户都可以通过自己的终端以交互方式使用计算机。

分时系统实现的关键问题

最关键的问题是如何使用户能与自己的作业进行交互

• 及时处理(多路卡、命令缓冲区)
• 及时处理
  • 作业直接进入内存
  • 采用轮转运行方式

分时系统的特征

1. 多路性：允许将多态终端同时连接到一台主机，并同时使用
2. 独立性：感觉用户独占主机
3. 及时性：用户的请求能在很短的诗句获得相应(1~3秒)
4. 交互性：用户可通过终端与系统进行广泛的人机用户

实时系统

概念

系统能及时响应外部事件的请求，在规定的时间内完成对该事件的处理，并控制所有实时任务统一协调一致地运行。

最主要的特征：实时性

实时系统类型

1. 工业(武器)控制系统
2. 多媒体系统
3. 信息查询系统
4. 嵌入式系统

实时任务的类型

• 根据任务执行时是否呈现周期性来划分
  • 周期性实时任务、非周期性实时任务
• 根据对截止时间的要求来划分
  • 硬实时任务、软实时任务

实时系统与分时系统的比较

1. 多路性
2. 独立性
3. 及时性
4. 交互性
5. 可靠性

微机操作系统

单用户任务操作系统

CP/M ，MS-DOS

单用户多任务操作系统

Windows 95/98

多用户多任务操作系统

• Solaris OS
• Linux OS
• Windows
• NT/Server

嵌入式操作系统

嵌入式系统

• 为了完成某个功能而设计的系统，或者是有附加机制的系统

  ，或是其他部分的计算机硬件与软件的结合体

• 有实时限制，如响应速度、测量精读、持续时间等

嵌入式OS

用于嵌入式系统的OS

• µC/OS-II、嵌入式Linux、Windows Embedded、VxWorks、Android、iOS等
• 特点：
  • 系统内核小
  • 系统精简
  • 高实时性
  • 具有可配置性

网络操作系统

网络OS概念

• 在计算机网络环境下对网络资源进行管理和而控制，实现数据通信及对网络资源的共享，为用户提供与网络资源接口的一组软件和规章的集合。
• UNIX、Linux、Window Nt/2000/Serve

网络OS的特征

1. 硬件独立性
2. 接口一致性
3. 资源透明性
4. 系统可靠性
5. 执行并行性

网络OS的功能

1. 数据通信
2. 应用互操作
3. 网络管理

分布式操作系统

分布式系统

定义：基于软件实现额一种多处理机系统，是多个处理机通过通信线路互连而构成的松耦合系统。

特征：分布性、透明性、同一性、全局性。

分布式OS

定义：配置在分布式系统上的公用OS

例子：万维网、鸿蒙OS

分布式OS的功能

1. 单处理机OS的主要功能
2. 网络OS所拥有的全部功能
3. 还包括：通信管理功能、资源管理功能、进程管理功能

操作系统的基本特征⭐⭐⭐⭐⭐

1. 并发
2. 共享
3. 虚拟
4. 异步

并发

• 并行性：两个或多个事件再统一时刻发生
• 并发性：两个或多个事件在同一时间间隔内发生
• 引入进程(任务)：动态、并发

共享

系统中的资源科供内存中多个并发执行的进程共同使用

• 互斥共享方式(临界资源)
• 同时访问方式

虚拟

• 时分复用技术：虚拟处理机、虚拟设备
• 空分复用技术：虚拟存储

异步

• 进程的异步性：进程是人们不可预知的速度向前推进的

操作系统的运行环境

1. 指令：CPU执行
2. 执行程序：位于内存
3. 引导程序：位于固件
   • 定位OS内核并将其加载到内存中
4. 事件：硬件中断或软件终端引起
5. 程序：位于外存

操作系统内核

1. 常驻内存，通常与硬件紧密相关
2. 支持功能
   • 中断处理
   • 时钟管理
   • 原语操作
     • 由若干条指令组成，用于完成一定功能
     • 原子操作：要么不做，要么全做，不可分割
3. 资源管理功能
   • 进程管理
   • 存储器管理
   • 设备管理

处理机的双重工作模式⭐

1. 特权指令
2. 内核态
3. 用户态
4. 由硬件提供模式位

特权指令

如果误用，有可能引起系统奔溃的指令

内核态(管态、系统态)

执行包括特权指令在内的一切指令

用户态(目态)

不能执行特权指令

由硬件提供模式位

• 提供了区分系统正在运行用户代码或内核代码的能力
• 系统调用切换运行模式得到内核态，并将调用结果返回给用户。

特权指令和非特权指令⭐

特权指令：在内核态运行的指令

• 不仅能访问用户控件，还能访问系统空间
• 如启动外部设备、设置系统时钟、管中断、切换执行状态、I/O指令

非特权指令：在用户态运行的指令

• 应用程序所使用的都是非特权指令
• 防止应用程序的运行异常对系统造成破坏
• 仅能访问用户空间

用户态和内核态的切换

状态位(Mode bit)的状态表示：

• 内核态(0)
• 用户态(1)

当中断或错误出现，硬件切换至内核态

中断与异常

操作系统是中断驱动的，OS总是在等待某个事件的发生，事件总是由某个中断或异常引起的。

中断(interrupt)

由硬件引起

异常/陷阱(trap)

由软件引起

• 出错(如除数为零活无效的存储访问)
• 用户程序的特定请求(如执行OS的某个服务)

操作系统的主要功能

1. 处理机管理功能
2. 内存管理功能
3. 设备管理功能
4. 文件管理功能
5. 操作系统与用户之间的接口
6. 线代OS的新功能

现代操作系统的新功能

系统安全

1. 认证技术
2. 密码技术
3. 访问控制技术
4. 反病毒技术

网络功能和服务

1. 网络通信
2. 资源管理
3. 应用互操作

支持多媒体

1. 接纳控制技术
2. 实时调度
3. 多媒体文件的存储

引论2：操作系统的设计

简单结构

OS是无结构的，是为数众多的一组过程的集合，内部复杂、混乱，也称整体系统结构

例子：MS-DOS、早起的UNIX

模块化结构

概念

将OS按功能划分为若干个模块，并规定好各模块间的接口，成为“模块”

优点

• 增强OS设计的正确性、可理解性和易维护性
• 增强OS的可适应性
• 加速OS的开发过程

未来

大部分现代OS采用可加载的内核模块来设计

• 内核有一组核心组件，提供核心服务
• 其他服务可在内核运行时动态实现(动态链接)
• 每个组件在需要时内加载到内核
• 例子：Linux、MacOSX、Solaris、Windows

分层式结构

组成

操作系统划分为若干层，在低层上构建高层，高层仅依赖于紧邻它的底层。

• 底层(0层)为硬件
• 最高层(N层)为用户层

优点

1. 易保证系统的准确性
2. 可保证系统的易维护性和可扩充性

缺点

• 系统效率低

例子

THE、Multics

微内核结构

基本概念

• 足够小的内核
• 基于客户/服务器模式
• 应用“机制与策略分离”原理
• 采用面向对象技术

基本功能

1. 进程管理
2. 低级存储器管理
3. 中断和陷入处理

微内核系统优点

1. 提高了系统的可扩展性
2. 增强了系统的可靠性、可移植性
3. 提供了对分布式系统的支持
4. 融入了面向对象技术

微内核系统存在的问题

1. 运行效率有所减低

**主要原因：**在完成一次客户对操作系统提出的服务请求时，需要利用消息实现多次交互和进行用户/内核模型与上下文的多次切换。

例子

Mach OS、Windows 2000/XP

外核结构

基本思想

内核不提供传统的OS中的进程、虚拟存储器等抽象，而是专注于物理资源的隔离(保护)与复用。

系统调用

系统调用目的

使应用程序可以通过它间接调用OS内核中的相关过程，取得相应的服务。

系统调用概念

• 应用程序请求OS内核完成某功能时的一种过程调用
• 用户与内核的接口

与一般过程调用的区别

1. 运行在不同的系统状态
2. 转改的转换
3. 发乎问题
4. 嵌套调用

系统调动的类型

进程控制类

1. 创建和终止进程
2. 获得和设置进程属性
3. 等待某事件出现的系统调用

进程通信类

用于进程之间通信的系统调用

文件操作类

打开和关闭文件、春节和删除文件、读写文件的系统调用

设备管理类

申请设备、释放设备、设备I/O重定向、获得和设置设备属性等系统调用

信息维护类

获得包括有关系统和文件的时间信息、OS版本、当前用户、空闲内存、磁盘等

进程的描述与控制

前趋图与程序执行

程序顺序执行(单处理机)

• 一个较大的程序通常都由若干个程序段组成
• 程序在执行时，必须按照某种先后次序逐个执行，仅当前一操作执行完后，才能执行后续操作

前趋图

• 有向无循环图，用于描述进程之间执行的先后顺序
• 结点表示进程或者程序段，有向边表示前趋关系

程序并发执行

采用多道程序技术，将多个程序同时装入内存，使之并发运行。

前趋关系：

$$I_i->C_i,I_i->I_{i+1},C_1->P_i,C_i->C_{i+1},P_i->P_{i+1}$$

例题：某程序段如下

$$S_1：a:=x+2$$

$$S_2：b:=y+4$$

$$S_3：c:=a+b$$

$$S_4：d:=c+b$$

答：

$$S_1：a:=x+2$$

$$S_2：b:=y+4$$

$$S_3：c:=x+y+6 \quad => \quad S_3=S_1+S_2$$

$$S_4：d:x+2y+10 \quad => \quad S_4=S_2+S_3$$

程序顺序执行和并发执行的特征

顺序执行

• 顺序性
  • 严格按规定的顺序执行
• 封闭性
  • 程序独占全机资源
  • 执行结构不收外界影响
• 可再现性
  • 只要程序执行时的环境和初始条件相同，都可获得相同的结果

并发执行

• 间断性
  • 并发程序之间相互制约
  • 执行—>暂停执行—>执行
• 失去封闭性
  • 多个程序共享全机资源
  • 执行状态收外界因素影响
• 不可再现性
  • 程序经过多次执行后，虽然其执行时的环境和初始条件都相同，但得到的结果却各不相同

进程的描述

几种典型的定义⭐

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

进程定义

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

进程控制块(process control block，也叫PCB)

专门的数据结构，与进程一 一对应

进程的特征⭐

1. 动态性(最基本的特征)
2. 并发性
3. 独立性
4. 异步性

动态性⭐

• 生命期

并发性⭐

• 一段时间同时运行

独立性⭐

• 进程实体是一个独立运行的基本单位
• 是系统中独立获得资源和独立调度的基本单位

异步性⭐

• 按各自独立、不可预知的速度向前推进

进程和程序的区别

1. 进程是程序的一个实例，是程序的一次执行
2. 程序时进程的代码部分
3. 进程是活动的，程序是静止的
4. 进程在内存中，程序在外存中

进程的基本状态和转换⭐

就绪状态

等待被执行的状态

• 一个较大的程序通常都由若干个程序段组成
• 程序在执行时，必须按照某种先后次序诸葛执行，仅当前已操作之心完后，才能执行后续操作

执行状态

已获得CPU，正在执行的状态

• 单处理机：一个进程处于执行状态
• 多处理机：多个进程处于执行状态

阻塞状态

正在执行的进程由于发生某事件而暂时无法继续执行的状态

• 典型事件：请求I/O、申请缓冲空间
• 根据阻塞原因，设置多个阻塞队列

进程状态的转换

创建转改和终止状态

创建状态

1. 申请一个空白PCB
2. 填写PCB
3. 分配资源
4. 设置就绪状态插入就绪队列

终止状态

1. 等待OS善后
2. 收回PCB

状态转换

引入挂起状态的状态转换

挂起操作的引入

1. 终端用户的需要
2. 父进程的需要
3. 负荷调节的需要
4. OS的需要

引入挂起后几种状态转换

• 活动就绪-->精致就绪
• 活动阻塞-->静止阻塞
• 静止就绪-->动就绪
• 静止阻塞-->活动阻塞

进程管理中的数据结构

进程控制块( control block，也叫PCB)⭐⭐

定义⭐

PCB是进程的一部分，是操作系统中最重要的记录型数据结构，是进程存在的唯一标志，常驻内存。

PCB的作用⭐

1. 作为独立运行基本单位的标志
2. 能实现间断性运行方式
3. 提供进程管理所需要的的信息
4. 提供进程调度所需要的信息
5. 实现与其他进程的同步与通信

PCB的信息⭐

1. 进程标识符
2. 处理机状态
3. 进程调度信息
4. 进程控制信息

PCB的组织方式⭐

1. 线性方式
2. 链接方式
3. 索引方式

进程控制

定义

• 进程管理最基本的功能
• 一般由OS内核中的原语实现

其中包括：

1. 进程创建
2. 进程终止
3. 进程阻塞与唤醒
4. 进程挂起与激活

进程创建

1. 进程具有层次结构
2. 引入进程创建的事件
   • 用户登录
   • 作业调度
   • 提供服务
   • 应用请求
3. 进程图
   • 描述进程家族关系的有向树
4. 进程创建过程
   1. 申请空白PCB(进程控制块)
   2. 分配所需资源
   3. 初始化PCB
   4. 插入就绪队列

进程终止

引起进程终止的事件：

1. 正常结束
2. 异常结束
3. 外界干预

进程的终止过程：

1. 根据被终止进程的标识符，从PCB集合中检索出该进程的PCB，从中读出该进程的状态
2. 若被终止进程正处于执行状态，应立即终止该进程的执行，并设置调度标志为真，用于指示该进程被终止后应重新进行调度
3. 若该进程还要子孙进程，还应将其所有子进程予以终止
4. 将该进程所拥有的全部资源，或者归还给其父进程或系统
5. 将被终止进程(PCB)从所在的队列中移去

进程的阻塞与唤醒

1. 引起进程阻塞和唤醒的事件

   1. 向系统请求共享资源失败
   2. 等待某种操作的完成
   3. 新数据尚未到达
   4. 等待新任务的到达

2. 进程阻塞过程

   • 阻塞原语Block()
   • 进程的阻塞是进程吱声的一种主动欣慰
   • 具体过程：停止执行->状态由执行改为阻塞->将PCB插入到阻塞队列

3. 进程唤醒过程

   • 唤醒原语Wakeup()
   • 具体过程：从阻塞队列中移出->状态有阻塞改为就绪->将PCB插入就绪队列
   • 必须成对使用Block和Wakeup原语

进程的挂起与激活

进程的挂起

• Suspend()原语
• 执行过程

进程的激活过程

• Active()原语
• 执行过程

进程的通信与线程

进程通信

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

**低级进程通信：**进程的同步与互斥

• 效率低
• 通信对用户不透明

高级进程通信：

• 使用方便
• 高效地传输大量数据

进程的通信类型

共享存储器系统

• 基于共享数据结构的通信方式（效率低）
• 基于共享存储区的通信方式（高级）

管道通信

• 管道：用于连接一个读进程和一个写进程以实现它们之间通信的一个共享文件，又名pipe文件
• 管道机制的协调能力：互斥、同步、对方是否存在

消息传递系统

• 直接通信方式
• 简洁通信方式（通过邮箱）

客户机-服务器系统

• 套接字（Socket）
• 远程过程调用（RPC）和远程方法调用（RMI、Java）

消息传递通信的实现方式

直接通信方式

• 发送原语：send(receiver , message)
• 接收原语：receive(sender , message)

间接通信方式：通过信箱来完成

• 信箱结构
• 消息的发送和接收
• 发送原语：sned(mailbox , message)
• 接收原语：receive(mailbox , message)
• 信箱类型
  • 使用邮箱、公共邮箱、共享邮箱

Linux进程通信方式

1. 管道
2. 信号
3. 消息队列
4. 共享内存
5. 信号量
6. 套接字

管道的实例

无名管道的实例：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32

#define INPUT 0
#define OUTPUT 1
void main()
{
	int file_descriptors[2];
	pid_t pid; /*定义子进程号*/
	char buf[256];
	int returned_count;
	pipe(file_descriptors); /*创建无名管道*/
	if ((pid = fork()) == -1)
	{ /*创建子进程*/
		printf("Error in fork/n");
		exit(1);
	}
	if (pid == 0)
	{ /*执行子进程*/
		printf("in the spawned (child) process.../n");
		/*子进程向父进程写数据，关闭管道的读端*/
		close(file_descriptors[INPUT]);
		write(file_descriptors[OUTPUT], "test data", strlen("test data"));
		exit(0);
	}
	else
	{ /*执行父进程*/
		printf("in the spawning (parent) process.../n");
		/*父进程从管道读取子进程写的数据，关闭管道的写端*/
		close(file_descriptors[OUTPUT]);
		returned_count = read(file_descriptors[INPUT],
							  buf, sizeof(buf));
		printf("%d bytes of data received from spawned process: %s/n", returned_count, buf);
	}
}

有名管道实例：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26

#include <stdio.h>
#include <unistd.h>
void main()
{
	FILE *in_file, *out_file;
	int count = 1;
	char buf[80];
	in_file = fopen("mypipe", "r"); /*读有名管道*/
	if (in_file == NULL)
	{
		printf("Error in fdopen./n");
		exit(1);
	}
	while ((count = fread(buf, 1, 80, in_file)) > 0)
		printf("received from pipe: %s/n", buf);
	fclose(in_file);
	out_file = fopen("mypipe", "w"); /*写有名管道*/
	if (out_file == NULL)
	{
		printf("Error in fdopen./n");
		exit(1);
	}
	sprintf(buf, "this is test data for the named pipe example./n");
	fwrite(buf, 1, 80, out_file);
	fclose(out_file);
}

线程的概念

提出时间

60年代中期：提出线程概念

80年代中期：提出线程概念

90年代后：多处理机系统引入线程

引入线程的目的

• 使多个程序并发执行
• 提高资源利用率及系统吞吐量

线程的两个基本属性：⭐

1. 线程是一个可拥资源的独立单位
2. 进程是一个可独立调度和分派的基本单位

提出线程的目的

1. 减少程序在并发执行时所付出的时空开销
2. 使OS具有更好的并发性
3. 使用于SMP结构的计算机系统

进程是拥有资源的基本单位（传统进程称为重型进程）

线程作为调度和分派的基本单位（又称为轻型进程））

线程与进程的比较

调度的基本单位

• 在传统的OS中，拥有资源、独立调度和分派的基本单位都是进程
• 在引入线程的OS中，线程作为调度和分派的基本单位，进程作为资源拥有的基本单位
• 在同一进程中，线程的切换不会引起进程切换，在由一个进程中的线程切换到另一个进程中的线程时，将会引起进程切换

并发性

• 在引入线程的操作系统中会，不仅进程之间可用并发执行，而且在一个进程中的多个线程之间，也可以并发执行。

拥有资源

• 进程是系统中有用资源的一个基本单位，它可以拥有资源
• 线程本身不拥有系统资源，仅有的一点保证独立运行的资源
• 允许多个线程共享其隶属进程所拥有的资源

独立性⭐

• 同一进程中的不同线程之间的独立性要比不同进程之间的独立低得多

系统开销

• 在创建或撤销进程时，OS所付出的开销将显著大于创建或撤销进程时的开销
• 线程切换的代价远低于进程切换的代价

支持多处理机系统

线程状态

• 执行态
• 就绪态
• 阻塞态

线程控制块（Thread Control Block ，TCB）

• 线程标识符、一组寄存器、线程运行状态、优先级、线程转悠存储区、信号屏蔽、堆栈指针

线程的实现

实现方式

1. 内核支持线程KST
2. 用户级线程ULT
3. 组合方式

具体实现

1. 内核支持线程的实现（利用系统调用）
2. 用户级线程的实现（借助中间系统）

内核支持线程LST

在内核空间实心

优点

1. 在多处理机系统中，内核可同时调度同一进程的多个线程
2. 如同一线程阻塞了，内核可调度其他线程(同一或其他进程)
3. 线程的切换比较快，开销小
4. 内核本身可采用多线程技术，提高执行速度和效率

缺点

• 对用户线程切换，开销较大

用户级线程ULT

在用户空间实现

优点

1. 线程切换不需要转换到内核空间
2. 调度算法可以是进程专用
3. 线程的实现与OS平台无关

缺点

1. 系统调度的阻塞问题
2. 多线程应用不能利用多处理机进行多重处理的优点

线程的创建与终止

如同线程一样，线程也是有生命期，由创建而产生、由终止而消亡。在OS中，由用于创建线程的函数（或系统调用）和用于终止线程的函数（或系统调用）

线程的创建

• 应用程序启动时，由“初始化线程”创建新线程

线程的终止

• 由终止线程通过调用相应的函数（或系统调用）对他执行终止操作
• 有些线程（系统线程）一旦被简历起来之后，便会一直运行下去而不被终止
• 只有当线程中的其他线程执行了分离函数，被终止的线程才会与资源分离

处理机调度与死锁

处理机调度概述

处理机调度是对处理机进行分配，调度的实质是一种资源分配处理机调度算法是指根据处理机分配策略所规定的处理机分配算法。

处理机调度的层次

1. 高级调度（长城调度/作业调度）
2. 中级调度（中程调度/内存调度）
3. 低级调度（短程调度/进程调度）

高级调度

调度对象：作业

根据某种算法，决定将外存上处于后备队列中的作业调入内存，并未它们创建进程和分配必要的资源。然后，将创建的进程排在就绪队列上等待调度。

主要用与多道批处理系统中

中级调度

调度对象：内存

• 将暂不运行的进程，调至3外存等待
• 将处于外存上的继续运行的进程，调入内存运行
• 即“对换”功能

低级调度

• 调度对象：进程

• 根据某种调度算法，决定就绪队列中的哪个进程应获得处理机

• 应用在于躲到批处理、分时和实时OS

进程调度的任务和方式

进程调度的任务

1. 保存处理机的现场信息
2. 按目中算法选取进程
3. 把处理器分配给进程

进程调度机制（调度程序分为三部分）

• 排队器：用于将就绪进程插入相应的就绪队列
• 分派器：用于将选定的进程移出就绪队列
• 上下文切换器：进程新旧进程之间的上下切换

进程调度方式

抢占方式

允许调度程序根据某种规则，去暂停某个正在执行的进程，将已分配的给该进程的处理机重新分配给另一进程。(现代OS广泛使用)

1. 优先权原则：允许优先权高的新到进程抢占当前进程的处理机
2. 短作业优先原则：短作业可以抢占当前较长作业的处理机
3. 时间片原则：各进程按时间片运行，当一个时间片用完后，便停止该进程的执行而重新进行调度

非抢占方式

一旦把处理机分配到某进程后，便让该进程一直执行，直到该进程完成或发生某事件而被阻塞时，才再把处理机分配给其他进程，决不允许某进程抢占已经分配出去的处理机。

处理机调度算法的目标

共同目标

1. 资源利用率
2. 公平性
3. 平衡性
4. 策略强制执行

批处理系统的目标

平均周期时间短、系统吞吐量高、处理机利用率高

分时系统的目标

响应事假快、均衡性

实时系统的目标

截止时间的保证、可预测性

$$\text{CPU利用率}=\frac{\text{CPU有效工作时间}}{\text{CPU有效工作时间+CPU空闲等待时间}}$$

评价指标

周转时间

周转时间=完成时间-到达时间，一般在计算周转时间，该进程的等待时间和进程切换时间开销也算入周转时间。

从作业提交给系统开始，到作业完成为止的这段时间间隔

• 平均周转时间计算

$$T=\frac{1}{n}\left ( \sum_{i=1}^{n}T_i \right )$$

• 带权周转时间：权值为作业周转时间T与系统为之服务时间Ts之比
• 平均带权周转时间

$$W=\frac{1}{n}(\sum_{i=1}^{n}\frac{T_i}{T_S}_i ) \\\\ \text{带权周转时间}= \frac{\text{周转时间}}{\text{运行时间}} \\\\ \text{平均带权周转时间}= \frac{\text{各个周转时间之和}}{\text{进程个数}}$$

响应时间

从用户通过键盘提交请求开始，直到系统首次显示出结果为止的一段时间

等待时间(进程调度)

进程在就绪队列中等待调度的所有时间之和

调度算法

1. 先来先服务调度算法(FCFS)
2. 短作业优先调度算法(SJF)
3. 优先级调度算法(PR)
4. 高响应比优先调度算法(HRRN)

FCFS、SJF、PR即可用于作业调度，也可以用于进程调度。

进程调度算法

进程常见调度算法有7种。

1. 先来先服务调度算法(FCFS)
2. 短作业优先调度算法(SJF)
3. 优先权调度算法(PR)
4. 时间片轮转调度算法(RR)
5. 多级队列调度算法
6. 多级反馈队列调度算法
7. 基于公平原则的调度算法

先来先服务调度算法(FCFS)

例题1：

答：

要算平均周转时间，先算单个J1~J3的周转时间，再除以进程个数即可。

周转时间=完成时间(结束时间)-到达时间(或者叫提交时间)，如上甘特图中

J1的周转时间为24，J2的周转时间为27，J3的周转时间为30。

虽然有部分的进程是在等待执行，还没开始执行，但该进程已经到达了，已经算入周转时间内了，如果某个进程还有等待时间，则该进程的周转时间还应该将等待时间算入内。

$$\text{平均等待时间}=\frac{(0+24+27)}{3}=17 \\ \text{根据公式} \quad T=\frac{1}{n}\left ( \sum_{i=1}^{n}T_i \right ) \quad \text{得：} \\ \text{平均周转时间}=\frac{(24+27+30)}{3}=27$$

例题2：

$$\text{平均等待时间}=\frac{(0+3+6)}{3}=3 \\ \text{根据公式} \quad T=\frac{1}{n}\left ( \sum_{i=1}^{n}T_i \right ) \quad \text{得：} \\ \text{平均周转时间}=\frac{(3+6+30)}{3}=13$$

短作业优先(SJF)调度算法

SJF算法：即可用于作业、也可用于进程

• 对作业：从后备队列中选择若干个估计运行时间最短的作业
• 对进程：关联到每个进程下次运行的CPU区间长度，调度最短的进程

对进程调度，SJF有两种模式

• 非抢占式SJF
• 抢占式SJF–>抢占发生在有比当前进程剩余时间片更短的进程到达时，也称为最短剩余时间优先调度

SJF是最优的，（对一组指定的进程而言），它给出了最短的平均等待时间。

非抢占式SJF例题1

答：

$$\text{平均等待时间}=\frac{(0+6+3+7)}{4}=4 \\ \text{根据公式} \quad T=\frac{1}{n}\left ( \sum_{i=1}^{n}T_i \right ) \quad \text{得：} \\ \text{平均周转时间}=\frac{(7+10+4+11)}{4}=8$$

1. 执行顺序：根据题目给的执行算法，本题是根据短作业优先，也就是运行时间最短先执行，但J1的到达时间是0.0，则第一个开始，之后开始从最短时间开始执行。

2. 每一次的结束时间既是下一次的开始时间，如果有进程切换时间或者作业切换时间间隔，则需要加上这个间隔。

3. 结束时间= 开始时间+运行时间

4. 周转时间= 结束时间-到达时间

5. 带权周转时间 = 周转时间÷运行时间

平均周转时间= 各周转时间之和除以进程数即可

抢占式SJF例题2

$$\text{平均等待时间}=\frac{(9+1+0+2)}{4}=3 \\ \text{根据公式} \quad T=\frac{1}{n}\left ( \sum_{i=1}^{n}T_i \right ) \quad \text{得：} \\ \text{平均周转时间}=\frac{(16+5+1+6)}{4}=7$$

缺点

1. 只能估算进程的运行时间（估值不准确），所以通常用于作业调度
2. 对长作业不利
3. 采用SJF算法时，人-机无法实现交互
4. 完全未考虑作业的紧迫程度

SJF比FCFS算法有明显改进

优先级调度算法PR

• 既可用于作业调度，又可用于进程调度
• 基于作业/进程的紧迫程度，由外部赋予作业相应的优先级，调度算法根据优先级进行调度
  • 每个进程都有一个优先数，优先数为整数
  • 默认：小的优先数具有优先级
  • ``目前主流的操作系统调度算法`
• 高响应比优先调度算法是一种优先级调度算法，用于作业调度

进程优先级调度算法

1. 优先级调度算法的类型

• 非抢占式
• 抢占式

2. 优先级类型

• 静态优先级
  • 创建进程时确定优先数(整数)，在进程的整个运行期间保持不变
  • 简单易行，系统开销小
  • 不够精确，可能会出现优先级低的进程长期没有被调度的情况
• 动态优先级
  • 创建进程时先赋予其一个优先级，然后其值随进程的推进或等待时间的增加而改变

非抢占式优先级调度算法例题

答：

要算平均周转时间，先算单个P1~P5的周转时间，再除以进程个数即可。

周转时间=完成时间-到达时间，如上甘特图中

P1的周转时间为16，P2的周转时间为1，P3的周转时间为18，P4的周转时间为19，P5的周转时间为1.

虽然有部分的进程是在等待执行，还没开始执行，但该进程已经到达了，已经算入周转时间内了，如果某个进程还有等待时间，则该进程的周转时间还应该将等待时间算入内。

$$\text{平均等待时间}=\frac{(6+0+16+18+1)}{5}=8.2 \\ \text{平均周转时间}=\frac{(16+1+18+19+6)}{5}=12$$

优先级调度算法的优缺点

优点

1. 实现简单，考虑了进程的紧迫程度
2. 灵活，可模拟其他算法

存在问题

饥饿——低优先级的进程可能永远得不到运行

解决问题

老化——视进程等待时间的延长提高其优先数

高响应比优先级调度算法（PR的特例）

• 既考虑作业的等到时间，又考虑作业的运行时间
• 优先级：

$$\text{优先级}=\frac{\text{等待时间+要求服务时间}}{\text{要求服务时间}}$$

• 响应比：

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

• 如等待时间相同，运行时间越短，类似于SJF
• 如运行时间相同，取决于等待时间，类似于FCFS
• 长作业可随其等待时间的增加而提高，也可得到服务
• 缺点：每次调度之前，都需要计算响应比，增加系统开销

时间片轮转（RR）调度算法

• 转为分时系统设计，类似于FCFS，但增加了抢占
• 时间片：小单位的CPU时间，通常为10~100毫秒
• 为每个进程分配不超过一个时间分的COU。时间片用完后，该进程将被抢占并插入就绪队列末尾，循环执行
• 嘉定就绪队列中有n个进程、时间片为q，则每个进程每次得到1/n的、不超过q单位的成块CPU时间，没有任何一个进程的等待时间会超过（n-1）q单位

时间片为20的RR例子

$$\text{平均等待时间}=\frac{(57+20+64+80)}{4}=55.25 \\ \text{平均周转时间}=\frac{(0+20+37+57)}{4}=28.5 \\ \text{通常，RR的平均周转时间比SJF长，但响应时间要短一些}$$

特性

• q大：FCFS
• q小：增加上下文切换时间

时间片设置应考虑

• 系统对响应时间的要求
• 就绪队列中进程的数目
• 系统的处理能力

一般准则：时间片/10 > 进程上下文切换时间

重点

填空题

1. 一次仅允许一个进程使用的资源叫__临界资源__，一个进程访问这类资源的代码叫__临界区__
2. 在采用多道程序设计技术的系统汇总，用户编写程序时使用对的地址是__逻辑地址__，在装入内存后的地址为__物理地址__，这种地址转换的过程叫做__重定位__。
3. 如果信号量的当前值为-2，则表示系统中在该信号量上有__2__个等待进程。
4. 设有四个作业同时到达，每个作业的执行时间均为2小时，它们在一台处理机上按单道方式运行，平均周转时间为__5__小时。(2+4+6+8)/4=5

计算题-模拟

求平均周转时间 & 平均带权周转时间

计算模板

假设进程都在时刻2开始。

例题-1

假定要在一台处理机上执行下表所示的作业，且假定这些作业在时刻0以1,2,3,4,5的顺序到达。请说明分别采用FCFS、RR（时间片为1）、SJF及非抢占式优先级调度算法时，这些作业的执行情况（优先级的高低顺序依次为1到5）。针对上述每种调度算法，给出平均周转时间和平均带权周转时间。

答：

判断题

2018-2019

2019-2020

问答题

2018-2019

2019-2020

计算题

2018-2019

2019-2020