操作系统复习整理

使用说明

多关注最后的总结部分

上面的是知识点整理

不会的知识点用Ctrl+F查找

绪论

操作系统目标和作用

计算机系统的组成

硬件系统（裸机）：CPU、存储器（主存、辅存）、输入/输出设备等

软件系统：系统软件、应用软件

系统软件：管理计算机本身的操作。如操作系统、编译…

应用软件：提供给用户进行解题。如科学计算、事物管理…

操作系统定义

操作系统是计算机系统中的一个系统软件，是一些程序模块的集合——它们能以尽量有效、合理的方式组织和管理计算机的软硬件资源，合理地组织计算机的工作流程，控制程序的执行并向用户提供各种服务功能，使得用户能够灵活、方便、有效地使用计算机，使整个计算机系统能高效地运行，从而在计算机与用户之间起到接口的作用

计算机系统层次结构

计算机系统由硬件和软件组成

操作系统是在硬件基础上的第一层软件

操作系统是其他软件和硬件之间的接口

操作系统目标

有效性

改善资源利用率，提高系统吞吐量

方便性

使计算机系统使用起来更方便

可扩充性

能够不断适应发展的要求

开放性

使来自不同厂家的计算机和设备能够有效地协同工作，实现应用的可移植性和互操作性

操作系统作用

OS作为用户与计算机硬件之间的接口

OS处于用户和计算机硬件系统之间，用户通过OS使用计算机系统

用户可以通过命令方式、系统调用方式和图形、窗口方式使用计算机

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

处理机管理：用于分配和控制处理机

存储器管理：主要负责内存的分配与回收

I/O设备管理：负责I/O设备的分配与操纵

文件管理：负责文件的存取、共享和保护

OS实现了对计算机资源的抽象

当计算机上覆盖了操作系统后，便为用户提供了一台功能显著增强，使用更加方便，效率明显提高的虚拟计算机

操作系统发展过程

发展动力

不断提高计算机资源利用率

方便用户

器件的不断更新换代

计算机体系结构的不断发展

不断提出新的应用需求

未配置操作系统的计算机系统

人工操作方式：缺点：用户独占全机，CPU等待人工操作

脱机输入/输出方式：优点：减少了CPU的空闲时间，提高I/O速度

单道批处理系统

一批作业脱机方式存到磁带，由监督程序控制逐个装入内存运行

单道批处理特征

自动性

顺序性

单道性

单道批处理缺点

主要缺点：系统中的资源不能充分利用

程序在运行中发出I/O请求后，CPU便处于等待状态，必须在其 I/O完成后才继续运行

多道批处理系统

在内存中同时存在多道用户作业，他们共享CPU和系统中的各种资源

多道批处理特征

多道性

无序性

调度性

（与单道对比：自动性，顺序性，单道性）

多道批处理好处

提高CPU的利用率

提高内存和I/O设备的利用率

增加系统吞吐量

多道批处理优缺点

优点

资源利用率高

系统吞吐量大

缺点

平均周转时间长

无交互能力

分时系统

指在一台主机上连接了多个带有显示器和键盘的终端，同时允许多个用户通过自己的终端，以交互方式使用计算机时间片，然后交由下个用户使用，共享主机中的资源

分时系统关键问题

及时接收

及时处理

分时系统特征

多路性

独立性

及时性

交互性

实时系统

实时系统(Real-Time System)是指系统能及时(或即时)响应外部事件的请求，在规定的时间内完成对该事件的处理，并控制所有实时任务协调一致地运行

实时系统类型

工业控制系统

信息查询系统

多媒体系统

嵌入式系统

操作系统基本特征

并发性

区分“并行”和“并发”

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

并发性是指两个或多个事件在同一时间间隔内发生（间隔极短）

共享性

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

虚拟性

把一个物理实体变为若干个逻辑上的对应物

如把一块磁盘分为C, D, E三个盘

异步性

进程是以人们不可预知的速度向前推进，此即进程的异步性

走走停停

操作系统主要功能

处理机管理功能

进程控制

进程同步

进程通信

调度

存储器管理功能

内存分配

内存保护

地址映射

内存扩充

设备管理功能

缓冲管理

设备分配

设备处理

文件管理功能

文件存储空间管理

目录管理

文件的读/写管理和保护

操作系统与用户之间的接口

用户接口（联机用户接口、脱机用户接口、图形用户接口）

程序接口

OS结构设计

软件，是指当计算机运行时，能提供所要求的功能和性能的指令和程序的集合，该程序能够正确地处理信息的数据结构，还应具有描述程序功能需求以及程序如何操作使用的文档

无结构操作系统

模块化OS结构

模块化OS优点

提高了OS设计的正确性、 可理解性和可维护性

增强了OS的可适应性

加速了OS的开发过程

模块化OS缺点

对模块的划分及对接口的规定并不精确，使在把这些模块装配成OS时发生困难

使模块间存在着复杂的依赖关系使OS结构变得不清晰

分层式OS结构

基本原则是：每一层都仅使用其底层所提供的功能和服务，使系统的调试和验证都变得容易

分层OS优缺点

优点：

易保证系统的正确性

易扩充和易维护性

缺点：

系统效率降低

微内核OS结构

微内核的基本功能

进程（线程）管理

低级存储器管理

中断和陷入处理

微内核操作系统的优点

提高了系统的可扩展性

增强了系统的可靠性

可移植性

提供了对分布式系统的支持

融入了面向对象技术

进程的描述与控制

前趋图和程序执行

在早期未配置OS的系统和单道批处理系统中，程序的执行方式是顺序执行，即在内存中仅装入一道用户程序，由它独占系统中的所有资源，只有在一个用户程序执行完成后，才允许装入另一个程序并执行

前驱图

描述一个程序的各部分（程序段或语句）间的依赖关系，或者是一个大的计算的各个子任务间的因果关系

前趋图中的每个结点可以表示一条语句、一个程序段或一个进程

前驱图中不能存在循环

程序的顺序执行

顺序执行

顺序执行的特征

顺序性

一个程序的各个部分的执行，严格地按照某种先后次序执行

封闭性

程序在封闭的环境下运行，即程序运行时独占全部系统资源，资源的状态(除初始状态外)只有本程序才能改变它，程序一旦开始执行，其执行结果不受外界因素影响

可再现性

只要程序执行时的环境和初始条件相同，当程序重复执行时，不论它是从头到尾不停顿地执行，还是“停停走走”地执行，都将获得相同的结果

程序的并发执行

并发执行

并发执行的特征

间断性

程序并发执行时，由于它们共享资源或程序之间相互合作完成一项共同任务，因而使程序之间相互制约

并发程序具有“执行—暂停—执行”

失去封闭性

程序在并发执行时，是多个程序共享系统中的各种资源，因而这些资源的状态将由多个程序来改变，致使程序的运行失去了封闭性

不可再现性

由于程序的并发执行，打破了由另一程序独占系统资源的封闭性，因而破坏了可再现性

进程的描述

进程的定义

进程是程序的一次执行，该程序可以与其它程序并发执行

进程的组成

PCB

程序段

数据段

进程的特征

动态性

进程的实质是程序的一次执行过程，因此，动态特征是进程最重要的特征

并发性

没有为之建立进程的程序是不能并发执行的，仅当为之建立一个进程后才能参加并发执行

独立性

进程是一个能独立运行的基本单位，同时也是系统分配资源和调度的独立单位

异步性

由于进程间的相互制约，使进程具有执行的间断性，即进程按各自独立的、不可预知的速度向前推进

结构特征

为了控制和管理进程，系统为每个进程设立一个进程控制块——PCB

进程与程序的区别

程序是进程的静态文本，进程是执行程序的动态过程

一个进程可以执行一个或多个程序，几个进程可以同时执行一个程序

程序可作为软件资源长期保存，进程只是一次执行过程，是暂时的，不能长期保存

进程是系统分配调度的独立单位，能与其他进程并发执行

进程基本状态及转换

进程的三种基本状态

就绪状态(Ready)

无CPU，有其他所需资源

执行状态(Running)

有CPU，有其他所需资源

阻塞状态(Block)

无CPU，无其他所需资源

进程的创建和终止状态

创建状态

创建一个进程是个很复杂的过程，一般要通过多个步骤才能完成

首先由进程申请一个空白PCB，并向PCB中填写用于控制和管理进程的信息

然后为该进程分配运行时所必须的资源

最后，把该进程转入就绪状态并插入就绪队列之中

但如果进程所需的资源尚不能得到满足，比如系统尚无足够的内存使进程无法装入其中，此时创建工作尚未完成，进程不能被调度运行，于是把此时进程所处的状态称为创建状态

终止状态

进程的终止也要通过两个步骤

首先，是等待操作系统进行善后处理

最后将其PCB清零，并将PCB空间返还系统

当一个进程到达了自然结束点，或是出现了无法克服的错误，或是被操作系统所终结，或是被其他有终止权的进程所终结，它将进入终止状态

进程状态的转换

进程在运行过程中会经常发生状态的转换

处于就绪状态的进程，在调度程序为之分配了处理机之后便可执行，相应地，其状态就由就绪态转变为执行态

正在执行的进程(当前进程)如果因分配给它的时间片已完而被剥夺处理机暂停执行时，其状态便由执行转为就绪

如果因发生某事件，致使当前进程的执行受阻(例如进程访问某临界资源，而该资源正被其它进程访问时)，使之无法继续执行，则该进程状态将由执行转变为阻塞

三种基本状态的转变：

阻塞不能直接执行

只有就绪和执行是双向箭头

五种状态的转变：

挂起操作

引入挂起状态的原因

终端用户的请求

父进程请求

负荷调节的需要

操作系统的需要

引入挂起原语操作后三个进程状态的转换

在引入挂起原语Suspend和激活原语Active后，进程将可能发生以下几种状态的转换

活动就绪→静止就绪

活动阻塞→静止阻塞

静止就绪→活动就绪

静止阻塞→活动阻塞

进程控制中的数据管理

操作系统中用于管理控制的数据结构

在计算机系统中，对于每个资源和每个进程都设置了一个数据结构，用于表征其实体，我们称之为资源信息表或进程信息表

其中包含了资源或进程的标识、描述、状态等信息以及一批指针

OS管理的这些数据结构一般分为以下四类：内存表、设备表、文件表和用于进程管理的进程表

通常进程表又被称为进程控制块PCB

进程控制块PCB

\(\color{red}{PCB是进程存在的唯一标志}\)

PCB作用

作为独立运行基本单位的标志

能实现间断性运行方式

提供进程管理所需要的信息

提供进程调度所需要的信息

实现与其它进程的同步与通信

PCB中的信息

