《操作系统教程》概述

3.4 进程控制
3.3.3 进程状态和转换
三状态：

五状态：

七状态：

3.3.4 进程控制块（PCB）
· 是一个操作系统为管理进程设置的数据结构
· 是进程存在的唯一标识
· 作用：
- 进程的创建：为该进程创理一个PCB
- 进程的终止：回收它的PCB
- 进程的组织管理：通过对PCB的组织管理实现
· 内容：
1. 进程描述信息。如本进程的标识；它的父进程标识；用户标识。
2. 进程控制信息。进程当前状态，优先级，进程间同步和通信等。
3. 所拥有的资源和使用情况。
4. CPU现场保护信息。

· 多采用链表的组织方式。可以更好地完成动态插入删除。如果比较固定，也可以采用索引表方式。

3.4.1 进程创建
引起创建的三个主要事件：
1. 系统初始化时；
2. 用户请求创建一个新进程
3. 正在运行的进程执行了创建进程的系统调用
fork():

0 : 在父进程中，返回值为子进程的id值
0： 在子进程中，返回值为0，表示当前进程是子进程
-1：创建失败

3.4.2进程的阻塞和唤醒

3.6 处理器调度
三级调度
1. 高级调度（作业调度、宏观调度、长程调度）
任务：将作业从后备队列中装人内存
2. 中级调度（平衡负载调度、中程调度）
任务：内存资源紧张的时候，将一些进程换出主存，使之进入挂起态。调整系统负荷。
3. 低级调度（进程调度、短程调度）
任务：按照某种原则决定就绪队列中的哪个进程获得CPU

3.7 作业的管理和调度
作业
· 定义：用户需要计算机完成某项任务时要求计算机所做工作的集合。
· 四个阶段：
1. 作业提交：从输入设备到外存的后备队列中
2. 作业收容：后备队列中等待进入内存执行
3. 作业执行：在内存中执行
4. 作业完成
· 作业和进程区别：
1. 作业是用户向计算机提交的任务实体；
进程是完成任务的执行实体，是向系统申请分配资源的基本单位
2. 作业由若干进程组成
3. 作业的概念主要用于批处理系统；
进程的概念用于所有的多道程序系统中

两个指标：
1. 作业平均周转时间：
假设n个作业，其中作业i进入系统时间为Si，它被选中执行，得到结果的时间（完成时间）为Ei，其周转时间为Ti = Ei - Si，则这批作业平均周转时间为T = （T1 + T2 + … + Tn）/ n
· 有时间单位
· Ti不是完成时间 - 进入内存时间（开始时间）
2. 平均带权周转时间：
ri为作业i的实际执行时间。则带权周转时间为Wi = Ti/ri
W = （T1/r1 + T2/r2 + … + Tn/rn）/n
· 是一个比值，没有时间单位
注：T 不同调度算法对同一个作业流的性能衡量；W 同一调度算法对不同作业流的性能衡量。

作业调度算法
1. FCFS算法（先来先服务调度算法）
根据作业提交的先后次序分派CPU
2. SJF算法（短作业优先调度）
根据作业的估计运行时间分派CPU
3. HRN算法（高响应比调度）
相应比R = 作业周转时间/作业运行时间 = 1+等待时间/(估计)运行时间
4. HPF算法（基于优先数调度）
5. 均匀调度算法
6. 最短剩余时间优先调度算法

3.9 线程
目的：将进程以更细的粒度切分，以低开销进一步提高系统并发度。
定义：轻量级进程，是进程的一个运行实体，作为CPU的调度单位。

线程资源：
· 系统引入线程后：
- 调度单位——线程
- 资源分配单位——进程
· 线程只拥有少量在运行时必不可少的资源
· 同一个进程中的所有线程共享进程的地址空间和资源

线程和进程比较：
【资源】进程是资源分配的基本单位；同进程内的线程共享进程的资源
【调度时】不同进程有不同地址空间；同个进程内所有线程有相同地址空间
【开销】进程切换开销大；同进程的线程切换开销小
【关系】进程间关系较疏远；同进程的线程间关系较紧密

线程的优越性：
1. 快速关联切换
2. 系统开销小
3. 通信易实现
4. 线程个数比进程多的多

4.5 死锁
死锁检测
进程资源分配图如下：

- 图中，如果能消去此进程的所有边，成为孤立结点。经一系列简化，所有进程都成为孤立结点，则该图是可完全简化的，否则为不可完全简化的。
- 【死锁定理】系统为死锁的充分条件是：当且仅当该状态的“进程-资源分配图”是不可完全简化的。

