操作系统笔记

一、操作系统引论

操作系统的基本特性

并发，共享，虚拟，异步（执行结果不确定，程序不可再现）

操作系统的主要功能

处理机管理功能：进程控制/同步/通信/调度

存储器管理功能：内存分配/保护/扩充/地址映射

文件管理功能：文件存储空间管理、目录管理、文件的读/写管理和保护

操作系统与用户之间的接口

内核功能

支撑功能：中断管理、时钟管理、原语操作

资源管理功能：进程管理、存储器管理、设备管理

二、进程管理

进程

进程是进程实体的运行过程，是系统进行资源分配和调度的一个独立单位

特征：动态性、并发性、独立性、异步性

状态：就绪、执行、阻塞

挂起前：活动就绪/活动阻塞挂起后：静止就绪/静止阻塞

PCB

作用：作为独立运行基本单位的标志、实现间断性运作方式、提供进程管理/调度需要的信息、实现与其他进程的同步和通信。

内容：进程标识符、处理机状态（寄存器）、进程调度信息（优先级等）、进程控制信息（信号量等）

进程同步

临界资源：需要进程互斥访问的共享资源

信号量机制：wait(mutex) 加锁； signal(mutex)解锁。

生产者——消费者：

producer: wait(empty) wait(mutex) 生产 signal(mutex) signal(full)

consumer: wait(full) wait(mutex) 消费 signal(mutex) signal(empty)

哲学家就餐：只有两根筷子可用时才就餐

三、处理机调度与死锁

处理机调度

作业控制块：资源要求、资源使用情况、类型级别、状态...

处理机调度的层次：高级调度、中级调度、低级调度和I/O调度等

高级调度：作业调度，决定把哪些作业调入内存，用于批处理系统，用户最大限度发挥各种资源的利用率

低级调度：进程调度，决定就绪队列中的哪个进程获得处理机，调用最频繁，排队分派上下文切换

中级调度：将暂时不能运行的进程挂起，节省内存资源，在可运行后调回。目的是提高内存利用率和系统吞吐量

高级调度运行频率最低，算法复杂性最高

高级调度+低级调度的调度模型：有后备队列和就绪队列，作业调度决定哪些作业进就绪队列，就绪队列的作业由进程调度决定谁执行，出现等待时间则调入阻塞队列中，等待结束则调入就绪队列。

同时具有三级调度的调度模型：就绪分为内存就绪和外存就绪，阻塞分成内存阻塞和外存阻塞，中级调度可将就绪挂起队列中的调入就绪队列

引起进程调度的因素：进程执行完毕或因事件不能再继续执行；进程提出I/O请求而暂停执行；进程通信或同步。

调度算法

先来先服务FCFS：

按进入系统的先后次序，有利于长作业和cpu繁忙型，不利于IO繁忙型

短进程优先SJF：

运行时长最短的优先，有利于降低作业平均等待时间、提高吞吐量，不利于长进程，不考虑紧迫程度和人机交互

最短剩余时间优先SRT：选择离执行完毕的预期时间最短的进程

优先权调度算法PSA：优先分配处理机给优先权最高的进程

高响应比优先调度算法HRRN：动态优先权，优先权=（等待时间+要求服务时间）/ 要求服务时间

HRRN照顾短作业同时考虑了长作业的等待时间，但要进行响应比计算，增加了系统开销

时间片轮转法RR(q=x)：进程进队列，每个时间片执行队首，时间片结束队首进队尾，q：时间片长度

RR对短的、计算型进程比较有利，用于分时系统

多级反馈队列调度算法FB：统一为抢占式；设置多级队列，下一级的时间片是上一级的一倍，最上级的优先级最高；进程一次时间片结束后就降级。

死锁

定义：一组进程中每一个进程都在等待仅由该组进程中的其他进程才能引发的事件

条件：

互斥条件：资源排他性使用
请求和保持条件：请求其他资源但不释放已有资源
不剥夺条件：资源只能由进程自己释放
循环等待条件：存在一组资源-进程的循环等待链

死锁预防：用很大的限制破坏死锁的必要条件，可能影响运行效率

死锁避免：预测死锁的可能性，动态分配资源

安全状态：存在一个安全序列，使得进程按这个顺序分配资源可以顺利完成

银行家算法：

策略：假设将资源分给进程；检查分配后的系统状态是否安全，安全则确认分配，否则取消分配

中间量：

可利用资源量Available：当前某资源的可用量
最大需求Max：某进程对某资源的最大需求
当前分配量Allocation：当前某进程已分得的某资源的量
当前需求Need：某个进程还需要某资源的量