在进程控制块中，主要包括下述四个方面的信息

进程标识符

进程标识符用于唯一地标识一个进程

外部标识符：方便用户对进程访问

内部标识符：方便系统对进程的使用

处理机状态

处理机状态信息也称为处理机的上下文，主要是由处理机的各种寄存器中的内容组成的

进程调度信息

进程状态：作为进程调度和对换时的依据

进程优先级

进程调度所需的其它信息

事件：阻塞原因

进程控制信息

用于进程控制所必须的信息

程序和数据的地址

进程同步和通信机制：消息队列指针、信号量

资源清单：除CPU以外，进程在运行期间所需的全部资源

链接指针：本进程(PCB)所在队列中的下一个进程的PCB的首地址

进程控制块的组织方式

(串讲中强调三遍)

线性方式

将系统中所有的PCB都组织在一张线性表中

将该表的首址存放在内存的一个专用区域中

适合进程数目不多的系统

链接方式

即把具有相同状态进程的PCB分别通过PCB中的链接字链接成一个队列

索引方式

进程控制

进程控制是进程管理中最基本的功能

主要包括创建新进程、终止已完成的进程、将因发生异常情况而无法继续运行的进程置于阻塞状态、负责进程运行中的状态转换等功能

进程控制一般是由OS的内核中的原语来实现

操作系统内核

现代操作系统一般将OS划分为若干层次，再将OS的不同功能分别设置在不同的层次中

通常将一些与硬件紧密相关的模块（中断处理程序等）、各种常用的设备驱动程序以及运行频率较高的模块（时钟管理、进程调度等），都安排在紧靠硬件的层次中，将它们常驻内存，即通常被称为OS内核

OS内核功能

支撑功能

中断处理：中断处理是内核最基本的功能，是整个OS赖以活动的基础

时钟管理

原语操作

资源管理功能

进程管理

存储器管理

设备管理

进程创建

进程的层次

在OS中，允许一个进程创建另一个进程

通常把创建进程的进程称为父进程，而把被创建的进程称为子进程（进程的家族关系）

进程图

进程图就是用于描述进程间关系的一棵有向树

进程图和前驱图的差异

前趋图描述的是任务（或进程）之间的前趋关系；只有在前趋进程完成后，其后继进程才能运行

在进程图中，创建者和被创建者可以并发执行，也可以是父进程等待其所有的子进程结束后再执行，这完全取决于创建原语和创建者的需要

引起创建进程的事件

用户登录

作业调度

提供服务

应用请求

进程的创建

在系统中每当出现了创建新进程的请求后，OS便调用进程创建原语Creat创建一个新进程

创建原语

功能：创建一个具有指定标识符的进程

入口信息：进程标识符、优先级、进程开 始地址、初始CPU状态、资源清单等

进程创建过程

申请空白PCB

为新进程分配资源

初始化进程控制块

将新进程插入就绪队列，如果进程就绪队列能够接纳新进程， 便将新进程插入就绪队列

进程终止

引起进程终止的事件

正常结束

异常结束

外界干预

进程的终止

如果系统中发生了要求终止进程的某事件，OS便调用进程终止原语去终止指定的进程

终止原语

功能：撤消一个指定的进程

入口信息：被撤消的进程名

进程终止过程

根据被终止进程的标识符，从PCB集合中检索出该进程的PCB，从中读出该进程的状态

若被终止进程正处于执行状态，应立即终止该进程的执行，并置调度标志为真，用于指示该进程被终止后应重新进行调度

若该进程还有子孙进程，还应将其所有子孙进程予以终止，以防他们成为不可控的进程

将被终止进程所拥有的全部资源，或者归还给其父进程，或者归还给系统

将被终止进程(它的PCB)从所在队列(或链表)中移出，等待其他程序来搜集信息

进程的阻塞和唤醒

引起进程阻塞与唤醒的事件

向系统请求共享资源失败：当资源满足时，请求进程才被唤醒

等待某种操作完成：当该操作完成后将其唤醒

新数据尚未到达：所需数据到达后将其唤醒

等待新任务的到达

进程的阻塞

正在执行的进程，如果发生了上述某事件，进程便通过调用阻塞原语block将自己阻塞

阻塞原语

阻塞原语（block）

功能：停止调用进程的执行，变为等待

入口信息：可省

进程阻塞过程

进入block过程后，由于该进程还处于执行状态，所以应先立即停止执行

把进程控制块中的现行状态由“执行”改为阻塞，并将PCB插入阻塞队列

如果系统中设置了因不同事件而阻塞的多个阻塞队列，则应将本进程插入到具有相同事件的阻塞队列

进程的唤醒

唤醒原语

唤醒原语（wakeup）

功能：唤醒某一处于等待队列当中的进程

入口信息：被唤醒进程的名字

进程唤醒过程

wakeup执行的过程是：首先把被阻塞的进程从等待该事件的阻塞队列中移出，将其PCB中的现行状态由阻塞改为就绪，然后再将该PCB插入到就绪队列中

进程的挂起与激活

挂起原语

挂起原语（suspend）

功能：自身挂起、挂起具有指定标识符的进程、将其进程及其全部或部分“子孙”挂起

激活原语

激活原语（Active）

功能：使处于静止状态的进程变为活动

进程同步

在多道程序系统中，由于资源共享或进程合作，使进程间形成间接相互制约和直接相互制约关系

这需要用进程互斥与同步机制来协调两种制约关系

我们期望进程并发的时候按我们期望的顺序、资源使用方式进行

进程同步基本概念

两种制约关系

互斥

间接相互制约关系（进程—资源—进程）→进程的互斥

同步

直接相互制约关系（进程—进程）→进程的同步

即让各并发进程按要求有序推进

临界资源

虽然在多道程序系统中的诸进程可以共享各类资源

然而临界资源却是一次只能供一个进程使用，使用完后归还系统，才能给其他进程使用

临界区

进程对临界资源必须互斥使用，为实现对临界资源的互斥访问，应保证诸进程互斥地进入自己的临界区

把每个进程中访问临界资源的那段代码称为临界区

为此，每个进程在进入其临界区前，必须先申请，经允许后方能进入

同步机制应遵循的准则

空闲让进

当无进程处于临界区内时，必须让一个要求进入临界区的进程立即进入，以有效地利用临界资源

忙则等待

当已有进程处于临界区内时，其它试图进入临界区的进程必须等待，以保证它们互斥地进入临界区

有限等待

对要求进入临界区的进程，应在有限时间内使之进入，以免陷入“死等”

让权等待

对于等待进入临界区的进程而言，它必须立即释放处理机，以免进程“忙等”

硬件同步机制

关中断

实现互斥的最简单的方法之一

缺点

滥用关中断权力可能导致严重后果

关中断时间过长，会影响系统效率，限制了处理器交叉执行程序的能力

关中断方法也不适用于多CPU 系统，因为在一个处理器上关中断并不能防止进程在其它处理器上执行相同的临界段代码

利用Test-and-Set指令实现互斥

利用Swap指令实现进程互斥

信号量机制

按用途不同，信号量分为整形信号量和记录型信号量

整形信号量

Dijkstra把整型信号量定义为一个用于表示资源数目的整型量S，它与一般整型量不同

除初始化外，仅能通过两个标准的原子操作(Atomic Operation): wait(S)和signal(S)来访问

两个操作一直被分别称为P、V操作

S：互斥资源量

P：申请资源

V：释放资源

P操作

意味着请求分配一个单位资源

P(S)

① \(S∶=S-1\)；

②若\(S\ge 0\)，则调用\(P(S)\)的进程继续运行；

③若\(S<0\)，则调用\(P(S)\)的进程被阻塞，并把它插入到等待信号量\(S\)的阻塞队列中

V操作

意味着释放一个单位资源

V(S)

① \(S∶=S+1\)；

② 若\(S>0\)，则调用\(V(S)\)的进程继续运行；

③ 若\(S\le0\)，从等待信号量\(S\)的阻塞队列中唤醒头一个进程， 然后调用\(V(S)\)的进程继续运行

P、V操作可表示为如下两个过程

Procedure P(Var S:Semaphore);
begin S∶=S-1;
        if S<0 then W(S)
end; {P}

Procedure V(Var S:Semaphore);
begin S∶=S+1;
         if S≤0 then R(S)
end; {V}

整形信号量代码

wait(S){		//P操作，申请资源
	while(S<=0);	//如果此时S<=0，则无法申请到资源，一直循环
	s--;		//不满足循环条件，即S>0，申请到资源
}

signal(S){		//V操作，释放资源
    s++;
}

整形信号量存在问题

不满足让权等待

记录型信号量

记录型信号量可以实现进程互斥、进程同步

记录型信号量代码

wait(Semaphore S){		//P操作
	S.value--;			//先自减
	if(S.value < 0){	//如果自减后S<0，说明自减前没有资源
		block(S.L);		//阻塞
	}
}

signal(Semaphore S){		//V操作
	S.value++;			//先自增
	if(S.value <= 0){	//如果自增后S<=0，说明此时S的等待队列里有进程
		wakeup(S.L);	//唤醒进程
	}
}

当\(S.value<0\)时， $ |S.value|$ 代表等待队列中的进程个数

AND型信号量~

将进程整个运行过程中需要的所有资源一次性分给进程，进程使用完后一起释放

信号量集~

信号量应用

实现进程互斥

设置互斥信号量为1

如示例代码，P1和P2两进程互斥

PV操作必须成对出现，独占资源后还要让出资源

Semaphore: 信号标，信号量

示例代码

Semaphore mutex = 1;	//设置互斥信号量为1

P1(){
    ...
    P(mutex);		//使用临界资源必须加锁
    执行操作;
    v(mutex);		//使用完后必须解锁
    ...
}

P2(){
    ...
    P(mutex);
    执行操作;
    V(mutex);
    ...
}

过程

确定临界区

设置互斥信号量为1

临界区前后PV成对出现

实现进程同步

进程同步，即让各并发进程有序推进

设置同步信号量为0

如示例代码，P1与P2同步

顺序为P1→P2

即P1先制造资源，让P2消耗资源

所以P1先V，P2再P

示例代码

Semaphore S = 0;

P1(){
    ...
    操作;
    V(S);
    ...
}

P2(){
    P(S);
    操作;
    ...
}

过程

找出一前一后同步关系

设置同步信号量为0

提供资源V，消耗资源P

实现前趋关系

管程机制

解决信号量机制编程麻烦、易出错问题

组成

管程的名称

局部于管程的共享变量说明

对该数据结构进行操作的一组过程

对局部于管程的数据设置初始值的语句

生产者消费者问题

互斥信号量mutex使诸进程对缓冲池实现互斥访问