死锁的解除：
1. 资源剥夺法。从其他进程那里剥夺资源给死锁进程。
2. 撤销进程法。撤销死锁进程。

第五章 存储管理
5.1 分区存储管理
· os中的离散和连续是物理空间上的分配，而DS中的链表和数组是逻辑空间上的分配。

分类：（根据划分分区的时机不同）
· 连续分配
- 固定分区分配
· 内存启动时，划分成若干个大小固定的分区，每个进程占一个分区
· 固定：分区个数固定；分区大小固定（大小相等；不相等）

- 可变（动态）分区分配
基本思想：
作业执行过程中，根据作业大小找到一个空闲的分区，并进行划分。
分配算法：
1）首次适应法：
· 思想：空闲分区地址递增排列。进行分配时，从空闲分区开始位置查找，直到第一个满足大小要求的分区，再按照作业大小划分出一块。
· 特点：保留了内存高地址部分大的空闲分区；低地址部分存在许多碎片。
2）循环首次适应法（下次适应法）：
· 思想：首次适应法的变形。进行内存分配时，从上次找到的空闲分区的下一个空闲区开始查找
· 特点：对存储空间利用更均衡；没有保留大的空闲分区
3）最佳适应法：
· 思想：空闲分区容量递增排列。从开始位置开始查找
· 特点：没有保留大的空闲分区；划分后有许多碎片
4）最坏适应法：
· 思想：空闲分区容量递减排列。只检查第一个空闲分区。
· 特点：没有保留大的空闲分区；每次只用查第一个空闲分区
回收算法：
根据回收区与空闲分区的位置关系，分为四种情况。回收后系统中空闲分区个数不同。

· 离散分配
- 分页式存储管理
- 分段式存储管理
- 段页式存储管理

· 分区移动技术：合并分散的小空闲分区 —> 大空闲分区。允许作业在运行过程中在内存中移动，必须采用动态重定位方法。
· 覆盖技术
· 交换技术：把内存中暂时不能运行的进程或暂时不用的程序和数据，换到外存。把已经具备运行条件的进程，或进程所需的程序或数据换入内存。

5.2 页式存储管理
一、概念
页：逻辑空间划分成大小相等的若干个页，又称页面。
块：物理空间划分成大小相同的若干块，又叫页框。（每页的大小和每块的大小相同，一般大小为2的幂，512B~4MB）

二、数据结构
页表：
- （索引）页号(页面号)和块号(页框号)的对应关系
- 系统为每个装入内存的进程建立一张相应的页表
请求表：
- 用来确定进程的地址空间的各页在内存中的实际位置关系
- 记录每个进程页表的起始地址，还有所需的页面数
存储页面表
- 记录系统中物理块的使用情况
- 二维数组表示一维物理空间使用情况

三、地址转换（重定位）

页的大小：L；逻辑地址：LA；页号对应的块号：b

十进制计算过程：
页号P = LA / L
页内偏移地址d = LA % L
物理地址PA = b*L+d

十六进制计算过程：
E.g

根据页面大小得到位数。这里是12。LA转换成二进制，后12位不变，为d；前四位根据页表查询块号（页号推出页框号）。物理地址PA就是它们再转换成16进制。该过程通常由硬件完成。

如果给出物理地址—->对应的虚拟地址：根据页面大小得到位数。LA转换成二进制，后面的偏移地址不变。由前面的页框号推出页号。虚拟地址就是再转换为16进制。

四、快表
· 无快表的分页式
两次访问内存：①形成物理地址(PA)要访问页表，页表在内存中。②PA访问数据，也在内存。
普通内存：平均o（n），最好o（logn）

· 快表机制：
1. o（1）即可以得到内存
2. 快表是页表的子集，存放当前访问最频繁的页表项
3. 介质不是内存。是有并行查询能力的高速寄存器组，称为相联存储器，构成一张快表，按内容查找

· 快表机制的地址转换：
根据页号P查快表。若命中，得到块号b（快表时间+访问内存时间）；若未命中，接着查页表，得到b（页表时间+访问内存时间）因为查页表和快表的操作是并行的。

五、页面的共享与保护
页式分配的离散分配灵活的特点，允许两个及以上进程共享程序库中的例程（复杂），或公共数据的同一副本（简单，可以将共享的数据页面安排在地址空间的任意一个页面上）
分页不利于页面共享。对于库例程必须使共享页面具有相同的页号，或者要在地址之间重叠。