尝试分配：

确认request小于need
确认request小于available，否则让进程等待
尝试分配资源，计算available、request和need
执行安全性检查

安全性检查：

临时变量：work：系统当前可继续提供的资源的量，开始时=available；Finish：是否有足够资源满足某进程

找到尚未分配（finish==false）且need<=work（有足够资源分配）的进程；
分配（work=work+allocation（也就是释放掉并获得这个进程此前已占有的资源），finish = true）
回到第一步，直到所有进程都得到满足或最终有些进程满足不了

总之，如果找不到一种分配顺序使所有进程得到满足，就是不安全的

安全检查列表：work、need、allocation、work+allocation、finish

此时有进程提出资源请求：判断是否在need范围内、available是否够用，修改available和need，然后进行安全性算法检查。

死锁的检测：化简资源分配图，先看系统剩下多少资源没分配，把不阻塞（有空余资源满足他的）进程的所有边都去掉，并收回他申请的资源；继续化简，直到完全简化或发现没法继续简化为止。如果不能完全简化，则产生死锁

死锁的解除：从其他进程剥夺足够的资源以满足死锁进程；或撤销掉死锁的全部或部分进程。

四、存储器管理

存储器分配

动态分配方式：存储空间位置在作业装入时才确定；在执行过程中可以申请额外空间；执行过程中可以将不需要的空间归还给系统；存储区域大小可变；允许作业的存储空间在内存中迁移。

地址空间：程序用来访问信息所用地址单元的集合，是逻辑地址（相对地址）的集合，由编译程序生成

存储空间：主存中物理单元的集合；单元的标号称为物理地址（绝对地址）。

动态运行时装入：在程序执行时才把相对地址转换为绝对地址，而不是在程序装入时转换。

运行时动态链接：在执行时才将模块链接装入内存，可避免执行中未使用到的模块浪费内存空间

分区分配

单一连续分配：单用户在内存内只有一个进程

分区式分配：系统划分为多个区，一个进程占用一个区

固定分区分配：内存分为固定分区，每个分区只装入一道作业；易于实现开销小，但存在内碎片，限制了并发执行的程序数，空间的利用率低

分区分配算法

最佳适应算法BF：总是选择大小最接近且满足作业要求的区域
优点：划的空间尽量小；缺点：总是产生很小的空白区，且合并困难；实现：空白区按大小递增地链接起来
最坏适应算法WF：总是选择最大的空白区
优点：划分后剩下的空白区最大；缺点：由于最大的块先被使用，所以不利于满足大作业的要求
首次适应算法FF：按地址增序查找第一个满足要求的空白块
优点：简单速度快，低地址满足小作业、高地址满足大作业；缺点：空间利用率低，大空白块查找效率低
下次适应算法NF：同FF，但每次查都从上一次结束的位置开始
优点：不使小块堆在低地址、大块堆在高地址，利用更均衡；缺点：满足大块的可能性降低
快速适应算法QF：将空闲分区根据容量大小分类，每一类设一个空闲分区链表，申请时到对应链表取第一块
优点：查找效率高，不会分割分区产生碎片；缺点：归还算法复杂,一个分区只属于一个进程，存在浪费

伙伴算法

伙伴算法是一种固定分区和动态分区方案的折中

可用内存块的大小为2^k，2^1是最小块的尺寸，2^k是可分配的最大块尺寸。
空闲区按大小分类，相同大小的分区链接为双向链表；最多形成k个链表
请求大小为n的空间：找到i值使2^{i-1}<n\le2^i，进入2^i的链表中寻找，如果找到则分配；如果没有，说明2^i的块耗尽，在2^{i+1}的链表上找一个块，将其拆成两个2^i的分区，一个用于分配，一个插入2^i的链表中

基本分页存储管理

离散分配：程序在内存中不一定连续存放，避免连续分配产生的内外碎片

分页：将程序地址空间分页(page)，每页映射到物理内存中大小固定的一块(frame)

优点：没有外碎片，仅有小于一个页面的内碎片

页面大小一般在1KB-8KB，由机器地址结构决定

页表：每个进程对应1个页表，描述该进程各页对应的物理块号，由操作系统访问和维护

作业表：整个系统1张，记录作业的页表地址等；空闲块表：整个系统一张，记录当前空闲块

快表TLB：为缓存进程页表设置的专用的高速缓存存储器，避免需要两次访问存储器

内存访问有效时间EAT：从请求到取出数据的总时间，如查快表10ns、查内存100ns，则缓存命中的EAT为120ns

