操作系统复习总结：理论总结- -

操作系统是计算机系统之上的第一层软件，它的功能主要有三点：硬件资源的管理者，对用户的接口，扩充机器。操作系统的主要任务包括：
1.进程管理：包括进程控制（进程的创建，执行，阻塞，终止），进程调度（各种调度算法）和进程通信（高级通信和低级通信），死锁管理；
2.存储器管理：包括内存分配（连续分配，如：单一连续分配，固定分区分配，可变分区分配，运行时动态连续分区分配，以及离散分配方式，如分段，分页，段页），虚拟存储（请求分页，页面置换，抖动消除）；
3.设备管理：包括缓冲区管理，设备的分配（实现设备无关性），驱动程序；
4.文件管理：包括文件在外存上的组织（连续分配，链接分配，索引分配），目录的组织，目录查询技术，文件访问保护；
5.外存管理：包括磁盘调度（各种调度算法），空闲磁盘块管理，磁盘容错技术等。

一、综述

操作系统是计算机系统之上的第一层软件，它的功能主要有三点：硬件资源的管理者，对用户的接口，扩充机器。操作系统的主要任务包括：

1.进程管理：包括进程控制（进程的创建，执行，阻塞，终止），进程调度（各种调度算法）和进程通信（高级通信和低级通信），死锁管理；

2.存储器管理：包括内存分配（连续分配，如：单一连续分配，固定分区分配，可变分区分配，运行时动态连续分区分配，以及离散分配方式，如分段，分页，段页），虚拟存储（请求分页，页面置换，抖动消除）；

3.设备管理：包括缓冲区管理，设备的分配（实现设备无关性），驱动程序；

4.文件管理：包括文件在外存上的组织（连续分配，链接分配，索引分配），目录的组织，目录查询技术，文件访问保护；

5.外存管理：包括磁盘调度（各种调度算法），空闲磁盘块管理，磁盘容错技术;

操作系统分为单道批处理系统，多道批处理系统，单道分时系统，多道分时系统和实时系统。在多处理机上有多处理机操作系统。现代操作系统还有网络操作系统和分布式操作系统。网络操作系统和分布式操作系统主要有一下区别：（1）网络操作系统为集中式控制，控制主要集中在服务器上，分布式操作系统为分布式控制，有各站点均匀承担；（2）网络操作系统不具备任务分配功能，任务在主站上串行执行，分布式系统具备任务分配功能，任务在各站点并行执行；（3）网络操作系统对用户不透明，分布式操作系统对用户透明；（4）网络操作系统是集中式控制，服务器发生故障将导致网络的瘫痪，而分布式操作系统中一个站点发生故障对网络的运行没有影响。

操作系统之上是编译系统，包括编译器，链接器，装载器，以及函数库，之后是用户程序。用户程序先经过编译产生目标程序，在根据它应用的库函数进行连接装配，最后成为可执行文件。绝对地址的可执行文件在装载器装入时按照其绝对地址装入，而支持静态重定位的程序则在装入时由装载器将可执行文件中的各个相对地址改为绝对地址，再行装入；支持动态重定位的程序则是在运行时仍然可以将其在内存中改变位置，可以进行对换。

操作系统中最基本的管理模块形成操作系统内核(kernel)。内核中如果集成了操作系统的所有功能，这样操作系统的所用程序皆出于一个地址空间，这种结构称为强内核(Monolithic)，如UNIX。它在设计上简单，但是不灵活，不易扩充；采用C/S结构，内核中只包含最基本最重要的功能模块，如进程管理，存储管理，设备驱动程序，其余模块和客户程序皆通过消息传递机制与内核通信，这种结构称为微内核(microkernel)，如Windows NT。微内核设计比较灵活，易于修改和扩充，可是进程通信代价较大。除此之外操作系统体系结构还有层式结构和虚拟机结构。

