操作系统学习笔记

第一章

操作系统的特征

• 并发
• 共享
  • 互斥共享方式
  • 同时共享方式
• 虚拟
  • 空分复用技术
  • 时分复用技术
• 异步

操作系统的发展与分类

• 手工操作阶段
• 批处理系统阶段
• 分时操作系统
• 实时操作系统
• 网络操作系统
• 分布式操作系统
• 个人计算机操作系统

操作系统的运行机制

中断和异常

CPU 上会运行两种程序，一种是操作系统内核程序，一种是应用程序

在合适的情况下，操作系统内核会把 CPU 的使用权主动让给应用程序（第二章进程管理相关内容）“中断”是让操作系统内核夺回 CPU 使用权的唯一途径

中断的类型：

• 内中断（来自 CPU 内部，也称 “异常”）：陷阱、陷入（trap）、故障、终止
• 外中断（来自 CPU 外部，也称 “中断”）：时钟中断…

不同的中断信号，需要用不同的中断处理程序来处理。当 CPU 检测到中断信号后，会根据中断信号的类型去查询“中断向量表”，以此来找到相应的中断处理程序在内存中的存放位置。

系统调用

操作系统作为用户和计算机硬件之间的接口，需要向上提供一些简单易用的服务。主要包括命令接口和程序接口。其中，程序接口由一组系统调用组成。

“系统调用”是操作系统提供给应用程序（程序员/编程人员）使用的接口，可以理解为一种可供应用程序调用的特殊函数，应用程序可以通过系统调用来请求获得操作系统内核的服务

系统调用（按照功能分类）:

• 设备管理
• 文件管理
• 进程控制
• 进程通信
• 内存管理

可以了解 Linux 系统调用

操作系统的体系结构

主要通过一些结构图来介绍：

操作系统引导

操作系统引导：

1. CPU 从一个特定主存地址开始，取指令，执行 ROM 中的引导程序（先进行硬件自检，再开机）
2. 将磁盘的第一块，主引导记录 读入内存，执行磁盘引导程序，扫描分区表
3. 从活动分区（又称主分区，即安装了操作系统的分区）读入分区引导记录，执行其中的程序
4. 从根目录下找到完整的操作系统初始化程序（即启动管理器）并执行，完成“开机”的一系列动作

第二章

进程的概念、组成、特征

• 操作系统要记录 PID、进程所属用户 ID（UID）

• 这些信息都被保存在一个数据结构 PCB（Process Control Block） 中，即进程控制块操作系统需要对各个并发运行的进程进行管理，但凡管理时所需要的信息，都会被放在 PCB 中

进程的状态和状态转换

在进程运行的过程中，可能会请求等待某个事件的发生（如等待某种系统资源的分配，或者等待其他进程的响应）。

在这个事件发生之前，进程无法继续往下执行，此时操作系统会让这个进程下 CPU，并让它进入“阻塞态”

进程 PCB 中，会有一个变量 state 来表示进程的当前状态。如：1 表示创建态、2 表示就绪态、3 表示运行态..

• 进程的组织—索引方式
• 进程的组织—连接方式

进程控制

原语的执行具有原子性，即执行过程只能一气呵成，期间不允许被中断。可以用“关中断指令”和“开中断指令”这两个特权指令实现原子性

进程间通信 IPC

进程间通信（Inter-ProcessCommunication，IPC） 是指两个进程之间产生数据交互。

通信方式：

• 共享存储
  • 基于数据结构的共享
  • 基于存储区的共享
• 消息传递
  • 直接通信
  • 间接通信
• 管道通信

管道通信的实现是 FIFO 的，和共享内存存在区别，但是本质上也是一段内存缓冲区。
可以看作是一个循环队列的数据结构。

• 管道只能采用半双工通信，某一时间段内只能实现单向的传输。如果要实现双向同时通信，则需要设置两个管道。

• 各进程要互斥地访问管道（由操作系统实现）

• 当管道写满时，写进程将阻塞，直到读进程将管道中的数据取走，即可唤醒写进程。

• 当管道读空时，读进程将阻塞，直到写进程往管道中写入数据，即可唤醒读进程。

• 管道中的数据一旦被读出，就彻底消失。因此，当多个进程读同一个管道时，可能会错乱。对此，通常有两种解决方案：

  1. 一个管道允许多个写进程，一个读进程（2014 年 408 真题高教社官方答案）；
  2. 允许有多个写进程，多个读进程，但系统会让各个读进程轮流从管道中读数据（Linux 的方案）。

