Operating System

Operating System

1&2 Introduction & Operating System Structures

Definition

Operating system: a program that acts an intermediary between a user of a computer and the computer hardware.

OS is a resource allocator: manages all resources, decides between confilicting requests for efficient and fair resource use

OS is a control program: controls execution of programs to prevent errors and improper use of the computer

Operating System Goals

Execute user programs and makesolving user problems easier
Make the computer system convenient to use
Use the computer hardware in an efficient manner

Components of a Computer System

Hardware (CPU, Memory, I/O Devices)
Operating system
Application programs
Users

Interrupt Handling

Polling (轮询)
Vectored Interrupt System (向量式中断)

Storage Structure

Storage Hierarchy

Caching

Operating System Structure

Multiprogramming (多道程序)

Multiprogramming organizes jobs (code and data) so CPU always has one to execute
A subset of total jobs in system is kept in memory
One job selected and run via job scheduling (作业调度)
When it has to wait (for I/O for example), OS switches to another job

Timesharing (Multitasking, 多任务)

CPU switches jobs so frequently that users can interact with each job while it is running, creating interactive computing
response time should be < 1 second
process
CPU scheduling
swapping
virtual memory

Dual Mode

user mode (用户模式) and kernel mode (内核模式)

Operating System Components

Process Management (进程管理)
Memory Management (内存管理)
Storage Management (外存管理)
I/O Subsystem (I/O 设备管理)
Protection and Security (安全管理)

3 Process

Process Concept

Process (进程): A program in execution

Process Structure

The code, also called text section
Program counter, processor registers
Stack containing temporary data
Data section containing global variables
Heap containing memory dynamically allocated during run time

Program vs. Process

Program is passive entity, process is active

One program can be several process

Process Life Cycle

new (新建状态)
running (运行状态)
waiting (等待状态，或称阻塞状态)
ready (就绪状态)
terminated (终止状态)

Process Control Block (PCB)

Information associated with each process:
- Process state
- Program counter
- CPU registers
- CPU scheduling information
- Memory-management information
- Accounting information
- I/O status information

Process Scheduling

multiple processes competing for scarce CPU time
maximize CPU usage
- quickly switch processes onto CPU for time sharing
selects among available processes for next execution on CPU
maintains scheduling queues of process:
- job queue
- ready queue (就绪队列)
- device queues (等待队列)

Figure: Ready Queue and Various I/O Device Queues

Figure: Representation of Process Scheduling

Long-term Scheduler vs. Short-term Scheduler

long-term scheduler (job scheduler)
- select which process should be brought into ready queue
- invoked very infrequently (seconds, minutes)
- may be slow
short-term scheduler (CPU scheduler)
- select which process should be executed next and allocates CPU
- invoked very frequently (milliseconds)
- must be fast
- Sometimes the only scheduler in a system

InterProcess Communication (IPC)

Processes within a system may be independent or cooperating
Cooperating process (协作进程) can affect or be affected by other process
Reasons for cooperating processes:
- Information sharing
- Computation speedup
- Modularity
Two models of IPC:
- shared memory
- message passing

Direct Communication - Indirect Communication (mailbox)
Blocking (synchronous) - Non-blocking (asynchronous)
Buffering: zero capacity, bounded capacity, unbounded capacity

5 CPU 调度

Scheduling Criteria

CPU 利用率（CPU utilization）
吞吐量（throughput）：单位时间内完成的进程数量
周转时间（turnaround time）：从进程提交到进程完成的时间
等待时间（waiting time）：进程在就绪队列中等待的时间之和
响应时间（response time）：对于分时系统，从提交请求到第一次响应的时间
带权周转时间：周转时间和实际运行时间的比

先来先服务（First-Come, First-Served, FCFS）

缺点：周转时间与响应时间无法保证；对短作业不利

最短作业优先（Shortest Job First, SJF）

分配 CPU 给下个 CPU 区间最短的进程