操作系统与用户之间的接口有命令接口和程序接口。命令接口是用户在操作系统Shell中输入命令得到执行，而程序接口则是一系列系统调用。它响应用户需要，完成用户指定的任务。系统调用在执行时通过中断进入，调度器要进行上下文切换，并且在核心态执行。

二、进程管理

进程管理包括进程控制，进程调度，进程同步与通信，死锁控制四个内容。

（一）进程控制

进程是操作系统中运行的基本单位，包括程序段，数据段和进程控制段。操作系统通过进程控制块(PCB)管理进程。每一个PCB唯一标示一个进程。它存储进程的PID,UID，当前状态等信息，以及进程执行某一时刻的寄存器值，并且指向进程的数据段和程序段。OS把所有PCB链接为一个链表。

进程在刚刚被创建时出于new状态。OS负责申请一块存储空间作为该进程的PCB，在其中填上进程的信息，标示为ready，链接到PCB队列和就绪队列中，此时进程进入"就绪"态。进程调度程序在未来某一时刻将其分配给处理机执行，该进程出于"执行"态，OS将根据PCB中的内容初始化处理机的各个寄存器值，之后进入用户态执行；进程请求I/O或系统调用时将放弃处理机，进入"活动阻塞"态，进程调度程序将当前处理机各寄存器值压栈（存入PCB中，或存入核心栈），将该进程PCB运行队列中移入阻塞队列；当系统调用或I/O完成时被唤醒再次进入活动就绪态，即PCB由阻塞队列链入就绪队列。如果在系统调用完成之前，进程被换到外存，相应内存空间被释放，则进程进入"静止阻塞态"，这里中级调度程序将和磁盘驱动程序一起，把相应内容拷贝到对换空间，同时释放内存；系统调用完成时若仍在外存中而为未被换入，则出于"静止就绪"态，之后被换入内存可直接进入执行态，或动态就绪态。进程执行完毕后进入"僵死"态，系统将释放内存空间，回收所有资源。

UNIX系统中提供的系统调用中，fork产生一个与父进程完全相同的子进程，在子进程的地址空间中运行；spawn则从文件中装入一个文件作为子进程，在其地址空间运行；exec则从文件中装一个进程到当前进程地址空间，覆盖当前进程执行。

（二）进程调度
这里说的进程调度主要指低级调度，即由调度程序负责完成的，在内存和处理机之间的调度。在文件和内存之间的调度成为高级调度，又叫作业调度，在内存和对换空间的调度称为中级调度，又称对换。低级调度算法主要有：先来先服务FIFO；.短作业优先SJF；.时间片轮转Round Robin；静态优先级调度；多级队列反馈轮转调度。UNIX系统中采用的动态优先级＋多级队列反馈轮转调度。具体内容可参见前面的文章。

（三）进程通信

进程通信有直接通信和间接通信，直接通信是两进程直接交换数据或发送信息，间接通信则是把信息发送到一个中间实体中。根据同步方式，可分为：1.发送进程阻塞，接受进程阻塞；2.发送进程不阻塞，接受进程阻塞；3.发送进程和接收进程都阻塞。

进程通信也分为高级通信和低级通信。高级通信通常传输数据量较大，包括：消息机制，共享存储区，管道。在消息机制里值得注意的是消息缓冲队列方式。发送进程首先申请一块缓冲区，把消息内容和消息首部填入其中，之后调用send系统调用。send将把该进程的消息内容拷贝到消息缓冲队列中；接受进程首先申请接受缓冲区，之后调用receive系统调用，OS负责把消息缓冲队列中的消息拷贝到该进程空间的缓冲区中。

低级通信包括同步和互斥两种，通过信号量实现，主要针对临界区问题。临界区的互斥访问要遵循4个原则：空闲让进，忙则等待，有限等待，让权等待。主要信号量分为0/1信号量，整型信号量，记录型信号量，AND型信号量和信号量集。经典同步问题有生产者－消费者问题，读者－写者问题，哲学家进餐问题。此处略。

