操作系统复习资料

第一章 操作系统概论

操作系统的目标:方便性，有效性，可扩充性，开放性。 操作系统的作用有：作为用户与计算机硬件系统之间的接口，作为计算机系统资源的管理者，用作扩充机器。

用户使用计算机的三种方式：命令方式，系统调用方式，图形、窗口方式。 资源分为四种：处理器，存储器，I/O设备，信息（数据和程序）。

推动操作系统发展的主要动力有：不断提高计算机资源利用率，方便用户，器件的不断更新换代，计算机体系结构的不断发展。

操作系统同计算机系统发展的几个阶段：无操作系统的计算机系统，单道批处理系统，多道批处理系统，分时系统，实时系统。

操作系统:一组控制和管理计算机硬件和软件资源，合理地对各类作业进行调度，以及方便用户使用的程序的集合。

分时系统是指:在一台主机上连接了多个带有显示器和键盘的终端，同时允许多个用户通过自己的终端，以交互方式使用计算机，共享主机中的资源。

实时系统是指，系统能及时（或即时）响应外部事件的请求，在规定的时间内完成对该事件的处理，并控制所有实时任务协调一致地运行。

实时任务可分为:周期性实时任务和非周期性实时任务，也可分为硬实时任务和软实时任务。 操作系统都具有四个基本特征：（程序）并发，（资源）共享，虚拟和异步。

并行性指:两个或多个事件在同一时间发生，并发性指两个或多个事件在同一时间间隔内发生。

共享指:系统中地资源可供内存中多个并发执行的进程（线程）共同使用，可分为互斥共享方式和同时访问方式。

虚拟指:通过某种技术把一个物理实体变为若干个逻辑上的对应物。 如果n是某物理设备所对应的虚拟的逻辑设备数，则虚拟设备的平均速度必然是物理设备速度的1/n。

操作系统的功能：处理机管理，存储器管理，设备管理和文件管理。 处理器管理包括：进程控制，进程同步，进程通信，调度。 存储器管理包括：内存分配，内存保护，地址映射，内存扩充。 设备管理包括：缓冲管理，设备分配，设备处理。

文件管理包括：文件存储空间管理，目录管理，文件的读写管理和保护。 操作系统向用户提供的接口有：命令接口，程序接口，图形接口。

操作系统的结构发展：无结构，模块式结构，层次式结构，微内核OS结构。 软件:指当计算机运行时，能提供所要求的功能和性能的指令和程序的集合。

微内核技术是:精心设计的、能实现现代OS核心功能的小型内核，它与一般的OS（程序）不同，它更小更精炼，它不仅运行在核心态，而且在开机后常驻内存，它不会因内存紧张而换出内存来。

微内核提供的通常都是一些最基本的功能：进程管理，存储器管理，进程通信管理，低级I/O功能。

第二章 进程管理

程序顺序执行的特征：顺序性，封闭性，可再现性。

前趋图:是一个有向无循环图，DAG，用于描述进程之间执行的前后关系。 进程的实体:由程序段、相关的数据段和进程控制块PCB构成。 创建和撤消进程都是指:创建或撤消进程中的PCB。 进程具有:动态性、并发性、独立性和异步性的特征。

进程是:进程实体的运行过程，是系统进行资源分配和调度的一个独立单位。 进程的三种基本状态是:就绪状态、执行状态和阻塞状态（等待状态）。（见P31图2-5） 系统根据PCB控制进程，PCB:是进程存在的唯一标志。PCB常驻内存，系统将所有PCB组织成若干链表（或队列），存放在操作系统专门开辟的PCB区内。

进程控制块PCB主要包括四方面的信息:进程标识符（内部标识符和外部标识符），处理机状态（一些寄存器中断时的信息），进程调度信息，进程控制信息。

进程控制块的组织方式通常有:链接方式（指针链接）和索引方式（索引表）两种。 PCB中都设置了:家族关系表项，以标明自己的父进程及所有的子进程。

进程创建进程的典型事件可分为四类：用户登录，作业调度，提供服务，应用请求。 进程创建步骤：1申请空白PCB，2分配资源，3初始化PCB，4插入就绪队列。 初始化进程控制块包括：初始化标识信息；初始化处理机状态信息；初始化处理机控制信息。 引起进程终止的事件有：正常结束，异常结束，外界干预。