线程的概念与特点

可以把线程理解为“轻量级进程”。

线程是一个基本的 CPU 执行单元，也是程序执行流的最小单位。引入线程之后，不仅是进程之间可以并发，进程内的各线程之间也可以并发，从而进一步提升了系统的并发度，使得一个进程内也可以并发处理各种任务（如 QQ 视频、文字聊天、传文件）

引入线程后，进程只作为除 CPU 之外的系统资源的分配单元（如打印机、内存地址空间等都是分配给进程的）。

线程的实现方式—多线程模型

用户级线程（User-Level Thread, ULT）
历史背景：早期的操作系统（如：早期 Unix）只支持进程，不支持线程。当时的“线程”是由线程库实现的

一些问题：

1. 线程的管理工作由谁来完成？
2. 线程切换是否需要 CPU 变态？
3. 操作系统是否能意识到用户级线程的存在?
4. 这种线程的实现方式有什么优点和缺点？

答案：

1. 用户级线程由应用程序通过线程库实现，所有的线程管理工作都由应用程序负责（包括线程切换）
2. 用户级线程中，线程切换可以在用户态下即可完成，无需操作系统干预。
3. 在用户看来，是有多个线程。但是在操作系统内核看来，并意识不到线程的存在。“用户级线程”就是“从用户视角看能看到的线程”
4. 优缺点
   • 优点：用户级线程的切换在用户空间即可完成，不需要切换到核心态，线程管理的系统开销小，效率高
   • 缺点：当一个用户级线程被阻塞后，整个进程都会被阻塞，并发度不高。多个线程不可在多核处理机上并行运行。

内核级线程（Kernel-LevelThread,KLT,又称“内核支持的线程”）

一些问题：

1. 线程的管理工作由谁来完成?
2. 线程切换是否需要 CPU 变态？
3. 操作系统是否能意识到内核级线程的存在?
4. 这种线程的实现方式有什么优点和缺点？

答案：

1. 内核级线程的管理工作由操作系统内核完成。
2. 线程调度、切换等工作都由内核负责，因此内核级线程的切换必然需要在核心态下才能完成。
3. 操作系统会为每个内核级线程建立相应的 TCB（Thread Control Block，线程控制块），通过 TCB 对线程进行管理。“内核级线程”就是“从操作系统内核视角看能看到的线程”
4. 优缺点
   • 优点：当一个线程被阻塞后，别的线程还可以继续执行，并发能力强。多线程可在多核处理机上并行执行。
   • 缺点：一个用户进程会占用多个内核级线程，线程切换由操作系统内核完成，需要切换到核心态，因此线程管理的成本高，开销大。

重点重点重点：操作系统只“看得见”内核级线程，因此只有内核级线程才是处理机分配的单位。

线程的状态与转换

处理机调度的基本概念、层次

作业：一个具体的任务

用户向系统提交一个作业≈用户让操作系统启动一个程序（来处理一个具体的任务）

高级调度（作业调度）。按一定的原则从外存的作业后备队列中挑选一个作业调入内存，并创建进程。每个作业只调入一次，调出一次。作业调入时会建立 PCB，调出时才撤销 PCB。

低级调度（进程调度/处理机调度）— 按照某种策略从就绪队列中选取一个进程，将处理机分配给它。

中级调度（内存调度）— 按照某种策略决定将哪个处于挂起状态的进程重新调入内存。

注意“挂起”和“阻塞”的区别，两种状态都是暂时不能获得 CPU 的服务，但挂起态是将进程映像调到外存去了，而阻塞态下进程映像还在内存中。
有的操作系统会把就绪挂起、阻塞挂起分为两个挂起队列，甚至会根据阻塞原因不同再把阻塞挂起进程进一步细分为多个队列。

进程调度的时机 切换与过程调度方式

临界区的概念

临界资源：一个时间段内只允许一个进程使用的资源。各进程需要互斥地访问临界资源。临界区：访问临界资源的那段代码。

内核程序临界区一般是用来访问某种内核数据结构的，比如进程的就绪队列（由各就绪进程的 PCB 组成）

进程调度方式

非剥夺调度方式，又称非抢占方式。即，只允许进程主动放弃处理机。在运行过程中即便有更紧迫的任务到达，当前进程依然会继续使用处理机，直到该进程终止或主动要求进入阻塞态。