empty和full计数信号量分别表示空缓冲及满缓冲的数量

进程关系

既有同步，又有互斥

互斥在于对缓冲区的使用

同步在于生产者生产一个数据以后，消费者才能使用这个数据

设置信号量

互斥：mutex = 1

同步：full = 0, empty = n

编码框架

Semaphore mutex = 1, full = 0, empty = n;

Producer(){
    while(1){
        生产数据;
        P(empty);	//检查有无空间资源
        P(mutex);	//申请缓冲区的使用
        将生产数据放入缓冲区
        V(mutex);	//放开缓冲区
        V(full);	//发送信号：已经添加一个生产数据
    }
}

Consumer(){
    while(1){
        P(full);	//检查缓冲区有无生产数据
        P(mutex);	//申请缓冲区使用
        从缓冲区拿数据;
        V(mutex);	//放开缓冲区
        V(empty);	//发送信号：拿走一个生产数据，空闲空间
    }
}

进程通信

信号量机制作为同步工具卓有成效，但作为通信工具不够理想，因为其效率甚低，因此称为低级通信方式

高级通信方式将以较高的效率传送大批数据

定义

进程通信：指相关进程之间所进行的信息交换

高级进程通信：指进程间可直接利用操作系统所提供的一组通信命令（或原语）来传送大量数据的通信方式

进程通信类型

(串讲强调两遍)

共享存储器方式

相互通信的进程通过共享某些数据结构或存储区来进行通信，可分为共享数据结构方式、共享存储区方式

消息传递通信方式

进程间的信息交换以消息或报文为单位，程序员利用一组通信命令（原语）来实现通信，可分为直接、间接通信方式

直接通信方式

是指发送进程利用OS所提供的发送命令，直接把消息发送给目标进程

直接通信方式以内存缓冲区为基础，故有较高的通信速度，它已成为单处理机多道程序系统中最流行的一种通信方式

间接通信方式

信箱通讯

共享文件方式

利用共享文件来实现进程间的通信

UNIX系统中的管道通信

在UNIX系统中，利用一个打开的共享文件来连接两个相互通信的进程，该共享文件称为管道（Pipe），因而该方式又称为管道通信

为了协调双方通信，管道通信必须提供三方面的协调能力：互斥、同步、对方是否存在

综合示例

（串讲：万一要考到它呢？）

设某台机挂有两个I/O通道：分别挂一台输入机和一台打印机

卡片机上有一叠数据卡片，现在要把这些数据逐一输入到缓冲区B1，然后再复制到缓冲区B2，并在打印机上打印出来

系统可设3个进程：输入进程、复制进程、打印进程

分别用进程R、进程C 、进程P来表示

R受C的约束；C受R、P的约束；P受C的约束

RC是同步，先有R的数据才有C的拿取

CP同理

设4个信号量：S1=1，S2=0，S3=1，S4=0

图只给了同步，但应该也有互斥的存在，P(S1)以后是不是要接V(S1)?

线程

程序并发执行所需付出的时空开销

为使程序能并发执行，系统必须进行以下的一系列操作

创建进程，系统在创建一个进程时，必须为它分配其所必需的、除处理机以外的所有资源，如内存空间、I/O设备，以及建立相应的PCB

撤消进程，系统在撤消进程时，又必须先对其所占有的资源执行回收操作，然后再撤消PCB

进程切换，对进程进行上下文切换时，需要保留当前进程的CPU环境，设置新选中进程的CPU环境，因而须花费不少的处理机时间

线程

作为调度和分派的基本单位

线程与进程对比

调度的基本单位

并发性

拥有资源

独立性

系统开销

支持多处理机系统

线程三种状态

执行状态

就绪状态

阻塞状态

线程控制块TCB

处理机调度与死锁

处理机调度的层次和调度算法的目标

在多道程序系统中，调度的实质是一种资源分配，处理机调度是对处理机资源进行分配

处理机调度算法是指根据处理机分配策略所规定的处理机分配算法

处理机调度层次

有些三种都有，有些只有其中两种，但低级调度一定有

高级调度(High Level Scheduling)

又称长程调度或作业调度，它的调度对象是作业，主要应用于批处理系统

低级调度(Low Level Scheduling)

又称为进程调度或短程调度，调度对象是进程（或内核级线程），主要用于批处理系统、分时系统和实时系统中

低级调度一定存在

中级调度(Intermediate Scheduling)

又称为内存调度。主要目的是提高内存利用率和系统吞吐量。把那些暂时不能运行的进程，调至外存等待

处理机调度算法的目标

处理机调度算法的共同目标

资源利用率

应使系统中的处理机和其它所有资源都尽可能地保持忙碌状态

\(CPU的利用率 = \dfrac{CPU有效工作时间}{CPU有效工作时间+CPU空闲等待时间}\)

公平性

公平性是指应使诸进程都获得合理的CPU 时间，不会发生进程饥饿现象

平衡性

为使系统中的CPU和各种外部设备都能经常处于忙碌状态，调度算法应尽可能保持系统资源使用的平衡性

策略强制执行

对所制订的策略其中包括安全策略，只要需要，就必须予以准确地执行，即使会造成某些工作的延迟也要执行

批处理系统的目标

平均周转时间短

系统吞吐量高

处理机利用率高

分时系统的目标

响应时间快

均衡性

实时系统的目标

截止时间的保证

可预测性

作业与作业调度

批处理系统中的作业

作业

作业(Job) ，不仅包含程序和数据，而且还应有作业说明书

系统根据说明书对程序的运行进行控制

是以作业为基本单位从外存调入内存的

作业步

作业步(Job Step) ，在作业运行期间，每个作业都必须经过若干个相对独立又相互关联的顺序加工步骤才能得到结果，其中的每个加工步骤称为一个作业步

作业控制块

作业控制块（JCB）是作业在系统中存在的标志，其中保存了系统对作业进行管理和调度所需的全部信息

作业标识、用户名称、用户帐号、作业类型（CPU繁忙型、I/O繁忙型 、批量型、终端型）、作业状态、调度信息（优先级、作业的运行时间）、资源请求、进入系统时间、开始处理时间、作业 完成时间、作业推出时间、资源使用情况等

作业运行的三个阶段和三种状态

作业从进入系统到运行结束，通常需要经历收容、运行和完成三个阶段

分别对应“后备状态”、“运行状态”和“完成状态”

作业调度任务

接纳多少个作业

接纳哪些作业

作业调度算法

调度算法相关参数计算

CPU利用率

\(CPU的利用率 = \dfrac{CPU有效工作时间}{CPU有效工作时间+CPU空闲等待时间}\)

系统吞吐量

\(系统吞吐量=\dfrac{总共完成作业道数}{总共用时}\)

周转时间

\[ \begin{align*} 周转时间 &= 完成时间-到达时间\\ 带权周转时间&= \frac{周转时间}{运行时间}\\\\ 平均周转时间 &= \frac{各作业周转时间之和}{作业数}\\ 平均带权周转时间 &= \frac{各作业带权周转时间之和}{作业数}\\ \end{align*} \]

等待时间

\(等待时间=周转时间-运行时间=开始时间-到达时间\)

先来先服务(FCFS)

按时间排队，早来先调度

最简单的调度算法，既适用于作业调度，也适用于进程调度

不会导致饥饿

短作业优先(SJF)

指对短作业或短进程优先调度的算法

可用于作业调度和进程调度

可能导致饥饿

缺点：

该算法不利于长作业

该算法完全未考虑作业的紧迫程度，因而不能保证紧迫性作业会被及时处理

由于作业(进程)的长短只是根据用户所提供的估计执行时间而定的，而用户又可能会有意或无意地缩短其作业的估计运行时间，致使该算法不一定能真正做到短作业优先调度

优先级调度算法

各个作业的紧迫程度不同，由外部赋予作业相应的优先级，调度算法是根据该优先级进行调度的

高响应比优先调度算法(HRRN)

高响应比优先调度算法则是既考虑了作业的等待时间，又考虑作业运行时间的调度算法，因此既照顾了短作业，又不致使长作业的等待时间过长，从而改善了处理机调度的性能

优先权变化规律： \[ 优先权 = \frac{等待时间+要求服务时间}{要求服务时间} \] 由于等待时间与服务时间之和，就是系统对该作业的响应时间，故该优先权又相当于响应比\(R_P\)。据此，又可表示为 \[ 优先权 = \frac{等待时间+要求服务时间}{要求服务时间}=\frac{响应时间}{要求服务时间} \]

如果作业的等待时间相同，则要求服务的时间愈短，其优先权愈高，因而该算法有利于短作业

当要求服务的时间相同时，作业的优先权决定于其等待时间，等待时间愈长，其优先权愈高，因而它实现的是先来先服务

对于长作业，作业的优先级可以随等待时间的增加而提高，当其等待时间足够长时，其优先级便可升到很高， 从而也可获得处理机

不会导致饥饿

进程调度

进程调度的任务

保存处理机的现场信息

按某种算法选取进程

把处理器分配给进程

进程调度的机制

三个模块：

排队器

分派器

上下文切换器

进程调度方式

非抢占方式

一旦把处理机分配给某进程后，就一直让它运行下去，决不会因为时钟中断或任何其它原因去抢占当前正在运行进程的处理机，直至该进程完成，或发生某事件而被阻塞时，才把处理机分配给其它进程

主动让出处理机

抢占方式

现代OS中广泛采用抢占方式

允许调度程序根据某种原则，去暂停某个正在执行的进程，将已分配给该进程的处理机重新分配给另一进程

进程调度算法

轮转法

基本思想

系统将所有的就绪进程按FCFS策略排成一个就绪队列

把CPU分配给队首进程，执行一个时间片

当它运行完毕后，又把处理机分配给就绪队列中新的队首进程，也让它执行一个时间片

切换时机

若一个时间片尚未用完，正在运行的进程便已经完成，就立即激活调度程序，将它从就绪队列中删除，再调度就绪队列中队首的进程运行，并启动一个新的时间片

在一个时间片用完时，计时器中断处理程序被激活。如果进程尚未运行完毕，调度程序将把它送往就绪队列的末尾

时间片大小确定

选择很小的时间片，将有利于短作业，因为它能在该时间片内完成。但时间片小，意味着会频繁地执行进程调度和进程上下文的切换，这无疑会增加系统的开销

相反，若时间片选择得很长，且为使每个进程都能在一个时间片内完成，RR算法便退化为FCFS算法，无法满足短作业和交互式用户的需求

优先级调度算法

优先级进程调度算法，是把处理机分配给就绪队列中优先级最高的进程

按抢占分类

抢占式优先级调度算法

非抢占式优先级调度算法

按优先级分类