进程终止步骤：1根据被终止进程的标识符，在PCB集合中检索出该进程的PCB，读取其状态，2若处于执行状态，立即终止，置调度标志为真，用于指示该进程被终止后应重新进行调度，3如果有的话，终止所有子进程，4将被终止进程拥有的全部资源归还其父进程或系统，5将被终止进程PCB从所在队列（或链表）中移出，等待其他程序来搜集信息。 引起进程阻塞或唤醒的条件：请求系统服务，启动某种操作，新数据未到，无新工作做。 进程阻塞过程：调用阻塞原语block把自己阻塞，如在执行状态，立即停止执行，修改PCB中状态为“阻塞”，PCB插入阻塞队列。转调度程序将CPU重新调度给另一就绪进程。 进程唤醒过程：调用唤醒原语wakeup，将被阻塞的进程从等待该事件的阻塞队列中移出，将PCB中状态改为“就绪”，将PCB插入到就绪队列中去。

进程挂起过程：调用挂起原语suspend，如进程为活动就绪状态就改为静止就绪，如活动阻塞状态就改为静止阻塞，如进程正在执行就转向调度程序重新调度。

进程激活过程：调用激活原语active，先将进程从外存调入内存，如进程为静止就绪就改为活动就绪，如静止阻塞就改为活动阻塞，判定新就绪的进程的优先级是否能抢夺CPU。 进程之间包括:互斥和同步两种关系。

进程同步的主要任务:是使并发执行的诸进程之间能有效地共享资源和相互合作，从而使程序的执行具有可再现性。

临界区CS（critical section）是指:每个进程中访问临界资源的那段代码。 临界区前面用于检查是否能访问临界资源的代码叫进入区，后面加上一段代码退出区用于恢复标志，其余的代码部分叫做剩余区。

进程同步可以采用:信号量机制和管程机制。

同步机制遵循的原则：空闲让进，忙则等待，有限等待，让权等待。

记录型信号量:采用wait(S)和signal(S)来防止类似整型信号量会导致的忙等。 AND型信号量采用:Swait(S1,S2,?Sn)和Ssignal(S1,S2,?Sn)来防止死锁。 信号量集用:Swait（S,t,d）表示，S为信号量，t为下限值，d为需求值。 例子：利用信号量实现前趋关系。（P45，图2-10） 例子：利用记录型信号量解决生产者－消费者等问题。（P46）

一个管程定义了:一个数据结构和能为并发进程所执行（在该数据结构上）的一组操作，这组操作能同步进程和改变管程中的数据。

管程由三部分组成：局部于管程的共享变量说明；对该数据结构进行操作的一组过程；对局部于管程的设置初始值的语句。

例子：利用管程解决生产者－消费者问题。（P52）

进程通信包括:低级通信（进程之间的互斥和同步）和高级通信（共享存储器系统，消息传

递系统以及管道通信系统），又可分为直接通信（通信原语）和间接通信（信箱）。

高级进程通信:是指用户可直接利用操作系统所提供的一组通信命令，高效的传送大量数据的一种通信方式。可归结为三大类：共享存储系统、消息传递系统以及管道通信系统。 管道通信具有三方面的协调能力：互斥，同步，确定对方是否存在。 进程通信可分为直接通信方式和间接通信方式。

直接通信方式指:利用OS提供的发送命令，直接把消息发送给目标进程。通常系统提供两条通信命令（原语）：Send（Receive,Message）和Receive（Sender,Message）。

间接通信方式指:进程之间的通信需要通过作为共享数据结构的实体，通常称之为信箱。 信箱可分为:私用信箱（单向通信链路的信箱），公用信箱（双向通信链路的信箱）和共享信箱。拥有私用信箱的进程结束时，信箱随之消失。公用信箱在系统运行期间始终存在。 公用信箱和共享信箱的区别在于:公用信箱是由操作系统创建，并提供给系统中的所有核准进程使用的。而共享信箱是由某进程创建给它和其他指定共享进程使用的。

两种方式建立一条通信链路：用显式的“建立连接”命令原语请求系统为之建立（常用于计算机网络中）；利用发送命令原语，系统自动为之建立（常用于单机系统中）。

通信链路可分为：点对点连接通信链路和多点连接链路；单向通信链路和双向链路；无容量通信链路（无缓冲区）和有容量通信链路（有缓冲区）。

消息分为消息头（控制信息）和消息正文（实际上发送的数据）。

进程同步方式有：1发送进程阻塞，接收进程阻塞（又称为汇合）2发送进程不阻塞，接收进程阻塞3发送进程接收进程都不阻塞。

消息缓冲队列通信机制及其中的发送原语和接收原语。（P59）

在操作系统中引入线程:是为了减少程序在并发执行所付出的时控开销，使操作系统具有更好的并发性。

在多线程OS中，通常是:在一个进程中包含多个线程，每个线程都是作为利用CPU的基本单位，是花费最小开销的实体。

线程具有以下属性：轻型实体，独立调度和分派的基本单位，可并发执行，共享进程资源。 线程的状态：状态参数和运行状态（也有执行状态，就绪状态，阻塞状态）