由于进程竞争资源或推进顺序非法，可能会造成进程死锁。死锁有四个必要条件：互斥访问，请求保持，非剥夺，环路等待。打破其中任何一个都可以不出现死锁。对于死锁的处理有三类方法：

1.死锁预防：主要是打破死锁必要条件中的一个。打破请求保持条件，则要求进程在执行之前一次性请求到所有资源才可以执行；打破非剥夺条件，要求进程执行过程中因为缺少资源无法执行时，剥夺所有资源，将其阻塞；打破环路等待条件，则给资源编号，要求进程请求资源的顺序依照编号由高到低进行。

2.死锁避免：指Dijkstra的银行家算法；

3.死锁检测消除：指在发生死锁时检测资源分配图中是否有子环，然后将一个或多个进程挂起，消除死锁；检测算法是NP完全问题，CPU代价较大。

三、存储器管理

存储器管理涉及的内容是存储器的分配，虚拟存储。

（一）存储器分配

存储器分配有一下几种策略：

1.单一分区连续分配：内存中一次只能运行一道程序，将整个用户空间连续的分配给一个进程；

2.固定分区连续分配：内存划分为固定的几块，容纳固定数量的进程同时运行；

3.可变分区连续分配：内存中的空闲空间链接成一个队列，来了一个进程，将它需要的空间从队列中划出给它。检索空闲块的方法有：首次拟合，最优拟合，最差拟合，下次拟合等；以上三种分配方式都有大量外部碎片，可以通过存储紧缩解除；

4.对换：将内存中的进程换到外存，通常遵循连续分配方法，提高对换速度；

5.分页离散存储：将内存空间划分成若干页框，进程划分为若干页面，把一个页面映射到一个页框上，实现离散存储。进程通过<页框号，页内偏移>给出逻辑地址，通过地址变换机构转化为物理地址。地址变换机构是通过页表和页表基地址寄存器实现的，具体变换过程为：页框号×l＋页表基地址，从对应的页表项中读出页框地址，右移加上页内偏移得到物理地址。为了提高地址变换速度，引入相联存储器TLB；为了提高逻辑地址空间，引入多级页表；为了减小页表体积，引入倒转页表（每一个表项存储页框号和PID，每一次地址变换都要检索整个页表）；分页解决了外部碎片问题，但是有内部碎片，平均内部随便大小为页面大小的1/2;分页是一维地址空间；

6.分段离散存储：将进程按照程序员的编程需要分为若干自然段，每一段都连续分配，但是整个进程是离散分配的。这种分配方式仍然具有外部碎片问题；地址变换机构用段表实现；分段时二维地址空间；

7.段页式离散存储：将分段和分页的优点结合起来，进程仍然分为若干段，但是每一段都使用分页存储。这种存储方式下，逻辑地址包括3部分：<段号，页框号，页内偏移>，处理器内配备段表基地址寄存器STR和页表基地址寄存器PTR，但是段表不存储各个段的物理基地址，而存储各个段对应的页表的基地址。因此，根据段号＋[STR]对应的段表中可得到该段页表基地址，加上页框号，对应的页表中存储了该页框的物理地址，左移后加上页内偏移得到物理地址。同样使用TLB提高检索速度。

（二）虚拟存储

虚拟存储是以离散内存分配为基础的。这里主要包括请求调页和页面置换功能。硬件支持包括：页表，缺页中断，地址变换。

实现虚拟存储要在原有的页表上扩充若干域，包括有效位和物理块号，表示该页面是否以调入内存，如果访问一未调入内存的页面，则会产生缺页中断，到对应的磁盘物理块上读入内存；访问位：表明该页面近期是否被访问；修改位：表明该页面最近是否被修改。这两个位主要用于进行页面置换使用。而如果页面根本没有被修改，则置换时根本不需要将其写入外存，而直接释放就可以了。