静态优先级

进程类型：系统进程的优先级高，用户优先级低

进程对资源的需求：要求资源多的优先级低，资源需求少的优先级高

用户要求

动态优先级

动态优先级是指在创建进程之初，先赋予其一个优先级，然后其值随进程的推进或等待时间的增加而改变，以便获得更好的调度性能

多级反馈队列调度算法

调度机制

应设置多个就绪队列，每个队列优先级不一样

第一个队列时间片小，最后一个队列时间片大

当一个新进程进入内存后，首先将它放入第一队列的末尾，按FCFS原则排队等待调度，当轮到该进程执行时，如它能在该时间片内完成，便可准备撤离系统；如果它在一个时间片结束时尚未完成，调度程序便将该进程转入第二队列的末尾，再同样地按FCFS原则等待调度执行；如果它在第二队列中运行一个时间片后仍未完成，再依次将它放入第三队列……

仅当第一队列空闲时，调度程序才调度第二队列中的进程运行。如果处理机正在第i队列中为某进程服务时，又有新进程进入优先权较高的队列(第1~(i-1)中的任何一个队列)，则此时新进程将抢占正在运行进程的处理机，即由调度程序把正在运行的进程放回到第i队列的末尾，把处理机分配给新到的高优先权进程

调度算法的性能

可以满足需要：

终端型作业用户

短批处理作业用户

长批处理作业用户

进程调度算法总结

轮转法抢占，不会导致饥饿

优先级调度算法有抢占，有不抢占，会导致饥饿

多级反馈队列抢占，会导致饥饿

实时调度

实现实时调度的基本条件

提供必要信息

就绪时间

开始截止时间和完成截止时间

处理时间

资源要求

优先级

系统处理能力强

但处理系统计算能力强

采用多处理机系统

采用抢占式调度机制

具有快速切换机制

对外部中断的快速响应能力

快速的任务分派能力

实时调度算法

非抢占式

非抢占式轮转调度算法

非抢占式优先调度算法

抢占式

基于时钟中断的抢占式优先权调度算法

立即抢占(Immediate Preemption)的优先权调度算法

死锁概述

资源问题

可重用性资源和消耗性资源

可消耗性资源又称为临时性资源

可抢占性资源和不可抢占性资源

可抢占性资源，是指某进程在获得这类资源后，该资源可以再被其它进程或系统抢占

不可抢占性资源，即一旦系统把某资源分配给该进程后，就不能将它强行收回，只能在进程用完后自行释放

计算机中的死锁

竞争不可抢占性资源引起死锁

竞争可消耗资源引起死锁

进程推进顺序不当引起死锁

产生死锁的条件

以下四个条件共同存在才会产生死锁

互斥条件

进程要求对所分配的资源进行排它性控制，即在一段时间内某资源仅为一进程所占用

即对不可抢占性资源的争抢

请求和保持条件

当进程因请求资源而阻塞时，对已获得的资源保持不放

不剥夺条件

进程已获得的资源在未使用完之前，不能剥夺，只能在使用完时由自己释放

环路等待条件

在发生死锁时，必然存在一个进程--资源的环形链

循环等待未必死锁，死锁一定循环等待

处理死锁方法

预防死锁

避免死锁

检测死锁

解除死锁

从上到下越来越复杂

资源利用率从上到下依次提高

预防死锁

通过破坏四个必要条件之一

破坏“请求和保持”条件

为了能破坏“请求和保持”条件，系统必须保证做到：当一个进程在请求资源时，它不能持有不可抢占资源

两种协议

第一种协议

该协议规定，所有进程在开始运行之前，必须一次性地申请其在整个运行过程中所需的全部资源

第二种协议

该协议是对第一种协议的改进，它允许一个进程只获得运行初期所需的资源后，便开始运行

破坏“不可抢占”条件

当一个已经保持了某些不可被抢占资源的进程，提出新的资源请求而不能得到满足时，它必须释放已经保持的所有资源，待以后需要时再重新申请

这意味着进程已占有的资源会被暂时地释放，或者说是被抢占了，从而破坏了“不可抢占”条件

破坏“循环等待”条件

个能保证“循环等待”条件不成立的方法是，对系统所有资源类型进行线性排序，并赋予不同的序号

避免死锁

允许出现死锁，但是绕开就行

避免系统进入不安全状态

在避免死锁的方法中，允许进程动态地申请资源，但系统在进行资源分配之前，应先计算此次资源分配的安全性

若此次分配不会导致系统进入不安全状态，则将资源分配给进程，否则，令进程等待

安全状态

是指系统能按某种进程顺序 \((P_1, P_2, \cdots, P_n)\)(称 \(<P_1, P_2, \cdots, P_n>\)序列为安全序列)，来为每个进程\(P_i\)分配其所需资源，直至满足每个进程对资源的最大需求，使每个进程都可顺利地完成

如果系统无法找到这样一个安全序列，则称系统处于不安全状态

银行家算法避免死锁

银行家算法中的数据结构

可利用资源向量Available

含有m个元素的数组，其中的每一个元素代表一类可利用的资源数目，其初始值是系统中所配置的该类全部可用资源的数目，其数值随该类资源的分配和回收而动态地改变

如果 \(Available[j]= K\)，则表示系统中现有 \(R_j\) 类资源 \(K\)个

最大需求矩阵Max

这是一个n×m的矩阵，它定义了系统中n个进程中的每一个进程对m类资源的最大需求

如果 \(Max[i,j]=K\)，则表示进程\(i\)需要\(R_j\)类资源的最大数目为\(K\)

已经分配资源矩阵Allocation

这也是一个n×m的矩阵，它定义了系统中每一类资源当前已分配给每一进程的资源数

如果\(Allocation[i,j]=K\)，则表示进程 \(i\)当前已分得 \(R_j\)类资源的数目为 \(K\)

需求矩阵Need

这也是一个n×m的矩阵，用以表示每一个进程尚需的各类资源数

如果\(Need[i,j]=K\)，则表示进程 \(i\)还需要 \(R_j\) 类资源 \(K\)个，方能完成其任务 \[ Need[i,j]=Max[i,j]-Allocation[i,j] \]

请求矩阵Request

如果\(Request_i[j]=K\)，表示进程 \(P_i\)需要\(K\)个\(R_j\)类型的资源

银行家算法步骤

检查此次申请是否超过了之前声明的最大需求数

检查此时系统剩余可用资源是否还能满足需求

试探着分配资源，更改各数据结构

执行安全性算法，查看分配是否进入不安全状态

安全性算法

检查当前剩余资源是否能满足某个进程的最大需求，如果可，把该进程加入安全序列

把该进程的所有资源回收

不断重复，直至最后所有进程加入安全序列

银行家算法例

假定系统中有五个进程 \(\{P_0, P_1, P_2, P_3, P_4\}\) 和三类资源 \(\{A, B, C\}\)

各种资源的数量分别为10、5、7，在 \(T_0\)时刻的资源分配情况如下图

\(T_0\)时刻的安全性：利用安全性算法对\(T_0\)时刻的资源分配情况进行分析(如下图所示)可知，在\(T_0\)时刻存在着一个安全序列\(\{P_1, P_3, P_4, P_2, P_0\}\)，故系统是安全的

\(P_1\)请求资源：\(P_1\)发出请求向量\(Request_1(1，0，2)\)，系统按银行家算法进行检查

\(Request_1(1, 0, 2)\le Need_1(1, 2, 2)\)

\(Request_1(1, 0, 2)\le Available_1(3, 3, 2)\)

系统先假定可为\(P_1\)分配资源，并修改\(Available, Allocation_1\)和\(Need_1\)向量，由此形成的资源变化情况如前图中的圆括号所示

再利用安全性算法检查此时系统是否安全

死锁的检测

资源分配图

方框代表资源

圆圈代表进程

请求边是进程指向方框

分配边始于方框里一个点

如图，\(P_1\)已经分配了2个\(r_1\)资源，申请一个\(r_2\)资源

\(P_2\)已经分配了1个 \(r_1\) 资源和1个 \(r_2\) 资源，申请一个 \(r_1\) 资源

死锁定理

依次消除与不阻塞进程相连的边，直到无边可消

不阻塞进程：申请的资源数还足够的进程

若资源分配图的边没完全消除，则死锁

死锁的解除

剥夺资源

撤消进程

存储器管理

存储器层次结构

存储层次至少应具有三级：最高层为CPU寄存器，中间为主存，最底层是辅存

主存储器---内存，保存进程运行时的程序和数据

寄存器---与CPU协调工作，用于加速存储器的访问速度，或用作地址寄存器加快地址转换速度

程序的装入和链接

在多道程序环境下，程序要运行必须为之创建进程

而创建进程的第一件事，就是要将程序和数据装入内存

程序处理的步骤

编译

由编译程序将用户源代码编译成若干个目标模块

链接

由链接程序将编译后形成的目标模块以及它们所需要的库函数,链接在一起，形成一个装入模块

装入

由装入程序将装入模块装入内存

程序装入方式

绝对装入方式

可重定位装入方式

动态运行时装入方式

程序的链接

静态链接

在程序运行之前，先将各目标模块及它们所需的库函数，链接成一个完整的装配模块，以后不再拆开

装入时动态链接

将用户源程序编译后所得到的一组目标模块，在装入内存时，采用边装入边链接的链接方式

优点：便于修改和更新，便于实现对目标模块的共享

运行时动态链接

对某些目标模块的链接，是在程序执行中需要该模块时，才对它进行的链接

可加快程序的装入过程，而且可节省大量的内存空间

连续分配存储管理方式

单一连续分配

把内存分为系统区和用户区两部分

系统区仅提供给OS使用，由于中断向量通常驻留在低地址部分，故OS通常是放在内存的低址部分

用户区是指除系统区以外的全部内存空间，提供给用户使用

检查地址是否超过界限地址

用户程序放用户区只放一个，执行完换另一个

作业或进程一旦进入主存，就一直等到它运行结束后才能释放主存

优点

方法简单，易于实现

缺点

不支持多道程序设计，主存利用率不高，程序的运行受主存容量限制

固定分区分配

把原来的用户区分为一个一个的区，每个区放一个程序

固定体现在分区的方法上

分区方法

分区大小相等， 即使所有的内存分区大小相等

分区大小不等

优点

简单内存分配、回收算法，容易实现

缺点

主存空间利用率不高，容易造成内零头

动态分区分配

数据结构

用空闲分区表和空闲分区链管理

分区分配算法

最佳适应算法

为作业选择分区时总是寻找其大小最接近于作业所要求的存储区域

要求空闲分区按容量从小到大的顺序形成空闲分区链

A：12K B：3K C：10K