非抢占（Nonpreemptive）
抢占（preemptive）

SJF 能最小化平均等待时间

问题：需要事先知道，或至少需要估计每个进程所需要的处理时间；长作业可能长期得不到运行而“饿死”

剩余时间最短者优先（Shortest-Remaining-Time-First, SRTF）
抢占，总是选择预期剩余时间最短的进程

从周转时间看，SRT比SJF有更好的性能

优先级调度（Priority Scheduling）

每个进程都有一个优先数
CPU 被分配给具有最高优先级的进程
SJF 也是一种优先级调度算法，优先级是下一个 CPU 时间
问题：饥饿，低优先级进程可能永远无法执行
解决方案：老化，随着时间增加进程优先级

轮转法（Round Robin）

CPU 时间划分为时间片，进程轮流执行

时间片长度的选择

过短：进程上下文切换开销增大
过长：轮转法退化为先来先服务法，对短作业不公平

多级队列（Multilevel Queue）

就绪队列被分为多个
每个队列都有自己的调度算法
队列之间有调度
- 固定优先级：可能饥饿
- 时间片：每个队列有一定的 CPU 时间

多级反馈队列（Multillevel Feedback Queue）：

进程可以在队列之间移动来实现老化

多处理器调度

6 进程同步

临界区三大要求

互斥
空闲让进
有限等待：要控制进程从作出进入临界区选择到请求被允许的过程中，其他进程被允许进入该临界区的次数

互斥问题的软件解法

两个进程

flag[i] = true;
turn = j;
while (flag[j] && turn == j)
  ;
// 临界区
flag[i] = false;

多个进程：面包店算法

choosing[i] = 1;
number[i] = max(number[0], ...,number[n-1]) + 1;
choosing[i]=0;

for(j=0; j < n; j++){
  while(choosing[j])
    ;
  while((number[j]!=0) && (number[j] < number[i] || (number[j] == number[i] && j < i)))
    ;
}
// 临界区
number[i]=0;

互斥问题的硬件解法

互斥锁

TestAndSet 指令

boolean TestAndSet(boolean *target) {
	boolean rv = *target;
	*target = true;
	return rv;
}

使用 TestAndSet 指令的互斥实现

waiting[i] = true;
key = true;
while (waiting[i] && true) {
  key = TestAndLock(lock);
}
waiting[j] = false;
// 临界区
j = (i+1) % n;
while (j != i && !waiting[j]) {
  j = (j+1) % n;
}
if (j == i) {
  lock = false;
}
else {
  waiting[j] = false;
}

信号量

生产者消费者问题

缓冲区大小 n；生产者 m；消费者 k

生产者：

empty = n;
full = 0;
i = 0;
while (true) {
  // 生产产品
  P(empty);
  P(mutex1);
  // 往 buffer[i] 放产品
  i = (i + 1) % n;
  V(mutex1);
  V(full);
}

消费者：

empty = n;
full = 0;
j = 0;
while (true) {
  P(full);
  P(mutex2);
  // 从 buffer[j] 取产品
  j = (j + 1) % n;
  V(mutex2);
  V(empty);
}

7 死锁（Deadlock）

死锁的四个必要条件

互斥：一次只有一个进程可以使用一个资源
占有并等待：一个至少持有一个资源的进程等待获得额外的由其他进程所持有的资源
不可抢占：一个资源只有当持有它的进程完成任务后，自由的释放
循环等待：等待资源的进程之间存在环

资源分配图（Resource-Allocation Graph ）

进程结点：

资源结点：

请求边：

分配边：

Methods for Handling Deadlocks

执行前：死锁预防（破坏死锁的四个必要条件之一）
执行中：死锁避免（避免系统进入不安全状态）
发生死锁：死锁检测、死锁恢复

Ignore the problem and pretend that deadlocks never occur in the system; used by most operating systems, including UNIX.（好多系统不采取任何措施）

死锁预防