缺页中断与一般中断不同，它在指令的执行过程中处理，而且在一条指令的执行过程中可能会发生多次中断。发生缺页中断时，原进程被阻塞，OS将首先申请一张页面用于存储即将调入的页面，如果没有空闲存储区，则按照一定的策略进行页面置换，之后，通过页表中存储的磁盘物理块号向磁盘驱动程序请求读。磁盘驱动程序接到请求后，会申请缓冲区，初始化磁盘控制器，启动读，完成后唤醒原进程。原进程唤醒后将页面内容从缓冲区拷贝到以分配的内存页框内，置该页面的有效位为valid，唤醒原进程。原进程从发生中断地那条指令开始重新执行。请求调入的地点，可以是内存中的页面缓冲区，文件，或者对换空间。UNIX为了实现这一点安排了页表，磁盘块描述表，页框数据表，对换使用表4个数据结构来实现。

如果OS在请求页面时无法申请到空闲页面，则要唤醒页面置换进程换出页面。换出页面有两种方式：局部置换方式，只换出该进程的页面；全局置换方式，可以换出其他进程的页面。后者是较好的换出方式，但是可能会造成抖动。抖动的发生是由于多道度的增加使得每一个进程平均分得的页框数较少，当页框数低于每个进程正常执行的工作集时，就会频繁发生缺页和页面置换现象，使得大量时间花费在对外存的读写上，CPU使用率急剧下降的现象。解决此现象的一种方法是工作集算法。它过一段时间记录一下每个进程近期的工作页面数量，确保进程分得的页框数不能低于这个数，否则则选择某一进程换出，从而组织抖动的发生。

页面置换算法有一下以下几种：

1.最优置换算法：选择将来最远不用的页面换出，这是最优算法，但是实际不可行；

2.LRU算法：根据局部性原理选择最近最久不用的算法换出。它性能较好，但是要对每一个页面辅以一个移位寄存器，每过一段时间右移一位，每次被方位时最高位置位。这样，当要换出时，寄存器数值最小的页面就是LRU页面。硬件和软件实现都较为复杂；

3.Clock算法：是LRU的近似算法，仅使用每个页面的访问位。把所有页面连成一个循环链表，从表头开始检索，对于访过的页面，将访问位其复位，找到第一个没有访问的页面将其换出。这种方法又叫NRU算法(not recently used)。

4.改进Clock算法：把页面分为四类，分别为：访问且修改，未访问且修改，访问且未修改，未访问未修改。显然，越向后越是理想换出页面。每次扫面向后降低以及。每次原则最后一类页面换出；

5.LFU算法：硬件要求和LRU一样，但是选择寄存器各位之和最小的换出，表示近期访问次数最少，所以叫Least Frequent Used。

四、设备管理

设备管理包括：缓冲管理，设备分配和设备处理三个内容。

先简单谈一下硬件。进程I/O一共有四种方式：程序查询方式，程序中断方式，DMA方式，通道控制方式。通道处理器也是一个处理机，但是与CPU相比，它指令较为单一，没有独立的存储空间（使用内存空间）。通道分为字节多路通道，数组多路通道和数组选择通道。

（一）缓冲管理
缓冲管理包括单缓冲，双缓冲，循环缓冲和缓冲池。这里需要注意的是缓冲池。它包括输入队列，输出队列和空闲队列，有四种工作方式：

1.收容输入方式：进程请求向缓冲区输入，从空闲缓冲队列中申请一个缓冲区输入，将之链接在输入队列尾；

2.提取输入方式：进程要从缓冲区中提取输入，则从输入队列尾部缓冲区中拷贝信息，同时释放空间，将之重新链入空闲队列中；

3.收入输出方式：进程要想缓冲区输出，从空闲缓冲区队列中申请一个缓冲区输出，将之链接在输出队列尾；

4.提取输出方式：进程要想缓冲区提取输出，则从输出队列尾部缓冲区中拷贝信息，同时释放空间，将之重新链入空闲队列中。