线程被中止后并不立即释放它所占有的资源，只有当进程中的其它线程执行了分离函数后，被终止的线程才与资源分离，此时的资源才能被其他线程利用。

多线程OS中的进程：进程仍是系统分配资源的基本单位，每个进程都含有多个相对独立的线程，进程不是一个可执行的实体，而是把线程作为独立运行的基本单位。所谓进程处于“执行”状态，实际上是指该进程中的某线程正在执行。把某个进程挂起或激活，该进程的所有线程也都被挂起或激活。

线程同步和通信机制有：互斥锁，条件变量，信号量机制。

互斥锁适合于:高频度使用的关键共享数据和程序段，关锁lock和开锁unlock操作mutex 每个条件变量通常都和一个互斥锁一起使用,线程首先对mutex执行关锁操作，若成功便进入临界区，然后查找用于描述该资源状态的数据结构，以了解资源的情况。只要发现所需资源R正处于忙碌状态，线程便转为等待状态，并对mutex执行开锁操作后，等待资源被释放；若资源处于空闲状态，表明线程可以使用该资源，于是将该资源设置为忙碌状态，再对mutex执行开锁操作。

线程的实现方式有:用户级线程和内核支持线程。

内核支持线程是:无论是用户进程中的线程还是系统进程中的线程，他们的创建、撤消和切换等，都是依靠内核实现的。此外，内核空间中还每个线程设置了一个线程控制块。

用户级线程仅存在于用户空间中。这种线程的创建、撤消、同步等都无须利用系统调用来实现。所以线程的切换速度特别快。内核完全不知道用户级线程的存在。

用户级线程的调度以:进程为单位，而内核支持线程的调度以线程为单位。 用户级线程的实现可分为:运行时系统和内核控制线程。 第三章 处理机调度和死锁

高级调度又称为:作业调度或长程调度，用于决定把外存上处于后备队列中的哪些作业调入内存，并为它们创建进程，分配必要的资源，然后，再将新创建的进程排在就绪队列上。 低级调度称为:进程调度或短程调度，用来决定就绪队列中的哪个进程应获得处理机，然后再由分派程序执行把处理机分配给该进程的具体操作。

进程调度可分为非抢占方式和抢占方式（优先权原则/短作业优先原则/时间片原则）。 中级调度又称:中程调度。引入中级调度的主要目的是为了提高内存利用率和系统吞吐量，实际上就是存储器管理中的对换功能。

三种调度队列模型：仅有进程调度的调度队列模型，具有高级和低级调度的调度队列模型，同时具有三级调度的调度队列模型。

调度算法是指：根据系统的资源分配策略所规定的资源分配算法。 先来先服务调度算法（FCFS），短作业（进程）优先调度算法（SJF），高优先权优先调度算法，基于时间片的轮转调度算法。（P76）

高优先权优先调度算法分为:非抢占式优先权算法和抢占式优先权调度算法。 优先权分为:静态优先权和动态优先权。

基于时间片的轮转调度算法可分为:时间片轮转法和多级反馈队列调度算法。

实现实时调度的条件：提供必要的信息，系统处理能力强，采用抢占式调度机制，具有快速切换机制。

抢占调度的时机可在时钟中断发生的时候或者立即抢占。 实时调度算法：最早截止时间优先算法（EDF），最低松弛度优先算法（LLF）。（P84） 多处理器系统可分为:紧密耦合MPS（通过高速总线或高速交叉开关）和松弛耦合MPS（通过通道或通信线路）。

多处理器系统可分为:对称MPS（所有处理器都一样）和非对称MPS（一主多从）。

多处理器的进（线）程调度方式有：自调度方式、成组调度方式和专用处理器分配方式。 产生死锁的原因有：竞争资源、进程间推进顺序非法。

死锁的发生必须具备四个必要条件：1互斥条件，2请求和保持条件，3不剥夺条件，4环路等待条件。

处理死锁的基本方法有：预防死锁，避免死锁，检测死锁，解除死锁。

预防死锁的方法是使以上四个必要条件中的2，3，4不成立，如静态分配，有序分配。 安全序列是指:系统能按某种进程顺序来为每个进程Pi分配其所需资源，直至满足每个进程对资源的最大需求，使每个进程都可顺利完成。 避免死锁：例子：银行家算法避免死锁。（P95）

检测死锁：死锁定理：当且仅当S状态的资源分配图使不可完全简化的。（P99） 解除死锁：死锁解除可以通过剥夺资源和撤消进程（最小代价进程撤消法）。 第四章 存储器管理

创建进程的第一件事便是:将程序和数据装入内存。