二级页表：单级页表可能占用连续的较大空间，所以对页表进行分页并离散存储在物理块中；建立外层页表，指向页表分页的物理块号。4KB二级页表->4MB一级页表->4GB的用户进程，即将页表本身分为页长1K的页面。

具有两级页表的地址变换：逻辑地址=外层页号,外层页内地址,页内地址；多级列表同理。

反置页表IPT：为每一个物理块建一个页表，页表包含访问该块的进程标识、页号等，让页表与物理空间对应而非与逻辑空间对应，避免一个进程一个页表。

反置页表查询过程：给出进程标识和页号（每个进程一套），在整个IPT中查询。若整个反置页表都没有找到匹配的项，则说明该页不在主存，要申请操作系统调入；若找到，则该表项的序号就是物理块号。

反置页表地址变换：逻辑地址=进程pid+页号+页内地址，常通过hash加快查找过程

分段式存储管理

分段思想：程序由若干具有完整逻辑意义的信息段组成，根据分段进行分段共享、分段保护、动态链接、动态增长

分段：作业地址空间按逻辑信息的完整性划分为若干段，每段有段名，从0开始编址、段内空间连续

段表：每个分段分配一个连续分区，各个段离散地移入内存中的不同分区，段表映射段号和段内存起始地址，同时记录段长和RWX权限等

段页式存储管理：结合分段与分页，先将程序分段，每段再划分为若干页，每段内部有连续页号。

段页式存储管理地址变换：逻辑地址=段号,段内页号,页内位移量

段页式优点：结合了分段和分页的优点，既能有效利用存储空间，又能方便用户进行程序设计

虚拟存储器

虚拟存储：实现逻辑扩充，在有限的内存中自动装入更大的程序

虚拟存储器：先将当前要运行的部分程序装入内存，其他部分暂留外存；要执行的指令不在内存时触发中断，通知操作系统从外存调入；内存不足时允许部分程序换入、换出。

虚拟存储器特征：多次性：一个作业可分成多次调入内存；对换性：作业运行中进行换进换出；虚拟性：从逻辑上扩充内存容量，使用户看到的内存容量远大于实际内存容量。

请求分页存储管理：只将作业一部分装入内存，其余在辅存；需要的页不在主存则发出缺页中断将其调入主存，如果主存无空块则选择一个页淘汰以装入新的页面

请求分页存储的硬件支持：请求分页的页表机制；缺页中断机构；地址变换机构。

内存分配策略：如何为进程分配物理块，常用：可变分配全局置换（系统维护一个全局空闲块队列，产生缺页则将其装入，空闲块用完时系统选择全部进程中的一页从内存中调出）

页面置换算法：常用：LRU，换下最久没使用的页面；Clock算法，循环查询，使用过的页面置1，查到时若为0则换出，若为1则置0；改进clock算法：换出首选最近没有被使用过且驻留内存期间没有被修改过的页面

五、I/O系统

I/O系统：用于实现数据输入输出及数据存储的系统

I/O系统的层次式结构：用户层软件->设备独立性软件->设备驱动程序->中断处理程序->硬件

I/O接口：块设备接口：以数据块为单位存取（DMA）；字符设备接口：以字符为单位（中断驱动）；网络接口。

设备控制器

设备控制器：设备不直接与CPU通信，而是由设备控制器控制一个或多个I/O设备，实现设备与计算机的数据交换

设备控制器功能：接收和识别CPU命令，数据交换，设备状态了解，地址识别，数据缓冲，差错控制

设备控制器组成：与cpu：数据线、地址线、控制线；与设备：数据信号线、状态信号线、控制信号线；I/O逻辑

内存映像I/O：不区分内存单元地址和设备控制器中的寄存器地址，可以用访问内存的方法完成I/O操作

I/O通道：一种特殊的处理机，有执行I/O指令的能力，专门负责输入输出工作

中断

中断指CPU对I/O设备发来的中断信号的一种响应，和陷入的区别在强调来源是cpu外

陷入：如运算溢出/程序出错等cpu内部事务引起的中断，执行陷入事件

中断流程：设备启动（进程请求I/O）->I/O完成->设备控制器发送中断->cpu运行中断处理程序

中断处理流程：唤醒被阻塞的驱动程序进程；保护被中断进程CPU环境；转入相应的设备驱动程序；中断处理；恢复被中断进程的现场。

设备驱动程序

