408-theory-Operation-System

原文链接：408-theory-Operation System

1.计算机系统概述

1.1基本概念

1. 计算机系统自下而上可大致分为4部分：硬件、操作系统、应用程序和用户
2. 操作系统管理各种计算机硬件，为应用程序提供基础，并充当计算机硬件与用户之间的中介。
3. 操作系统(Operating System, OS)是指控制和管理整个计算机系统的硬件与软件资源，合理地组织、调度计算机的工作与资源的分配，进而为用户和其他软件提供方便接口与环境的程序集合。操作系统是计算机系统中最基本的系统软件。

1.1.1操作系统的特征

并发和共享是操作系统两个最基奎的特征

1. 并发
   并发是指两个或多个事件在同一时间间隔内发生。
2. 共享
   资源共享即共享，是指系统中的资源可供内存中多个并发执行的进程共同使用。主要包括：互斥共享方式、 同时访问方式
3. 虚拟
   虚拟是指把一个物理上的实体变为若干逻辑上的对应物。物理实体（前者）是实的，即实际存在的；而后者是虚的，是用户感觉上的事物。
4. 异步
   多道程序环境允许多个程序并发执行，但由于资源有限，进程的执行并不是一贯到底的，而是走走停停的，它以不可预知的速度向前推进，这就是进程的异步性。

1.1.2操作系统的目标和功能

资源管理：

1. 处理机管理
   对处理机的管理可归结为对进程的管理。进程管理的主要功能包括进程控制、进程同步、进程通信、死锁处理、处理机调度等
2. 存储器管理
   内存分配与回收、地址映射、内存保护与共享和内存扩充等功能
3. 设备管理
   缓冲管理、设备分配、设备处理和虚拟设备等功能
4. 文件管理
   文件存储空间的管理、目录管理及文件读写管理和保护等

接口功能：

1. 命令接口
   包括联机命令接口（交互式命令接口，它由一组键盘操作命令组成。）和脱机命令接口（批处理命令接口，它由一组作业控制命令组成。脱机用户不能直接干预作业的运行）
2. 程序接口
   由一组系统调用(也称广义指令)组成。用户通过在程序中使用这些系统调用来请求操作系统为其提供服务

没有任何软件支持的计算机称为裸机，它仅构成计算机系统的物质基础，而覆盖了软件的机器称为扩充机器或虚拟机

原语通常由若干条指令组成，用来实现某个特定的操作。通过一段不可分割的或不可中断的程序实现其功能。

易错补充点：

• 并发性是指若干事件在同一时间间隔内发生，而并行性是指若干事件在同一时刻发生。
• 顺序性是单道程序设计的基本特征。引入多道程序设计后，程序的执行就失去了封闭性和顺序性
• 在单处理机系统中，同一时刻只能有一个进程占用处理机，因此进程之间不能并行执行。
• 操作系统的基本特点：丑发、芸皇、虚拟、异步，其中最基本、一定要实现的是并发和共享。
• 进程多并不意味着CPU利用率高，进程数量越多，进程之间的资源竞争越激烈，甚至可能因为资源竞争而出现死锁现象，导致CPU利用率低

1.2操作系统发展历程

1.2.1手工操作阶段（此阶段无操作系统）

缺点：

1. 用户独占全机
2. CPU的利用不充分

1.2.2批处理阶段

• 单道批处理系统
  特点：自动性 顺序性 单道性
  缺陷：单作业运行时会出现高速CPU等待低速IO完成的情况
• 多道批处理系统
  特点：多道 宏观上并行 微观上串行
  优点：资源利用率高 系统吞吐
  量大
  缺点：用户响应的时间较长 用户既不能了解自己的程序的运行情况，又不能控制计算机

1.2.3分时操作系统

特点： 同时性 交互性 独立性 及时性

1.2.4实时操作系统

某个时间限制内完成某些紧急任务而不需要时间片排队
硬实时系统（某个动作必须绝对地在规定的时刻）
软实时系统（偶尔违反时间规定且不会引起任何永久性的损害）

1.2.5网络操作系统和分布式计算机系统

网络操作系统：由网络连接
分布式计算机系统：多台计算机资源设备共享

1.2.6个人计算机操作系统

嵌入式操作系统、服务器操作系统、智能手机操作系统

易错补充点：

• 实时系统的进程调度，通常采用抢占式的优先级高者优先算法
• 分时系统使用优先级+非抢占式调度算法改进响应时间
• 多任务操作系统可并发和并行

1.3操作系统运行环境

1.3.1处理器运行模式

操作系统CPU执行两种程序：系统内核程序和用户自编程序。
操作系统CPU存在两种运行模式：用户态(目态)和核心态(又称管态、内核态)。内核程序运行在内核态，用户程序运行在用户态。

特权指令是指不允许用户直接使用的指令,非特权指令是指允许用户直接使用的指令。切换状态的指令也是特权指令。

访管指令（陷入指令）
在用户态下运行的进程调用操作系统内核程序。应用程序向操作系统请求服务时通过使用访管指令，从而产生一个中断事件将操作系统转换为核心态

操作系统的内核包括4方面：

1. 时钟管理
   最关键的设备，包括中断管理 进程切换 轮换调度等
2. 中断机制
   这样可以减少中断的处理时间，提高系统的并行处理能力
3. 原语
   底层公共微程序，不可中断执行，调用频繁。定义原语的直接方法是关闭中断,让其所有动作不可分割地完成后再打开中断。
4. 系统控制的数据结构及处理
   进程管理 存储器管理 设备管理

1.3.2中断和异常

用户程序工作在用户态，通过中断加入核心态，这是通过硬件实现的
中断包括外部中断和内部异常

定义

中断是指来自CPU执行指令外部的事件
异常是指来自CPU执行指令内部的事件

分类

外部中断包括：可屏蔽中断(INTR线请求如设备IO执行完成) 不可屏蔽中断(NMI线请求硬件故障如电源)
内部异常包括:故障fault（指令执行异常如除0运算），自陷trap（需要内核态时主动调用），终止abort（cpu硬件出错）

处理

中断和异常处理过程的大致描述如下：当CPU在执行用户程序的第i条指令时检测到一个异常事件，或在执行第i条指令后发现一个中断请求信号，则CPU打断当前的用户程序，然后转到相应的中断或异常处理程序去执行。若中断或异常处理程序能够解决相应的问题，则在中断或异常处理程序的最后，CPU通过执行中断或异常返回指令，回到被打断的用户程序的第，条指令或第i+1条指令继续执行；若中断或异常处理程序发现是不可恢复的致命错误，则终止用户程序。 通常情况下，对中断和异常的具体处理过程由操作系统（和驱动程序）完成。

1.3.3系统调用

用户在程序中调用操作系统所提供的一些子功能
系统调用按功能分类： 设备管理 文件管理 进程控制 进程通信 内存管理
用户通过操作系统运行上层程序
上层程序的运行依赖于操作系统的底层管理程序
系统则通过硬件中断机制进入核心态，运行管理程序
也可能是程序运行出现异常情况，被动地需要管理程序的服务
这时就通过异常处理来进入核心态
管理程序运行结束时，中断返回断点处继续执行

易错补充点：

• 中断处理：需要保存通用寄存器（包括数据、地址）、程序计数器PC、程序状态字PSW寄存器。
• 子程序调用：需要保存通用寄存器（包括数据、地址）、程序计数器PC。
• 计算机通过硬件中断机制完成由用户态到核心态的转换。
• 外部中断、内部异常都可以在用户态发生，但是异常中断服务程序在内核态执行
• 中断和异常中 由操作系统保存通用寄存器 PC,cache,psw,内核态由硬件cpu保存

1.4操作系统结构

1.4.1分层法

优点：

1. 便于系统的调试和验证，简化了系统的设计和实现
2. 易扩充和易维护
   缺点：
3. 合理定义各层比较困难
4. 效率较差

1.4.2模块化

评价：高内聚(元素关系紧密)，低耦合(模块关系独立) 最佳
优点：

1. 提高了操作系统设计的正确性、可理解性和可维护性
2. 增强了操作系统的可适应性
3. 加速了操作系统的开发过程
   缺点：
4. 模块间的接口规定很难满足对接口的实际需求
5. 无法找到一个可靠的决定顺序

1.4.3宏内核

是指将系统的主要功能模块都作为一个紧密联系的整体运行在核心态，从而为用户程序提供高性能的系统服务

1.4.4微内核

是指将内核中最基本的功能保留在内核，而将那些不需要在核心态执行的功能移到用户态执行，从而降低内核的设计复杂性
操作系统分为微内核和多个服务器，只有微内核运行在内核态，其余模块都运行在用户态
微内核的基本功能：

1. 进程（线程）管理
2. 低级存储器管理
3. 断和陷入处理
   优点：
4. 扩展性和灵活性
5. 可靠性和安全性
6. 可移植性
7. 分布式计算

1.4.5外核

对机器进行分区，给每个用户整个资源的一个子集
任务是为虚拟机分配资源，并检查使用这些资源的企图，以确保没有机器会使用他人的资源
优点：

1. 减少了映射层
2. 将多道程序（在外核内）与用户操作系统代码（在用户空间内）加以分离，而且相应的负载并不重，因为外核所做的只是保持多个虚拟机彼此不发生冲突。