（二）设备分配

操作系统为实现设备分配需要配备的数据结构有：设备使用表，控制器使用表，通道使用表，系统设备表。利用设备独立性的思想分配设备。所谓设备独立性，是指使用逻辑设备名称来请求某种设备，而系统通过某种名称转换方式将其转换成物理设备名称进行分配。实现设备独立性需要再驱动程序之上再增加一层设备独立性软件，负责实现名称和地址的转换，这种转换信息使用逻辑设备表LUT实现，每一个表项存储逻辑设备名，物理设备名，驱动程序入口地址。使用设备独立性方法实现设备分配，具有灵活性和易于设备重定向。

SPOOLing是设备分配的一个重要例子。它实现了独占设备的共享。SPOOLing系统包括输入井，输出井，输入缓冲，输出缓冲，输入进程和输出进程。进程在请求独占设备输出时，OS要求它先把要输出的内容输入到输入缓冲，之后有输入进程将其输入到输入井中，此时如果处理机要处理这些数据，则从输入井中取数据；独占设备要输出时，由输出进程将输出井中的信息送至输出缓冲，由输出设备输出。这种方式实现了独占设备的共享，如网络打印机。

（三）设备处理
设备处理指的是一系列驱动程序。它们是OS与外设的接口，把OS进程发来的抽象的要求转化为对硬件的具体的控制命令，如设置命令控制字，读取设备状态信息，启动设备等。它们对操作系统提供统一的接口，方便用户调用。

五、文件和磁盘管理

文件管理包括：文件在磁盘上的组织；目录的组织，磁盘调度

（一）文件组织

主要有一下几种方式：

1.连续存储：容易产生外部碎片，且文件无法自由生长；文件目录存储每个文件的起始块号和结束块号；

2.链接存储：是离散存储方式，不会产生外部碎片，但是具有内部碎片。有显式链接和隐式链接两种方式。隐式链接是每一个块尾部存储下一个块的指针，缺点是一个链一旦断掉，后面的信息将会丢失，由此引入双向链；显式链接是使用文件分配表（FAT）实现，在磁盘分区开始开辟一段空间，描述磁盘中各个文件的链接信息。在检索文件时需要将整个FAT表调入内存；文件目录中存储指向每个文件FAT表中起始单元和结束单元的指针；

3.索引方式：有单级索引，使用一个磁盘块专门存储该文件各块的索引，目录中存储索引块的地址。这样的检索文件时不需要将整个分区的FAT表全部装入，而是只要装入索引块，但是对小文件造成浪费；多级索引；混合索引：UNIX使用；

（二）目录组织

目录组织有单级，多级，树型，DAG型和图形。文件的共享有两种方式：共享磁盘索引节点，但是文件主在删除文件后会造成共享者的悬空引用；链接共享，使用一个链接文件，存储共享文件的路径名，文件主删除文件后不会造成悬空访问问题，而只是产生"无此文件"异常。

（三）空闲盘块组织

空闲盘块组织有一下几种方式：

1.空闲表法：使用一张表，存储各个空闲块的其实块号，结束块号，块大小；

2.空闲链表发：分空闲盘块链和空闲盘区链。空闲盘块链是以块为单位把各个空闲块拉成链，根据用户请求每次从链首取下若干块；空闲盘区链则是把大小不同的各连续空闲区拉成链，根据用户的请求选择足够大的盘区，分割后分配给它；

3.位视图法：使用2进制数描述所有磁盘块的使用情况，LINUX使用；

4.成组链接法：把磁盘块若干个分为一组，把一组中的各个块号存储在前一组第一个块中，第一组的块号存储在超级块中。UNIX使用。

（四）磁盘调度算法

磁盘调度算法中，FCFS,SSTF(最短寻道时间优先)，SCAN,C-SCAN是基本算法，改进算法有N-Step Scan，F-Scan算法。这里不加详述