最坏适应算法

与最佳适应法相反，它在作业选择存储块时，总是寻找最大的空白区

要求空闲分区按容量从大到小的顺序形成空闲分区链

首次适应算法（最先适应算法）

要求空闲分区链以地址递增次序连接

为作业选择分区时总是按地址从低到高搜索，只要找到可以容纳该作业的空白块，就把该空白块分配给该作业

分区分配与回收

分配内存

回收情况

可重定位分区分配

用“紧凑”技术解决“外零头”

存储器的“紧凑”

可重定位分区的优缺点

优点

解决了可变分区分配所引入的“外零头”问题

消除内存碎片，提高内存利用率

缺点

高硬件成本，紧凑时花费CPU时间

对换

内存和外存内容进行交换

对换类型

如果对换是以整个进程为单位，便称之为“整体对换”或“进程对换”

如果以“页”或“段”为单位进行，则分别称为“页面对换”或“分段对换”

对换空间管理

在具有对换功能的OS中，通常把外存分为文件区和对换区

文件区空间的管理采取离散分配方式

对换区采用连续分配方式

分页存储管理方式

基本想法

把程序和内存按定长分割，内存跟程序的片大小相等，在内存里找一个空闲的块，把页面放进去

用一张页表登记下来什么页面放进了哪个块

用页表实现地址转换

地址转换就是把逻辑地址里的页号查表转换为对应的块号

页内地址不变，由块号和页内地址构成物理地址

一次装入，离散分配

页面大小

分页系统中页面的大小是由机器的地址结构所决定的，亦即由硬件决定

分页系统中的页面其大小应适中

页内碎片

进程的最后一页经常装不满一块而形成了不可利用的碎片，称之为“页内碎片”

分页存储有页内碎片

地址结构

页表

系统为每个进程建立一张页面映射表，简称页表

页表的作用是实现从页号到物理块号的地址映射

地址变换机构

为了提高地址变换速度，可在地址变换机构中，增设一个具有并行查寻能力的特殊高速缓冲存储器，又称为“联想存储器”或“快表”

快表用以存放当前访问的那些页表项

分段存储管理方式

一次装入，离散分配

按段装入内存

优势

方便编程

分段共享

信息保护

动态链接

动态增长

地址结构

分页是一维地址，分段是两维地址

段是自己分的，页是系统分的

段表

地址变换机构

分页分段主要区别

（1）页是信息的物理单位，分页是为实现离散分配方式，以消减内存的外零头，提高内存的利用率。或者说，分页仅仅是由于系统管理的需要而不是用户的需要。段则是信息的逻辑单位，它含有一组其意义相对完整的信息，分段的目的是为了能更好地满足用户的需要

（2）页的大小固定且由系统决定，由系统把逻辑地址划分为页号和页内地址两部分，是由机器硬件实现的，因而在系统中只能有一种大小的页面；而段的长度却不固定，决定于用户所编写的程序，通常由编译程序在对源程序进行编译时，根据信息的性质来划分

（3）分页的作业地址空间是一维的，即单一的线性地址空间，程序员只需利用一个记忆符，即可表示一个地址；而分段的作业地址空间则是二维的，程序员在标识一个地址时，既需给出段名，又需给出段内地址

段页式存储管理方式

对程序先分段，每段再分页，页表存入内存

分段有段表，分页有页表

每个程序有一张段表，有若干页表

在段页式系统中，为了获得一条指令或数据，须三次访问内存

虚拟存储器

部分装入和对换，在有限存储器中运行大程序

常规存储器：一次性，非驻留

虚拟存储器两个支撑

局部性原理

时间局限性

空间局限性

多次，非驻留是可以的

交换技术

定义

虚拟存储器，是指具有请求调入功能和置换功能，能从逻辑上对内存容量加以扩充的一种存储器系统

逻辑容量=内存容量+外存容量，运行速度接近于内存速度，而每位的成本却又接近于外存

小内存运行大程序

实现方法

分页请求系统

硬件支持

请求分页的页表机制，它是在纯分页的页表机制上增加若干项而形成的，作为请求分页的数据结构

缺页中断机构，即每当用户程序要访问的页面尚未调入内存时便产生一缺页中断，以请求OS将所缺的页调入内存

地址变换机构，它同样是在纯分页地址变换机构的基础上发展形成的

实现请求分页的软件

请求分段系统

硬件支持

请求分段的段表机制，这是在纯分段的段表机制基础上，增加若干项而形成的

缺段中断机构，每当用户程序要访问的段尚未调入内存时，产生一缺段中断，以请求OS将所缺的段调入内存

地址变换机构， 它同样是在纯分段地址变换机构的基础上发展形成的。

实现请求分段的软件

虚拟存储器特征

离散性：内存分配时采用离散分配的方式

多次性：一个作业被分成多次地调入内存运行

对换性：允许在作业的运行过程中换进、换出

虚拟性：能够从逻辑上扩充内存容量，使用户所看到的内存容量远大于实际内存容量

请求分页存储管理方式

扩充页表位

状态位以后都是扩充

状态位P 用于指示该页是否已调入内存，供程序访问时参考

访问字段A 用于记录本页在一段时间内被访问的次数，或最近已有多长时间未被访问，提供给置换算法选择换出页面时参考

修改位M 表示该页在调入内存后是否被修改过。作为该页换出时是否写回外存的依据

外存地址 用于指出该页在外存上的地址，通常是物理块号，供调入该页时使用

缺页中断机构

在指令执行期间产生和处理中断信号

一般中断是在指令执行完才检查是否有中断请求

而缺页中断是在指令执行期间，发现所要访问的指令或数据不在内存时产生和处理的

一条指令在执行期间，可能产生多次缺页中断

地址变换

内存分配策略和算法

最小物理块数

能保证进程正常运行所需的最小物理块数

当系统为进程分配的物理块数少于此值时，进程将无法运行

物理块的分配策略

固定分配局部置换

可变分配全局置换

可变分配局部置换

物理块分配算法

平均分配算法

按比例分配算法

考虑优先权的分配算法

调页策略

何时调入页面

预调页策略：就是将那些预计在不久之后便会被访问的页面预先调入内存

请求调页策略：当进程在运行中需要访问某部分程序和数据时，若发现其所在的页面不在内存，便立即提出请求，由OS将其所需页面调入内存

何处调入页面

页面置换算法

$ 缺页率 = $

如：下图最佳置换算法

总访问页面数为20

缺页中断有9次（页面置换只有6次，最开始的3次不算页面置换，但是算作中断次数）

则缺页率为45%

最佳置换算法

先进先出(FIFO)页面置换算法

最近最久未使用(LRU)置换算法

是根据页面调入内存后的使用情况进行决策的

时钟置换算法（Clock）

抖动

请求分页系统的优势：实现虚拟内存，用小存储运行大程序

请求分页系统的缺点：会产生缺页中断，若次数变大，对换频繁，则性能变差

请求分页系统中，缺页率很大，对换增加，进程大量时间用在页面对换，处理机利用率下降并趋于0的情况

原因

并发进程太多

每个进程拥有物理块太少

若进程缺页率过高，则增加常驻集以分配更多的物理页面

若进程缺页率过低，则减少常驻集以减少它的物理页面数

预防抖动

局部置换策略

在处理机调度中采用工作集

将阻塞等状态进程调出

检测并调节

请求分段

跟请求分页单位不一样

一个是在系统内实现分页

一个是由用户实现分段

输入输出系统

所有设备都是用设备控制器连接到主机的

所有的设备都是通过总线跟主机的内存交换数据的

I/O系统的功能、模型和接口

I/O基本功能

隐藏物理设备的细节

与设备的无关性

提高处理机和I/O设备的利用率

I/O系统的第三个功能是尽可能地让处理机和I/O设备并行操作，以提高它们的利用率

对I/O设备进行控制

对I/O设备进行控制是驱动程序的功能

四种控制方式

采用轮询的可编程I/O方式

采用中断的可编程I/O方式

直接存储器访问方式（DMA方式）

I/O通道方式

处理器参与程度从1到4越来越低

确保对设备的正确共享

错误处理

I/O系统的层次结构和模型

I/O分层

I/O分层好处

（串讲中强调三遍）

\(\color{red}{使复杂的I/O软件具有清晰的结构、更好的可移植和易适应性}\)

I/O软件层次

用户层

设备独立性软件

设备驱动程序

中断处理程序

设备和中断程序之间有软硬件接口

独立性软件和用户层之间有I/O系统接口

I/O设备和设备控制器

I/O设备分类

按从属关系分类

用户设备

系统设备

按传输速率分类

低速设备：每秒钟几个字节（键盘、鼠标器、语音的输入和输出等设备）

中速设备：每秒钟数千个字节至数万个字节（行式打印机、激光打印机等）

高速设备：在数百千个字节至数十兆字节（磁带机、 磁盘机、 光盘机等）

按信息交换的单位分类

块设备

字符设备

按设备的共享属性分类

独占设备（打印机）

共享设备（磁盘）

虚拟设备

设备和设备控制器之间传递三种信息

数据信号

控制信号

状态信号

设备控制器

功能

接收和识别命令—控制寄存器；命令译码

数据交换—CPU(总线)->控制器(数寄)->设备

标识和报告设备的状态—状态寄存器

地址识别—设备和寄存器地址；地址译码器

数据缓冲—用缓冲器暂存由CPU传来的数据

差错控制—差错检测、重发

组成

设备控制器与处理机的接口

设备控制器与设备的接口

I/O逻辑

内存映射I/O

统一编址

内存映射I/O

当k值处于0～n-1范围时，被认为是内存地址，若k大于等于n时，被认为是某个控制器的寄存器地址

一套命令

独立编址

利用特定的I/O指令

访问内存和访问设备需要两种不同的指令

增加指令数量

I/O通道

概念

通道是处理机，有自己的指令，但是没有内存

执行通道程序控制设备操作

通道程序是放在主机的内存中的，通道与CPU共享内存

通道类型

字节多路通道

数组选择通道

数组多路通道

瓶颈问题

单通路系统

每个设备只能找到一个传输路径，路径故障这个设备就不起作用

多通路系统

把每个设备连接到每个控制器，每个控制器连接到每个通道，构成多通路系统

对设备来说存在多个数据通道，可以解决一个路径故障导致设备不起作用的问题

中断机构和中断处理程序

设备驱动程序

设备处理程序又称为设备驱动程序，它是I/O系统的高层与设备控制器之间的通信程序

任务是接收上层软件发来的抽象I/O要求，如read或write命令，再把它转换为具体要求后，发送给设备控制器，启动设备去执行

反之，它也将由设备控制器发来的信号传送给上层软件

功能