1.5操作系统引导

操作系统引导是一个复杂且综合的部分，细节很多，参考操作系统引导全过程

引导过程：

1. 激活CPU
2. 硬件自检
3. BIOS加载带有操作系统的硬盘，加载主引导记录MBR
4. 扫描分区表，加载活动分区引导记录PBR
5. PBR加载启动管理器
6. 加载操作系统

1.6虚拟机

虚拟机是一台逻辑计算机，是指利用特殊的虚拟化技术，通过隐藏特定计算平台的实际物理特性，为用户提供抽象的、统一的、模拟的计算环境。

1.6.1第一类虚拟机管理程序（裸金属架构）

第一类虚拟机管理程序就像一个操作系统，因为它是唯一一个运行在最高特权级的程序。每台虚拟机都与裸机相同。
虚拟机作为用户态的一个进程运行，不允许执行敏感指令。
在支持虚拟化的CPU上，虚拟机管理程序检查会判断是操作系统还是用户，前者直接运行，后者将模拟真实硬件面对用户态执行敏感指令时的行为。
不支持虚拟化的CPU上，指令转为对虚拟机管理程序的调用，由虚拟机管理程序模拟这些指令的功能。

1.6.2第二类虚拟机管理程序（寄居架构）

类似一个普通的进程，如VMware Workstation，仍然伪装成具有CPU和各种设
备的完整计算机。
运行在虚拟机管理程序上的为客户操作系统，运行在底层硬件上的操作系统称为宿主操作系统

1. 中断和陷入处理也应放入微内核
2. 微内核中的服务器通信依赖内核，系统效率不会太高
3. 引导程序仅将硬盘中存储的操作系统内核加载到内存，其它部分在使用时加载
4. 操作系统的引导程序包括 自举程序位于ROM中的BIOS，和装有操作系统硬盘的活动分区的引导扇区中的引导程
5. 虚拟机真正并行的是多核处理机，在单核机上为并发

2进程与线程

2.1进程

2.1.1进程概念与特征

进程是程序的一次执行过程，进程是具有独立功能的程序在一个数据集合上运行的过程，它是系统进行资源分配和调度的一个独立单位。
进程实体包括程序段、数据段和PCB(Process Control Block)，进程实体是静态的，进程则是动态的。

特征：

1. 动态性（基本特征）
2. 并发性（重要特征）
3. 独立性
4. 异步性（导致结果不可再现）

2.1.2进程的状态与转换

状态：

• 运行态：进程正在处理机上运行。在单处理机中，每个时刻只有一个进程处于运行态。
• 就绪态：进程获得了除处理机外的一切所需资源，所有处于就绪状态的进程在就绪队列中
• 阻塞态（等待态）：进程正在等待某一事件而暂停运行，根据阻塞原因的不同，设置多个阻塞队列，只有就绪态能够转为阻塞态
• 创建态：进程正在被创建，当在创建态不能获取到足够资源时依旧处于创建态
• 终止态：进程正从系统中消失，正常结束或异常结束

状态转换：

• 创建态->就绪态：进程创建完成转为就绪态
• 就绪态->运行态：处于就绪态的进程被调度后，获得处理机资源
• 运行态->就绪态：处理机时间用完或被抢占
• 运行态->阻塞态：主动请求资源或等待事件发生，进程以系统调用的形式请求操作系统提供服务
• 阻塞态->就绪态：进程获取到资源或等待的事件到来时
• 运行态->终止态：进程结束

2.1.3进程的组成

1. 进程控制块
   进程创建时，操作系统为它新建一个PCB,该结构之后常驻内存，任意时刻都可以存取，在进程结束时删除。PCB是进程实体的一部分，是进程存在的唯一标志。
   PCB包括：进程描述信息(PID,UID)，进程控制和管理信息，资源分配清单，处理机相关信息
2. 程序段
   程序可被多个进程共享，即多个进程可以运行同一个程序
3. 数据段
   原始数据或执行时产生的中间或最终结果

2.1.4进程的控制

进程的控制程序属于原语，即不可被中断

1. 创建
   分配唯一进程ID，申请空白PCB，分配资源，初始化PCB，插入就绪队列
2. 终止
   包括：正常结束 异常结束 外界干预
   检索该进程PCB，终止进程运行，将处理机资源分配其他进程，终止子孙进程，资源归还父进程，将该pcb删除
3. 阻塞
   找到PCB，转为阻塞态，停止运行，插入到相应事件的等待队列
4. 唤醒
   在该事件等待队列找到PCB，移除该队列，转为就绪态，插入就绪队列

2.1.5进程的通信

通信方式：

1. 共享存储
   基于数据结构的共享 基于存储区的共享
2. 消息传递
   使用格式化消息进行通信（消息传递机制），使用直接通信方式，或间接通信方式（中间代理）
3. 管道通信
   管道可以限制大小，且当管道空或满会自动阻塞相应进程

2.2线程

2.2.1概念

1. 一个基本的CPU执行单元 程序执行流的最小单元
2. 线程是进程中的一个实体
3. 被系统独立调度和分派的基本单位
4. 同属一个进程的其他线程共享进程所拥有的全部资源
5. 一个线程可以创建和撤销另一个线程
6. 同一进程中的多个线程之间可以并发执行
7. 引入线程后，线程变为处理机调度单位

2.2.2线程进程比较

进程的目的是更好地使多道程序并发执行，提高资源利用率和系统吞吐量
线程的目的则是减小程序在并发执行时所付出的时空开销，提高操作系统的并发性能

1. 调度
   进程调度会上下文切换，开销大，而同一进程的线程之间切换开销小
2. 并发性
   线程之间可以并发，提高了系统资源的利用率和系统的吞吐量。
3. 资源占有
   进程分配的资源独占，而同一线程资源共享，不同进程线程资源不共享。正因为线程不会独占资源，切换线程开销小
4. 独立性
   进程之间独立，同一进程线程之间共享
5. 系统开销
   进程开销大，线程开销小
6. 支持多处理机系统
   单线程进程只能在一个处理机上运行，而多线程进程可以在不同处理机运行

2.2.3线程属性

1. 线程是一个轻型实体，它不拥有系统资源
2. 不同的线程可以执行相同的程序
3. 同一进程中的各个线程共享该进程所拥有的资源
4. 线程是处理机的独立调度单位，多个线程是可以并发执行的
5. 一个线程被创建后，便开始了它的生命周期，直至终止
   线程的提出有利于提高系统并发性原因在于线程降低了切换的平均开销

2.2.4状态转换

执行状态：线程己获得处理机而正在运行。
就绪状态：线程已具备各种执行条件，只需再获得CPU便可立即执行。
阻寒状态：线程在执行中因某事件受阻而处于暂停

2.2.5组织控制

线程控制块TCB：
线程标识符
一组寄存器（包括程序计数器、状态寄存器和通用寄存器）
线程运行状态 用于描述线程正处于何种状态
优先级
线程专有存储区，线程切换 时用于保存现场等
堆栈指针，用于过程调用时保存局部变量及返回地址等

2.2.6实现方式

包括用户级线程ULT，内核级线程KLT
ULT：
通过线程库实现线程设计，在内核来看只有一个线程
优点：

1. 线程切换不需要转换到内核空间，节省了模式切换的开销
2. 调度算法可以是进程专用的，不同的进程可根据自身的需要，对自己的线程选择不同的调度算法
3. 用户级线程的实现与操作系统平台无关，对线程管理的代码是属于用户程序的一部分
   缺点：
4. 单个线程阻塞，该进程其它线程也被阻塞
5. 内核只会分配一个处理机给该进程，不能实现多线程并行

KLT：
在操作系统内核的支持下运行的

1. 能发挥多处理机的优势，内核能同时调度同一进程中的多个线程并行执行
2. 进程某个线程阻塞，内核仍然可以运行其它线程
3. 线程切换开销小
4. 内核本身也可采用多线程技术，可以提高系统的执行速度和效率
   缺点：
   同一进程的线程切换也需要切换上下文，因为线程切换是在内核完成

组合方式
多个内核线程和多个用户线程组合

2.2.7多线程模型

用户级线程和内核级线程连接方式的不同，形成了下面三种不同的多线程模型

1. 多对一模型
   将多个用户级线程映射到一个内核级线程
2. 一对一模型
   将每个用户级线程映射到一个内核级线程
3. 多对多模型
   将n个用户线程映射到m个内核级线程上
   

易错补充点：

• 在单处理器系统中，任何时刻都只有一个进程处于运行态（X，存在所有进程都阻塞情况）
• 程序封闭性是指进程执行的结果只取决于进程本身，不受外界影响，并发进程失去封闭性是指并发进程共享变量，其执行结果与速度有关
• 进程之间可能是无关的，但也可能是有交互性的
• 线程（Thread）是一种特殊的进程
• 进程中的数据存放在正文段，堆区和栈区，不变的数据在正文段，malloc在堆区，局部变量在栈区

2.3处理机调度

2.3.1概念

处理机调度是对处理机进行分配。
进程的数量往往多于处理机的个数，从就绪队列中按照一定的算法选择进程执行即为调度。
处理机调度是多道程序操作系统的基础，是操作系统设计的核心问题

调度三个层次：