5.3 段式存储管理
一、基本思想
1. 作业空间划分成若干段，每段定义一组逻辑信息。每个段地址不一定连续，段内编号连续
2. 装人程序分段装入
3. 系统以段为单位分配内存，每个段分配一个连续内存。段表记录起始地址
4. 标识进程的地址时，要同时给出段名和段内地址。地址空间是二维的
5. 段长由相应的逻辑信息组决定

二、段的地址转换
设置段表，包含段号，段始址，段长度。查找段表，找到每个段对应的内存区，实现从逻辑段–>物理内存区的映射。
与页式存储管理相同。

分配和回收与可变分区类似

三、段的共享和保护
共享：
共享段表
保护：
1. 越界检查
2. 存取控制检查
3. 环保护机制
将所有进程进行分层。
0环：属于操作系统内核，管理I/O操作、存储管理功能，可使用特权指令，访问所有段和页面。
1环：某些重要的实用程序、操作系统服务，如系统调用管理程序。
2环：共享库的过程和函数
3环：一般应用程序
访问较高特权环，需要采用调用服务的方式。

四、段和页的比较
相同：
1. 离散分配
2. 地址映射机构实现地址转换
不同：
1. 页是物理单位，为了减少内存碎片
段是逻辑单位，为了满足用户需求
2. 页的大小固定，在系统初始化时完成
段的大小取决于用户所编写的程序
3. 页式管理中，逻辑地址是一维的
段式管理中，逻辑地址是二维的

五、碎片
碎片：无法被利用的存储空间
固定分区管理：有内存碎片——每个分区中
可变分区管理：有外部碎片——这些空闲空间过小，不能被利用
分段式：有外部碎片——可以通过分区移动技术，将若干碎片拼凑利用
分页式：有页内碎片（属于内部碎片）——最后一页往往装不满

说明：内部碎片不好消除，外部碎片可以通过分区移动消除

5.4 虚拟机存储管理
· 虚拟存储（VM）：用外存来虚拟内存，逻辑上扩充内存容量
· 程序访问局部性原理：指CPU对指令和数据在时间、空间、顺序上往往集中在一定的范围内。
- 时间局部性：某条指令/某个数据结构被访问，则在不久一段时间内可能再次被访问
- 空间局部性：某个存储单元被访问，则在不久一段时间内，附近的存储单元可能被访问
- 顺序局部性：程序执行是在内存中的连续地址进行的；只有遇到跳转才会到一个不连续的地址空间
基于此，可以只把当前作业所需的程序和数据装入内存就能启动运行：
• 一次性装入内存
多次装入内存 / 理论基础是局部性原理 （时间顺序局限性）/ 基于结构化程序设计（三种基本结构——顺序分支循环）

· 基本思想：
1. 基于程序执行的局部性原理，将当前正在使用的部分装入内存就能启动运行（部分装入）
2. 如果访问的程序和数据不在内存中，则系统将这部分装入内存。（请求调入）
3. 如果内存中没有足够存储空间，则需要将内存中暂不用的信息移到外存（部分对换）
特点：离散，虚拟，多次，对换

· 特点：
1. 离散性：内存分配采用离散分配，将一个进程分成多个部分
2. 虚拟性：逻辑上扩充内存容量
3. 多次性：进程多个部分分多次调入内存
4. 对换性：允许进程部分在运行过程中换入换出到对换区

· 实现方法：请求页式/段式/段页式存储管理
· 请求分页式存储：
• 请求页式存储管理的页表

· 中断位：判断页是否在内存中，若不在则产生缺页中断
· 访问位：
记录该页在一段时间被访问的次数，或记录该页最近已经有多长时间未被访问。
提供给置换算法在选择换出页面时参考
· 修改位：表示该页在调入内存后是否被修改过
· 外存地址：指出该页在外存上的地址
• 地址转换：快表命中；页表命中；缺页中断
• 页面调入策略：
· 请页式调入：确保只有被访问的页才调入内存
· 预调式调入：系统动态预测进程最可能要访问的那些页面，使用前预先调入，常一次调入连续多个页面

• 页面清除策略：清除内存中某些页面。要考虑何时把修改过的页面写回外存
· 请页式清除：仅当一页选中要被置换，且之前它被修改过，才把这个页面写入外存。                                                
· 预约式清除 ：对更改过的页面，在被置换前就把它们都写回外存。