预先分配法：要求进程在执行前申请全部的资源，每个进程在获取了执行所需的所有资源之后才能开始执行，系统对于每一个进程的资源申请都能满足时才分配，否则一个也不分配，破坏了占有并等待条件，但资源利用效率低
有序分配法：要求一个进程按特定的顺序申请所需的资源，破坏环路等待条件

死锁避免

避免系统进入可能产生死锁的不安全状态

系统安全指存在一个执行序列，所有进程都能完成

单资源实例：资源分配图

多资源实例：银行家算法

数据结构

当前可用资源向量 Available[m]
最大需求矩阵 Max[n][m]
分配矩阵 Allocation[n][m]
需求矩阵 Need[n][m]
- Need[i,j] = Max[i,j] - Allocation[i,j]
当前请求矩阵 Request[n][m]

资源请求算法

如果 request > need，出错
如果 request > available，等待
预分配资源
1. available -= request
2. allocation += request
3. need -= request
如果 safe，分配资源；否则等待，并恢复原状

安全检测算法

work = available
finish[1,2,...,n] = false
找到满足下面两个条件的 i，如果不存在满足条件的 i，到步骤 4
1. finish[i] = false
2. need[i] < work
work += allocation[i]
finish[i] = true
到步骤 2
如果对所有的 i，finish[i] == true，则系统安全，否则不安全

不足

必须预先申明每个进程需要的资源总量；
进程之间相互独立，其执行顺序取决于系统安全，而非进程之间的同步要求；
系统必须提供固定数量的资源供进程使用
每一次分配资源都要进行检测，系统开销较大

死锁检测

单资源实例：进程等待图

多资源实例

work = available
for i=1,2,...,n, finish[i] = (false if allocation[i] != 0; true otherwise)
找到满足下面两个条件的 i，如果不存在满足条件的 i，到步骤 4
1. finish[i] = false
2. request[i] < work
work += allocation[i]
finish[i] = true
到步骤 2
finish[j] = false <=> 进程 j 死锁

死锁恢复

撤销进程
剥夺资源

8 内存管理

内存管理基本概念

内存管理涉及的个体：内核，进程
基本功能：
- 为进程分配内存空间；
- 管理内存空间；
- 物理内存不足时，结合外存空间

地址绑定

将各种类型的地址形式最终对应到物理内存中的绝对地址

地址绑定时机

编译时绑定
加载时绑定
运行时绑定

地址重定位

静态重定位
- 优点：容易实现，无需硬件支持。
- 缺点：程序经地址重定位后就不能移动了，因而不能重新分配内存，不利于内存的有效利用；必须占用连续的内存空间，这就难以做到程序和数据的共享。
动态重定位
- 优点：可以对内存进行非连续分配；提供了实现虚拟存储的基础；有利于程序段的共享
- 需要附加的硬件支持；实现存储管理的软件算法比较复杂

内存分配

9 虚拟内存

页错误（Page Fault）

访问无效页时，产生 Page Fault，陷入 OS：

检查内部页表：

非法访问 -> 终止
不在内存中 -> 步骤 2

找到一个空闲帧

如果有空闲帧，使用之
如果没有空闲帧，选择一个作为 victim 换入外存

换入页到该帧中
修改表
修改 validation 位
重新开始因陷阱而中断的指令

页置换算法

FIFO

可能发生 Belady 现象，即分配的页面数增多，缺页次数反而增加

Optimal (OPT) Algorithm

当需要淘汰某一页时，算法选择在访问串中将来再也不出现的或者是在离当前最远的位置上出现的页

Least Recently Used (LRU) Algorithm

选择离当前时间最近的一段时间内最久没有使用过的页先淘汰。

10 文件系统接口

目录结构

单层结构

一个目录对应所有的用户
不允许有同名的文件
没有分组功能

双层结构

目录分为 2 级：主目录和用户文件目录
不同用户可以为文件取相同名字
有效搜索
没有分组功能

树状结构