1. 高级调度（作业调度）
   从后备队列中选择分配内存设备资源创建进程，每个作业只调入一次、调出一次。
2. 中级调度（内存调度）
   目的是提高内存利用率和系统吞吐量，将等待的进程存放在外存，此时为挂起态，当己具备运行条件且内存又稍有空闲时再重新调入内存修改就绪态并进入就绪队列
3. 低级调度（进程调度）最基本
   按照某种算法从就绪队列中选取一个进程，进程调度的频率很高，一般几十毫秒一次

三种调度关系:

1. 作业调度为进程活动做准备，进程调度使进程正常活动起来。
2. 中级调度将暂时不能运行的进程挂起，中级调度处于作业调度和进程调度之间。
3. 作业调度次数少，中级调度次数略多，进程调度频率最高。
4. 进程调度是最基本的，不可或缺。

2.3.2目标

评价标准：

1. CPU利用率
   α=CPU有效工作时间/(CPU有效工作时间+ CPU空闲等待时间)
2. 单位时间内CPU完成作业的数量
3. 作业周转事件
   周转时间=作业完成时间-作业提交时间
   平均周转时间=（作业1的周转时间+…+作业n的周转时间）/n
   带权周转时间=作业周转时间/作业实际运行时间
   平均带权周转时间=(作业1的带权周转时间+…+作业n的带权周转时间)/n
4. 等待时间
   周转时间-实际运行时间
5. 响应时间
   作业提交到首次相应的时间

2.3.3实现

2.3.3.1调度程序

调度器对CPU分派和进程调度
调度器包括：

1. 排队器
   将系统中的所有就绪进程按照一定的策略排成一个或多个队列
2. 分派器。依据调度程序所选的进程，将其从就绪队列中取出
3. 上下文切换器，保存当前进程上下文到PCB，加载分派进程上下文

调度的执行顺序：请求调度->内核执行调度程序->进程切换

2.3.3.2调度过程

不能进程调度的情况：

1. 中断处理过程
2. 进程访问临界区资源时
3. 原子操作
   执行调度情况：
4. 引起调度条件，当前进程无法运行
5. 中断或异常结束

进程切换往往在调度完成后立刻发生，它要求保存原进程当前断点的现场信息，恢复被调度进程的现场信息。现场切换时，操作系统内核将原进程的现场信息推入当前进程的内核堆栈来保存它们，并更新堆栈指针。内核完成从新进程的内核栈中装入新进程的现场信息、更新当前运行进程空间指针、重设PC寄存器等相关工作之后，开始运行新的进程

2.3.3.3调度方式

• 非抢占式
• 抢占式
  抢占处理机需要遵循规则，主要有优先权、短进程优先和时间片原则。抢占式对提高系统吞吐率和响应效率都有明显的好处。

2.3.3.4闲逛进程(idle)

没有其他进程就绪，该进程就一直运行，该进程不会阻塞

2.3.3.5线程调度

• 用户级线程调度
  由进程进行调度
• 内核级线程调度
  类似进程

2.3.4调度算法

FCFS

算法简单
效率低
对长作业比较有利 但对短作业不利
有利于CPU繁忙型作业 而不利于I/O繁忙型作业

SJF

该算法对长作业不利，会出现饥饿现象
该算法完全未考虑作业的紧迫程度
算法不一定能真正做到短作业优先调度
平均等待时间、平均周转时间最少

优先级调度算法

能否抢占分为：

• 非抢占式优先级调度算法
• 抢占式优先级调度算法
  优先级是否可变：
• 静态优先级 创建时优先级即确定 主要依据有进程类型、进程对资源的要求、用户要求
• 动态优先级 据进程情况的变化动态调整优先级 主要依据有进程占有CPU时间的长短、就绪进程等待CPU时间的长短
  优先级的设置：

1. 系统进程>用户进程
2. 交互型进程〉非交互型进程
3. I/O型进程>计算型进程

HRRN

每次进行作业调度时,先计算后备作业队列中每个作业的响应比，从中选出响应比最高的作业投入运行.
响应比$R_p=(等待时间+运行时间)/运行时间$
特点：

1. 作业的等待时间相同时，要求服务时间越短，响应比越高，有利于短作业
2. 要求服务时间相同时，等待时间越长响应比越高，类似于FCFS
3. 长作业响应比可以随等待时间的增加而提高，克服了饥饿现象

RR

时间片轮转调度算法主要适用于分时系统。在这种算法中，系统将所有就绪进程按FCFS策略排成一个就绪队列，调度程序总是选择就绪队列中的第一个进程执行，但仅能运行一个时间片， 如50ms。在使用完一个时间片后，即使进程并未运行完成，它也必须释放出（被剥夺）处理机给下一个就绪进程，而被剥夺的进程返回到就绪队列的末尾重新排队，等候再次运行。
特点：

1. 时间片的大小对系统性能的影响很大
2. 时间片的长短通常由以下因素确定：系统的响应时间、就绪队列中的进程数目和系统的处理能力。

MLQ多级队列调度算法

在系统中设置多个就绪队列，将不同类型或性质的进程固定分配到不同的就绪队列，每个队列可实施不同的调度算法。同一队列，不同队列，不同处理机设置不同调度策略，实现了多个线程分配到多个处理机运行。

MLFQ多级反馈队列调度算法

1. 设置多个就绪队列，并为每个队列赋予不同的优先级，优先级递减
2. 不同队列时间片不同，优先级越高时间片越小
3. 每个队列都采用FCFS算法
4. 进程在当前时间片结束未完成，转入下一队列，直到最后一个队列采用时间片轮转调度
5. 按队列优先级调度，前一个队列为空才调度第二个队列进程，当当前加入一个高优先级队列的进程，将该进程放回队尾，执行高优先级进程

多级反馈队列的优势有以下几点：

1. 终端型作业用户：短作业优先。
2. 短批处理作业用户：周转时间较短。
3. 长批处理作业用户：经过前面几个队列得到部分执行，不会长期得不到处理

2.3.5进程切换

上下文切换：切换CPU到另一个进程需要保存当前进程状态并恢复另一个进程的状态
上下文是指某一时刻CPU寄存器和程序计数器的内容

上下文切换的流程：

1. 挂起一个进程，保存CPU上下文，包括程序计数器和其他寄存器
2. 更新PCB信息
3. 把进程的PCB移入相应的队列，如就绪、在某事件阻塞等队列
4. 选择另一个进程执行，并更新其PCB
5. 跳转到新进程PCB中的程序计数器所指向的位置执行
6. 恢复处理机上下文

上下文切换开销大，有些处理器提供多个寄存器组，实现上下文切换就只需要简单改变当前寄存器组的指针

模式切换与上下文切换

1. 用户态和内核态之间的切换称为模式切换
2. 模式切换不会导致上下文切换
3. 上下文切换只能发生在内核态

易错补充点：

1. 中断发生时，由硬件保护并更新程序计数器（PC）,而不是由软件完成，主要是为了提高安全性，处理速度是次要

2.4同步互斥

2.4.1概念

临界资源：一次仅允许一个进程使用的资源
临界区：访问临界资源的那段代码

临界资源的访问过程：

1. 进入区。为了进入临界区使用临界资源，在进入区要检查可否进入临界区，若能进入临界区，则应设置正在访问临界区的标志，以阻止其他进程同时进入临界区。
2. 临界区。进程中访问临界资源的那段代码，又称临界段。
3. 退出区。将正在访问临界区的标志清除。
4. 剩余区。代码中的其余部分

同步：多个进程共同完成同一个任务

互斥：同一时刻只能一个进程访问临界区资源

2.4.2方法

软件实现

1. 单标志法：两个进程使用1个共享标志，只允许交替访问
2. 双标志法先检查：可连续使用，会出现同时进入临界区
3. 双标志法后检查：将算法2中先设置值再判断，会导致饥饿现象
4. Peterson’s Algorithm，结合双标+单标

// 单标志法 交替执行
int s=0;
P1:
    while(s!=0){}
    //临界区操作
    s=1;
P2:
    while(s!=1){}
    //临界区操作
    s=0;

// 双标志法先检查
int s1=0,s2=0;
P1:
    while(s2){}
    s1=1;
    //临界区操作
    s1=0;
P2:
    while(s1){}
    s2=1;
    //临界区操作
    s2=0;


// 双标志法后检查
int s1=0,s2=0;
P1:
    s1=1;
    while(s2){}
    //临界区操作
    s1=0;
P2:
    s2=1;
    while(s1){}
    //临界区操作
    s2=0;


// Peterson's Algorithm

int s=0,s1=0,s2=0;
P1:
    s1=1;
    s=0; //使用单标志实现主动等待
    while(s2&&s==0){}
    //临界区操作
    s1=0;
P2:
    s2=1;
    s=1;
    while(s1&&s==1){}
    //临界区操作
    s2=0;

硬件实现(原子操作,该指令是关中断的,不可中断)
TAS(TestAndSet)自旋锁(spin lock):将提供的地址设为1,返回旧值

// TAS同步:进程1 lock为0,跳出,设置lock为1,进程2等1结束后lock归0,后跳出
lock=0;
while(test_and_set(lock)==1){}
// 临界区代码
lock=0;

CAS(compare_and_swap(V,A,B))自旋锁(spin lock): 返回V的原值,当V==A:V修改B,!=A,不操作