功能：接收I/O进程发来的命令和参数，转换为具体要求；检查请求合法性和I/O设备状态，设置设备的相关参数；发出I/O命令并检查设备状态；及时响应由控制器或通道发来的中断请求并处理

特点：驱动程序是请求I/O的进程与设备控制器之间的通信和转换程序；与硬件特性紧密相关，一类设备配备一种驱动程序；驱动程序一部分必须用汇编语言；驱动程序允许可重入。

处理过程：将抽象要求转换为具体要求；检查I/O请求的合法性；读出和检查设备的状态；传送必要的参数；工作方式的设置；启动I/O设备

I/O控制方式：程序I/O方式（忙等）、中断方式、DMA、通道方式（I/O通道负责处理，以内存为中心，cpu只需在开始和结束干预）

设备独立性软件

设备独立性软件即设备无关性软件，引入逻辑设备，实现设备无关性。

基于设备独立性软件，可以执行所有设备的共有操作（设备分配/回收、映射到物理设备名、保护设备、缓冲管理）、向用户层软件提供统一接口（read，write）

设备分配

设备控制表DCT：为每个设备配置一张，记录设备的特性及I/O可控制器连接的情况

控制器控制表：每个控制器配置一张，反应控制器的使用情况和通道的连接状况

通道控制表：每个通道一张，反应通道的使用状态

设备的固有属性：独占性：独占设备同一时间只允许一个进程独占；共享性：允许多个进程同时共享；可虚拟性：虚拟设备是用某种技术把独占设备改造成可由多个进程共享的设备

基本的设备分配程序：分配设备、控制器和通道

请求分配I/O设备流程：通过逻辑设备名，先查逻辑设备表LUT，找到物理设备和设备驱动程序入口地址，再由系统启动设备驱动程序完成信息输出

用户层I/O软件

用户层软件必须使用系统调用来取得操作系统服务

假脱机Spooling技术：将一台物理I/O设备虚拟为多台逻辑I/O设备，允许多个用户共享一台物理设备

Spooling定义：在主机直接控制下实现脱机输入、输出功能，此时外围操作与cpu对数据的处理同时进行

输入井和输出井：磁盘上的两个空间，输入井模拟脱机输入，暂存输入；输出井模拟脱机输出，暂存输出数据

输入缓冲区和输出缓冲区：在内存中，用来缓解cpu与磁盘之间的速度矛盾

输入进程Spi和输出进程Spo：模拟脱机I/O时的外围控制机

井管理程序：用来控制作业和磁盘井之间的信息交换

Spooling输入：进程n请求，Spi为进程n在输入井分配空间，将设备数据由输入缓冲区转到输入井，生成输入请求表挂输入请求队列；当CPU空闲时取出请求表中任务，送进程缓冲区。

Spooling输出：进程n请求，Spo为进程n在输出井分配空间，将数据由进程缓冲区转到输出井，生成打印请求表挂打印请求队列；当打印机（设备）空闲时查打印请求表中的任务，取输出井中对应的数据，送输出缓冲区，打印。

Spooling系统的特点：提高了IO速度，将独占设备改造为共享设备，实现了虚拟设备功能。

缓冲区管理

缓冲作用：缓和CPU与IO设备速度不匹配的矛盾；减少对CPU的中断频率；解决数据粒度不匹配的问题；提高CPU与IO设备之间的并行性

单缓冲：CPU与外设之间轮流使用，一方处理完后要等待对方处理

双缓冲：两个缓冲区，CPU和外设可以同时传送不用等待对方

循环缓冲：多个缓冲区编成一个环，输入和输出在环上追逐

缓冲池：分为块型设备和字符型设备两种，公共缓冲池用于给多个设备和进程服务

磁盘

柱面：所有盘面中处于同一磁道号上的所有磁道

扇区：盘面中的扇形切片

磁盘调度算法：

最短寻道时间优先SSTW：优先选择距当前磁头最近的访问请求。优点：改善了平均服务时间；缺点：产生饥饿
扫描算法SCAN：沿一个方向移动，服务移动过程中遇到的请求，如果该方向还有请求则继续扫描，否则换方向，无请求时不动。优点：既有较好的寻道性能又能防止饥饿问题：可能出现某些请求恰好错过磁头被大大推迟
循环扫描算法CSCAN：总是自里向外移动，到达最后一个柱面后立即返回最里的磁道，返回时不处理服务，返回后再次扫描。

六、文件管理

文件概念

文件建立了字符流到盘块集合的映射关系

文件系统：操作系统中的各类文件、管理文件的软件，以及管理文件所涉及到的数据结构等信息的集合

文件系统功能：

