导图社区 操作系统10.12-iOS1
- 19
- 0
- 0
- 举报
操作系统10.12-iOS1
408操作系统，操作系统（Operating System，简称OS）是控制和管理整个计算机系统的硬件和软件资源，并合理地组织调度计算机的工作和资源的分配，以提供用户和其他软件方便的接口和环境的系统软件。
编辑于2024-07-13 16:29:18- 文件管理
- 进程管理
- 操作系统10.12-iOS1
408操作系统，操作系统（Operating System，简称OS）是控制和管理整个计算机系统的硬件和软件资源，并合理地组织调度计算机的工作和资源的分配，以提供用户和其他软件方便的接口和环境的系统软件。
- 计算机网络
计算机网络相关知识，覆盖了计算机网络的基础知识和核心技术。结合了大量的实际案例和应用场景，使读者能够更好地理解和应用所学知识，实用性强。按照网络层次结构组织内容，便于读者逐步深入学习和掌握。帮助读者巩固所学知识，提高学习效果。适合作为通信、计算机以及相关专业本科生和研究生的教材或参考书目，也适合从事计算机网络工作的工程技术人员学习。
- 数据结构
这是一篇关于数据结构的思维导图，包括线性表、栈和队列、串、树与二叉树、查找、排序等内容，非常实用，值得收藏。
操作系统10.12-iOS1
社区模板帮助中心，点此进入>>
- 操作系统10.12-iOS1
408操作系统，操作系统（Operating System，简称OS）是控制和管理整个计算机系统的硬件和软件资源，并合理地组织调度计算机的工作和资源的分配，以提供用户和其他软件方便的接口和环境的系统软件。
- 计算机网络
计算机网络相关知识，覆盖了计算机网络的基础知识和核心技术。结合了大量的实际案例和应用场景，使读者能够更好地理解和应用所学知识，实用性强。按照网络层次结构组织内容，便于读者逐步深入学习和掌握。帮助读者巩固所学知识，提高学习效果。适合作为通信、计算机以及相关专业本科生和研究生的教材或参考书目，也适合从事计算机网络工作的工程技术人员学习。
- 数据结构
这是一篇关于数据结构的思维导图，包括线性表、栈和队列、串、树与二叉树、查找、排序等内容，非常实用，值得收藏。
- 相似推荐
- 大纲
操作系统10.12
第一章 计算机系统概述
1.1操作系统的基本概念
操作系统的概念
计算机系统自上而下分为
硬件
操作系统
应用程序
用户
操作系统
是指控制和管理整个计算机系统的硬件和软件资源
合理地组织和调度计算机工作与资源的分配
进而为用户和其他软件提供方便接口与环境的程序集合
操作系统是计算机系统中最基本的软件
操作系统的特征
并发
并发与并行
并发指两个或多个事件在同一时间间隔内发生。这些事件宏观上是同时发生的，但微观上是交替发生的。
单核CPU同一时刻只能执行一个程序，各个程序只能并发地执行
并行指两个或多个事件在同一时刻同时发生。
多核CPU同一时刻可以同时执行多个程序，多个程序可以并行地执行
共享
共享即资源共享，是指系统中的资源可供内存中多个并发执行的进程共同使用。
两种资源共享方式
互斥共享方式
系统中的某些资源，虽然可以提供给多个进程使用，但一个时间段内只允许一个进程访问该资源
同时共享方式
允许一个时间段内由多个进程“同时”对它们进行访问
所谓的“同时”往往是宏观上的，而在微观上，这些进程可能是交替地对该资源进行访问的（即分时共享）
并发和共享是操作系统的两个最基本的特征
两者互为存在的条件
资源共享是以程序的并发为条件的，若系统不允许程序并发执行，则自然不存在资源共享问题
若系统不能对资源共享实施有效的管理，则必将影响到程序的并发执行，甚至根本无法并发执行
虚拟
虚拟是指把一个物理上的实体变为若干个逻辑上的对应物。
虚拟技术
时分复用技术（处理器的分时共享）
虚拟处理器
通过多道程序设计技术，采用多道程序并发执行的方法
虚拟设备技术
将一台物理I/O设备虚拟为多台逻辑上的I/O设备，并允许每个用户占用一台逻辑上的I/O设备
空分复用技术（虚拟存储器）
虚拟磁盘
虚拟存储器
显然，如果失去了并发性，则一个时间段内系统中只需运行一道程序，那么就失去了实现虚拟性的意义了。因此，没有并发性，就谈不上虚拟性
异步
异步是指，在多道程序环境下，允许多个程序并发执行，但由于资源有限，进程的执行不是一贯到底的，而是走走停停，以不可预知的速度向前推进，这就是进程的异步性。
操作系统的功能与目标
作为系统资源的管理者
处理机处理
在多道程序环境下，处理机的分配和运行都以线程（或进程）为基本单位，因而对处理机的管理可归结为对进程的管理
存储器管理
文件管理
操作系统中负责文件管理的部分称为文件系统
设备管理
作为用户与计算机硬件系统之间的接口
接口分类
命令接口
用户利用这些操作命令来组织和控制作业的执行
按作业控制方式的不同
联机命令接口/交互式命令接口
CMD
脱机命令接口/批处理命令接口
脚本
程序接口
可以在程序中进行系统调用来使用程序接口。普通用户不能直接使用程序接口，只能通过程序代码间接使用。
GUI图形接口
用作扩充机器
没有任何软件支持的计算机成为裸机。
通常把覆盖了软件的机器成为扩充机器，又称之为虚拟机
1.2操作系统的发展和分类
手工操作阶段
缺点
用户独占全机、人机速度矛盾导致资源利用率极低
CPU等待手工操作，CPU利用率较低
批处理阶段
单道批处理系统
引入脱机输入/输出技术（用外围机+磁带完成），并由监督程序负责控制作业的输入、输出
优点
缓解了一定程度的人机速度矛盾，资源利用率有所提升。
缺点
内存中仅能有一道程序运行，只有该程序运行结束之后才能调入下一道程序。
CPU有大量的时间是在空闲等待I/O完成。资源利用率依然很低。
特点
自动性
顺序性
单道性
多道批处理系统
多道程序设计技术允许多个程序同时进入内存并允许它们在CPU中交替的运行，这些程序共享系统中的各种软硬件资源
特点
多道
计算机内存同时存放多道相互独立的程序
宏观上并行
微观上串行
多道程序的实现需要解决的问题
如何分配处理器
多道程序的内存分配问题
I/O设备的分配
优点
多道程序并发执行，共享计算机资源。
资源利用率大幅提升，CPU和其他资源更能保持“忙碌”状态，系统吞吐量增大
缺点
用户响应时间长
没有人机交互功能
分时操作系统
计算机以时间片为单位轮流为各个用户/作业服务，各个用户可通过终端与计算机进行交互
特点
同时性
也称多路性
允许多个终端用户同时使用一台计算机
宏观上，多个用户同时工作共享系统资源
微观上，每个用户作业轮流运行一个时间片
交互性
独立性
系统中各个用户可以彼此独立操作，互不干扰
及时性
优点
用户请求可以被即时响应，解决了人机交互问题。
允许多个用户同时使用一台计算机，并且用户对计算机的操作相互独立，感受不到别人的存在。
缺点
不能优先处理一些紧急任务。
实时操作系统
系统能及时响应外部事件的请求，在规定时间内完成对该事件的处理，并控制所有实时任务协调一致地运行
分类
按任务执行时是否呈现周期性来划分
周期性实时任务
外部设备周期性地发出激励信号给计算机
非周期性实时任务
外部设备所发出的激励信号并无明显的周期性，但都必须联系着一个截止时间
根据对截止时间的要求划分
硬实时任务
系统必须满足任务对截止时间的要求
软实时任务
也联系着任务对截止时间的要求，但并不严格
微机操作系统的发展
单用户单任务操作系统
CP/M
MS-DOS
单用户多任务操作系统
WINDOWS
多用户多任务操作系统
允许多个用户通过各自的终端使用同一台机器，而每个用户程序又可进一步分为几个任务，使它们能够并发执行
1.3操作系统的运行环境
操作系统的运行机制
内核程序和用户程序
内核程序
执行特权指令和非特权指令
特权指令：I/O指令、置中断指令、存取用于内存保护的寄存器等
内核是操作系统最重要最核心的部分，也是最接近硬件的部分
用户程序
执行非特权指令
内核态和用户态
处于内核态时，说明此时正在运行的是内核程序，此时可以执行特权指令
处于用户态时，说明此时正在运行的是应用程序，此时只能执行非特权指令
内核态→用户态
执行一条特权指令——修改PSW的标志位为“用户态”，这个动作意味着操作系统将主动让出CPU使用权
用户态→内核态
由“中断”引发，硬件自动完成变态过程，触发中断信号意味着操作系统将强行夺回CPU的使用权
内核
大内核
将操作系统的主要功能模块作为系统内核，运行在核心态
优点
高性能
缺点
内核代码庞大、结构混乱、难以维护
微内核
只把最基本的功能保留在内核
优点
内核功能少、结构清晰，方便维护
缺点
需要频繁在用户态和核心态之间切换，性能低
微内核结构有效地分离了内核与服务、服务与服务，使得它们之间的接口更加清晰，维护的代价大大降低，各部分可以独立地优化和演进，从而保证了操作系统的可靠性。

内核包含的内容
时钟管理
计时
时钟中断的管理，实现进程的切换
中断处理
在中断机制中，只有一小部分功能属于内核，负责保护和恢复中断现场的信息，转移控制权到相关的处理程序
原语
具有如下特点的程序称为原语
处于操作系统的最低层，是最接近硬件的部分
程序的运行具有原子性
程序运行时间短，并且调用频繁
系统控制的数据结构及处理
进程管理
存储器管理
设备管理
中断和异常的概念 唯一能使用户态变为核心态的方法
中断
也称外中断
与当前执行的指令有关，中断信号来源于CPU内部
返回到下一条指令
因为外中断执行时都是在此条指令执行结束时检查是否有指令请求
由于外设要求或者人工干预
异常
也称内中断
与当前执行的指令无关，中断信号来源于CPU外部
对异常的处理一般要依赖于当前的运行现场，而且异常不能被屏蔽，一旦出现应立刻处理
分类
陷入（trap)
由陷入指令引发，是应用程序故意引发的
系统调用就是使用的陷入
返回到下一条指令
故障（fault)
由错误条件引起的，可能被内核程序修复。内核程序修复故障后会把CPU使用权还给应用程序，让它继续执行下去。
如：缺页故障
可能返回到当前指令
终止（abort)
由致命错误引起，内核程序无法修复该错误，因此一般不再将CPU使用权还给引发终止的应用程序，而是直接终止该应用程序。
如：整数除0、非法使用特权指令
不会返回
系统调用
用户在程序中调用操作系统所提供的一些子功能。
凡是与共享资源有关的操作（如存储分配、I/O操作、文件管理等），都必须通过系统调用的方式向操作系统内核提出服务请求，由操作系统内核代为完成。这样可以保证系统的稳定性和安全性，防止用户进行非法操作。
分类
设备管理
完成设备请求、释放和启动等功能
文件管理
完成文件的读、写、创建和删除等功能
进程控制
完成进程的创建、撤销、阻塞及唤醒等功能
进程通信
完成进程之间的消息传递和信号传递等功能
内存管理
完成内存的分配、回收以及获取作业占用内存区大小及始址等功能
系统调用运行在核心态，用户可以执行陷入指令（访管指令/trap指令）来发起调用，请求操作系统提供服务
系统调用的过程

注意
陷入指令是在用户态执行的，执行陷入指令之后立即引发一个内中断，使CPU进入核心态
发出系统调用请求是在用户态，而对系统调用的相应处理在核心态下进行
第二章 进程管理
2.1进程与线程
进程的概念与特征
进程的概念
进程是进程实体的运行过程，是系统进行资源分配的一个独基本单位，(线程是接受调度的基本单位)
进程是动态的，是程序的一次执行过程
进程映像（进程实体）
是静态的
由程序段、相关数据段和PCB组成
PCB是进程存在的唯一标志
进程的特征
动态性
是进程最基本的特征
并发性
独立性
异步性
结构性
程序并发执行的特征
间断性
失去封闭性
并发进程共享变量，其执行结果与速度有关
不可再现性
进程的状态与转换
运行态
在单核处理机环境下，每个时刻最多只有一个进程处于运行态
就绪态
进程获得了除了处理机外所需的一切资源，一旦得到处理机，便可立即运行
处于就绪态的进程进程可能有多个，通常将它们排成一个就绪队列
阻塞态/等待态
等待某资源可用（不包括处理机）或等待输入/输出完成，即使处理机空闲，该进程也不能运行
创建态
进程正在被创建，尚未转到就绪态
创建进程的步骤
申请一个空白的PCB，并PCB填入一些控制和管理进程的信息
系统为该进程分配运行时所必须的资源
把进程转为就绪态
结束态
进程正在从系统中消失，可能是进程正常运行结束或其他原因中断退出运行
进程转换图

阻塞态→就绪态是不受进程自身能控制的，是一种被动行为
运行态→阻塞态是一种进程自身做出的主动行为
不能由阻塞态直接转换为运行态，也不能由就绪态直接转换为阻塞态（因为 进入阻塞态是进程主动请求的，必然需要进程在运行时才能发出这种请求）
进程控制
进程控制的主要功能是对系统中的所有进程实施有效的管理
原语
一般把进程控制的程序段称为原语
进程控制程序必须一气呵成，避免中途被中断，相关变量与状态不匹配等问题出现
特点
不允许被中断
可以用“关中断指令”和“开中断指令”这两个特权指令实现原子性
是不可分割的基本单位
进程的创建
创建原语
申请空白PCB
为新进程分配所需资源
初始化PCB
将PCB插入到就绪队列
允许一个进程创建（fork)另一个进程，创建者为父进程，被创建者为子进程。子进程可以继承父进程所拥有的资源，子进程被撤销时，应将从父进程哪里得到的资源归还给父进程。撤销父进程，要撤销所有的子进程
父进程与子进程可以并发执行
父进程与子进程具有不同的PID
父进程与子进程具有相同却独立的地址空间
进程间的关系是树形结构
引起进程创建的事件
终端用户登录系统
作业调度
作业为该程序仍在外存中未被调入内存部分
系统提供服务
用户程序的应用请求
进程的终止
撤销原语
从PCB集合中找到终止进程的PCB
若进程正在运行，立刻剥夺CPU,将CPU分配给其他进程
终止其所有子进程
将该进程拥有的所有资源归还给父进程或操作系统
整个OS的进程为树形结构
删除PCB
引起进程终止的事件
正常结束
进程自己请求终止（exit系统调用）
异常结束
整数除以0、非法使用特权指令，然后被操作系统强行杀掉
外界干预
Ctrl+Alt+delete，用户选择杀掉进程
进程的阻塞
阻塞原语
找到将要阻塞进程的标识号对应的PCB
保护进程运行现场，将PCB状态信息设置为阻塞态，暂时停止程序运行
将PCB插入到相应时间的等待队列
引起进程阻塞的事件
需要等到系统分配某种资源
需要等待相互合作的其他进程完成工作
进程的唤醒
唤醒原语
等待队列找到相应进程的PCB
将其从等到进程中移出，并将其状态变为就绪态
把PCB插入到等待队列，等待调度程序调度
引起进程唤醒的事件
等待事件的发生
阻塞原语唤醒原语必须成对使用
进程的切换
切换原语
保留处理机上下文，包括PC，psw和通用寄存器
更新PCB信息
把进程的PCB移入到相应的队列
选择另一个进程执行，更新其PCB
更新内存管理的数据结构
恢复处理机上下文
引起进程切换的事件
当前进程时间片到时
有更高优先级的进程到达
当前进程主动阻塞
当前进程终止

教材
进程的挂起
与挂起(阻塞)对应的是激活(唤醒)操作
挂起操作的引入
引起挂起的原因
终端用户的需要
父进程请求
负荷调节的需要
操作系统的需要
引入挂起原语操作后的三个进程状态的转换
活动就绪→静止就绪
活动阻塞→静止阻塞
静止就绪→活动就绪
静止阻塞→活动阻塞
进程的组织
PCB
进程描述信息
进程标识符PID
用户标识符UID
进程调度信息
进程当前状态，进程优先级等
进程控制信息
处理机状态
也称处理机的上下文
进程控制块的组织方式
线性方式
链接方式
索引方式