```

优点：每个进程一个变量即可实现，缺点：由于是随机抢占资源，会出现饥饿现象
1. 中断屏蔽：程序使用关中断和开中断，组织cpu切换进程，可能会导致系统终止
2. 硬件指令TestAndSet设置临界区锁
3. swap交换指令实现互斥 由于硬件指令不会中断

互斥锁

使用加锁解锁的硬件方法函数实现互斥
缺点是忙等待，被锁后其它进程需要一直循环阻塞

信号量

整型信号量简单，记录型信号量使用进程链表，实现让权等待
wait等待，signal释放

* 信号量功能：
  1. 信号量实现同步
  2. 信号量实现进程互斥
  3. 信号量实现前驱关系
* 信号量设置步骤：
  1. 关系分析
  2. 整理思路
  3. 设置信号量 

管程monitor

管程：共享资源的数据结构，以及由对该共享数据结构实施操作的一组过程所组成的资源管理程序
组成：

1. 管程的名称
2. 局部于管程内部的共享数据结构说明
3. 对该数据结构进行操作的一组过程(或函数)
4. 对局部于管程内部的共享数据设置初始值的语句。 

条件变量：当进程在管程内阻塞，会导致其它进程无法进入，使用条件变量控制进程阻塞
1. 管程中对多个阻塞条件设置不同条件变量，不同阻塞原因的进程会加入到不同的条件变量的等待进程队列



#### 2.4.3经典同步问题
生产者消费者:N个缓冲区,多个生产者和消费者,不能同时存取
```shell
semaphore used=0,empty=N,mutex=1;

producer:
    P(empty);
    P(mutex);
    //put
    V(mutex);
    V(used);
consumer:
    P(used);
    P(mutex);
    //get
    V(mutex);
    V(empty);

读者写者:N个缓冲区,多个读者和写者,可以同时读,不能同时读写

semaphore count=0,rmutex=1,mutex=1;

writer:
    P(mutex);
    //write
    V(mutex);

    
reader:
    P(rmutex);
    if(cout==0) P(mutex);
    cout++;
    V(rmutex);
    
    //read

    P(rmutex);
    cout--;
    if(cout==0) V(mutex);
    V(rmutex);

哲学家:5个人5支筷子,会出现死锁,可通过多种方法解决

#使用奇数号先拿左,偶数先拿右
semaphore ck={1,1,1,1,1};

pi:
    //think
    if(i%2==0){
        P(ck[i+1]);
        P(ck[i]);
        //eat
        V(ck[i+1]);
        V(ck[i]);
    }else{
        P(ck[i]);
        P(ck[i+1]);
        //eat
        V(ck[i]);
        V(ck[i+1]);
    }

2.4.4

2.5死锁

定义：多个进程竞争导致互相等待

产生原因：

1. 系统资源的竞争，对不可剥夺资源的竞争导致死锁
2. 进程推进顺序非法，信号量使用不当也会造成死锁

死锁产生的必要条件：

1. 互斥条件：某资源只能被一个进程占有
2. 不剥夺条件：进程获得的资源不能被剥夺
3. 请求并保持条件：进程请求新的资源时仍保持已占有资源
4. 循环等待条件：多个进程资源之间循环请求。但循环不一定等待，因为当循环外存在资源时就不存在死锁

死锁的解决：

1. 死锁预防：破坏产生死锁的4个必要条件
2. 死锁避免：分配资源时使用某种方法防止系统进入不安全状态
   安全状态是系统能按某种进程推进顺序分配资源，称为安全序列，使每个进程都可顺序完成。不能找到称为不安全状态
   安全状态下必定不会死锁。使用银行家算法死锁避免。
3. 死锁检测：能够检测并解除死锁
   绘制资源分配图，圆圈表示进程，框表示一类资源，框中的一个圆代表一类资源中的一个资源，进程到资源为请求边，资源到进程为分配边
   使用死锁定理判断死锁发生：S为死锁的条件是当且仅当S状态的资源分配图是不可完全简化的
   死锁解除：资源剥夺法 撤销进程法 进程回退法

易错补充点：

1. 临界区是指并发进程访问共享变量段的代码程序
2. 管程是被进程调用的，管程是语法范围，无法创建和撤销，signal操作的作用和信号量机制中的V操作不同
3. 进程进入资源等待队列的条件S.value的条件应该与P操作执行顺序相关
4. 信箱通信即消息队列，使用进程外的资源进行通信，属于间接通信
5. 等待进入临界区的进程不会主动放弃CPU

3内存管理

3.1概念

3.1.1内存管理主要功能

1. 内存空间分配与回收
2. 地址转换
3. 内存共享
4. 内存扩充
5. 存储保护

3.1.2进程运行的基本原理

1. 程序链接与装入
   源代码到程序需要：编译，链接，装入
   链接包括：静态链接，装入时动态链接，运行时动态链接
   装入包括：绝对装入（仅适用单道程序设计），静态重定位（可重定位装入），动态重定位（动态运行时装入）

2. 逻辑地址和物理地址
   逻辑地址即模块的相对地址，进程操作针对逻辑地址，实际操作系统提供内存管理部件MMU进行地址转换

3. 进程的内存映像
   进程装入内存中即为内存映像，包括代码段，数据段，PCB，堆，栈，堆栈空间大小是动态的

4. 内存保护
   使用上下寄存器存放上下界地址，每次访问判断是否越界
   使用重定位寄存器（基地址寄存器），界地址寄存器（限长寄存器），基地址寄存器存放程序的最小物理地址，界地址寄存器存放最大逻辑地址。访问时比较当前地址是否超过界地址寄存器存放最大值，不超过加上基地址寄存器值即为物理地址。加载重定位寄存器和界地址寄存器时必须使用特权指令

5. 内存共享

6. 内存分配与回收
   页式存储管理

3.1.3内存连续分配方式

1. 单一连续分配
   内存在此方式下分为系统区和用户区，系统区仅供操作系统使用，通常在低地址部分，单出现对用户区独占
2. 固定分区分配
   对内存分区设置大小，大小相等或不等。按分区大小排队创建分区使用表，程序找满足大小且未分配区装配。
   问题：程序可能太大而放不进任何一个分区，程序小于固定分区大小存在空间浪费，这种现象称为内部碎片
3. 动态分区分配
   不进行限制分区，通过不断换入换出实现进程装入，但随着时间的推移，内存中会产生越来越多小的内存块，小的内存块称为外部碎片，通过紧凑技术来解决
   动态分区的分配策略：
   • 首次适应：从首地址寻找满足分区：通常也是最好和最快的
   • 邻近适应：从上次结束的位置开始寻找满足分区：比首次适应算法要差
   • 最佳适应：每次寻找满足大小的最小分区：性能通常很差，会产生最多的外部碎片
   • 最坏适应：每次寻找满足大小的最大分区：会很快导致没有可用的大内存块，因此性能也非常差

3.1.4内存非连续分配方式

解决连续分配方式中没有连续空间满足分配的问题

3.1.4.1基本分页存储管理

将内存等分很多小块，每块作为主存的基本单位，进程申请内存按块申请。
进程的块为页面，内存的块为页框，外存中为块。申请内存就是申请内存中的页框，进程的每个页面和页框相对应。
使用页表实现逻辑地址到物理地址块的转换。
逻辑地址包括：页号，页内偏移量。
页表是每个进程的页号与物理块号的映射表。由页表项组成，页表项包括页号和块号。
页表寄存器PTR：页表寄存器存放页表起始地址和页表长，该数据存放与进程PCB中，进程调度的时候装入。

• 通过页表实现逻辑地址转换物理地址流程
  1. 逻辑地址A通过页表项长L 计算出页号P=A/L,偏移地址W=A%L
  2. 页号P与页表长度M比较，P>M越界，否则P*L+页表起始地址F 获得页表中对应的页地址
  3. 通过页号找到对应块号b
  4. 物理地址为b*页表大小+页内偏移量W

• 存在的两个主要问题

  1. 每次访存都要地址转换
  2. 每个进程都需要一个页表

• 通过快表实现逻辑地址转换物理地址流程

  1. 页号直接访问快表，如果存在对应页号，直接计算物理地址
  2. 快表中不存在则在慢表中查找
  3. 将该页表项采用算法将块表中的项换出

分页存储管理存在的主要问题：页表本身需要的空间就很大，降低了内存效率，为了解决这一问题，引入二级页表。

3.1.4.2基本分段存储管理

使用逻辑空间与内存空间映射的段表，段表项包括段号，段长，段基址

• 通过段表实现逻辑地址转换物理地址流程
  1. 逻辑地址A包括段号S偏移地址W，显示给出，因为段长不定
  2. 段号P与段表长度M比较，S>M越界，否则S*L+段表起始地址F获得段表中对应的段地址
  3. 通过段号找到对应段的基址b，此时需要比较段长和段内偏移W比较，超过产生越界中断
  4. 物理地址为 b+段内偏移量W
     

3.1.4.3段页式管理

该结构中段表存放段号，页表长，页表起始地址；页表存放页号，块号。
先通过段号寻找到对应页表，再通过对应页表找到块