有效搜索
支持分组
路径名一般较长

无环图结构

11 文件系统实现

文件系统分层结构

自下而上：

最底层：对 I/O 设备的控制
- 设备驱动程序 + 中断处理程序
基本文件系统
- 完成以物理块为单位的数据读写
文件组织模块
- 知道文件的逻辑块和物理块
- 根据文件的空间分配类型以及文件的位置，该模块可以完成逻辑块地址到物理块地址的转换
- 该模块也包含空闲空间管理模块
逻辑文件系统
- 管理文件系统元数据
- 通过文件控制块（FCB）来维护文件结构

虚拟文件系统

Virtual File Systems (VFS)
虚拟文件系统是按照面向对象的设计理念来提供操作系统的多文件系统支持
VFS 提供一套统一的文件系统访问接口

空间分配方法

连续空间分配

顺序存取速度快
所需磁盘寻道次数和时间最少
简单，只需记录起始块号和文件长度
很方便地支持随机访问

缺点：

要求有连续的存储空间
必须事先知道文件的长度，以后不能动态增长
不利于文件插入和删除
外部碎片问题

链式分配

每个磁盘块中留出一个指针地址，用来进行块间链接
链接方式实现简单，一个文件只需要记录其起始地址（起始块号）
浪费空间较少

缺点：不支持随机访问

索引分配

文件的信息存放在若干不连续物理块中，系统为每个文件建立一个专用数据结构--索引表，并将这些块的块号存放在一个索引表中
既可以满足文件动态增长的要求，又可以较为方便和迅速地实现随机存取。

缺点：

由于使用了索引表而增加了存储空间的开销。
在存取文件时需要至少访问存储器二次以上。其中，一次是访问索引表，另一次是根据索引表提供的物理块号访问文件信息。由于文件在存储设备的访问速度较慢，因此，如果把索引表放在存储设备上，势必大大降低文件的存取速度。

空闲块管理方法

空闲空间表

为所有的空白文件建立一个目录，即空白文件目录，每个表项对应一个由多个空闲块组成的空闲区。
这种方法仅当有少量空白文件时才有较好的效果。如果存储空间中有大量的小的空白文件，则使该目录变得很大，因而效率大为降低。这种管理技术适用于连续分配。

空闲块链

把文件存储设备上的所有空闲块链接在一起

位示图法

12 大容量存储器的结构

磁盘调度

FCFS

SSTF

最短寻道时间优先：选择与磁头位置最近的待处理请求
可能会产生饥饿

SCAN 电梯算法

磁臂从磁盘的一端向另一端移动，当磁头移过每一个柱面时，处理位于该柱面上的请求服务。当到达另一端时，改变方向继续处理。

C-SCAN

返回时不处理请求，而是马上回到磁盘开始

LOOK/C-LOOK

只移动到某个方向上最远的请求，而不是移动到磁盘的尽头

旋转优化

为了减少旋转延迟，对同一磁道上的连续读写信息进行合理分布称为旋转优化。

13 I/O 输入系统

数据传送控制方式

程序直接控制方式

一种循环 I/O 测试方式，通过执行 I/O 测试指令测试设备忙/闲标志以确定是否进行数据传输。高速 CPU 和慢速 I/O 设备矛盾突出，CPU 浪费严重，一般出现在早期计算机或者现在微机系统中。

中断控制方式

当 I/O 操作正常或异常结束时中断 CPU，从而实现了 I/O 设备和 CPU 间一定程度的并行操作，改善了 CPU 的利用率，适用于字符设备的 I/O。

DMA 方式

在外围设备和内存之间开辟直接的数据交换通道进行数据传输，适用于块设备的 I/O。

通道方式

使用通道来控制内存或 CPU 和外围设备之间的数据传输。大大提高了 CPU 和外设之间的并行能力，可把种类繁多，物理特性各异的外设以标准的接口方式连接到系统中。

缓冲技术

缓冲技术是利用空间来换取时间