接收由I/O进程发来的命令和参数，并将命令中的抽象要求转换为具体要求，例如，将磁盘块号转换为磁盘的盘面、磁道号及扇区号

检查用户I/O请求的合法性，了解I/O设备的状态，传递有关参数，设置设备的工作方式

发出I/O命令，如果设备空闲，便立即启动I/O设备去完成指定的I/O操作；如果设备处于忙碌状态，则将请求者的请求块挂在设备队列上等待

及时响应由控制器或通道发来的中断请求，并根据其中断类型调用相应的中断处理程序进行处理

对于设置有通道的计算机系统，驱动程序还应能够根据用户的I/O请求，自动地构成通道程序

特点

设备驱动程序属于低级的系统例程，它与一般的应用程序及系统程序之间，有很明显的差异

就像要区分进程和软件的区别，线程和进程的区别

1. 驱动程序主要是指在请求I/O的进程与设备控制器之间的一个通信和转换程序

2. 驱动程序与设备控制器和I/O设备的硬件特性紧密相关，因而对不同类型的设备应配置不同的驱动程序

3. 驱动程序与I/O设备所采用的I/O控制方式紧密相关

4. 由于驱动程序与硬件紧密相关，因而其中的一部分必须用汇编语言书写

5. 驱动程序应允许可重入，一个正在运行的驱动程序常会在一次调用完成前被再次调用

6. 驱动程序不允许系统调用

设备处理方式

为设备设置进程，分为以下三种

为每一类设备设置一个进程，专门用于执行这类设备的I/O操作

在整个系统中设置一个I/O进程，专门用于执行系统中所有各类设备的I/O操作。也可以设置一个输入进程和一个输出进程

不设置专门的设备处理进程，而只为各类设备设置相应的设备处理程序(模块)， 供用户进程或系统进程调用

对I/O设备控制方式

使用轮询的可编程I/O方式

程序I/O方式又称忙--等待方式

使用中断的可编程I/O方式

在现代计算机系统中，对I/O设备的控制，广泛采用中断驱动（Interrupt---Driven）方式

在I/O设备输入每个数据的过程中，由于无须CPU干预，因而可使CPU与I/O设备并行工作

当输完一个数据时，才需CPU花费极短的时间去做些中断处理

直接存储器访问方式（DMA方式）

数据传输的基本单位是数据块

所传输的数据是从设备直接送入内存的，或者相反

整块数据的传送是在控制器的控制下完成的

DMA方式较之中断驱动方式，又是成百倍地减少了CPU对I/O的干预，进一步提高了CPU与I/O设备的并行操作程度

I/O通道控制方式

I/O通道方式是DMA方式的发展，它可进一步减少CPU的干预，即把对一个数据块的读(或写)为单位的干预，减少为对一组数据块的读(或写)及有关的控制和管理为单位的干预

同时，又可实现CPU、通道和I/O设备三者的并行操作，从而更有效地提高整个系统的资源利用率

通道是通过执行通道程序，并与设备控制器来共同实现对I/O设备的控制的

通道程序是由一系列的通道指令（或称通道命令）所构成

与设备无关的I/O软件

设备无关性：应用程序独立于使用的物理设备

逻辑设备名，物理设备名

逻辑设备名称到物理设备名称的转换

为了实现设备的独立性，系统必须能够将应用程序中所使用的逻辑设备名映射为物理设备名

为此，须设立一张逻辑设备表LUT

LUT的设置可采取两种方式：

整个系统设置一张LUT，主要用于单用户

为每个用户设置一张LUT，每当用户登录时，便为该用户建立一个进程，同时也为之建立一张LUT，并将该表放入进程的PCB中，用于多用户

与设备无关的软件

与设备无关的软件是I/O系统的最高层软件，在它下面的是设备驱动程序，其间的界限，因操作系统和设备的不同而有所差异

具体有以下几种

1. 设备驱动程序的统一接口

2. 缓冲管理

⑶ 差错控制

⑷ 对独立设备的分配与回收

⑸ 独立于设备的逻辑数据块

设备分配

为了实现设备分配，必须在系统中设置相应的数据结构

设备分配的数据结构

设备控制表DCT：系统为每一个设备都配置了一张设备控制表

控制器控制表COCT

通道控制表CHCT

系统设备表SDT

设备分配时考虑因素

设备的固有属性

设备分配算法

设备分配的安全性

设备独立性

基本的设备分配程序

对于具有I/O通道的系统，在进程提出I/O请求后，系统的设备分配程序可按下述步骤进行设备分配

分配设备

分配控制器

分配通道

用户层的I/O软件

大部分的I/O软件都在操作系统内部，但仍有一小部分在用户层，包括与用户程序链接在一起的库函数，以及完全运行于内核之外的假脱机系统等

系统调用和库函数调用

用户层软件必须通过一组系统调用来取得操作系统服务

高级语言通常提供了与各系统调用一一对应的库函数，用户程序通过调用对应的库函数使用系统调用

假脱机（SPOOLing）系统

SPOOLing技术就是用于将一台独占设备改造成共享设备的一种行之有效的技术

特点

提高了I/O的速度

将独占设备改造为共享设备

实现了虚拟设备功能

应用

共享打印机

缓冲区管理

在现代OS中，几乎所有的I/O设备在与处理机（内存）交换数据时，都使用了缓冲区

缓冲管理的主要功能是组织好这些缓冲区，并提供获得和释放缓冲区的手段

引入缓冲的原因

缓和CPU与I/O设备间速度不匹配的矛盾

减少对CPU的中断频率，放宽对CPU中断响应时间的限制

提高CPU和I/O设备之间的并行性

单缓冲

单缓冲是OS提供的最简单的一种缓冲形式

每当一个用户进程发出一I/O请求时，操作系统便在主存中为之分配一缓冲区

双缓冲

为了加快输入、输出速度和提高设备利用率，又引入了双缓冲工作方式

也称为缓冲对换（Buffer Swapping）方式

在设备输入时，先将数据输入第一缓冲区，装满后便转向第二缓冲区

循环缓冲

当输入、输出或生产者--消费者的速度相差甚远时，双缓冲的效果则不够理想，但可以增加缓冲区数量而使情况有所改善

因此，引入了多缓冲，并将多缓冲组织成循环缓冲形式

磁盘存储器的性能与调度

数据组织格式

磁道：磁盘旋转时, 磁头的轨迹形成一道道同心圆, 信息就存贮在这些同心圆上，我们把这些同心圆叫做磁道

扇区：磁道划分成的扇段，每个扇区可以存贮 128×2n个字节, 其中 n = 0,1,2,3

容量：= 面数×磁道数×每道扇区数×每扇区字节数

交错数：相邻编号的扇区会交错地排在磁道上的间隔扇区数，访问一个完整磁道时磁盘所转的圈数

磁盘访问时间

寻道时间

这是指把磁臂(磁头)移动到指定磁道上所经历的时间，该时间是启动磁臂的时间s与磁头移动n条磁道所花费的时间之和

\(T_s=m \times n + s\)

m是一常数，与磁盘驱动器的速度有关，对一般磁盘，m=0.2；对高速磁盘，m≤0.1，磁臂的启动时间约为2ms

旋转延迟时间

这是指定扇区移动到磁头下面所经历的时间

\(T_{\tau}\)

硬盘平均旋转延迟时间\(T_{\tau}\)为5.55 ms

软盘平均\(T_{\tau}\)为50-100 ms

传输时间

这是指把数据从磁盘读出或向磁盘写入数据所经历的时间

\(T_t\)的大小与每次所读/写的字节数b和旋转速度有关

\(T_t = \dfrac{b}{rN}\)

其中，r为磁盘每秒钟的转数，N为一条磁道上的字节数

访问时间

\(T_a = T_s+\dfrac{1}{2r}+\dfrac{b}{rN}\)

磁盘调度算法

公平：一个I/O请求在有限时间内满足

高效：减少设备机械运动所带来的时间浪费

一次访盘时间=寻道时间+旋转延迟时间+存取时间

考虑的问题：减少寻道时间，减少延迟时间

用更好的磁头调度算法减少寻道时间

提高转速减少延迟时间

常用磁盘调度算法

先来先服务FCFS

优点：公平、简单

缺点：平均寻道时间较长

最短寻道时间优先SSTF

扫描(SCAN)算法

进程饥饿现象

不断有新进程的请求到达，且其所要访问的磁道与磁头当前所在磁道的距离较近，这种新进程的I/O请求必须优先满足

SCAN算法不仅考虑到欲访问的磁道与当前磁道间的距离，更优先考虑的是磁头当前移动的方向

这种算法中磁头移动的规律颇似电梯的运动，因而又常称为电梯调度算法

循环扫描(CSCAN)算法

特点：规定磁头单向移动

N-Step-SCAN和FSCAN调度算法

文件管理

文件和文件系统

数据项、记录和文件

数据项

最低级数据组织形式

基本数据项

原子数据，数据元素

组合数据项

若干个基本数据项组成

记录

记录是一组相关数据项的集合，用于描述一个对象在某方面的属性

关键字是能唯一标识一个记录的数据项

文件

文件是指由创建者所定义的、具有文件名的一组相关信息的集合，可分为有结构文件和无结构文件两种

在有结构的文件中，文件由若干个相关记录组成

而无结构文件则被看成是一个字符流

文件在文件系统中是一个最大的数据单位，它描述了一个对象集

文件属性

文件类型

文件长度

文件的物理位置

文件的建立时间

文件名

文件名

拓展名

文件类型

按用途分类

系统文件

用户文件

库文件

按文件数据形式分类

源文件

目标文件

可执行文件

按存取控制属性分类

只执行文件

只读文件

读写文件

按文件是否有结构分类

有结构文件（记录式文件）

无结构文件（流式文件）

按文件组织方式分类

有结构文件分为以下三类：

顺序文件

索引文件

索引顺序文件

按文件物理结构分类

顺序文件

链接文件

索引文件

按组织形式和处理方式分类

普通文件

目录文件

特殊文件

文件系统层次结构

最低层

对象及其属性说明

文件、目录、磁盘存储空间

中间层

对对象操纵和管理的软件集合

功能

对文件存储空间的管理

对文件目录的管理

用于将文件的逻辑地址转换为物理地址的机制

对文件的读和写的管理

对文件的共享与保护

最高层

文件系统提供给用户的接口

命令接口

这是指作为用户与文件系统交互的接口

用户可通过键盘终端键入命令，取得文件系统的服务

程序接口

这是指作为用户程序与文件系统的接口

用户程序可通过系统调用来取得文件系统的服务

文件操作

基本文件操作

创建

删除

读

写

设置文件的读/写位置