• 通过段表和页表实现逻辑地址转换物理地址流程
  1. 逻辑地址A包括 段号S 页号P 页内偏移W
  2. 段号P与段表长度M比较，S>M越界，否则S*L+段表起始地址F获得段表中对应的段地址
  3. 由段号找到页表长度和起始地址，比较页表长与页号大小，并将页号+页表起始地址找到页表中对应页号，获得块号
  4. 物理地址为 块号*页表大小+页内偏移量W
     

易错补充点：

1. 对于二级页表管理，页大小1KB，页表项大小2B，逻辑空间2^16页。则一页可放2^9页表项，逻辑空间需要2^16项，则总共需要2^7页，则页目录表需要2^7个页表项
2. 程序处理流程：预处理-编译-汇编-链接，其中在链接时将多个程序块地址链接并转为逻辑地址

3.2虚拟内存管理

3.2.1概念

传统存储管理方式的特征：

1. 一次性
2. 驻留性

局部性原理：

1. 时间局部性：程序中的某条指令一旦执行，不久后该指令可能再次执行
2. 空间局部性：一旦程序访问了某个存储单元，其附近的存储单元也将被访问

虚拟存储器定义：
基于局部性原理，在程序装入时，仅须将程序当前要运行的少数页面或段先装入内存，而将其余部分暂留在外存，便可启动程序执行。在程序执行过程中，当所访问的信息不在内存时，由操作系统将所需要的部分调入内存，然后继续执行程序。另一方面，操作系统将内存中暂时不使用的内容换出到外存上，从而腾出空间存放将要调入内存的信息。这样，系统好像为用户提供了一个比实际内存容量大得多的存储器，称为虚拟存储器

虚拟存储器特征：

1. 多次性：作业被多次装入内存而不是一次性
2. 对换性：无须在作业运行时一直常驻内存，当需要时从外存载入内存，不需要时内存载入外存
3. 虚拟性（最重要特征）：用户所看到的内存容量远大于实际的内存容量

虚拟内存技术的实现：

• 请求分页管理。
• 请求分段管理。
• 请求段页式管理

虚拟存储技术需要满足以下支持：

1. 页表机制
   由于页表中对应的页框不一定在内存中，页表需要能够检测并处理，因此页表项字段变为：

   1. 页号
   2. 物理块号
   3. 状态位P（合法位）：该页是否在内存中
   4. 访问字段A：该页访问次数
   5. 修改位M：是否修改过，如果修改过需要写回外存
   6. 外存地址：在外存上的地址

2. 中断机构:在请求分页系统中，每当所要访问的页面不在内存中时，便产生一个缺页中断，请求操作系统将所缺的页调入内存。此时应将缺页的进程阻塞（调页完成唤醒），若内存中有空闲块，则分配一个块，将要调入的页装入该块，并修改页表中的相应页表项，若此时内存中没有空闲块，则要淘汰某页（若被淘汰页在内存期间被修改过，则要将其写回外存）。

3. 地址变换机构:地址变换过程加入了缺页中断处理
   

3.2.2请求分页管理方式

3.2.2.1页框分配

1. 驻留集大小
   给一个进程分配的物理页框(物理块)的集合就是这个进程的驻留集，即为进程分配页框(物理块)数量。驻留集就是分配的内存块的地址集合,在缺页替换时从外存将对应块导入对应物理地址内存,页框号没变,但是实际存放的数据页号不同.
   页框越少，可驻留进程多，缺页率高，页框过多依据局部性原理对进程的缺页率没有太明显的影响
2. 内存分配策略
   进程分配物理块方式：
   固定分配和可变分配：固定分配即每个进程拥有的页框数是不变的，可变分配就是会增加或减少
   全局置换和局部置换：全局置换是当进程缺页，系统为该进程增加一个空闲页框作为该缺页，局部置换就是换出一个页，再换入，总页不变。
   • 固定分配局部置换(固定驻留集,局部淘汰策略)：缺页选入一页换出一页
   • 可变分配全局置换(全局淘汰策略)：缺页时增加物理块
   • 可变分配局部置换(驻留集可变,局部淘汰策略)：缺页率高增加物理块，低则在不引起缺页率过高情况下减少物理块
3. 物理块调入算法
   采用固定分配策略时，将系统中的空闲物理块分配给各个进程，可采用下述几种算法
   1. 平均分配算法
   2. 按比例分配算法，根据进程的大小按比例分配物理块
   3. 优先权分配算法，为重要和紧迫的进程分配较多的物理块
4. 调入页面的时机
   1. 预调页策略：调入多页
   2. 请求调页策略：进程请求调入1页
5. 从何处调入页面
   外存分为 存放文件的文件区、用于存放对换页面的对换区
   1. 系统拥有足够的对换区空间：全部从对换区调入所需页面，以提高调页速度
   2. 系统缺少足够的对换区空间：不会被修改的文件都直接从文件区调入，但对于那些可能被修改的部分，将它们换出时须调到对换区
   3. 与进程有关的文件都放在文件区，未运行过的页面都应从文件区调入，曾经运行过但又被换出的页面，放在对换区。共享页面若被其他进程调入内存，则无须再从对换区调入。
6. 如何调入页面
   访问的页面不在内存->向CPU发出缺页中断,转入缺页中断处理程序->查找页表得到该页的物理块->内存未满通过IO将所缺页调入内存，并修改页表->内存已满，按置换算法选出一页换出，该页若被修改则写回磁盘->将缺页调入内存，修改相应页表项->返回地址变换的程序中断处继续执行

3.2.3页面置换算法

OPT最佳置换算法(无法实现)

通过已知的页面引用序列选择最佳策略，将永不使用或最长时间不访问的页面置换。该算法无法实现。但可利用该算法去评价其他算法

FIFO先进先出页面置换算法(维护一个队列)

淘汰在内存中驻留时间最久的页面

请求队列	3	2	1	0	3	2	4	3	2	1	0	4
①	3	2	1	0	3	2	4	4	4	1	0	0
②		3	2	1	0	3	2	2	2	4	1	1
③			3	2	1	0	3	3	3	2	4	4
缺页	1	1	1	1	1	1	1			1	1

请求队列	3	2	1	0	3	2	4	3	2	1	0	4
①	3	2	1	0	0	0	4	3	2	1	0	4
②		3	2	1	1	1	0	4	3	2	1	0
③			3	2	2	2	1	0	4	3	2	1
④				3	3	3	2	1	0	4	3	2
缺页	1	1	1	1			1	1	1	1	1	1

算法实现简单，但与进程实际运行时的规律不适应，且会出现belady现象（增大容量反而会增大缺页率）

LRU最近最久未使用置换算法(2^n个页面需要n个算法位)

每次访问的页面放在首位，缺页时换出最后一位

请求队列	3	2	1	0	3	2	4	3	2	1	0	4
①	3	2	1	0	3	2	4	4	4	1	0	0
②		3	2	1	0	3	2	2	2	4	1	1
③			3	2	1	0	3	3	3	2	4	4
缺页	1	1	1	1	1	1	1			1	1

LRU算法的性能较好，但需要寄存器和栈的硬件支持。LRU是堆栈类的算法

CLOCK时钟置换算法

简单CLOCK(1个访问位):页面在页表将该页设1,页面不在,标记为0的页换出,若标记为1置0,继续向下寻找.

请求队列	3	2	1	0	3	2	4	3	2	1	0	4
①	3(1)	3(1)	3(1)<	0(1)	0(1)	0(1)<	4(1)	4(1)	4(1)<	1(1)	1(1)	1(1)<
②	<	2(1)	2(1)	2(0)<	3(1)	3(1)	3(0)<	3(1)	3(1)	3(0)<	0(1)	0(1)
③		<	1(1)	1(0)	1(0)<	2(1)	2(0)	2(0)<	2(1)	3(0)	3(0)<	4(1)
缺页	1	1	1	1	1	1	1			1	1	1

改进CLOCK(1个访问位,1个修改位)

1. 找(0,0)无访问无修改->找到替换,没有则继续

2. 找(0,1)无访问有修改,访问置0->找到替换,没有则继续

(到这步都是被访问过的)

3. 找(0,0)无修改,访问置0->找到替换,没有则继续
4. 找(0,1),找到替换

优先级:(0,0)>(0,1)>(1,0)>(1,1)

3.2.4抖动和工作集

3.2.4.1抖动

刚刚换出的页面马上又要换入主存，刚刚换入的页面马上又要换出主存 频繁的页面调度行为称为抖动或颠簸
抖动的根本原因：系统中同时运行的进程太多，分配给每个进程的物理块太少，不能满足进程正常运行的基本要求。

3.2.4.2工作集

工作集是指在某段时间间隔内，进程要访问的页面集合。基于局部性原理，可以用最近访问过的页面来确定工作集。一般来说，工作集可由时间t和工作集窗口大小Δt来确定。
分配给进程的物理块小于工作集大小，则该进程就很有可能频繁缺页，所以为了防止这种抖动现象，一般来说分配给进程的物理块数（即驻留集大小）要大于工作集大小。
当所有进程工作集综合超过可用物理块总数，系统会暂停一个进程并调出该进程物理块，防止抖动现象发生

3.2.5内存映射文件