剥夺调度方式，又称抢占方式。当一个进程正在处理机上执行时，如果有一个更重要或更紧迫的进程需要使用处理机，则立即暂停正在执行的进程，将处理机分配给更重要紧迫的那个进程。

• 可以优先处理更紧急的进程，也可实现让各进程按时间片轮流执行的功能（通过时钟中断）。适合于分时操作系统、实时操作系统

调度器、闲逛进程

调度程序永远的备胎，没有其他就绪进程时，运行闲逛进程（ide）

闲逛进程的特性：

• 优先级最低
• 可以是 0 地址指令，占一个完整的指令周期（指令周期末尾例行检查中断）
• 能耗低

调度算法的评价指标

• cpu 利用率
• 系统吞吐量
• 周转时间

对于计算机的用户来说，他很关心自己的作业从提交到完成花了多少时间。
周转时间，是指从作业被提交给系统开始，到作业完成为止的这段时间间隔。

• 等待时间
• 响应时间

调度算法

Tips：各种调度算法的学习思路

1. 算法思想
2. 算法规则
3. 这种调度算法是用于作业调度还是进程调度？
4. 抢占式？非抢占式?
5. 优点和缺点
6. 是否会导致饥饿: 某进程/作业长期得不到服务

先来先服务（FCFS）

短作业优先（SJF）

高响应比优先（HRRN）

注：这几种算法主要关心对用户的公平性、平均周转时间、平均等待时间等评价系统整体性能的指标，但是不关心“响应时间”，也并不区分任务的紧急程度，因此对于用户来说，交互性很糟糕。因此这三种算法一般适合用于早期的批处理系统，当然，FCFS 算法也常结合其他的算法使用，在现在也扮演着很重要的角色。而适合用于交互式系统的调度算法将在下个小节介绍..

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

如果时间片太大，使得每个进程都可以在一个时间片内就完成，则时间片轮转调度算法退化为先来先服务调度算法，并且会增大进程响应时间。因此时间片不能太大。

另一方面，进程调度、切换是有时间代价的（保存、恢复运行环境），因此如果时间片太小，会导致进程切换过于频繁，系统会花大量的时间来处理进程切换，从而导致实际用于进程执行的时间比例减少。可见时间片也不能太小。

优先级调度算法

就绪队列未必只有一个，可以按照不同优先级来组织。另外，也可以把优先级高的进程排在更靠近队头的位置
根据优先级是否可以动态改变，可将优先级分为静态优先级和动态优先级两种。
静态优先级：创建进程时确定，之后一直不变。
动态优先级：创建进程时有一个初始值，之后会根据情况动态地调整优先级。

通常：
系统进程优先级高于用户进程
前台进程优先级高于后台进程

操作系统更偏好 I/O 型进程（或称 I/O 繁忙型进程）
注：与 I/O 型进程相对的是计算型进程（或称 CPU 繁忙型进程）

I/O 设备和 CPU 可以并行工作。如果优先让 I/O 繁忙型进程优先运行的话，则越有可能让 I/O 设备尽早地投入工作，则资源利用率、系统吞吐量都会得到提升

可以从追求公平、提升资源利用率等角度考虑
如果某进程在就绪队列中等待了很长时间，则可以适当提升其优先级
如果某进程占用处理机运行了很长时间，则可适当降低其优先级
如果发现一个进程频繁地进行 I/o 操作，则可适当提升其优先级

多级反馈队列调度算法

注：比起早期的批处理操作系统来说，由于计算机造价大幅降低，因此之后出现的交互式操作系统（包括分时操作系统、实时操作系统等）更注重系统的响应时间、公平性、平衡性等指标。而这几种算法恰好也能较好地满足交互式系统的需求。因此这三种算法适合用于交互式系统。（比如 UNIX 使用的就是多级反馈队列调度算法）

多级队列算法

同步、互斥的基本概念

进程具有异步性的特征。异步性是指，各并发执行的进程以各自独立的、不可预知的速度向前推进。

同步亦称直接制约关系，它是指为完成某种任务而建立的两个或多个进程，这些进程因为需要在某些位置上协调它们的工作次序而产生的制约关系。进程间的直接制约关系就是源于它们之间的相互合作。

我们把一个时间段内只允许一个进程使用的资源称为临界资源。许多物理设备（比如摄像头、打印机）都属于临界资源。此外还有许多变量、数据、内存缓冲区等都属于临界资源。