文件的“打开”和“关闭”操作

所谓“打开”，是指系统将指名文件的属性(包括该文件在外存上的物理位置)从外存拷贝到内存打开文件表的一个表目中，并将该表目的编号(或称为索引)返回给用户

用户再要求对该文件进行相应的操作时，可直接利用该索引号到打开文件表中去查找，从而避免了对该文件的再次检索

这样不仅节省了大量的检索开销，也显著地提高了对文件的操作速度

如果用户已不再需要对该文件实施相应的操作时，可利用“关闭”(close)系统调用来关闭此文件，OS将会把该文件从打开文件表中的表目上删除掉

其他文件操作

有关文件属性的：改变已存文件的文件名、改变文件的拥有者(文件主)、改变对文件的访问权，以及查询文件的状态（包括文件类型、大小和拥有者以及对文件的访问权等）

有关目录的：创建一个目录，删除一个目录，改变当前目录和工作目录等

文件的逻辑结构

文件两种形式的结构

逻辑结构

对文件内容在意识空间组织的方式，定义、描述文件

物理结构

在存储器上存放的方式，在外存上存储组织形式，又称文件存储结构

提高文件访问速度

磁盘和系统间建立缓存（IO）

设计更好的文件结构

更优的文件目录结构

更好的文件检索方法

改善磁头调度算法（软件）

顺序文件

排序方式

串结构----记录之间的顺序与关键字无关。通常的办法是由时间来决定，即按存入时间的先后排列

顺序结构----文件中的所有记录按关键字排序

优点

对诸记录进行批量存取时，存取效率最高

只有顺序文件才能存储在磁带上并能有效地工作

缺点

交互应用时性能很差

增加或修改一个记录比较困难（解决该问题可以配置一个运行记录文件或事务文件）

记录寻址

隐式寻址方式

对于定长记录的顺序文件，如果已知当前记录的逻辑地址，便很容易确定下一个记录的逻辑地址

显式寻址方式

可用于对定长记录的文件实现直接或随机访问

通过文件中记录的位置

利用关键字

索引文件

变长记录较难实现直接存取

按关键字建立索引

索引表本身是一个定长记录的顺序文件

在对索引文件进行检索时，首先是根据用户（程序）提供的关键字，并利用折半查找法去检索索引表，从中找到相应的表项

再利用该表项中给出的指向记录的指针值，去访问所需的记录

直接文件和哈希文件

对于直接文件，则可根据给定的记录键值，直接获得指定记录的物理地址

这种由记录键值到记录物理地址的转换被称为键值转换

哈希文件是目前应用最为广泛的一种直接文件，它利用Hash函数(或称散列函数)可将关键字转换为相应记录的地址

文件目录

要求

实现“按名存取”

提高对目录的检索速度

文件共享

允许文件重名

文件控制块

类似于进程控制块（记录抽象活动）

用于记录文件这个数据结构

包含信息

基本信息

文件物理位置

文件名

存储控制信息

文件主存取权限

核准用户存取权限

一般用户存取权限

使用信息

文件建立日期

文件上一次修改日期

当前使用信息

索引结点

简单理解为，文件控制块中除了文件名，剩下的东西

文件的文件名和其他信息分开存储

先看文件名，决定要不要访问，如果要访问，按索引结点号就在索引结点表里检索文件其余信息

按存放位置区分

磁盘索引结点（唯一）

内存索引结点

单级目录

能实现目录管理的基本功能----按名存取

查找速度慢，不允许重名，不便于实现文件共享

多级目录

提高了检索目录的速度

在不同的用户目录中，可使用相同的文件名，只要在用户自己的UFD中其文件名都是唯一

不同用户可使用不同文件名来访问系统中的同一个共享文件

树形目录

在现代OS中，最通用且实用的文件目录无疑是树形结构目录

目录操作

创建目录

删除目录

改变目录

移动目录

链接(Link)操作

查找

目录检索方式

线性检索法

Hash方法

共享

内存中共享：存储管理

磁盘上共享：文件目录实现

基于有向无循环图实现文件共享

利用索引结点

共享的是索引结点，拥有的是索引结点的地址，而不是文件

利用符号链实现文件共享

克服指针悬空

实线指：有文件的文件控制块

虚线指：没有完全拥有文件的控制或描述，即文件控制块，只拥有文件在树中的路径信息

文件控制块可以完全控制文件

路径信息只能找到文件，不能控制文件

通常存放符号链构成的路径

文件保护

影响文件安全的因素

人为因素

系统因素

自然因素

三类措施

通过存取控制机制，防止由人为因素所造成的文件不安全性

采取系统容错技术，防止系统部分的故障所造成的文件的不安全性

建立后备系统，防止由自然因素所造成的不安全性

口令保护

加密保护

访问控制

磁盘存储器的管理

文件存储空间的管理

空闲表法

空闲链表法

位示图法

成组链接法

总结

算法

有~的是非重点

处理机调度算法~

处理机的高级调度是调度作业

作业调度算法

评判标准

CPU利用率

系统吞吐量

周转时间

等待时间

算法分类

先来先服务(FCFS)：非抢占

短作业优先(SJF)：默认为非抢占，但也有抢占，可能会导致饥饿

高响应比优先(HRRN)：非抢占

进程调度算法

轮转法：抢占式，不会导致饥饿

优先级调度算法：有抢占式，有非抢占式，会导致饥饿

多级反馈队列调度算法：抢占式，会导致饥饿

实时调度算法~

非抢占式

抢占式

银行家算法（安全性算法）

分区分配算法

最佳适应算法

最坏适应算法

首次适应算法

物理块分配算法~

平均分配算法

按比例分配算法

考虑优先权的分配算法

页面置换算法

最佳置换算法

先进先出

最久未使用

时钟

磁盘调度算法

先来先服务

最短寻道时间优先

扫描：电梯调度算法

循环扫描：磁头单向移动

N-Step-SCAN~

FSCAN调度算法~

大题

作业调度算法

求周转时间，带权周转时间，平均周转时间，平均带权周转时间 \[ \begin{align*} 周转时间 &= 完成时间-到达时间\\ 带权周转时间&=\frac{周转时间}{运行时间} \end{align*} \]

页面置换算法

求缺页次数，缺页率

PV操作

银行家算法

分区分配算法

磁盘调度算法

概念对比

进程和线程

线程是调度和分派的基本单位

进程是系统资源分配的基本单位，也是独立运行的基本单位

进程线程都可并发执行

同一进程内的线程共享本进程的资源如内存、I/O、CPU等

但是进程之间的资源是独立的

进程可以独立执行

线程不能独立执行，必须依存在应用程序

线程执行开销小，但是不利于资源的管理和保护

进程执行开销大，但是能够很好的进行资源管理和保护

支持多处理机系统

进程和程序

程序是进程的静态文本，进程是执行程序的动态过程

一个进程可以执行一个或多个程序，几个进程可以同时执行一个程序

程序可作为软件资源长期保存，进程只是一次执行过程，是暂时的，不能长期保存

进程是系统分配调度的独立单位，能与其他进程并发执行

进程和软件

软件，是指当计算机运行时，能提供所要求的功能和性能的指令和程序的集合，该程序能够正确地处理信息的数据结构，还应具有描述程序功能需求以及程序如何操作使用的文档

进程是程序的一次执行，该程序可以与其它程序并发执行

设备驱动程序与应用程序

设备驱动程序属于低级的系统例程

1. 驱动程序主要是指在请求I/O的进程与设备控制器之间的一个通信和转换程序

2. 驱动程序与设备控制器和I/O设备的硬件特性紧密相关，因而对不同类型的设备应配置不同的驱动程序

3. 驱动程序与I/O设备所采用的I/O控制方式紧密相关

4. 由于驱动程序与硬件紧密相关，因而其中的一部分必须用汇编语言书写

5. 驱动程序应允许可重入，一个正在运行的驱动程序常会在一次调用完成前被再次调用

6. 驱动程序不允许系统调用

单道批处理和多道批处理特征

单道批处理：自动性，顺序性，单道性

多道批处理：调度性，无序性，多道性

段页式存储管理方式和请求分页请求分段

段页式、分段、分页都是内存的分配

请求分段，请求分页是虚拟内存的方式

进程和作业的状态

进程状态：就绪，运行，阻塞，创建，终止

作业状态：后备状态、运行状态，完成状态（没有就绪状态）

分段和分页

分页对用户不可见，分段对用户可见

分页地址是一维，分段地址是二维

分段更容易实现信息的共享和保护

分页、分段访问一个逻辑地址都要两次访存，分段也可以引入快表机构

（段页式访存要3次）

碎片的有无

外部碎片：内存中某些空闲分区太小，难以利用

内部碎片：分配给内存的区域有些部分没用上

单一连续分配无外部碎片，有内部碎片

固定分区分配无外部碎片，有内部碎片

动态分区分配无内部碎片，有外部碎片

动态分区分配的外部碎片可以用可重定位分区（紧凑）消除

可重定位分区分配消除内存碎片

分页存储有页内碎片

各大特征

单道批处理特征

自动性，顺序性，单道性

多道批处理特征

调度性，无序性，多道性

分时系统特征

多路性，独立性，及时性，交互性

操作系统基本特征

并发性，共享性，虚拟性，异步性

顺序执行的特征

顺序性，封闭性，可再现性

并发执行的特征

间断性，失去封闭性，不可再现性

进程的特征

动态性，并发性，独立性，异步性，结构特征PCB

虚拟存储器特征

离散性：内存分配时采用离散分配的方式

多次性：一个作业被分成多次地调入内存运行

对换性：允许在作业的运行过程中换进、换出

虚拟性：能够从逻辑上扩充内存容量，使用户所看到的内存容量远大于实际内存容量

各种层次

计算机系统层次结构

从低到高

计算机硬件、操作系统、系统软件、应用软件

进程的层次

在OS中，允许一个进程创建另一个进程

通常把创建进程的进程称为父进程，而把被创建的进程称为子进程（进程的家族关系）

处理机调度层次

低级调度：调度进程

中级调度：调度内存

高级调度：调度作业

低级调度一定存在

存储器层次结构

最高层为CPU寄存器，中间为主存，最底层是辅存

I/O软件层次

从高到低

用户层软件，设备独立性软件，设备驱动程序，中断处理程序

文件系统层次结构

最底层：对象及其属性说明

中间层：对对象操纵和管理的软件集合

最高层：文件系统接口

各种控制

进程控制

进程控制一般是由OS的内核中的原语来实现

实现状态：就绪，运行，阻塞，创建，终止之间的转换

对I/O设备进行控制

采用轮询的可编程I/O方式

采用中断的可编程I/O方式

直接存储器访问方式（DMA方式）