将一个用户源程序变为一个可在内存中执行的程序:首先要编译，由编译程序将用户源代码编译成若干目标模块；其次是链接，由链接程序将目标模块和需要的库函数链接在一起形成一个完整的装入模块；最后是装入，由装入程序将装入模块装入内存。

将装入模块装入内存的方式有：绝对装入方式，可重定位装入方式和动态运行时装入方式。 采用可重定位装入程序将装入模块装入内存后，会使装入模块中的所有逻辑地址与实际装入内存的物理地址不同。在装入时对目标程序中的指令和数据的修改过程成为重定位。

动态运行时装入，在把装入模块装入内存后，并不立即把装入模块中的相对地址转换为绝对地址，而是把这种地址转换推迟到程序真正要执行时才进行，该方式需要一个重定位寄存器的支持。

链接的方式有：静态链接，装入时动态链接和运行时动态链接。 连续分配方式是指为:一个用户程序分配一个连续的内存空间，进一步可分为单一连续分配，固定分区分配，动态分区分配以及动态重定位分区分配四种方式。 单一连续分配是:把内存分为系统区和用户区两部分。

固定分区分配是:将内存用户空间划分为若干固定大小（分区大小可等可不等）的区域，每个分区只装一道作业。

通常按分区大小排队:建立一张分区使用表，给程序一个能满足要求又尚未分配的分区。 动态分区分配中的数据结构可采用:空闲分区表和空闲分区链两种。 分区分配算法有:首次适应算法，循环首次适应算法和最佳适应算法。

最佳适应算法是:将空闲分区大小从小到大形成一个链，最先适应的必然是最佳的。但是这种分配算法通常会导致切割下来的剩余空间最小，而产生许多难以利用的小空闲区。

分配内存时看:是否剩下的空间大于事先规定的不再切割的剩余分区的大小，而回收内存时根据前后是否是空闲分区决定是否需要合并。

动态重定位分区分配是:指将空闲分区紧凑成连续空闲区分配给需要的程序，同时修改有关数据结构使已经被分配空间的程序能继续正常运行。 “对换”，是指:把内存中暂时不能运行的进程或暂时不用的程序和数据，调出到外存上，以便腾出足够的内存空间，再把已具备运行条件的进程或进程需要的程序和数据调入内存。 以整个进程为单位的对换称为:“整体对换”或“进程对换”。以“页”或“段”为单位的对换分别称为“页面对换”或“分段对换”。

为实现进程对换，系统必须具有以下功能：对换空间的管理，进程的换出，进程的换入。 将一个进程直接分散装入到许多不相邻接的分区中，则无须再进行“紧凑”，此谓离散分配方式，离散分配的基本单位是“页”或“段”，对应于分页/段存储管理方式。

分页存储管理是:将一个进程的逻辑地址空间分为若干大小相等的片，称为页面或页。 分页大小应适中，太小会使进程的页表过长，占用大量内存；太大会使页内碎片增大。 分页地址中的地址分为两部分:前一部分为页号P，后一部分为位移量W（页内地址）。 系统为每个进程建立了一张页面映象表，简称页表，其作用是实现页号到物理块号的映射。即使在最简单的页表系统中，也设置一存取控制字段，用于保护该存储块中的内容。

地址变换机构的任务:只是将逻辑地址中的页号，转换为内存中的物理块号。地址变换的任务就可以借助于页表来完成。

页表通常驻留在内存中，而系统中只设置一个页表寄存器PTR来实现页表功能。 “快表”又称:“联想寄存器”，是为了:提高地址变换速度而增设的一个具有并行查寻能力的特殊高速缓冲寄存器。此时，在CPU给出有效地址后，首先将页号与联想寄存器中的页号对比，如果有，就直接读出对应物理块号送物理地址寄存器，若无再访问内存中的页表。 两级页表和多级页表是为了:防止页表占有太大内存空间而对页表结构再进行分级。

分段存储管理方式的引入主要是为了满足以下需要：方便编程，信息共享，信息保护，动态增长，动态链接。

分段存储管理方式中，作业的地址空间被划分为:若干个段，每个段定义了一组逻辑信息。例如，有主程序段MAIN，子程序段X，数据段D及栈段S等。 段的长度由:相应的逻辑信息组的长度决定，因而各段长度不等。

段的数据结构可分为两部分:段号和段内地址。一般情况下，段比页大。 系统为每个进程建立了一张段表，用于实现从逻辑段到物理内存区的映射。

百度搜索“77cn”或“免费范文网”即可找到本站免费阅读全部范文。收藏本站方便下次阅读，免费范文网，提供经典小说综合文库操作系统复习资料在线全文阅读。