文档内容
操作系统
第一章 操作系统概述
1.1 操作系统的目标和作用
1.1.1 操作系统的目标
目标：
1. 方便性。不需要人人都是程序员
2. 有效性。工作协调高效
3. 可扩充性。各自独立发展
4. 开放性。移植和互操作
1.1.2 操作系统的作用
1. OS 作为用户与计算机硬件系统之间的接口OS处于用户与计算机硬件系统之间，用户通
过OS来使用计算机系统。（从用户角度来看，来操纵计算机。）
(1) 命令输入。形式又分为以下几种：
命令行（Command Line Input ）：由OS提供的一组联机命令（语言），用户可通过键盘输入有
关命令，来直接操纵计算机系统。图形用户界面（GUI ）：用户通过显示设备上的窗口和图标
来操纵计算机系统和运行自己的程序。自然输入方式（NUI ）：用户通过语音识别输入来操纵
计算机系统和运行自己的程序。
(2) 系统调用方式（System Call ）。OS提供了一组系统调用，用户可在自己的应用程序中
通过相应的使用编程调用API
1.1.3 推动操作系统发展的主要动力
1.不断提高计算机资源利用率
2. 方便用户
3. 器件的不断更新换代
4. 计算机体系结构的不断发展用户的需求是推动OS发展的根本动力
2. OS 作为计算机系统资源的管理者在一个计算机系统中通常都含有各种各样的硬件和软
件资源。需要空间和时间来使用这些资源，OS合理调配和使用。（这是从管理者的角度来看）
3. OS用作扩展机、虚拟机隐藏了计算机具体细节，为用户展现的是一台虚拟机，功能上扩展
了几个功能部件的组合。（这是从发展的角度来看）Government
1.2 操作系统的发展过程
1.2.1 无操作系统的计算机系统
1. 人工操作方式
从第一台计算机ENIAC 诞生(1945 年2月)到50年代中期的计算机，属于第一代。这种人工
操作方式有以下两方面的缺点：(1) 用户独占全机。(2) CPU 等待人工操作。
2. 脱机输入/输出(Off-Line I/O) 方式这种脱机I/O方式的主要优点如下：
(1)减少了CPU的空闲时间。(2) 提高I/O速度。
- 1 -1.2.2 单道批处理系统
1. 单道批处理系统(Simple Batch Processing System) 的处理过程
2. 单道批处理系统的特征
该系统的主要特征如下：(1) 自动性。(2) 顺序性。(3) 单道性。
1.2.3 多道批处理系统
1. 多道程序设计的基本概念
多道批处理系统(Multiprogrammed Batch Processing System) 。在该系统中，用户所提交
的作业都先存放在外存上并排成一个队列，称为后备队列；然后，由作业调度程序按一定的
算法从后备队列中选择若干个作业调入内存，使它们共享CPU和系统中的各种资源。这种调
度称之为作业调度。
1.2.4 分时系统
1. 分时系统(Time Sharing System) 的产生
如果说，推动多道批处理系统形成和发展的主要动力，是提高资源利用率和系统吞吐量，那
么，推动分时系统形成和发展的主要动力，则是用户的需求。用户的需求具体表现在以
下几个方面：
(1) 人机交互。
(2) 共享主机。
(3) 便于用户上机。
2. 分时系统实现中的关键问题
分时系统性能好坏的主要指标是响应时间。
(1) 及时接收。
(2) 及时处理。
(3) 符合使用习惯。
在OS中引入多道程序设计技术可带来以下好处：
(1)提高CPU的利用率。
(2)可提高内存和I/O 设备利用率。
(3)增加系统吞吐量。
2. 多道批处理系统的特征
(1)多道性。(2) 无序性。(3) 调度性。
3. 多道批处理系统的优缺点
(1)资源利用率高。
(2) 系统吞吐量大。
(3) 平均周转时间长。
(4) 无交互能力。
4. 多道批处理系统需要解决的问题
(1)处理机管理问题。
(2) 内存管理问题。
(3) I/O 设备管理问题。
(4) 文件管理问题。
(5) 作业管理问题。
3. 分时系统的特征
(1)多路性。(2) 独立性。(3) 及时性。(4) 交互性。
1.2.5 实时系统
- 2 -实时系统(Real-Time System) 是指系统能及时(或即时)响应外部事件的请求，在规定的间
内完成对该事件的处理，并控制所有实时任务协调一致地运行。
1.3 操作系统的基本特性
1.3.1 并发(Concurrence)
并行性和并发性是既相似又有区别的两个概念，并行性是指两个或多个事件在同一时刻发
生；而并发性是指两个或多个事件在同一时间间隔内发生。最基本的特征！
1.3.2 共享(Sharing)
在操作系统环境下，所谓共享是指系统中的资源可供内存中多个并发执行的进程(线程)共
同使用。
1.3.3 虚拟(Virtual)
操作系统中的所谓虚拟，是指通过某种技术把一个物理实体变为若干个逻辑上的对应物。
1.3.4 异步性(Asynchronism)
在多道程序环境下，多个进程是以停停走走的方式运行。失去封闭性
第二章进程管理
2.1 进程的基本概念
2.1.1 程序的顺序执行及其特征
2.1.2 前趋图
前趋图(Precedence Graph) 是一个有向无循环图，记为DAG(Directed Acyclic Graph) ，
用于描述进程之间执行的前后关系。
2.1.3 程序的并发执行及其特征
2.1.4 进程的特征与状态
One program which has an independent function works on certain data set
dynamically and allocate resources dynamically What is a process?
一个具有一定独立功能的程序对某个数据
集合上的一次动态执行过程和资源分配过程
Code，Data，Process Table The Difference Between Process and Program Process is
dynamic, and the program is static Process is temporary, the program is
permanence
The elements of process and program is different Code Data – PT The
relationships of process and program are complex Create System call
2. 进程的三种基本状态
1)就绪(Ready) 状态 2) 执行状态 3)阻塞状态
2.1.5 进程控制块
1. 进程控制块的作用
进程控制块的作用是记录一个独立运行的进程的基本信息。或者说，OS是根据PCB来对并发
执行的进程进行控制和管理的。
2. 进程控制块中的信息
3. 进程控制块的组织方式
1) 链接方式 2) 索引方式
2.2 进程控制
2.2.1 进程的创建
- 3 -(1)用户登录。
(2) 作业调度。
(3) 提供服务。
(4) 应用请求。
(1) 申请空白PCB。
(2) 为新进程分配资源。
(3) 初始化进程控制块。
(4) 将新进程插入就绪队列，如果进程就绪队列能够接纳新进程，便将新进程插入就
绪队列。
2. 进程的终止过程
(1) 根据被终止进程的标识符，从PCB集合中检索出该进程的PCB，从中读出该进程的状态。
(2) 若被终止进程正处于执行状态，应立即终止该进程的执行，并置调度标志为真，用于指
示该进程被终止后应重新进行调度。
(3) 若该进程还有子孙进程，还应将其所有子孙进程予以终止，以防他们成为不可控的进程。
(4) 将被终止进程所拥有的全部资源，或者归还给其父进程，或者归还给系统。
(5) 将被终止进程(它的PCB) 从所在队列(或链表)中移出，等待其他程序来搜集信息。
2.2.2 进程的终止
1) 正常结束（自愿的）
2) 异常结束
普通错误退出（自愿的）
致命错误退出（非自愿的）
3) 外界干预（非自愿的）
2.2.3 进程的阻塞与唤醒
1. 引起进程阻塞和唤醒的事件
1)请求系统服务
2) 启动某种操作
3) 新数据尚未到达
4) 无新工作可做
2.2.4 进程的挂起与激活
2.3 进程同步
2.3.1 进程同步的基本概念
1. 两种形式的制约关系
(1)间接相互制约关系。
(2) 直接相互制约关系。
2. 临界资源(Critical Resource)
3. 临界区(critical section)
一个飞机订票系统，两个终端，运行T1、T2进程
T1：
……
read(x);
if x>=1 then
x:=x-1;
write(x);
……
- 4 -T2：
……
read(x);
if x>=1 then
x:=x-1;
write(x);
……
Critical Regions
Coming data blocks
Synchronization
4. 同步机制应遵循的规则
(1)空闲让进。
(2) 忙则等待。
(3) 有限等待。
(4) 让权等待。
(Peterson’s Algorithm)：
先修改、后检查、后修改者等待正确的算法
turn=j; 描述可进入的进程（同时修改标志时）
在进入区先修改后检查，并检查并发修改的先后：
检查对方flag， 如果不在临界区则自己进入－－空闲则入
否则再检查turn ： 保存的是较晚的一次赋值，则较晚的进
程等待，较早的进程进入－－先到先入，后到等待
Mutual Exclusion with Busy Waiting
Entering and leaving a critical region using the
TSL instruction
Sleep and
Wakeup
Producer-consumer problem with fatal race condition
2.3.2 信号量机制
1. 整型信号量
最初由Dijkstra 把整型信号量定义为一个整型量，仅能通过初始化和两个标准的原子操作
(Atomic Operation) wait(S) 和 signal(S) 来访问。两个操作被分别称为 P、V 操作
(primitive) 。
wait(S): while S≤0 do no op
S∶=S-1;
signal(S): S∶=S+1;
2.记录型信号量
在整型信号量机制中的wait 操作，只要是信号量S≤0，就会不断地测试。因此，该机制并未
遵循让权等待的准则，而是使进程处于忙等的状态。记录型信号量机制，则是一种不存在忙
等现象的进程同步机制。但在采取了让权等待的策略后，又会出现多个进程等待访问同一临
界资源的情况。为此，在信号量机制中，除了需要一个用于代表资源数目的整型变量value
外，还应增加一个进程链表L，用于链接上述的所有等待进程。记录型信号量是由于它采用了
记录型的数据结构而得名的。
P 原语wait(s); down(s); P(s)
- 5 ---s.count; //表示申请一个资源;
if (s.count <0)// 表示没有空闲资源;
{ 调用进程进入等待队列s.queue; 阻塞调用进程;}
V 原语signal(s); up(s); V(s)
++s.count; //表示释放一个资源；
if (s.count <= 0) //表示有进程处于阻塞状态；
{ 从等待队列s.queue中取出一个进程P; 进程P进入就绪队列;}
Semaphores
The producer-
consumer
problem using
semaphores
Monitors
Example of a monitor
2.4 经典进程的同步问题
2.4.1 生产者消费者问题
1. 利用记录型信号量解决生产者消费者问题
Dining Philosophers
Philosophers eat/think
Eating needs 2 forks
Pick one fork at a time
How to prevent deadlock
2.4.2 哲学家进餐问题
让奇数号的哲学家先取右手边的筷子，让偶数号的哲学家先取左手边的筷子。
send(i)
begin
if i mod 2 = 0 then else
{ {
P(c[i]); P(c[i+1 mod 5]);
P(c[i+1 mod 5]); P(c[i]);
eat; eat;
V(c[i+1 mod 5]); V (c[i]);
V (c[i]); V(c[i+1 mod 5]);
} }
end
2.4.3 读者写者问题
读者-写者问题描述
The Readers
and Writers
Problem
1. 利用记录型信号量解决读者写者问题
- 6 -The Sleeping Barber Problem
The Sleeping
Barber
Problem
Solution to
sleepingbarber
problem
Shared memory(共享内存)
Message(消息机制)
Pipe(管道)
Signal(信号)
Socket(套接字)
Interprocess Communication
2.5 进程通信2.5.1 进程通信的类型
1. 共享存储器系统(Shared Memory System)
(1)基于共享数据结构的通信方式。
(2) 基于共享存储区的通信方式。
2. 消息传递系统(Message passing system)
在消息传递系统中，进程间的数据交换，
是以格式化的消息(message) 为单位的；
在计算机网络中，又把message 称为报
文。程序员直接利用系统提供的一组通信命令
(原语)进行通信。
3. 管道(Pipe) 通信
管道是指用于连接一个读进程和一个
写进程以实现他们之间通信的一个共享文
件，又名pipe文件。这种方式首创于UNIX
系统，由于它能有效地传送大量数据，因
而又被引入到许多其它操作系统中。
2.5.2 消息传递通信的实现方法
1. 直接通信方式
通信命令(原语)：
Send(Receiver, message); 发送一个消息给接收进程；
Receive(Sender, message); 接收Sender 发来的消息；
例如，原语Send(P2, m1)表示将消息m1发送给接收进程P2; 而原语Receive(P1，m1)
则表示接收由P1发来的消息m1。
不指定发送者的接收原语可表示为：Receive (id, message);
利用直接通信原语，解决生产者消费者问题。
repeat
…
produce an item in nextp;
…
send(consumer, nextp);
- 7 -until false;
repeat
receive(producer, nextc);
…
consume the item in nextc;
until false;
Message
Passing
.The
producer-
consumer
problem
with N
messages
2. 间接通信方式
(1) 信箱的创建和撤消。
(2) 消息的发送和接收。
Send(mailbox, message); 将一个消息发送到指定信箱；
Receive(mailbox, message); 从指定信箱中接收一个消息；
3. 进程同步方式
(1)发送进程阻塞、接收进程阻塞。
(2) 发送进程不阻塞、接收进程阻塞。
(3) 发送进程和接收进程均不阻塞。
2.6 线程
2.6.1 线程的基本概念
为使程序能并发执行，系统还必须进行以下的一系列操作。
1) 创建进程
2) 撤消进程
3) 进程切换
1. 线程的引入
The Thread Model
(a) Three processes each with one thread
(b) One process with three threads
For Example The Thread Model
Each thread has its own stack
2. 线程的属性
(1)轻型实体（容易创建和撤销）。
(2) 独立调度和分派的基本单位。
(3) 可并发执行。
(4) 共享进程资源。
(5) 适应硬件的发展
The Thread Model
Items shared by all threads in a process
Items private to each thread
- 8 -3. 线程的状态
(1) 状态参数。
(2) 线程运行状态。
5. 多线程OS中的进程
在多线程OS中，进程是作为拥有系统资源的基本单位，通常的进程都包含多个线程并为它
们提供资源，但此时的进程就不再作为一个执行的实体。多线程OS中的进程有以下属性：
(1) 作为系统资源分配的单位。
(2) 可包括多个线程。
(3) 进程不是一个可执行的实体。
4. 线程的创建和终止
在多线程OS环境下，应用程序在启动时，通常仅有一个线程在执行，该线程被人们称为初始
化线程。它可根据需要再去创建若干个线程。终止线程的方式有两种：一种是在线程完成了
自己的工作后自愿退出；另一种是线程在运行中出现错误或由于某种原因而被其它线程强
行终止。
2.6.2 线程间的同步和通信
1. 互斥锁(mutex)
互斥锁是一种比较简单的、用于实现线程间对资源互斥访问的机制。
2. 条件变量
Use of a barrier
processes approaching a barrier
all processes but one blocked at barrier
last process arrives, all are let through
2.6.3 内核支持线程和用户级线程
1. 内核支持线程
这里所谓的内核支持线程，也都同样是在内核的支持下运行的，即无论是用户进程中的线程，
还是系统进程中的线程，他们的创建、撤消和切换等，也是依靠内核实现的。此外，在内核空
间还为每一个内核支持线程设置了一个线程控制块，内核是根据该控制块而感知某线程的
存在的，并对其加以控制。
Implementing Threads in the Kernel
A threads package managed by the kernel
2. 用户级线程
用户级线程仅存在于用户空间中。对于这种线程的创
建、撤消、线程之间的同步与通信等功能，都无须利用
系统调用来实现。对于用户级线程的切换，通常是发生在
一个应用进程的诸多线程之间，这时，也同样无须内核的
支持。由于切换的规则远比进程调度和切换的规则简单，
因而使线程的切换速度特别快。可见，这种线程是与内核
无关的。
Implementing Threads in User Space
A user-level threads package
Hybrid Implementations
Multiplexing user-level threads onto kernel-
level threads
- 9 -The Multithreading Revolution
第三章处理机调度与死锁
3.1 处理机调度的基本概念
Bursts of CPU usage alternate with periods of I/O wait
a CPU-bound process
an I/O-bound process
Scheduling Algorithm Goals
3.1.1 高级、中级和低级调度
Three level scheduling
FCFS
SJF
HRF
SRF
FCFS
SPF
RR
PS
1.高级调度(High Scheduling)
宏观调度
在每次执行作业调度时，都须做出以下两个决定。
1) 接纳多少个作业?
2) 接纳哪些作业?
2. 低级调度(Low Level Scheduling) 微观调度
1) 非抢占方式(Non-preemptive Mode)
优点：实现简单、系统开销小。
调度时机：
① 正在执行的进程执行完毕退出
② 发生某事件而被阻塞（外部原因）
③ 执行中的进程提出阻塞请求（自我原因）
2) 抢占方式(Preemptive Mode)
优点：处理及时，实现复杂
抢占的时机：
①具有抢先权的进程创建就绪
②具有抢先权的进程被唤醒进入就绪
③具有抢先权的进程从挂起进入就绪
3. 中级调度(Intermediate-Level Scheduling)
中程调度
引入中级调度的主要目的，是为了提高内存利用率和系统吞吐量。
中级调度的算法主要由内存管理来实现，与高级调度和低级调度的算法不同。
3.1.2 调度队列模型
1. 仅有进程调度的调度队列模型
2. 具有高级和低级调度的调度队列模型
- 10 -3. 同时具有三级调度的调度队列模型
3.1.3 选择调度方式和调度算法的若干准则
1. 面向用户的准则
(1) 周转时间短（批处理）
平均周转时间
带权周转时间W T/TS
而平均带权周转时间
(2) 响应时间快（交互式系统）
(3) 截止时间的保证（实时系统）
(4) 优先权准则（特权处理）
2. 面向系统的准则
(1)系统吞吐量高（批处理）
(2) 处理机利用率好（所有的）
(3) 各类资源的平衡利用（所有的）
符合习惯思维（交互式）
具有前瞻预测（实时系统）
3.2 调度算法
3.2.1 先来先服务和短作业(进程)优先调度算法
1. 先来先服务调度算法
2. 短作业(进程)优先调度算法
FCFS的特点
比较有利于长作业，而不利于短作业。有利于CPU繁忙的作业，而不利于I/O 繁
忙的作业。
SJF的特点
优点：
比FCFS改善平均周转时间和平均带权周转时间，缩短作业的等待时间；提高系统的吞吐量；
缺点：
对长作业非常不利，可能长时间得不到执行；未能依据作业的紧迫程度来划分执行的优先级；
难以准确估计作业（进程）的执行时间，从而影响调度性能。
SJF的变型
.“最短剩余时间优先”SRT(Shortest
Remaining Time)
允许比当前进程剩余时间更短的进程来抢占
.“最高响应比优先”HRRN(Highest
Response Ratio Next)
响应比R = (等待时间+ 要求执行时间) / 要
求执行时间
是FCFS和SJF 的折衷
3.2.2 高优先权优先调度算法
1. 优先权调度算法的类型
1)非抢占式优先权算法
2)抢占式优先权调度算法
2. 优先权的类型
1) 静态优先级
- 11 -创建进程时就确定，直到进程终止前都不改变。通常是一个整数。
依据：
进程类型（系统进程优先级较高）
对资源的需求（对CPU和内存需求较少的进程，优先级较高）
用户要求（紧迫程度和付费多少）
2) 动态优先权
在创建进程时赋予的优先级，在进程运行过程中可
以自动改变，以便获得更好的调度性能.
在就绪队列中，等待时间延长则优先级提高，从
而使优先级较低的进程在等待足够的时间后，其优先
级提高到可被调度执行
进程每执行一个时间片，就降低其优先级，从而
一个进程持续执行时，其优先级降低到出让CPU
3. 高响应比优先调度算法
3.2.3 基于时间片的轮转调度算法
1. 时间片轮转法
Round Robin Scheduling
list of runnable processes
list of runnable processes after B uses up its quantum
2. 多级反馈队列调度算法
(Round Robin with Multiple Feedback)
多级反馈队列算法是时间片轮转算法和优
先级算法的综合和发展。优点：
为提高系统吞吐量和缩短平均周转时间而照顾
短进程
为获得较好的I/O 设备利用率和缩短响应时间而
照顾I/O 型进程
不必估计进程的执行时间，动态调节
A scheduling algorithm with four priority classes
PS
3. 多级反馈队列调度算法的性能
(1)终端型作业用户。
(2) 短批处理作业用户。
(3) 长批处理作业用户。
3.2a 实时调度
Schedulable real-time system
.Given
m periodic events
event i occurs within period Pi and requires Ci
seconds
Then the load can only be handled if
We will discuss in the multimedia OS
- 12 -3.3 产生死锁的原因和必要条件
3.3.1 产生死锁的原因
(1) 互斥资源分配不当
(2) 进程间推进顺序不当
1. 竞争资源引起进程死锁
1)可剥夺和非剥夺性资源
2) 竞争非剥夺性资源
3) 竞争临时性资源
Resources
Examples of computer resources
–printers
tape drives
–tables
Processes need access to resources in reasonable
order
Suppose a process holds resource A and requests
resource B
at same time another process holds B and requests A
both are blocked and remain so
Resources Resources
Resources
Two process resource trajectories
2. 进程推进顺序不当引起死锁
Introduction to Deadlocks
Formal definition :
A set of processes is deadlocked if each process in the set
is waiting for an event that only another process in the
set can cause
Usually the event is release of a currently held
resource
None of the processes can …
–run
release resources
be awakened
3.3.2 产生死锁的四个必要条件
(1) 互斥条件
(2) 请求和保持条件
(3) 不剥夺条件
(4) 环路等待条件
3.3.3 处理死锁的基本方法
(1) 忽略死锁
(2) 检测和解除死锁
(3) 避免死锁
- 13 -(4) 预防死锁
3.4 解决死锁的方法
3.4.1 忽略死锁
1.鸵鸟算法
死锁发生的概率小
解决死锁的代价太大
3.4.2 死锁的检测与解除
3.4.2.1 死锁的检测
1. 资源分配图(Resource Allocation Graph)
Detection with One Resource of Each
Type
Note the resource ownership and requests
A cycle can be found within the graph, denoting deadlock
T
2. 死锁定理
3. 死锁检测中的数据结构
Detection with Multiple Resource of Each
Type
An example for the deadlock detection algorithm
3.4.2.2 死锁的解除
(1) 剥夺资源(2) 回溯到还原点
(3) 撤消进程(4) 重起系统
3.4.3 死锁的避免
3.4.3.1. 安全和不安全状态
安全状态之例：
假定系统中有三个进程P1、P2和P3，共有12台磁带机。
进程P1总共要求10台磁带机，P2和P3分别要求4台和9台。假
设在T0时刻，进程P1、P2和P3已分别获得5台、2台和2台磁带
机，尚有3台空闲未分配，如下表所示：
进程最大需求已分配可用
P1
P2
P3
10
4
9
5
2
2
3
3.4.3.2 利用银行家算法避免死锁
一个银行家把他的固定资金
（capital）贷给若干顾客。
只要不出现一个顾客借走所
- 14 -有资金后还不够，银行家的
资金应是安全的。银行家需
一个算法保证借出去的资金
在有限时间内可收回。
3.4.4 预防死锁
1. 摒弃互斥条件
2. 摒弃“请求和保持” 条件
3. 摒弃“不剥夺” 条件
4. 摒弃“环路等待”
Attacking the Mutual Exclusion
Condition
Some devices (such as printer) can be spooled
only the printer daemon uses printer resource
thus deadlock for printer eliminated
Not all devices can be spooled
PCB,HD
.Principle:
avoid assigning resource when not absolutely necessary
as few processes as possible actually claim the resource
Attacking the Hold and Wait Condition
Require processes to request resources before
starting
a process never has to wait for what it needs
.Problems
may not know required resources at start of run
also ties up resources other processes could be using
Variation:
process must give up all resources
then request all immediately needed
Attacking the No Preemption Condition
This is not a viable option
Consider a process given the printer
halfway through its job
now forcibly take away printer
–!!??
Attacking the Circular Wait Condition
Normally ordered resources
A resource graph
9
Summary of approaches to deadlock prevention
预防死锁的各种分类对策
本章重要习题分析
- 15 -第四章存储器管理
4.1 定位和重定位
4.2 简单连续分配方式
4.3 基本页式存储管理方式
4.4 基本段式存储管理方式
4.5 段页式存储管理
4.6 虚拟存储器
4.7 请求式分页的基本原理
4.8 页面置换算法
Relocation and Protection
Cannot be sure where program will be loaded in
memory
address locations of variables, code routines cannot be
absolute
must keep a program out of other processes partitions
Use base and limit values
address locations added to base value to map tophysical address
address locations larger than limit value is an error
4.1 定位和重定位
4.1.1 程序的装入
1. 绝对装入方式(Absolute Loading Mode)
程序中所使用的绝对地址，既可在编译或汇编时给出，也可由程序员直接赋予。
例如：
ORG 1000H
dfb309a
dfb309a
00f3976
1b3c446 00f3976
1b3c446 00f3976
2. 可重定位装入方式(Relocation Loading Mode)
P1
P2
P3
P4
P5
3. 动态运行时装入方式(dynamic Run-time Loading)
动态运行时的装入程序，在把装入模块装入内存后，并不立即把装入模块中的相对地址转换
为绝对地址，而是把这种地址转换推迟到程序真正要执行时才进行。因此，装入内存后的所
有地址都仍是相对地址。
4.1.2 程序的链接
1. 静态链接方式(Static Linking)
在将这几个目标模块装配成一个装入模块时，须解决以下两个问题：
(1) 对相对地址进行修改。
- 16 -(2) 变换外部调用符号。
2. 装入时动态链接(Load time Dynamic Linking)
装入时动态链接方式有以下优点：
(1)便于修改和更新。
(2) 便于实现对目标模块的共享。
3. 运行时动态链接(Run-time Dynamic Linking)
在执行过程中，当发现一个被调用模块尚未装入内存时，立即由OS去找到该模块并将之装
入内存，把它链接到调用者模块上。这样不仅可加快程序的装入过程，而且可节省大量的内
存空间。
4.2 简单连续分配方式
4.2.1 单一连续分配
这是最简单的一种存储管理方式，但只能用于单用户、单任务的操作系统中。采用这种存储
管理方式时，可把内存分为系统区和用户区两部分，系统区仅提供给OS使用，通常是放在内
存的低址部分；用户区是指除系统区以外的全部内存空间，提供给用户使用。
Mono programming
Three simple ways of organizing memory
an operating system with one user process
无分区
4.2.2 固定分区分配
1. 划分分区的方法
(1)分区大小相等，即使所有的内存分区大小相等。
(2) 分区大小不等。
2. 内存分配
等额固定分区
差额固定分区
Multiprogramming with Fixed Partitions
Fixed memory partitions
separate input queues for each partition
single input queue
动态分区
4.2.3 动态分区分配
碎片Hole
1. 分区分配中的数据结构
(1)空闲分区表。
(2) 空闲分区链。
Memory Management with Bit
Maps
Part of memory with 5 processes, 3 holes
tick marks show allocation units
shaded regions are free
Corresponding bit map
Same information as a list
Memory Management with Linked
Lists
- 17 -Four neighbor combinations for the terminatingprocess X Fragment 碎片
2. 分区分配算法
(1)首次适应算法FF。
(2) 循环首次适应算法。
(3) 最佳适应算法。
(4) 最坏适应算法。
(5) 快速适应算法。
Pointer
Coming a
New process is
16K
Worst fit
4.2.4 可重定位分区分配
1. 动态重定位的引入
2. 动态重定位的实现
3. 动态重定位分区分配算法
4.2.5 对换(Swapping)
1.对换的引入
2.对换空间的管理
3. 进程的换出与换入
(1) 进程的换出。
每当一进程由于创建子进程而需要更多的内存空间，
但又无足够的内存空间等情况发生时，系统应将某进程换
出。
(2) 进程的换入。
系统应定时地查看所有进程的状态，从中找出就绪
状态但已换出的进程，将其中换出时间(换出到磁盘上)最
久的进程作为换入进程，将之换入，直至已无可换入的进
程或无可换出的进程为止。
4.3 基本分页存储管理方式
4.3.1 页面与页表
1. 页面
1) 页面和物理块
2) 页面大小
在分页系统中的页面其大小应适中。页面若太小，一方面虽然可使内存碎片减小，从而减少
了内存碎片的总空间，有利于提高内存利用率，但另一方面也会使每个进程占用较多的页面，
从而导致进程的页表过长，占用大量内存；此外，还会降低页面换进换出的效率。然而，如果
选择的页面较大，虽然可以减少页表的长度，提高页面换进换出的速度，但却又会使页内碎
片增大。因此，页面的大小应选择得适中，且页面大小应是2的幂，通常为512 B~8 KB。
Page Size
Small page size
Advantages
less internal fragmentation
better fit for various data structures, code
- 18 -sections
less unused program in memory
Disadvantages
programs need many pages, larger page tables
0
Page size large, the fragmentation big
Page size small, the page table big
Fragmentation 内碎片
Most program’s pieces are less than 4K
A.0
A.1
A.2
A.3
B.0
B.1
B.2
C.0
C.1
C.2
C.3
Page Size
Overhead due to page table and internal
fragmentation
.Where
s = average process size in bytes
p = page size in bytes
e = page entry
Optimized when
internal
fragmentation
page table space
2. 地址结构
分页地址中的地址结构如下：
页号P 位移量W
31 12 11 0
对某特定机器，其地址结构是一定的。若给定一个逻辑地址空间中的地址为A，页面的大小为
L，则页号P和页内地址d可按下式求得：
3. 页表
4.3.2 地址变换机构
1. 基本的地址变换机构
2. 具有快表的地址变换机构
4.3.3 两级和多级页表
现代的大多数计算机系统，都支持非常大的逻辑地址空间(232~264)。在这样的环境下，页表
就变得非常大，要占用相当大的内存空间。可以采用这样两个方法来解决这一问题：
- 19 -①采用离散分配方式来解决难以找到一块连续的大内存空间的问题：②只将当前需要的部
分页表项调入内存，其余的页表项仍驻留在磁盘上，需要时再调入。
1. 两级页表(Two-Level Page Table)
逻辑地址结构可描述如下：
Windows 的多级页表结构
2. 多级页表
对于32位的机器，采用两级页表结构是合适的；但对于64位的机器，如果页面大小仍采用4
KB即212 B，那么还剩下52位，假定仍按物理块的大小(212位)来划分页表，则将余下的42
位用于外层页号。此时在外层页表中可能有4096 G个页表项，要占用16384 GB的连续内存
空间。必须采用多级页表，将外层页表再进行分页，也是将各分页离散地装入到不相邻接的
物理块中，再利用第2级的外层页表来映射它们之间的关系。
Inverted Page Tables
Comparison of a traditional page table with an invertedpage table
4.4 基本分段存储管理方式
4.4.1 分段存储管理方式的引入
引入分段存储管理方式，主要是为了满足用户和程序员的下述一系列需要：
1) 方便编程
2) 信息共享
3) 信息保护
4) 动态增长
5) 动态链接
4.4.2 分段系统的基本原理
1. 分段
分段地址中的地址具有如下结构：
段号段内地址
31 16 15 0
2. 段表
4. 分页和分段的主要区别
(1) 页是信息的物理单位，分页是为实现离散分配方式，以消减内存的外零头，提高内存的
利用率。或者说，分页仅仅是由于系统管理的需要而不是用户的需要。段则是信息的逻辑单
位，它含有一组其意义相对完整的信息。分段的目的是为了能更好地满足用户的需要。
(2) 页的大小固定且由系统决定，由系统把逻辑地址划分为页号和页内地址两部分，是由机
器硬件实现的，因而在系统中只能有一种大小的页面；而段的长度却不固定，决定于用户所
编写的程序，通常由编译程序在对源程序进行编译时，根据信息的性质来划分。
(3) 分页的作业地址空间是一维的，即单一的线性地址空间，程序员只需利用一个记忆符，
即可表示一个地址；而分段的作业地址空间则是二维的，程序员在标识一个地址时，既需给
出段名，又需给出段内地址。
4.5 段页式存储管理方式
4.5.1 基本原理
4.5.2 地址变换过程
4.6 虚拟存储器的基本概念
4.6.1 虚拟存储器的引入
1. 常规存储器管理方式的特征
(1)一次性。
- 20 -(2) 驻留性。
2. 局部性原理
1968 年，Denning.P 指出：
(1) 程序执行时，大多数情况下仍是顺序执行的。
(2) 过程调用将会使程序转移，过程调用的深度在大多数情况下都不超过5。
(3) 程序中存在许多循环结构，它们将多次执行。
(4) 程序中还包括许多对数据结构的处理，如对数组进行操作，它们往往都局限于很小的范
围内。局限性又表现在下述两个方面：(1) 时间局限性。如果程序中的某条指令一旦执行，则
不久以后该指令可能再次执行；如果某数据被访问过，则不久以后该数据可能再次被访问。
产生时间局限性的典型原因，是由于在程序中存在着大量的循环操作。
(2) 空间局限性。一旦程序访问了某个存储单元，在不久之后，其附近的存储单元也将被访
问，即程序在一段时间内所访问的地址，可能集中在一定的范围之内，其典型情况便是程序
的顺序执行。
3. 虚拟存储器定义
所谓虚拟存储器，是指具有请求调入功能和置换功能，能从逻辑上对内存容量加以扩充的一
种存储器系统。其逻辑容量由内存容量和外存容量之和所决定，其运行速度接近于内存速度，
而每位的成本却又接近于外存。可见，虚拟存储技术是一种性能非常优越的存储器管理技术，
故被广泛地应用于大、中、小型机器和微型机中。CPU及其存储器的地址线宽度
4.6.2 虚拟存储器的实现方法
1. 分页请求系统
(1)硬件支持。
①请求分页的页表机制，它是在纯分页的页表机制上增加若干项而形成的，作为请求分页的
数据结构；
②缺页中断机构，即每当用户程序要访问的页面尚未调入内存时便产生一缺页中断，以请求
OS将所缺的页调入内存
③地址变换机构，它同样是在纯分页地址变换机构的基础上发展形成的。
(2) 实现请求分页的软件。
Page Tables
Typical page table entry
Virtual time and so on
Only for memory mapped I/O
The worse page faults happens
Beyond fault
4.6.3 虚拟存储器的特征
1.多次性
对换性
3. 虚拟性
4.7 请求分页存储管理方式
4.7.1 请求分页中的硬件支持
1. 页表机制
2. 缺页中断机构
3. 地址变换机构
4.7.2 内存分配策略和分配算法
1. 最小物理块数的确定
- 21 -2. 物理块的分配策略
在请求分页系统中，可采取两种内存分配策略，即固定和可变分配策略。在进行置换时，也可
采取两种策略，即全局置换和局部置换。于是可组合出以下三种适用的策略。
1) 固定分配局部置换(Fixed Allocation, Local Replacement)
2) 可变分配全局置换(Variable Allocation, Global Replacement)
3) 可变分配局部置换(Variable Allocation, Local Replacemen
2) 按比例分配算法
根据进程的大小按比例分配物理块的算法。如果系统中共有n个进程，每个进程的页面数为
Si，则系统中各进程页面数的总和为：又假定系统中可用的物理块总数为m，则每个进程所能
分到的物理块数为bi，将有：b应该取整，它必须大于最小物理块数。
3. 物理块分配算法
1) 平均分配算法
3) 考虑优先权的分配算法
在实际应用中，为了照顾到重要的、紧迫的作业能尽快地完成，应为它分配较多的内存空间。
通常采取的方法是把内存中可供分配的所有物理块分成两部分：一部分按比例地分配给各
进程；另一部分则根据各进程的优先权，适当地增加其相应份额后，分配给各进程在有的系
统中，如重要的实时控制系统，则可能是完全按优先权来为各进程分配其物理块的。
4.7.3 调页策略
1. 何时调入页面
1)预调页策略
2) 请求调页策略
2. 从何处调入页面
在请求分页系统中的外存分为两部分：用于存放文件的文件区和用于存放对换页面的对换
区。通常，由于对换区是采用连续分配方式，而事件是采用离散分配方式，故对换区的磁盘
I/O 速度比文件区的高。这样，每当发生缺页请求时，系统应从何处将缺页调入内存，可分成
如下三种情况：
(1) 系统拥有足够的对换区空间，这时可以全部从对换区调入所需页面，以提高调页速度。
为此，在进程运行前，便须将与该进程有关的文件，从文件区拷贝到对换区。
(2) 系统缺少足够的对换区空间，这时凡是不会被修改的文件，都直接从文件区调入；而当
换出这些页面时，由于它们未被修改而不必再将它们换出，以后再调入时，仍从文件区直接
调入。但对于那些可能被修改的部分，在将它们换出时，便须调到对换区，以后需要时，再从
对换区调入。
(3) UNIX 方式。由于与进程有关的文件都放在文件区，故凡是未运行过的页面，都应从文件
区调入。而对于曾经运行过但又被换出的页面，由于是被放在对换区，因此在下次调入时，应
从对换区调入。由于UNIX 系统允许页面共享，因此，某进程所请求的页面有可能已被其它进
程调入内存，此时也就无须再从对换区调入。Solaris 存储3. 页面调入过程每当程序所要
访问的页面未在内存时，便向CPU发出一缺页中断，中断处理程序首先保留CPU环境，分析
中断原因后，转入缺页中断处理程序。该程序通过查找页表，得到该页在外存的物理块后，如
果此时内存能容纳新页，则启动磁盘I/O 将所缺之页调入内存，然后修改页表。如果内存已
满，则须先按照某种置换算法从内存中选出一页准备换出；如果该页未被修改过，可不必将
该页写回磁盘；但如果此页已被修改，则必须将它写回磁盘，然后再把所缺的页调入内存，并
修改页表中的相应表项，置其存在位为“1 ，并将此页表项写入快表中。在缺页调入内存后，
利用修改后的页表，去形成所要访问数据的物理地址，再去访问内存数据。
4.8 页面置换算法
- 22 -Page fault forces choice
which page must be removed
make room for incoming page
Modified page must first be saved
unmodified just overwritten
Better not to choose an often used page
will probably need to be brought back in soon
4.8.1 最佳置换算法和先进先出置换算法
1. 最佳(Optimal) 置换算法
最佳置换算法是由Belady 于1966年提出的一种理论上的算法。其所选择的被淘汰页面，将
是以后永不使用的，或许是在最长(未来)时间内不再被访问的页面。采用最佳置换算法，通
常可保证获得最低的缺页率。
OPT 4 3 2 1 4 3 5 4 3 2 1 5
页1 4 3 2 1 1 1 5 5 5 2 1 1
页2 4 3 3 3 3 3 3 3 5 5 5
页3 4 4 4 4 4 4 4 4 4 4
x x x x √√x √√x x
√
共缺页中断7次
2. 先进先出(FIFO)页面置换算法
Second Chance Page Replacement
Algorithm
Operation of a second chance
pages sorted in FIFO order
Page list if fault occurs at time 20, A has Rbit set
(numbers above pages are loading times)
The Clock Page Replacement
Algorithm 2. 改进型Clock 置换算法
由访问位A和修改位M可以组合成下面四种类型的页面：
1类(A=0, M=0): 表示该页最近既未被访问，又未被修改，是最佳淘汰页。
2类(A=0, M=1) ：表示该页最近未被访问，但已被修改，并不是很好的淘汰页。
3类(A=1, M=0) ：最近已被访问，但未被修改，该页有可能再被访问。
4类(A=1, M=1): 最近已被访问且被修改，该页可能再被访问。
1. 简单的Clock 置换算法
4.8.2 Clock 置换算法
Not Recently Used Page Replacement Algorithm
Each page has Reference bit, Modified bit
bits are set when page is referenced, modified
Pages are classified
1. not referenced, not modified
2. not referenced, modified
3. referenced, not modified
4. referenced, modified
NRU removes page at random
- 23 -from lowest numbered non empty class
4.8.3 最近最久未使用(LRU) 置换算法
1. LRU(Least Recently Used) 置换算法的描述
2. LRU置换算法的硬件支持
4.8.4 其它置换算法
1.最少使用(LFU：Least Frequently Used) 置换算法
2. 页面缓冲算法(PBA：Page Buffering Algorithm)
The Working Set Page Replacement Algorithm
The working set is the set of pages used by the kmost recent memory references
w(k,t) is the size of the working set at time, tLocality of reference
The Working Set Page Replacement Algorithm
The working set algorithm
0
The WSClock
Page
Replacement
Algorithm
Operation of the WSClock algorithm
Review of Page Replacement
Algorithms
4.8.5 其它
Belady’s Anomaly
Stack Algorithm
The Distance String
Predicting Page Fault Rates
Belady's Anomaly
FIFO with 3 page frames
FIFO with 4 page frames
P's show which page references show page faults
DESIGN ISSUES FOR PAGING SYSTEMS
Local versus Global Allocation Policies
Load Control
Page Size
Separate Instruction and Data Spaces
Shared Pages
Cleaning Policy
Virtual Memory Interface
Local versus Global Allocation Policies
Original configuration
Local page replacement
Global page replacement
7 frames
Local versus Global Allocation Policies
Page fault rate as a function of the number of page
- 24 -frames assigned
Load Control
Despite good designs, system may still thrash
When PFF algorithm indicates
some processes need more memory
but no processes need less
Solution :
Reduce number of processes competing for
memory
swap one or more to disk, divide up pages they held
reconsider degree of multiprogramming
Separate Instruction and Data Spaces
One address space
Separate I and D spaces
Shared
Pages
Two processes sharing same program sharing itspage table
Cleaning Policy
Need for a background process, paging daemon
periodically inspects state of memory
When too few frames are free
selects pages to evict using a replacement algorithm
It can use same circular list (clock)
as regular page replacement algorithm but with
difference pointer
Segmentation with Paging: Pentium
Pentium code segment descriptor
Data segments differ slightly
Segmentation with Paging: Pentium
Conversion of a (selector, offset) pair to a linear
address
Segmentation with Paging: Pentium
Mapping of a linear address onto a physical
address
15
Segmentation with Paging: Pentium
Protection on the Pentium
本章重要习题分析
第五章设备管理
5.1 I/O系统
- 25 -5.2 I/O控制方式
5.3 缓冲管理
5.4 设备分配
5.5 设备处理
5.6 磁盘存储空间管理
5.7 IO管理的其它问题
5.1 I/O系统
5.1.1 I/O 设备
1. I/O 设备的类型
1) 按传输速率分类
2) 按信息交换的单位分类
3) 按设备的共享属性分类
2. 设备与控制器之间的接口
Principles of
I/O Hardware
Some typical device, network, and data base rates
Device Controllers
I/O devices have components:
mechanical component
electronic component
The electronic component is the device controller
may be able to handle multiple devices
Controller's tasks
convert serial bit stream to block of bytes
perform error correction as necessary
make available to main memory
5.1.2 设备控制器
1. 设备控制器的基本功能
1)接收和识别命令
2) 数据交换
3) 标识和报告设备的状态
4) 地址识别
5) 数据缓冲
6) 差错控制
2. 设备控制器的组成
Memory-Mapped I/O (1)
Separate I/O and memory space
Memory mapped I/O
.Hybrid
Cache?
Memory-Mapped I/O (2)
(a) A single-bus architecture
(b) A dual-bus memory architecture
ISA Bus
- 26 -Memory-Mapped I/O (3)
Structure of a large Pentium system
N
S
Direct Memory Access (DMA)
Operation of a DMA transfer
Interrupts Revisited
How interrupts happens. Connections between devices and
interrupt controller actually use interrupt lines on the busrather than
dedicated wires
5.1.3 I/O 通道
1. I/O 通道(I/O Channel) 设备的引入
2. 通道类型
1)字节多路通道(Byte Multiplexor Channel)
2)数组选择通道(Block Selector Channel)
3)数组多路通道(Block Multiplexor Channel)
3. “瓶颈问题
Channel mode I/O
5.1.4 总线系统
1. ISA 和EISA 总线
1) ISA(Industry Standard Architecture) 总线
2) EISA(Extended ISA) 总线
2. 局部总线(Local Bus)
1) VESA(Video Electronic Standard Association) 总线
2) PCI(Peripheral Component Interface) 总线
5.2 I/O控制方式
Goals of I/O Software
Device independence
programs can access any I/O device
without specifying device in advance
(floppy, hard drive, or CD-ROM)
Uniform naming
name of a file or device a string or an integer
not depending on which machine
Error handling
handle as close to the hardware as possible
5.2 I/O控制方式(续)
Goals of I/O Software
Synchronous vs. asynchronous transfers
blocked transfers vs. interrupt driven
Buffering
data coming off a device cannot be stored in final
destination
Sharable vs. dedicated devices
- 27 -disks are sharable
tape drives would not be
5.2.1 程序I/O方式
5.2.2 中断驱动I/O控制方式
Writing a string to the printer using interruptdriven I/O
Code executed when print system call is made
Interrupt service procedure
5.2.3 直接存储器访问DMA I/O 控制方式
1. DMA(Direct Memory Access) 控制方式的引入
2. DMA控制器的组成
5.2.4 I/O 通道控制方式
1. I/O 通道控制方式的引入
5.3 缓冲管理
5.3.1 缓冲的引入
(1)缓和CPU与I/O 设备间速度不匹配的矛盾。
(2) 减少对CPU的中断频率，放宽对CPU中断响应时间的
限制。
(3) 提高CPU和I/O设备之间的并行性。
5.3.2 单缓冲和双缓冲
1. 单缓冲(Single Buffer)
2. 双缓冲(Double Buffer)
5.3.3 循环缓冲
1. 循环缓冲的组成
5.3.4 缓冲池(Buffer Pool)
1. 缓冲池的组成
对于既可用于输入又可用于输出的公用缓冲池，其中至少应含有以下三种类型的缓冲区：①
空(闲)缓冲区；②装满输入数据的缓冲区；③装满输出数据的缓冲区。为了管理上的方便，可
将相同类型的缓冲区链成一个队列，于是可形成以下三个队列：
（1）空缓冲队列emq 。
(2) 输入队列inq 。
(3) 输出队列outq 。
2. 缓冲区的工作方式
5.4 设备分配
5.4.1 设备分配中的数据结构
1. 设备控制表DCT
2. 控制器控制表、通道控制表和系统设备表
User-Space I/O Software
System Device Table
Device Control Table
COntroller Control Table CHannel Control Table
Hardware
5.4.2 设备分配时应考虑的因素
1. 设备的固有属性
(1)独享设备。
- 28 -(2) 共享设备。
(3) 虚拟设备。
2. 设备分配算法
(1)先来先服务。
(2) 优先级高者优先。
3. 设备分配中的安全性
1)安全分配方式
2) 不安全分配方式
5.4.3 设备独立性
1. 设备独立性(Device Independence) 的概念
为了提高OS的可适应性和可扩展性，在现代OS中都毫无例外地实现了设备独立性，也称为
设备无关性。其基本含义是：应用程序独立于具体使用的物理设备。为了实现设备独立性而
引入了逻辑设备和物理设备这两个概念。在应用程序中，使用逻辑设备名称来请求使用某类
设备；而系统在实际执行时，还必须使用物理设备名称。因此，系统须具有将逻辑设备名称转
换为某物理设备名称的功能，这非常类似于存储器管理中所介绍的逻辑地址和物理地址的
概念。在实现了设备独立性的功能后，可带来以下两方面的好处。
1) 设备分配时的灵活性
2) 易于实现I/O重定向
Device-Independent I/O
Software
Functions of the device-independent I/O software
Uniform interfacing for device drivers
Buffering
Error reporting
Allocating and releasing dedicate devices
Providing a deice-independent block size
2. 设备独立性软件
1) 执行所有设备的公有操作
2) 向用户层(或文件层)软件提供统一接口
I/O Software Layers
Layers of the I/O Software System
User-Space I/O Software
Layers of the I/O system and the main functions
of each layer
Device
Drivers
Logical position of device drivers is shown here
Communications between drivers and device controllers
goes over the bus
5.4.4 独占设备的分配程序
1. 基本的设备分配程序
1)分配设备
2) 分配控制器
3) 分配通道
- 29 -2. 设备分配程序的改进
1)增加设备的独立性
2) 考虑多通路情况
5.4.5 SPOOLing 技术
1. 什么是SPOOLing
为了缓和CPU 的高速性与I/O设备低速性间的矛盾而引入了脱机输入、脱机输出技术。该技
术是利用专门的外围控制机，将低速I/O设备上的数据传送到高速磁盘上；或者相反。事实
上，当系统中引入了多道程序技术后，完全可以利用其中的一道程序，来模拟脱机输入时的
外围控制机功能，把低速I/O设备上的数据传送到高速磁盘上；再用另一道程序来模拟脱机
输出时外围控制机的功能，把数据从磁盘传送到低速输出设备上。这样，便可在主机的直接
控制下，实现脱机输入、输出功能。此时的外围操作与CPU 对数据的处理同时进行，我们把
这种在联机情况下实现的同时外围操作称为
SPOOLing(Simultaneaus Periphernal Operating On-Line) ，或称为假脱机操作。
Spooling system
Simultaneous Peripheral Operation On Line
3. 共享打印机
共享打印机技术已被广泛地用于多用户系统和局域网络中。当用户进程请求打印输出时，
SPOOLing系统同意为它打印输出，但并不真正立即把打印机分配给该用户进程，而只为它做
两件事：①由输出进程在输出井中为之申请一个空闲磁盘块区，并将要打印的数据送入其中；
②输出进程再为用户进程申请一张空白的用户请求打印表，并将用户的打印要求填入其中，
再将该表挂到请求打印队列上。
4. SPOOLing 系统的特点
(1)提高了I/O 的速度。
(2) 将独占设备改造为共享设备。
(3) 实现了虚拟设备功能。
5.5 设备处理
5.5.1 设备驱动程序的功能和特点
1. 设备驱动程序的功能
(1) 接收由I/O进程发来的命令和参数，并将命令中的抽象要求转换为具体要求，例如，将
磁盘块号转换为磁盘的盘面、磁道号及扇区号。
(2) 检查用户I/O 请求的合法性，了解I/O设备的状态，传递有关参数，设置设备的工作方
式。
(3) 发出I/O命令，如果设备空闲，便立即启动I/O 设备去完成指定的I/O 操作；如果设备
处于忙碌状态，则将请求者的请求块挂在设备队列上等待。
(4) 及时响应由控制器或通道发来的中断请求，并根据其中断类型调用相应的中断处理程
序进行处理。
(5) 对于设置有通道的计算机系统，驱动程序还应能够根据用户的I/O请求，自动地构成通
道程序。
2. 设备处理方式
(1) 为每一类设备设置一个进程，专门用于执行这类设备的I/O操作.
(2) 在整个系统中设置一个I/O 进程，专门用于执行系统中所有各类设备的I/O操作。
(3) 不设置专门的设备处理进程，而只为各类设备设置相应的设备处理程序(模块)，供用户
进程或系统进程调用。
3. 设备驱动程序的特点
- 30 -(1) 驱动程序主要是指在请求I/O 的进程与设备控制器之间的一个通信和转换程序。
(2) 驱动程序与设备控制器和I/O设备的硬件特性紧密相关，因而对不同类型的设备应配
置不同的驱动程序。
(3) 驱动程序与I/O设备所采用的I/O控制方式紧密相关。
(4) 由于驱动程序与硬件紧密相关，因而其中的一部分必须用汇编语言书写。
5.5.2 设备驱动程序的处理过程
1.将抽象要求转换为具体要求
2. 检查I/O请求的合法性
3. 读出和检查设备的状态
4. 传送必要的参数
5. 工作方式的设置
6. 启动I/O设备
5.6 磁盘存储器管理
5.6.1 磁盘性能简述
1. 数据的组织和格式
2. 磁盘的类型
1) 固定头磁盘
这种磁盘在每条磁道上都有一读/写磁头，所有的磁头都被装在一刚性磁臂中。通过这些磁
头可访问所有各磁道，并进行并行读/写，有效地提高了磁盘的I/O速度。这种结构的磁盘
主要用于大容量磁盘上。
2) 移动头磁盘
每一个盘面仅配有一个磁头，也被装入磁臂中。为能访问该盘面上的所有磁道，该磁头必须
能移动以进行寻道。可见，移动磁头仅能以串行方式读/写，致使其I/O速度较慢；但由于其
结构简单，故仍广泛应用于中小型磁盘设备中。
Disk Hardware (1)
Disk parameters for the original IBM PC floppydisk and a Western Digital WD
18300 hard disk
Disk Hardware (2)
Physical geometry of a disk with two zones
A possible virtual geometry for this disk
Disk Hardware (3)
Raid levels 0 through 2
Backup and parity drives are shaded
Disk Hardware (4)
Raid levels 3 through 5
Backup and parity drives are shaded
Disk Hardware (5)
Recording structure of a CD or CD-ROM
Disk Hardware (6)
Logical data layout on a CD-ROM
Disk Formatting (1)
A disk sector
Disk Formatting (2)
An illustration of cylinder skew
- 31 -Disk Time
Time required to read or write a disk
block determined by 3 factors
1.Seek time
2.Rotational delay
3.Actual transfer time
. Seek time dominates
Error checking is done by controllers
Time required
Disk busy
Equipment
Hold
&
Wait
Cylinder
Location
Seek
Time
Rotational
Latency
Data
Transmission
I/O
Channel
Wait
3. 磁盘访问时间
1) 寻道时间Ts
这是指把磁臂(磁头)移动到指定磁道上所经历的时间。该时间是启动磁臂的时间s与磁头
移动n条磁道所花费的时间之和，即
Ts m×n+s
其中，m是一常数，与磁盘驱动器的速度有关，对一般磁盘，m=0.2；对高速磁盘，m≤0.1,磁臂
的启动时间约为2 ms 。这样，对一般的温盘，其寻道时间将随寻道距离的增加而增
大，大体上是5~30 ms 。
2) 旋转延迟时间Tτ
这是指定扇区移动到磁头下面所经历的时间。对于硬盘，典型的旋转速度大多为5400 r/min
，每转需时11.1 ms，平均旋转延迟时间Tτ为5.55 ms ；对于软盘，其旋转速度为
300 r/min 或600 r/min ，这样，平均Tτ为50~100 ms 。
3) 传输时间Tt这是指把数据从磁盘读出或向磁盘写入数据所经历的时间。Tt的大小与每
次所读/写的字节数b和旋转速度有关：其中，r为磁盘每秒钟的转数；N为一条磁道上的字
节数，当一次读/写的字节数相当于半条磁道上的字节数时，Tt与Tτ相同，因此，可将访问
时间Ta表示为：
Disk Scheduling
The operating system is responsible for using
hardware efficiently for the disk drives, this
- 32 -means having a fast access time and disk
bandwidth.
Access time has two major components
– Seek time is the time for the disk are to move the
heads to the cylinder containing the desired sector.
– Rotational latency is the additional time waiting forthe disk to rotate the
desired sector to the disk head.
Disk Scheduling
Minimize seek time
Seek time ≈seek distance
Disk bandwidth is the total number of bytes
transferred, divided by the total time
between the first request for service and the
completion of the last transfer.
Disk Scheduling (Cont.)
Several algorithms exist to schedule the
servicing of disk I/O requests.
We illustrate them with a request queue (0199).
98, 183, 37, 122, 14, 124, 65, 67
Head pointer 53
5.6.2 磁盘调度
1. 先来先服务FCFS(First-Come, First Served)
Illustration shows total head movement of
640 cylinders.
2. 最短寻道时间优先SSTF(Shortest Seek Time First)
Illustration shows total head movement of
236 cylinders.
3. 扫描(SCAN)算法
The disk arm starts at one end of the disk,
and moves toward the other end, servicing
requests until it gets to the other end of the
disk, where the head movement is reversed
and servicing continues.
Sometimes called the elevator algorithm.
2) SCAN 算法
Illustration shows total head movement of
208 cylinders.
4. 循环扫描(CSCAN) 算法
Illustration shows total head movement of
183 cylinders + return.
5. N-Step-SCAN 和FSCAN调度算法
1) N-Step-SCAN 算法
在SSTF、SCAN 及CSCAN几种调度算法中，都可能出现磁臂停留在某处不动的情况，例如，有
一个或几个进程对某一磁道有较高的访问频率，即这个(些)进程反复请求对某一磁道的I/O
- 33 -操作，从而垄断了整个磁盘设备。我们把这一现象称为磁臂粘着”(Armstickiness) 。在高
密度磁盘上容易出现此情况。N步SCAN算法是将磁盘请求队列分成若干个长度为N的子队
列，磁盘调度将按FCFS 算法依次处理这些子队列。而每处理一个队列时又是按SCAN算法，
对一个队列处理完后，再处理其他队列。当正在处理某子队列时，如果又出现新的磁盘I/O
请求，便将新请求进程放入其他队列，这样就可避免出现粘着现象。当N值取得很大时，会使
N步扫描法的性能接近于SCAN算法的性能；当N=1时，N步SCAN算法便蜕化为FCFS 算法。
2) FSCAN 算法
FSCAN 算法实质上是N 步SCAN 算法的简化，即FSCAN只将磁盘请求队列分成两个子队列。
一个是由当前所有请求磁盘I/O 的进程形成的队列，由磁盘调度按SCAN 算法进行处理。在
扫描期间，将新出现的所有请求磁盘I/O 的进程，放入另一个等待处理的请求队列。这样，
所有的新请求都将被推迟到下一次扫描时处理。
C-LOOK
Version of C-SCAN
Arm only goes as far as the last request in
each direction, then reverses direction
immediately, without first going all the way
to the end of the disk.
C-LOOK (Cont.)
Illustration shows total head movement of
153 cylinders + return.
Selecting a Disk-Scheduling
Algorithm
SSTF is common and has a natural appeal
SCAN and C-SCAN perform better for
systems that place a heavy load on the disk.
Performance depends on the number and
types of requests.
Requests for disk service can be influenced
by the file-allocation method.
5.7 IO 管理的其它问题
5.7.1磁盘高速缓存(Disk Cache)
是指利用内存中的存储空间，来暂存从磁盘中读出的一系列盘块中的信息。因此，这里的高
速缓存是一组在逻辑上属于磁盘，而物理上是驻留在内存中的盘块。高速缓存在内存中可分
成两种形式。第一种是在内存中开辟一个单独的存储空间来作为磁盘高速缓存，其小是固定
的，不会受应用程序多少的影响；第二种是把所有未利用的内存空间变为一个缓冲池，供请
求分页系统和磁盘I/O时(作为磁盘高速缓存)共享。此时高速缓存的大小，显然不再是固定
的。当磁盘I/O 的频繁程度较高时，该缓冲池可能包含更多的内存空间；而在
应用程序运行得较多时，该缓冲池可能只剩下较少的内存空间。
Selecting a Disk-Scheduling
Algorithm
The disk-scheduling algorithm should be
written as a separate module of the
operating system, allowing it to be replaced
with a different algorithm if
- 34 -necessary.( Policy vs. Mechanism)
Either SSTF or LOOK is a reasonable
choice for the default algorithm.
5.7.2 提高磁盘I/O速度的其它方法
1.提前读(Read-Ahead)
2. 延迟写
3. 优化物理块的分布
4. 虚拟盘
13
本章重要习题分析
第六章文件管理
6.1 文件和文件系统
6.2 文件的逻辑结构
6.3 外存分配方式
6.4 目录管理
6.5 文件存储空间的管理
6.6 文件共享与文件保护
6.7 文件系统的其它问题
6.1 文件和文件系统
6.1.1 文件、记录和数据项
1. 数据项
(1) 基本数据项。
(2) 组合数据项。
2. 记录
3. 文件
文件属性可以包括：
文件类型。
(2) 文件长度。
(3) 文件的物理位置。
(4) 文件的建立时间。
6.1.2 文件类型和文件系统模型
1. 文件类型
1)按用途分类
(1)系统文件。
(2) 用户文件。
(3) 库文件。
2) 按文件中数据的形式分类
(1)源文件。
(2) 目标文件。
(3) 可执行文件。
3) 按存取控制属性分类
- 35 -(1)只执行文件。
(2) 只读文件。
(3) 读写文件。
2. 文件系统模型
1) 对象及其属性
2) 对对象操纵和管理的软件集合
3) 文件系统的接口
6.1.3 文件操作
(1)创建文件create() 。
(2) 删除文件delete() 。
(3) 读文件read。
(4) 写文件write 。
(5) 打开/关闭文件open()/close() 。
(6) 设置文件的读/写位置seek() 。
6.2 文件的逻辑结构
对于任何一个文件，都存在着以下两种形式的结构：
(1) 文件的逻辑结构(File Logical Structure) 。
(2) 文件的物理结构，又称为文件的存储结构，是指文件在外存上的存储组织形式。
6.2.1 文件逻辑结构的类型
1.有结构文件
(1)定长记录。
(2)变长记录。
文件组织顺序文件。
(2) 索引文件。
(3) 索引顺序文件。
2. 无结构文件
如果说大量的数据结构和数据库，是采用有结构的文件形式的话，则大量的源程序、可执行
文件、库函数等，所采用的就是无结构的文件形式，即流式文件。其长度以字节为单位。对流
式文件的访问，则是采用读写指针来指出下一个要访问的字符。可以把流式文件看作是记录
式文件的一个特例。在UNIX系统中，所有的文件都被看作是流式文件；即使是有结构文件，
也被视为流式文件；系统不对文件进行格式处理。
File Structure
Three kinds of files
byte sequence
record sequence
–tree
无结构文件累积文件
索引结构文件
File Types
(a) An executable file (b) An archive
6.2.2 顺序文件
1. 逻辑记录的排序
第一种是串结构，各记录之间的顺序与关键字无关。通常的办法是由时间来决定，即按存入
时间的先后排列，最先存入的记录作为第一个记录，其次存入的为第二个记录，…… 依此类
- 36 -推。第二种情况是顺序结构，指文件中的所有记录按关键字(词)排列。可以按关键词的长短
从小到大排序，也可以从大到小排序；或按其英文字母顺序排序。
2. 顺序文件的优缺点
顺序文件的最佳应用场合，是在对诸记录进行批量存取时，即每次要读或写一大批记录。此
时，对顺序文件的存取效率是所有逻辑文件中最高的；此外，顺序文件存储在磁带上交有利，
并能有效地工作。
6.2.3 索引文件
对于定长记录文件Ai=i×L
对于可变长度记录的文件
6.2.4 索引顺序文件
6.2.5 直接文件和哈希文件
1. 直接文件
对于直接文件，则可根据给定的记录键值，直接获得指定记录的物理地址。换言之，记录键值
本身就决定了记录的物理地址。这种由记录键值到记录物理地址的转换被称为键值转换
(Key to address transformation) 。组织直接文件的关键，在于用什么方法进行从录值到
物理地址的转换。
2. 哈希(Hash) 文件
6.3 外存分配方式
6.3.1 连续分配
2. 连续分配的主要优缺点
连续分配的主要优点如下：
(1)顺序访问容易。
(2) 顺序访问速度快。
连续分配的主要缺点如下：
(1)要求有连续的存储空间。
(2) 必须事先知道文件的长度。
6.3.2 链接分配
1. 隐式链接
2. 显式链接
6.3.3 索引分配
1. 单级索引分配
链接分配方式虽然解决了连续分配方式所存在的问题，但又出现了另外两个问题，即：
(1) 不能支持高效的直接存取。要对一个较大的文件进行直接存取，须首先在FAT中顺序地
查找许多盘块号。
(2) FAT 需占用较大的内存空间。
2. 多级索引分配
(1) 直接地址。
为了提高对文件的检索速度，在索引结点中可设置 10 个直接地址项，即用
iaddr(0)~iaddr(9) 来存放直接地址。换言之，在这里的每项中所存放的是该文件数据的盘
块的盘块号。假如每个盘块的大小为4 KB，当文件不大于40 KB 时，便可直接从索引结点中
读出该文件的全部盘块号。
(2) 一次间接地址。
对于大、中型文件，只采用直接地址是不现实的。为此，可再利用索引结点中的地址项
iaddr(10) 来提供一次间接地址。这种方式的实质就是一级索引分配方式。图中的一次间址
- 37 -块也就是索引块，系统将分配给文件的多个盘块号记入其中。在一次间址块中可存放1K个
盘块号，因而允许文件长达4 MB。
(3) 多次间接地址。
当文件长度大于4 MB+40 KB时(一次间址与10个直接地址项)，系统还须采用二次间址分配
方式。这时，用地址项iaddr(11) 提供二次间接地址。该方式的实质是两级索引分配方式。
系统此时是在二次间址块中记入所有一次间址块的盘号。在采用二次间址方式时，文件最大
长度可达4 GB。同理，地址项iaddr(12) 作为三次间接地址，其所允许的文件最大长度可达
4 TB。
6.4 目录管理
对目录管理的要求如下：
(1)实现按名存取。
(2) 提高对目录的检索速度。
(3) 文件共享。
(4) 允许文件重名。
6.4.1 文件控制块和索引结点
1.文件控制块
(1)基本信息类
①文件名；②文件物理位置；③文件逻辑结构；
④文件的物理结构
(2) 存取控制信息类
(3) 使用信息类
2. 索引结点
1) 索引结点的引入
文件名索引结点编号
文件名1
文件名2
…
…
2) 磁盘索引结点
(1)文件主标识符
(2) 文件类型
(3) 文件存取权限
(4) 文件物理地址
(5) 文件长度
(6) 文件连接计数
(7) 文件存取时间
3) 内存索引结点
(1) 索引结点编号。用于标识内存索引结点。
(2) 状态。指示i结点是否上锁或被修改。
(3) 访问计数。每当有一进程要访问此i结点时，将该访问计数
加1，访问完再减1。
(4) 文件所属文件系统的逻辑设备号。
(5) 链接指针。设置有分别指向空闲链表和散列队列的指针。
6.4.2 目录结构
- 38 -1. 单级目录结构
文件名物理地址文件说明状态位
文件名1
文件名2
…
单级目录的优点是简单且能实现目录管理的基本功能按名存取，但却存在下述一些缺点：
(1) 查找速度慢
(2) 不允许重名
(3) 不便于实现文件共享
2. 两级目录
具有以下优点：
(1)提高了检索目录的速度
(2) 在不同的用户目录中，可以使用相同的文件名。
(3) 不同用户还可使用不同的文件名来访问系统中的同一个共享文件
3. 多级目录结构
(2) 路径名。
在树形目录结构中，从根目录到任何数据文件，都只有一条惟一的通路。在该路径上从树的
根(即主目录)开始，把全部目录文件名与数据文件名，依次地用“/ 连接起来，即构成该数
据文件的路径名(path name) 。系统中的每一个文件都有惟一的路径名。例如，在图6-18 中
用户B为访问文件J，应使用其路径名/B/F/J 来访问。
(3) 当前目录(Current Directory) 。
当一个文件系统含有许多级时，每访问一个文件，都要使用从树根开始直到树叶(数据文件)
为止的、包括各中间结点(目录)名的全路径名。这是相当麻烦的事，同时由于一个进程
运行时所访问的文件，大多仅局限于某个范围，因而非常不便。基于这一点，可为每个进程设
置一个当前目录，又称为工作目录。进程对各文件的访问都相对于当前目录而进行。此时各
文件所使用的路径名，只需从当前目录开始，逐级经过中间的目录文件，最后到达要访问的
数据文件。把这一路径上的全部目录文件名与数据文件名用“/ 连接形成路径名，如用户B
的当前目录是F，则此时文件J的相对路径名仅是J本身。这样，把从当前目录开始直到数据
文件为止所构成的路径名，称为相对路径名(relative path name) ；而把从树根开始的路
径名称为绝对路径名(absolute path name) 。
4. 增加和删除目录
(1) 不删除非空目录。当目录(文件)不空时，不能将其删除，而为了删除一个非空目录必须
先删除目录中的所有文件，使之先成为空目录，后再予以删除。如果目录中还包含有子目录，
还必须采取递归调用方式来将其删除，在MS-DOS中就是采用这种删除方式。
(2) 可删除非空目录。当要删除一目录时，如果在该目录中还包含有文件，则目录中的所有
文件和子目录也同时被删除。
6.4.3 目录查询技术
1. 线性检索法
2. Hash 方法
一种处理此冲突的有效规则是：
(1) 在利用Hash 法索引查找目录时，如果目录表中相应的目录项是空的，则表示系统中并
无指定文件。
(2) 如果目录项中的文件名与指定文件名相匹配，则表示该目录项正是所要寻找的文件所
对应的目录项，故而可从中找到该文件所在的物理地址。
- 39 -(3) 如果在目录表的相应目录项中的文件名与指定文件名并不匹配，则表示发生了冲突，此
时须将其Hash 值再加上一个常数(该常数应与目录的长度值互质)，形成新的索引
值，再返回到第一步重新开始查找。
6.5 文件存储空间的管理
6.5.1 空闲表法和空闲链表法
1. 空闲表法
序号第一空闲盘块号空闲盘块数
1 2 4
2 9 3
3 15 5
4
(2) 存储空间的分配与回收。
空闲盘区的分配与内存的动态分配类似，同样是采用首次适应算法、循环首次适应算法等。
例如，在系统为某新创建的文件分配空闲盘块时，先顺序地检索空闲表的各表项，直至找到
第一个其大小能满足要求的空闲区，再将该盘区分配给用户(进程)，同时修改空闲表系统在
对用户所释放的存储空间进行回收时，也采取类似于内存回收的方法，即要考虑回收区是否
与空闲表中插入点的前区和后区相邻接，对相邻接者应予以合并。
2. 空闲链表法
(1)空闲盘块链。
(2) 空闲盘区链
6.5.2 位示图法
1. 位示图
2. 盘块的分配
(1) 顺序扫描位示图，从中找出一个或一组其值为“0”的二进制位(“0 表示空闲时)。
(2) 将所找到的一个或一组二进制位，转换成与之相应的盘块号。假定找到的其值为“0 的
二进制位，位于位示的第i行、第j列，则其相应的盘块号应按下式计算：
b=n(i 1)+j 式中，n代表每行的位数。
(3) 修改位示图，令map［i,j］=1。
3. 盘块的回收
(1) 将回收盘块的盘块号转换成位示图中的行号和列号。转换公式为：
i=(b-1)DIV n+1
j=(b-1)MOD n+1
(2) 修改位示图。令map ［i,j］=1。
6.5.3 成组链接法
1. 空闲盘块的组织
2. 空闲盘块的分配与回收
当系统要为用户分配文件所需的盘块时，须调用盘块分配过程来完成。该过程首先检查空闲
盘块号栈是否上锁，如未上锁，便从栈顶取出一空闲盘块号，将与之对应的盘块分配给用户，
然后将栈顶指针下移一格。若该盘块号已是栈底，即S.free(0) ，这是当前栈中最后一个可
分配的盘块号。由于在该盘块号所对应的盘块中记有下一组可用的盘块号，因此，须调用磁
盘读过程，将栈底盘块号所对应盘块的内容读入栈中，作为新的盘块号栈的内容并把原栈底
对应的盘块分配出去(其中的有用数据已读入栈中)。然后，再分配一相应的缓冲区(作为该
盘块的缓冲区)。最后，把栈中的空闲盘块数减1并返回。在系统回收空闲块时，须调用盘块
回收过程进行回收。它是将回收盘块的盘块号记入空闲盘块号栈的顶部，并执行空闲盘块数
- 40 -加1操作。当栈中空闲盘块号数目已达100 时，表示栈已满，便将现有栈中的100个盘块号，
记入新回收的盘块中，再将其盘块号作为新栈底。
6.6 文件共享与文件保护6.6.2 利用符号链实现文件共享
在利用符号链方式实现文件共享时，只是文件主才拥有指向其索引结点的指针；而共享该文
件的其他用户，则只有该文件的路径名，并不拥有指向其索引结点的指针。这样，也就不会发
生在文件主删除一共享文件后留下一悬空指针的情况。当文件的拥有者把一个共享文件删
除后，其他用户试图通过符号链去访问一个已被删除的共享文件时，会因系统找不到该文件
而使访问失败，于是再将符号链删除，此时不会产生任何影响。
6.6.3 磁盘容错技术
(1) 通过存取控制机制来防止由人为因素所造成的文件不安全性。
(2) 通过磁盘容错技术，来防止由磁盘部分的故障所造成的文件不安全性。
(3) 通过后备系统来防止由自然因素所造成的不安全性。
1. 第一级容错技术SFT-Ⅰ
1) 双份目录和双份文件分配表
在磁盘上存放的文件目录和文件分配表FAT，是文件管理所用的重要数据结构。如果这些表
格被破坏，将导致磁盘上的部分或全部文件成为不可访问的，因而也就等效于文件的丢失。
为了防止这类情况发生，可在不同的磁盘上或在磁盘的不同区域中，分别建立(双份)目录表
和FAT。其中，一份被称为主目录及主FAT ；把另一份称为备份目录及备份FAT。
2) 热修复重定向和写后读校验
(1)热修复重定向(Hot Redirection) 。
(2) 写后读校验(Read after write Verification) 方式。
2. 第二级容错技术SFT-Ⅱ
(1) 磁盘镜像(Disk Mirroring) 。
(2) 磁盘双工(Disk Duplexing) 。
6.7 文件系统的其它问题
6.7.1 文件系统的实现
6.7.2 文件系统的可靠性
6.7.3 文件系统的实例
File System Implementation
A possible file system layout
The MS-DOS File System (1)
The MS DOS directory entry
The Windows 98 File System (1)
The extended MOS-DOS directory entry used in Windows
98
7 6 5 4 3 2 1 0
保留保留存档子目录卷标系统文件隐藏只读
The Windows 98 File System (2)
An entry for (part of) a long file name in Windows 98
The Windows 98 File System (3)
An example of how a long name is stored inWindows 98
end
r
The UNIX V7 File System (2)
- 41 -A UNIX i-node
10
256+10=266K
256*256+10=64M
256*256*256+10=16T
The UNIX V7 File System (3)
The steps in looking up /usr/ast/mbox
本章重要习题分析
- 42 -
