操作系统

1 操作系统概述

1.1 操作系统概念

硬件抽象层（HAL）：硬件抽象层是位于操作系统 内核与硬件电路之间的接口层，其目的在于将硬件抽象化。它隐藏了特定平台的硬件接口细节,为操作系统提供虚拟硬件平台,使其具有硬件无关性,可在多种平台上进行移植。 从软硬件测试的角度来看，软硬件的测试工作都可分别基于硬件抽象层来完成，使得软硬件测试工作的并行进行成为可能。

操作系统运行视图：

操作系统的作用：管理系统中的软硬件资源；为用户（应用程序）提供良好的服务。

操作系统定义：是位于硬件层(HAL)之上，所有其它软件层之下的一个系统软件，是管理系统中各种硬/软件资源，方便用户使用计算机系统的程序集合。

1.2 操作系统的历史

1.2.2 操作系统的完善

1. 多道批处理系统
2. 分时系统
3. 实时处理系统
4. 通用操作系统

1.2.3 操作系统的发展

1.计算机体系结构由集中向分散的发展，出现了计算机网络，由此产生网络操作系统和分布式操作系统；

2.随着家用和商用微型计算机的普及，出现了单用户多任务的操作系统；

3.大型计算任务要求计算机系统具有极强的计算和处理能力，产生了支持多处理器的并行操作系统；

4.随着各种处理器芯片和存储介质在控制领域的广泛应用，要求操作系统具有专用的特性，出现了微内核操作系统体系结构，如嵌入式和智能卡系统；

5.随着芯片集成度的提高，提高单处理器速度已近极限，多核技术应运而生。新一代操作系统遇到的问题：多核的并发控制；多核下的进程调度。

1.3 操作系统的特性

1. 程序并发性。
2. 资源共享性
3. 程序异步性。中断随机发生，致使程序切换不确定，不可预知。
4. 虚拟性。利用虚拟技术把一个物理实体变为若干个逻辑实体；
   如：多道程序系统

        虚拟存储管理技术
        虚拟设备管理
   

1.4 操作系统的分类

只说那些重要的。

1. 单用户操作系统
   特点：单用户，多进程，多线程。
2. 网络操作系统
   提供网络服务：database server; ftp server; e-mail server; telnet server
3. 分布式操作系统：
   特点：统一OS；资源共享；可靠性；透明性
4. 多处理机操作系统：多个CPU
5. 嵌入式操作系统：微内核结构（Micro-kernel）

1.5 操作系统的硬件环境

定时装置产生中断，造成处理器状态转化，把一些信息压入系统栈，当程序要访问存储器时，就需要地址映射机构，寄存器和存储保护设施，当要进行I/O时，就需要通道与DMA控制器和I/O保护，程序的所有与硬件相关的资源相关的操作都要特权指令与非特权指令。

2 进程，线程与作业

2.1 多道程序设计

道数少造成资源利用率低，道数多造成系统开销大，程序响应速度低。

2.2 进程的引入

多道系统中的程序不断地暂停于推进：
暂停：保存现场（PSW+PC，寄存器）
推进：回复现场（寄存器，PSW+PC）

程序暂停的原因：
（1）自身原因：等待资源，启动I/O
（2）剥夺CPU

进程定义：可参与并发执行的程序称为进程。
强调：动态：执行中的程序
并发：可与其他进程同时执行

进程状态（基本状态）：
运行态（RUN）
就绪态（READY）
等待态（WAIT）

2.3 进程控制块

PCB：标志进程存在的数据结构，其中保存系统管理进程所需的全部信息

PCB的内容：

进程的组成：
1.PCB
2.程序：代码(code)；数据(data)；堆栈(stack+heap)
只表示进程的静态特征。

进程的队列：

2.4 进程的类型

系统进程
用户进程

2.5 进程的创建与撤销

除了初始进程外，其他进程都由父进程创建

2.6 线程及其控制块

什么是线程：对于一个任务，它有多个并发运行的子任务，由于子任务间耦合较为紧密，所以用进程来描述子任务非常不合适。一个线程是单一顺序的控制流，所有线程协同执行不同的角色。

线程的引入：
同一进程中包含多个线程
多个线程共享进程代码，数据，堆
线程上下文只涉及寄存器和栈，切换速度块
相关线程之间通讯方便，快捷

进程与线程的区别：

多进程结构：

多线程结构：

TCB：Thread Control Blolck 线程控制块

2.7 线程的实现

用户级别线程：User-level thread
核心级别线程：Kernel-level thread

3 中断与处理器调度

3.1 中断与中断系统

中断装置：

中断响应与处理基本过程：

中断源与中断字

中断类型：强迫性中断与自愿性中断

中断向量表

中断优先级

中断屏蔽

中断处理程序（把PSW和PC处理完之后）：

用户处理中断的过程：中断续元表

3.2 处理机调度

考虑因素：scheduling criteria：

几个处理机调度算法

处理机调度时机：4个时机

3.3 调度级别与多级调度

交换（swap）与中级调度（mid-level scheduling）：目的是控制并发度

作业与高级调度

3.4 实时调度

周期性实时任务可调度的判断：

最早截止期优先调度

速率单调调度

3.5 Linux进程调度

自旋锁用于多处理机系统中，将核心分为若干相对独立的部分，不同的CPU可以同时进入和执行核心中的不同部分，实现时可以为每个相对独立的区域设置一个自旋锁。

4 互斥，同步与通信

4.1 并发进程

前驱图

程序的顺序性

程序的并发性

程序并发执行的条件：Bernstein条件：P1和P2无前驱关系，则可以并发执行

4.2 进程互斥