将磁盘文件的全部或部分内容与进程虚拟地址空间的某个区域建立映射关系，便可以直接访问被映射的文件，而不必执行文件I/O操作，也无须对文件内容进行缓存处理。这种特性非常适合用来管理大尺寸文件。

3.2.6虚拟存储器性能影响因素

1. 页面大小
2. 分配物理块数
3. 写回磁盘频率，可以对写回实现惰性执行，只有达到一定限制才写回

易错补充点：

1. FIFO页面置换算法会发生Belady现象，即增大页帧数，缺页率增大
2. 虚拟空间大小由计算机的地址结构绝定
3. 固定分配不可能使用全局置换
4. t时刻工作集为前k个页的集合
5. 系统调用由用户发起，页面置换，进程调度是由操作系统独立处理，创建进程时使用到了系统调用

3.2.7地址翻译

4 文件管理

4.1文件系统基础

4.1.1文件概念

文件是以硬盘为载体的存储在计算机上的信息集合
输入输出中是以文件为基本单位。
文件需要一个文件管理系统进行访问修改保存实现文件管理。
文件需要实现存储空间，索引信息，访问权限。

文件控制块和索引结点

1. 文件属性（文件元数据）

   文件属性保存文件的相关信息，存在差异，一般包括：

   名称 类型 创建者ID 所有者ID 位置 大小 保护 创建时间

2. 文件控制块（FCB）

   用来存放控制文件需要的各种信息的数据结构，一个FCB就是一个文件目录项，FCB的有序集合称为文件目录
   每个新文件创建都会创建FCB存放在文件目录中，作为一个目录项（也是文件）

   主要包含：

   • 基本信息:如文件名、文件的物理位置、文件的逻辑结构、文件的物理结构等。
   • 存取控制信息:包括文件主的存取权限、核准用户的存取权限以及一般用户的存取权限。
   • 使用信息:如文件建立时间、上次修改时间等

3. 索引结点

   文件目录存放于磁盘，使用索引结点替代FCB作为目录项能有效减小文件目录大小，大大节省了系统开销

   磁盘索引结点：存放在磁盘上的索引结点。每个文件有一个唯一的磁盘索引结点

    * 文件主标识符，拥有该文件的个人或小组的标识符
    * 文件类型，包括普通文件、目录文件或特别文件。
    * 文件存取限，各类用户对该文件的存取权限。
    * 文件物理地址，每个索引结点中含有13个地址项，即iaddr(O)〜iaddr(12),它们以直接或间接方式给出数据文件所在盘块的编号。 
    * 文件长度，指以字节为单位的文件长度。
    * 文件链接计数，在本文件系统中所有指向该文件的文件名的指针计数。
    * 文件存取时间，本文件最近被进程存取的时间、最近被修改的时间及索引结点最近被修改的时间
   

   内存索引结点：当文件被打开时，要将磁盘索引结点复制到内存的索引结点中，便于以后使用。在内存索引结点中增加了以下内容

    * 索引结点编号，用于标识内存索引结点。 
    * 状态，指示i结点是否上锁或被修改。
    * 访问计数，每当有一进程要访问此结点时，计数加1；访问结束减1。 
    * 逻辑设备号，文件所属文件系统的逻辑设备号。 
    * 链接指针，设置分别指向空闲链表和散列队列的指针。
   

4.1.2文件操作

4.1.2.1文件的基本操作

1. 创建文件
2. 写文件
3. 读文件
4. 重定向文件
5. 删除文件
6. 截断文件

4.1.2.2文件的打开与关闭

系统中存在一个打开文件表，索引文件表，每个进程也包含一个文件描述符表

当open打开文件时，系统按照文件名搜索文件目录找到文件信息FCB，并复制到系统打开文件表中作为一个表目，表目编号返回用户，之后的文件操作不需要再次访问目录。

为了保证多个进程打开同一文件，每个进程打开文件时在进程的文件描述符表中新增表目（文件描述符fd和文件指针指向系统打开文件表表项），系统打开文件表会通过打开计数器对其计数。当文件打开数为0时删除该文件条目

文件名不必是打开文件表的一部分，因为一旦完成对FCB在磁盘上的定位，系统就不再使用文件名。

4.1.3文件保护

口令保护 加密保护 访问控制

访问类型：

1. 读 从文件中读
2. 写 向文件中写
3. 执行 将文件装入内存并执行
4. 添加 将新信息添加到文件结尾部分
5. 删除 删除文件，释放空间
6. 列表清单 列出文件名和文件属性。
7. …

访问控制：

1. ACL：每个用户配置访问权限
2. 精简的访问列表：
   将用户分为：拥有者 组 其它
   当访问文件时文件主，按照文件主所拥有的权限访问文件；若用户和文件主在同一个用户组，则按照同组权限访问，否则只能按其他用户权限访问。

口令和密码：

通过口令进行访问，但是口令在系统中不安全
密码为文件进行加密，文件被访问时需要使用密钥，保密性强，但是开销大。

注意：

1. 现代操作系统访问控制ACL和用户管理共同实现
2. 目录保护与文件保护不同，需要单独保护

4.1.4文件逻辑结构

4.1.4.1无结构文件（流式文件）

字节（Byte）为单位，用户可以方便地对其进行操作

4.1.4.2有结构文件（记录式文件）

1. 顺序文件

   文件中的记录一个接一个地顺序排列，记录通常是定长的，可以顺序存储或以链表形式存储
   
   顺序文件的效率是所有逻辑文件中最高的，对于顺序存储设备（如磁带），也只有顺序文件才能被存储并能有效地工作。在经常需要查找、修改、增加或删除单个记录的场合，顺序文件的性能也比较差。
   

2. 索引文件

    定长记录文件通过索引获得地址，变长记录文件通过对每个数据建立长度和指针的定长记录表，加快记录索引
   

3. 索引顺序文件

    对索引顺序文件将顺序文件中的所有记录分为若干组，为顺序文件建立一张索引表。
   
    索引表的索引项是对应组的第一个记录的关键字
   
    主文件的组内可以无序但组间有序
   
    通过索引找到对应组，再在组中顺序查找即可
   

4. 直接文件或散列文件（Hash File）

   给定记录的键值或通过散列函数转换的键值直接决定记录的物理地址。这种映射结构不同于顺序文件或索引文件，没有顺序的特性。
   

4.1.5文件物理结构

文件的物理结构决定文件的分配

1. 连续分配

   优点：
   1. 实现简单
   2. 存取速度块
   3. 作业访问磁盘时需要的寻道数和寻道时间最小
   缺点：
   1. 文件长度不宜动态增加
   2. 文件尾后面有其它文件时不能增加长度
   3. 产生外部碎片
   4. 文件大小难以确定

2. 链接分配

   隐式链接：
   文件目录项包含第一个指针和最后一个指针，每个盘块有指向下一个盘块的指针
   优点：消除了外部碎片 无需确定文件大小 缺点：只能顺序访问，随机查找效率低
   改进：将多个盘块设置为簇，按簇分配，减少了查找时间，但是会产生内部碎片。
   显示链接：
   将链接指针从物理块中取出到内存建立磁盘的文件分配表（File Allocation Table FAT），-1为文件尾，-2为空闲。FAT记录文件顺序而且标记空闲盘块。并且查找在内存中减少了磁盘访问次数，提高检索速度。
   
   显式链接包括2个结构：文件目录（存放文件目录项包括文件名和起始块号），FAT文件分配表（块号以及指向的下一块号），查找文件的数据时，查找文件目录找到对应文件，访问起始块，依次按照FAT查找下一块，直到-1。同时可以通过FAT查找空闲块分配空间。

3. 索引分配

   将文件的每个盘块建立一个索引数组，存放在该文件的索引块中，每个文件都有一个索引块。

   优点：支持直接访问 没有外部碎片

   缺点：索引块会增加存储空间开销。

   通过以下方案控制索引块：
   链接索引：多个索引块链接
   多层索引：类似多级页表，第一层索引存放第二层索引块，实现大文件的索引。
   混合索引：多种索引分配相结合
   为了降低访存次数，索引块会加载到内存

4. 混合索引分配

   为了实现不同大小文件的管理，使用多种分配方式。

   UNIX系统中，设置13个地址项，32位计算机中一个数据4B，盘块大小4KB，则一个盘块存放1K个数据，设置10个直接地址，一次间接，多次间接地址。前10个地址可存放40KB数据，当超过时，使用一次简介地址，该盘块存放1K个盘块索引，每个盘块4KB，可存放4MB数据，二次间址存放4G，三次间址存放4T。

易错补充点：

1. UNIX操作系统中，输入/输出设备视为特殊文件
2. FAT文件目录项即FCB，FCB中包括文件的各种信息
3. 用户的访问权限是指用户有没有权限访问该文件，用户优先级是指在多个用户同时请求该文件时的优先顺序
4. FCB中包括了文件的访问控制信息
5. 访问控制机制必须由系统实现，且灵活度高
6. 逻辑索引的目的是加快文件数据的定位，物理索引的主要目的是管理不连续的物理块
7. 链接分配不适合直接存取
8. 设有一个记录文件，采用链接分配方式，逻辑记录的固定长度为100B,在磁盘上存储时采用记录成组分解技术。盘块长度为512B。若该文件的目录项已经读入内存，则对第22个逻辑记录完成修改后，共启动了磁盘（）次。 6次，第22个记录在盘块5，链式分配需要寻找5次，找到后将记录写回直接访问物理地址。