有效地管理文件的存储空间；
管理文件目录；
完成文件的读写操作；
完成文件共享与保护；
为用户提供交互式命令接口和程序调用接口。

数据项：用于描述一个对象的某种属性的字符集

记录：一组数据项的集合，描述一个对象某方面的属性

文件：具有文件名的一组相关记录的集合，是文件系统中最大的数据单位

文件系统模型的三个层次：文件系统接口->对对象操纵和管理的软件集合->对象及其属性

文件操作

文件的创建：分配外存空间，在目录中为之建立一个目录项，目录项中记录文件名和外存地址等属性

文件的打开：系统将指定文件的属性（物理地址等）从外存拷贝到内存打开文件表中的一个表目中，并将该表目的编号（或者叫索引）返回给用户，使用户伺候可以通过索引号向系统提出请求，避免再次检索文件

文件的关闭：将该文件的文件控制块FCB中的有关信息写入外存的目录信息中，删除该文件在打开文件表的表目，释放文件占用的其他系统资源，切断用户与该文件的联系

撤销（删除）文件：删除对应的目录项，回收占用的外存空间

复制文件：拷贝文件内容及目录项。先查找目录文件得到目录项，从目录项得到外存地址，通过外存地址找到文件内容，将目录项和文件内容按指定路径拷贝。

修改文件名：找到其目录项，将其中的文件名修改为新的

读文件：给出文件名和所读字节数，查找目录文件，找到指定目录项，取得外存地址，从该位置开始读取指定字节数到缓冲区，最后返回最新读指针位置

写文件：给出文件名和写的字节数，从缓冲区将指定长度的信息写入写指针位置，顺延写指针

更新文件：从文件查找指定数据项值，若找到则用替换值更新原值

插入操作：在文件的指定位置插入一个数据项。删除操作：删除文件中的指定数据项

文件逻辑结构

逻辑结构：又叫文件组织，是用户可以直接处理的数据及其结构

物理结构：又叫存储结构，是文件在外存上的存储组织形式

有结构文件：顺序文件（定长，字段固定长度相同，可直接读取适合批量处理）、索引文件（不定长，设一个索引表，每个记录设一个索引表项，不可直接读取）、索引顺序文件（和顺序文件一致，但分组，为每组建索引）

无结构文件：即流式文件，长度以字节为单位，采用读写指针来标识下一个访问的字符

文件物理结构

从逻辑组织看：文件由记录组成；从物理组织看：文件由若干数据块组成

外存组织方式：

连续分配：为每个文件分配一组连续盘块，表项记录起始块号和文件长度。优点：访问快缺点：要有连续空间、要事先知道文件长度、不能灵活插入和删除记录、不适应动态增长的文件，会产生磁盘碎片
链接分配：属于同一个文件的盘块链接成一个链表。隐式链接分配：指针存于硬盘目录项；显式：链接物理块的指针显式存放在内存的链接表，整个系统只维护一张FAT表，使查找记录的过程在内存进行优点：可离散存储；缺点：不能高效直接存取、FAT空间占用大
索引分配：用索引表记录分配给该文件的全部盘块号。优点：支持直接访问（可直接根据索引找第i个盘块的盘块号）缺点：索引项里面占用较多空间

目录管理

文件目录是由文件说明索引组成的用于文件检索的特殊文件

文件控制块FCB：存放管理文件所需的所有信息（属性，控制信息等），是文件存在的标志

文件目录：把所有FCB组织在一起，通常以文件的形式保存在外存，叫目录文件

二级目录：目录分为主文件目录和用户文件目录两级

树型目录结构：三级及以上的目录结构，根目录为“/”，每个文件有唯一路径

索引节点：将文件名和文件描述信息分开，将文件的描述信息单独形成索引节点，又叫i结点

按名存取：根据文件名查询文件目录，找到该文件的FCB或i节点；根据FCB或i节点的起始盘块号，计算文件的物理位置

线性检索：沿地址一层层检索

Hash方法检索：根据文件名hash简历索引文件目录，把用户提供的用户名唯一地转换为文件目录的索引值，再利用该索引值到hash索引文件目录中查找。如有冲突，用位移常数法

共享和保护

基于索引节点共享：将共享文件和目录连接到多个用户的目录中，形成有向无环图，共享索引节点来共享文件

基于符号链接共享：共享时在用户目录中创建一个新文件，但该文件只包含被链接文件的路径名，而非索引节点

文件保护：不同对象允许实施的操作不同，操作系统为所有对象规定一个允许进程实施的操作集