对临界资源的访问，必须互斥地进行。互斥，亦称间接制约关系。进程互斥指当一个进程访问某临界资源时，另一个想要访问该临界资源的进程必须等待。当前访问临界资源的进程访问结束，释放该资源之后，另一个进程才能去访问临界资源。

1. 空闲让进。临界区空闲时，可以允许一个请求进入临界区的进程立即进入临界区；
2. 忙则等待。当已有进程进入临界区时，其他试图进入临界区的进程必须等待：
3. 有限等待。对请求访问的进程，应保证能在有限时间内进入临界区（保证不会饥饿）；
4. 让权等待。当进程不能进入临界区时，应立即释放处理机，防止进程忙等待。

进程互斥的软件控制算法

单标志法

双标志先检查法

双标志后检查法

Peterson 算法

Peterson 算法用软件方法解决了进程互斥问题，遵循了空闲让进、忙则等待、有限等待三个原则，但是依然未遵循让权等待的原则。

进程互斥的硬件实现方法

互斥锁

互斥锁的主要缺点是忙等待。
需要连续循环忙等的互斥锁，都可称为自旋锁（spin lock），如 TSL 指令、swap 指令、单标志法

信号量机制

存在的问题：不满足“让权等待”原则，会发生“忙等”

用信号量实现进程互斥、同步、前驱关系

生产者消费者问题

多生产者、多消费者问题

哲学家进餐问题

管程

管程是一种特殊的软件模块，有这些部分组成：

1. 局部于管程的共享数据结构说明；
2. 对该数据结构进行操作的一组过程：
3. 对局部于管程的共享数据设置初始值的语句；
4. 管程有一个名字。

管程的基本特征：

1. 局部于管程的数据只能被局部于管程的过程所访问；
2. 一个进程只有通过调用管程内的过程才能进入管程访问共享数据；
3. 每次仅允许一个进程在管程内执行某个内部过程。

死锁的概念

在并发环境下，各进程因竞争资源而造成的一种互相等待对方手里的资源，导致各进程都阻塞，都无法向前推进的现象，就是“死锁”。发生死锁后若无外力干涉，这些进程都将无法向前推进。

预防死锁

该策略的缺点：并不是所有的资源都可以改造成可共享使用的资源。并且为了系统安全，很多地方还必须保护这种互斥性。因此，很多时候都无法破坏互斥条件。

避免死锁

死锁的检测和解除

不能消除所有的边，说明发生了死锁
最终还连着边的那些进程就是处于死锁状态的进程。

第三章

内存的基础知识

内存管理的概念

进程的内存映像

覆盖与交换

连续分配管理方式

动态分区分配算法

首次适应算法

最佳适应算法

最坏适应算法

临近适应算法

基本分页存储管理的基本概念

Tips：初学易混——页、页面vs 页框、页帧、物理页页号、页面号vs页框号、页帧号、物理页号
注意区分这里的区别。

为了能知道进程的每个页面在内存中存放的位置，操作系统要为每个进程建立一张页表。注：页表通常存在 PCB（进程控制块）中

基本地址变换机构

具有快表的地址变换机构

快表，又称联想寄存器（TLB，translation lookaside buffer），是一种访问速度比内存快很多的高速缓存（TLB 不是内存！），用来存放最近访问的页表项的副本，可以加速地址变换的速度。与此对应，内存中的页表常称为慢表。

两级页表

基本分段存储管理方式

段页式管理方式

“分段”对用户是可见的，程序员编程时需要显式地给出段号、段内地址。而将各段“分页”对用户是不可见的。系统会根据段内地址自动划分页号和页内偏移量。
因此段页式管理的二维的

虚拟内存的基本概念

请求分页管理方式

页面置换算法

该算法的实现需要专门的硬件支持，虽然算法性能好，实现困难，开销大

页面分配策略

内存映射文件

第四章

文件管理

文件的逻辑结构

文件目录

文件的物理结构

读取某个磁盘块时，需要移动磁头。访问的两个磁盘块相隔越远，移动磁头所需时间就越长。

结论：连续分配的文件在顺序读/写时速度最快

FAT 表

文件存储空间管理

成组链接法

文件的基本操作

文件共享

文件保护

第五章

I/O 设备的概念和分类

I/O 控制器

I/O 控制方式

I/O 软件层次结构

I/O 核心子系统

假脱机技术

设备的分配的回收

缓冲区管理