• 页面分配策略
分配物理块数
    a. 固定分配
    b. 可变分配
淘汰页面置换
    c. 局部置换：本进程内
    d. 全局置换：页面置换算法作用范围是整个系统
ab,bc,bd √
固定分配全局置换 ×

• 页面置换算法
① 最佳页面置换算法（OPT）：永不使用的或最长时间内不再被访问的页面被置换（将来）

【理想化，性能评价依据】

② 先进先出（first-in first-out FIFO 算法） 内存中驻留时间最久的页面（过去）                                                    Belady 贝莱德异常 分配物理块数增加了，缺页次数增加了

③最近最久未使用页面置换算法（least recently used LRU ）最近一段时间内最长时间没有被访问过的页面（过去）
符合局部性原理
工程实际上使用的是该算法的改进（时钟置换算法 clock，二次机会法 ）
④时钟置换算法 （也称最近未使用算法NRU）是LRU和FIFO的折衷
![在这里插入图片描述](https://img-blog.csdnimg.cn/2020082113194446.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MzQ4MjI3OQ==,size_16,color_FFFFFF,t_70#pic_center)

·内存中所有的页面链接为循环队列                                      
· 每页设置一位访问位，若某页被访问，置1
· 一个页面首次装入内存，其访问位置1
过程：
1）置换时，从指针当前指向的页面开始扫描。
2）先检查访问位。把遇到的所有“访问位”为1的页面“访问位”清0，检查下个页面；遇到“访问位”为0的页面置换掉，指针推进一步。

⑤改进的时钟算法
把访问位（引用位）和修改位结合起来使用：
![在这里插入图片描述](https://img-blog.csdnimg.cn/20200821132135239.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MzQ4MjI3OQ==,size_16,color_FFFFFF,t_70#pic_center)
1）选择最佳淘汰页面，从指针当前位置开始，扫描循环队列。
扫描过程中不改变引用位，把遇到的第一个r=0，m=0作为淘汰页面。
2）如果1失败，再从原位置开始，查找r=0且m=1的页面，把遇到的第一个这样的页面作为淘汰页面，而在扫描过程中，把所扫过的页面的引用位r置0。
思考：为什么会有修改过但未被访问过的情况（r=0，m=1）？
因为每次算法结束后都没有更改过修改位，最多只是置零访问位
⑥最少使用置换算法（LFU）当前为止访问次数最少的页面

• 性能分析
缺页率和进程 工作集的关系：
![在这里插入图片描述](https://img-blog.csdnimg.cn/20200821132154808.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MzQ4MjI3OQ==,size_16,color_FFFFFF,t_70#pic_center)

6.1 设备管理
按传输速率分：
1. 低速设备：(几B几百B) 键盘、鼠标、语音输入/输出设备
2. 中速设备：(千B) 打印机
3. 高速设备：(数十MB数百MB) 磁盘
按信息交换单位分：
1. 字符设备：键盘、鼠标、打印机
I/O采用中断驱动方式；不可寻址(不能指定源、目地址)
2. 块设备：磁盘
I/O采用DMA方式；可寻址
从资源分配角度分：
1. 独占设备：一段时间内只允许一个进程访问
打印机
2. 共享设备：一段时间内允许多个进程交替访问
磁盘
3. 虚拟设备：虚拟技术将独占设备（本质上）改造成共享设备（用户角度）
共享(虚拟)打印机：用磁盘来虚拟打印机

设备的功能和任务
1. 实现设备并行性，提高系统利用率
①设备与CPU并行
②设备之间并行
2. 采用动态分配方式分配设备，提高设备利用率
3. 采用缓冲技术，提高系统效率
4. 为方便用户使用，屏蔽设备物理特性，实现设备独立性

6.2 I/O控制方式
宗旨：减少主机对外设的干涉，以便有更多时间进行计算处理。
分类：
1. 程序之间查询控制方式（询问方式）
主机重复查询外设直到准备就绪。
· 没有中断，没有实现CPU与设备的并行
· 传送单位是字，每传一个字需要CPU干涉
2. 中断方式
· 引入中断机制，实现了CPU和设备并行
· 传送单位是字，每传一个字需要CPU干涉
3. 直接内存读取DMA方式
特点：
· 数据传输的基本单位是数据块
· 传输的数据直接从内存到外设，或相反
· 只在传输开始、结束时需要CPU干涉
DMA控制器组成：主机与DMA的接口、DMA与设备的接口、I/O逻辑
设置四个寄存器，实现CPU与控制器之间的块传输：
1. 命令/状态寄存器（CR）
接收CPU发出的I/O指令，或相关控制信息，或设备状态
2. 内存地址寄存器（MAR）
输入时，存放把数据从设备传到内存的起始目标地址；
输出时，存放即将传输到设备的数据在内存源地址
3. 数据计数器（DC）
存放本次CPU要读写的字节数
4. 数据寄存器（DR）
暂存从设备到内存，或相反的数据

4. 通道方式
通道又称“输入输出处理器”，独立于CPU的特殊处理器。
· 指令单一，只涉及输入输出
· 没有独立内存，与主机（CPU）共享内存

按信息交换方式分：
    1. 字节多路通道
    多连接低、中速外设
    2. 数组选择通道
    多连接高速外设
    3. 数组多路通道
    多连接中、高速外设

6.3 缓冲技术
基本思想：输出数据时，在内存中开辟一个输出缓冲区，将要输入到外设中的数据输入到该区中，等到装满系统再写到I/O设备上。输入类似。
四种机制：
1. 单缓冲
未采用缓冲：
数据进入工作区T；数据进入计算C
总时间: T+C
采用缓冲：输入、计算并行
数据从设备进入缓冲区 T；数据缓存区到工作区M
总时间：Max(T,C)+M （M远小于T，C）

2. 双缓冲
在单缓冲基础上进一步提高并行程度
3. 循环缓冲
组成：
①多个缓存区。每个大小相同。
空缓冲区R；已装满缓存区G；计算进程正在使用的缓存区C
②多个指针。
Nextg：指向计算进程下一个可用的G；
Nexti：指向输入进程下次可用的R；
Current：指向计算进程正在使用的缓存区C
过程：
①GetBuffer。
对于计算进程，调用GetBuffer过程：
1. 通过Nextg获得要进行计算的缓存区，相应地将该缓冲区改成C，将Current指向该缓冲区
2. Nextg指向下一个G缓存区

对于输入进程，调用GetBuffer过程：
1. 通过`Nexti`获得可用的缓存区，相应地将该缓冲区改成C，将Current指向该缓冲区

Nexti指向下一个R缓存区

②ReleaseBuffer。
当计算进程提取完毕后，当前缓存区空出。调用ReleaseBuffer过程，将C改为R。
类似输入进程输入完毕，调用ReleaseBuffer过程，将该缓存区改为G。

4. 缓冲池
缓冲池是一个临界资源，进程同步
组成：

两个基本操作：
①Getbuf（type）：从type指定的队列的队首摘下一个缓存区
②Putbuf（type，number）：将number所指示的缓存区挂在type队列上
过程：
收容输入：设备上的数据进入缓存区
提取输入：缓存区的数据进入工作区

6.4 驱动调度技术
6.4.1磁盘的物理结构
1。物理结构
顺序存取存储设备：严格依赖信息的物理位置进行定位和读写，容量大，稳定，便于保存（磁带）
直接 (随机) 存取存储设备：读取任何物理块所需时间几乎不依赖信息的位置（磁盘）

盘片：每个盘片有两个盘面
盘面：每个盘面有若干磁道(同心圆)、一个磁头（磁头号与盘面号一一 对应）
磁头：所有读写磁头固定在唯一的移动臂上同时移动
磁道：每个磁道分成若干物理块
扇区（物理块）：若干个扇区组成一个块
块（簇）：块是磁盘读写的基本单位
柱面：不同磁盘上的相同磁道号（磁头位置下的所有磁道）组成一个柱面
注：
· 文件的信息通常记录在同一个柱面的不同磁道上。（多磁头并发访问）
· 访问磁盘上的一个物理记录，需要三个参数：柱面号、磁头号、块号。
柱面号决定在哪个磁道上，磁头号决定在哪个盘面上，块号决定读写哪个块。
2.磁盘访问时间
（1）寻道时间 Ts
把磁臂（磁头）移到指定磁道上的时间。是启动磁臂的时间s和磁头移动n条磁道所花费的时间和：
Ts = m*n + s
· m是常数，与磁盘驱动器有关，对一般磁盘，m=0.2；对高速磁盘，m<=0.1。
· 磁臂启动时间约为2 ms
· 一般温盘，Ts=5~30ms
（2）旋转延迟时间
指定扇区移动到磁头下面所经历的时间。