进程通信
进程是分配系统资源的单位（包括内存地址空间），因此各进程拥有的内存地址空间相互独立。为了保证安全，一个进程不能直接访问另一个进程的地址空间。 所以进程通信由操作系统完成
共享存储
基于数据结构的共享
比如共享空间里只能放一个长度为10的数组。这种共享方式速度慢、限制多，是一种低级通信方式
基于存储区的共享
在内存中画出一块共享存储区，数据的形式、存放位置都由进程控制，而不是操作系统。相比之下，这种共享方式速度更快，是一种高级通信方式。
两个进程对共享空间的访问必须是互斥的（互斥访问通过操作系统提供的工具实现(PV操作)）
消息传递
进程间的数据交换以格式化的消息（Message）为单位。进程通过操作系统提供的“发送消息/接收消息”两个原语进行数据交换。
消息头包括：发送进程ID、接受进程ID、消息类型、消息长度等格式化的信息（计算机网络中发送的“报文”其实就是一种格式化的消息）
直接通信方式
消息直接挂到接收进程的消息缓冲队列上 消息发送进程要指明接收进程id(pid)
间接通信方式
消息要先发送到中间实体（信箱）中，因此也称“信箱通信方式”。Eg：计网中的电子邮件系统
管道通信
管道pipe只能采用半双工通信，某一时间段内只能实现单向的传输（如水管，管内水流一时间只能往一个方向流淌）。如果要实现双向同时通信，则需要设置两个管道。
各进程要互斥地访问管道。
需要通信的进程间自己实现，如使用操作系统同提供的PV操作的同步互斥的机制，本质上对共享区域的访问为读者-写者问题
数据以字符流的形式写入管道，当管道写满时，写进程的write()系统调用将被阻塞，等待读进程将数据取走。当读进程将数据全部取走后，管道变空，此时读进程的read()系统调用将被阻塞。
如果没写满，就不允许读。如果没读空，就不允许写。
数据一旦被读出，就从管道中被抛弃，这就意味着读进程最多只能有一个，否则可能会有读错数据的情况。
实际Linux中，管道允许有多个写与多个读进程 考试中，一个管道允许有多个写进程，一个读进程
与共享存储区别
共享存储不同进程可在共享内存区域内任意区域读写数据
管道通信中，规定读写数据存放位置与读写顺序FIFO，理解为循环队列
线程的概念和多线程模型
线程(Thread)的基本概念
引入线程的目的是为了减小程序在并发执行时所付出的时空开销，提高操作系统的并发性能(进程之间可以并发进行，线程之间也可以并发进行)
线程是CPU基本的执行单元，也是程序执行流的最小单元
由线程ID、程序计数器、寄存器集合和堆栈组成
一个进程可以创建线程，线程之间可以并发执行
线程有阻塞、就绪和运行三种状态
进程和线程的比较
调度
引入线程后，进程是资源分配的基本单位，线程是调度的基本单位。
同一进程的线程切换不会引起进程的切换，在不同进程进行线程切换，会引起进程切换
拥有资源
引入线程后，进程是资源分配的基本单位。而线程几乎不拥有资源，只拥有极少量的资源（线程控制块TCB、寄存器信息、堆栈等）
并发性
引入线程的操作系统中，不仅进程之间可以并发执行，而且多个线程之间可以并发执行
系统开销
当切换进程时，需要保存/恢复进程运行环境，还需要切换内存地址空间（更新快表、更新缓存）
同一进程内的各个线程间并发，不需要切换进程运行环境和内存地址空间，省时省力
地址空间和其他资源
进程的地址空间之间相互独立，同一进程的各线程之间共享进程的资源，某进程内的线程对其他进程不可见
通信方面
进程间通信需要进程同步和互斥手段的辅助，以保证数据的一致性，而线程间可以直接读/写进程数据段（如全局变量）来通信
进程已不是可执行的实体
进程处于执行状态，实际上指进程中的线程处于执行状态，其他状态也类似
线程的属性
1. 线程是个轻型实体，它不拥有系统资源，但每个线程应有一个唯一的标识符和一个线程控制块，线程控制块记录了线程执行的寄存器和栈等现场状态
2. 不同线程可以执行相同的程序
3. 同一进程的线程共享该进程拥有的资源
4. 在单CPU中，各线程可以交替地占用CPU；在多CPU中，各线程可以同时占用不同的CPU
5. 一个线程被创建时便拥有了它的生命周期，直至终止
线程的实现方式
用户级线程
用户级线程由应用程序通过线程库实现。
所有的线程管理工作都由应用程序负责（包 括线程切换），并非由操作系统完成
用户级线程中，线程切换可以在用户态下即 可完成，无需操作系统干预。
在用户看来，是有多个线程。但是在操作系 统内核看来，并意识不到线程的存在。（用 户级线程对用户不透明，对操作系统透明）
缺点
系统调用的阻塞
线程执行一个系统调用时，该进程的所有线程都会被阻塞 可以用上图中代码理解
多线程应用不能利用多处理机进行多重处理
内核给进程分配的只有一个cpu，进程中只有一个线程能执行
优点
线程转换不需要切换到内核空间
调度算法可以是进程专用的
用户线程的实现与OS平台无关
内核级线程
内核级线程的管理工作由操作系统内核完成。
线程调度、切换等工作都由内核负责，因此 内核级线程的切换必然需要在核心态下才能 完成。
操作系统只“看得见”内核级线 程，因此只有内核级线程才是处 理机分配的单位。
多线程模型
几个用户级线程映射到几个内核级线程的问题引 出了“多线程模型”问题。
多对一模型
多个用户及线程映射到一个内核级线程。每个用户进程只对应一个内核级线程。
优点
用户级线程的切换在用户空间即可完成，不需要切换到核心态，线程管理的系统开销小，效率高
缺点
当一个内核级线程被阻塞后，整个进程都会被阻塞
并发度不高。多个线程不可在多核处理机上并行运行
一对一模型
一个用户及线程映射到一个内核级线程。每个用户进程有与用户级线程同数量的内核级线程。
优点
当一个线程被阻塞后，别的线程还可以继续执行，并发能力强。多线程可在多核处理机上并行执行
缺点
一个用户进程会占用多个内核级线程，线程切换由操作系统内核完成，需要切换到核心态，因此线程管理的成本高，开销大。
多对多模型
n 个用户及线程映射到m 个内核级线程（n >= m）。每个用户进程对应m 个内核级线程。
克服了多对一模型并发度不高的缺点，又克 服了一对一模型中一个用户进程占用太多内 核级线程，开销太大的缺点。
TCB含有的内容
线程标识符
一组寄存器，包括PC、状态寄存器和通用寄存器的内容
线程运行状态
线程优先级
线程专用存储区
信号屏蔽
堆栈指针
2.2处理机调度
调度的概念
调度的基本概念
处理机调度，就是从就绪队列中按照一定的算法选择一个进程并将处理机分配给它运行，以实现进程的并发执行。
调度的层次
作业调度/高级调度
按一定的原则从外存上处于后备队列的作业中挑选一个（或多个）作业，给他们分配内存等必要资源，并建立相应的进程（建立PCB），以使它（们）获得竞争处理机的权利。
高级调度是辅存（外存）与内存之间的调度。
作业调入时会建相应的PCB，作业调出时才撤销PCB
中级调度/内存调度
引入了虚拟存储技术之后，可将暂时不能运行的进程调至外存等待，等它重新具备了运行条件且内存又稍有空闲时，再重新调入内存。这么做的目的是为了提高内存利用率和系统吞吐量。
暂时调到外存等待的进程状态为挂起状态。
PCB并不会一起调到外存，而是会常驻内存。PCB中会记录进程数据在外存中的存放位置，进程状态等信息，操作系统通过内存中的PCB来保持对各个进程的监控、管理。
被挂起的进程PCB会被放到的挂起队列中。
中级调度（内存调度），就是要决定将哪个处于挂起状态的进程重新调入内存。
一个进程可能会被多次调出、调入内存，因此中级调度发生的频率要比高级调度更高。
进程的挂起态和七状态模型

低级调度/进程调度
低级调度（进程调度），其主要任务是按照某种方法和策略从就绪队列中选取一个进程，将处理机分配给它
进程调度是操作系统中最基本的一种调度，在一般的操作系统中都必须配置进程调度。进程调度的频率很高，一般几十毫秒一次。
三种调度的对比

进程调度的时机切换与过程
子主需要进行进程调度与切换的情况
当前运行的进程主动放弃处理机
进程正常终止
运行过程中发生异常而终止
进程主动请求阻塞（如等待I/O）
当前运行的进程被动放弃处理机
分给进程的时间片用完
有更紧急的事需要处理（如I/O中断）
有更高优先级的进程进入就绪队列
不能进行进程调度与切换的情况
在处理中断的过程中
中断处理过程复杂，与硬件密切相关，很难 做到在中断处理过程中进行进程切换。
进程在操作系统内核程序临界区中
进程访问内核临界区时，如访问就绪队列，上锁，其他相关进程无法访问就绪队列进行进程切换 而进程访问一般临界区时，如打印机上锁，不影响其他进程访问就绪队列来进行进程切换。
在原子操作过程中（原语）
进程切换
1. 对原来运行进程各种数据的保存
2. 对新的进程各种数据的恢复
（如：程序计数器、程序状态字、各种数据寄存器等处理机现场信息，这些信息一般保存在进程控制块）
注意：进程切换是有代价的，因此如果过于频繁的进行进程调度、切换，必然会使整个系统的效率降低，使系统大部分时间都花在了进程切换上，而真正用于执行进程的时间减少。
“狭义的进程调度”与“进程切换”的区别
狭义的进程调度指的是从就绪队列中选中一个要运行的进程。（这个进程可以是刚刚被暂停执行的进程，也可能是另一个进程，后一种情况就需要进程切换）
进程切换是指一个进程让出处理机，由另一个进程占用处理机的过程。
广义的进程调度包含了选择一个进程和进程切换两个步骤。
进程调度方式
非剥夺调度方式/非抢占方式
在运行过程中即便有更紧迫的任务到达，当前进程依然会继续使用处理机，直到该进程终止或主动要求进入阻塞态。
实现简单，系统开销小但是无法及时处 理紧急任务，适合于早期的批处理系统
剥夺调度方式，又称抢占方式
当一个进程正在处理机上执行时，如果有一个更重要或更紧迫的进程需要使用处理机，则立即暂停正在执行的进程，将处理机分配给更重要紧迫的那个进程
可以优先处理更紧急的进程，也可实现让各 进程按时间片轮流执行的功能（通过时钟中 断）。适合于分时操作系统、实时操作系统
调度的基本准则
CPU利用率
指CPU “忙碌”的时间占总时间的比例
系统吞吐量
单位时间内完成作业的数量
周转时间
周转时间，是指从作业被提交给系统开始，到作业完成为止的这段时间间隔。
（作业）周转时间= 作业完成时间– 作业提交时间
平均周转时间
平均周转时间=各作业周转时间之和/作业数
带权周转时间
带权周转时间=作业周转时间/作业实际运行的时间
平均带权周转时间
平均带权周转时间=各作业带权周转时间之和/作业数
等待时间
等待时间，指进程/作业处于等待处理机状态时间之和，等待时间越长，用户满意度越低。
对于进程来说
等待时间就是指进程建立后等待被服务的时间之和，在等待I/O完成的期间其实进程也是在被服务的，所以不计入等待时间。
对于作业来说
不仅要考虑建立进程后的等待时间，还要加上作业在外存后备队列中等待的时间。
响应时间
响应时间，指从用户提交请求到首次产生响应所用的时间。
典型的调度算法
先来先服务（FCFS, First Come First Serve）
算法思想
主要从“公平”的角度考虑（类似于我们生活中排队买东 西的例子）
算法规则
按照作业/进程到达的先后顺序进行服务
用于作业/进程调度
用于作业调度时，考虑的是哪个作业先到达后备队列；用 于进程调度时，考虑的是哪个进程先到达就绪队列
是否可抢占？
非抢占式的算法
优缺点
优点
公平、算法实现简单
缺点
排在长作业（进程）后面的短作业需要等待很长时 间，带权周转时间很大，对短作业来说用户体验不好。
FCFS算法对长作业有利，对短作业不利
是否会导致饥饿（某进程/作业长期得不到服务）
否
短作业优先（SJF, Shortest Job First）
算法思想
追求最少的平均等待时间，最少的平均周转时间、最少的 平均带权周转时间
算法规则
最短的作业/进程优先得到服务（所谓“最短”，是指要求 服务时间最短）
用于作业/进程调度
即可用于作业调度，也可用于进程调度。用于进程调度时 称为“短进程优先（SPF, Shortest Process First）算法”
是否可抢占？
SJF和SPF是非抢占式的算法。但是也有抢占式的版本——最 短剩余时间优先算法（SRTN, Shortest Remaining Time Next）
优缺点
优点
“最短的”平均等待时间、平均周转时间
缺点
不公平。对短作业有利，对长作业不利。
可能产生饥饿现象。
作业/进程的运行时间是由用户提供的，并不一定真实，不一定能做到真正的短作业优先
是否会导致饥饿（某进程/作业长期得不到服务）
会。如果源源不断地有短作业/进程到来，可能使长作业/进 程长时间得不到服务，产生“饥饿”现象。如果一直得不 到服务，则称为“饿死”
如果题目中未特别说明，所提到的“短作业/进程优先算法”默认是非抢占式的
高响应比优先（HRRN,Highest Response Ratio Next）
算法思想
要综合考虑作业/进程的等待时间和要求服务的时间
算法规则
在每次调度时先计算各个作业/进程的响应比，选择响应 比最高的作业/进程为其服务服务时间最短）
响应比=（等待时间+要求服务时间）/要求服务时间
用于作业/进程调度
即可用于作业调度，也可用于进程调度
是否可抢占？
非抢占式的算法。因此只有当前运行的作业/进程主动放弃 处理机时，才需要调度，才需要计算响应比
优缺点
优点
综合考虑了等待时间和运行时间（要求服务时间）
等待时间相同时，要求服务时间短的优先（SJF 的优点）
要求服务时间相同时，等待时间长的优先（FCFS 的优点）
对于长作业来说，随着等待时间越来越久，其响应比也会 越来越大，从而避免了长作业饥饿的问题
缺点
是否会导致饥饿（某进程/作业长期得不到服务）
不会
注：这几种算法主要关心对用户的公平性、平均周转时间、平均等待时间等评价系统整体性能的指标，但是不关心“响应时间”，也并不区分任务的紧急程度，因此对于用户来说，交互性很糟糕。因此这三种算法一般适合用于早期的批处理系统
时间片轮转（RR, Round-Robin）
算法思想
公平地、轮流地为各个进程服务，让每个进程在一定时间 间隔内都可以得到响应
算法规则
按照各进程到达就绪队列的顺序，轮流让各个进程执行一 个时间片（如100ms）。若进程未在一个时间片内执行完， 则剥夺处理机，将进程重新放到就绪队列队尾重新排队。
用于作业/进程调度
用于进程调度（只有作业放入内存建立了相应的进程后， 才能被分配处理机时间片）
是否可抢占？
若进程未能在时间片内运行完，将被强行剥夺处理机使用 权，因此时间片轮转调度算法属于抢占式的算法。由时钟 装置发出时钟中断来通知CPU时间片已到
优缺点
优点
公平；响应快，适用于分时操作系统
缺点
由于高频率的进程切换，因此有一定开销
不区分任务的紧急程度
是否会导致饥饿（某进程/作业长期得不到服务）
不会
优先级调度算法
算法思想
随着计算机的发展，特别是实时操作系统的出现，越来越 多的应用场景需要根据任务的紧急程度来决定处理顺序
算法规则
每个作业/进程有各自的优先级，调度时选择优先级最高的作业/进程
用于作业/进程调度
既可用于作业调度，也可用于进程调度。甚至，还会用于 在之后会学习的I/O调度中
是否可抢占？
抢占式、非抢占式都有。做题时的区别在于：非抢占式只 需在进程主动放弃处理机时进行调度即可，而抢占式还需 在就绪队列变化时，检查是否会发生抢占。
优缺点
优点
用优先级区分紧急程度、重要程度，适用于实时操 作系统。可灵活地调整对各种作业/进程的偏好程度。
缺点
若源源不断地有高优先级进程到来，则可能导致饥饿
是否会导致饥饿（某进程/作业长期得不到服务）
会
根据优先级是否可以动态改变
静态优先级：创建进程时确定，之后一直不变。
动态优先级：创建进程时有一个初始值，之后会根据情况动态地调整优先级。
如何合理地设置各 类进程的优先级？
系统进程优先级高于用户进程 前台进程优先级高于后台进程 操作系统更偏好I/O型进程（或称I/O繁忙型进程） 注：与I/O型进程相对的是计算型进程（或称CPU繁忙型进程）
如果采用的是动态优先 级，什么时候应该调整？
可以从追求公平、提升资源利用率等角度考虑 如果某进程在就绪队列中等待了很长时间，则可以适当提升其优先级 如果某进程占用处理机运行了很长时间，则可适当降低其优先级 如果发现一个进程频繁地进行I/O操作，则可适当提升其优先级
多级反馈队列调度算法
算法思想
对其他调度算法的折中权衡
算法规则
1. 设置多级就绪队列，各级队列优先级由高到低，时间片从小到大
2. 新进程到达时先进入第1级队列，按FCFS原则排队等待被分配时间片，若用完时间片进程还未结束，则进程进入下一级队列队尾。如果此时已经是在最下级的队列，则重新放回该队列队尾
3. 只有第k 级队列为空时，才会为k+1 级队头的进程分配时间片
用于作业/进程调度
用于进程调度
是否可抢占？
抢占式的算法。在k 级队列的进程运行过程中，若更上级的队列 （1~k-1级）中进入了一个新进程，则由于新进程处于优先级更高的队列中，因此新进程会抢占处理机，原来运行的进程放回k 级队列队尾。
优缺点
优点
对各类型进程相对公平（FCFS的优点）；
每个新到达的进程都可以很快就得到响应（RR的优点）；
短进程只用较少的时间就可完成（SPF的优点）；
不必实现估计进程的运行时间（避免用户作假）；
可灵活地调整对各类进程的偏好程度，比如CPU密集型进程、I/O密集型进程
是否会导致饥饿（某进程/作业长期得不到服务）
会
注：比起早期的批处理操作系统来说，由于计算机造价大幅降低，因此之后出现的交互式操作系统（包括分时操作系统、实时操作系统等）更注重系统的响应时间、公平性、平衡性等指标。而这几种算法恰好也能较好地满足交互式系统的需求。因此这三种算法适合用于交互式系统。（比如UNIX使用的就是多级反馈队列调度算法）
2.3进程同步
进程同步的基本概念
同步
同步亦称直接制约关系：进程之间相互合作， 如管道通信中的都读进程和写进程 它是指为完成某种任务而建立的两个或多个进程，这些进程因为需要在某些位置上协调它们的工作次序而产生的制约关系。
临界资源
我们把一个时间段内只允许一个进程使用的资源称为临界资源。
许多物理设备（比如摄像头、打印机）都属于临界资源。
此外还有许多变量、数据、内存缓冲区等都属于临界资源。
临界资源的访问过程分为四个部分
进入区
负责检查是否可进入临界区，若可进入，则应 设置正在访问临界资源的标志（可理解为“上 锁”），以阻止其他进程同时进入临界区
临界区
临界区是进程中访问临界资源的代码段
退出区
负责解除正在访问临界资源的 标志（可理解为“解锁”）
剩余区
代码中的剩余部分
进入区和退出区是负责实现互斥的代码段。 临界区也可称为“临界段”。
互斥
互斥称为间接制约关系：进程之间相互占用各自要用的资源 如两进程使用打印机
为了实现对临界资源的互斥访问，需要遵循以下原则
1. 空闲让进。临界区空闲时，可以允许一个请求进入临界区的进程立即进入临界区
2. 忙则等待。当已有进程进入临界区时，其他试图进入临界区的进程必须等待
3. 有限等待。对请求访问的进程，应保证能在有限时间内进入临界区（保证不会饥饿）
4. 让权等待。当进程不能进入临界区时，应立即释放处理机，防止进程忙等待
请求临界区的进程是占用着处理机的
实现临界区互斥的基本方法
软件实现方法
单标志法
算法思想
两个进程在访问完临界区后会把使用临界区的权限转交给另一个进程。也就是说每个进程进入临界区的权限只能被另一个进程赋予