4.2目录

4.2.1目录概念

目录与文件系统和文件集合相关，在多用户系统中，目录需要进行访问控制，文件共享，目录命名等目录管理。

4.2.2目录结构

1. 单级目录结构

   文件系统中只有一个目录表，每个文件占据一个目录项。按名查找访问，新增文件就新增一个文件目录项，并设置信息。删除文件就回收存储空间删除文件目录项。

   查找慢 不能重命名 不能共享 不适应多用户系统

2. 两级目录结构

   设置MFD主文件目录和UFD用户文件目录，MFD中存放每个用户的UFD。用户访问文件时先通过MFD找到UFD再进行访问。解决了重命名问题，提高了查找效率。但缺乏灵活性，不能文件分类。

3. 树形目录结构

   Linux系统的目录结构

   方便分类 层次结构清晰 有效管理和保护文件

4. 有向无环图目录结构

   存在指向同一结点的有向边，可通过共享计数器实现计数

   实现了文件共享，但系统管理变复杂。

   共享不同于复制，复制文件的修改不会改变原文件，而共享文件的修改是同步的。

4.2.3目录操作

1. 搜索
2. 创建文件
3. 删除文件
4. 创建目录
5. 删除目录
6. 移动目录
7. 显示目录
8. 修改目录

4.2.4目录实现

目录存在的目的是实现文件的查找。为了减少IO操作，每次将当前目录加载到内存中操作。

1. 线性列表
   通过线性表实现文件目录，实现简单，链式结构查找费时，线性结构删除费时

2. 哈希表
   使用文件名获取到文件的数据块地址，很容易实现添加删除和查找，需要注意冲突问题。

4.2.5文件共享

1. 硬链接

   实现文件共享的文件索引结点包含文件的属性，并且被共享的用户目录创建目录项，指针指向该共享结点，结点能够对当前链接数进行统计。只要链接数不为0文件就不会被删除。

2. 软链接

   软链接共享的文件只包含被链接文件的路径名，不存在链接。访问时提供路径名进行读取。当创建者移动或删除时访问软链接会失效。

   硬链接的查找速度要比软链接的快

3. 动态链接

   软硬链接属于静态共享，当多个用户对同一文件操作时为动态共享

易错补充点：

1. 主流的文件是使用顺序检索
2. 检索到的是文件的逻辑地址

4.3文件系统

4.3.1文件系统结构

1. IO控制

   包括设备驱动程序和中断处理程序，在内存和磁盘系统之间传输信息。

   是系统与外设硬件的通信操作媒介

2. 基本文件系统

   向IO中的设备驱动程序发送命令进行读写操作，同时对内存进行缓冲区管理。

3. 文件组织模块

   文件组织模块 组织文件及其逻辑块和物理块，是实现逻辑到物理操作的转换

4. 逻辑文件系统

   管理元数据信息（文件系统的所有结构）

   管理目录结构，根据给定文件名称为文件组织模块提供所需要的信息

   通过文件控制块维护文件结构

   负责文件保护

4.3.2文件系统布局

• 文件系统在碰盘中的结构（磁盘分区）
  1. 主引导记录MBR：BIOS读入并执行，MBR读入首个活动块，即引导快
  2. 引导块：存放操作系统的块，每个分区都设置引导块
  3. 超级块：存放文件系统关键信息
  4. i结点（文件的信息），根目录，其他所有的目录和文件…
• 文件系统在内存中的结构
  1. 安装表
  2. 目录结构的缓存包含最近访问目录的信息
  3. 整个系统的打开文件表
  4. 每个进程的打开文件表

创建：

程序通过逻辑文件系统为文件分配FCB，将相应目录读入内存，更新磁盘中的目录

打开

使用open系统调用传入文件名，该函数搜索系统打开文件表，如果存在同名文件，则已使用，在进程打开文件表中创建条目，指向系统打开文件表中的条目。系统打开文件表中的条目能够对当前打开的数量统计。未使用则搜索目录结构找到文件将FCB在系统打开文件表中创建条目，并在进程打开文件表中创建条目指向系统表中条目。文件打开后通过文件描述符访问。

关闭

删除进程表中对应条目，系统表对应条目打开数递减，当全部关闭时，删除系统表中对应条目。更新的元数据（文件属性）写回磁盘

4.3.3外存空闲空间管理

磁盘存在分区，分区可以是盘的部分，也可以是多个盘组成RAID集。每个分区称为卷，分区可以有单独的文件系统。

一个分区中，存放文件数据的空间（文件区）和FCB的空间（目录区）是分离的

文件存储设备分成许多大小相同的物理块，并以块为单位交换信息，因此，文件存储设备的管理实质上是对空闲块的组织和管理，它包括空闲块的组织、分配与回收等问题

磁盘空间分配方法

1. 空闲表法
   与内存的动态分配相似，为所有空闲区建立空闲表，盘的分配可以与内存使用相同的算法如首次适应和最佳适应。盘块回收也如此。
2. 空闲链表法
   空闲盘块链：直接对盘块为单位建链表，盘块回收分配简单，但分配时效率低，链表过长
   空闲盘区链：多个盘块形成一个盘区，盘区需要指向下一个盘区的指针，还需要指明本盘区大小。分配盘区的方法与内存的动态分区分配类似，通常采用首次适应算法。分配与回收的过程比较复杂，但效率通常较高，且空闲盘区链较短
3. 位示图法
   二维表01表示是否空闲
4. 成组链法
   一个盘块存放一组空闲盘块号称为成组链块，将一个成组链块的最后指向的一个空闲盘块再作为成组链块，实现所有空闲盘块均予以链接。
   分配：按第一个成组链块依次分配，到最后一个时将该指向的成组链块读入指向首位继续分配
   回收：成组链块的指针上移一格，再记入回收盘块号。当成组链块的链接数达到顶时，表示己满，便将现有已记录n个空闲盘块号的成组链块号记入新回收的盘块

空闲表法和空闲链表法都不适用于大型文件系统，因为这会使空闲表或空闲链表太大

成组链块或其它记录空闲块的结构需要存放在超级块中

4.3.4虚拟文件系统（VFS）

VFS并不是一种实际的文件系统，它只存在于内存中，不存在于任何外存空间中。VFS在系统启动时建立，在系统关闭时消亡。
包括以下对象：

1. 超级块对象
2. 索引结点对象
3. 目录项对象
4. 文件对象

4.3.5分区和安装

一个磁盘可以划分为多个分区，每个分区都可以用于创建单独的文件系统，每个分区还可以包含不同的操作系统。

文件系统在超级块中，当希望对文件操作时，需要先挂载，即将该分区的超级块中的文件系统安装。

易错补充点：

1. 文件的存储空间管理实质上是对外存空闲区的组织和管理

5 IO管理

5.1概述

5.1.1IO设备

5.1.1.1设备分类

按信息交换的单位分类：

1. 块设备。信息交换以数据块为单位。它属于有结构设备，如磁盘等。磁盘设备的基本特征是传输速率较高、可寻址，即对它可随机地读/写任意一块。第5章 输入/输出（I/。）管理277
2. 字符设备。信息交换以字符为单位。它属于无结构类型，如交互式终端机、打印机等。 它们的基本特征是传输速率低、不可寻址，并且时常采用中断I/O方式。

按传输速率分类，I/O设备可分为：

1. 低速设备。传输速率仅为每秒几•字节到数百字节的一类设备，如键盘、鼠标等。
2. 中速设备。传输速率为每秒数千字节至数万字节的一类设备，如激光打印机等。
3. 高速设备。传输速率在数百千字节至千兆字节的一类设备，如磁盘机、光盘机等。

5.1.1.2IO接口组成

IO接口包括三个部分：

1. 控制器与CPU的接口
   包括数据寄存器，控制寄存器
   与CPU数据线地址线相连
2. 控制器与设备接口
   一个设备有一个或多个设备接口，每个接口都存在数据，控制和状态三种类型的信号
3. IO逻辑
   与地址线和控制线连接，接收地址和控制命令，对命令译码并控制设备。

设备控制器功能：

1. 接收识别CPU命令
2. 控制器与设备，内存之间数据传输
3. 标识报告设备
4. 地址识别
5. 数据缓冲
6. 差错控制

IO端口：I/O端口是指设备控制器中可被CPU直接访问的寄存器

1. 数据寄存器：数据缓冲
2. 状态寄存器：执行结果，设备状态
3. 控制寄存器：启动命令

通信方式：

1. 独立编址：所有IO端口分配IO端口号组成端口空间，只有操作系统通过IO指令才能访问
2. 统一编制，端口分配内存中一个靠近顶端的地址

5.1.2 IO控制方式

1. 程序直接控制方式
   易于实现，CPU利用率低
2. 中断驱动方式
   比直接控制有效，但中断导致CPU消耗高
3. DMA方式
   由DMA实现数据传输过程的控制，只有当数据开始传输和结束时需要CPU控制。数据存放位置和大小由CPU控制
4. 通道控制方式
   使用主机内存，可以同时控制多台设备，同时自主控制数据存放地址和大小

5.1.3 IO软件层次结构

