操作系统
计算机系统概述
操作系统的基本概念
操作系统的定义
- 操作系统是系统资源的管理者
- 向上提供方便使用的服务
- 是最接近硬件的一层软件
操作系统的功能
1.作为系统资源管理者
- 处理机管理
- 存储器管理
- 文件管理
- 设备管理
2.向上提供方便易用的服务
操作系统把一些丑陋的硬件功能封装成简单易用的服务，使用户能更方便地使用计算机，用户无需关心底层硬件的原理，只需要对操作系统发出命令即可。
向上提供服务：
- 给普通用户提供的：GUI、命令接口(联机、脱机)
- 给程序员提供的：程序接口(系统调用)
例如GUI图形化用户接口：用户可以直观理解界面进行操作，方便用户使用
例如联机命令接口，也称交互式命令接口—说一句做一句
例如脱机命令接口，也称批处理命令接口—说一堆，做一堆
例如程序接口—利用系统调用
3.作为最接近硬件的层次
没有任何软件支持的计算机成为裸机。在裸机上安装的操作系统，可以提供资源管理功能和方便用户的服务功能，将裸机改造成功能更强、使用更方便的机器
操作系统的四个特征
没有并发性和共享性，就谈不上虚拟和异步，因此并发和共享是操作系统最基本的两个特征
1.并发性
- 并发：指两个或多个事件在同一时间间隔内发生。这些事件宏观上是同时发生的，但微观上是交替发生的。
- 并行：指两个或多个事件在同一时刻同时发生。
2.共享性
共享：即资源共享，是指系统中的资源可供内存中多个并发执行的进程共同使用。
(1)资源共享根据属性可分为两种形式：
- 互斥共享形式:（当资源被程序A占用时,其他想使用的话只能等待，只有进程A使用完以后,其他进程才可以使用该资源）
- 同时访问形式 :（某种资源在一段时间内并发地被多个程序访问，这种“同时”是宏观的,从宏观去看该资源可以被同时访问,本质是一种微观的互斥共享）
(2)并发性与共享性互为存在条件
3.虚拟性
- 虚拟：是把一个物理上的实体变为若干逻辑上的对应物。
- 物理实体（前者）是实际存在的；而后者是虚的，是用户感觉上的事务
- 虚拟技术：用于实现虚拟的技术
- 虚拟处理器（CPU）：通过多道程序设计技术，采用让多道程序并发执行的方法，分时来使用一个CPU，实际物理上只有一个CPU，但是用户感觉到有多个CPU
- 虚拟存储器：从逻辑上扩充存储器容量，用户感觉到的但实际不存在的存储器
- 虚拟设备：将一台物理设备虚拟为逻辑上的多台设备，使多个用户在同一时间段内访问同一台设备，即同时共享，用户宏观上感觉是同时的，但实际上是微观交替访问同一台设备的
- 操作系统的虚拟技术科归纳为：
- 时分复用技术：如处理器的分时共享；一个单核的计算机，却可以同时运行多个程序（虚拟处理器技术 —— 时分复用技术）
- 空间复用技术：如虚拟存储器；一个 4 GB 内存的电脑，却可以运行远大于 4 GB 内存的程序（虚拟存储技术 —— 空分复用技术）
4.异步性
异步是指，在多道程序环境下，允许多个程序并发执行，但由于资源有限，进程的执行不是一贯到底的，而是走走停停，以不可预知的速度向前推进，这就是进程的异步性。
操作系统的发展与分类
手工操作阶段
手工操作阶段主要缺点：用户独占全机、人机速度矛盾导致资源利用率极低，手工装卸纸带的时间占了大部分
批处理阶段
批处理阶段又分为单道批处理系统和多道批处理系统
1.单道批处理系统
引入脱机输入/输出技术（用外围机+磁带完成），并由监督程序负责控制作业的输入、输出；通过外围机把程序提前存到磁带里
- 主要优点：缓解了一定程度的人机速度矛盾，资源利用率有所提升
- 主要缺点：内存中仅能有一道程序运行，只有该程序运行结束之后才能调入下一道程序。CPU有大量的时间是在空闲等待I/O完成。资源利用率依然很低。
2.多道批处理系统
每次往内存中读入多道程序，操作系统正式诞生，用于支持多道程序并发运行
- 主要优点：多道程序并发执行，共享计算机资源。资源利用率大幅提升，CPU和其他资源更能保持“忙碌”状态，系统吞吐量增大
- 主要缺点：用户响应时间长，没有人机交互功能（用户提交自己的作业之后就只能等待计算机处理完成，中间不能控制自己的作业执行。eg：无法调试程序/无法在程序运行过程中输入一些参数）
分时操作系统
计算机以时间片为单位轮流为各个用户/作业服务，各个用户可通过终端与计算机进行交互。
- 主要优点：用户请求可以被即时响应，解决了人机交互问题。允许多个用户同时使用一台计算机，并且用户对计算机的操作相互独立，感受不到别人的存在。
- 主要缺点：不能优先处理一些紧急任务。操作系统对各个用户/作业都是完全公平的，循环地为每个用户/作业服务一个时间片，不区分任务的紧急性
实时操作系统
实时操作系统要求计算机系统在接收到外部信号后及时进行处理，并且要在严格的时间内处理完事件，其主要特点是及时性和可靠性。
- 主要优点：能够优先响应一些紧急任务，某些紧急任务不需时间片排队
实时操作系统又分为硬实时系统和软实时系统。
1.硬实时系统
硬实时系统必须在绝对严格的规定时间内完成处理，比如导弹控制系统、自动驾驶系统等。
2.软实时系统
软实时系统能够接受偶尔违反时间的规定，例如订票系统。
其他几种操作系统
操作系统运行环境
操作系统的运行机制
程序时如何运行的？
程序运行的过程其实就是CPU执行一条一条的机器指令的过程
很多人习惯把 Linux、Windows、MacOS 的“小黑框”中使用的命令也称为“令”，其实这是“交互式命令接口”，注意与本节的“指令”区别开。本节中的“指令”指二进制机器指令
内核程序vs应用程序
- 普通程序员写的程序就是“应用程序”
- 微软、苹果有一帮人负责实现操作系统，他们写的是“内核程序”
由很多内核程序组成了“操作系统内核”，或简称“内核（Kernel）”内核是操作系统最重要最核心的部分，也是最接近硬件的部分甚至可以说，一个操作系统只要有内核就够了（eg：Docker—>仅需Linux内核）
操作系统的功能未必都在内核中，如图形化用户界面 GUI
特权指令vs非特权指令
- 应用程序只能使用“非特权指令”，如：加法指令、减法指令等
- 操作系统内核作为 “管理者”，有时会让CPU执行一些*特权指令 ，如：内存清零指令。这些指令影响重大，只允许“管理者”——即操作系统内核来使用*
常见的非特权指令
- 取数指令
- 存数指令
- 读时钟指令
- 加减乘除等算数运算指令
- 寄存器清零指令
- 压栈/弹栈指令(push/pop)
- 跳转指令（转移指令）
- trap指令
常见的特权指令
- 开中断指令
- 关中断指令
- 写时钟指令（置时钟指令）
- 输入/输出指令(1/O指令)
- 写PSW寄存器的指令
内核态vs用户态
CPU 有两种状态，“内核态”和“用户态”
处于内核态时，说明此时正在运行的是内核程序，此时可以执行特权指令
处于用户态时，说明此时正在运行的是应用程序，此时只能执行非特权指令
拓展：CPU 中有一个寄存器叫 程序状态字寄存器（PSW），其中有个二进制位，1表示“内核态”，0表示“用户态”
别名：内核态=核心态=管态；用户态=目态
中断和异常
中断的作用
“中断”是让操作系统内核夺回CPU使用权的唯一途径如果没有“中断”机制，那么一旦应用程序上CPU运行，CPU就会一直运行这个应用程序。
内核态->用户态：执行一条特权指令——修改PSW的标志位为“用户态”，这个动作意味着操作系统将主动让出CPU使用权。
用户态->内核态：由“中断”（陷入）引发，硬件自动完成变态过程，触发中断信号意味着操作系统将强行夺回CPU的使用权。
中断的分类
中断机制的基本原理
不同的中断信号，需要用不同的中断处理程序来处理。当CPU检测到中断信号后，会根据中断信号的类型去查询“中断向量表”，以此来找到相应的中断处理程序在内存中的存放位置。
显然，中断处理程序一定是内核程序，需要运行在“内核态
系统调用
什么是系统调用？
Linux内核中设置了一组用于实现各种系统功能的子程序，称为系统调用。用户可以通过系统调用命令在自己的应用程序中调用它们。
从某种角度来看，系统调用和普通的函数调用非常相似。区别仅仅在于，系统调用由操作系统核心提供，运行于核心态;而普通的函数调用由函数库或用户自己提供，运行于用户态。
系统调用与库函数的区别？
为什么系统调用时必须的？
计算机系统的各种硬件资源是有限的，在现代多任务操作系统上同时运行的多个进程都需要访问这些资源，为了更好的管理这些资源进程是不允许直接操作的，所有对这些资源的访问都必须有操作系统控制。 也就是说操作系统是使用这些资源的唯一入口，而这个入口就是操作系统提供的系统调用（System Call）。
什么功能需要系统调用？
应用程序通过系统调用请求操作系统的服务。而系统中的各种共享资源都由操作系统内核统一掌管，因此凡是与共享资源有关的操作（如存储分配、I/O操作、文件管理等），都必须通过系统调用的方式向操作系统内核提出服务请求，由操作系统内核代为完成。这样可以保证系统的稳定性和安全性，防止用户进行非法操作
系统调用的过程
传递系统调用参数–>执行陷入指令（用户态） –>执行相应的内请求核程序处理系统调用（核心态） –>返回应用程序
【注意】：
- 陷入指令是在用户态执行的，执行陷入指令之后立即引发一个内中断，使CPU进入核心态。
- 发出系统调用请求是在用户态，而对系统调用的相应处理在核心态下进行。
操作系统体系结构
操作系统的内核
操作系统的内核是什么？
内核是操作系统最基本、最核心的部分。实现操作系统内核功能的那些程序就是内核程序。内核是一个操作系统的核心。它负责管理系统的进程、内存、设备驱动程序、文件和网络系统等等，决定着系统的性能和稳定性。是连接应用程序和硬件的桥梁。
内核分为大内核和微内核
大内核
特性思想：功能包括，时钟管理、中断处理、原语(设备驱动、CPU切换)、进程管理、存储器管理、设备管理等功能。所有的系统功能都放在内核里（大内核结构的OS通常也采用了”模块化“的设计思想）
- 优点：
- 高性能，内核各种功能都能直接相互调用
- 缺点：
- 内核代码庞大，结构混乱，难以维护。
- 大内核中某个功能模块出错，就可能导致整个系统崩渍
微内核
特性思想：功能包括，时钟管理、中断处理、原语。只把中断、原语、进程通信等最核心的功能放入内核。进程管理、文件管理、设备管理等功能以用户进程的形式运行在用户态
- 优点：
- 内核功能少，结构清晰，方便维护；
- 内核外的某个功能模块出错不会导致整个系统崩溃
- 缺点：
- 性能低，需要频繁的切换用户态/核心态。
- 用户态下的各功能模块不可以直接相互调用，只能通过内核的”消息传递“来间接通信.
如果使用大内核操作系统，应用程序请求操作系统的服务，那么只需要用户态->内核态，内核态->用户态，总共两次变态
如果使用的是微内核，上述需要6次变态
分层结构
特性思想：内核分多层，每层可单向调用更低一层提供的接口
优点：
- 便于调试和验证，自底向上逐层测试验证
- 易扩充和维护，各层之间调用接口清晰固定
缺点： - 仅可调用相邻低层，难以合理定义各层的边界
- 效率低，不可跨层调用，系统调用执行时间长
模块化
特性思想：将内核划分为多个模块，各模块之间相互协作。
内核=主模块+可加载内核模块
主模块：只负责核心功能，如进程调度、内存管理
可加载内核模块：可以动态加载新模块到内核，而无需重新编译整个内核
外核
操作系统的引导(开机过程/Boot)
什么是操作系统的引导？
操作系统引导（boot）——开机的时候，怎么让操作系统运行起来？
磁盘里面有哪些相关数据？
操作系统引导过程
BIOS(Basic Input/Output System):基本输入输出系统
操作系统引导：
①CPU从一个特定主存地址开始，取指令，执行ROM引导程序（先进行硬件自检，再开机）
②将磁盘/硬盘的第一块——主引导记录MBR 读入内存，执行磁盘引导程序，扫描分区表
③从活动分区（又称主分区，即安装了操作系统的分区–C/D/…盘）读入分区引导记录PBR，执行其中的程序
④从根目录下找到完整的操作系统初始化程序（即 启动管理器）并执行，完成“开机”的一系列动作
拓展
注：完整的操作系统初始化程序（即启动管理器）可在根目录下找到
虚拟机
什么是虚拟机和虚拟机管理程序？
虚拟机–VM
使用虚拟化技术，将一台物理机器虚拟化为多台虚拟机器（Virtual Machine, VM），每个虚拟机器都可以独立运行一个操作系统
虚拟机管理程序–VMM
虚拟机管理程序/虚拟机监控程序/Virtual Machine Monitor/Hypervisor；是创建和运行虚拟机的软件。管理程序允许一台主机通过虚拟共享其资源（例如内存和处理器）来支持多个虚拟机(VM)。由于虚拟机独立于主机硬件，因此虚拟机管理程序可以使用更多系统的可用资源，并提供更大的 IT 移动性。这意味着它们可以轻松地在不同服务器之间移动。
两类管理程序
有两种主要的管理程序类型，称为“类型 1”（或“裸机”）和“类型 2”（或“托管”）。
- 类型 1 也称裸机管理程序，它就像一个轻量级操作系统，直接在主机硬件上运行。
- 类型 2 也称托管管理程序，它是一个软件层，运行在一个操作系统上，就像其他计算机程序一样。
第1类和第2类虚拟机管理程序的区别
虽然第 1 类和第 2 类虚拟机监控器的共同目标是运行和协调虚拟机（VM），但它们之间有一些显著差异。
资源分配
第 1 类虚拟机监控器直接访问底层计算机资源。这些虚拟机监控器可以实施自己的自定义资源分配策略来为虚拟机提供服务。
第 2 类虚拟机监控器与操作系统协商资源分配，这会使流程变慢且效率降低。
易于管理
管理第 1 类虚拟机监控器序及其虚拟机配置需要具备系统管理员级别的知识，因为此类管理相对复杂。
相比之下，可以将第 2 类虚拟机监控器作为应用程序在操作系统上安装和管理。即使是非技术型用户也可以操作这些应用程序。
性能
第 1 类虚拟机监控器可为其虚拟机提供更卓越的性能。这是因为这些虚拟机监控器不需要与操作系统协商资源，也不需要穿过操作系统层。第 1 类虚拟机监控器无需进行任何协商即可提供专用的底层资源。
第 2 类虚拟机监控器只能使用操作系统愿意提供的资源。
隔离
第 1 类虚拟机监控器为每种虚拟环境提供更高程度的隔离。因此，在此类环境中没有共享层，而第 2 类虚拟机监控器则以操作系统作为共享层。这使得在第 1 类虚拟机监控器上运行的虚拟机本质上更加安全。但是，更新和修补虚拟机操作系统就成为一项关键的安全活动。
Practice questions
操作系统基本概念
1 | 易混淆 |
1 | A请求系统服务包括了其他三项 |
1 | - shell、tcsh、zsh、csh、bash都是命令接口 |
1 | 多道程序设计是并发执行，多个进程交错进行，而不是顺序一管到底的 |
1 | 计算机开机，操作系统的安装过程 |
操作系统的发展历程
1 | 多道程序设计技术实现了并发，是资源利用率得到大幅提升 |
1 | 保证实时性，规定时间内处理外部事件，防止意外 |
1 | 分时系统 |
1 | 分时操作系统主要目标是实现人机交互，快速响应用户 |
1 | 分时操作系统，时间片一定时，用户越多，所需要的用户进程越多。时间片一定时，间隔处理的时间就越长，所以响应也就变慢 |
操作系统的运行环境
1 | 输入/输出指令是特权指令，如x86CPU的N指令、OUT指令 |
1 | 系统调用，是为了是系统更稳定安全的运行，防止小白用户、恶意用户进行非法的越权操作。 |
1 | 置时钟指令：将累积的时钟数，重置为0个 |
1 | 命令解释程序-->cmd.exe |
1 | PSW状态寄存器记录当前处理器的状态。中断处理一定会改变，但是还需要回到用户态，所以需要提前保存以回到原来状态 |
1 | 处理中断时，PC的内容由中断隐指令(硬件实现) |
1 | A.出现整数除0 |
1 | 3->2->4->1 |
核心态用户态之间的切换
操作系统体系结构
考点
操作系统的体系结构
- 分层式结构，只能上层调用下层功能，所以可以能逐层调试，便于调试。
- 模块化，可以相互调用，难以调试问题所在。
微内核结构，采用机制与策略分离
通过机制与硬件直接交互而实现的底层的一些具体的小功能
策略则是更高级的管理划分的方法，例如进程调度算法，内存分配算法
机制运行在内核态，策略运行在用户态
操作系统的引导
B.引导程序自检关键部位–检查外存和内存; 识别外设–开机屏幕出现系统画面
D.硬盘不同分区，安装不同操作系统，引导程序MBR开机时会要求用户选择启用那个系统
操作系统引导程序，就是启动管理器，存储在硬盘中
计算机启动过程
1.CPU加电，指向内存中第一条指令（是一条JMP 指令）
2.执行JMP指令跳转到BIOS
3.登记中断信号对应的中断处理服务程序存储的入口地址
4.检查关键硬件，硬盘、内存是否存在
5.最后进行操作系统的引导，内存汇总读入MBR，执行磁盘引导记录…..
虚拟机
第二类虚拟机本质上就是一个应用程序，运行在用户态，不能直接执行特权指令，需要虚拟机管理系统，向操作系统申请
进程与线程
进程与线程
进程的概念、组成和特征
进程的概念
- 程序：是静态的，就是个存放在磁盘里的可执行文件，如：QQ.exe
- 进程：是动态的，是程序的一次执行过程，如：可同时启动多次QQ程序，同一个程序多次执行会对应多个进程
进程的组成
进程（进程实体）由程序段、数据段、PCB 三部分组成。
进程组成–PCB(进程控制块)
当进程被创建时，操作系统会为该进程分配一个唯一的、不重复的“身份证号”—— PID（Process ID，进程ID）。PCB是进程存在的唯一标志，当进程被创建时，操作系统为其创建PCB，当进程结束时，会回收其PCB。
PCB(进程控制块)是一个数据结构，记录了如下的信息：
- 操作系统要记录PID、进程所属用户ID（UID，基本的进程描述信息，可以
让操作系统区分各个进程。 - 还要记录给进程分配了哪些资源（如：分配了多少内存、正在使用哪些I/O设备、正在使用哪些文件，可用于实现操作系统对资源的管理。
- 还要记录进程的运行情况（如：CPU使用时间、磁盘使用情况、网络流量使用情况等）可用于实现操作系统对进程的控制、调度。
进程的组成–程序段、数据段
- 程序段，程序代码即存放在此
- 数据段，程序运行时使用、产生的运算数据。如全局变量、局部变量、宏定义的常量就存放在数据段内
进程的特征
动态性试进程最基本特征
进程的状态与转换
! 当一个进程被阻塞时,它只是释放了对CPU的占用,进入了等待状态,而不会自动释放它已获得的其他资源(如内存、文件等)。
进程的组织
链接方式
按照进程状态，将PCB分为多个队列；操作系统维持有指向各个队列的指针
索引方式
进程的控制
什么是进程控制？
进程控制的主要功能是对系统中的所有进程实施有效的管理，它具有创建新进程、撤销已有进程、实现进程状态转换等功能。
简化理解：反正进程控制就是要实现进程状态转换
如何实现进程控制？
进程控制必须是一气呵成的
如果不能“一气呵成”，就有可能导致操作系统中的某些关键数据结构信息不统一的情况，这会影响操作系统进行别的管理工作
如何实现进程控制一气呵成，不受中断信号的影响呢？
原语
原语是一种特殊的程序，它的执行具有原子性。也就是说，这段程序的运行必须一气呵成，不可中断。原语通常是由底层硬件直接实现的。原语(Primitive)指的是操作系统或编程语言提供的最基本的操作单元。原语不能再细分拆分,必须由硬件直接执行。
原语的原子性
原语的执行具有原子性，即执行过程只能一气呵成，期间不允许被中断。可以用 “关中断指令”和“开中断指令”这两个特权指令实现原子性。
进程控制相关原语
进程的创建–创建原语
操作系统创建一个进程时使用的原语
进程的终止–撤销原语
进程的阻塞和唤醒
阻塞原语和唤醒原语必须成对使用，被阻塞了必须要被唤醒
进程的切换–切换原语
进程运行环境，就是进程运行过程，执行指令产生的各种数据暂时存放在寄存器中(PC 程序计数器、通用寄存器等存放着一些该进程运行的数据)，但是当时间片用完，或者其他原因，需要让下一个进程运行，那么寄存器里面的内容就会被覆盖，当进程重新得到时间片时，就无法从中断处继续。所以就需要将运行环境信息存入PCB
进程通信
什么是进程通信？
进程间通信（Inter-Process Communication， IPC）是指两个进程之间产生数据交互，类似于，我用微博将消息分享到微信的过程
为什么进程通信需要操作系统支持？
各个进程被分配了，相互独立的地址空间，但是这些进程只能访问自己的地址空间，无法访问别的进程地址空间，这样是为了保证安全
进程通信三种方式
1.共享存储区
- 使得多个进程可以可以直接读写同一块内存空间，是最快的可用IPC形式。是针对其他通信机制运行效率较低而设计的。
- 为了在多个进程间交换信息，内核专门留出了一块内存区，可以由需要访问的进程将其映射到自己的私有地址空间。进程就可以直接读写这一块内存而不需要进行数据的拷贝，从而大大提高效率。
- 由于多个进程共享一段内存，因此需要依靠某种同步机制（如信号量）来达到进程间的同步及互斥。
两类共享存储方式：基于数据结构的共享、基于存储区的共享
2.消息传递
进程间的数据交换以格式化的消息（Message）为单位。进程通过操作系统提供的“发送消息/接收消息”两个原语进行数据交换。并且数据都是存放在操作系统的内核空间内存中
1.直接通信方式
消息发送进程要指明接收进程的ID，只能一对一，消息存放在操作系统内核空间中
- 发送原语：指明接收方进程ID
- 接收原语：指明发送方进程ID
2.间接通信方式
通过“信箱”间接地通信。因此又称“信箱通信方式，能够多对多”，消息存放在信箱中(信箱位于操作系统内核空间)
- 发送原语指明要发往的信箱
- 接收原语指明从哪个信箱接收
3.管道通信
- 管道只能采用半双工通信，某一时间段内只能实现单向的传输。如果要实现双向同时通信，则需要设置两个管道。
- 各进程要互斥地访问管道（由操作系统实现）
- 当管道写满时，写进程将阻塞，直到读进程将管道中的数据取走，即可唤醒写进程。
- 当管道读空时，读进程将阻塞，直到写进程往管道中写入数据，即可唤醒读进程。
- 管道中的数据一旦被读出，就彻底消失。因此，当多个进程读同一个管道时，可能会错乱。对此，通常有两种解决方案：①一个管道允许多个写进程，一个读进程（2014年408真题高教社官方答案）；②允许有多个写进程，多个读进程，但系统会让各个读进程轮流从管道中读数据（Linux 的方案）。
线程的概念与特点
为什么引入线程？
- 可以把线程理解为“轻量级进程”。
- 线程是一个基本的CPU执行单元，也是程序执行流的最小单位。
- 引入线程之后，不仅是进程之间可以并发，进程内的各线程之间也可以并发，从而进一步提升了系统的并发度，使得一个进程内也可以并发处理各种任务（如QQ视频、文字聊天、传文件）
- 引入线程后，进程只作为除CPU之外的系统资源的分配单元（如打印机、内存地址空间等都是分配给进程的）。线程则作为处理机的分配单元。
有的进程可能需要“同时”做很多事，而传统的进程只能串行地执行一系列程序。为此，引入了“线程”，来增加并发度。
引入线程后的变化
【注：系统开销减小，是因为线程并发减少了进程之间的切换，也就减少了进程运行环境的切换，所以开销减小】
线程的属性
线程的实现方式
用户级线程
早期的操作系统（如：早期Unix）只支持进程，不支持线程。当时的“线程”是由线程库实现的。这种线程实现方式被称为“用户级线程”。
- 用户级线程由应用程序通过线程库实现，所有的线程管理工作都由应用程序负责（包括线程切换）。
- 用户级线程中，线程切换可以在用户态下即可完成，无需操作系统干预。
- 在用户看来，是有多个线程。但是在操作系统内核看来，并意识不到线程的存在。“用户级线程”就是“从用户视角看能看到的线程”
- 处理机的分配单元是进程，所以时间片是按照进程分配，其中一个线程阻塞，整个进程就阻塞(该进程下的其他进程也相应无法执行)，所以这种线程并发度不高。
- 优缺点
- 优点：用户级线程的切换在用户空间即可完成，不需要切换到核心态，线程管理的系统开销小，效率高
- 缺点：当一个用户级线程被阻塞后，整个进程都会被阻塞，并发度不高。多个线程不可在多核处理机上并行运行。
内核级线程
- 内核级线程的管理工作由操作系统内核完成。
- 线程调度、切换等工作都由内核负责，因此内核级线程的切换必然需要在核心态下才能完成。
- 操作系统会为每个内核级线程建立相应的TCB（Thread Control Block，线程控制块），通过TCB对线程进行管理。“内核级线程”就是“从操作系统内核视角看能看到的线程”。
- 处理机的分配单元是内核级线程，时间片按照线程分配，一个内核线程阻塞，该进程下其他内核线程任然可以获得时间片，执行下去，并发度高。
- 优缺点
- 优点：当一个线程被阻塞后，别的线程还可以继续执行，并发能力强。多线程可在多核处理机上并行执行。
- 缺点：一个用户进程会占用多个内核级线程，线程切换由操作系统内核完成，需要切换到核心态，因此线程管理的成本高，开销大。
在支持内核级线程的系统中，根据用户级线程和内核级线程的映射关系，可以划分为几种多线程模型
一对一模型
一对一模型：一个用户级线程映射到一个内核级线程。每个用户进程有与用户级线程同数量的内核级线程。
优点：当一个线程被阻塞后，别的线程还可以继续执行，并发能力强。多线程可在多核处理机上并行执行。
缺点：一个用户进程会占用多个内核级线程，线程切换由操作系统内核完成，需要切换到核心态，因此线程管理的成本高，开销大
多对一模型
多对一模型：多个用户级线程映射到一个内核级线程。且一个进程只被分配一个内核级线程。
优点：用户级线程的切换在用户空间即可完成，不需要切换到核心态，线程管理的系统开销小，效率高。
缺点：当一个用户级线程被阻塞后，整个进程都会被阻塞，并发度不高。多个线程不可在多核处理机上并行运行。
操作系统只“看得见”内核级线程，因此只有内核级线程才是处理机分配的单位。
多对多模型
多对多模型：n 用户及线程映射到 m 个内核级线程（n >= m）。每个用户进程对应 m 个内核级线程。
克服了多对一模型并发度不高的缺点（一个阻塞全体阻塞），又克服了一对一模型中一个用户进程占用太多内核级线程，开销太大的缺点。
线程的状态与转换
线程状态转换
与进程的状态转换差不多
线程的组成
线程控制块TCB，类似于进程控制块
处理机调度
调度的概念、层次
调度的基本概念
当有一堆任务要处理，但由于资源有限，这些事情没法同时处理。这就需要确定某种规则来决定处理这些任务的顺序，这就是“调度”研究的问题。
调度的三个层次
- 高级调度（作业调度）
作业：一个具体的任务。用户向系统提交一个作业 ≈ 用户让操作系统启动一个程序（来处理一个具体的任务）
<创建进程>
按一定的原则从外存上处于后备队列的作业中挑选一个（或多个）作业，给他们分配内存等必要资源，并建立相应的进程(建立PCB),以使它（们）获得竟争处理机的权利。高级调度是辅存（外存）与内存之间的调度。每个作业只调入一次，调出一次。作业调入时会建立相应的PCB,作业调出时才撤销PCB。高级调度主要是指调入的问题，因为只有调入的时机需要操作系统来确定，但调出的时机必然是作业运行结束才调出。
- 中级调度（内存调度）
<将已有进程，调出/入内存，缓解内存不足>
为了使内存中的内存不至于太多，有时需要把某些进程从内存中调到外存，暂时调到外存等待的进程状态为挂起状态。被挂起的进程PCB会被组织成挂起队列。在内存使用情况紧张时，将一些暂时不能运行的进程从内存中对换到外存中等待。当内存有足够的空闲空间时，再将合适的进程重新换入内存。一个进程可能会被多次调出、调入内存，因此中级调度发生的频率要比高级调度更高。
- 低级调度（进程调度/处理机调度）
<给进程分配处理机，时间片>
主要任务是按照某种方法和策略从就绪队列中选取一个进程，将处理机分配给它。进程调度是操作系统中最基本的一种调度，在一般的操作系统中都必须配置进程调度。进程调度的频率很高，一般几十毫秒一次。
回顾
调度算法的评价指标
CPU利用率
系统吞吐量
周转时间
周转时间，是指从作业被提交给系统开始，到作业完成为止的这段时间间隔。
它包括四个部分：作业在外存后备队列上等待作业调度（高级调度）的时间、进程在就绪队列上等待进程调度（低级调度）的时间、进程在CPU上执行的时间、进程等待I/O操作完成的时间。后三项在一个作业的整个处理过程中，可能发生多次。
只有作业真正提交/到达，进入外存后备队列开始，才算进程开始周转
1 | 对于周转时间相同的两个作业，实际运行时 |
eg
等待时间
计算机的用户希望自己的作业尽可能少的等待处理机。等待时间，指进程/作业处于等待处理机状态时间之和，等待时间越长，用户满意度越低。
- 对于进程来说，等待时间就是指进程建立后等待被服务的时间之和，在等待I/O完成的期间其实进程也是在被服务的(被CPU服务)，所以不计入等待时间。
- 对于作业来说，不仅要考虑建立进程后的等待时间，还要加上作业在外存后备队列中等待的时间。
对于等待I/O完成的进程,操作系统确实会视其为在运行状态,因为这只是一种阻塞的等待,进程仍在内核态运行。就进程而言,它发出了I/O请求后,并不知道具体的等待时间,只能被动等待通知,所以从进程角度来看,它仍是运行状态。
响应时间
对于计算机用户来说，会希望自己的提交的请求（比如通过键盘输入了一个调试命令）尽早地开始被系统服务、回应。响应时间，指从用户提交请求到首次产生响应所用的时间
进程调度(低级调度)
进程调度的时机
进程调度（低级调度），就是按照某种算法从就绪队列中选择一个进程为其分配处理机。
一、需要进程调度与切换的情况
- 当前运行的进程主动放弃处理机：
- 进程正常终止
- 运行过程中发生异常而终止
- 进程主动请求阻塞（如 等待I/O）
- 当前运行的进程被动放弃处理机：
- 分给进程的时间片用完
- 有更紧急的事需要处理（如 I/O中断）
- 有更高优先级的进程进入就绪队列
二、不能进行进程调度与切换的情况
- 在处理中断的过程中。中断处理过程复杂，与硬件密切相关，很难做到在中断处理过程中进行进程切换。
- 进程在操作系统内核程序临界区中。
- 在原子操作过程中（原语）。原子操作不可中断，要一气呵成（如之前讲过的修改PCB中进程状态标志，并把PCB放到相应队列）
扩展
临界资源：一个时间段内只允许一个进程使用的资源。各进程需要互斥地访问临界资源。
临界区：访问临界资源的那段代码。
内核程序临界区：一般是用来访问某种内核数据结构的，比如进程的就绪队列(由各就绪进程的PCB组成）
进程在操作系统内核程序临界区中不能进行调度与切换；
内核程序临界区访问的临界资源如果不尽快释放的话，极有可能影响到操作系统内核的其他管理工作。因此在访问内核程序临界区期间不能进行调度与切换
进程处于临界区时能进行处理机调度
普通临界区访问的临界资源不会直接影响操作系统内核的管理工作。因此在访问普通临界区时可以进行调度与切换。
进程调度的方式
进程调度与切换
小结
调度器和闲逛进程
调度器/调度程序
调度程序实现的是就绪态和运行态之间的切换，而不包括与阻塞态转换。
什么事件会触发”调度程序“？
1.创建新进程：新的进程计入就绪队列，并需调度程序，决定是否进入运行态
2. 进程退出：进程结束，需要调度程序，决定哪个就绪进程运行
3.运行进程阻塞：阻塞，需要进程顶上
4.非抢占式调度策略：只有运行阻塞，或完后退出才能发生调度
5. 抢占式调度策略：每个时钟周期(时钟中断)，进程时间片重新被争夺，需要调度就绪->运行
1 | 调度程序的调度对象是进程还是线程，取决于操作系统是否支持内核级线程 |
闲逛进程
仅仅作为备胎，当没有进程能够运行时，就运行闲逛进程
调度算法
批处理系统调度算法
先来先服务
Fisrt Come First Serve
例子
短作业优先
Short Job First
非抢占式-例子
严格来说，用于进程调度应该称为 短进程优先调度算法（ SPF ）
抢占式-例子
严格来说，抢占式的短作业优先算法又称“最短剩余时间优先算法（SRTN）“
注意区分
- 如果题目中未特别说明，所提到的“短作业/进程优先算法”默认是非抢占式的
- 很多书上都会说“SJF 调度算法的平均等待时间、平均周转时间最少”严格来说，这个表述是错误的，不严谨的。之前的例子表明，最短剩余时间优先算法得到的平均等待时间、平均周转时间还要更少应该加上一个条件“在所有进程同时可运行时，采用SJF调度算法的平均等待时间、平均周转时间最少”；或者说“在所有进程都几乎同时到达时，采用SJF调度算法的平均等待时间、平均周转时间最少”；如果不加上述前提条件，则应该说“抢占式的短作业/进程优先调度算法（最短剩余时间优先, SRNT算法）的平均等待时间、平均周转时间最少”
- 虽然严格来说，SJF的平均等待时间、平均周转时间并不一定最少，但相比于其他算法（如 FCFS），SJF依然可以获得较少的平均等待时间、平均周转时间
- 如果选择题中遇到“SJF 算法的平均等待时间、平均周转时间最少”的选项，那最好判断其他选项是不是有很明显的错误，如果没有更合适的选项，那也应该选择该选项
高响应比优先
High Response High Ratio Next
例子
小结
这几种算法主要关心对用户的公平性、平均周转时间、平均等待时间等评价系统整体性能的指标，但是不关心“响应时间”，也并不区分任务的紧急程度，因此对于用户来说，交互性很糟糕。因此这三种算法一般适合用于早期的批处理系统，当然，FCFS算法也常结合其他的算法使用，在现在也扮演着很重要的角色。
交互式系统的调度算法
时间片轮转算法
RR, Round-Robin
例子
特点：常用于分时操作系统，更注重“响应时间”，因而此处不计算周转时间；
0时刻（P1(5)）:0时刻只有P1到达就绪队列，让P1上处理机运行一个时间片。
2时刻（P2(4) ->P1(3)）->2时刻 P2到达就绪队列，P1运行完一个时间片，被剥夺处理机，重新放到队尾。此时P2排在队头，因此让P2上处理机。（注意： 2时刻，P1下处理机，同一时刻新进程P2到达，如果在题目中遇到这种情况， 默认 新到达的进程先进入就绪队列）。
4时刻（P1(3) -> P3(1) -> P2(2)）:4时刻，P3到达，先插到就绪队尾，紧接着，P2下处理机也插到队尾。
5时刻（P3(1) -> P2(2) -> P4(6)）:5时刻，P4到达插到就绪队尾（注意：由于P1的时间片还没用完，因此暂时不调度。另外，此时P1处于运行态，并不在就绪队列中）。
6时刻（P3(1) -> P2(2) -> P4(6) -> P1(1)）：6时刻，P1时间片用完，下处理机，重新放回就绪队尾，发生调度
7时刻（P2(2) -> P4(6) -> P1(1)）：虽然P3的时间片没用完，但是由于P3只需运行1个单位的时间，运行完了会主动放弃处理机，因此也会发生调度。队头进程P2上处理机。
9时刻（P4(6) -> P1(1)）：进程P2时间片用完，并刚好运行完，发生调度，P4上处理机。
11时刻（P1(1) -> P4(4) ）：P4时间片用完，重新回到就绪队列。P1上处理机。
12时刻（P4(4) ）：P1运行完，主动放弃处理机，此时就绪队列中只剩P4，P4上处理机。
14时刻（）：就绪队列为空，因此让P4接着运行一个时间片。
16时刻：所有进程运行结束。
1 | ！注意： |
优先级调度算法
非抢占式–例子
特点：用优先级区分紧急程度，适用于实时操作系统
抢占式–例子
特点：用优先级区分紧急程度，适用于实时操作系统
1 | 就绪队列未必只有一个，可以按照不同优先级来组织。另外，也可以把优先级 |
多级反馈队列算法
例子
小结
比起早期的批处理操作系统来说，由于计算机造价大幅降低，因此之后出现的交互式操作系统（包括分时操作系统、实时操作系统等）更注重系统的响应时间、公平性、平衡性等指标。而这几种算法恰好也能较好地满足交互式系统的需求。因此这三种算法适合用于交互式系统。（比如UNIX使用的就是多级反馈队列调度算法）
同步与互斥
同步与互斥的基本概念
进程互斥
进程互斥指当一个进程访问某临界资源时，另一个想要访问该临界资源的进程必须等待。当前访问临界资源的进程访问结束，释放该资源之后，另一个进程才能去访问临界资源。
1 | 注意： |
进程同步
是指散步在不同进程之间的若干程序片断，它们的运行必须严格按照规定的 某种先后次序来运行，这种先后次序依赖于要完成的特定的任务。显然，同步是一种更为复杂的互斥，而互斥是一种特殊的同步。也就是说互斥是两个线程之间不可以同时运行，他们会相互排斥，必须等待一个线程运行完毕，另一个才能运行，而同步也是不能同时运行，但他是必须要安照某种次序来运行相应的线程（也是一种互斥）！
为什么需要进程同步
进程具有异步性的特征。异步性是指，各并发执行的进程以各自独立的、不可预知的速度向前推进。操作系统要提供“进程同步机制”来解决异步问题。
软件实现与硬件实现的概念
硬件实现是直接在硬件电路上实现功能,软件实现是通过软件代码进行模拟或者抽象来间接实现功能。
硬件实现的特点是:
- 直接在数字逻辑电路或者模拟电路上对功能进行设计,实现速度很快。
- 不需要指令的翻译和调度,执行效率高。
- 硬件电路功能一旦实现就固化了,不太容易修改。
软件实现的特点是:
- 使用编程语言编写代码,通过代码逻辑来模拟实现功能。
- 需要将高级语言翻译成机器指令,存在一定的执行开销。
- 可以通过修改代码来调整功能实现,更加灵活。
- 可以通过软件在不同硬件上运行,更加通用。
进程互斥的软件实现方法
单标志法
1 | 算法思想：两个进程在 访问完临界区后 会把使用临界区的权限转交给另一个进程。也就是说每个进程进入临界区的权限只能被另一个进程赋予 |
双标志先检查法
1 | 算法思想：设置一个布尔型数组 flag[]，数组中各个元素用来标记各进程想进入临界区的意愿，比如“flag[0] = ture”意味着 0 号进程 P0 现在想要进入临界区。每个进程在进入临界区之前先检查当前有没有别的进程想进入临界区，如果没有，则把自身对应的标志 flag[i] 设为 true，之后开始访问临界区。 |
双标志后检查法
1 | 算法思想：双标志先检查法的改版。前一个算法的问题是先“检查”后“上锁”，但是这两个操作又无法一气呵成，因此导致了两个进程同时进入临界区的问题。因此，人们又想到先“上锁”后“检查”的方法，来避免上述问题 |
Peterson算法
1 | 算法思想：结合双标志法、单标志法的思想。如果双方都争着想进入临界区，那可以让进程尝试“孔融让梨”（谦让）。做一个有礼貌的进程。 |
进程互斥的硬件实现方法
中断屏蔽方法
利用“开/关中断指令”实现（与原语的实现思想相同，即在某进程开始访问临界区到结束访问为止都不允许被中断，也就不能发生进程切换，因此也不可能发生两个同时访问临界区的情况）
优点：简单、高效
缺点：不适用于多处理机；只适用于操作系统内核进程，不适用于用户进程（因为开/关中断指令只能运行在内核态，这组指令如果能让用户随意使用会很危险
TeatAndSet指令
注意：TestAndSet指令是通过硬件实现的，这里将指令用代码表示，是为了描述逻辑，硬件实现的内容，本质上并不是用代码实现的
简称TS指令，也有地方称为TestAndSetLock指令，或TSL指令。
TSL指令是用硬件实现的，执行的过程不允许被中断，只能一气呵成。以下是用c语言描述的逻辑
若刚开始lock 是 false，则TSL返回的old值为 false，while循环条件不满足，直接跳过循环，进入临界区。若刚开始lock 是true，则执行TLS后old返回的值为true，while循环条件满足，会一直循环，直到当前访问临界区的进程在退出区进行“解锁”。
相比软件实现方法，TSL指令把“上锁”和“检查”操作用硬件的方式变成了一气呵成的原子操作。
优点：实现简单，无需像软件实现方法那样严格检查是否会有逻辑漏洞;适用于多处理机环境(当一个进程陷入等待，等待任然占用着处理机，如果是单核处理机，那么其他进程就一直没办法得到处理机，无法执行别的进程)
缺点：不满足“让权等待”原则，暂时无法进入临界区的进程会占用CPU并循环执行TSL指令，从而导致“忙等”。
Swap指令
有的地方也叫 Exchange 指令，或简称 XCHG 指令。Swap 指令是用硬件实现的，执行的过程不允许被中断，只能一气呵成。以下是用C语言描述的逻辑。
逻辑上来看 Swap 和 TSL 并无太大区别，都是先记录下此时临界区是否已经被上锁（记录在 old 变量上），再将上锁标记 lock 设置为 true，最后检查 old，如果 old 为 false 则说明之前没有别的进程对临界区上锁，则可跳出循环，进入临界区。
优点：实现简单，无需像软件实现方法那样严格检查是否会有逻辑漏洞；适用于多处理机环境
缺点：不满足“让权等待”原则，暂时无法进入临界区的进程会占用CPU并循环执行TSL指令，从而导致“忙等”。
互斥锁
特性：
• 需忙等，进程时间片用完才下处理机，违反“让权等待”
• 优点：等待期间不用切换进程上下文，多处理器系统中，若上锁的时间短，则 等待代价很低
• 常用于多处理器系统，一个核忙等，其他核照常工作，并快速释放临界区
• 不太适用于单处理机系统，忙等的过程中不可能解锁
信号量机制
为什么需要信号量机制？
进程互斥的四种软件实现方式（单标志法、双标志先检查、双标志后检查、Peterson算法）进程互斥的三种硬件实现方式（中断屏蔽方法、TS/TSL指令、Swap/XCHG指令）
- 在双标志先检查法中，进入区的“检查”、“上锁” 操作无法一气呵成，从而导致了两个进程有可能同时进入临界区的问题；
- 所有的解决方案都无法实现“让权等待”
所以，1965年，荷兰学者Dijkstra提出了一种卓有成效的实现进程互斥、同步的方法——信号量机制
信号量机制的实现
信号量其实就是一个变量 ，可以用一个信号量来表示系统中某种资源的数量，比如：系统中只有一台打印机，就可以设置一个初值为 1 的信号量。
原语是一种特殊的程序段，其执行只能一气呵成，不可被中断。原语是由关中断/开中断指令实现的。软件解决方案的主要问题是由“进入区的各种操作无法一气呵成”，因此如果能把进入区、退出区的操作都用“原语”实现，使这些操作能“一气呵成”就能避免问题。
一对原语：wait(S) 原语和 signal(S) 原语，可以把原语理解为我们自己写的函数，函数名分别为 wait和 signal，括号里的信号量 S 其实就是函数调用时传入的一个参数。wait、signal 原语常简称为 P、V操作（来自荷兰语 proberen 和
verhogen）。因此，做题的时候常把wait(S)、signal(S) 两个操作分别写为
P(S)、V(S)
整数型信号量
- 整数型信号量S是一个int 整数，直接记录资源数量
- 检查和上锁一气呵成，避免并发、异步导致的临界资源同时访问的问题
- 不满足“让权等待”，陷入自旋实际上还是占用着处理机
1
2
3
4
5
6
7
8
9
10int S = 1; // 整型信号量S，表示某种资源的数量
void wait(int S) { // wait原语
while(S <= 0); // 资源数不足，循环等待
S = S - 1; // 占用资源
}
void signal(int S) { // signal原语
S = S + 1; // 释放资源
}
记录型信号量
- 记录型信号量S是一个结构体，里面包含着，资源数量和等待队列的信息
- 满足让权等待，资源不足时，直接bloack进入阻塞(并非循环)，此时不占用处理机。它只是释放了对CPU的占用,进入了等待状态,而不会自动释放它已获得的其他资源(如内存、文件等)。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18typedef struct {
int value; // 某种资源的数量
struct process *L; // 等待队列
} semaphore;
void wait(semaphore S) { // wait原语
S.value--;
if(S.value < 0) {
bloack(S.L); // 阻塞进程
}
}
void signal(semaphore S) { // signal原语
S.value++;
if(S.value <= 0) {
wakeup(S.L); // 唤醒进程
}
}
信号量机制实现进程互斥、同步、前驱关系
- 默认使用记录型信号量
信号量实现进程互斥
- 分析并发进程的关键活动，划定临界区（如：对临界资源打印机的访问就应放在临界区）
- 设置互斥信号量 mutex，初值为 1
- 在进入区 P(mutex)——申请资源
- 在退出区 V(mutex)——释放资源
【对不同的临界资源需要设置不同的互斥信号量。P、V操作必须成对出现。缺少P(mutex) 就不能保证临界资源的互斥访问。缺少 V(mutex) 会导致资源永不被释放，等待进程永不被唤醒。】
1 | 初始化semaphore mutex =1 是伪代码，实际上是对结构体内的value赋值为1 |
信号量实现进程同步
- 分析什么地方需要实现“同步关系”，即必须保证“一前一后”执行的两个操作（或两句代码）
- 设置同步信号量 S, 初始为 0
- 在“前操作”之后执行 V(S)
- 在“后操作”之前执行 P(S)
1 | 理解：信号量S代表“某种资源”，刚开始是没有这种资源的。P2需要使用这种资源， |
信号量机制实现前驱关系
管程
什么是管程？
概念
管程(Monitor)从概念上更接近一个类,而不是一个函数。
管程有以下特点:
- 管程包含了数据字段(属性)和过程(方法)。这与面向对象编程中的类非常类似。
- 管程的数据字段和过程是绑定在一起的,对管程的访问需要通过其公开的过程,不能直接访问其内部数据,这提供了封装性。类也有相同的封装特性。
- 管程有其独立的实例,每个管程实例包含独立的私有数据,这也是类的一个特征。
- 管程的过程(方法)共享管程的私有数据,不同实例的数据相互隔离,这符合类的设计。
而如果将管程看作一个函数,则不太恰当:
- 函数通常没有内部状态(属性),只有输入输出参数。但管程有自己的内部状态。
- 函数不具备多实例的特性。管程可以创建多个实例。
- 函数的调用不具备互斥和同步特性。管程通过互斥锁和条件变量可实现复杂的同步。
所以,从面向对象设计的角度,管程更接近一个类,它提供了封装性、数据隐藏、实例化等关键特征。
当然,管程也有与类不同的地方,它直接内置了同步和互斥的语义。但是从软件设计抽象的层面,管程是对一个同步对象的封装,可以看作是一个同步类。
特征
管程的基本特征：
- 局部于管程的数据只能被局部于管程的过程所访问；
- 一个进程只有通过调用管程内的过程才能进入管程访问共享数据；
- 每次仅允许一个进程在管程内执行某个内部过程。
为什么要引入管程？
主要是因为，编写程序时，每一个进程与进程之间P、V操作都要单独编写考虑，太过麻烦，且容易出错，所以引入管程，将内部逻辑封装，直接调用就可以逻辑自洽
管程解决生产者消费者问题
生产者-消费者问题
1.问题描述
2.问题分析
- 隐含两对同步
生产者、消费者共享一个初始为空、大小为n的缓冲区。
只有缓冲区没满时，生产者才能把产品放入缓冲区，否则必须等待。
只有缓冲区不空时，消费者才能从中取出产品，否则必须等待。 - 互斥性
缓冲区是临界资源，各进程必须互斥地访问。
3.如何实现
1 | mutex是互斥信号量，用于实现互斥访问，初始=1 |
4.能否改变相邻 P 、 V 操作的顺序？
P不能互换顺序
若此时缓冲区内已经放满产品，则 empty=0，full=n。
则生产者进程执行① 使mutex变为0，再执行②，由于已没有空闲缓冲区，因此生产者被阻塞。由于生产者阻塞，因此切换回消费者进程。消费者进程执行③，由于mutex为0，即生产者还没释放对临界资源的“锁”，因此消费者也被阻塞。这就造成了生产者等待消费者释放空闲缓冲区，而消费者又等待生产者释放临界区的情况，生产者和消费者循环等待被对方唤醒，出现“死锁”。因此，实现互斥的P操作一定要在实现同步的P操作之后
V可以互换顺序
V操作不会导致进程阻塞，因此两个V操作顺序可以交换。
多生产者-多消费者问题
”多“，只的是一个仓库，“多类产品和多类消费者“，并不是指“多个”。与上一个问题的区别，在于，产品类别有多个类，消费者也有多种
1.问题描述
爸爸专向盘子中放苹果，妈妈专向盘子中放橘子。
儿子专等着吃盘子中的橘子，女儿专等着吃盘子中的苹果。
只有盘子空时，爸爸或妈妈才可向盘子中放一个水果。仅当盘子中有自己需要的水果时，儿子或女儿可以从盘子中取出水果。
2.问题分析
互斥关系：（mutex = 1）
对缓冲区（盘子）的访问要互斥地进行
同步关系（一前一后）：
- 父亲将苹果放入盘子后，女儿才能取苹果
- 母亲将橘子放入盘子后，儿子才能取橘子
- 只有盘子为空时，父亲或母亲才能放入水果
3.如何实现
1 | 本题中的缓冲区大小为1，在任何时刻，apple、orange、plate 三个同步信号量中最多只有一个是1。因此在任何时刻，最多只有一个进程的P操作不会被阻塞，并顺利地进入临界区…所以即使不设置专门的互斥变量mutex，也不会出现多个进程同时访问盘子的现象 |
4.小结
解决“多生产者-多消费者问题”的关键在于理清复杂的同步关系。
在分析同步问题（一前一后问题）的时候不能从单个进程行为的角度来分析，要把“一前一后”发生的事看做是两种“事件”的前后关系。
比如，如果从单个进程行为的角度来考虑的话，我们会有以下结论：
- 如果盘子里装有苹果，那么一定要女儿取走苹果后父亲或母亲才能再放入水果
- 如果盘子里装有橘子，那么一定要儿子取走橘子后父亲或母亲才能再放入水果
这么看是否就意味着要设置四个同步信号量分别实现这四个“一前一后”的关系了？
正确的分析方法应该从“事件”的角度来考虑，我们可以把上述四对“进程行为的前后关系”抽象为一对“事件的前后关系”
盘子变空事件->放入水果事件。“盘子变空事件”既可由儿子引发，也可由女儿引发；“放水果事件”既可能是父亲执行，也可能是母亲执行。这样的话，就可以用一个同步信号量解决问题了
吸烟者问题
1.问题描述
假设一个系统有三个抽烟者进程和一个供应者进程。每个抽烟者不停地卷烟并抽掉它，但是要卷起并抽掉一支烟，抽烟者需要有三种材料：烟草、纸和胶水。三个抽烟者中，第一个拥有烟草、第二个拥有纸、第三个拥有胶水。
供应者进程无限地提供三种材料，供应者每次将两种材料放桌子上，拥有剩下那种材料的抽烟者卷一根烟并抽掉它，并给供应者进程一个信号告诉完成了，供
应者就会放另外两种材料再桌上，这个过程一直重复（让三个抽烟者轮流地抽烟
2.问题分析
本质上这题也属于“生产者-消费者”问题，更详细的说应该是“可生产多种产品的单生产者-多消费者”
3.如何实现
读者-写者问题
1.问题描述
有读者和写者两组并发进程，共享一个文件，当两个或两个以上的读进程同时访问共享数据时不会产生副作用，但若某个写进程和其他进程（读进程或写进程）同时访问共享数据时则可能导致数据不一致的错误。
因此要求：①允许多个读者可以同时对文件执行读操作；②只允许一个写者
往文件中写信息；③任一写者在完成写操作之前不允许其他读者或写者工作；④写者执行写操作前，应让已有的读者和写者全部退出。
2.问题分析
两类进程：写进程、读进程
互斥关系：写进程—写进程、写进程—读进程。读进程与读进程不存在互斥问题。
3.如何实现
其核心思想在于设置了一个计数器 count 用来记录当前正在访问共享文件的读进程数。我们可以用count 的值来判断当前进入的进程是否是第一个/最后一个读进程，从而做出不同的处理。另外，对 count 变量的检查和赋值不能一气呵成导致了一些错误，如果需要实现“一气呵成”，自然应该想到用互斥信号量。最后，还要认真体会我们是如何解决“写进程饥饿”问题的。
1 | 若两个读进程并发执行，则 count=0时两个进程也许都能满足 if 条件，都会执行 |
1 | 改进： |
哲学家进餐问题
1.问题描述
一张圆桌上坐着5名哲学家，每两个哲学家之间的桌上摆一根筷子，桌子的中间是一碗米饭。哲学家们倾注毕生的精力用于思考和进餐，哲学家在思考时，并不影响他人。只有当哲学家饥饿时，才试图拿起左、右两根筷子（一根一根地拿起）。如果筷子已在他人手上，则需等待。饥饿的哲学家只有同时拿起两根筷子才可以开始进餐，当进餐完毕后，放下筷子继续思考。
2.问题分析
- 关系分析。系统中有5个哲学家进程，5位哲学家与左右邻居对其中间筷子的访问是互斥关系。
- 整理思路。这个问题中只有互斥关系，但与之前遇到的问题不同的事，每个哲学家进程需要同时持有两个临界资源才能开始吃饭。如何避免临界资源分配不当造成的死锁现象，是哲学家问题的精髓。
- 信号量设置。定义互斥信号量数组chopstick[5]={1,1,1,1,1} 用于实现对5个筷子的互斥访问。并对哲学家按0~4编号，哲学家 i 左边的筷子编号为 i，右边的筷子编号为 (i+1)%5。
3.如何实现
5.小结
哲学家进餐问题的关键在于解决进程死锁。
这些进程之间只存在互斥关系，但是与之前接触到的互斥关系不同的是，每个进程都需要同时持有两个临界资源，因此就有“死锁”问题的隐患。
如果在考试中遇到了一个进程需要同时持有多个临界资源的情况，应该参考哲学家问题的思想，分析题中给出的进程之间是否会发生循环等待，是否会发生死锁。可以参考哲学家就餐问题解决死锁的三种思路
死锁
死锁的概念
! 补充：当一个进程被阻塞时,它只是释放了对CPU的占用,进入了等待状态,而不会自动释放它已获得的其他资源(如内存、文件等)。这也是为什么会产生死锁（记录型信号量机制，只是会使进程阻塞释放CPU,但是对其他已经申请的资源保持占有）
! 补充：未必发生循环等待就一定死锁，但死锁一定发生循环等待
死锁处理策略–预防死锁
预防死锁：通过设置某些限制条件，去破坏产生死锁的四个必要条件中的一个或几个条件，来防止死锁的发生。是一种静态的策略
破坏“互斥条件”
就是在系统里取消互斥。若资源不被一个进程独占使用，那么死锁是肯定不会发生的。
缺点：但一般来说在所列的四个条件中，“互斥”条件是无法破坏的。因此，在死锁预防里主要是破坏其他几个必要条件，而不去涉及破坏“互斥”条件。
破坏“不剥夺条件”
方案一：当某个进程请求新的资源得不到满足时，它必须立即释放保持的所有资源，待以后需要时再重新申请。也就是说，即使某些资源尚未使用完，也需要主动释放，从而破坏了不可剥夺条件。
方案二：当某个进程需要的资源被其他进程所占有的时候，可以由操作系统协助，将想要的资源强行剥夺。这种方式一般需要考虑各进程的优先级（比如：剥夺调度方式，就是将处理机资源强行剥夺给优先级更高的进程使用）
缺点：
- 实现起来比较复杂。
- 释放已获得的资源可能造成前一阶段工作的失效。因此这种方法一般只适用于易保存和恢复状态的资源，如CPU。
- 反复地申请和释放资源会增加系统开销，降低系统吞吐量。
- 若采用方案一，意味着只要暂时得不到某个资源，之前获得的那些资源就都需要放弃，以后再重新申请。如果一直发生这样的情况，就会导致进程饥饿。
破坏“请求和保持条件”
请求和保持条件：进程已经保持了至少一个资源，但又提出了新的资源请求，而该资源又被其他进程占有，此时请求进程被阻塞，但又对自己已有的资源保持不放。
可以采用静态分配方法，即进程在运行前一次申请完它所需要的全部资源，在它的资源未满足前，不让它投入运行。一旦投入运行后，这些资源就一直归它所有，该进程就不会再请求别的任何资源了。
缺点：有些资源可能只需要用很短的时间，因此如果进程的整个运行期间都一直保持着所有资源，就会造成严重的资源浪费，资源利用率极低。另外，该策略也有可能导致某些进程饥饿。
破坏“循环等待条件”
破坏“循环等待”条件的一种方法，是将系统中的所有资源统一编号，进程可在任何时刻提出资源申请，但所有申请必须按照资源的编号顺序（升序）提出。这样做就能保证系统不出现死锁(死锁发生只可能是大编号往小编号申请，但是违反了规则不会出现，所以死锁不会发生)。
1 | 例：拥有资源1,2,3。进程A需要1，3 ；进程B需要1,2；进程C需要2,3 |
缺点：
- 不方便增加新的设备，因为可能需要重新分配所有的编号；
- 进程实际使用资源的顺序可能和编号递增顺序不一致，会导致资源浪费；
- 必须按规定次序申请资源，用户编程麻烦
死锁处理策略–避免死锁
避免死锁： 用某种方法防止系统进入不安全状态，从而避免死锁（银行家算法）
什么是安全序列？安全状态？
所谓安全序列，就是指如果系统按照这种序列分配资源，则每个进程都能顺利完成。只要能找出一个安全序列，系统就是安全状态。当然，安全序列可能有多个。如果分配了资源之后，系统中找不出任何一个安全序列，系统就进入了不安全状态。这就意味着之后可能所有进程都无法顺利的执行下去。当然，如果有进程提前归还了一些资源，那系统也有可能重新回到安全状态，不过我们在分配资源之前总是要考虑到最坏的情况。
如果系统处于安全状态，就一定不会发生死锁。如果系统进入不安全状态，就可能发生死锁（处于不安全状态未必就是发生了死锁，但发生死锁时一定是在不安全状态）因此可以在资源分配之前预先判断这次分配是否会导致系统进入不安全状态，以此决定是否答应资源分配请求。这也是“银行家算法”的核心思想。
银行家算法
银行家算法：是荷兰学者 Dijkstra 为银行系统设计的，以确保银行在发放现金贷款时，不会发生不能满足所有客户需要的情况。后来该算法被用在操作系统中，用于避免死锁。
核心思想：在进程提出资源申请时，先预判此次分配是否会导致系统进入不安全状态。如果会进入不安全状态，就暂时不答应这次请求，让该进程先阻塞等待。
例子
资源总数 (10, 5, 7)
1 | 此时系统是否处于安全状态？ |
银行家算法实现
数据结构：
长度为 m 的一维数组 Available 表示还有多少可用资源
nxm 矩阵 Max 表示各进程对资源的最大需求数
nxm 矩阵 Allocation 表示已经给各进程分配了多少资源
Max – Allocation = Need 矩阵表示各进程最多还需要多少资源
用长度为 m 的一位数组 Request 表示进程此次申请的各种资源数
银行家算法步骤：
①检查此次申请是否超过了之前声明的最大需求数
②检查此时系统剩余的可用资源是否还能满足这次请求
③试探着分配，更改各数据结构
④用安全性算法检查此次分配是否会导致系统进入不安全状态
安全性算法步骤：
检查当前的剩余可用资源是否能满足某个进程的最大需求，如果可以，就把该进程加入安全序列，并把该进程持有的资源全部回收。不断重复上述过程，看最终是否能让所有进程都加入安全序列。
1 | 假设系统中有 n 个进程，m 种资源.每个进程在运行前先声明对各种资源的最大需求数，则可用一个 n*m 的矩阵（可用二维数组实现）表示所有进程对各种资源的最大需求数。不妨称为 最大需求矩 阵 Max，Max[i, j]=K 表示进程 Pi 最多需要 K 个资源 |
死锁处理策略–检测和解除
死锁的检测和解除：允许死锁的发生，不过操作系统会负责检测出死锁的发生，然后采取某种措施解除死锁。
死锁的检测
为了能对系统是否已发生了死锁进行检测，必须：
①用某种数据结构来保存资源的请求和分配信息；
②提供一种算法，利用上述信息来检测系统是否已进入死锁状态。
绿色边，代表已经被分配出去的一个资源，蓝色边代表还需要申请的资源
资源足够时，进程结束会将资源归还，从而消除这些边，如果能将所有边消除就称这个图是可完全简化的此时一定没有发生死锁（相当于能找到一个安全序列）如果最终不能消除所有边，那么此时就是发生了死锁。
1.可以消除所有的边说明没有发生死锁
2.不可以消除所有的边，说明发生死锁
死锁的解除
一旦检测出死锁的发生，就应该立即解除死锁。
补充：并不是系统中所有的进程都是死锁状态，用死锁检测算法化简资源分配图后，还连着边的那些进程就是死锁进程。
解除死锁的主要方法有：
- 资源剥夺法。挂起（暂时放到外存上）某些死锁进程，并抢占它的资源，将这些资源分配给其他的死锁进程。但是应防止被挂起的进程长时间得不到资源而饥饿。
- 撤销进程法（或称终止进程法）。强制撤销部分、甚至全部死锁进程，并剥夺这些进程的资源。这种方式的优点是实现简单，但所付出的代价可能会很大。因为有些进程可能已经运行了很长时间，已经接近结束了，一旦被终止可谓功亏一篑，以后还得从头再来。
- 进程回退法。让一个或多个死锁进程回退到足以避免死锁的地步。这就要求系统要记录进程的历史信息，设置还原点。
Practice questions
进程与线程
1 | 进程映像/进程实体 = PCB+程序段+数据段 |
1 | 属于不同进程的线程之间通信需要通过系统调用，保障信息的安全。 |
C.单处理器系统中，有可能发生死锁，导致没有任何一个进程获得处理机运行
D.当进程拥有运行所需的全部资源，只有处理机得不到满足时，是处于就绪态
某进程所需资源不在主存中，所以会请求I/O操作,那么期间进程所需资源还没得到满足，会先处在阻塞态。接着I/O操作完成，获得了需要的资源，就会由阻塞态转变成就绪态等待处理机
进程安全问题，需要同步互斥解决
引入线程之后，处理机分配的基本单位就是线程。资源分派的基本单位还是进程
拓展：即使数据集相同，进程就相同了吗？答：两次创建的进程依然不同。原因：每次创建的PCB是不同的。而PCB是进程存在的唯一标志，与进程是一一对应的，因此只要PCB不同，就一定不是相同的进程。
全局变量存放在进程映像中的数据段中，属于一个进程里面，不能与别的进程交换数据
进程被唤醒前处于阻塞状态，唤醒后处在就绪状态
时间片用完，适当降低优先级让其他进程有机会获得处理机
父进程创建子进程，是指父进程执行过程中启动了一个进程，两个进程互不影响，并发运行
父进程调用子进程，是指父进程顺序执行，中间调用了另外一段程序，必须等待子程序执行完，才能顺序执行接下来的主程序代码
处理机调度
1 | 时间片轮转调度算法没有使得系统变得高效，反而他使得每个任务的平均完成时间变长 |
1 | 首先搞清楚，IO繁忙型作业与CPU繁忙型作业的含义。 |
1 | 平均周转时间计算练习。 |
1 | 短作业优先算法，具有最短的平均周转时间，和平均等待时间 |
1 | 响应比 |
IV .中断发生，执行中断隐指令，为什么要用硬件实现？
答：因为无法用软件实现，因为，当程序执行时，无法提前预知到中断会从哪里出现，也就不能前在程序中写入跳转指向中断服务程序的代码。所以只能通过硬件实现
作业调度：从外存上处于后备队列的作业中挑选一个（或多个）作业，给他们分配内存等必要资源，并建立相应的进程(建立PCB),以使它（们）获得竟争处理机的权利
进程调度：在已有进程中选择其中几个赋予处理机的调度
同步与互斥
1 | A.进入区与退出区，实现进程互斥 |
1 | 进程并发，需要的是中断机制 |
1 | 同步和互斥都应当遵循以下的四条原则 |
1 | P、V 操作都是原语，一气呵成，P、V都是由开中断和关中断包括在中间实现。 |
1 | 互斥信号量，一般初始为1。 |
临界区是代码段，5个进程就有5个临界区
管程中的signal操作只是唤醒，与信号机制中的V操作不同在于，V还可以使得值+1
互斥信号量只能初始设为1，任何进程对其都只能互斥访问
同步信号量，根据资源数确定，只有当极端情况出现(空或满)时，才需要满足前后关系
软件法实现进程互斥–peteson算法
软件实现的进程互斥，使用while循环，阻止进程访问临界区，导致一个问题，一直占用CPU,不满足让权等待
让权等待，只有引入P,V机制后才得到实现，在这之前，互斥的实现都只满足以上三条
独自完成的一道题目
双标志先检查法，无法实现互斥，导致同时都能访问临界资源
双标志后检查法，导致两个进程都无法访问临界资源
多生产者，多消费者问题
*1.理清多少个进程：理发师、顾客*
*2.各个进程对应的资源是什么：顾客的资源：理发师+椅子。理发师的资源：顾客*
*3.当某种资源得不到满足就离开而不是阻塞时，该资源不应该作为信号量
读者写者问题
第一个观众负责申请资源，最后一个观众负责释放资源
死锁
破坏死锁的必要条件
非死锁的进程所持有的资源对死锁进程毫无作用，所以D
产生死锁的原因：1.竞争资源；2.进程推进顺序非法
产生死锁的必要条件：1.互斥；2.不可剥夺；3.请求和保持；4.循环等待
哲学家进餐问题
银行家算法
内存管理
内存的基础知识
内存管理的概念
操作系统作为系统资源的管理者，当然也需要对内存进行管理，要管些什么呢？
内存保护可以采取两种方式：
方法1：在CPU中设置一对上、下限寄存器，存放进程的上、下限地址。进程的指令要访问某个地址时，CPU检查是否越界
方法2：采用重定位寄存器（又称基址寄存器）和界地址寄存器（又称限长寄存器）进行越界检查。重定位寄存器中存放的是进程的起始物理地址。界地址寄存器中存放的是进程的最大逻辑地址.
进程的内存映像
这是一段代码，分别对应存储在不同的内存区域当中
#include studio.h头文件包括的库函数注意：#define X 1024 宏定义的常量不专门分配存储空间，在预编译阶段就将程序中所有X都想替换成了1024
32位系统的，内存空间是4GB。32位是MAR位数，指的是最多有232个内存地址，按照字节寻址，所以总容量就是232B=4GB
内存管理
内存空间的扩充
进程的覆盖技术与交换技术
1.覆盖技术
覆盖技术的思想：将程序分为多个段（多个模块）。常用的段常驻内存，不常用的段在需要时调入内存。内存中分为一个“固定区”和若干个“覆盖区”。需要常驻内存的段放在“固定区”中，调入后就不再调出（除非运行结束）不常用的段放在“覆盖区”，需要用到时调入内存，用不到时调出内存
缺点：必须由程序员声明覆盖结构，操作系统完成自动覆盖。对用户不透明，增加了用户编程负担。覆盖技术只用于早期的单道批处理操作系统中，现在已成为历史。
2.交换技术
交换（对换）技术的设计思想：内存空间紧张时，系统将内存中某些进程暂时换出外存（以进程为单位进行交换,），把外存中某些已具备运行条件的进程换入内存（进程在内存与磁盘间动态调度），中级调度(内存调度)实现。暂时换出外存等待的进程状态为挂起状态（挂起态，suspend）挂起态又可以进一步细分为就绪挂起、阻塞挂起两种状态
1. 应该在外存（磁盘）的什么位置保存被换出的进程？
2. 什么时候应该交换？
3. 应该换出哪些进程？
- 具有对换功能的操作系统中，通常把磁盘空间分为文件区和对换区两部分。文件区主要用于存放文件，主要追求存储空间的利用率，因此对文件区空间的管理采用离散分配方式；对换区空间只占磁盘空间的小部分，被换出的进程数据就存放在对换区。由于对换的速度直接影响到系统的整体速度，因此对换区空间的管理主要追求换入换出速度，因此通常对换区采用连续分配方式（学过文件管理章节后即可理解）。总之，对换区的I/O速度比文件区的更快。
- 交换通常在许多进程运行且内存吃紧时进行，而系统负荷降低就暂停。例如：在发现许多进程运行时经常发生缺页，就说明内存紧张，此时可以换出一些进程；如果缺页率明显下降，就可以暂停换出。
- 可优先换出阻塞进程；可换出优先级低的进程；为了防止优先级低的进程在被调入内存后很快又被换出，有的系统还会考虑进程在内存的驻留时间…（注意：PCB 会常驻内存，不会被换出外存）
虚拟存储技术
虚拟存储技术是通过把内存扩展到外部存储设备,让程序可以获得比实际内存更大的逻辑地址空间。它通过把内存分页,并与外部存储建立页面映射表,当需要访问不在内存的页面时,通过页面置换算法将其换入内存。
1. 虚拟存储以页面为单位,交换技术以进程为单位。
2. 虚拟存储需要建立地址映射表,维护页面与外存地址的对应关系。交换技术不需要。
3. 虚拟存储发生页面异常时才发生换页,交换技术在进程切换时就进行。
4. 虚拟存储对程序是透明的,程序不必关心页面访问,交换技术程序需要关心整个进程的换入换出。
5. 虚拟存储可以同时维持多个进程/程序的工作集,交换技术每次只能有一个进程在运行。
虚拟存储技术与覆盖技术的区别？
1. 工作方式不同
虚拟存储是把内存扩展到外部存储设备,建立页面映射表,实现地址映射和自动页面调度。数据按需换入换出。
覆盖技术是在内存中维持多个覆盖程序,只加载当前需要执行的覆盖程序到内存。数据不会自动调度,需要程序员控制。
2. 程序个数不同
虚拟存储可以同时维持多个进程在内存和外存的工作集。
覆盖技术每次只能加载一个覆盖程序到内存执行。
3. 对程序的影响不同
虚拟存储对运行程序透明,程序不必关心页面调度。
覆盖技术程序员必须控制程序的覆盖和重定位。
4. 实现难度不同
虚拟存储实现较复杂,需要建立地址映射、页面置换算法等机制。
覆盖技术原理简单,直接通过程序员控制实现。
5. 使用范围不同
虚拟存储广泛用于各种通用操作系统。
覆盖技术只适用于特定的嵌入式系统。
具体会在3.5中作详细介绍
内存空间的分配与回收
连续分配管理方式
连续分配是指为用户分配的必须是连续的一段内存空间
1.单一连续分配
在单一连续分配方式中，内存被分为系统区和用户区。系统区通常位于内存的低地址部分，用于存放操作系统相关数据；用户区用于存放用户进程相关数据。内存中只能有一道用户程序，用户程序独占整个用户区空间。
优点：实现简单；无外部碎片；可以采用覆盖技术扩充内存；不一定需要采取内存保护（eg：早期的 PC 操作系统 MS-DOS）。
缺点：只能用于单用户、单任务的操作系统中；有内部碎片；存储器利用率极低
2.固定分区分配
出现了支持多道程序的系统，为了能在内存中装入多道程序，且这些程序之间又不会相互干扰，于是将整个用户空间划分为若干个固定大小的分区，在每个分区中只装入一道作业，这样就形成了最早的、最简单的一种可运行多道程序的内存管理方式。
分区大小相等：缺乏灵活性，但是很适合用于用一台计算机控制多个相同对象的场合（比如：钢铁厂有n个相同的炼钢炉，就可把内存分为n个大小相等的区域存放n个炼钢炉控制程序）
分区大小不等：增加了灵活性，可以满足不同大小的进程需求。根据常在系统中运行的作业大小情况进行划分比如：划分多个小分区、适量中等分区、少量大分区）
操作系统需要建立一个数据结构——分区说明表，来实现各个分区的分配与回
收。每个表项对应一个分区，通常按分区大小排列。每个表项包括对应分区的
大小、起始地址、状态（是否已分配）。
当某用户程序要装入内存时，由操作系统内核程序根据用户程序大小检索该表，
从中找到一个能满足大小的、未分配的分区，将之分配给该程序，然后修改状
态为“已分配”
优点：实现简单，无外部碎片。
缺点：a. 当用户程序太大时，可能所有的分区都不能满足需求，此时不得不采
用覆盖技术来解决，但这又会降低性能；b. 会产生内部碎片，内存利用率低。
注：内部碎片是已经被分配出去的的内存空间大于请求所需的内存空间。 外部碎片是指还没有分配出去，但是由于大小太小而无法分配给申请空间的新进程的内存空间空闲块
3.动态分区分配
动态分区分配又称为可变分区分配。这种分配方式不会预先划分内存分区，而是在进程装入内存时，根据进程的大小动态地建立分区，并使分区的大小正好适合进程的需要。因此系统分区的大小和数目是可变的。（eg：假设某计算机内存大小为 64MB，系统区 8MB，用户区共 56 MB…）
系统要用什么样的数据结构记录内存的使用情况？
答：空闲分区表和空闲分区链（记录的都是空闲内存区域）当很多个空闲分区都能满足需求时，应该选择哪个分区进行分配？应该用最大的分区进行分配 ？还 是用最小的分区进行分配 ？ 又或是用地址最低 的部分进行分配?
答：下一节讨论如何进行分区的分配与回收操作？
答：相邻的空闲分区合并为一个
动态分区分配没有内部碎片，但是有外部碎片。
如果内存中空闲空间的总和本来可以满足某进程的要求，但由于进程需要的是一整块连续的内存空间，因此这些“碎片”不能满足进程的需求。可以通过紧凑（拼凑，Compaction）技术来解决外部碎片。
!（动态分区分配算法）
引入
当很多个空闲分区都能满足需求时，应该选择哪个分区进行分配？
1.首次适应算法
算法思想：每次都从低地址开始查找，找到第一个能满足大小的空闲分区。
如何实现：空闲分区以地址递增的次序排列。每次分配内存时顺序查找空闲分区链（或空闲分区表），找到大小能满足要求的第一个空闲分区。(Tips：在合适的空闲分区中，优先分配低地址，从低地址往高地址分配)
2.最佳适应算法
算法思想：由于动态分区分配是一种连续分配方式，为各进程分配的空间必须是连续的一整片区域。因此为了保证当“大进程”到来时能有连续的大片空间，可以尽可能多地留下大片的空闲区，即，优先使用更小的空闲区(Tips：在合适的空闲分区中，优先分配低地址，从低地址往高地址分配)。
如何实现：空闲分区按容量递增次序链接。每次分配内存时顺序查找空闲分区链（或空闲分区表），找到大小能满足要求的第一个空闲分区。
缺点：每次都是选取最小的分区进行分配，会留下越来越多，很小的难以利用的内存块，因此会产生很多的外部碎片
3.最坏适应算法
算法思想：为了解决最佳适应算法的问题——即留下太多难以利用的小碎片，可以在每次分配时优先使用最大的连续空闲区，这样分配后剩余的空闲区就不会太小，更方便使用。
如何实现：空闲分区按容量递减次序链接。每次分配内存时顺序查找空闲分区链（或空闲分区表），找到大小能满足要求的第一个空闲分区。(Tips：在合适的空闲分区中，优先分配低地址，从低地址往高地址分配)
缺点：每次都选最大的分区进行分配，虽然可以让分配后留下的空闲区更大，更可用，但是这种方式会导致较大的连续空闲区被迅速用完。如果之后有“大进程”到达，就没有内存分区可用了。
4.邻近适应算法
算法思想：首次适应算法每次都从链头开始查找的。这可能会导致低地址部分出现很多小的空闲分区，而每次分配查找时，都要经过这些分区，因此也增加了查找的开销。如果每次都从上次查找结束的位置开始检索，就能解决上述问题。
如何实现：空闲分区以地址递增的顺序排列（可排成一个循环链表）。每次分配内存时从上次查找结束的位置开始查找空闲分区链（或空闲分区表），找到大小能满足要求的第一个空闲分区。
小结
tip：所有动态分区分配算法，回收时，当回收的块与原来的空闲块相邻时，需要将这些块合并
非连续非配管理方式
非连续分配是指为用户分配的可以是一些分散的内存空间
基本分页存储管理
1.什么是分页存储？
将内存空间分为一个个大小相等的分区（比如：每个分区4KB），每个分区就是一个“页框”（页框=页帧=内存块=物理块=物理页面）。每个页框有一个编号，即“页框号”（页框号=页帧号=内存块号=物理块号=物理页号），页框号从 0 开始
将进程的逻辑地址空间也分为 与页框大小相等 的一个个部分，每个部分称为一个“页”或“页面” 。每个页面也有一个编号，即“页号”，页号也是 从 0 开始 。
操作系统以页框为单位为各个进程分配内存空间。进程的每个页面分别放入一个页框中。也就是说，进程的页面与内存的页框有一一对应的关系。各个页面不必连续存放，可以放到不相邻的各个页框中。
注：进程的最后一个页面可能没有一个页框那么大。也就是说，分页存储最后一个页面有可能产生内部碎片，因此页框不能太大，否则可能产生过大的内部碎片造成浪费
2.分页存储的逻辑地址结构
3.页表
为了能知道进程的每个页面在内存中存放的位置，操作系统要为每个进程建立一张页表。【注：页表通常存在PCB（进程控制块）中】
- 一个进程对应一张页表。
- 进程的每个页面对应一个页表项。
- 每个页表项由“页号”和“块号”组成。
- 页表记录进程页面和实际存放的内存块之间的映射关系。
- 每个页表项的长度是相同的。
4.每个页表项占多少个字节？
注：页表项连续存放，因此页号可以是隐含的，不占存储空间（类比数组）
假设页表中的各页表项从内存地址为 X 的地方开始连续存放…如何找到页号为 i 的页表项？（按字节编址）
i 号页表项的存放地址 = X + 3 * I 因此，页表中的页号可以是隐含的，即页号不占用存储空间。通过页号结合页表项长度，计算得出块号存放起始地址，然后就可以取得块号，最后将取得的块号与逻辑偏移量拼接就得到物理地址了
5.如何实现地址转换？
将进程地址空间 分页 之后，操作系统该如何实现逻辑地址到物理地址的转换？
在计算机内部，地址是用二进制表示的，如果页面大小 刚好是 2 的整数幂，则计算机硬件可以很快速的把逻辑地址拆分成（页号，页内偏移量）
小结：页面大小 刚好是 2 的整数幂有什么好处？
①逻辑地址的拆分更加迅速——如果每个页面大小为 2 K B，用二进制数表示逻辑地址，则末尾 K 位即为页内偏移量，其余部分就是页号。因此，如果让每个页面的大小为 2 的整数幂，计算机硬件就可以很方便地得出一个逻辑地址对应的页号和页内偏移量，而无需进行除法运算，从而提升了运行速度。
②物理地址的计算更加迅速——根据逻辑地址得到页号，根据页号查询页表从而找到页面存放的内存块号，将二进制表示的内存块号和页内偏移量拼接起来，就可以得到最终的物理地址。
!（基本地址变换机构）
地址变换过程
通常会在系统中设置一个页表基址寄存器（PTR），存放页表在内存中的起始地址F 和页表长度M。进程未执行时，页表的始址和页表长度 放在进程控制块（PCB）中，当进程被调度时，操作系统内核会把它们放到页表寄存器中。
设页面大小为L，逻辑地址A到物理地址E的变换过程如下：
①计算页号 P 和页内偏移量W（ 如果用十进制数手算，则 P=A/L，W=A%L；但是在计算机实际运行时，逻辑地址结构是固定不变的，因此计算机硬件可以更快地得到二进制表示的页号、页内偏移量）。
②比较页号P 和页表长度M，若 P≥M，则产生越界中断，否则继续执行。（注意：页号是从0开始的，而页表长度至少是1，因此 P=M 时也会越界）。
③页表中页号P对应的页表项地址 = 页表起始地址F + 页号P * 页表项长度，取出该页表项内容b，即为内存块号。（注意区分页表项长度、页表长度、页面大小的区别。页表长度指的是这个页表中总共有几个页表项，即总共有几个页；页表项长度指的是每个页表项占多大的存储空间；页面大小指的是一个页面占多大的存储空间）。
④计算 E = b * L + W，用得到的物理地址E 去访存。（如果内存块号、页面偏移量是用二进制表示的，那么把二者拼接起来就是最终的物理地址了）。
!（具有快表的地址变换机构）
1.什么是快表？
快表，又称相联寄存器（TLB， translation lookaside buffer ），是一种访问速度比内存快很多的高速缓存（TLB不是内存！）与使用组相联映射。与Cache一样都是使用SRAM芯片实现，用来存放最近访问的页表项的副本，可以加速地址变换的速度。与此对应，内存中的页表常称为慢表。
补充！
快表TLB与与Cache采用的都是相联映射方式，由于只有局部的表项数据，查找快表或Cache时，不像页表那样通过虚拟块号计算物理块号，而是采用标志位比对的方式。具体标志位的位数取决于相联映射的方式
TLB 和 普通 Cache 的区别——TLB 中只有页表项的副本，而普通 Cache 中可能会有其他各种数据的副本
2.引入快表后，地址变换过程
① CPU给出逻辑地址，由某个硬件算得页号、页内偏移量，将页号与快表中的所有页号进行比较。
② 如果找到匹配的页号，说明要访问的页表项在快表中有副本，则直接从中取出该页对应的内存块号，再将内存块号与页内偏移量拼接形成物理地址，最后，访问该物理地址对应的内存单元。因此，若快表命中，则访问某个逻辑地址仅需一次访存即可。
③ 如果没有找到匹配的页号，则需要访问内存中的页表，找到对应页表项，得到页面存放的内存块号，再将内存块号与页内偏移量拼接形成物理地址，最后，访问该物理地址对应的内存单元。因此，若快表未命中，则访问某个逻辑地址需要两次访存（注意：在找到页表项后，应同时将其存入快表，以便后面可能的再次访问。但若快表已满，则必须按照一定的算法对旧的页表项进行替换）
例：某系统使用基本分页存储管理，并采用了具有快表的地址变换机构。访问一次快表耗时 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
显然，引入快表机制后，访问一个逻辑地址的速度快多了。
由于查询快表的速度比查询页表的速度快很多，因此只要快表命中，就可以节省很多时间。因为局部性原理，一般来说快表的命中率可以达到 90% 以上。
3.什么是局部性原理？
时间局部性：如果执行了程序中的某条指令，那么不久后这条指令很有可能再次执行；如果某个数据被访问过，不久之后该数据很可能再次被访问。（因为程序中存在大量的循环）
空间局部性：一旦程序访问了某个存储单元，在不久之后，其附近的存储单元也很有可能被访问。（因为很多数据在内存中都是连续存放的）
4.区别
!（两级页表）
1.单页表存在的问题
问题一：页表必须连续存放，因此当页表很大时，需要占用很多个连续的页框。
问题二：没有必要让整个页表常驻内存，因为进程在一段时间内可能只需要访问某几个特定的页面。
2.如何解决单级页表的问题
解决问题一：把页表再分页并离散存储，然后再建立一张页表记录页表各个部分的存放位置，称为页目录表，或称外层页表，或称顶层页表。
解决问题二：可以在需要访问页面时才把页面调入内存（虚拟存储技术）。可以在页表项中增加一个标志位，用于表示该页面是否已经调入内存。若想访问的页面不在内存中，则产生缺页中断（内中断/异常），然后将目标页面从外存调入内存。
3.二级页表的原理、地址结构
4.如何实现地址变换
①按照地址结构将逻辑地址拆分成三部分
②从PCB 中读出页目录表始址，再根据一级页号查页目录
表，找到下一级页表在内存中的存放位置
③根据二级页号查二级页表，找到最终想访问的内存块号
④结合页内偏移量得到物理地址
例：将逻辑地址 (0000000000,0000000001,111111111111) 转换为物理地址（用十进制表示）。
5.需要注意的几个细节
若分为二级级页表后，页表依然很长，则可以采用更多级页表，一般来说各级页表的大小不能超过一个页面。
价点：各级页表不再需要连续的存储空间来存放。
缺点：地址转换时访存次数增加了（每一级页表的查询都要访存）
重要重要重要：在二级页表（或更多级的页表）中，若引入快表机构，则快表中的“页号”是“复合页号”！！
多级页表中，快表命中并不指的是查到一级页表块号，而是由于快表中页号采用的是坐标/向量 ，所以命中了往后所有级别的块号，直接得到了最终的目标物理地址。
基本分段存储管理
与“分页”最大的区别就是——离散分配时所分配地址空间的基本单位不同。在分页当中，每个页面的大小是相同的；分段当中，每个段的大小是不同的。
1.什么是分段存储？
进程的地址空间：按照程序自身的逻辑关系划分为若干个大小不一的段，每个段都有一个段名（在低级语言中，程序员使用段名来编程），每段从0开始编址内存分配规则：以段为单位进行分配，每个段在内存中占据连续空间，但各段之间可以不相邻。
2.分段存储的逻辑地址结构
分段系统的<>逻辑地址<>结构由段号（段名）和段内地址（段内偏移量）所组成。如：
在上述例子中，若系统是按字节寻址的，
则段号占16位，因此在该系统中，每个进程最多有 2 16 = 64K 个段。
段内地址占 16位，因此每个段的最大长度是 2 16 = 64KB。
3.段表
- 每个段对应一个段表项，其中记录了该段在内存中的起始位置（又称“基址”）和段的长度。（由于主存中的分段大小不一，所以不能只存块号，应直接存基址）
- 各个段表项的长度是相同的。例如：某系统按字节寻址，采用分段存储管理，逻辑地址结构为（段号16位, 段内地址16位），因此用16位即可表示最大段长。物理内存大小为4GB（可用32位表示整个物理内存地址空间）。因此，可以让每个段表项占 16+32 = 48位，即6B。由于段表项长度相同，因此段号可以是隐含的，不占存储空间。若段表存放的起始地址为 M，则 K号段对应的段表项存放的地址为 M + K * 6
4.如何实现地址转换?
5.分段与分页管理的对比
段是信息的逻辑单位。分段的主要目的是更好地满足用户需求。一个段通常包含着一组属于一个逻辑模块的信息。分段对用户是可见的，用户编程时需要显式地给出段名。
页的大小固定且由系统决定。段的长度却不固定，决定于用户编写的程序。
分页 的用户进程地址空间是一维的，程序员只需给出一个记忆符即可表示一个地址。
分段 的用户进程地址空间是二维的，程序员在标识一个地址时，既要给出段名，也要给出段内地址。
访问一个逻辑地址需要几次访存？
分页（单级页表）：第一次访存——查内存中的页表，第二次访存——访问目标内存单元。总共两次访存。
分段：第一次访存——查内存中的段表，第二次访存——访问目标内存单元。总共两次访存与分页系统类似，分段系统中也可以引入快表机构，将近期访问过的段表项放到快表中，这样可以少一次访问，加快地址变换速度。分段比分页更容易实现信息的共享和保护
1 | 假如要共享进程中绿色部分信息： |
6.小结
虚拟内存管理
虚拟内存管理基本概念
传统存储管理方式的特征
上一节所讨论的各种内存管理策略都是为了同时将多个进程保存在内存中以便允许多道程序设计。它们都具有以下两个共同的特征：
- 一次性
作业必须一次性全部装入内存后，方能开始运行。这会导致两种情况发生：
- 当作业很大，不能全部被装入内存时，将使该作业无法运行；
- 当大量作业要求运行时，由于内存不足以容纳所有作业，只能使少数作业先运行，导致多道程序度的下降。
- 驻留性
作业被装入内存后，就一直驻留在内存中，其任何部分都不会被换出，直至作业运行结束。运行中的进程，会因等待I/O而被阻塞，可能处于长期等待状态。
由以上分析可知，许多在程序运行中不用或暂时不用的程序（数据）占据了大量的内存空间，而一些需要运行的作业又无法装入运行，显然浪费了宝贵的内存资源。
虚拟内存的定义和特征
时间局部性：如果执行了程序中的某条指令，那么不久后这条指令很有可能再次执行；如果某个数据被访问过，不久之后该数据很可能再次被访问。（因为程序中存在大量的循环）
空间局部性：一旦程序访问了某个存储单元，在不久之后，其附近的存储单元也很有可能被访问。（因为很多数据在内存中都是连续存放的，并且程序的指令也是顺序地在内存中存放的）
基于局部性原理，在程序装入时，可以将程序中很快会用到的部分装入内存，暂时用不到的部分留在外存，就可以让程序开始执行。
在程序执行过程中，当所访问的信息不在内存时，由操作系统负责将所需信息从外存调入内存，然后继续执行程序。
若内存空间不够，由操作系统负责将内存中暂时用不到的信息换出到外存。在操作系统的管理下，在用户看来似乎有一个比实际内存大得多的内存，这就是虚拟内存
虚拟内存有一下三个主要特征：
- 多次性：无需在作业运行时一次性全部装入内存，而是允许被分成多次调入内存。
- 对换性：在作业运行时无需一直常驻内存，而是允许在作业运行过程中，将作业换入、换出。
- 虚拟性：从逻辑上扩充了内存的容量，使用户看到的内存容量，远大于实际的容量
如何实现虚拟内存技术
虚拟内存技术，允许一个作业分多次调入内存。如果采用连续分配方式，会不方便实现。因此，虚拟内存的实现需要建立在离散分配的内存管理方式基础上。虚拟内存的实现有以下三种方式：
小结
请求分页管理方式
请求分页系统是建立在基本分页的基础上的，为了能支持虚拟存储器功能而增加了请求调页功能和页面置换功能。
相应地，每次调入和换出的基本单位都是长度固定的页面，这使得请求分页系统在实现上要比请求分段系统简单。
请求分段系统在换进和换出时是可变长度的段因此，请求分页便成为目前最常用的一种实现虚拟存储器的方式
请求分页中的硬件支持
为了实现请求分页，系统必须提供一定的硬件支持。除了需要一台具有一定容量的内存及外存的计算机系统外，还需要有页表机制、缺页中断机构以及地址变换机构
页表机制
在请求分页系统中所需要的主要数据结构是页表。其基本作用仍然是将用户空间中的逻辑地址变换为内存空间中的物理地址。
由于只将应用程序的一部分调入内存，还有一部分仍在盘上，故需在页表中再增加4个字段，供程序（数据）在换进、换出时参考。
请求分页系统中的每个页表项如下所示：
- 状态位P：用于指示该页是否已调入内存，供程序访问时参考。
- 访问字段A：用于记录本页在一段时间内被访问的次数，或记录本页最近已有多长时间未被访问，供选择换出页面时参考。
- 修改位M：表示该页在调入内存后是否被修改过。供置换页面时参考。由于内存中的每一页都在外存上有一份副本，因此，若未被修改，在置换该页时就不需要将该页写回到外存上，以减少系统的开销和启动磁盘的次数；若已被修改，则必须将该页重写到外存上，以保证外存中所保留的始终是最新副本。
- 外存地址：用于指出该页在外存上的地址
缺页中断机制
地址变换机制
1.操作系统要提供请求调页功能，将缺失页面从外存调入内存
2.操作系统要提供页面置换的功能，将暂时用不到的页面换出外存
在具有快表机构的请求分页系统中访问一个逻辑地址 时，若发生缺页，则地址变换步骤是：
查快表(未命中)——查慢表(发现未调入内存)——调页(调 入的页面对应的表项会直接加入快表)——查快表(命 中)——访问目标内存单元
补充细节
①只有“写指令”才需要修改 “修改位”。并且，一般来说只 需修改快表中的数据，只有要将 快表项删除时才需要写回内存中 的慢表。这样可以减少访存次数。
②和普通的中断处理一样，缺页 中断处理依然需要保留CPU现场
③需要用某种“页面置换算法” 来决定一个换出页面（下节内容）
④换入/换出页面都需要启动慢 速的I/O操作，可见，如果换入/ 换出太频繁，会有很大的开销
⑤页面调入内存后，需要修改慢 表(页表)，同时也需要将表项复制到快 表中
页面置换算法
请求分页存储管理与基本分页存储管理的主要区别：
在程序执行过程中，当所访问的信息不在内存时，由操作系统负责将所需信息从外存调入内存，然后继续执行程序。若内存空间不够，由操作系统负责将内存中暂时用不到的信息换出到外存。用页面置换算法决定应该换出哪个页面
最佳置换算法(OPT)
最佳置换算法（OPT，Optimal）：每次选择淘汰的页面将是以后永不使用，或者在最长时间内不再被访问的页面，这样可以保证最低的缺页率。
最佳置换算法可以保证最低的缺页率，但实际上，只有在进程执行的过程中才能知道接下来会访问到的是哪个页面。操作系统无法提前预判页面访问序列。因此，最佳置换算法是无法实现的。
先进先出置换算法(FIFO)
先进先出置换算法（FIFO）：每次选择淘汰的页面是最早进入内存的页面
实现方法：把调入内存的页面根据调入的先后顺序排成一个队列，需要换出页面时选择队头页面即可。队列的最大长度取决于系统为进程分配了多少个内存块。
最近最久未使用置换算法(LRU)
最近最久未使用置换算法（LRU，least recently used）：每次淘汰的页面是最近最久未使用的页面。
实现方法：赋予每个页面对应的页表项中，用访问字段记录该页面自上次被访问以来所经历的时间t。当需要淘汰一个页面时，选择现有页面中 t 值最大的，即最近最久未使用的页面。(该算法的实现需要专门的硬件支持，虽然算法性能好，但是实现困难，开销大)
时针置换算法(CLOCK)
最佳置换算法性能最好，但无法实现；先进先出置换算法实现简单，但算法性能差；最近最久未使用。置换算法性能好，是最接近OPT算法性能的，但是实现起来需要专门的硬件支持，算法开销大。时钟置换算法是一种性能和开销较均衡的算法，又称CLOCK算法，或最近未用算(NRU，NotRecently Used)。
简单的CLOCK 算法实现方法：为每个页面设置一个访问位，再将内存中的页面都通过链接指针链接成一个循环队列。当某页被访问时，其访问位置为1。当需要淘汰一个页面时，只需检查页的访问位。
如果是0，就选择该页换出；如果是1，则将它置为0，暂不换出，继续检查下一个页面，若第一轮扫描中所有页面都是1，则将这些页面的访问位依次置为0后，再进行第二轮扫描（第二轮扫描中一定会有访问位为0的页面，因此简单的CLOCK 算法选择一个淘汰页面最多会经过两轮扫描
改进型的时钟置换算法
简单的时钟置换算法仅考虑到一个页面最近是否被访问过。事实上，如果被淘汰的页面没有被修改过，就不需要执行I/O操作写回外存。只有被淘汰的页面被修改过时，才需要写回外存。
因此，除了考虑一个页面最近有没有被访问过之外，操作系统还应考虑页面有没有被修改过。在其他条件都相同时，应优先淘汰没有修改过的页面，避免I/O操作。这就是改进型的时钟置换算法的思想。修改位=0，表示页面没有被修改过；修改位=1，表示页面被修改过。
为方便讨论，用（访问位，修改位）的形式表示各页面状态。如（1，1）表示一个页面近期被访问过，且被修改过。
简单型/改进型CLOCK需要注意的细节：
①各个页面排成一个环形，各个页面按装入内存的时间排序
②若题目没有特别说明，则扫描指针默认指问最先装入的页面
小结
页面分配策略
驻留集
指请求分页存储管理中给进程分配的物理块的集合。在采用了虚拟存储技术的系统中，驻留集大小一般小于进程的总大小。若驻留集太小，会导致缺页频繁，系统要花大量的时间来处理缺页，实际用于进程推进的时间很少；驻留集太大，又会导致多道程序并发度下降，资源利用率降低。所以应大小合理
页面分配、置换策略
分配
- 固定分配：操作系统为每个进程分配一组固定数目的物理块，在进程运行期间不再改变。即，驻留集大小不变
- 可变分配：先为每个进程分配一定数目的物理块，在进程运行期间，可根据情况做适当的增加或减少。即，驻留集大小可变
置换
- 局部置换：发生缺页时只能选进程自己的物理块进行置换。
- 全局置换：可以将操作系统保留的空闲物理块分配给缺页进程，也可以将别的进程持有的物理块置换到外存，再分配给缺页进程。
- 固定分配局部置换: 系统为每个进程分配一定数量的物理块，在整个运行期间都不改变。若进程在运行中发生缺页，则只能从该进程在内存中的页面中选出一页换出，然后再调入需要的页面。这种策略的缺点是：很难在刚开始就确定应为每个进程分配多少个物理块才算合理。(采用这种策略的系统可以根据进程大小、优先级、或是根据程序员给出的参数来确定为一个进程分配的内存块数)。
- 可变分配全局置换: 刚开始会为每个进程分配一定数量的物理块。操作系统会保持一个空闲物理块队列。当某进程发生缺页时，从空闲物理块中取出一块分配给该进程；若已无空闲物理块，则可选择一个未锁定的页面换出外存，再将该物理块分配给缺页的进程。采用这种策略时，只要某进程发生缺页，都将获得新的物理块，仅当空闲物理块用完时，系统才选择一个未锁定的页面调出。被选择调出的页可能是系统中任何一个进程中的页，因此这个被选中的进程拥有的物理块会减少，缺页率会增加。
- 可变分配局部置换: 刚开始会为每个进程分配一定数量的物理块。当某进程发生缺页时，只允许从该进程自己的物理块中选出一个进行换出外存。如果进程在运行中频繁地缺页，系统会为该进程多分配几个物理块，直至该进程缺页率趋势适当程度；反之，如果进程在运行中缺页率特别低，则可适当减少分配给该进程的物理块。
调入页面的时机
预调页策略：根据局部性原理，一次调入若干个相邻的页面可能比一次调入一个页面更高效。但如果提前调入的页面中大多数都没被访问过，则又是低效的。因此可以预测不久之后可能访问到的页面，将它们预先调入内存，但目前预测成功率只有50%左右。故这种策略主要用于进程的首次调入，由程序员指出应该先调入哪些部分。运行前调入
请求调页策略：进程在运行期间发现缺页时才将所缺页面调入内存。由这种策略调入的页面一定会被访问到，但由于每次只能调入一页，而每次调页都要磁盘I/O操作，因此I/O开销较大。运行时调入
从何处调入页面
系统拥有足够的对换区空间：页面的调入、调出都是在内存与对换区之间进行，这样可以保证页面的调入、调出速度很快。在进程运行前，需将进程相关的数据从文件区复制到对换区。
系统缺少足够的对换区空间：凡是不会被修改的数据都直接从文件区调入，由于这些页面不会被修改，因此换出时不必写回磁盘，下次需要时再从文件区调入即可。对于可能被修改的部分，换出时需写回磁盘对换区，下次需要时再从对换区调入。
UNIX 方式：运行之前进程有关的数据全部放在文件区，故未使用过的页面，都可从文件区调入。若被使用过的页面需要换出，则写回对换区，下次需要时从对换区调入。
抖动现象
工作集
驻留集：指请求分页存储管理中给进程分配的内存块的集合。
工作集：指在某段时间间隔里，进程实际访问页面的集合。
操作系统会根据“窗口尺寸”来算出工作集。例：
某进程的页面访问序列如下，窗口尺寸为 4，各时刻的工作集为？
实际上工作集大小可能小于窗口尺寸，实际应用中，操作系统可以统计进程的工作集大小，根据工作集大小给进程分配若干内存块。
如：窗口尺寸为5，经过一段时间的监测发现某进程的工作集最大为3，那么说明该进程有很好的局部性，可以给这个进程分配3个以上的内存块即可满足进程的运行需要。
一般来说，驻留集大小不能小于工作集大小，否则进程运行过程中将频繁缺页。
小结
内存映射文件
什么是内存映射文件？
内存映射文件——操作系统向上层程序员提供的功能（系统调用）
• 方便程序员访问文件数据
• 方便多个进程共享同一个文件
传统的内存访问方式
open 系统调用——打开文件
seek 系统调用——将读写指针移到某个位置
read 系统调用——从读写指针所指位置读入若干数据（从磁盘读入内存）
write 系统调用——将内存中的指定数据，写回磁盘（根据读写指针确定要写回什么位置)
内存映射文件访问方式
open 系统调用——打开文件
mmap 系统调用——将文件映射到进程的虚拟地址空间
• 以访问内存的方式访问文件数据
• 文件数据的读入、写出由操作系统自动完成(缺页时系统自动调入内存)
• 进程关闭文件时，操作系统自动将文件被修改的数据写回磁盘
小结
Practice questions
内存管理概念
最佳适应算法，是内存空间动态分配算法中的一种，选择大小最接近的一块空闲块分配给进程
基本分段式存储管理的地址转换练习
静态重定位
要注意起始块号是否从0开始，不同起始块号会得到不同答案
**
实际上就是问哪种内存分配策略能为用户分配更多的可用的物理地址。起始就只有页表和段表占用的地址不能被用户使用，而我们无法确定页表和段表那个大，所以无法确定
系统中所有程序共用一个重定位寄存器
段式存储，一个程序如何分段在用户变成决定
页式存储，一个程序如何分页由操作系统在装入作业的时候决定
相对地址=逻辑地址–>相对于本身的起始位置来说，地址是多少
绝对地址=物理地址=实地址–>相对于物理内存的起始地址来说，的地址
分区存储，由于内存是连续分配，只需要一个重定位寄存器和界地址寄存器就可以访问进程空间。
分页式，分段式的代价就高很多，由于内存不连续分配，所以需要页表，段表寄存器以及多许多的判断
交换技术，实现虚拟内存
1 | 所谓一维地址结构，指的是只需要提供一个参数(地址总位数)，就可以知道其在内存中存放的块号，及页内偏移量。 |
1 | 1个进程对应1张页表。页表必须常驻内存，不能调入调出，因为页表调入调出，起始位置会发生改变，PCB里存储的页表起始地址就会寻找一个错误的地址 |
1 | 分页存储管理方式，对于程序员来说，地址空间是一维的，页面大小确定不能被用户更改，所以分页是管理物理存储空间的方法。 |
多级页表，并没有增加所表示的页表项，只是将单个过长的页表划分为好几个更小的页表
编译、链接、装载分别的作用
当多个进程共享一段代码时，内存中就没必要存多段相同代码，所以有共享段表，每一条段表项都是可变的，记录着同时共享该段代码的进程
虚拟内存管理
虚拟存储器的最大容量是理论上可以达到的极限容量，受限于寻址范围。
实际虚拟存储容量则是内存+外存总容量
页面失效包括所有缺页的次数
页面淘汰，只包括淘汰页面的次数
磁盘交换空间的磁盘利用率很高，说明与主存之间频繁的换入换出，说明内存已满，这种情况，可以增加内存条容量来提高系统性能
系统调用是由用户进程发起的，请求操作系统的服务。对于A,当内存中的空闲页框不够时，操作系统会将某些页面调出，并将要访问的页面调入，这个过程完全由操作系统完成，不涉及系统调用。对于B,进程调度完全由操作系统完成，无法通过系统调用完成。对于C,创建新进程可以通过系统调用来完成，如Liux中通过fork系统调用来创建子进程。对于D,生成随机数只需要普通的函数调用，不涉及请求操作系统的服务，如C语言中random（）函数。
覆盖技术和虚拟存储技术有何本质不同？
注意：调页之后，会更新快表中的内容，所以调页后可以在快表直接命中
最佳置换算法，往后找到末端几个页面时，由于后面没有更多的页面用来预测，所以淘汰算法转变为先进先出原则
行优先存储，指的是每行数据连续存放
文件管理
初识文件管理
内存的逻辑地址与外存的逻辑地址区别
- 内存的逻辑地址是CPU通过段基址寄存器和偏移地址计算得到的,用于访问内存。外存的逻辑地址是文件系统生成的,用于定位文件在外存上的位置。
- 内存的逻辑地址需要映射为物理地址才能真正访问内存。外存的逻辑地址可以直接对应到外存的物理位置。
- 内存的逻辑地址用于程序代码和数据。外存的逻辑地址对应于文件系统的文件及目录。
- 内存的逻辑地址由内存管理单元(MMU)映射。外存的逻辑地址由文件系统解析。
- 内存的逻辑地址对程序是透明的。外存的逻辑地址可以为用户程序所见。
- 内存的逻辑地址空间连续统一。外存的逻辑地址分散不连续。
- 内存的逻辑地址方便程序编址。外存的逻辑地址方便文件查找。
- 内存的逻辑地址范围由操作系统管理。外存的逻辑地址用户可更改。
总之,两者是不同的地址体系,内存逻辑地址由CPU产生,外存逻辑地址由文件系统管理,用途和转换机制不同。但都提供了更简单的地址抽象。
文件的逻辑结构
文件结构的分类
按文件是否有结构分类，可以分为无结构文件、有结构文件两种。
- 无结构文件：文件内部的数据就是一系列二进制流或字符流组成。又称“流式文件”。如：Windows 操作系统中的 .txt 文件。
- 有结构文件：由一组相似的记录组成，又称“记录式文件”。每条记录又若干个数据项组成。如：数据库表文件。一般来说，每条记录有一个数据项可作为关键字。根据各条记录的长度（占用的存储空间）是否相等，又可分为定长记录和可变长记录两种。下边图示的表格就是一个定长记录的有结构文件
有结构文件
由一组相似的记录组成，又称“记录式文件”。每条记录又若干个数据项组成。如：
数据库表文件。一般来说，每条记录有一个数据项可作为关键字。根据各条记录的长度（占用的存储空间）是否相等，又可分为定长记录和可变长记录两种。
有结构文件按各条记录长度是否相等分为定长和不定长记录两种
1.定长记录的有结构文件
这个有结构文件由定长记录组成，每条记录的长度都相同（共 128 B）。各数据项都处在
记录中相同的位置，具有相同的顺序和长度（前32B一定是学号，之后32B一定是姓名……）
2.不定长记录的有结构文件
这个有结构文件由可变长记录组成，由于各个学生的特长存在很大区别，因此“特长”这个数据项的长度不确定，这就导致了各条记录的长度也不确定。当然，没有特长的学生甚至可以去掉“特长”数据项
有结构文件的逻辑结构
顺序文件
顺序文件：文件中的记录一个接一个地顺序排列（逻辑上），记录可以是定长的或可变长的。各个记录在物理上可以顺序存储或链式存储。
为什么变长记录的顺序存储无法实现随机存取，而定长记录的顺序存储可以？
对于不定长记录的顺序存储，由于记录长度不等，寻找第i个记录时，就需要从前往后依次将前i-1个记录长度相加，得到第i个记录的长度所在的位置。
但是对于定长记录的顺序存储，由于记录长度相等，寻找第i个记录时，只需要，字段长度 L * i ,瞬间得到第i个字段的长度位置。
一般来说，考试题目中所说的“顺序文件”指的是物理上顺序存储的顺序文件。之后的讲解中提到的顺序文件也默认如此。可见，顺序文件的缺点是增加/删除一个记录比较困难（如果是串结构则相对简单）
对于可变长记录文件，要找到第 i 个记录，必须先顺序第查找前 i-1 个记录，但是很多应用场景中又必须使用可变长记录。如何解决这个问题？这就需要索引文件
索引文件
索引表本身是定长记录的顺序文件。因此可以快速找到第 i 个记录对应的索引项。可将关键字作为索引号内容，若按关键字顺序排列，则还可以支持按照关键字折半查找。每当要增加/删除一个记录时，需要对索引表进行修改。由于索引文件有很快的检索速度，因此主要用于对信息处理的及时性要求比较高的场合。
思考索引文件的缺点：每个记录对应一个索引表项，因此索引表可能会很大。比如：文件的每个记录平均只占 8B，而每个索引表项占32个字节，那么索引表都要比文件内容本身大4倍，这样对存储空间的利用率就太低了。这就需要索引顺序文件
索引顺序文件
索引顺序文件是索引文件和顺序文件思想的结合。索引顺序文件中，同样会为文件建立
一张索引表，但不同的是：并不是每个记录对应一个索引表项，而是一组记录对应一个
索引表项。
用这种策略确实可以让索引表“瘦身”，但是能否解决不定长记录的顺序文件检索速度慢的问题呢？
为了进一步提高检索效率，可以为顺序文件建立多级索引表。
多级索引表
例如，对于一个含 10 6 个记录的文件，可先为该文件建立一张低级索引表，每 100 个记录为一组，故低级索引表中共有 10000 个表项（即10000个定长记录），再把这 10000 个定长记录分组，每组100个，为其建立顶级索引表，故顶级索引表中共有 100 个表
文件目录
文件目录就是我们很熟悉的Windows操作系统的文件夹
文件控制块(FCB)
.目录本身就是一种有结构文件，由一条条记录组成。每条记录对应一个在该放在该目录下的文件.
目录文件中的一条记录就是一个“文件控制块（FCB)“
FCB 的有序集合称为“文件目录”，一个FCB就是一个文件目录项。FCB 中包含了文件的基本信息（文件名、物理地址、逻辑结构、物理结构等），存取控制信息（是否可读/可写、禁止访问的用户名单等），使用信息（如文件的建立时间、修改时间等）。最重要，最基本的还是 文件名、文件存放的物理地址。FCB 实现了文件名和文件之间的映射。使用户（用户程序）可以实现“按名存取”。
注意区分：目录vs文件目录vs目录文件
①目录=文件目录
②目录文件是对目录进行描述的文件，是存放在外存中的数据
③“目录”可以理解为windows系统中的一个文件夹，而“目录文件”是描述这个文件夹中内容的文件
需要对目录进行哪些操作？
搜索：当用户要使用一个文件时，系统要根据文件名搜索目录，找到该文件对应的目录项
创建文件：创建一个新文件时，需要在其所属的目录中增加一个目录项
删除文件：当删除一个文件时，需要在目录中删除相应的目录项
显示目录：用户可以请求显示目录的内容，如显示该目录中的所有文件及相应属性
修改目录：某些文件属性保存在目录中，因此这些属性变化时需要修改相应的目录项（如：文件重命名）
目录结构
单级目录结构
早期操作系统并不支持多级目录，整个系统中只建立一张目录表，每个文件占一个目录项。
单级目录实现了“按名存取”，但是不允许文件重名。
在创建一个文件时，需要先检查目录表中有没有重名文件，确定不重名后才能允许建立文件，并将新文件对应的目录项插入目录表中
显然，单级目录结构不适用于多用户操作系统。
两级目录结构
早期的多用户操作系统，采用两级目录结构。分为主文件目录（MFD，Master File Directory）和用户文件目录（UFD，User Flie Directory）。
允许不同用户的文件重名。文件名虽然相同，但是对应的其实是不同的文件
两级目录结构允许不同用户的文件重名，也可以在目录上实现实现访问限制（检查此时登录的用户名是否匹配）。
但是两级目录结构依然缺乏灵活性，用户不能对自己的文件进行分类，所以提出了多级目录结构
多级目录结构
又称树形目录结构
用户（或用户进程）要访问某个文件时要用文件路径名标识文件，文件路径名是个字符串。各级目录之间用“/”隔开。从根目录出发的路径称为绝对路径。例如：自拍.jpg 的绝对路径是 “/照片/2015-08/自拍.jpg”
每次都从根目录开始查找，是很低效的。因此可以设置一个“当前目录”。例如，此时已经打开了“照片”的目录文件，也就是说，这张目录表已调入内存，那么可以把它设置为“当前目录”。当用户想要访问某个文件时，可以使用从当前目录出发的“相对路径” 。在 Linux 中，“.”表示当前目录，因此如果“照片”是当前目录，则”自拍.jpg”的相对路径为：
“./2015-08/自拍.jpg”。
.树形目录结构可以很方便地对文件进行分类，层次结构清晰，也能够更有效地进行文件的管理和保护。但是，树形结构不便于实现文件的共享。为此，提出了“无环图目录结构”
无环图目录结构
可以用不同的文件名指向同一个文件，甚至可以指向同一个目录（共享同一目录下的所有内容）。
需要为每个共享结点设置一个共享计数器，用于记录此时有多少个地方在共享该结点。用户提出删除结
点的请求时，只是删除该用户的FCB、并使共享计数器减1，并不会直接删除共享结点。
只有共享计数器减为0时，才删除结点。
注意：共享文件不同于复制文件。在共享文件中，由于各用户指向的是同一个文件，因此只要其中一个用户修改了文件数据，那么所有用户都可以看到文件数据的变化。
索引结点(FCB的改进)
思考有何好处？
假设一个FCB是64B，磁盘块的大小为1KB，则每个盘块中只能存放16个FCB。若一个文件目录中共有640个目录项，则共需要占用640/16 = 40 个盘块。因此按照某文件名检索该目录，平均需要查询320 个目录项，平均需要启动磁盘20次（每次磁盘I/O读入一块）。
若使用索引结点机制，文件名占14B，索引结点指针站2B，则每个盘块可存放64个目录项，那么按文件名检索目录平均只需要读入 320/64 = 5 个磁盘块。显然，这将大大提升文件检索速度。
当找到文件名对应的目录项时，才需要将索引结点调入内存，索引结点中记录了文件的各种信息，包括文件在外存中的存放位置，根据“存放位置”即可找到文件。存放在外存中的索引结点称为“磁盘索引结点”，当索引结点放入内存后称为“内存索引结点”。相比之下内存索引结点中需要增加一些信息，比如：文件是否被修改、此时有几个进程正在访问该文件等。
无论采用连续分配还是索引分配，文件系统都需要利用索引节点来组织和管理文件。连续分配文件主要通过索引节点中的起始块号确定文件位置。索引分配文件在索引节点中放置索引号(索引表存放的块号)。
小结
文件的物理结构（分配方式）
首先了解文件块与磁盘块
在内存管理中，进程的逻辑地址空间被分为一个一个页面，同样的在外存管理中，为了方便对文件数据的管理，文件的逻辑地址空间也被分为了一个一个的文件“块”。于是文件的逻辑地址也可以表示为（逻辑块号，块内地址）的形式。
连续分配
连续分配方式要求每个文件在磁盘上占有一组连续的块
连续分配的优点有哪些？
磁盘分为很多的扇形块，读取一个块时，需要移动读写头，到对应的扇区，而连续分配方式，使得文件数据存放的扇区相邻，读取某个磁盘块时，需要移动磁头。访问的两个磁盘块相隔越远，移动磁头所需时间就越长。
所以，连续分配的文件在顺序读/写时速度最快
用户给出要访问的逻辑块号，操作系统找到该文件对应的目录项（FCB）…
.物理块号 = 起始块号 + 逻辑块号
当然，还需要检查用户提供的逻辑块号是否合法（逻辑块号 ≥ 长度 就不合法）
可以直接算出逻辑块号对应的物理块号，因此连续分配支持顺序访问和直接访问（即随机访问）
连续分配的缺点有哪些？
.不方便文件拓展；存储空间利用率低，会产生磁盘碎片
链接分配
链接分配采取离散分配的方式，可以为文件分配离散的磁盘块。分为隐式链接和显式链接两种。
1.隐式链接
目录中记录了文件存放的起始块号和结束块号。当然，也可以增加一个字段来表示文件的长度
除了文件的最后一个磁盘块之外，每个磁盘块中都会保存指向下一个盘块的指针，这些指针对用户是透明的
隐式链接又是如何实现文件逻辑块号到物理块号的转变的？
用户给出要访问的逻辑块号 i，操作系统找到该文件对应的目录项（FCB）…
从目录项中找到起始块号（即0号块），将0号逻辑块读入内存，由此知道1号逻辑块存
放的物理块号，于是读入1号逻辑块，再找到2号逻辑块的存放位置……以此类推。
因此，读入i号逻辑块，总共需要 i+1 次磁盘I/O。
结论：采用链式分配（隐式链接）方式的文件，只支持顺序访问，不支持随机访问，查
找效率低。另外，指向下一个盘块的指针也需要耗费少量的存储空间。
隐式链接是否方便拓展文件呢？
若此时要拓展文件，则可以随便找一个空闲磁盘块，挂到文件的磁盘块链尾，并修改文件的FCB
结论：采用隐式链接的链接分配方式，很方便文件拓展。另外，所有的空闲磁盘块都可以被利用，不会有碎片问题，外存利用率高
2.显示连接
把用于链接文件各物理块的指针显式地存放在一张表中。即 文件分配表（FAT，File Allocation Table）
假设某个新创建的文件“aaa”依次存放在磁盘块 2 ->5 ->0 ->1
假设某个新创建的文件“bbb”依次存放在磁盘块 4 ->23 ->3
注意：一个磁盘仅设置一张FAT。开机时，将FAT读入内存，并常驻内存。 FAT 的各个表项在物理上连续存储，且每一个表项长度相同，因此“物理块号”字段可以是隐含的
显示链接是如何实现文件的逻辑块号到物理块号的转变的？
用户给出要访问的逻辑块号 i，操作系统找到该文件对应的目录项（FCB）…
从目录项中找到起始块号，若i>0，则查询内存中的文件分配表FAT，往后找到 i 号逻辑块对应的物理块号。逻辑块号转换成物理块号的过程不需要读磁盘操作。
结论：采用链式分配（显式链接）方式的文件，支持顺序访问，也支持随机访问（想访问 i 号逻辑块时，并不需要依次访问之前的 0 ~ i-1号逻辑块），由于块号转换的过程不需要访问磁盘，因此相比于隐式链接来说，访问速度快很多。
显然，显式链接也不会产生外部碎片，也可以很方便地对文件进行拓展。
注意：考试题目中遇到未指明隐式/显式的“链接分配”，默认指的是隐式链接的链接分配
显示链接需要借助文件分配表，但是文件分配表也需要占用一定的内存，显然当外存中文件内容很多时，文件分配表就会很大大，有没有办法解决呢？引出了索引分配
索引分配
.索引分配允许文件离散地分配在各个磁盘块中，系统会为每个文件建立一张索引表，索引表中记录了文件的各个逻辑块对应的物理块（索引表的功能类似于内存管理中的页表——建立逻辑页面到物理页之间的映射关系）。索引表存放的磁盘块称为索引块。文件数据存放的磁盘块称为数据块。
假设某个新创建的文件“aaa”的数据依次存放在磁盘块 2 ->5 ->13 ->9 。7号磁盘块作为“aaa”的索引块，索引块中保存了索引表的内容。
注：在显式链接的链式分配方式中，文件分配表FAT 是一个磁盘对应一张。而索引分配方式中，索引表是一个文件对应一张
可以用固定的长度表示物理块号（如：假设磁盘总容量为1TB=2 40 B，磁盘块大小为1KB，则共有 2 30 个磁盘块，则可用4B 表示磁盘块号），因此，索引表中的“逻辑块号”可以是隐含的。
如何实现文件逻辑块号到物理块号的转换？
用户给出要访问的逻辑块号 i，操作系统找到该文件对应的目录项（FCB）…从目录项中可知索引表存放位置，将索引表从外存读入内存，并查找索引表即可只 i 号逻辑块在外存中的存放位置。
.可见，索引分配方式可以支持随机访问。文件拓展也很容易实现（只需要给文件分配
一个空闲块，并增加一个索引表项即可）但是索引表需要占用一定的存储空间
若每个磁盘块1KB，一个索引表项4B，则一个磁盘块只能存放 256 个索引项。如果一个文件的大小超过了256块，那么一个磁盘块是装不下文件的整张索引表的，如何解决这个问题？
①链接方案
②多层索引
③混合索引
1.链接方案
①链接方案：如果索引表太大，一个索引块装不下，那么可以将多个索引块链接起来存放。
假设磁盘块大小为1KB，一个索引表项占4B，则一个磁盘块只能存放256个索引项。若一个文件大小为 256 * 256KB =65,536 KB = 64MB该文件共有 256 * 256 个块，也就对应256 * 256个索引项，也就需要 256 个索引块来存储，这些索引块用链接方案连起来。若想要访问文件的最后一个逻辑块，就必须找到最后一个索引块（第256个索引块），而各个索引块之间是用指针链接起来的，因此必须先顺序地读入前 255 个索引块。
这显然是很低效的。如何解决呢？
2.多层索引
②多层索引：建立多层索引（原理类似于多级页表）。使第一层索引块指向第二层的索引块。还可根据文件大小的要求再建立第三层、第四层索引块。
假设磁盘块大小为1KB，一个索引表项占4B，则一个磁盘块只能存放256 个索引项。若某文件采用两层索引，则该文件的最大长度可以到2562561KB = 65,536 KB = 64MB可根据逻辑块号算出应该查找索引表中的哪个表项。
如：要访问 1026 号逻辑块，则1026/256 = 4，1026%256 = 2因此可以先将一级索引表调入内存，查询 4 号表项，将其对应的二级索引表调入内存，再查询二级索引表的2号表项即可知道 1026 号逻辑块存放的磁盘块号了。访问目标数据块，需要3次磁盘I/O。
注意：
1.采用 K 层索引结构，且顶级索引表未调入内存，则访问一个数据块只需要 K + 1 次
读磁盘操作
2.若采用多层索引，则各层索引表大小不能超过一个磁盘块
3.混合索引
③混合索引：多种索引分配方式的结合。例如，一个文件的顶级索引表中，既包含直接地址索引（直接指向数据块），又包含一级间接索引（指向单层索引表）、还包含两级间接索引（指向两层索引表） 。
对于小文件，只需较少的读磁盘次数就可以访问目标数据块。（一般计算机中小文件更多）
小结
逻辑结构vs物理结构
逻辑结构和物理结构上，名词概念比较模糊，没有比较清晰的界定。通常顺序文件，索引文件，即可表示文件的逻辑结构，也可以表示文件块的物理存放结构。平时需要注意区分题目要求的到底是哪种
文件存储空间管理
文件的物理结构探讨的是对非空闲磁盘块的管理
.文件存储空间的管理探讨的是对空闲磁盘块的管理
存储空间的划分与初始化
安装 Windows 操作系统的时候，一个必经步骤是——为磁盘分区（C: 盘、D: 盘、E: 盘等）存储空间的划分：就是将物理磁盘划分为一个个文件卷（逻辑卷、逻辑盘）
.存储空间的初始化：将各个文件卷划分为目录区、文件区
目录区主要存放文件目录信息（FCB）、用于磁盘存储空间管理的信息。
文件区用于存放文件数据
存储空间管理方法
空闲表法
空闲表法适用于怎样的分配方式？
适用于 “连续分配方式”
空闲表法如何分配空闲磁盘块给文件使用呢？
与内存管理中的动态分区分配很类似，为一个文件分配连续的存储空间。同样可采用首次适应、最佳适应、最坏适应等算法来决定要为文件分配哪个区间。
空闲表法又是如何回收磁盘块呢？
与内存管理中的动态分区分配很类似，当回收某个存储区时需要有四种情况——①回收区的前后都没有相邻空闲区；②回收区的前后都是空闲区；③回收区前面是空闲区；④回收区后面是空闲区。总之，回收时需要注意表项的合并问题。
空闲链表法
空闲链表法有可以链结点单位不同分为空闲盘区链、空闲盘块链
1.空闲盘块链
.适用于离散分配的物理结构。为文件分配多个盘块时可能要重复多次操作
操作系统保存着链头、链尾指针。
如何分配?
若某文件申请 K 个盘块，则从链头开始依次摘下 K 个盘块分配，并修改空闲链的链头指针。
如何回收？
回收的盘块依次挂到链尾，并修改空闲链的链尾指针
2.空闲盘区链
.离散分配、连续分配都适用。为一个文件分配多个盘块时效率更高
操作系统保存着链头、链尾指针。
如何分配?
若某文件申请 K 个盘块，则可以采用首次适应、最佳适应等算法，从链头开始检索，按照算法规则找到一个大小符合要求的空闲盘区，分配给文件。若没有合适的连续空闲块，也可以将不同盘区的盘块同时分配给一个文件，注意分配后可能要修改相应的链指针、盘区大小等数据。
如何回收？
若回收区和某个空闲盘区相邻，则需要将回收区合并到空闲盘区中。若回收区没有和任何空闲区相邻，将回收区作为单独的一个空闲盘区挂到链尾。
位示图法
每个二进制位对应一个盘块。在本例中，“0”代表盘块空闲，“1”代表盘块已分配。位示图一般用连续的“字”来表示，如本例中一个字的字长是16位，字中的每一位对应一个盘块。因此可以用（字号，位号）对应一个盘块号。当然有的题目中也描述为（行号，列号）
如本例中盘块号、字号、位号从0开始，若n表示字长，则…
(字号, 位号)=(i, j) 的二进制位对应的 盘块号 b = ni + j
b号盘块对应的字号 i = b/n，位号 j = b%n
如何分配?
若文件需要K个块，①顺序扫描位示图，找到K个相邻或不相邻的“0”；②根据字号、位号算出对应的盘块号，将相应盘块分配给文件；③将相应位设置为“1”。
如何回收?
①根据回收的盘块号计算出对应的字号、位号；②将相应二进制位设为“0”
成组链接法
.空闲表法、空闲链表法不适用于大型文件系统，因为空闲表或空闲链表可能过大过长。UNIX系统中采用了成组链接法对磁盘空闲块进行管理。它克服了空闲链表法表太长的缺点，但是保持了其优点，即分配和回收一个盘块比较简单。
文件卷的目录区中专门用一个磁盘块作为“超级块”，当系统启动时需要将超级块读入内存。并且要保证内存与外存中的“超级块”数据一致.
这张图我得好好解释一下，首先来看左边绿色的空闲盘块号栈，这是第一组(唯一进入内存的一组，只有它会占据存储空间)。看到S.free = 100了没，这表示该组有100个空闲块数目，再往下看，第0号对应的是300，表示下一组物理空闲块的物理盘块号为300，你看它指向的是不是300号对应的磁盘块。再看黄色的块，这些块里保存的才是真正的可用的空闲块，也就是说每组中只有99个块可用。尽管如此，每组还是有100个块的。特别要注意的是，最后一组的下一组盘块号不是没有么，我们这里采用的是结束标记“0”，也就是最右边一个蓝色块的第二项为0。
如何分配？
记住一点的是，分配过程是从前往后分配，先分配第一组，然后分配第二组……
Eg ：需要100个空闲块
①检查第一个分组的块数是否足够。100=100，是足够的。
②分配第一个分组中的100个空闲块。但是由于300号块内存放了再下一组的信息，因此300号块的数据需要复制到超级块中
如何回收？
回收过程是正好相反，从后往前分配，先将释放的空闲块放入第一组，第一组满了，再开辟一组，之前的第一组变为第二组……
Eg ：假设每个分组最多为100个空闲块，此时第一个分组已有100个块，还要再回收一块。需要将超级块中的数据复制到新回收的块中，并修改超级块的内容，让新回收的块成为第一个分组。
文件的基本操作
创建文件
进行 Create 系统调用时，需要提供的几个主要参数：
- 所需的外存空间大小（如：一个盘块，即1KB）
- 文件存放路径（“D:/Demo”）
- 文件名（这个地方默认为“新建文本文档.txt”）
操作系统在处理 Create 系统调用时，主要做了两件事：
- 在外存中找到文件所需的空间（结合上小节学习的空闲链表法、位示图、成组链接法等管理策略，找到空闲空间）
- 根据文件存放路径的信息找到该目录对应的目录文件（此处就是 D:/Demo 目录），在目录中创建该文件对应的目录项。目录项中包含了文件名、文件在外存中的存放位置等信息。
删除文件
进行 Delete 系统调用时，需要提供的几个主要参数：
- 文件存放路径（“D:/Demo”）
- 文件名（“test.txt”）
操作系统在处理 Delete 系统调用时，主要做了几件事：
- 根据文件存放路径找到相应的目录文件，从目录中找到文件名对应的目录项。
- 根据该目录项记录的文件在外存的存放位置、文件大小等信息，回收文件占用的磁盘块。（回收磁盘块时，根据空闲表法、空闲链表法、位图法等管理策略的不同，需要做不同的处理）。
- 从目录表中删除文件对应的目录项。
打开文件
在很多操作系统中，在对文件进行操作之前，要求用户先使用 open 系统调用“打开文件”，需要提供的几个主要参数：
- 文件存放路径（“D:/Demo”）
- 文件名（“test.txt”）
- 要对文件的操作类型（如：r 只读；rw 读写等）
操作系统在处理 open 系统调用时，主要做了几件事：
- 根据文件存放路径在外存中找到相应的
目录文件，从目录中找到文件名对应的的目录项(FCB)，并检查该用户是否有指定的操作权限。 - 将
目录项(FCB)复制到内存中的“系统打开文件表”中。并将对应表目的编号k返回给用户进程的打开文件表。之后用户使用进程的打开文件表的编号2(文件描述符)来指明要操作的文件。
关闭文件
进程使用完文件后，要“关闭文件”操作系统在处理 Close 系统调用时，主要做了几件事：
- 将进程的打开文件表相应表项删除
- 回收分配给该文件的内存空间等资源
- 系统打开文件表的打开计数器count 减1，若 count =0，则删除对应表项
读文件
可以“读文件”，将文件数据读入内存，才能让CPU处理（双击后，“记事本”应用程序通过操作系统提供的“读文件”功能，即 read 系统调用，将文件数据从外存读入内存，并显示在屏幕上）
进程使用 read系统调用完成写操作。
- 需要指明是哪个文件（在支持“打开文件”操作的系统中，只需要提供文件在打开文件表中的
索引号即可）， - 还需要指明要读入多少数据（如：读入 1KB）、指明读入的数据要放在内存中的什么位置。
- 操作系统在处理 read 系统调用时，会从读指针指向的外存中，将用户指定大小的数据读入用户指定的内存区域中。
写文件
进程使用 write 系统调用完成写操作，
- 需要指明是哪个文件（在支持“打开文件”操作的系统中，只需要提供文件在打开文件表中的
索引号即可） - 还需要指明要写出多少数据（如：写出 1KB）、写回外存的数据放在内存中的什么位置
- 操作系统在处理 write 系统调用时，会从用户指定的内存区域中，将指定大小的数据写回写指针指向的外存。
小结
文件共享
文件共享的含义
注意：多个用户共享同一个文件，意味着系统中只有“一份”文件数据。并且只要某个用户修改了该文件的数据，其他用户也可以看到文件数据的变化。
如果是多个用户都“复制”了同一个文件，那么系统中会有“好几份”文件数据。其中一个用
户修改了自己的那份文件数据，对其他用户的文件数据并没有影响。
基于索引结点的共享方式(硬连接)
索引结点是什么？前面讲过，先回顾一下
索引结点，是一种文件目录瘦身策略。由于检索文件时只需用到文件名，因此可以将除
了文件名之外的其他信息放到索引结点中。这样目录项就只需要包含文件名、索引结点指针。
那要如何通过索引结点来实现文件的共享呢？
索引结点中设置一个链接计数变量 count，用于表示链接到本索引结点上的用户目录项数。
- 若 count = 2，说明此时有两个用户目录项链接到该索引结点上，或者说是有两个用户在共享此文件。
- 若某个用户决定“删除”该文件，则只是要把用户目录中与该文件对应的目录项删除，且索引结点的count值减 1。
- 若 count>0，说明还有别的用户要使用该文件，暂时不能把文件数据删除，否则会导致指针悬空。
- 当 count = 0 时系统负责删除文件。
基于符号链的共享方式(软连接)
硬链接不是也借助了索引结点吗？他与硬链接有什么区别吗
区别在于，硬链接是直接将不同用户目录的目录项的索引结点指针指向同一个索引结点，从而共同指向一个文件；
但是软连接，是将目录中目录项的索引结点指针指向link文件(Link类型文件记录了存放文件1的存放路径，类似于Windows操作系统的快捷方式)，再通过Link文件层层查找找到User1的目录表中，aaa的表项，于是就找到了文件1的索引结点
小结
文件保护
口令保护
为文件设置一个“口令”（如：abc112233），用户请求访问该文件时必须提供“口令”。
口令一般存放在文件对应的 FCB 或索引结点中。用户访问文件前需要先输入“口令”，操作系统会将用户提供的口令与FCB中存储的口令进行对比，如果正确，则允许该用户访问文件
- 优点：保存口令的空间开销不多，验证口令的时间开销也很小。
- 缺点：正确的“口令”存放在系统内部，不够安全。
加密保护
使用某个“密码”对文件进行加密，在访问文件时需要提供正确的“密码”才能对文件进行正确的解密。
Eg：一个最简单的加密算法——异或加密假设用于加密/解密的“密码”为“01001”
- 优点：保密性强，不需要在系统中存储“密码”
- 缺点：编码/译码，或者说加密/解密要花费一定时间
访问控制
在每个文件的FCB（或索引结点）中增加一个访问控制列表（Access-ControlList,ACL)，该表中记录了各个用户可以对该文件执行哪些操作。
有的计算机可能会有很多个用户，因此访问控制列表可能会很大，可以用精简的访问列表解决这个问题
精简的访问列表：以“组”为单位，标记各“组”用户可以对文件执行哪些操作。
如：分为 系统管理员、文件主、文件主的伙伴、其他用户 几个
分组。
当某用户想要访问文件时，系统会检查该用户所属的分组是否有相应的访问权限。
小结
文件系统的层次
用一个例子来辅助记忆文件系统的层次结构：
假设某用户请求删除文件 “D:/工作目录/学生信息.xlsx” 的最后100条记录。
- 用户需要通过操作系统提供的接口发出上述请求——用户接口
- 由于用户提供的是文件的存放路径，因此需要操作系统一层一层地查找目录，找到对应的目录项——文件目录系统
- 不同的用户对文件有不同的操作权限，因此为了保证安全，需要检查用户是否有访问权限——存取控制模块（存取控制验证层）
- 验证了用户的访问权限之后，需要把用户提供的“记录号”转变为对应的逻辑地址——逻辑文件系统与文件信息缓冲区
- 知道了目标记录对应的逻辑地址后，还需要转换成实际的物理地址——物理文件系统
- 要删除这条记录，必定要对磁盘设备发出请求——设备管理程序模块
- 删除这些记录后，会有一些盘块空闲，因此要将这些空闲盘块回收——辅助分配模块
文件系统的全局结构
文件系统在外存中的结构
磁盘的初始化
1.原始磁盘
2.物理格式化
物理格式化，即低级格式化——划分扇区，检测坏扇区，并用备用扇区替换坏扇区
产生如奇偶校验、CRC 循环冗余校验码等，校验码用于校验扇区中的数据是否发生错
误
3.磁盘分区
创建磁盘分区表
4.逻辑格式化
磁盘分区（分卷 Volume）后，对各分区进行逻辑格式化
逻辑格式化后，灰色部分就有实际数据了，白色部分还没有数据
需要在每个分区初始化一个特定的文件系统，并创建文件系统的根目录。如果某个分区采用 Unix 文件系统 (U F S ), 则还要在该分区中建立文件系统的索引结点表
了解了文件系统在外存中的结构，接下来了解文件系统在内存当中的结构
文件系统在内存中的结构
文件系统在内存中的结构分为三个部分：
- 目录缓存
- 系统打开文件表
- 进程打开文件表
1.目录的缓存
查找目录需要将外存中目录M中的FCB都读入主存，所以为了避免每次查找目录都需要访问外存，所以近期访问过的目录文件会缓存在内存中，不用每次都从磁盘读入，这样可以加快目录检索速。
2.系统打开文件表
系统打开文件表是内核维护的一个数据结构，它记录了所有打开文件的信息，包括文件描述符、文件状态标志、文件偏移量、文件结构体指针等。当一个文件被打开时，系统会在系统打开文件表中为该文件分配一个对应的条目，以便内核对该文件进行管理和跟踪。
3.用户打开文件表
用户打开文件时，会在进程打开文件表中增加一个条目，记录文件打开方式，需要注意的是进程打开文件表中不会保存文件的FCB，而是保存系统打开文件表中的索引，通过系统打开文件表找到打开文件的FCB
虚拟文件系统
普通的文件系统是如何的？
普通的文件系统，外存文件如果使用的不同系统，那么对文件的访问使用的方法以及参数各不相同，用户进程就需要使用不同的方法以及参数才能访问文件，这样是十分不方便的，有没有方法使得接口统一呢？
虚拟文件系统？它有什么作用？
虚拟文件系统（Virtual File System，简称VFS）是Linux内核的子系统之一，它为用户程序提供文件和文件系统操作的统一接口，屏蔽不同文件系统的差异和操作细节。借助VFS可以直接使用open()、read()、write()这样的系统调用操作文件，而无须考虑具体的文件系统和实际的存储介质。
举个例子，Linux用户程序可以通过read() 来读取ext3、NFS、XFS等文件系统的文件，也可以读取存储在SSD、HDD等不同存储介质的文件，无须考虑不同文件系统或者不同存储介质的差异。
通过VFS系统，Linux提供了通用的系统调用，可以跨越不同文件系统和介质之间执行，极大简化了用户访问不同文件系统的过程。另一方面，新的文件系统、新类型的存储介质，可以无须编译的情况下，动态加载到Linux中。
存在的问题：不同的文件系统，表示文件数据结构各不相同。打开文件后，其在内存中的表示就不同，VFS是如何解决的呢？
VFS每打开一个文件，VFS就在主存中新建一个 vnode，用统一的数据结构表示文件，无论该文件存储在哪个文件系统。
注意：vnode 只存在于主存中，而 inode(索引结点) 既会被调入主存，也会在外存中存储
打开文件后，创建vnode，并将文件信息复制到vnode中，vnode的功能指针指向具体文
件系统的函数功能。
文件系统挂载
文件系统挂载（mounting），即文件系统安装/装载——如何将一个文件系统挂载到操作系统中？
文件系统挂载要做的事：
①在VFS中注册新挂载的文件系统。内存中的挂载表（mount table）包含每个文件系统的相关信息，包括文件系统类型、容量大小等。
②新挂载的文件系统，要向VFS提供一个函数地址列表。
③将新文件系统加到挂载点（mountpoint），也就是将新文件系统挂载在某个父目录下。
磁盘的结构
详见组成原理
磁盘调度算法
一次磁盘读/写操作需要的时间
1 | 寻找时间（寻道时间）T S ：在读/写数据前，将磁头移动到指定磁道所花的时间。 |
先来向服务算法（FCFS）
1 | 根据进程请求访问磁盘的先后顺序进行调度。 |
最短寻找时间优先（SSTF）
1 | 描述：SSTF 算法会优先处理的磁道是与当前磁头最近的磁道。可以保证每次的寻道时间最短，但是并不能保证总的寻道时间最短。（其实就是贪心算法的思想，只是选择眼前最优，但是总体未必最优） |
扫描算法（SCAN）
1 | 描述：SSTF 算法会产生饥饿的原因在于：磁头有可能在一个小区域内来回来去地移动。为了防止这个问题，可以规定，只有磁头移动到最外侧磁道的时候才能往内移动，移动到最内侧磁道的时候才能往外移动。这就是扫描算法（SCAN）的思想。由于磁头移动的方式很像电梯，因此也叫电梯算法。 |
LOOK调度算法
1 | 描述：扫描算法（SCAN）中，只有到达最边上的磁道时才能改变磁头移动方向，事实上，处理了184号磁道的访问请求之后就不需要再往右移动磁头了。LOOK 调度算法就是为了解决这个问题，如果在磁头移动方向上已经没有别的请求，就可以立即改变磁头移动方向。（边移动边观察，因此叫 LOOK） |
循环扫描算法（C-SCAN）
1 | 描述：SCAN算法对于各个位置磁道的响应频率不平均，而 C-SCAN 算法就是为了解决这个问题。规定只有磁头朝某个特定方向移动时才处理磁道访问请求，而返回时直接快速移动至起始端而不处理任何请求。 |
C-LOOK调度算法
1 | 描述：C-SCAN 算法的主要缺点是只有到达最边上的磁道时才能改变磁头移动方向，并且磁头返回时不一定需要返回到最边缘的磁道上。C-LOOK 算法就是为了解决这个问题。如果磁头移动的方向上已经没有磁道访问请求了，就可以立即让磁头返回，并且磁头只需要返回到有磁道访问请求的位置即可。 |
小结
若题目中无特别说明，则SCAN 就是 LOOK，C-SCAN 就是C-LOOK
减少磁盘延迟时间的方法
交替编号
1 | 磁头读取一块的内容（也就是一个扇区的内容）后，需要一小段时间处理，而盘片又在不停地旋转,因此，如果2、3号扇区相邻着排列，则读完2号扇区后无法连续不断地读入3号扇区,就需要等到下一圈来到3号扇区才能够读取，所以为了空出充分的处理时间给磁头，于是就采用交替编号的策略 |
磁盘地址结构的设计
1 | 磁盘地址结构采用(柱面号，磁盘号，扇区号)，而不是采用(磁盘号，柱面号，扇区号) |
错位命名
不采用错位命名，相邻的盘面相对位置相同处扇区编号相同
注意，所有盘面都是一起连轴转的。
读取完磁盘块（000,00, 111）之后，需要短暂的时间处理，而盘面又在不停地转动，因此当（000, 01, 000）第一次划过1号盘面的磁头下方时，并不能读取数据，只能再等该扇区再次划过磁头。
错位命名，相邻的盘面相对位置相同处扇区编号不相同
由于采用错位命名法，因此读取完磁盘块（000, 00, 111）之后，还有一段时间处理，当（000, 01, 000）第一次划过1号盘面的磁头下方时，就可以直接读取数据。从而减少了延迟时间
小结
磁盘管理
磁盘初始化
1 | 磁盘初始化： |
引导块
计算机开机时需要进行一系列初始化的工作，这些初始化工作是通过执行初始化程序（自举程序）完成的。
初始化程序可以放在ROM （只读存储器）中。ROM中的数据在出厂时就写入了，并且以后不能再修改。
初始化程序程序（自举程序）放在ROM中存在什么问题？
万一需要更新自举程序，将会很不方便，因为ROM中的数据无法更改
那要怎么解决呢？
ROM中只存放很小的“自举装入程序”.完整的自举程序放在磁盘的启动块（即引导块/启动分区）上，启动块位于磁盘的固定位置。拥有启动分区的磁盘称为 启动磁盘 或系统磁盘 （C:盘）
坏块的处理
坏了、无法正常使用的扇区就是“坏块”。这属于硬件故障，操作系统是无法修复的。应该将坏块标记出来，以免错误地使用到它。
- 对于简单的磁盘，可以在逻辑格式化时（建立文件系统时）对整个磁盘进行坏块检查，标明哪些扇区是坏扇区，比如：在 FAT 表上标明。（在这种方式中，坏块对操作系统不透明）
- 对于复杂的磁盘，磁盘控制器（磁盘设备内部的一个硬件部件）会维护一个坏块链表。在磁盘出厂前进行低级格式化（物理格式化）时就将坏块链进行初始化。会保留一些“备用扇区”，用于替换坏块。这种方案称为扇区备用。且这种处理方式中，坏块对操作系统透明。
小结
固态硬盘
Practice questions
文件系统基础
注意区分逻辑结构和物理结构上的索引表
1.逻辑结构上的索引表–记录的的是一个文件内部 记录项 的索引号、记录长度、内存上的逻辑地址等信息
2.物理结构上的索引表–记录的是各个文件所对应的在磁盘上的物理地址，针对的是文件块
物理结构上的连续存储，注意不是逻辑结构
A.连续分配，支持随机存取。因为，连续分配，文件在硬盘中存储在多个连续的块内，只需要知道，该文件的起始地址+要访问的逻辑块号，就可以直接调入该块内容
B.链接分配，不支持随机存放，因为，文件内容所存放的磁盘块，是离散存放(不互相挨在一起)，所以无法计算出所需访问的物理块号。需要一张FAT 文件分配表，记录各个物理块以及对应的下一个物理块号，这样就实现了逻辑上的链接
C.索引分配，虽然文件块也是离散存放在磁盘上的，但是索引表是顺序的，顺序记录逻辑块号、以及其对应的物理块号，需要访问逻辑块号，直接计算就能查表得到物理块号
记录成组分解技术，不可跨越块存储记录，就是同一条记录必须存放在同一磁盘块中，当该块磁盘剩余空间不足存储一条记录时，选择空余，直接存放在下一块磁盘块。。这题5次读磁盘，1次写磁盘
，因为读文件之前需要打开文件，read系统调用只需要，打开文件表中对应所需要读取的文件的索引号(文件描述符)，就可以，不需要文件名称
索引结点就是用来索引整个文件的，一个文件对应一个索引结点，是在FCB 控制块上改进，以提高文件查找速度的，与文件长度无关
直接索引结构，比连续存储，多一步查索引表。而连续分配，只需要知道起始块号，就能直接计算出物理块位置。
*假如磁盘数据有1,2,3,4 。
读写操作都需要经过缓冲区，再到用户区。
- 提前读，是指，用户本来只需读0数据，同时也提前将1,2,4数据读入缓存，那么下一次访问别的数据就可以直接从缓存中快速读取
- 延迟写，是指，等待用户多写一些数据到缓存后，再一次性写入磁盘，避免了多次写操作*
用户访问权限，限制不同用户对文件的操作权限
文件属性，文件本身属性，例如pdf文件，只读不可写
1 | (1)(2) |
1 | (2)注意，物理磁盘分配时以块为单位的，一个物理块不允许存放不同文件的数据。即使当前这个块没有填满，也不会让其他文件数据紧接着放入。 |
数据块+索引块+索引结点=总占空间大小
目录
删除了文件，但是快捷方式还存在，只是指向了一个空
B.可以从当前目录开始逐级查找
D.顺序检索法找到目录项后，目录项里既可能包含物理地址，也可能是索引结点
当前目录开始的路劲–相对路劲
根目录开始的路劲–绝对路径
设置了当前工作目录–检索文件时就不需要从根目录开始，可以更快的从当前的工作目录中检索
硬链接–F3的索引结点，直接指向文件，F1删除后，文件的引用数-1
软连接–F2的索引结点，指向Link文件，再由link文件寻找文件，文件删除后，F2任然指向link文件，所以引用数不变
1 | (2) |
1 | 细节，链式存储，FCB包含的是起始块号，和结束块号 |
1 | 细节,连续存储，虽然可以实现随机访问，但那前提是知道要访问的块号是逻辑上第几块。 |
1 | 查目录，要减少磁盘存取次数一般两种方法： |
文件系统
输入输出(IO)管理
I/O设备的基本概念和分类
什么是I/O设备
“I/O” 就是 “输入/输出”（Input/Output）
I/O 设备就是可以将数据输入到计算机，或者可以接收计算机输出数据的外部设备，属于计算机中的硬件部件。
I/O设备按使用特性分类
I/O设备按传输速率分类
I/O设备按信息交换单位分类
小结
IO控制器
为什么要有I/O控制器？
1 | I/O设备由机械部件和电子部件组成 |
I/O控制器的功能
1 | 1.接收和识别CPU发出的命令 |
I/O控制器的组成
1 | 值得注意的小细节： |
内存映像 I/O v.s. 寄存器独立编址
1 | 寄存器独立编制。控制器中的寄存器使用单独的地址 |
I/O控制方式
程序直接控制方式
如下图所示，计算机从外部设备读取数据到存储器，每次读一个字的数据。对读入的每个字， CPU 需要对外设状态进行循环检查，直到确定该字已经在I/0 控制器的数据寄存器中。在程序直接控制方式中，由于CPU 的高速性和I/0设备的低速性，致使CPU 的绝大部分时间都处于等待I/0 设备完成数据I/0 的循环测试中，造成了CPU 资源的极大浪费。在该方式中， CPU 之所以要不断地测试I/0 设备的状态，就是因为在CPU 中未采用中断机构，使I/0 设备无法向CPU报告它已完成了一个字符的输入操作。
attention
【痛点】程序直接控制方式虽然简单且易于实现，但其缺点也显而易见，由于CPU 和I/0 设备只能串行工作，导致CPU 的利用率相当低。
中断驱动方式
其实后一种的方式都是对前一种的方式的一种改进（OS里面都是为了提高资源利用率和并发性等才改进的，其他也差不多），408的课程很多都可以用这样的方法学习，不要硬背，这些都不是孤立的，回答的时候体现出改进，一步一步的讲出来，条理和逻辑会比较清楚！
中断驱动方式的思想是，允许I/0 设备主动打断CPU 的运行并请求服务，从而“解放”CPU, 使得其向I/0 控制器发送读命令后可以继续做其他有用的工作。如下图所示，我们从I/0 控制器和CPU 两个角度分别来看中断驱动方式的工作过程:
①从I/0 控制器的角度来看， I/0 控制器从CPU 接收一个读命令，然后从外围设备读数据。一且数据读入该I/0 控制器的数据寄存器，便通过控制线给CPU 发出一个中断信号，表示数据已准备好，然后等待CPU 请求该数据。I/0 控制器收到CPU 发出的取数据请求后，将数据放到数据总线上，传到CPU 的寄存器中。至此，本次I/0 操作完成， I/0 控制器又可开始下一次I/0操作。
②从CPU 的角度来看， CPU 发出读命令，然后保存当前运行程序的上下文（现场，包括程序计数器及处理机寄存器），转去执行其他程序。在每个指令周期的末尾， CPU 检查中断。当有来自I/0 控制器的中断时， CPU 保存当前正在运行程序的上下文，转去执行中断处理程序以处理该中断。这时， CPU 从I/0 控制器读一个字的数据传送到寄存器，并存入主存。接着， CPU 恢复发出I/0 命令的程序（或其他程序）的上下文，然后继续运行。
- 【痛点】：中断驱动方式比程序直接控制方式有效，但由于数据中的每个字在存储器与I/0 控制器之间的传输都必须经过CPU, 这就导致了中断驱动方式仍然会消耗较多的CPU 时间。
- 【注意】：什么叫经过CPU呢？ 答：在DMA(Direct memory access 直接存储器访问)之前，输入数据流大概是这样的： 【外围设备->I/O控制器的数据寄存器->CPU寄存器->存储器】，这就叫经过CPU，或者说传输数据的过程需要CPU的干预，于是引出了所谓的DMA(直接在I/O设备和内存之间建立数据通路)。
DMA方式
为何引入DMA前面提到了，所有改进如下：
- 基本单位是数据块（前面是一个字）。
- 所传送的数据，是从设备直接送入内存的，或者相反。
- 仅在传送一个或多个数据块的开始和结束时，才需CPU 干预，整块数据的传送是在DMA控制器的控制下完成的。
- 命令／状态寄存器(CR) 。用于接收从CPU 发来的I/0 命令或有关控制信息，或设备的状态。
- 内存地址寄存器(MAR) 。在输入时，它存放把数据从设备传送到内存的起始目标地址；在输出时，它存放由内存到设备的内存源地址。
- 数据寄存器(DR) 。用于暂存从设备到内存或从内存到设备的数据。
- 数据计数器(DC) 。存放本次要传送的字（节）数。
如下图所示，DMA方式的工作过程是： CPU 接收到I/O 设备的DMA 中断请求时，它给I/0 控制器发出一条命令，启动DMA 控制器，然后继续其他工作。之后CPU 就把控制操作委托给DMA 控制器，由该控制器负责处理。DMA 控制器直接与存储器交互，传送整个数据块，每次传送一个字，这个过程不需要CPU 参与。传送完成后，DMA 控制器发送一个中断信号给处理器。因此只有在传送开始和结束时才需要CPU的参与(预处理【设置CR、MAR、DC等】和后处理【中断处理、唤醒因该I/O阻塞的进程程等】)。
attention
DMA控制方式与中断驱动方式的主要区别是:中断驱动方式在每个数据需要传输时中断 CPU, 而DMA 控制方式则是在所要求传送的一批数据全部传送结束时才中断CPU; 此外，中断驱动方式数据传送是在中断处理时由CPU 控制完成的，而DMA 控制方式则是在DMA 控制器的控制下完成的（前面提到了，加深印象！）。 ❝ 【不算痛点】：如何进一步提高资源利用率呢？当然是请更牛逼的秘书（通道），老板（CPU）尽可能的从累活中解放出来。 ❞
通道控制方式
通道：一种硬件，可以理解为是 “弱鸡版的CPU”。通道可以识别并执行一系列通道指令。
I/0 通道是指专门负责输入／输出的处理机。I/O通道方式是DMA方式的发展，它可以进一步 减少CPU的干预，即把对一个数据块的读（或写）为单位的干预，减少为对一组数据块的读（或写）及有关控制和管理为单位的干预。同时，又可以实现CPU、通道和I/0 设备三者的并行操作，从而更有效地提高整个系统的资源利用率。
[!for example]
❝ 例如，当CPU要完成一组相关的读（或写）操作及有关控制时，只需向I/O 通道发送一条 I/O 指令，以给出其所要执行的通道程序的首地址和要访问的I/0 设备，通道接到该指令后，执行通道程序便可完成CPU 指定的I/O任务，数据传送结束时向CPU发中断请求。(都有预处理和后处理，毕竟CPU才是老板！)
❞
❝ I/O通道与一般处理机的区别是：通道指令的类型单一，没有自己的内存，通道所执行的通 道程序是放在主机的内存中的，也就是说通道与CPU 共享内存。
❞
❝ I/O 通道与DMA方式的区别是:DMA 方式需要CPU 来控制传输的数据块大小、传输的内 存位置，而通道方式中这些信息是由通道控制的。另外，每个DMA 控制器对应一台设备与内存传递数据，而一个通道可以控制多台设备与内存的数据交换(包工头；也是上面提到的三者能并行的原因)。
❞
总(举例子)
[!for example]
❝ 想象一位客户要去裁缝店做一批衣服的情形。
1）采用程序直接控制时，裁缝没有客户的联系方式，客户必须每隔一段时间去裁缝店看看裁缝 把衣服做好了没有，这就浪费了客户不少的时间。
2）采用中断驱动方式时，裁缝有客户的联系方式，每当他完成一件衣服后，给客户打一个电话，让客户去拿，与程序直接控制能省去客户不少麻烦，但每完成一件衣服就让客户去拿一次，仍然比较浪费客户的时间。
3）采用DMA 方式时，客户花钱雇一位单线秘书，并向秘书交代好把衣服放在哪里（存放仓库），裁缝要联系就直接联系秘书，秘书负责把衣服取回来并放在合适的位置，每处理完100 件衣服，秘书就要给客户报告一次（大大节省了客户的时间）。
4）采用通道方式时，秘书拥有更高的自主权，与DMA方式相比，他可以决定把衣服存放在哪里，而不需要客户操心。而且，何时向客户报告，是处理完100 件衣服就报告，还是处理完10000件衣服才报告，秘书是可以决定的。客户有可能在多个裁缝那里订了货，一位DMA 类的秘书只能负责与一位裁缝沟通，但通道类秘书却可以与多名裁缝进行沟通。
❞
I/O软件层次结构
用户层软件
1 | 用户层软件实现了与用户交互的接口，用户可直接使用 |
设备独立性软件
设备独立性软件，又称设备无关性软件。与设备的硬件特性无关的功能几乎都在这一层实现。
主要实现的功能：
①向上层提供统一的调用接口（如 read/write 系统调用）
1 | 原理类似与文件保护。设备被看做是一种特殊的文件，不同用 |
②设备的保护
1 | 设备独立性软件需要对一些设备的错误进行处理 |
④设备的分配与回收
1 |
⑤数据缓冲区管理
1 | 可以通过缓冲技术屏蔽设备之间数据交换单位大小和传 |
⑥建立逻辑设备名到物理设备名的映射关系；根据设备类型选择调用相应的驱动程序
1 | 用户或用户层软件发出I/O操作相关系统调用的系统调用时， |
设备驱动程序
思考：为什么不同类型的I/O设备需要有不同的驱动程序处理？
答：各式各样的设备，外形不同，其内部的电子部件（I/O控制器）也有可能不同，不同设备的内部硬件特性也不同，这些特性只有厂家才知道，因此厂家须提供与设备相对应的驱动程序，CPU执行驱动程序的指令序列，来完成设置设备寄存器，检查设备状态等工作
1 | 主要负责对硬件设备的具体控制，将上层发出的一系列命令（如read/write）转化成特定设备“能听得懂”的一系列操作。包括设置设备寄存器；检查设备状态等 |
中断处理程序
1 | 当I/O任务完成时，I/O控制器会发送一个中断信号，系统会根据中断信号类型找到相应的中断 |
小结
1 | 理解并记住I/O软件各个层次之间的顺序，要能够推理判断某个处理应该是在哪个层次完成的 |
输入输出应用程序接口&设备驱动程序接口
输入/输出应用程序接口
阻塞/非阻塞I/O
阻塞I/O：应用程序发出I/O系统调用，进程需转为阻塞态等待。
eg：字符设备接口——从键盘读一个字符 get
非阻塞I/O：应用程序发出I/O系统调用，系统调用可迅速返回，进程无需阻塞等待。
eg：块设备接口——往磁盘写数据 write
设备驱动程序接口
不同的操作系统，对设备驱动程序接口的标准各不相同。设备厂商必须根据操作系
统的接口要求，开发相应的设备驱动程序，设备才能被使用
若各公司开发的设备驱动程序接口不统一，则操作系统很难调用设备驱动程序
操作系统规定好设备驱动程序的接口标准，各厂商必须按要求开发设备驱动程序
假脱机技术（SPOOLing技术）
脱机技术
在没有出现操作系统前，即手工操作阶段，主机直接从 I/O设备获得数据，由于设备速度慢，主机速度很快。人机速度矛盾明显，主机要浪费很多时间来等待设备
后来，在批处理阶段引入了 脱机技术（用磁带完成）：
在脱机技术中，在外围控制机的控制下，慢速的输入设备先将数据输入到更快速的磁带上，之后主机就可以快速的从磁带上读入数据，从而缓解了速度矛盾。同理，输出时，可以先将数据输出到快速的磁带上，之后通过外围控制机控制磁带将数据依次的输出到慢速的设备上。脱机技术——脱离主机的控制进行输入/输出操作。
假脱机技术（SPOOLing技术）
假脱机技术，又称“SPOOLing 技术”是用软件的方式模拟脱机技术。
假脱机技术由输入井和输出井、输入进程和输出进程以及输入缓冲区和输出缓冲区组成
其中输入井和输出井是用于模拟脱机技术中的磁带；输入进程和输出进程用于模拟脱机技术中的外围控制机；输入缓冲区用于暂存从输入设备输入的数据，之后再转存到输入井中，而输出缓冲区用于暂存从输出井传送的数据，之后再传送到输出设备上。
输入进程和输出进程需要和用户进程并发执行才可以模拟脱机技术，所以要实现SPOOLing技术需要多道程序技术的支持。
共享打印机的实现
打印机是独占设备，只允许各个进程串行使用设备，一段时间内只能满足一个进程的请求。
既然打印机是独占设备，那要如何实现共享呢？
答：当多个用户进程提出输出打印的请求时，系统会答应它们的请求，但是并不是真正把打印机分配给他们，而是由假脱机管理进程为每个进程做两件事：
(1)在磁盘输出井中为进程申请一个空闲缓冲区（也就是说，这个缓冲区是在磁盘上的），并将要打印的数据送入其中；
(2) 为用户进程申请一张空白的打印请求表，并将用户的打印请求填入表中（其实就是用来说明用户的打印数据存放位置等信息），再将该表挂到假脱机文件队列上。
当打印机空闲时，输出进程会从文件队列的队头取出一张打印请求表，并根据表中的要求将要打印数据从输出井传送到输出缓冲区，再输出到打印机打印。用这种方式可依次处理完全部地打印任务。
虽然系统中只有一台打印机，但每个进程提出打印请求时，系统都会为在输出井中为其分配一个存储区（相当于一个逻辑设备），使每个用户进程都觉得自己在独占一台打印机，从而实现对打印机的共享
小结
设备的分配与回收
设备分配应该考虑的因素
- 设备的固有属性
1 | 设备的固有属性可分为三种：独占设备、共享设备、虚拟设备。 |
- 设备的分配算法
1 | 设备的分配算法： |
- 设备分配中的安全性
1 | 从进程运行的安全性上考虑，设备分配有两种方式： |
静态分配与动态分配
静态分配
进程运行前为其分配全部所需资源，运行结束后归还资源【破坏了“请求和保持”条件，不会发生死锁】
动态分配
进程运行过程中动态申请设备资源
设备分配管理中的数据结构
“设备、控制器、通道”之间的关系：
一个通道可控制多个设备控制器，每个设备控制器可控制多个设备。
设备控制表（DCT）
系统为每个设备配置一张DCT，用于记录设备情况控制器控制表（COCT）
每个设备控制器都会对应一张COCT。操作系统根据COCT的信息对控制器进行操作和管理。通道控制表（CHCT）
每个通道都会对应一张CHCT。操作系统根据CHCT的信息对通道进行操作和管理。系统设备表（SDT）
记录了系统中全部设备的情况，每个设备对应一个表目
设备分配的步骤
①根据进程请求的物理设备名查找SDT（注：物理设备名是进程请求分配设备时提供的参数）
②根据SDT找到DCT，若设备忙碌则将进程PCB挂到设备等待队列中，不忙碌则将设备分配给进程。
③根据DCT找到COCT，若控制器忙碌则将进程PCB挂到控制器等待队列中，不忙碌则将控制器分配给进程。
④根据COCT找到CHCT，若通道忙碌则将进程PCB挂到通道等待队列中，不忙碌则将通道分配给进程。
注：只有设备、控制器、通道三者都分配成功时，这次设备分配才算成功，之后便可启动I/O设备进行数据传送
缺点：
①用户编程时必须使用“物理设备名”，底层细节对用户不透明，不方便编程
②若换了一个物理设备，则程序无法运行
③若进程请求的物理设备正在忙碌，则即使系统中还有同类型的设备，进程也必须阻塞等待
改进
建立逻辑设备名与物理设备名的映射机制，用户编程时只需提供逻辑设备名
设备分配步骤的改进
①根据进程请求的逻辑设备名查找SDT（注：用户编程时提供的逻辑设备名其实就是“设备类型”）
②查找SDT，找到用户进程指定类型的、并且空闲的设备，将其分配给该进程。操作系统在逻辑设备表（LUT）中新增一个表项。
③根据DCT找到COCT，若控制器忙碌则将进程PCB挂到控制器等待队列中，不忙碌则将控制器分配给进程。
④根据COCT找到CHCT，若通道忙碌则将进程PCB挂到通道等待队列中，不忙碌则将通道分配给进程。
1 | 逻辑设备表（LUT）建立了逻辑设备名与物理设备名之间的映射关系。 |
小结