turn表谦让
turn 的初值为0，即刚开始只允许0 号进程进入临界区。若P1 先上处理机运行，则会一直卡在⑤。直到P1 的时间片用完，发生调度，切换P0 上处理机运行。代码① 不会卡住P0，P0 可以正常访问临界区，在P0 访问临界区期间即时切换回P1，P1依然会卡在⑤。只有P0 在退出区将turn 改为1 后，P1才能进入临界区。
主要问题
违背“空闲让进”原则
临界区没有进程访问时，P1访问不了临界区，临界区空闲
双标志先检查法(检查为while)
算法思想
设置一个布尔型数组flag[]，数组中各个元素用来标记各进程想进入临界区的意愿，比如“flag[0] = ture”意味着0 号进程P0 现在想要进入临界区。每个进程在进入临界区之前先检查当前有没有别的进程想进入临界区，如果没有，则把自身对应的标志flag[i] 设为true，之后开始访问临界区。

flag表意愿
主要问题
违反“忙则等待”原则
进程切换都是切换都之前所运行的位置，一旦开锁，再切换回来则不需要重复开锁判断，而是直接继续运行下面语句
原因在于，进入区的“检查”和“上锁” 两个处理不是一气呵成的。“检查”后，“上锁”前可能发生进程切换。
双标志后检查法
算法思想
双标志先检查法的改版。前一个算法的问题是先“检查”后“上锁”，但是这两个操作又无法一气呵成，因此导致了两个进程同时进入临界区的问题。因此，人们又想到先“上锁”后“检查”的方法，来避免上述问题。

flag表意愿
主要问题
又违背了“空闲让进”和“有限等待”原则
会因各进程都长期无法访问临界资源而产生“饥饿”现象。
不是死锁
注意饥饿与死锁的区别
饥饿为竞争的所有进程都得不到资源
死锁为两进程都拥有对方所请求的资源，互相等待
Peterson 算法
算法思想
结合双标志法、单标志法的思想。如果双方都争着想进入临界区，那可以让进程尝试“孔融让梨”（谦让）。做一个有礼貌的进程。
P0为例 进程先表达自己的意愿 flag[0]=true， 然后说客气话谦让 turn=1， 再看自己是不是真客气坏了 while(flag[1]==true && turn==1); 若最后一句客气话不是自己说的，则自己可以访问临界区

主要问题
未遵循让权等待的原则
相比单标志法，双标志先检查法，双标志后检查法已经很好了，但还不够好
硬件实现方法
中断屏蔽方法
利用“开/关中断指令”实现
优点：简单、高效 缺点：不适用于多处理机；只适用于操作系统内核进程，不适用于用户进程（因为开/关中断指令 只能运行在内核态，这组指令如果能让用户随意使用会很危险）
优点
简单、高效
缺点
不适用于多处理机,若一个处理机关中断访问A临界资源，另一个处理机中的进程仍然可以访问临界资源A
只适用于操作系统内核进程，不适用于用户进程（因为开/关中断指令（因为开/关中断指令只能运行在内核态，这组指令如果能让用户随意使用会很危险）
硬件指令方法
TestAndSet指令
简称 TS 指令，也有地方称为 TestAndSetLock 指令，或 TSL 指令
TSL指令是用硬件实现的，执行的过程不允许被中断，只能一气呵成。
指令的功能描述

实现进程互斥

若刚开始 lock 是 false，则 TSL 返回的old 值为 false，while 循环条件不满足，直接跳过循环，进入临界区。若刚开始 lock 是 true，则执行 TLS 后old 返回的值为 true，while 循环条件满足，会一直循环，直到当前访问的临界区的进程在退出区进行“解锁”。
优点
实现简单，无需像软件实现方法那样严格检查是否会有逻辑漏洞
适用于多处理机环境
缺点
不满足“让权等待”原则，暂时无法进入临界区的进程会占用CPU并循环执行TSL指令，从而导致“忙等”
Swap指令
有的地方也叫 Exchange 指令，或简称 XCHG 指令
Swap指令是用硬件实现的，执行的过程不允许被中断，只能一气呵成。
指令的功能描述

实现进程互斥

逻辑上来看 Swap 和 TSL 并无太大区别，都是先记录下此时临界区是否已经被上锁（记录在old 变量上），再将上锁标记 lock 设置为 true，最后检查 old，如果old 为 false 则说明之前没有别的进程则可跳出循环，进入临界区。
优点
实现简单，无需像软件实现方法那样严格检查是否会有逻辑漏洞
适用于多处理机环境
缺点
不满足“让权等待”原则，暂时无法进入临界区的进程会占用CPU并循环执行TSL指令，从而导致“忙等”
信号量
用户进程可以通过使用操作系统提供的一对原语来对信号量进行操作，从而很方便的实现了进程互斥、进程同步。
信号量其实就是一个变量可以用信号量来表示系统中某种资源的数量，比如：系统中只有一台打印机，就可以设置一个初值为 1
原语是一种特殊的程序段，其执行只能一气呵成，不可被中断。原语是由关中断/开中断指令实现的。软件解决方案的主要问题是由“进入区的各种操作无法一气呵成”，因此如果能把进入区、退出区的操作都用“原语”实现，使这些操作能“一气呵成”就能避免问题。
将“检查”与“上锁”一气呵成
一对原语
一对原语：wait(S) 原语和 signal(S) 原语，可以把原语理解为我们自己写的函数，函数名分别为 wait和 signal，括号里的信号量 S 其实就是函数调用时传入的一个参数。
wait、signal 原语常简称为P、V操作。因此，做题的时候常把 wait(S)、signal(S) 两个操作分别写为 P(S)、V(S)
整型信号量
用一个整数型的变量作为信号量，用来表示系统中某种资源的数量
wait和signal的操作描述

wait操作相当于双标志先检查法，先检查，后加锁
执行过程

缺点
违背“让权等待”原则，会发生“忙等”，卡住的进程会一直等待资源S
记录型信号量
整型信号量的缺陷是存在“忙等”问题，因此人们又提出了“记录型信号量”，即用记录型数据结构表示的信号量
记录型信号量的定义

记录信号量最大的特点是，引入了一个进程链表L作为阻塞队列，可以实现“让权等待“ 让权等待是软硬件同步方法以及整形信号量都不能实现的，只有记录型信号量和管程可以实现
S.value的初值表示系统中某种资源的数目
WAIT和SIGNAL操作

对信号量S 的一次P 操作意味着进程请求一个单位的该类资源，因此需要执行 S.value--，表示资源数减1，当 S.value < 0 时表示该类资源已分配完毕，因此进程应调用block 原语进行自我阻塞（当前运行的进程从运行态→阻塞态），主动放弃处理机，并插入该类资源的等待队列 S.L 中。可见，该机制遵循了“让权等待”原则，不会出现“忙等”现象。
对信号量S 的一次V 操作意味着进程释放一个单位的该类资源，因此需要执行 S.value++，表示资源数加1，若加1后仍是 S.value <= 0，表示依然有进程在等待该类资源，因此应调用 wakeup 原语唤醒等待队列中的第一个进程（被唤醒进程从阻塞态变为就绪态，并把此时恢复的临界资源分配给这个被唤醒的进程
注：若考试中出现 P(S)、V(S) 的操作，除非特别说明，否则默认S 为记录型信号量。
AND型信号量
AND同步机制的基本思想是
将进程在整个运行过程中需要的所有资源，一次性分配给进程，待进程使用完后再一起释放
信号量集
对进程所申请的所有资源以及每类资源不同的资源需求量，在一次PV原语操作中完成申请或释放
信号量机制实现进程互斥

同时要会写信号量的数据结构 typedef struct{ int value; struct process*L; }semaphore;
看到semaphore类就可以说明是记录型信号量，具有排队阻塞功能，不会盲等
对不同的临界资源需要设置不同的互斥信号量。
P、V操作必须成对出现。缺少 P(mutex) 就不能保证临界资源的互 斥访问。缺少V(mutex) 会导致资源永不被释放，等待进程永不被唤醒。
信号量机制实现进程同步

若先执行到V(S) 操作，则 S++ 后 S=1。之后当执行到 P(S) 操作时，由于 S=1，表示有可用资源，会执行 S--，S 的值变回 0， P2 进程不会执行block 原语，而是继续往下执行代码4。 若先执行到 P(S) 操作，由于 S=0，S-- 后 S=-1，表示此时没有可用资源，因此P操作中会执行block 原语，主动请求阻塞。之后当执行完代码2，继而执行V(S) 操作， S++，使 S 变回 0，由于此时有进程在该信号量对应的阻塞队列中，因此会在V 操作中执行 wakeup 原语，唤醒 P2 进程。这样 P2 就可以继续执行代码4了
保证了代码4 一定是在代码2 之后执行
实现步骤
分析什么地方需要实现“同步关系”，即必须保证“一前一后”执行的两个操作（或两句代码）
先后V，后前P，接力了属于是
设置同步信号量 S, 初始为 0
实现进程同步时，mutex设置为资源数
在“前操作”之后执行V(S)
在“后操作”之前执行 P(S)
信号量机制实现前驱关系


步骤
1. 要为每一对前驱关系各设置一个同步信号量
2. 在“前操作”之后对相应的同步信号量执行V 操作
3. 在“后操作”之前对相应的同步信号量执行P 操作
管程
为什么要引入管程
信号量机制存在的问题：编写程序困难、易出错
管程的定义和基本特征
管程是一种特殊的软件模块，有这些部分组成
1. 局部于管程的共享数据结构说明；
2. 对该数据结构进行操作的一组过程；
3. 对局部于管程的共享数据设置初始值的语句；
4. 管程有一个名字。
管程的基本特征：
1. 局部于管程的数据只能被局部于管程的过程所访问；
2. 一个进程只有通过调用管程内的过程(入口/函数)才能进入管程访问共享数据；
3. 每次仅允许一个进程在管程内执行某个内部过程。
用管程实现生产者和消费者问题

编译器来实现互斥