1. 用户层IO软件
   用户可直接调用在用户层提供的、与I/O操作有关的库函数包括。用户层软件必须通过一组系统调用来获取操作系统服务

2. 设备独立性软件

   • 执行所有设备的公有操作，包括：对设备的分配与回收；将逻辑设备名映射为物理设备名；对设备进行保护，禁止用户直接访问设备；缓冲管理；差错控制；提供独立于设备的大小统一的逻辑块，屏蔽设备之间信息交换单位大小和传输速率的差异。
   • 向用户层(或文件层)提供统一接口

3. 设备驱动程序
   发出的操作指令：
   接收上层软件发来的抽象I/O要求处理后发送给设备控制器
   驱动I/O设备工作：
   由设备控制器发来的信号传送给上层软件，隐藏设备控制器之间的差异

4. 中断处理程序
   处理IO中断的程序，中断当前进程，执行IO程序

5. 硬件

5.1.4 应用程序IO接口

根据设备类型不同，有不同的接口

1. 字符设备接口

   以字符为单位 键盘、打印机
   传输速率较低、不可寻址
   通常采用中断驱动方式
   get，put顺序读存取
   设备是独占的

2. 块设备接口

   存取和传输是以数据块为单位 磁盘
   传输速率较高、可寻址
   采用DMA方式
   隐藏了磁盘的二维结构
   将抽象命令映射为低层操作

3. 网络设备接口

   网络套接字接口
   通过套接字建立连接，通过此连接发送和接收数据

4. 阻塞、非阻塞IO

   阻塞IO：执行IO操作时进程阻塞
   非阻塞IO：执行时不阻塞
   通过轮询方式查询IO操作

易错补充点：

1. 设备的固有属性决定了设备的使用方式；设备独立性可以提高设备分配的灵活性和设备的利用率；设备安全性可以保证分配设备时不会导致永久阻塞。设备分配时一般不需要考虑及时性。

2. 计算机系统为每台设备确定一个编号以便区分和识别设备，这个确定的编号称为设备的绝对号。

3. 通道在执行cpu启动io指令时需要回答cpu，只有在完成通道程序时需要中断

4. 设备无关软件是屏蔽逻辑程序和硬件指令的层，接收参数并转为相应指令

5. IO操作流程：CPU启动DMA或通道-DMA对CPU响应-执行设备驱动程序-执行完成后，数据已经在内存中-发出中断请求=CPU执行中断处理程序。

6. 设备无关的软件是I/O系统的最高层软件

5.2设备独立性软件

5.2.1设备无关软件

设备独立性软件包括执行所有设备公有操作的软件。不同操作系统对设备独立软件和驱动程序功能实现不同

5.2.2高速缓存与缓冲区

1. 磁盘高速缓存(Disk Cache)

   利用内存中的存储空间来暂存从磁盘中读出的一系列盘块中的信息

   逻辑上属于磁盘，物理上则是驻留在内存中的盘块

   使用内存中独立的固定分区作为高速缓存，或者将未利用内存作为缓冲池供请求分页系统和磁盘I/O时共享。

2. 缓冲区

• 解决：
  1. CPU与IO速度不匹配矛盾
  2. 减少中断频率，放宽对响应时间
  3. 基本数据单元大小不匹配。
  4. 提高CPU和IO设并行性
• 实现
  硬件缓冲器（成本太高）
  缓冲区
• 缓冲技术
  1. 单缓冲
     初始状态：工作区满，缓冲区空
     单个数据用时max(T,C)+M
     T为输入时间，C为处理时间，M为传送时间
  2. 双缓冲
     初始状态：工作区空，缓冲区1满
     单个数据用时max(T,C+M)
     T为输入时间，C为处理时间，M为传送时间
  3. 循环缓冲
     多个缓冲区链接构成一个环形，通过两个指针形成循环队列结构进行读写操作。
  4. 缓冲池
     包括空缓冲队列、装满输入数据的缓冲队列（输入队列）和装满输出数据的缓冲队列（输出队列）

• 两种缓冲技术对比

5.2.3设备分配与回收

1. 设备分配概述
   分配原则：提高设备使用率，避免死锁
   设备使用方式（设备类别）：独占式（独占设备），分时式共享（共享设备），SPOOLing（虚拟设备）

2. 数据结构

   1. 设备控制表(DCT)
      一个设备一个表，表中为设备属性
   2. 控制器控制表(COCT)
      控制设备与内存交换数据，需要CHCT支持
   3. 通道控制表(CHCT)
      一个通道有多个设备，可以为多个COCT提供服务
   4. 系统设备表(SDT)
      整个系统只有一张SDT，每个物理设备一个表项

3. 设备分配策略

   • 分配原则
     设备分配应根据设备特性、用户要求和系统配置情况。既要充分发挥设备的使用效率，又要避免造成进程死锁，还要将用户程序和具体设备隔离开
   • 分配方式
     • 静态分配：独占设备开始工作前就分配所有的设备。不会出现死锁，但设备的使用效率低
     • 动态分配：系统调用命令申请，一旦用完，便立即释放。高利用率，可能出现死锁

4. 设备分配的安全性

• 安全分配
  每当进程发出I/O请求后便进入阻塞态，直到其I/O操作完成时才被唤醒。获得设备后不再申请保持资源。
  安全 串行工作
• 不安全分配
  设备与CPU同时工作，需要设备即申请，无设备可申请时阻塞
  不安全，可能死锁 可同时操作多设备

5. 逻辑设备名到物理设备名的映射

   在系统中设置一张逻辑设备（Logical Unit Table, LUT）。

   逻辑设备名、物理设备名和设备驱动程序入口地址

   系统单LUT方式和每个用户一个LUT

5.2.4 SPOOLing假脱机

组成：

1. 输入井和输出井
2. 输入缓冲区和输出缓冲区
3. 输入进程和输出进程

作用：

1. 提高了 I/O的速度，缓和了CPU和低速设备之间的速度不匹配的矛盾
2. 独占设备改造为共享设备
3. 实现了虚拟设备功能

5.2.5设备驱动程序接口

要求每个设备驱动程序与操作系统之间都有着相同或相近的接口。这样会使得添加一个新设备驱动程序变得很容易

易错补充点：

1. 缓冲区管理需要对进程同步，缓冲区属于临界资源
2. SPooling结束不需要外围设备
3. 优化文件物理块的分布能改善磁盘设备I/O性能，而在一个磁盘上设置多个分区无影响
4. 每个设备都有相应的驱动程序，对设备的操作都是由驱动程序完成的，也是由驱动初始化的。当设备已占用的时候进程可能进入阻塞

5.3磁盘和固态硬盘

5.3.1磁盘概念

物理结构
主轴 盘片 读写磁头 磁头臂
盘片包括上下两个盘面

磁盘地址用 柱面号（磁道）•盘面号•扇区号
存储的物理块数目由扇区数、磁道数及磁盘面数决定
分类：
可换盘磁盘 固定盘磁盘
固定头磁盘 活动头磁盘

5.3.2磁盘管理

5.3.2.1磁盘初始化

1. 低级格式化
   对空白盘分区，低级格式化为每个扇区使用特殊的数据结构填充磁盘。每个扇区的数据结构由头部、数据区域和尾部组成
2. 分区
   操作系统使用前，需要将自己的数据结构记录到磁盘。具体的先进行柱面分区，然后创建文件系统（逻辑格式化）。并将多个扇区合并为簇（块），一般一簇只能放一个文件。
3. 引导块
   磁盘中存放着完整功能的引导程序，自举程序找到引导程序，引导程序读取分区表，从指定的分区中加载操作系统到内存。具有启动分区的磁盘称为启动磁盘或系统磁盘。
4. 坏块
   磁盘有移动部件且容错能力弱
   简单磁盘手动处理，复杂磁盘维护一个坏块列表，并用备用块逻辑代替坏块（扇区备用）

5.3.2磁盘调度算法

5.3.2.1磁盘操作时间：寻道+旋转+传输

1. 寻道
   $T_s=m*n+s$
   磁头移动速度m，跨越磁道数n，磁臂启动时间s
2. 旋转
   $T_r=1\frac{2r}$
   r为转速，单向移动平均查找为周期的一半
3. 传输
   $T_t=b\frac{rN}$
   字节数b，转速r，磁道字节数N

5.3.2.2磁盘调度

1. 先来先服务FCFS
2. 最短寻找时间优先SSTF
3. 扫描(SCAN)算法(又称电梯调度算法)
4. 循环扫描(Circular SCAN, C-SCAN)
   LOOK调度：磁头移动只需要到达最远端的一个请求即可返回，不需要到达，磁盘端点

通过交错扇区编号减少磁头延迟时间

5.3.3固态硬盘

由闪存块和闪存翻译层（功能同磁盘控制器，实现请求转为设备的读写信号）组成

特点：

1. 闪存块由页组成，读写按页为单位，只有页被擦除后才能写，重复读写会磨损。
2. 随机写、修改慢
3. 随机访问快
4. 没有机械噪声
5. 能耗更低、抗震性好、安全性高

磨损均衡：闪存擦写寿命低，一般是几百次到几千次。通过两种方法均衡

1. 动态磨损均衡：写数据时自动选择较新块
2. 静态磨损均衡：自动数据分配，让老块不进行写数据任务。将新块数据留空。