临界区管理原则：

进程互斥的硬件实现：test_and_set，不满足有限等待性

满足有限等待性的test_and_set

多处理机的互斥：锁总线

4.3 进程同步

一组进程，为协调其推进速度，在某些关键点处需要相互等待与相互唤醒，进程之间这种相互制约的关系称为进程同步，简称同步(Synchronization)。

典型同步机制：
信号量与P/V操作
条件临界区
管程

生产者和消费者问题：互斥与同步的实现：

生产者与消费者问题，并发性提高策略：

读者与写者问题：

管程有等待/唤醒机制：wait, signal

唤醒时有3中处理方法（P唤醒Q）：

1. P等待，Q运行，直到Q退出或等待（Hoare）
2. Q等待，P继续，直到P退出或等待（Java）
3. 唤醒是管程中可执行的最后一个操作（Hansen）

磁头引臂调度问题：

5 死锁与饥饿

5.1 死锁的概念

5.2 死锁的类型

5.3 死锁的条件

5.4 死锁的处理

死锁预防：静态，进程有关资源的活动按照某种协议加以限制

死锁避免：动态，实时检测进程的资源申请，拒绝不安全的请求，保证不发生死锁。

5.5 资源分配图

5.6 死锁预防

5.7 死锁避免

安全状态与安全进程序列

银行家算法

死锁检测算法：本质上是资源分配图的约简算法

6 存储管理

7 文件系统

7.2 文件的访问方式

顺序访问

随机访问

7.3 文件的组织

逻辑组织：外部组织形式，用户看到的组织形式

物理组织：内部组织形式，物理存储设备上的组织形式

OS完成逻辑组织形式到物理组织形式的转换

文件的逻辑组织：
流式文件：文件由字节序列组成
记录式文件：记录的序列

物理组织：
逻辑组织到磁盘块的映射
顺序结构：一个文件占有若干连续的磁盘块
链接结构
索引结构：inode
散列结构
倒排结构

文件的物理组织与内存存储管理（页式，段式等）相似。

7.4 文件控制块

每一个文件有一个FCB，保存在外存中。
打开文件时，将FCB读入内存

目录项：
目录文件中的一项，内容为FCB

文件目录的改进：

7.7 文件系统的实现

7.7.1 内存所需表目

7.7.2 外存空间管理

成组链接方式：空闲块表与空闲块链的结合

外存空间管理（成组链接等）与空闲内存管理（位示图等）相似

外存空间有导引快，超级块（就是成组链接中的超级块，磁盘中有一块，内存中也有相同内容的一块），inode区域（保存所有文件的inode），目录与文件区。

专业英语

1 操作系统概述

HAL：Hardware Abastraction Layer; 硬件抽象层

Micro-kernel：微内核，用于嵌入式操作系统

2 进程，线程与作业

PSW：Program Status Word 程序状态字；可用于OS在管态（系统态）和目态（用户态）之间的转换；PSW用来存放两类信息：一类是体现当前指令执行结果的各种状态信息，另一类是存放控制信息，称为控制状态，如允许中断(IF位)

PC：Program Counter 程序计数器。

PCB：Process Control Block 进程控制块

Process Context：进程上下文

TCB：Thread Control Block 线程控制块

User-level thread

Kernel-level thread

3 中断与处理器调度

interrupt：中断

interrupt mask：中断屏蔽

CPU burst cycle：CPU阵发期

CPU burst time：

I/O burst cycle

preemptive：剥夺式

FCFS：First Come First Serve。先到先服务

SJF：Shortest Job First 最短作业优先算法

SRTN：Shortest Remaining Time Next 最短剩余时间优先

HRN：Highest Response Ratio Next 最高响应比优先

HPF：Highest Priority First 最高优先数

RR：Round Robin 循环轮转算法

MLQ：Multi-Level Queues 分类排队算法

FB：Feed-Back 反馈排队算法

degree of multi-programming：并发度

swapping：交换

mid-level scheduling：中级调度

Real-time Scheduling：实时调度

Starting deadline：开始截止期

Processing time：处理时间

Completion deadline：完成截止期

EDF：Earliest Deadline First 最早截止期优先调度

RMS：Rate Monotonic Scheduling 速率单调调度

spin_lock：自旋锁

4 互斥，同步与通信

Bernstein条件

shared variable：共享变量

critical region：临界区

mutual exclusion：互斥性

progress：进展性

bounded waiting：有限等待性

test_and_set：进程互斥的硬件实现

Bus-locking ：锁总线

Bus-unlocking：总线解锁

Synchronization：进程同步

Primitive：原语，一段不可间断执行的程序

semaphore：信号量

monitor：管程

LOOK：elevator algorithm 电梯算法（磁头引臂调度问题）

IPC：Inter-Process Communication 进程通信

memory sharing：共享内存

message passing：消息传递

buffering：有缓冲途径

non-buffering：无缓冲途径

5 死锁与饥饿

deadlock：死锁

mutual exclusion：资源独占

non preemption：不可抢占

hold-and-applying：保持申请

circular wait：循环等待

deadlock prevention：死锁预防

deadlock avoidance：死锁避免

deadlock detection：死锁检测

deadlock revovery：死锁恢复

Banker’s algorithma：银行家算法

6 存储管理

First Fit：首次适应（动态异长的分区分配算法）

Best Fit：最佳适应

Worst Fit：最坏适应

Next Fit：邻近适应

OPT：最佳置换算法

FIFO：先进先出置换算法

LRU：Least Recently Used 最近最少使用算法

CLOCK：时钟置换算法（NRU，Not Recently Used，最近未用算法）

赏

谢谢你请我吃糖果