I/O通道方式

串讲强调的内容

进程控制块的组织方式

线性方式

链式方式

索引方式

进程通信类型

共享存储器方式

消息传递通信方式

共享文件方式

管道通信方式

I/O分层好处

结构清晰、可移植性好、适应性好

操作系统课程作业

为什么说OS实现了对计算机资源的抽象

当计算机上覆盖了操作系统后，便为用户提供了一台功能显著增强，使用更加方便，效率明显提高的虚拟计算机

用户无需了解物理接口的实现细节，在窗口环境下使用计算机

OS的特征，以及最基本的特征

并发，共享，虚拟，异步

并发和共享是最基本特征

微内核OS有什么优点，以及这些优点的原因

提高了系统的可扩展性

增强了系统的可靠性

可移植性

提供了对分布式系统的支持

融入了面向对象技术

原因：微内核OS结构建立在模块化、层次化结构基础上，采用客户/服务器模式和面向对象程序设计技术

为什么程序并发执行会产生间断性特征

程序并发执行时，由于它们共享资源或程序之间相互合作完成一项共同任务，因而使程序之间相互制约

并发程序具有“执行—暂停—执行”

程序并发执行为什么会失去封闭性和可再现性

程序在并发执行时，是多个程序共享系统中的各种资源，因而这些资源的状态将由多个程序来改变，致使程序的运行失去了封闭性

由于程序的并发执行，打破了由另一程序独占系统资源的封闭性，因而破坏了可再现性

为什么引入挂起状态，以及该状态的性质

引入挂起原因：终端用户的请求，父进程请求，负荷调节的需要，操作系统的需要

挂起状态不能接收处理机调度

试说明引起进程创建的主要事件

用户登录

作业调度

提供服务

应用请求

创建一个进程时完成的主要工作是什么

调用创建原语，按以下步骤创建新进程

申请空白PCB

为新进程分配资源

初始化进程控制块

将新进程插入就绪队列，如果进程就绪队列能够接纳新进程， 便将新进程插入就绪队列

高级调度和低级调度主要任务是什么，为什么引入中级调度

高级调度，调度作业，主要应用于批处理系统

低级调度，调度进程，主要用于批处理系统、分时系统和实时系统

中级调度，内存调度，主要目的是提高内存利用率和系统吞吐量，把那些暂时不能运行的进程，调至外存等待

说明低级调度主要功能

根据某种算法，决定队列里哪个进程获得相应处理机，并由分派程序把处理机分配给相应进程

（为什么不保护现场？）

比较FCFS和SJF算法

都可用于作业调度和进程调度

FCFS不利于短作业

SJF不利于长作业

什么是优先级倒置现象，采用什么方法解决

高优先级进程被低优先级进程延迟或阻塞

解决：规定不允许抢占、动态优先级继承

解决死锁问题的方法哪个最容易实现，哪种资源利用率最高

预防死锁最容易实现

解除死锁资源利用率最高

一道银行家算法题目

什么是装入时动态链接，有何优点

装入内存时，边装入边链接

优点：便于修改更新、便于实现对目标模块共享

什么是运行时动态链接，有何优点

对某些目标模块的链接，是在程序执行中需要该模块时，才对它进行的链接（用的时候才链接）

优点：加快程序装入过程，节省大量内存空间

分区存储管理常用分配策略，以及优缺点

固定分区分配

优点：简单，最早出现

缺点：空间浪费（每块大小一样）

动态分区分配

优点：灵活性高，内存利用率搞

一道缺页率题目

分页系统“抖动”原因

并发进程太多，每个进程拥有物理块太少

请求分段系统中缺页中断处理过程

为实现CPU与设备控制器间通信，设备控制器要有什么功能

接收和识别命令

数据交换

标识和报告设备的状态

地址识别

数据缓冲

差错控制

比较各I/O控制方式

程序轮询I/O：适用于早期计算机系统

程序中断：CPU与I/O设备并行工作

DMA：减少了CPU对I/O的干预，进一步提高了CPU与I/O设备的并行操作程度

I/O通道：DMA方式的发展，它可进一步减少CPU的干预，即把对一个数据块的读(或写)为单位的干预，减少为对一组数据块的读(或写)及有关的控制和管理为单位的干预

各磁盘调度算法优先考虑问题

FCFS：先来先服务，按请求先后顺序

SSTF：考虑当前磁头与要访问磁道的距离

SCAN：考虑磁头与要访问磁道的距离，更优先考虑的是磁头当前移动的方向

操作系统HS简答题

简述进程调度的任务

保存处理机的现场信息

按某种算法选取进程

把处理器分配给进程

什么叫临界资源？使用临界资源的诸进程间如何实现进程同步

虽然在多道程序系统中的诸进程可以共享各类资源

然而临界资源却是一次只能供一个进程使用，使用完后归还系统，才能给其他进程使用

可使用PV操作实现同步，将同步信号量设置为0即可

进程产生死锁的条件，并简要说明

互斥条件：即对不可抢占性资源的争抢

请求和保持条件：当进程因请求资源而阻塞时，对已获得的资源保持不放

不剥夺条件：进程已获得的资源只能在使用完时由自己释放，不能剥夺

环路等待条件：在发生死锁时，必然存在一个进程--资源的环形链

有几种I/O控制方式，以及各自的特点

程序轮询I/O：适用于早期计算机系统

程序中断：CPU与I/O设备并行工作

DMA：减少了CPU对I/O的干预，进一步提高了CPU与I/O设备的并行操作程度

I/O通道：DMA方式的发展，它可进一步减少CPU的干预，即把对一个数据块的读(或写)为单位的干预，减少为对一组数据块的读(或写)及有关的控制和管理为单位的干预

简述设备驱动程序功能

接收由I/O进程发来的命令和参数，并将命令中的抽象要求转换为具体要求

检查用户I/O请求的合法性

发出I/O命令，如果设备空闲，便启动I/O设备去完成指定的I/O操作；如果设备处于忙碌状态，则将请求者的请求块挂在设备队列上等待

及时响应中断请求，并根据其中断类型调用相应的中断处理程序进行处理

对于设置有通道的计算机系统，驱动程序还应能够根据用户的I/O请求，自动地构成通道程序

文件存储空间的管理归结于盘空闲区的管理问题，常用技术有哪些，以及各自特点

空闲表法：连续分配方式，与内存管理中的动态分区方式类似

空闲链表法：用于分配和回收一个盘块的过程非常简单，但空闲盘块链可能很长

位示图法：由所有盘块对应的位构成一个集合，称为位示图，可描述为一个二维数组

成组链接法：兼备了空闲表、空闲链表两种方法的优点而克服了两种方法均有的、表太长的缺点

文件逻辑结构按文件组织方式分为哪3类，简要说明

顺序文件：指由一系列记录按某种顺序排列所形成的文件，其中的记录可以是定长记录或可变长记录

索引文件：指为可变长记录文件建立一张索引表，为每个记录设置一个表项，以加速对记录检索的速度

索引顺序文件：顺序文件和索引文件相结合的产物，这里，在为每个文件建立一张索引表时，并不为每个记录建立一个索引表项，而是为一组记录中的第一个记录建立一个索引表项

简述设备分配过程

分配设备

分配控制器

分配通道

OS中，处理机调度层次有哪几层

高级调度

它的调度对象是作业

中级调度

又称为内存调度。主要目的是提高内存利用率和系统吞吐量，把那些暂时不能运行的进程，调至外存等待

低级调度

调度对象是进程（或内核级线程）

进程用消息传递系统实现进程通信，请分别说明直接与间接消息传递方式

直接消息传递：是指发送进程利用OS所提供的发送命令，直接把消息发送给目标进程

间接消息传递：信箱传递

什么是操作系统，以及操作系统主要功能

操作系统是控制和管理计算机系统中各种硬件和软件资源，合理地组织计算机工作流程，方便用户使用计算机的程序集合

处理机管理功能、存储器管理功能、设备管理功能、文件管理功能、操作系统与用户之间的接口

简述固定分区和动态分区在管理方式上区别

把原来的用户区分为一个一个的区，每个区放一个作业，可以装入多道作业，固定体现在分区的方法上

动态分区在装入程序时按实际需要的空间分配，也能支持多道程序，增加了空间利用率

简述OS基本特征

并发性

共享性

虚拟性

异步性

分析引起进程阻塞和唤醒的事件主要有哪些

向系统请求共享资源失败：当资源满足时，请求进程才被唤醒

等待某种操作完成：当该操作完成后将其唤醒

新数据尚未到达：所需数据到达后将其唤醒

等待新任务的到达

简述OS中引入缓冲的主要原因

缓和CPU与I/O设备间速度不匹配的矛盾

减少对CPU的中断频率，放宽对CPU中断响应时间的限制

提高CPU和I/O设备之间的并行性

说明进程结构、特征以及基本状态

结构：PCB，程序段，数据段

特征：动态性，并发性，独立性，异步性，PCB

基本状态：阻塞，就绪，执行，创建，终止

设备分配中数据结构有哪些

设备控制表DCT：系统为每一个设备都配置了一张设备控制表

控制器控制表COCT

通道控制表CHCT

系统设备表SDT

什么是虚拟存储器，以及特点

虚拟存储器，是指具有请求调入功能和置换功能，能从逻辑上对内存容量加以扩充的一种存储器系统

特点：离散型，多次性，对换性，虚拟性

↓↓↓不写了↓↓↓

简述请求分页存储管理优缺点

文件逻辑结构、物理组织以及存储方法之间关系

请求分页管理存储中有哪些常用页面置换算法，比较优缺点

常用外存分配方式，以及优缺点

请求分页系统中，页表应该包含哪些数据项，简述每项作用

中断处理程序的处理过程

多级反馈队列调度算法实施过程

设备控制中数据传输方式

考后感想

看到老师在群里的聊天记录有感而发

这次操作系统的考试重点都在简答题，整张考卷几乎没有出现计算题，所以考的更多的是对操作系统整个体系的理解，有道10分大题甚至考从不同角度说明提高文件访问速度的方法

如果考试前能把基础知识扎扎实实过一遍，可能考的分数会好很多，毕竟简答题的作用就是检查对各个部件的功能是否更好的理解

个人认为HS的作用仅限于对不会的知识点查漏补缺，碰到不会的题应该先去书上找相同类型的题型，毕竟书上题的答案可信度比HS高多了，历年的考试题HS上甚至没有所谓的正确答案

如果把过考试甚至拿高分的希望都压在背HS上，那我认为大概率事与愿违，毕竟我已经吃过一次大学物理的亏了

---

参考资料

操作系统课程PPT

操作系统体系梳理

PV操作讲解