1. 需要在管程中定义共享数据（如生产者消费者问题的缓冲区） 2. 需要在管程中定义用于访问这些共享数据的“入口”——其实就是一些函数（如生产者消费者问题中，可以定义一个函数用于将产品放入缓冲区，再定义一个函数用于从缓冲区取出产品） 3. 只有通过这些特定的“入口”才能访问共享数据 4. 管程中有很多“入口”，但是每次只能开放其中一个“入口”，并且只能让一个进程或线程进入（如生产者消费者问题中，各进程需要互斥地访问共享缓冲区。管程的这种特性即可保证一个时间段内最多只会有一个进程在访问缓 冲区。注意：这种互斥特性是由编译器负责实现的，程序员不用关心） 5. 可在管程中设置条件变量及等待/唤醒操作以解决同步问题。可以让一个进程或线程在条件变量上等待（此时，该进程应先释放管程的使用权，也就是让出“入口”）；可以通过唤醒操作将等待在条件变量上的进程或线程唤醒。
条件变量
将阻塞原因定义为条件变量
对条件变量只有两种操作
x.wait
当x对应的条件不再满足时，正在调用管程的进程调用x.wait将自己插入x条件的等待队列，并释放管程
执行wait操作，过程直接给阻塞放到队列，不判断 信号量的p操作才需要判断
x.signal
当x对应的条件发生变化时，调用x.signal,唤醒因为x条件而阻塞的进程
条件变量与信号量的比较
条件变量的wait和signal类似于信号量的P/V操作，可以实现进程的阻塞和唤醒
条件变量是没有值的，仅实现了排队等待的功能，在管程中剩余资源数用共享数据结构记录 信号量才有值，表示资源数
PV操作专指(记录型)信号量，管程里没有这一说
经典同步问题
生产者消费者问题 (同步问题)
问题描述
系统中有一组生产者进程和一组消费者进程，生产者进程每次生产一个产品放入缓冲区，消费者进程每次从缓冲区中取出一个产品并使用。（注：这里的“产品”理解为某种数据）生产者、消费者共享一个初始为空、大小为n的缓冲区。
只有缓冲区没满时，生产者才能把产品放入缓冲区，否则必须等待。
缓冲区没满→生产者生产
只有缓冲区不空时，消费者才能从中取出产品，否则必须等待。
缓冲区没空→消费者消费
缓冲区是临界资源，各进程必须互斥地访问。
互斥关系
PV操作题目分析步骤
1. 关系分析
找出题目中描述的各个进程，分析它们之间的同步、互斥关系
2. 整理思路
根据各进程的操作流程确定P、V操作的大致顺序
3. 设置信号量
并根据题目条件确定信号量初值。（互斥信号量初值一般为1，同步信号量的初始值要看对应资源的初始值是多少）
具体算法
semaphore mutex = 1; //互斥信号量，实现对缓冲区的互斥访问 semaphore empty = n; //同步信号量，表示空闲缓冲区的数量 semaphore full = 0; //同步信号量，表示产品的数量，也即非空缓冲区的数量 producer (){ while(1){ 生产一个产品; P(empty); P(mutex); 把产品放入缓冲区; V(mutex); V(full); } }
consumer (){ while(1){ P(full); P(mutex); 从缓冲区取出一个产品; V(mutex); V(empty); 使用产品; }
能否改变P V的顺序？

互斥一定要在同步P操作之后， 同步与互斥的V操作可以交换
多生产者消费者问题 (同步问题)
问题描述
、桌子上有一只盘子，每次只能向其中放入一个水果。爸爸专向盘子中放苹果，妈妈专向盘子中放橘子，儿子专等着吃盘子中的橘子，女儿专等着吃盘子中的苹果。只有盘子空时，爸爸或妈妈才可向盘子中放一个水果。仅当盘子中有自己需要的水果时，儿子或女儿可以从盘子中取出水果。
这里的“多”指的是多类
分析
互斥关系
对缓冲区（盘子）的访问要互斥地进行
mutex=1
同步关系
1. 父亲将苹果放入盘子后，女儿才能取苹果
2. 母亲将橘子放入盘子后，儿子才能取橘子
3. 只有盘子为空时，父亲或母亲才能放入水果
从“事件”角度理解，来设置信号量； 从客体出发，也就是从公用资源(盘子)出发； 盘子变空事件发生在放入水果之前，盘子变空事件可由女儿和儿子引发，放入水果事件可由父亲和母亲引发
具体算法
semaphore mutex = 1; //实现互斥访问盘子（缓冲区） semaphore apple = 0; //盘子中有几个苹果 semaphore orange = 0; //盘子中有几个橘子 semaphore plate = 1; //盘子中还可以放多少个水果
dad () { while(1){ 准备一个苹果; P(plate); P(mutex); 把苹果放入盘子; V(mutex); V(apple); } }
mom (){ while(1){ 准备一个橘子; P(plate); P(mutex); 把橘子放入盘子; V(mutex); V(orange); } }
daughter (){ while(1){ P(apple); P(mutex); 从盘中取出苹果; V(mutex); V(plate); 吃掉苹果; } }
son (){ while(1){ P(orange); P(mutex); 从盘中取出橘子; V(mutex); V(plate); 吃掉橘子; }
即使不设置专门的互斥变量mutex，也不问会出现可多个进程同时访 互问盘号子量的现象
原因在于：本题中的缓冲区大小为1，在任 何时刻，apple、orange、plate 三个同步信 号量中最多只有一个是1。因此在任何时刻， 最多只有一个进程的P操作不会被阻塞，并 顺利地进入临界区…
盘子容量为2则必须需要mutex
吸烟者问题 (同步问题)
问题描述
假设一个系统有三个抽烟者进程和一个供应者进程。每个抽烟者不停地卷烟并抽掉它，但是要卷起并抽掉一支烟，抽烟者需要有三种材料：烟草、纸和胶水。三个抽烟者中，第一个拥有烟草、第二个拥有纸、第三个拥有胶水。供应者进程无限地提供三种材料，供应者每次将两种材料放桌子上，拥有剩下那种材料的抽烟者卷一根烟并抽掉它，并给供应者进程一个信号告诉完成了，供应者就会放另外两种材料再桌上，这个过程一直重复（让三个抽烟者轮流地抽烟）
分析
互斥关系
桌子抽象为容量为1的缓冲区，要互斥访问
同步关系
组合一：纸+胶水 组合二：烟草+胶水 组合三：烟草
桌上有组合一→第一个抽烟者取走东西 桌上有组合二→第二个抽烟者取走东西 桌上有组合三→第三个抽烟者取走东西 发出完成信号→供应者将下一个组合放到桌上
算法
semaphore offer1 = 0; //桌上组合一的数量 semaphore offer2 = 0; //桌上组合二的数量 semaphore offer3 = 0; //桌上组合三的数量 semaphore finish = 0; //抽烟是否完成 int i = 0; //用于实现“三个抽烟者轮流抽烟”

读者-写者问题 (互斥问题)
问题描述
有读者和写者两组并发进程，共享一个文件，当两个或两个以上的读进程同时访问共享数据时不会产生副作用(生产者-消费者模型中，消费者取数据会影响数据)，所以允许多个读进程 ，但若某个写进程和其他进程（读进程或写进程）同时访问共享数据时则可能导致数据不一致的错误。因此要求： ①允许多个读者可以同时对文件执行读操作； ②只允许一个写者往文件中写信息； ③任一写者在完成写操作之前不允许其他读者或写者工作； ④写者执行写操作前，应让已有的读者和写者全部退出。
算法
在这种算法中，连续进入的多个读者可以同时读文件；写者和其他进程不能同时访问文件；写者不会饥饿，但也并不是真正的“写优先”，而是相对公平的先来先服务原则。有的书上把这种算法称为“读写公平法”。
读者-写者问题为我们解决复杂的互斥问题提供了一个参考思路。 解决读读不互斥，读写与写写互斥 其核心思想在于设置了一个计数器 count用来记录当前正在访问共享文件的读进程数。我们可以用 count 的值来判断当前进入的进程是否是第一个/最后一个读进程，从而做出不同的处理。 另外，对 count 变量的检查和赋值不能一气呵成导致了一些错误，如果需要实现“一气呵成”，自然应该想到用互斥信号量。 最后，还要认真体会我们是如何解决“写进程饥饿”问题的。
哲学家进餐问题 (互斥问题)
算法描述
一张圆桌上坐着哲学家们倾注毕生的精力用于思考和进餐，哲学家在思考时，并不影响他人。只有当哲学家饥饿时，才试图拿起左、右两根筷子（一根一根地起）。如果筷子已在他人手上，则需等待。饥饿的哲学家只有同时拿起两根筷子才可以开始进餐，当进餐完毕后，放下筷子继续思考。
哲学家进餐问题的关键在于解决进程死锁。 这些进程之间只存在互斥关系，但是与之前接触到的互斥关系不同的是，每个进程都需要同时持有两个(或大于两个)临界资源，因此就有“死锁”问题的隐患。 如果在考试中遇到了一个进程需要同时持有多个临界资源的情况，应该参考哲学家问题的思想，分析题中给出的进程之间是否会发生循环等待，是否会发生死锁。 可以参考哲学家就餐问题解决死锁的三种思路。
不合理
防止死锁的发生
①可以对哲学家进程施加一些限制条件，比如最多允许四个哲学家同时进餐。这样可以保证至少有一个哲学家是可以拿到左右两只筷子的
semaphore chopstick[5]={1,1,1,1,1}; semaphore count=4; // 设置一个count，最多有四个哲学家可以进来 void philosopher(int i) { while(true) { think(); wait(count); //请求进入房间进餐 当count为0时 不能允许哲 学家再进来了 wait(chopstick[i]); //请求左手边的筷子 wait(chopstick[(i+1)%5]); //请求右手边的筷子 eat(); signal(chopstick[i]); //释放左手边的筷子 signal(chopstick[(i+1)%5]); //释放右手边的筷子 signal(count); //离开饭桌释放信号量 } }
②要求奇数号哲学家先拿左边的筷子，然后再拿右边的筷子，而偶数号哲学家刚好相反。用这种方法可以保证如果相邻的两个奇偶号哲学家都想吃饭，那么只会有其中一个可以拿起第一只筷子，另一个会直接阻塞。这就避免了占有一支后再等待另一只的情况。
semaphore chopstick[5]={1,1,1,1,1}; void philosopher(int i) { while(true) { think(); if(i%2 == 0) //偶数哲学家，先右后左。 { wait (chopstick[(i + 1)%5]) ; wait (chopstick[i]) ; eat(); signal (chopstick[(i + 1)%5]) ; signal (chopstick[i]) ; } else //奇数哲学家，先左后右。 { wait (chopstick[i]) ; wait (chopstick[(i + 1)%5]) ; eat(); signal (chopstick[i]) ; signal (chopstick[(i + 1)%5]) ; } } }
③仅当一个哲学家左右两支筷子都可用时才允许他抓起筷子。

2.4死锁
死锁的概念
死锁的定义
在并发环境下，各进程因竞争资源而造成的一种互相等待对方手里的资源，导致各进程都阻塞，都无法向前推进的现象，就是“死锁”。
死锁、饥饿、死循环的区别
死锁：各进程互相等待对方手里的资源，导致各进程都阻塞，无法向前推进的现象。
饥饿：由于长期得不到想要的资源，某进程无法向前推进的现象。比如：在短进程优先（SPF）算法
死循环：某进程执行过程中一直跳不出某个循环的现象。有时是因为程序逻辑bug 导致的，有时是程序员故意设计的。
可能只有一个进程发生死循环。死循环的进程可以上处理机运行（可以是运行态），只不过无法像期待的那样顺利推进。死锁和饥饿问题是由于操作系统分配资源的策略不合理导致的，而死循环是由代码逻辑的错误导致的。死锁和饥饿是管理者（操作系统）的问题，死循环是被管理者的问题。
死锁产生的必要条件
互斥条件
只有对必须互斥使用的资源的争抢才会导致死锁（如哲学家的筷子、打印机设备）。
不剥夺条件
进程所获得的资源在未使用完之前，不能由 其他进程强行夺走，只能主动释放。
请求和保持条件
进程已经保持了至少一个资源，但又提出了新的资源请求，而该资源又被其他进程占有，此时请求进程被阻塞，但又对自己已有的资源保持不放
循环等待条件
存在一种进程资源的循环等待链，链中的每一个进程已获得的资源同时被下一个进程所请求。
发生死锁时一定有循环等待，但是发生循环等 待时未必死锁
一个进程处于一个循环等待中，同时又可以从其他进程获取等待的资源，处于循环等待的状态，但并不构成死锁
发生死锁的原因
1. 对系统资源的竞争
各进程对不可剥夺的资源（如打印机）的竞争可能引起死锁，对可剥夺的资源（CPU）的竞争是不会引起死锁的
2. 进程推进顺序非法
请求和释放资源的顺序不当，也同样会导致死锁。例如，并发执行的进程P1、P2 分别申请并占有了资源R1、R2，之后进程P1又紧接着申请资源R2，而进程P2又申请资源R1，两者会因为申请的资源被对方占有而阻塞，从而发生死锁。
3. 信号量的使用不当也会造成死锁
如生产者-消费者问题中，如果实现互斥的P操作在实现同步的P操作之前，就有可能导致死锁。（可以把互斥信号量、同步信号量也看做是一种抽象的系统资源）
对不可剥夺资源分配不合理时，会引发死锁 所以操作系统的工作有对不可剥夺资源的合理分配
死锁的处理策略
预防死锁
破坏死锁产生的四个必要条件中的一个或几个。
避免死锁
用某种方法防止系统进入不安全状态，从而避免死锁（银行家算法）
死锁的检测和解除
允许死锁的发生，不过操作系统会负责检测出死锁的发生，然后采取某种措施解除死锁。
死锁预防
破坏互斥条件
如果把只能互斥使用的资源改造为允许共享使用，则系统不会进入死锁状态
比如: SPOOLing技术
进程1进程2把要打印的数据同时传送给输出进程，之后两进程就可以去各自工作，输出进程再依次将任务发送给打印机 属于逻辑上实现了共享使用，改变了互斥使用
缺点
并不是所有的资源都可以改造成可共享使用的资源。并且为了系统安全，很多地方还必须保护这种互斥性。因此，很多时候都无法破坏互斥条件。
破坏不剥夺条件
方案一：当某个进程请求新的资源得不到满足时，它必须立即释放保持的所有资源，待以后需要时再重新申请。也就是说，即使某些资源尚未使用完，也需要主动释放，从而破坏了不可剥夺条件。
方案二：当某个进程需要的资源被其他进程所占有的时候，可以由操作系统协助，将想要的资源强行剥夺。这种方式一般需要考虑各进程的优先级（比如：剥夺调度方式，就是将处理机资源强行剥夺给优先级更高的进程使用）
缺点
1. 实现起来比较复杂。
2. 释放已获得的资源可能造成前一阶段工作的失效。因此这种方法一般只适用于易保存和恢复状态的资源，如CPU。
3. 反复地申请和释放资源会增加系统开销，降低系统吞吐量。
4. 若采用方案一，意味着只要暂时得不到某个资源，之前获得的那些资源就都需要放弃，以后再重新申请。如果一直发生这样的情况，就会导致进程饥饿。
破坏请求和保持条件
可以采用静态分配方法
即进程在运行前一次申请完它所需要的全部资源，在它的资源未满足前，不让它投入运行。一旦投入运行后，这些资源就一直归它所有，该进程就不会再请求别的任何资源了。
缺点
有些资源可能只需要用很短的时间，因此如果进程的整个运行期间都一直保持着所有资源，就会造成严重的资源浪费，资源利用率极低。
另外，该策略也有可能导致某些进程饥饿。
也可以对静态分配进行改进，允许一个进程只获得运行初期所需的资源后，便开始运行
破坏循环等待条件
可采用顺序资源分配法
首先给系统中的资源编号，规定每个进程必须按编号递增的顺序请求资源，同类资源（即编号相同的资源）一次申请完。
缺点
不方便增加新的设备，因为可能需要重新分配所有的编号
进程实际使用资源的顺序可能和编号递增顺序不一致，会导致资源 浪费
必须按规定次序申请资源，用户编程麻烦。
死锁的避免
系统安全状态
所谓安全序列，就是指如果系统按照这种序列分配资源，则每个进程都能顺利完成。只要能找出一个安全序列，系统就是安全状态。当然，安全序列可能有多个。
如果分配了资源之后，系统中找不出任何一个安全序列，系统就进入了不安全状态。这就意味着之后可能所有进程都无法顺利的执行下去。
如果系统处于安全状态，就一定不会发生死锁
如果系统进入不安全状就未必就是发生了死锁，但发生死锁时一定是在不安全状态
银行家算法
核心思想
在进程提出资源申请时，先预判此次分配是否会导致系统进入不安全状态。如果会进入不安全状态，就暂时不答应这次请求，让该进程先阻塞等待。
数据结构描述
假设系统中有n 个进程，m 种资源
每个进程在运行前先声明对各种资源的最大需求数，则可用一个n*m 的矩阵（可用二维数组实现）表示所有进程对各种资源的最大需求数。不妨称为最大需求矩阵Max，Max[i, j]=K 表示进程 Pi 最多需要K 个资源 Rj
同理，系统可以用一个 n*m 的分配矩阵 Allocation表示对所有进程的资源分配情况。
Max – Allocation =Need 矩阵，表示各进程最多还需要多少各类资源。
另外，还要用一个长度为m的一维数组 Available 表示当前系统中还有多少可用资源。
算法描述
1.反贪 ：Requesti[j]<=Need[i,j](0<=j<=m) 2.确保在能力范围内:Requesti[j]<=Availablei[j](0<=j<=m) 3.1.2.都完成后，试探交付资源
安全性算法

死锁检测和解除
资源分配图
一般用矩形表示资源结点，矩形中的小圆代表该类资源的数量
从进程到资源的有向边为请求边
从资源到进程的有向边为分配边
死锁定理
简化方法


概括：依次消除与不阻塞进程相连的边，直到无边可消
死锁定理：如果某时刻系统的资源分配图是不可完全简化的，那么此时系统死锁
死锁的解除
1. 资源剥夺法
挂起（暂时放到外存上）某些死锁进程，并抢占它的资源，将这些资源分配给其他的死锁进程。但是应防止被挂起的进程长时间得不到资源而饥饿。
2. 撤销进程法（或称终止进程法）
强制撤销部分、甚至全部死锁进程，并剥夺这些进程的资源。这种方式的优点是实现简单，但所付出的代价可能会很大。因为有些进程可能已经运行了很长时间，已经接近结束了，一旦被终止可谓功亏一篑，以后还得从头再来。
3. 进程回退法
让一个或多个死锁进程回退到足以避免死锁的地步。这就要求系统要记录进程 的历史信息，设置还原点。
第三章 内存管理
3.1内存管理概念
内存管理的基本原理和要求
内存管理的功能有：
内存空间的分配和回收
地址转换
内存空间的扩充
内存保护
程序的装入和链接
编译
由编译程序将用户源代码编译成若干个目标模块（编译就是把高级语言翻译为机器语言）
链接
由链接程序将编译后形成的一组目标模块，以及所需库函数链接在一起，形成一个完整的装入模块 目的：将多个从0开始的逻辑地址，形成一个完整的，从0开始的逻辑地址空间，(还没考虑到内存中相对地址的问题)
链接的三种方式
静态链接
在程序运行之前，先将各目标模块及它们所需的库函数连接成一个完整的可执行文件（装入模块），之后不再拆开。
解决的问题
对相对地址进行修改
变换外部调用符号
装入时动态链接
将各目标模块装入内存时，边装入边链接的链接方式。
优点
便于修改和更新
便于实现与目标模块的共享
运行时动态链接
在程序执行中需要该目标模块时，才对它进行链接
其优点是便于修改和更新，便于实现对目标模块的共享。
装入（装载）(.exe)
由装入程序将装入模块装入内存运行 目的：将完整的逻辑地址空间与实际的物理地址空间对应
装入的三种方式
绝对装入
在编译时，如果知道程序将放到内存中的哪个位置，编译程序将产生绝对地址的目标代码。装入程序按照装入模块中的地址，将程序和数据装入内存。
绝对装入只适用于单道程序环境。
程序中使用的绝对地址，可在编译或汇编时给出，也可由程序 员直接赋予。通常情况下都是编译或汇编时再转换为绝对地址。
静态重定位/可重定位装入
编译、链接后的装入模块的地址都是从0开始的指令中使用的地址、数据存放的地址都是相对于起始地址而言的逻辑地址。可根据内存的当前情况，将装入模块装入到内存的适当位置。装入时对地址进行“重定位”，将逻辑地址变换为物理地址（地址变换是在装入时一次完成的）
重定位
装入时对目标程序中的指令和数据的修改过程
特点
是在一个作业装入内存时，必须分配其要求的全部内存空间，如果没有足够的内存，就不能装入该作业。。
作业一旦进入内存后，在运行期间就不能再移动，也不能再申请内存空间
动态重定位/动态运行时装入
编译、链接后的装入地址都是从0开始的。装入程序把装入模块装入内存后，并不会立即把逻辑地址转换为物理地址，而是把地址转换推迟到程序真正要执行时才进行。因此装入内存后所有的地址依然是逻辑地址。这种方式需要一个重定位寄存器的支持。
重定位寄存器
存放装入模块存放的起始位置
特点
可将程序分配到不连续的存储区中；
在程序运行前只需装入它的部分代码即可投入运行，然后在程序运行期间，根据需要动态申请分配内存；
便于程序段的共享，可以向用户提供一个比存储空间大得多的 地址空间。
逻辑地址空间个物理地址空间
地址重定位
将逻辑地址转换为物理地址
内存保护
内存保护可采取两种方法：
在CPU中设置一对上、下限寄存器，存放进程的上、下限地址。进程的指令要访问某个地址时，CPU检查是否越界
采用重定位寄存器（又称基址寄存器）和界地址寄存器（又称限长寄存器，存放最大的逻辑地址(长度)）进行越界检查。重定位寄存器中存放的是进程的起始物理地址。界地址寄存器中存放的是进程的最大逻辑地址。
覆盖和交换
覆盖技术
覆盖技术的思想
1. 将程序分为多个段（多个模块）。常用的段常驻内存，不常用的段在需要时调入内存。
2. 内存中分为一个“固定区”和若干个“覆盖区”。
3. 需要常驻内存的段放在“固定区”中，调入后就不再调出（除非运行结束）不常用的段放在“覆盖区”，需要用到时调入内存，用不到时调出内存
必须由程序员声明覆盖结构，操作系统完成自动覆盖。
缺点
对用户不透明，增加了用户编程负担。覆盖技术只用于早期的操作系统中，现在已成为历史。
交换技术
交换（对换）技术的设计思想
内存空间紧张时，系统将内存中某些进程暂时换出外存，把外存中 某些已具备运行条件的进程换入内存（进程在内存与磁盘间动态调度）
中级调度（内存调度），就是要决定将哪个处于挂起状态的进程重新调入内存
具有对换功能的操作系统中，通常把磁盘空间分为文件区和对换区两部分。
文件区主要用于存放文件，主要追求存储空间的利用率，因此对文件区空间的管理采用离散分配方式；
对换区空间只占磁盘空间的小部分，被换出的进程数据就存放在对换区。由于对换的速度直接影响到系统的整体速度，因此对换区空间的管理主要追求换入换出速度，因此通常对换区采用连续分配方式（学过文件管理章节后即可理解）。总之，对换区的I/O速度比文件的速度更快
交换通常在许多进程运行且内存吃紧时进行，而系统负荷降低就暂停。
例如：在发现许多进程运行时经常发生缺页，就说明内存紧张，此时可以换出一些进程；如果缺页率明显下降，就可以暂停换出。
可优先换出阻塞进程；可换出优先级低的进程；为了防止优先级低的进程在被调 入内存后很快又被换出，有的系统还会考虑进程在内存的驻留时间…
（注意：PCB 会常驻内存，不会被换出外存）
覆盖与交换的区别
覆盖是在同一个程序或进程中的
交换是在不同进程（或作业）之间的
内存分配
连续分配管理方式
连续分配：指为用户进程分配的必须是一个连续的内存空间。
单一连续分配
在单一连续分配方式中，内存被分为系统区和用户区。
系统区通常位于内存的低地址部分，用于存放操作系统相关数据；用户区用于存放用户进程相关数据。
内存中只能有一道用户程序，用户程序独占整个用户区空间。
优点
实现简单；无外部碎片；（整个内存空间都是一道程序的空间，都是内部）
可以采用覆盖技术扩充内存；
不一定需要采取内存保护（eg：早期的 PC 操作系统 MS-DOS）。
缺点
有内部碎片，内存利用率低。
补：这里的内部和外部指的是系统为进程分配的在内存中空间的内部和外部
固定分区分配
于是将整个用户空间划分为若干个固定大小的分区，在 每个分区中只装入一道作业，这样就形成了最早的、最 简单的一种可运行多道程序的内存管理方式。
分区大小相等
缺乏灵活性，但是很适合用于用一台计算机控制多个相同对象的场合（比如：钢铁厂有n个相同的炼钢炉，就可把内存分为n个大小相等的区域存放n个炼钢炉控制程序）
分区大小不等
增加了灵活性，可以满足不同大小的进程需求。根据常在系统中运行的作业大小情况进行划分（比如：划分多个小分区、适量中等分区、少量大分区）
分区说明表
操作系统需要建立一个数据结构--分区说明表，来实现分区的分配和回收，每个表项对应一个分区，通常按分区大小排列。每个表项包括对应分区的大小、起始地址、状态（是否已分配）。
当某用户程序要装入内存时，由操作系统内核程序根据用户程序大小检索该表，从中找到一个能满足大小的、未分配的分区，将之分配给该程序，然后修改状态为“已分配”。
优点
实现简单，无外部碎片。
缺点
a. 当用户程序太大时，可能所有的分区都不能满足需求，此时不得不采 用覆盖技术来解决，但这又会降低性能
b. 会产生内部碎片，内存利用率低。
动态分区分配/可变分区分配 (这里的动态分区分配与上面的固定分区分配，所谓的固定与动态指的是分区是否根据程序大小量身订造空间，两者都是连续的，指初始分配的分区在内存中连续)
这种分配方式不会预先划分内存分区，而是在进程装入内存时，根据进程的大小动态地建立分区，并使分区的大小正好适合进程的需要。因此系统分区的大小和数目是可变的。
动态，可变就表现在，可以为要分配空间的进程量身定做大小
记录内存的使用情况
空闲分区表
每个空闲分区对应一个表项。表项中包含分区号、分区大小、分区起始地址等信息
注：各表项的顺序不一定按照地址递增顺序排列，具体 的排列方式需要依据动态分区分配算法来确定。
空闲分区链
每个分区的起始部分和末尾部分分别设置前向指针和后向指针。起始部分处还可记录分区大小等信息
分区的分配与回收
分区的回收
情况一：回收区的后面有一个相邻的空闲分区
两个相邻的空闲分区合并为一个
情况二：回收区的前面有一个相邻的空闲分区
两个相邻的空闲分区合并为一个
情况三：回收区的前、后各有一个相邻的空闲分区
三个相邻的空闲分区合并为一个
情况四：回收区的前、后都没有相邻的空闲分区
新增一个表项
动态分区分配没有内部碎片，但是有外部碎片。
内部碎片和外部碎片
内部碎片
分配给某进程的内存区域中，有些部分没有用上
开始分配过多
外部碎片
是指内存中的某些空闲分区由于太小而难以利用。
反复交换产生的
可以通过紧凑（拼凑，Compaction）技术来解决外部碎片
动态分区分配算法
首次适应算法
算法思想
每次都从低地址开始查找，找到第一个能满足大小的空闲分区。
如何实现
空闲分区以地址递增的次序排列。每次分配内存时顺序查找空闲分区链（或空闲分区表），找到大小能满足要求的第一个空闲分区。
优点
综合看性能最好，算法开销小(回收分区后一般不需要对空闲分区队列进行排序)
最佳适应算法
算法思想
由于动态分区分配是一种连续分配方式，为各进程分配的空间必须是连续的一整片区域。因此为了保证当“大进程”到来时能有连续的大片空间，可以尽可能多地留下大片的空闲区，即，优先使用更小的空闲区。
如何实现
如何实现：空闲分区按容量递增次序链接。每次分配内存时顺序查找空闲分区链（或空闲分区表），找到大小能满足要求的第一个空闲分区。
缺点
每次都选最小的分区进行分配，会留下越来越多的、很小的、难以利用的内存块。因此这种方法会产生很多的外部碎片。 算法开销大(每次回收后可能需要排序)
最大适应算法（Largest Fit)
算法思想
为了解决最佳适应算法的问题——即留下太多难以利用的小碎片，可以在每次分配时优先使用最大的连续空闲区，这样分配后剩余的空闲区就不会太小，更方便使用。
如何实现
空闲分区按容量递减次序链接。每次分配内存时顺序查找空闲分区链（或空闲分区 表），找到大小能满足要求的第一个空闲分区。
缺点
每次都选最大的分区进行分配，虽然可以让分配后留下的 空闲区更大，更可用，但是这种方式会导致较大的连续空闲区被 迅速用完。如果之后有“大进程”到达，就没有内存分区可用了。 算法开销大(回收后可能排序)
邻近适应算法/循环首次适应算法
算法思想
首次适应算法每次都从链头开始查找的。这可能会导致低地址部分出现很多小的空闲分区，而每次分配查找时，都要经过这些分区，因此也增加了查找的开销。如果每次都从上次查找结束的位置开始检索，就能解决上述问题。
如何实现
空闲分区以地址递增的顺序排列（可排成一个循环链表）。每次分配内存时从上次查找结束的位置开始查找空闲分区链（或空闲分区表），找到大小能满足要求的第一个空闲分区。
优点
算法开销小
缺点
会使高地址的大分区也被用完
综合来看，四种算法中，首次适应算法的效果反而更好
四种算法的对比

首次适应与临近适应不需要分配后对空间排序，开销小 最佳适应和最坏适应可能需要分配后对空间排序，开销大
非连续分配方式
基本分页管理方式
将内存空间分为一个个大小相等的分区（比如：每个分区4KB），每个分区就是一个“页框”，page frame（页框=页帧=内存块=物理块=物理页面）。每个页框有一个编号，即“页框号”（页框号=页帧号=内存块号=物理块号=物理页号），页框号从0开始。
页框/页帧是物理上划分的
将进程的逻辑地址空间也分为与页框大小相等的一个个部分， 每个部分称为以一个“页”或“页面” 。每个页面也有一个编号，即“页号”，页号也是从从0开始的
操作系统以页框为单位为各个进程分配内存空间。进程的每个页面分别放入一个页框中。也就是说，进程的页面与内存的页框有一一对应的关系。各个页面不必连续存放，可以放到不相邻的各个页框中。
对比
页、页面 vs 页框、页帧、物理页
页号、页面号 vs 页框号、页帧号、物理页号
进程的最后一个页面可能没有一个页框那么大。也就是说，分页存储有可能产生内部碎片，因此页框不能太大，否则可能产生过大的内部碎片造成浪费）
页表
为了能知道进程的每个页面在内存中存放的位置，操作系统要为每个进程建立一张页表。页表通常存在PCB（进程控制块）中
1. 一个进程对应一张页表
2. 进程的每个页面对应一个页表项
3. 每个页表项由“页号”和“块号”组成
4. 页表记录进程页面和实际存放的内存块之间的映射关系
5. 每个页表项的长度是相同的
每个页表项占多少字节？
Eg：假设某系统物理内存大小为 4GB，页面大小为4KB，则 每个页表项至少应该为多少字节？
内存块大小=页面大小=4KB= 2^12 B ◇4GB 的内存总共会被分为 2^32 / 2^12 = 2^20 个内存块 ◇内存块号的范围应该是 0 ~ 2…^20 -1 ◇内存块号至少要用 20 bit 来表示 ◇至少要用3B来表示块号（3*8=24bit）
假设页表中的各页表项从内存地址为X 的地方开始连续存放… 如何找到页号为i 的页表项？
i 号页表项的存放地址= X + 3*I
因此，页表中的页号可以是隐含的，即页号不占用存储空间
类似于数组，”下标“表示页号，不占用存储空间
注意：页表存放的只是内存块号(页框号),并不是内存块的起始地址， J号内存块的起始地址=J*内存块大小
如何实现地址的转换?
如何确定一个逻辑地址对应的页号、页内偏移量？
Eg：在某计算机系统中，页面大小是50B。某进程逻辑地址空间大小为200B，则逻辑地址 110 对应的页号、页内偏移量是多少？
页号= 逻辑地址/ 页面长度（取除法的整数部分） 页内偏移量= 逻辑地址% 页面长度（取除法的余数部分）
页号=110/50=2 页内偏移量= 110%50=10
逻辑地址可以拆分为（页号，页内偏移量） 通过页号查询页表，可知页面在内存中的起始地址 页面在内存中的起始地址+页内偏移量= 实际的物理地址
页面大小刚好是 2 的整数幂有什么好处？
①逻辑地址的拆分更加迅速
如果每个页面大小为 2KB，用二进制数表示逻辑地址，则末尾K 位即为页内偏移量，其余部分就是页号。因此，如果让每个页面的大小为 2 的整数幂，计算机硬件就可以很方便地得出一个逻辑地址对应的页号和页内偏移量，而无需进行除法运算，从而提升了运行速度。
②物理地址的计算更加迅速
根据逻辑地址得到页号，根据页号查询页表从而找到页面存放的内存块号，将二进制表示的内存块号和页内偏移量拼接起来，就可以得到最终的物理地址。
逻辑地址结构
页号+页偏移量
如果有K 位表示“页内偏移量”，则说明该系统中一个页面的大小是 2^K 个内存单元
如果有M 位表示“页号”，则说明在该系统中，一个进程最多允许有 2^M 个页面
解题技巧：页面大小与页内偏移量位数互推！然后得知逻辑地址
若页面大小不是2的整数次幂，则只能使用十进制取模算页号，十进制取余算页内偏移量
基本地址变换机构 (逻辑地址->物理地址) 重要！！！
页表寄存器（PTR）
通常会在系统中设置一个页表寄存器（PTR），存放页表在内存中的起始地址F 和页表长度M。进程未执行时，页表的始址和页表长度放在进程控制块（PCB）中，当进程被调度时，操作系内核会把它们放到页表寄存器中。
地址变换过程
进程恢复时，将系统区的PCB中的信息放到相关寄存器中，其中就包括页表寄存器PTR，PC等 PTR中的页表长度M，指的是这个页表中有多少个页表项
分页式进程管理中，逻辑地址结构是不变的(系统知道页内地址的固定位数和页号) 判断页号P与页表长度M的大小，若P大于M，访问非法
注意这里：页表项中存放的内存块号为什么可以直接拼接形成物理地址？ 不用乘内存块大小吗？？？ 答：直接拼接就相当于乘了内存块大小，因为拼接在物理地址的前端，带着权重，权重为内存块大小！！！
解题细节：不要忽略对要访问的页号进行越界检查
例题
页式存储管理地址是一维的，只需要告诉OS一个逻辑地址，OS就可以自动计算出页号，页内偏移量
页内偏移量与页面大小之间的关系(两者互推)
两次访存
查页表
访问目标内存单元
常常会让一个页表项占更多的字节，使得每个页面恰好可以装得下整数个页表项。
实际应用：4B的页表项 题目让求最小页表项：3B
具有快表的地址变换机构
快表
快表，又称相联寄存器（TLB， translation lookaside buffer ），是一种访问速度比内存快很多的高速缓存（TLB不是内存！），用来存放最近访问的页表项的副本，可以加速地址变换的速度。与此对应，内存中的页表常称为慢表。
引入快表后，地址的变换过程
① CPU给出逻辑地址，由某个硬件算得页号、页内偏移量，将页号与快表中的所有页号进行比较。
② 如果找到匹配的页号，说明要访问的页表项在快表中有副本，则直接从中取出该页对应的内存块号，再将内存块号与页内偏移量拼接形成物理地址，最后，访问该物理地址对应的内存单元。因此，若快表命中，则访问某个逻辑地址仅需一次访存即可。
③ 如果没有找到匹配的页号，则需要访问内存中的页表，找到对应页表项，得到页面存放的内存块号，再将内存块号与页内偏移量拼接形成物理地址，最后，访问该物理地址对应的内存单元。因此，若快表未命中，则访问某个逻辑地址需要两次访存（注意：在找到页表项后，应同时将其存入快表，以便后面可能的再次访问。但若快表已满，则必须按照一定的算法对旧的页表项进行替换）
进程切换时，TLB被清楚
例：某系统使用基本分页存储管理，并采用了具有快表的地址变换机构。访问一次快表耗时 1us，访问一次内存耗时 100us。若快表的命中率为 90%，那么访问一个逻辑地址的平均耗时是多少？
(1+100) * 0.9 + (1+100+100) * 0.1 = 111 us 有的系统支持快表和慢表同时查找，如果是这样，平均耗时应该是(1+100) * 0.9 + (100+100) * 0.1 =110.9 us 若未采用快表机制，则访问一个逻辑地址需要 100+100 = 200us 显然，引入快表机制后，访问一个逻辑地址的速度快多了。
TLB 和普通Cache 的区别
TLB 中只有页表项的副本，而普通Cache 中可能会有其他各种数据的副本
两级页表
单级页表存在的问题
问题一：页表必须连续存放，因此当页表很大时，需要占用很多个连续的页框
问题二：没有必要让整个页表常驻内存，因为进程在一段时间内可能只需要访问某几个特定的页面。
某计算机系统按字节寻址，支持 32 位的逻辑地址，采用分页存储管理，页面大小为4KB，页表项长度为 4B。
4KB = 2^12B，因此页内地址要用12位表示，剩余 20 位表示页号。 因此，该系统中用户进程最多有 2^20 页。相应的，一个进程的页表中，最多会有 2^20 = 1M = 1,048,576 个页表项，所以一个页表最大需要 2^20 * 4B = 2^22 B，共需要 2^22/2^12 = 2^10 个页框存储该页表。根据局部性原理可知，很多时候，进程在一段时间内只需要访问某几个页面了。因此没有必要让整个页表都常驻内存。
把页表再分页并离散存储，然后再建立一张页表记录页表各个部分 的存放位置，称为页目录表，或称外层页表，或称顶层页表
地址结构
一级页号（页目录号）+二级页号+页内偏移量
针对问题二
可以在需要访问页面时才把页面调入内存（虚拟存储技术）。可以 在页表项中增加一个标志位，用于表示该页面是否已经调入内存
若想访问的页面不在内存中，则产生缺页中断（内中断/异常），然后将目标页面从外存调入内存
若分为两级页表后，页表依然很长，则可以采用更多级页表，一般来说各级页表的大小不能超过一个页面
两级页表的访存次数（假设没有快表机构）
第一次访存：访问内存中的页目录表
第二次访存：访问内存中的二级页表
总结：无TLB时，n级页表需要访存n+1次
第三次访存：访问目标内存单元
基本分段存储管理方式
进程的地址空间
按照程序自身的逻辑关系划分为 若干个段名（在低级语言中，程序员使用段名来编程），每段从0开始编址
内存分配规则
以段为单位进行分配，每个段在内存中占据连续空间，但各段之间可以不相邻。
地址结构
段号+段内地址
段号的位数决定了每个进程最多可以分几个段
段内地址位数决定了每个段的最大长度是多少
段表
程序分多个段，各段离散地装入内存，为了保证程序能正常运行，就必须能从物理内存中找到各个逻辑段的存放位置。为此，需为每个进程建立一张段映射表，简称“段表”。
每个段对应一个段表项，其中记录了该段在内存中的起始位置（又称 基址”）和段的长度。
各个段表项的长度是相同的。因此段号可以隐含
地址变换过程

可重入代码
不能被修改的代码称为纯代码或可重入代码（不属于临界资源），这样的代码是可以共享的。
可修改的代码是不能共享的（比如，有一个代码段中有很多变量，各进程并发地同时访问可能造成数据不一致）
分段与分页的比较
1
页是信息的物理单位。分页的主要目的是为了实现离散分配，提高内存利用率。
段是信息的逻辑单位。分段的主要目的是更好地满足用户需求
2
分页仅仅是系统管理上的需要，完全是系统行为，对用户是不可见的。
一个段通常包含着一组属于一个逻辑模块的信息。分段对用户是可见的，用户编程时需要显式地给出段名。
3
页的大小固定且由系统决定。
段的长度却不固定，决定于用户编写的程序。
4
分页的用户进程地址空间是一维的，程序员只需给出一个记忆符即可表示一个地址。
分段的用户进程地址空间是二维的，程序员在标识一个地址时，既要给出段名，也要给出段内地址。
5
分段比分页更容易实现信息的共享和保护。
分页、分段的优缺点分析
分页
优点
不方便按照逻辑模块实现信息的共享和保护
缺点
如果段长过大，为其分配很大的连续空间会很不方 便。另外，段式管理会产生外部碎片
分段
优点
很方便按照逻辑模块实现信息的共享和保护
缺点
如果段长过大，为其分配很大的连续空间会很不方 便。另外，段式管理会产生外部碎片
段页式管理方式
将进程按逻辑模块分段，再将各段分页（如每个页面4KB）再将内存空间分为大小相同的内存块/页框/页帧/物理块面分别装入各内存块中
逻辑地址结构
段号+页号+页内偏移量
段号的位数决定了每个进程最多可以分几个段
页号位数决定了每个段最大有多少页
页内偏移量决定了页面大小、内存块大小是多少
因此段页式管理的地址结构是二维的。
段表、页表
每个段对应一个段表项，每个段表项由段号、页表长度、页表存放块号（页表起始 地址）组成。每个段表项长度相等，段号是隐含的。
每个页面对应一个页表项，每个页表项由页号、页面存放的内存块号组成。每个页 表项长度相等，页号是隐含的。
地址转换过程

3.2虚拟内存管理
虚拟内存的基本概念
传统存储管理方式的特征、缺点
一次性
作业必须一次性全部装入内存后才能开始运行。这会造成两个问题：
①作业很大时，不能全部装入内存，导致大作业无法运行；
②当大量作业要求运行时，由于内存无法容纳所有作业，因此只有少量作业能运行，导致多道程序并发度下降。
驻留性
一旦作业被装入内存，就会一直驻留在内存中，直至作业运行结束。
导致了内存中会驻留大量的、暂时用不到的数据，浪费了宝贵的内存资源。
局部性原理
时间局部性
如果执行了程序中的某条指令，那么不久后这条指令很有可能再次执行；如果某个数据被访问过，不久之后该数据很可能再次被访问。（因为程序中存在大量的循环）
空间局部性
一旦程序访问了某个存储单元，在不久之后，其附近的存储单元也很有可能被访问。（因为很多数据在内存中都是连续存放的，并且程序的指令也是顺序地在内存中存放的）
高速缓存的思想
将近期会频繁访问到的数据放到更高速的存储器中，暂时用不到的数 据放在更低速存储器中。
虚拟内存的定义和特征
在操作系统的管理下，在用户看来似乎有一个比实际 内存大得多的内存，这就是虚拟内存
请求分页/段存储管理与基本分页/段存储管理的主要区别：
在程序执行过程中，当所访问的信息不在内存时，由操作系统负责将所需信息从外存调入内存，然后继续执行程序。
请求调页/段
若内存空间不够，由操作系统负责将内存中暂时用不到的信息换出到外存。
页面置换/段置换
虚拟内存的最大容量
是由计算机的地址结构（CPU寻址范围）确定的
虚拟内存的实际容量
虚拟内存的实际容量= min（内存和外存容量之和，CPU寻址范围）
虚拟内存的主要特征
多次性
无需在作业运行时一次性全部装入内存，而是允许被分成多次调入内存。
对换性
在作业运行时无需一直常驻内存，而是允许在作业运行过程中，将作业换入、换出。
虚拟性
从逻辑上扩充了内存的容量，使用户看到的内存容量，远大于实际的容量。
虚拟内存技术的实现
虚拟内存的实现需要建立在离散分配的内存管理方式基础上
请求分页存储管理
请求分段存储管理
请求段页式存储管理
请求分页管理方式
页表机制
请求页表增加了四个字段
状态位P
是否已调入内存
访问字段A
可记录最近被访问过几次，或记录上次访问的时间，供置换算法选择换出页面时参考
修改位M
页面调入内存后是否被修改过
外存地址
页面在外存中的存放位置
缺页中断机构
当访问的页面不在内存时(先检查状态位)
产生一个缺页中断，然后由操作系统的缺页中断处理程序处理中断。 此时缺页的进程阻塞，放入阻塞队列，调页完成后再将其唤醒，放回就绪队列。
如果内存中有空闲块，则为进程分配一个空闲块，将所缺页面装入该块，并修 改页表中相应的页表项。
如果内存中没有空闲块，则由页面置换算法选择一个页面淘汰，若该页面在内 存期间被修改过，则要将其写回外存。未修改过的页面不用写回外存。
缺页中断与一般中断的区别
缺页中断是因为当前执行的指令想要访问的目标页面未调入内存而产生的，因此属于故障，是内中断
一条指令在执行期间，可能产生多次缺页中断。（如：copy A to B，即将逻辑地址A中的数据复制到逻辑地址B，而A、B属于不同的页面，则有可能产生两次中断）
地址变换机构
请求分页的地址变换过程

注释
①只有“写指令”才需要修改“修改位”。并且，一般来说只需修改快表中的数据，只有要将快表项删除时才需要写回内存中的慢表。这样可以减少访存次数。
②和普通的中断处理一样，缺页 中断处理依然需要保留CPU现场。
③需要用某种“页面置换算法” 来决定一个换出页面
④换入/换出页面都需要启动慢速的I/O操作，可见，如果换入/ 换出太频繁，会有很大的开销
⑤页面调入内存后，需要修改慢 表，同时也需要将表项复制到快 表中。
在具有快表机构的请求分页系统中，访问一个逻辑地址时，若发生缺页，则地址变换步骤是：
查快表(未命中)——查慢表(发现未调入内存)——调页(调入的页面对应的表项会直接加入快表)——查快表(命中)——访问目标内存单元
页面置换算法
页面的换入、换出需要磁盘I/O，会有较大的开销，因此好的页面置换算法应该追求更少的缺页率
最佳置换算法（OPT）
每次选择淘汰的页面将是以后永不使用，或者在最长时间内不再被 访问的页面，这样可以保证最低的缺页率。

最佳置换算法可以保证最低的缺页率，但实际上，只有在进程执行的过程中才能知道接下来会访问到的是哪个页面。操作系统无法提前预判页面访问序列。因此，最佳置换算法是无法实现的。
先进先出置换算法（FIFO）
每次选择淘汰的页面是最早进入内存的页面
实现方法
把调入内存的页面根据调入的先后顺序排成一个队列，需要换出页面时选择队头页面即可。队列的最大长度取决于系统为进程分配了多少个内存块。
Belady 异常
当为进程分配的物理块数增大时，缺页次数不减反增的异常现象。
只有FIFO算法会出现，LRU和OPT算法永远不会出现Belady异常
异常。另外，FIFO算法虽然实现简单，但是该算法与进程实际运行时的 规律不适应，因为先进入的页面也有可能最经常被访问。因此，算法性能差
最近最久未使用置换算法（LRU）
每次淘汰的页面是最近最久未使用的页面
实现方法
赋予每个页面对应的页表项中，用访问字段记录该页面自上次被访问以来所经历的时间t。
该算法的实现需要专门的寄存器和栈的硬件支持，虽然算法性能好， 但是实现困难，开销大
时钟置换算法（CLOCK或NRU）
时钟置换算法是一种性能和开销较均衡的算法，又称CLOCK算法，或最近未用算法（NRU，Not Recently Used）
简单的CLOCK 算法
实现方法
为每个页面设置一个访问位，再将内存中的页面都通过链接指针链接成一个循环队列。当某页被访问时，其访问位置为1。当需要淘汰一个页面时，只需检查页的访问位。如果是0，就选择该页换出；如果是1，则将它置为0，暂不换出，继续检查下一个页面，若第一轮扫描中所有页面都是1，则将这些页面的访问位依次置为0后，再进行第二轮扫描（第二轮扫描中一定会有访问位为0的页面，因此简单的CLOCK 算法选择一个淘汰页面最多会经过两轮扫描）
扫描的过程，像Clock
简单的时钟置换算法仅考虑到一个页面最近是否被访问过。
改进的CLOCK算法
事实上，如果被淘汰页没有被修改过，就不需要执行I/O操作写回外存。只有被淘汰的页面被修改过时，才需要写回外存。
思想
除了考虑一个页面最近有没有被访问过之外，操作系统还应考虑页面有没有被修改过。在其他条件都相同时，应优先淘汰没有修改过的页面，避免I/O操作。
实现方法
将所有可能被置换的页面排成一个循环队列（u访问位,m修改位)
第一轮：从当前位置开始扫描到第一个（0, 0）的帧用于替换。本轮扫描不修改任何标志位
第二轮：若第一轮扫描失败，则重新扫描，查找第一个（0, 1）的帧用于替换。本轮将所有扫描过的帧访问位设为0
第三轮：若第二轮扫描失败，则重新扫描，查找第一个（0, 0）的帧用于替换。本轮扫描不修改任何标志位
第四轮：若第三轮扫描失败，则重新扫描，查找第一个（0, 1）的帧用于替换。
优先级
第一优先级：最近没访问，且没修改的页面 第二优先级：最近没访问，但修改过的页面 第三优先级：最近访问过，但没修改的页面 第四优先级：最近访问过，且修改过的页面
由于第二轮已将所有帧的访问位设为0，因此经过第三轮、第四轮扫描一定会有一个帧被选中，因此改进型CLOCK置换算法选择一个淘汰页面最多会进行四轮扫描
四种算法的比较

页面分配策略
驻留集与分配策略
驻留集
指请求分页存储管理中给进程分配的物理块的集合
分配给进程的存储量越小，则任何时候驻留在主存中的进程数越多，从而可以提高处理机的时间利用效率
若进程在主存中的页数过少，尽管有局部性原理，则页错误率相对较高
若页数过多，则由于局部性原理，给特定的进程分配更多的主存空间对该进程的错误率没有明显影响
分配与置换
分配方式 （驻留集大小是否可变！）
固定分配
操作系统为每个进程分配一组固定数目的物理块，在进程运行期间不再改变。即，驻留集大小不变
可变分配
先为每个进程分配一定数目的物理块，在进程运行期间，可根据情况做适当的增加或减少。即，驻留集大小可变
置换方式
局部置换 (类似覆盖)
发生缺页时只能选进程自己的物理块进行置换。
全局置换 （交换）
可以将操作系统保留的空闲物理块分配给缺页进程，也可以将别的进程持有的物理块置换到外存，再分配给缺页进程。
置换策略
固定分配局部置换
系统为每个进程分配一定数量的物理块，在整个运行期间都不改变。若进程在运 行中发生缺页，则只能从该进程在内存中的页面中选出一页换出，然后再调入需要的页面。
缺点
很难在刚开始就确定应为每个进程分配多少个物理块才算合理。（采用这种策略的系统可以根据进程大小、优先级、或是根据程序员给出的参数来确定为一个进程分配的内存块数）
可变分配全局置换
刚开始会为每个进程分配一定数量的物理块。操作系统会保持一个空闲物理块队 列。当某进程发生缺页时，从空闲物理块中取出一块分配给该进程；若已无空闲物理块，则可选择一个未锁定（操作系统可将内核数据锁定）的页面换出外存，再将该物理块分配给缺页的进程。
缺点
盲目地给进程增加物理块，从而导致系统多道程序的并发能力下降
可变分配局部置换
进程发生缺页时，只允许从该进程在内存的页面选出一页换出外存。如果进程在运行中频繁地缺页，系统会为该进程多分配几个物理块，直至该进程缺页率趋势适当程度；反之，如果进程在运行中缺页率特别低，则可适当减少分配给该进程的物理块。
缺点
需要更复杂的实现，需要更大的开销
调入页面的时机
预调页策略
根据局部性原理，一次调入若干个相邻的页面可能比一次调入一个页面更高效。但如果提前调入的页面中大多数都没被访问过，则又是低效的。因此可以预测不久之后可能访问到的页面，将它们预先调入内存，但目前预测成功率只有50%左右。故这种策略主要用于进程的首次调入，由程序员指出应该先调入哪些部分
运行前的调入
请求调页策略
进程在运行期间发现缺页时才将所缺页面调入内存。由这种策略调入的页 一定会 被访问到，但由于每次只能调入一页，而每次调页都要磁盘I/O操作，因此I/O开销较大。
运行期间的调入
从何处调入页面
外存分为两部分
存放文件的文件区
离散分配法方式
存放对换页面的对换区
采用连续分配的方式
I/O速度快于文件区
存在三种情况
系统拥有足够的对换区空间
页面的调入、调出都是在内存与对换区之间进行，这样可以保 证页面的调入、调出速度很快。在进程运行前，需将进程相关的数据从文件区复制到对换区。
系统缺少足够的对换区空间
凡是不会被修改的数据
直接从文件区调入，由于这些页面不会被修改，因此换出时不必写回磁盘，下次需要时再从文件区调入即可。
对于可能被修改的部分
换出时需写回磁盘对换区，下次需要时再从对换区调入。
UNIX方式
与进程有关的的数据全部放在文件区，故未使用过的页面，都可从文件区调入。若被使用过的页面需要换出，则写回对换区，下次需要时从对换区调入。
抖动
刚刚换出的页面马上又要换入内存，刚刚换入的页面马上又要换出外存，这种频繁的页面调度行为称为抖动，或颠簸。
产生抖动的主要原因
进程频繁访问的页面数目高于可用的物理块数（分配给进程的物理块不够）
工作集
工作集
指在某段时间间隔里，进程实际访问页面的集合。
引入工作集的原因
为进程分配的物理块太少，会使进程发生抖动现象。为进程分配的物理块太多，又会降低系统整体的并发度，降低某些资源的利用率
为了研究为应该为每个进程分配多少个物理块，Denning 提出了进程 “工作集”的概念
工作集大小可能小于窗口尺寸，实际应用中，操作系统可以统计进程的工作集大小，根据工作集大小给进程分配若干内存块。
如：窗口尺寸为5，经过一段时间的监测发现某进程的工作集最大为3，那么说明该进程有很好的局部性，可以给这个进程分配3个以上的内存块即可满足进程的运行需要。
一般来说，驻留集大小不能小于工作集大小，否则进程运行过程中将频繁缺页。
拓展：基于局部性原理可知，进程在一段时间内访问的页面与不久之后会访问的页面是有相关性的。因此，可以根据进程近期访问的页面集合（工作集）来设计一种页面置换算法——选择一个不在工作集中的页面进行淘汰。
第五章 输入\输出(I/O)管理
第四章 文件管理
4.1文件系统基础
文件的概念
文件的基本操作
创建文件（“create 系统调用”)
提供的参数
1. 所需的外存空间大小（如：一个盘块，即1KB)
2. 文件存放路径（"D:/Demo")
3. 文件名（这个地方“认为"新建文本文档.txt")
操作系统在处理 Create 系统调用时，主要做了两件事：
1. 在外存中找到文件所需的空间（结合上小节学习的空闲链表法、位示图、成组链接法等管理策略，找到空闲空间）
2.根据文件存放路径的信息找到该目录对应的目录文件（此处就是 D:/Demo 目录），在目录中创建该文件对应的目录项。目录项中包含了文件名、文件在外存中的存放位置等信息。
删除文件（“delete”系统调用）
提供的参数
1. 文件存放路径（"D:/Demo")
2. 文件名
操作系统在处理 delete系统调用时，主要做了三件事：
1. 根据文件存放路径的信息找到该目录对应的目录文件，从目录中找到文件对应的目录项
2. 根据该目录项记录的文件在外存的存放位置、文件大小等信息，回收文件占用的磁盘块。（回收磁盘块时，根据空闲表法、空闲链表法、位图法等管理策略的不同，需要做不同的处理）
3. 从目录表中删除文件对应的目录项。
打开文件（“open”系统调用）
提供的参数
1. 文件存放路径（"D:/Demo")
2. 文件名
3. 对文件的操作类型（r、rw)
操作系统在处理 open系统调用时，主要做了三件事：
1. 根据文件存放路径的信息找到该目录对应的目录文件，从目录中找到文件名对应的目录项，并检查用户是否有指定操作的权限
2. 将文件项复制到内存中的“打开文件表”中。并将对应的表目的编号返回给用户。之后用户使用打开文件表的编号指明要操作的文件

open系统调用
int open (char *filename ,int flags,mode_t mode)
open 将文件名名转换为文件标识符，返回数字
flags参数指明进程如何访问这个文件 O_RDONLY O_WRONLY O_RDRW
关闭文件（“close”系统调用）
操作系统在处理 delete系统调用时，主要做了三件事：
1. 将进程的打开文件表相应表项删除
2. 回收分配给该文件的内存空间等资源
3. 回收分配给该文件的内存空间等资源,系统打开文件表的打开计数器count 减1,若 count = 0,则删除对应表项。
读文件（“read”系统调用）
提供的参数
打开文件中的索引号
读入多少数据
数据在内存中的位置
操作系统在处理 read 系统调用时，会从读指针指向的外存中，将用户指定大小的数据读入用户指定的内存区域中。
read系统调用： ssize_t read (int fd,void *buf, size_t n)
从描述符为fd的当前文件位置复制最多n个字节到内存位置buf，返回值为-1表示错误，为0表示EOF，否则表示实际传送的字节数量
写文件（“write”系统调用）
提供的参数
打开文件中的索引号
写入多少数据
数据在内存中的位置
操作系统在处理 write 系统调用时，会从用户指定的内存区域中，将指定大小的数据写回写指针指向的外存。
write系统调用： ssize_t write (int fd,const void *buf, size_t n)
从内存位置buf复制至多n个字节到描述符fd的当前文件位置
文件的逻辑结构
按文件是否有结构分类
无结构文件
文件内部的数据就是 系列二进制流或字符流组成。又称“流式文件”。如：Windows 操作系统中的 .txt 文件。
有结构文件
由一组相似的记录组成，又称“记录式文件”。每条记录又若干个数据项组成，如：数据库表文件。一般来说，每条记录有一个数据项可作为关键字（作为识别不同记录的ID）
根据各条记录的长度（占用的存储空间）是否相等
定长记录
可变长记录
根据逻辑上如何组织
顺序文件
文件中的记录一个接一个地顺序排列（逻辑上），记录可以是定长的或可变长的。各个记录在物理上可以顺序存储或链式存储。
通常按照记录存入的时间决定记录的顺序
串结构
记录之间的顺序与关键字无关
顺序结构
记录之间的顺序按关键字排序
链式存储
无法实现随机存取
顺序存储
可变长记录
无法实现随机存取
定长记录
可实现随机存取
若采用串结构，无法快速找到关键字对应的记录
若采用顺序结构，可以快速找到关键字对应的记录（折半查找）
注：一般来说，考试题目中所说的“顺序文件”指的是物理上顺序存储的顺序文件。之后的讲解中提到的顺序文件也默认如此。 可见，顺序文件的缺点是增加/删除一个记录比较困难（如果是串结构则相对简单）
索引文件
索引表本身是定长记录的顺序文件，可以快 速找到第i 个记录对应的索引项。
每当要增加/删除一个记录时，需要对索引表进行修改。
由于索引文件有很快的检索速度，因此主要用于对信息处理的及时性要求比较高的场合。
可以用不同的数据项建立多个索引表。
索引顺序文件
索引顺序文件中，同样会为文件建立一张索引表，但不同的是：并不是每个记录对应一个索引表项，而是一组记录对应一个索引表项。
检索效率
若一个顺序文件有10000个记录，则根据关键字检索文件，只能从头开始顺序查找（这里指的并不是定长记录、顺序结构的顺序文件），平均须查找 5000个记录
若采用索引顺序文件结构，可把 10000 个记录分为√10000 = 100 组，每组 100 个记录。则需要先顺序查找索引表找到分组（共100个分组，因此索引表长度为 100，平均需要查 50 次），找到分组后，再在分组中顺序查找记录（每个分组100 个记录，因此平均需要查 50 次）。可见，采用索引顺序文件结构后，平均查找次数减少为 50+50 = 100 次。
多级索引顺序文件
为了进一步提高检索效率，可以为顺序文件建立多级索引表。例如，对于一个含 10^6 个记录的文件，可先为该文件建立一张低级索引表，每 100 个记录为一组，故低级索引表中共有 10000 个表项（即10000个定长记录），再把这 10000 个定长记录分组，每组100个，为其建立顶级索引表，故顶级索引表中共有 100 个表。
检索效率
Tips: 要为N 个记录的文件建立K 级索引，则最优的分组是每组N^(1/(K+1) 个记录。检索一个记录的平均查找次数是((N^(1/(K+1) )/2) * (K+1)
文件目录
文件控制块FCB
FCB 的有序集合称为“文件目录”，一个FCB就是一个文件目录项。
FCB 中包含了文件的基本信息（文件名、物理地址、逻辑结构、物理结构等），存取控制信息（是否可读/可写、禁止访问的用户名单等），使用信息（如文件的建立时间、修改时间等）。基本的还是文件名、文件存放的物理地址。
FCB名和文件之间的映射。使用户（用户程序）可以实现“按名存取”
对目录进行的操作
显示目录：用户可以请求显示目录的内容，如显示该目录中的所有文件及相应属性 修改目录：某些文件属性保存在目录中，因此这些属性变化时需要修改相应的目录项（如：文件重命名）
搜索
当用户要使用一个文件时，系统要根据文件名搜索目录，找到该文件对应的目录项
创建文件
创建一个新文件时，需要在其所属的目录中增加一个目录项
删除文件
当删除一个文件时，需要在目录中删除相应的目录项
显示目录
用户可以请求显示目录的内容，如显示该目录中的所有文件及相应属性
修改目录
某些文件属性保存在目录中，因此这些属性变化时需要修改相应的目录项（如：文件重命名）
目录结构 (特殊的文件)
单级目录结构
早期操作系统并不支持多级目录，整个系统中只建立一张目录表，每个文件占一个目录项。
单级目录实现了“按名存取”，但是不允许文件重名。
显然，单级目录结构不适用于多用户操作系统。
两级目录结构
早期的多用户操作系统，采用两级目录结构
主文件目录（MFD，Master File Directory）
和用户文件目录（UFD，User Flie Directory）
允许不同用户的文件重名。文件名虽然相同，但是对应的其实是不同的文件
也可以在目录上实现实现访问限制（检查此时登录的用户名是否匹配）。
但是两级目录结构依然缺乏灵活性，用户不能对自己的文件进行分类
多级目录结构
又称树形目录
用户（或用户进程）要访问某个文件时要用文件路径名标识文件，文件路径名是个字符串。各级目录之间用“/”隔开。从根目录出发的路径称为绝对路径。
例如：自拍.jpg 的绝对路径是“/照片/2015-08/自拍.jpg”系统根据绝对路径一层一层地找到下一级目录。刚开始从外存读入根目录的目录表；找到“照片”目录的存放位置后，从外存读入对应的目录表；再找到“2015-08”目录的存放位置，再从外存读入对应目录表；最后才找到文件“自拍.jpg”的存放位置。整个过程需要3次读磁盘I/O操作
使用从当前目录出发的“相对路径”
引入“当前目录”和“相对路径”后，磁盘I/O的次数减少了。这就提升了访问文件的效率。
树形目录结构可以很方便地对文件进行分类，层次结构清晰，也能够更有效地进行文件的管理和保护。
但是，树形结构不便于实现文件的共享。为此，提出了“无环图目录结构”。
无环图目录结构
在树形目录结构的基础上，增加一些指向同一节点的有向边，使整个目录成为一个有向无环图。可以更方便地实现多个用户间的文件共享。
可以用不同的文件名指向同一个文件，甚至可以指向同一个目录（共享同一目录的所有内容）
需要为每个共享结点设置一个共享计数器，用于记录此时有多少个地方在共享该结点。 用户提出删除结点的请求时，只是删除该用户的FCB、并使共享计数器减1，并不会直接删除共享结点。只有共享计数器减为0时，才删除结点
共享文件不同于复制文件。在共享文件中，由于各用户指向的是同一个文件，因此只要其中一个用户修改了文件数据，那么所有用户都可以看到文件数据的变化。
索引结点
索引结点包含除了文件名之外的文件描述信息
当找到文件名对应的目录项时，才需要将索引结点调入内存，索引结点中记录了文件的各种信息，包括文件在外存中的存放位置，根据“存放位置”即可找到文件。
存放在外存中的索引结点称为“磁盘索引结点”
当索引结点放入内存后称为“内存索引结点”
相比之下内存索引结点中需要增加一些信息，比如：文件是否被修改、此时有几个进程正在访问该文件等。
文件保护
口令保护
为文件设置一个“口令＂（如：abc112233)，用户请求访问该文件时必须供“口令＂
口令一般存放在文件对应的 FCB 或索引结点中。用户访问文件前需要先输入“口令”，操作系统会将用户提供的口令与FCB中存储的口令进行对比，如果正确，则允许该用户访问文件
优点：保存口令的空间开销不多，验证口令的时间开销也很小。
缺点：正确的＂口令“存放在系统内部，不够安全。
加密保护
使用某个“密码”对文件进行加密，在访问文件时需要提供正确的“密码”才能对文件进行正确的解密。
优点：保密性强，不需要在系统中存储“密码”
缺点：编码/译码，或者说加密/解密要花费一定时间。
访问控制
在每个文件的FCB（或索引结点）中增加一个访问控制列表（Access-Control List, ACL），该表中记录了各个用户可以对该文件执行哪些操作。 每个文件都有一个自己的访问控制表
精简的访问列表
以“组”为单位，标记各“组”用户可以对文件执行哪些操作。 如：分为系统管理员、文件主、文件主的伙伴、其他用户几个分组。
当某用户想要访问文件时，系统会检查该用户所属的分组是否有相应的访问权限。
文件共享
基于索引结点的文件共享方式（硬链接）
利用符号链实现文件共享（软链接）
为使用户B能共享用户A的文件F，由系统创建一个LINK类型的新文件，也取名为F，并将F写入用户B的目录中，在新文件只包含文件F的路径名
相当于快捷方式
只有文件的拥有者才拥有指向其索引结点的指针，而共享该文件的其他用户只有该文件的路径名，并不拥有指向其索引结点的指针
当文件拥有者删除共享文件后，第一时间这个符号链还存在，其他用户通过符号链访问它，会出现访问失败，于是将符号链删除
存在的问题
当文件拥有者删除共享文件后，有人在同一路径下创建了另一个同一名称的文件，则该符号链仍然有效，会导致错误
硬链接和软链接都是静态链接的方法，文件系统中还存在着两个进程对同一个文件进行操作，即动态链接
4.2文件系统实现
文件实现
文件的物理结构 （文件分配方式） （对已分配的空间的管理）
类似于内存分页，磁盘中的存储单元也会被分为一个个“块/磁盘块/物理 块”。很多操作系统中，磁盘块的大小与内存块、页面的大小相同
内存与磁盘之间的数据交换（即读/写操作、磁盘I/O）都是以 “块”为单位进行的。即每次读或每次写出一块
同样的，在外存管理中，为了方便对文件数据的管理，文件的逻辑地址空间也被分为了一个一个的文件“块”。于是文件的逻辑地址也可以表示为（逻辑块号，块内地址）的形式
分类
连续分配
连续分配方式要求每个文件在磁盘上占有一组连续的块
用户给出要访问的逻辑块号，操作系统找到该文件对应的目录项（FCB）…物理块号= 起始块号+ 逻辑块号，当然，还需要检查用户提供的逻辑块号是否合法（逻辑块号≥长度 就不合法）
缺点
物理上采用连续分配的文件不方便拓展。
物理上采用连续分配，存储空间利用率低，会产生难以利用的磁盘碎片(外部碎片）可以用紧凑来处理碎片，但是需要耗费很大的时间代价
优点
读取某个磁盘块时，需要移动磁头。访问的两个磁盘块相隔越远，移动磁头所需时间就越长。因此，连续分配的文件在顺序读/写时速度最快
连续分配支持顺序访问和直接访问（即随机访问）
链式分配
链接分配采取离散分配的方式，可以为文件分配离散的磁盘块。分为隐式链接和显式链接两种。
隐式链接
目录中记录了文件存放的起始块号和结束块号。当然，也可以增加一个字段来表示文件的长度
除了文件的最后一个磁盘块之外，每个磁盘块中都会保存指向下一个盘块的指针，这些指针对用户是透明的
从目录项中找到起始块号（即0号块），将0号逻辑块读入内存，由此知道1号逻辑块存放的物理块号，于是读入1号逻辑块，再找到2号逻辑块的存放位置……以此类推。因此，读入i号逻辑块，总共需要 i+1 次磁盘 I/O操作
缺点
只支持顺序访问，不支持随机访问，查找效率低
指向下一个盘块的指针也需要耗费少量的存储空间。
优点
很方便文件拓展
所有的空闲磁盘块都可以被利用，不会有碎片问题，外存利用率高
显式链接
把用于链接文件各物理块的指针显式地存放在一张表中。即文件分配表（FAT）
目录中只需记录文件的起始块号
一个磁盘仅设置一张FAT。开机时，将FAT读入内存，并常驻内存。
FAT 的各个表项在物理上连续存储，且每一个表项长度相同，因此“物理块号”字段可以是隐含的。
过程
用户给出要访问的逻辑块号i，操作系统找到该文件对应的目录项（FCB）从目录项中找到起始块号
若i>0，则查询内存中的文件分配表FAT，往后找到i 号逻辑块对应的物理块号。逻辑块号转换成物理块号的过程不需要读磁盘操作。
操作系统也可以通过FAT对文件的存储空间进行管理，当某进程请求操作系统分配个磁盘块时，操作系统只需在FAT中找到-2的的表项，然后分配给进程
缺点
文件分配表的需要占用一定的存储空间。
优点
很方便文件拓展，不会有碎片问题，外存利用率高，并且支持随机访问。
相比于隐式链接来说，地址转换时不需要访问磁盘，因此文件的访问效率更高。
考试题目中遇到未指明隐式/显式的“链接 分配”，默认指的是隐式链接的链接分配
索引分配
索引分配允许文件离散地分配在各个磁盘块中，系统会为每个文件建立一张索引表，索引表中记录了文件的各个逻辑块对应的物理块（索引表的功能类似于内存管理中的页表——建立逻辑页面到物理页之间的映射关系）。
索引表存放的磁盘块称为索引块。文件数据存放的磁盘块称为数据块。
目录中需要记录文件的索引块是几号磁盘块
索引分配方式中，索引表是一个文件对应一张。 （FAT表是一个文件对应一张）
因此，索引表中的“逻辑块号”可以是隐含的
过程
用户给出要访问的逻辑块号i
操作系统找到该文件对应的目录项（FCB),从目录项中可知索引表存放位置，将索引表从外存读入内存，并查找索引表即可只i 号逻辑块在外存中的存放位置。
缺点
但是索引表需要占用一定的存储空间
优点
索引分配方式可以支持随机访问。
文件拓展也很容易实现（只需要给文件分配一个空闲块，并增加一个索引表项即可）
如何解决一个块装不下一张索引表的问题
链接方案
如果索引表太大，一个索引块装不下，那么可以将多个索引块链接起来存放。
多层索引
建立多层索引（原理类似于多级页表）。
使第一层索引块指向第二层的索引块。还可根据文件大小的要求再建立第三层、第四层索引块。
若采用多层索引，则各层索引表大小不能超过一个磁盘块
采用K层索引结构，且顶级索引表未调入内存，则访问一个数据块只需要K+1次读磁盘操作
混合索引
多种索引分配方式的结合
例如，一个文件的顶级索引表中，既包含直接地址索引（直接指向数据块），又包含一级间接索引（指向单层索引表）、还包含两级间接索引（指向两层索引表） 。
重要考点
①要会根据多层索引、混合索引的结构计算出文件的最大长度（Key：各级索引表最大不能超过一个块）；
②要能自己分析访问某个数据块所需要的读磁盘次数（Key：FCB中会存有指向顶级索引块的指针，因此可以根据FCB读入顶级索引块。每次读入下一级的索引块都需要一次读磁盘操作。另外，要注意题目条件——顶级索引块是否已调入内存）
“文件的某种逻辑结构支持随机存取/随机访问”是指：采用这种逻辑结构的文件，可以根据记录号直接算出该记录对应的逻辑地址（逻辑块号，块内地址）。
逻辑地址与物理地址 （串联成体系）
用户决定以顺序存储
用户看起来连续的逻辑地址，操作系统可以采用任意分配方式，对用户透明
连续分配
链式分配
索引分配
用户决定以链式存储
区别链式存储与链接分配 链式存储：用户决定 连接分配：系统决定
连续分配
链式分配
索引分配
用户决定以索引分配
连续分配
链式分配
索引分配
文件存储空间管理 （未分配的空间）
存储空间的划分与初始化
安装 Windows 操作系统的时候，一个必经步骤是——为磁盘分区（C: 盘、D: 盘、E: 盘等）
存储空间的初始化
将各个文件卷划分为目录区、文件区
目录区主要存放文件目录信息（FCB）、用于磁盘存储空间管理的信息
文件区用于存放文件数据
存储空间的划分
将物理磁盘划分为一个个文件卷（逻辑卷、逻辑盘）
有的系统支持超大型文件，可支持由多个物理磁盘组成一个文件卷
空闲表法
适用于“连续分配方式”
如何分配磁盘块：与内存管理中的动态分区分配很类似，为一个文件分配连续的存储空间
同样可采用首次适应、最佳适应、最坏适应等 算法来决定要为文件分配哪个区间。
与内存分配类似，分配时要注意表项的合并问题
空闲链表法
空闲盘块法
空闲盘块中存储着下一个空闲盘块的指针
操作系统保存着链头、链尾指针。
如何分配
若某文件申请K 个盘块，则从链头开始依次摘下K 个盘块分配，并修改空闲链的链头指针。
如何回收
回收的盘块依次挂到链尾，并修改空闲链的链针。
适用于离散分配的物理结构。为文件分配多个盘块时可能要重复多次操作
空闲盘区法
连续的空闲盘块组成一个空闲盘区
空闲盘区中的第一个盘块内记录了盘区的长度、下一个盘区的指针
操作系统保存着链头、链尾指针。
如何分配
若某文件申请K 个盘块，则可以采用首次适应、最佳适应等算法，从链头开始检索， 按照算法规则找到一个大小符合要求的空闲盘区，分配给文件。
若没有合适的连续空闲块，也可以将不同盘区的盘块同时分配给一个文件，注意分配后可能要修改相应的链指针、盘区大小等数据。
如何回收
若回收区和某个空闲盘区相邻，则需要将回收区合并到空闲盘区中。若回收区没有和任何空闲区相邻，将回收区作为单独的一个空闲盘区挂到链尾。
离散分配、连续分配都适用。为一个文件分配多个盘块时效率更高
位示图法
位示图
每个二进制位对应一个盘块。在本例中，“0”代表盘块空闲， “1”代表盘块已分配。
位示图一般用连续的“字”来表示，如本例中一个字的字长是16位，字中的每一位对应一个盘块。因此可以用（字号，位号）对应一个盘块号。当然有的题目中也描述为（行号，列号）
注意题目条件：盘块号、字号、位号到底是从0开始还是从1开始
(字号, 位号)=(i, j) 的二进制位对应的盘块号b = ni + j（从0开始）
b号盘块对应的字号i = b/n，位号j = b%n（从0开始）
如何分配
若文件需要K个块
①顺序扫描位示图，找到K个相邻或不相邻的“0”；
②根据字号、位号算出对应的盘块号，将相应盘块分配给文件；
③将相应位设置为“1”。
如何回收
①根据回收的盘块号计算字号、位号；
②将相应二进制位设为“0”
成组链接法
空闲表法、空闲链表法不适用于大型文件系统，因为空闲表或空闲链表可能过大。UNIX系统中采用了成组链接法对磁盘空闲块进行管理。
文件卷的目录区中专门用一个磁盘块作为“超级块”，当系统启动时需要将超级块读入内存。并且要保证内存与外存中的“超级块”数据一致。
如何分配？
Eg ：需要100个空闲块 ①检查第一个分组的块数是否足够。100=100，是足够的。 ②分配第一个分组中的100个空闲块。但是由于300号块内存放了再下一组的信息，因此 300号块的数据需要复制到超级块中。 成组链接法存放的只有空闲块的信息，所以分配后，要把已分配的块直接从超级块链表中剔除，链接原结点所指向的下一组结点信息
如何回收？
Eg ：假设每个分组最多为100个空闲块，此时第一个分组已有99个块，还要再回收一块。需要将超级块中的数据复制到新回收的块中，并修改超级块的内容，让新回收的块成为第一个分组。
4.3磁盘的组织和管理
磁盘的结构
磁盘
磁盘的表面由一些磁性物质组成，可以用这些磁性物质来记录二进制数据
磁道
磁盘的盘面被划分成一个个磁道。这样的一个＂圈”就是一个磁道
扇区
一个磁道又被划分成一个个扇区，每个扇区就是一个 “磁盘块”。各个扇区存放的数据量相同（如1KB)
最内侧磁道上的扇区面积最小，因此数据密度最大
盘面和柱面
一个盘片可能会有两个盘面
每个盘面对应一个磁头
所有盘面中相对位置相同的磁道组成柱面
所有的磁头都是连在同一个磁臂上的，因此所有磁头只能“共进退”
如何在磁盘中读/写数据
可根据该地址读取一个＂块“
1. 根据＂柱面号“移动磁臂，让磁头指向指定柱面；
2. 激活指定盘面对应的磁头；
3. 磁盘旋转的过程中，指定的扇区会从磁头下面划过，这样就完成了对指定扇区的读
磁盘的物理地址
可用（柱面号，盘面号，扇区号）来定位任意一个“磁盘块”。
磁盘的分类
活动头磁盘
磁头可以移动的称为活动头磁盘。磁臂可以来回伸缩来带动磁头定位磁道
固定头磁盘
磁头不可移动的称为固定头磁盘。这种磁盘中每个磁道有一个磁头
可换盘磁盘
盘片可以更换
固定盘磁盘
盘片不可更换
磁盘调度算法
一次磁盘读/写操作需要的时间
寻找时间（寻道时间）Ts:在读/写数据前，将磁头移动到指定磁道所花的时间。
启动磁头臂是需要时间的。假设“耗时为s;
移动磁头也是需要时间的。假“磁头匀速移动，每跨越一个磁道耗时m,共需要跨越n 条磁道
寻道时间Ts=s+m*n
操作系统的磁盘调度算法会直接影响寻道时间
延迟时间TR:通过旋转磁盘，使磁头定位到目标扇区所需要的时间。
磁盘转速为r 转/分），则平均所需的延迟时间TR=(1/2)*(1/r)=1/2r
传输时间Tt:从磁盘读出或向磁盘写入数据所经历的时间
假设“磁盘转速为r,此次读/写的字节数为b,每个磁道上的字节数为N。则传输时间T=(1/r)*b/N
总的平均存取时间Ta = Ts + 1/2r + b/(rN)
先来先服务算法(FCFS)
根据进程请求”问磁盘的先后顺序进行调度。
优点
公平
如果请求”问的磁道比较集中的话，算法性能还算过的去
缺点
如果有大量进程竞争使用磁盘，请求访问的磁道很分散，则FCFS在性能上很差，寻道时间长。
最短时间优先算法（SSTF)
SSTF 算法会优先处理的磁道是与当前磁头最近的磁道。可以保证每次的寻道时间最短，但是并不能保证总的寻道时间最短。（其实就是贪心算法的思想，只是选择眼前最优，但是总体未必最优）
优点
性能较好，平均寻道时间短
缺点
可能产生”饥饿“现象
产生饥饿的原因在于：磁头在一个小区域内来回来去地移动
扫描算法(SCAN)
只有磁头移动到 最外侧磁道的时候才往内移动，移动到最内侧磁道的时候才能往外移动。这就是扫描算法(SCAN）的思想。由于磁头移动的方式很像电梯，因此也叫电梯算法。
优点
性能较好，平均寻道时间较短，不会产生饥饿现象
缺点
只有到达最边上的磁道时才能改变磁头移动方向。
SCAN算法对于各个位置磁道的响应频率不平均
LOOK算法
如果磁头在移动方向没有别的请求，就可以改变磁头的移动方向
优点
比起 SCAN 算法来，不需要每次都移动到最外侧或最内侧才改变磁头方向，使寻道时间进一步缩短
缺点
子主题
循环扫描算法(C-SCAN)
规定只有磁头朝某个特定方向移动时才处理磁道”问请求，而返回时直接快速移动至起始端而不处理任何请求。
优点
比起SCAN 来，对于各个位置磁道的响应频率很平均。
缺点
只有到达最边上的磁道时才能改变磁头移动方向，事实上，处理了184号磁的”问请求之后就不需要再往右移动磁头了；并且，磁头返回时其实只需要返回到18号磁道即可，不需要返回到最边缘的磁道。
另外，比起SCAN算法来，平均寻道时间更长。
C-LOOK调度算法
C-LOOK 算法就是为了解决这个问题。如果磁头移动的方向上已经没有磁道”访问请求了，就可以立即让磁头返回，并且磁头只需返回到有磁道访问请求的位置即可。
优点
比起 C-SCAN 算法来，不需要每次都移动到最外侧或最内侧才改变磁头方向，使寻道时间进一步缩短
若无特殊说明，默认SCAN算法和C-SCAN算法为LOOK和C-LOOK算法
减少延迟时间的方法
问题提出的原因
假设要连续读取橙色区域的磁头读取一块的内容（也就是一个扇区的内容）后，需要一小段时间处理，而盘片又在不停地旋转，因此，如果2、3号扇区相邻着排列，则读完2号扇区后无法连续不断地读入3号扇区，必须等盘片继续旋转， 3号扇区再次划过磁头，才能完成扇区读入
问题得出的结论
磁头读入一个扇区数据后需要一小段时间处理，如果逻辑上相邻的扇区在物理上也相邻，则读入几个连续的逻辑扇区，可能需要很长的＂延迟时间”
减少延迟时间的方法：交替编号
若采用交替编号的策略，即让逻辑上相邻的扇区在物理上有一定 的间隔，可以使读取连续的逻辑扇区所需要的延迟时间更小。
减少延迟时间的方法：错位命名（不同盘面之间错位命名）
方案一：若相邻的盘面相对位置相同处扇区编号相同
所有盘面都是在一起连轴转的
读取完磁盘块(000, 00, 111)之后，需要 短暂的时间处理，而 盘面又在不停地转动，因此当(000, 01, 000)第一次划过1号盘面的磁头下方时，并不能读取数据，只能再等该扇区再次划过磁头。
方案二：错位命名
由于采用错位命名法，因此读取完磁盘块 (000, 00, 111)之后， 还有一段时间处理，当(000, 01, 000)第一次划过1号盘面的 磁头下方时，就可以直接读取数据。从而减少了延迟时间
磁盘地址结构的设计
为什么磁盘的物理地址是（柱面号，盘面号，扇区号） 而不是（盘面号，柱面号，扇区号）？
原因
假设某磁盘有8个柱面/磁道(假设最内侧柱面/磁道号为0 )， 4个盘面，8个扇区。则可用3个二进制位表示柱面，2个二进 制位表示盘面，3个二进制位表示扇区。
若物理地址结构是(盘面号，柱面号，扇区号)，且需要连续读取物理地址(00, 000, 000)~(00, 001, 111)的扇区： (00, 000, 000) ~( 00, 000, 111 ) 转两圈可读完， 之后再读取物理地址相邻的区域，即(00, 001, 000) ~( 00, 001, 111 )，需要启动磁头臂，将磁头移动到下一个磁道
若物理地址结构是(柱面号，盘面号，扇区号)，且需要连续读取物理地址(000, 00, 000)~(000, 01, 111)的扇区： (000, 00, 000) ~( 000, 00, 111 ) 由盘面0的磁头读入数据之后再读取物理地址相邻的区域，即(000, 01, 000) ~( 000, 01, 111 )，由于柱面号/磁道号相同， 只是盘面号不同，因此不需要移动磁头臂。只要激活相邻磁头即可
读取地址连续的磁盘块时，采用（柱面号， 盘面号，扇区号）的地址结构可以减少磁头移 动消耗的时间
磁盘的管理
磁盘初始化
1. 进行低级格式化（物理格式化）
将磁盘的各个磁道划分为扇区。一个扇区通常可分为头、数据区域（如512B大小）、尾三个部分组成。管理扇区所需要的各种数据结构一般存放在头、尾两个部分，包括扇区校验码（如奇偶校验、CRC循环冗余校验码等，校验码用于校验扇区中的数据是否发生错误）
2. 将磁盘分区
每个分区由若干柱面组成（即分为我们熟悉的C盘、D盘、E盘）
3. 进行逻辑格式化
创建文件系统。包括创建文件系统的根目录、初始化存储空间管理所用的数据结构（如位示图、空闲分区表）
引导块
计算机开机时需要进行一系列初始化的工作，这些初始化工作是通过执行初始化程序（自举程序）完成的
ROM只存放很小的“自举装入程序”,完整的自举程序放在磁盘的启动块（即引导块/启动分区）上，启动块位于磁盘的固定位置。
拥有启动分区的磁盘称为启动磁盘或系统磁盘(如C盘）
开机时计算机先运行“自举装入程序”，通过执行该程序就可 找到引导块，并将完整的“自举程序”读入内存，完成初始化
坏块的管理
坏块
坏了、无法正常使用的扇区就是“坏块”。这属于硬件故障，操作系统是无法修复的。应该将坏块标记出来，以免错误地使用到它
对千简单的磁盘，可以在逻辑格式化时（建立文件系统时）对整个磁盘进行坏块检查，标明哪些扇区是坏扇区，比如：在 FAT 表上标明。（在这种方式中，坏块对操作系统不透明）
对于复杂的磁盘，磁盘控制器（磁盘设备内部的一个硬件部件）会维护一个坏块链表。在磁盘出厂前进行低级格式化（物理格式化）时就将坏块链进行初始化。 会保留一些“备用扇区”，用于替换坏块。这种方案称为扇区备用。且这种处理方式中，坏块对操作系统透明。
文件系统层次结构
第五章 I/O管理
5.1I/O管理概述
IO设备分类
块设备
字符设备
IO控制器
I/O控制方式
程序直接控制方式
轮询
中断驱动方式
DMA方式
数据传送单位是块(前两种是字符流) 只能IO连续的块，离散的不行
通道控制方式
传送的单位是是一组数据块
与CPU相比，通道可以执行的指令很单一，并且通道程序是放在主机内存中的，也就是说通道与CPU共享内存
I/O子系统的层次结构
用户层软件
用户层软件实现了与用户交互的接口，用户可直接使用 该层提供的、与I/O操作相关的库函数对设备进行操作
用户层软件将用户请求翻译成格式化的I/O请求，并通过“系统调用“请求操作系统内核的服务
假脱机技术(SPOOLing技术） (408中认为处于IO子系统中)
设备独立性/设备无关性软件
设备独立性软件，又称设备无关性软件。与设备的硬件特性无关的功能几乎都在这一层实现。
主要实现的功能
1. 向上层提供统一的调用接口（如 read/write 系统调用）
2. 设备的保护
原理类似与文件保护。设备被看做是一种特殊的文件，不同用 户对各个文件的访问权限是不一样的，同理，对设备的访问权 限也不一样。
3. 差错控制
设备独立性软件需要对一些设备的错误进行处理
4. 设备的分配与回收
5. 数据缓冲区管理
可以通过缓冲技术屏蔽设备之间数据交换单位大小和传送速度的差异
6. 建立逻辑设备名到物理设备名的映射关系；根据设备类 型选择调用对应的驱动程序
设备独立性软件需要通过“逻辑设备表(LUT,Logical Unit Table)"来确定逻辑设备对应的物理设备,并找到该设备对应的设备驱动程序
操作系统系统可以采用两种方式管理逻辑设备表(LUT)
第一种方式，整个系统只设置一张LUT，这就意味着所有用户不能使用相同的逻辑设备名，因此这种方式只适用于单用户操作系统。
第一种方式，为每个用户设置一张LUT，这就意味着各个用户使用的逻辑设备名可以重复，因此这种方式只适用于多用户操作系统。用户登录时为其建立一个用户管理进程，而LUT就放在PCB中
I/O调度、设备保护、 设备的分配与回收、缓冲区管理
设备驱动程序
主要负责对硬件设备的具体控制，将上层发出的一系列命令（如 read/write)转化成特定设备“能听得懂＂的一系列操作。包括设置 设备寄存器；检查设备状态等
不同设备的内部硬件特性也不同，这些特性只有厂家才知道，因此厂家须提供与设备对应的驱动程序，CPU执行驱动程序的指令序列，来完成设置设备寄存器，检查设备状态等工作
中断处理程序
当I/O任务完成时，I/O控制器会据中断信号类型找到相应的中断处理程序并执行。
中断处理程序

硬件
只需理解一个特点即可：直接涉及到硬件具体细节、且与中断无关的操作肯定是在设备驱动程序层完成的；没有涉及硬件的、对各种设备都需要进行的管理工作都 是在设备独立性软件层完成的）
与硬件相关：设备驱动程序；中断处理程序
5.2I/O核心子系统
I/O调度
I/O调度：用某种算法确定一个好的顺序来处理各个I/O请求。
如磁盘调度
打印机等设备也可以用FCFS算法等算法来确定I/O调度顺序
假脱机技术(SPOOLing技术）
脱机技术
批处理阶段引入了脱机输入/输出技术（用磁带完成）
在外围控制机的控制下，慢速输入设备的数据先被输入到更快速的磁带上。之后主机可以从快速的磁带上读入数据，从而缓解了速度矛盾
引入脱机技术后，缓解了CPU和慢速I/O设备的速度矛盾。另一方面，即使CPU在忙碌，也可以提前将数据输入到磁带；即使慢速的输出设备正在忙碌，也可以提前将数据输出到磁带。
假脱机技术”，又称“SPOOLing 技术”是用软件的方式模拟脱机技术。

在磁盘上开辟出两个存储区域——“输入井”和“输出井”
“输入井”模拟脱机输入时的磁带，用于收容I/O设备输入的数据
“输入进程”模拟脱机输入时的外围控制机
“输出进程”模拟脱机输出时的外围控制机
“输出井”模拟脱机输出时的磁带，用千收容用户进程输出的数据
在输入进程的控制下，＂输入缓冲区“用于暂存从输入设备输入的数据，之后再转存到输入井中
在输出进程的控制下，＂输出缓冲区“用于暂存从输出井送来的数据，之后再传到到输出设备上
输入输出缓冲区在内存中
共享打印机原理分析
独占式设备——只允许各个进程串行使用的设备。一段时间内只能满足一个进程的请求。
共享设备——允许多个进程”同时“使用的设备（宏观上同时使用，微观上可能是交替使用）。可以同时满足多个进程的使用请求。
打印机是独占式设备，但是可以用SPOOLing 技术改造成“共享设备”

要实现SPOOLing 技术，必”要有多道程序技术的支持。系统会建立“输入进程”和“输出进程”。
设备的分配与回收
设备分配时应考虑的因素
设备的固有属性
独占设备
共享设备
虚拟设备
采用 SPOOLing 技术将独占设备改造成虚拟的共享设备，可同时分配给多个进程使用（如采用 SPOOLing 技术实现的共享打印机）
设备分配算法
设备分配的安全性
安全分配方式
为进程分配一个设备后就将进程阻塞，本次I/O完成后才将进程唤醒。(eg：考虑 进程请求打印机打印输出的例子）
优点：破坏了“请求和保持“条件，不会死锁
缺点：对于一个进程来说，CPU和I/O设备只能串行工作
不安全分配方式
进程发出I/O请求后，系统为其分配I/O设备，进程可继续执行，之后还可以发出新的I/O请求。只有某个I/O请求得不到满足时才将进程阻塞。
优点：进程的计算任务和I/O任务可以并行处理，使进程迅速推进
缺点：有可能发生死锁（死锁避免、死锁的检测和解除）
设备分配方式
静态分配：进程运行前为其分配全部所需资源，运行结束后归还资源 破坏了“请求和保持“条件，不会发生死锁
动态分配：进程运行过程中动态申请设备资源
设备分配管理中的数据结构
一个通道可控制多个设备控制器，每个设备控制器可控制多个设备
设备控制表(DCT)
系统为每个设备配置一张DCT，用于记录设备情况

控制器控制表(COCT)
每个设备控制器都会对应一张COCT。操作系统根据COCT的信息对控制器 进行操作和管理。

通道控制表(CHCT)
每个通道都会对应一张CHCT。操作系统根据CHCT的信息对通道进行操作和 管理。

系统设备表(SDT)
记录了系统中全部设备的情况，每个设备对应一个表目。

设备分配的步骤
1. 根据进程请求的物理设备名查找SDT（注：物理设备名是进程请求分配设备时提供的参数）
2. 根据SDT找到DCT,若设备忙碌则将进程PCB挂到设备等待队列中,不忙碌则将设备分配给进程。
3. 根据DCT找到COCT,若控制器忙碌则将进程PCB挂到控制器等待队列中,不忙碌则将控制器分配给进程。
4. ＠根据COCT找到CHCT,若通道忙碌则将进程PCB挂到通道等待队列中,不忙碌则将通道分配给进程。
注：只有设备、控制器、通道三者都分配成功时，这次设备分配才算成功，之后便可启动I/O设备进行数据传送
设备分配步骤的改进
原设备分配的缺点
用户编程时必须使用“物理设备名”，底层细节对用户不透明，不方便编程
若换了一个物理设备，则程序无法运行
若进程请求的物理设备正在忙碌，则即使系统中还有同类型 的设备，进程也必须阻塞等待
改进方法：建立逻辑设备名与物理设备名的映射机制，用户编 程时只需提供逻辑设备名

逻辑设备表(LUT)建立了逻辑设备名与物理设备名之间的 映射关系。
某用户进程第一次使用设备时使用逻辑设备名向操作系统发出请求，操作系统根据用户进程指定的设备类型（逻辑设备名）查找系统设备表，找到一个空闲设备分配给进程，并在 LUT中增加相应表项。
如果之后用户进程再次通过相同的逻辑设备名请求使用设备，则操作系统通过LUT表即可知道用户进程实际“使用的是哪个物理设备了，并且也能知道该设备的驱动程序入口地址。
缓冲区管理
缓冲区
缓冲区是一个存储区域，可以由专门的硬件寄存器组成，也可利用内存作为缓冲区。
使用硬件作为缓冲区的成本较高，容量也较小，一般仅用在对速度要求非常高的场合（如存储器管理中所用的联想寄存器，由千对页表的访问频率极高，因此使用速度很快的联想寄存器来存放页表项的副本）
一般情况下，更多的是利用内存作为缓冲区，“设备独立性软件”的缓冲区管理就是要组织管理好这些缓冲区
缓冲区的作用
缓和CPU和I/O速度不匹配的矛盾
减少CPUI/O的中断频率，放宽对CPU响应时间的限制
解决基本数据单元（数据粒度）不匹配的问题
如：“出进程每次可以生成一块数 但I/O设备每次只能“出一个字符“
提高CPU和I/O的并行性
单缓冲
假设某用户进程请求某种块设备读入若干块的数据。若采用单缓冲的策略，操作系统会在主存中为其分配一个缓冲区（若题目中没有特别说明，一个缓冲区的大小就是一个块）。
注意：当缓冲区数据非空时，不能往缓冲区冲入数据，只能从缓冲区把数据传出；当缓冲区为空时，可以往缓冲区冲入数据，但必须把缓冲区充满以后，才能从缓冲区把数据传出。
常考题型：计算每处理一块数 据平均需要多久？
技巧：假定一个初始状态，分析下 次到”相同状态需要多少时间，这 就是处理一块数据平均所需时间。

结论：采用单缓冲策略，处理一块数据平均耗时MAX(T,C)+M
双缓冲
假设某用户进程请求某种块设备读入若干块的数据。若采用双缓冲的策略，操作系统会在主存中为其分配两个缓冲区（若题目中没有特别说明，一个缓冲区的大小就是一个块）


结论：采用双缓冲策略，处理一个数据块的平均耗时为MAX(T,C+M)
使用单/双缓冲在通信时的区别
显然，若两个相互通信的机器只设置单缓冲区，在任一时刻只能实现数据的单向传输
循环缓冲区
将多个大小相等的缓冲区链接成一个循环队列。
in 指针，指向下一个可以冲入数据的空缓冲区
out 指针，指向下一个可以取出数据的满缓冲区
缓冲池
缓冲池由系统中共用的缓冲区组成。
这些缓冲区按使用状况可以分为
空缓冲队列
装满输入数据的缓冲队列（输入队列）
装满输出数据的缓冲队列（输出队列）
根据一个缓冲区在实际运算中扮演的功能不同
用于收容输入数据的工作缓冲区（hin）
用于提取输入数据的工作缓冲区（sin)
用于收容输出数据的工作缓冲区（hout)
用于提取数据的工作缓冲区（sout)

输入进程需要输入数据时
从空缓冲队列中取出一块作为收容输入数据的工作缓冲区(hin)。冲满数据后将缓冲区挂到输入队列队尾
计算进程想要取得一块输入数据
从输入队列中取得一块冲满输入数据的缓冲区作为 “提取”输入数据的工作缓冲区(sin)"。缓冲区读空后挂到空缓冲区队列
计算进程想要将准备好的数据冲入缓冲区
从空缓冲队列中取出一块作为“收容输出数据的工作缓冲区(hout)"。数据冲满后将缓冲区挂到输出队列队尾
输出进程请求输出数据时
从输出队列中取得一块冲满输出数据的缓冲区作为 ”提取“出数据的工作缓冲区(sout)"。缓冲区读空后挂到空缓冲区队列
教材补充
通道类型
字节多路通道
每个子通道连接一台I/O设备
子通道通过时间片共享主通道
不适于连接高速设备
数组选择通道
可以连接多台高速设备
只含有一个分配型子通道
通道的利用率低
数组多路通道
含有多个非分配型子通道
通道既具有很高的数据传输速率，又有令人满意的通道利用率
广泛用于连接多台高、中速的外围设备
数据传输按数组方式进行
设备驱动程序的处理过程
将抽象要求转换为具体要求
例如将抽象的盘块号转换为盘面、磁道号和扇区
对服务请求进行校验
如用户请求从打印机输入数据，驱动程序能检查出非法
检查设备的状态
检查设备控制器中的状态寄存器
传送必要的参数
如利用RS232C接口进行异步通信，应设定波特率、奇偶校验方式、停止位数目及数据字节长度
启动I/O设备
向控制器的命令寄存器传送相应的控制命令