操作系统期末复习资料
- 考试题型及分值分布
单选20题/40分、判断10题/20分、解答题4题/40分
- 重点解析
2.1 信号量解决进程互斥与合作P57√
① 信号量定义，初值，取值的含义和变化范围；
② 根据定义的信号量，写出wait和signal原语；
③ 写出相应算法，以保证多进程并发运行。
2.2 页面置换算法比较p174√
系统为进程提供一定数量的页帧，且已知进程在运行过程中访问页面的序列。要求根据相应的置换算法，列出页面淘汰顺序并统计页面置换次数。参与比较的算法是：
① 最佳置换算法P175
② 先进先出算法P175
③ 最近最久未使用算法P176
2.3 进程调度算法比较√
已知系统上运行若干进程及各自的到达时间和服务时间。要求根据相应的进程调度算法求出各进程的执行顺序，平均周转时间和平均带权周转时间。参与比较的算法是：
周转时间 = 完成时间 - 提交时间
平均周转时间 = 各作业周转时间之和 / 作业数
带权周转时间 = 作业周转时间 / 作业运行时间
平均带权周转时间 = 各作业带权周转时间之和 / 作业数
① 先来先服务算法P96
② 最短作业优先算法P97
③ 最高响应比优先算法P98
2.4 分段存储管理的地址转换√
在分段存储管理系统中，逻辑地址形式表述为（段号，段内地址）。已知系统的段表包含段号、内存首地址和段长，要求根据段表的内容完成逻辑地址到物理地址的转换。
3. 知识点总结
3.1 操作系统概述
操作系统的定义P1，四个基本特征P14。
操作系统的定义：
操作系统是配置在计算机硬件上的第一层软件，是对硬件系统的首次补充。
【学小易】操作系统的定义:
操作系统( Operation System ,简称 OS )是控制和管理计算机系统的硬件和软件资源,合理的组织计算机的工作流程,以充分发挥计算机系统的工作效率和方便用户充分而有效地使用计算机资源的一种系统软件。是用户和计算机之间的接口。
四个基本特征：
并发性、共享性、虚拟性、异步性（其中操作系统最基本的特征是共享性和并发性）
3.2 进程的描述与控制
① 进程的定义及组成P15
进程的定义及组成：进程是指在系统中能独立运行并作为资源分配的基本单位，它是由一组机器指令、数据和堆栈等组成的，是一个能独立运行的活动实体。
P39.进程是进程实体的运行过程，是系统进行资源分配和调度的一个独立单位。
程序和进程的区别
【学小易】程序是一组有序的静态指令，进程是一次程序的执行过程；程序可以长期保存，进程是暂时的；进程有状态，程序没有状态；进程有并发特征，程序没有。
进程的四大特征P39
动态性、并发性、独立性、异步性
动态性：进程的实质是进程实体的执行过程，因此，动态性就是进程的最基本的特征。
并发性：是指多个进程实体同存于内存中，且能在一段时间内同时运行。
独立性：在传统的OS中，独立性是指进程实体是一个能独立运行、独立获得资源和独立接受调度的基本单位。
异步性：是指进程是按异步方式运行的，即按各自独立的、不可预知的速度向前推进。
② 进程的状态及状态转换P40-41；
进程的三种基本状态
就绪状态、执行状态、阻塞状态P40
就绪状态、执行状态、阻塞状态、创建状态、终止状态P41
③ 进程的撤销，理解子进程撤销时，应将父进程那儿获得的资源归还父进程；P50
进程撤销就是进程终止
【百度】进程撤销的过程：
- 从PCB集合中检索出该进程的PCB
- 置该进程的状态以提醒处理机重新调度
- 释放该进程的所有资源
- 从相应队列中移出
④ 进程同步的相关概念，包括临界区、临界资源、同步机制遵循的四个规则P52；
进程同步机制：
进程同步机制的主要任务，是对多个相关进程在执行次序上进行协调，使并发执行的诸进程之间能按照一定的规则（或时序）共享系统资源，并能很好地相互合作，从而使程序的执行具有可再现性。
临界区：每个进程中访问临界资源的那段代码成为临界区。P55
【百度】临界区指的是一个访问共用资源（例如：共用设备或是共用存储器）的程序片段，而这些共用资源又无法同时被多个线程访问的特性。当有线程进入临界区段时，其他线程或是进程必须等待（例如：bounded waiting 等待法），有一些同步的机制必须在临界区段的进入点与离开点实现，以确保这些共用资源是被互斥获得使用，例如：semaphore。只能被单一线程访问的设备，例如：打印机。
临界资源：许多硬件资源如打印机、磁带机等都属于临界资源。P53
【百度】多道程序系统中存在许多进程，它们共享各种资源，然而有很多资源一次只能供一个进程使用。一次仅允许一个进程使用的资源称为临界资源。许多物理设备都属于临界资源，如输入机、打印机、磁带机等。
同步机制遵循的四个规则：P55
(1)空闲让进。当无进程处于临界区时，表明临界资源处于空闲状态，应允许一个请求进入临界区的进程立即进入自己的临界区，以有效地利用临界资源。
(2)忙则等待。当已有进程进入临界区时，表明临界资源正在被访问，因而其它试图进入临界区的进程必须等待，以保证对临界资源的互斥访问。
(3)有限等待。对要求访问临界资源的进程，应保证在有限时间内能进入自己的临界区，以免陷入“死等”状态。
(4)让权等待。当进程不能进入自己的临界区时，应立即释放处理机，以免进程陷入“忙等”状态。
⑤ 信号量机制，包括信号量的定义、p、v操作、信号量集的三种特殊情况P57；
信号量的定义：信号量机制是一种卓有成效的进程同步工具。
p、v操作：整型信号量最初被定义为一个用于表示资源数目的整型量S，它与一般整型量不同，除初始化外，仅能通过两个标准的原子操作wait(S)和signal(S)来访问，很长时间以来，这两个操作被称为p、v操作。P58
信号量集的三种特殊情况：P60
(1)Swait(S, d, d)。此时在信号量集中只有一个信号量S,但允许它每次申请d个资源，当现有资源数少于d时，不予分配。
(2) Swait(S, 1, 1)。此时的信号量集已蜕化为一般的记录型信号量(S> 1时)或互斥信号量(S= 1时)。
(3)Swait(S, 1,0)。这是一种很特殊且很有用的信号量操作。当S≥1时，允许多个进程进入某特定区:当S变为0后，将阻止任何进程进入特定区。换言之，它相当于一个可控开关。
⑥ 信号量的应用，包括进程互斥、解决经典进程同步问题；P61 P65-72
⑦ 线程的定义，进程和线程的区别P82。
线程的定义：
【百度】线程是操作系统能够进行运算调度的最小单位。它被包含在进程之中，是进程中的实际运作单位。一个线程指的是进程中一个单一顺序的控制流，一个进程中可以并发多个线程，每个线程并行执行不同的任务。
进程和线程的区别：P82-83
根本区别：进程是操作系统资源分配的基本单位，而线程是任务调度和执行的基本单位。
- 进程是资源分配最小单位，线程是程序执行的最小单位。(2)进程有自己独立的地址空间，每启动一个进程，系统都会为其分配地址空间，建立数据表来维护代码段、堆栈段和数据段，线程没有独立的地址空间，它使用相同的地址空间共享数据。(3)CPU切换一个线程比切换进程花费小；创建一个线程比进程开销小。(4)线程占用的资源要⽐进程少很多。(5)进程对资源保护要求高，开销大，效率相对较低，线程资源保护要求不高，但开销小，效率高，可频繁切换。
【学小易】进程是系统进行资源分配和调度的单位；线程是CPU调度和分派的单位，一个进程可以有多个线程，这些线程共享这个进程的资源。
(1)调度：线程作为调度和分配的基本单位，进程作为拥有资源的基本单位(2)并发性：不仅进程之间可以并发执行，同一个进程的多个线程之间也可并发执行(3)拥有资源：进程是拥有资源的一个独立单位，线程不拥有系统资源，但可以访问隶属于进程的资源.(4)系统开销：在创建或撤消进程时，由于系统都要为之分配和回收资源，导致系统的开销明显大于创建或撤消线程时的开销。
3.3 处理器调度与死锁
① 处理器调度的三个层次，包括高级、低级、中级；P92
[高级调度]
高级调度又称长程调度或作业调度，它的调度对象是作业。其主要功能是根据某种算法，决定将外存上处于后备队列中的哪几个作业调入内存，为它们创建进程、分配必要的资源，并将它们放入就绪队列。高级调度主要用于多道批处理系统中，而在分时和实时系统中不设置高级调度。
[低级调度]
低级调度又称为进程调度或短程调度，其所调度的对象是进程(或内核级线程)。其主要功能是，根据某种算法，决定就绪队列中的哪个进程应获得处理机，并由分派程序将处理机分配给被选中的进程。进程调度是最基本的一种调度， 在多道批处理、分时和实时三种类型的OS中，都必须配置这级调度。
[中级调度]
中级调度又称为内存调度。引入中级调度的主要目的是，提高内存利用率和系统吞吐量。为此，应把那些暂时不能运行的进程，调至外存等待，此时进程的状态称为就绪驻外存状态(或挂起状态)。当它们已具备运行条件且内存又稍有空闲时，由中级调度来决定，把外存上的那些已具备运行条件的就绪进程再重新调入内存，并修改其状态为就绪状态，挂在就绪队列上等待。中级调度实际上就是存储器管理中的对换功能。
② 熟悉进程调度算法与评价指标P92 P96；
进程调度算法是指：根据系统的资源分配策略所规定的资源分配算法。常见的进程调度算法有：
(1)先来先服务调度算法(2)短作业优先调度算法(3)优先级调度算法(4)高响应比优先调度算法
1.CPU利用率
利用率 = 忙碌的时间/总时间
2.系统吞吐量
单位时间内完成作业的数量
3.周转时间 = 完成时间 - 提交时间
平均周转时间 = 各作业周转时间之和 / 作业数
带权周转时间 = 作业周转时间 / 作业运行时间
平均带权周转时间 = 各作业带权周转时间之和 / 作业数
4.等待时间
平均等待时间
5.响应时间
指用户提出请求到得到响应的时间
③ 死锁的原因P112与四个必要条件P116。
死锁的产生原因
1.竞争不可抢占性资源引起死锁
2.竞争可消耗资源引起死锁
3.进程推进顺序不当引起死锁
产生死锁的四个必要条件
2.产生死锁的四个必要条件
(1)互斥条件。进程对所分配到的资源进行排它性使用，即在一段时间内，某资源只能被一个进程占用。如果此时还有其它进程请求该资源，则请求进程只能等待，直至占有该资源的进程用毕释放。
(2)请求和保持条件。进程已经保持了至少一个资源，但又提出了新的资源请求，而该资源已被其它进程占有，此时请求进程被阻塞，但对自己已获得的资源保持不放。
(3)不可抢占条件。进程已获得的资源在未使用完之前不能被抢占，只能在进程使用完时由自己释放。
(4)循环等待条件。在发生死锁时，必然存在一个进程——资源的循环链，即进程集合{P0 P1,P2 ...Pn}中的P0正在等待一个P1占用的资源， P1正在等待 P2占用的资源， ......,Pn正在等待已被P0占用的资源。
3.4 存储器管理
① 理解连续分配存储管理方式，包括单一连续分配P135、固定分区分配P136、动态分区分配P137；
② 逻辑地址和物理地址的含义P150；
【百度】
CPU产生的地址称为逻辑地址；内存单元看到的地址物理地址。
③ 分页和分段存储管理方式P148、P155，学会根据页表或段表，完成逻辑到物理地址转换P150、P158；
④ 虚拟存储器的定义，虚拟存储技术P166；
虚拟存储器：是指具有请求调入功能和置换功能，能从逻辑上对内存容量加以扩充的一种存储器系统。
虚拟存储技术是一种性能非常优越的存储管理技术，被广泛地应用于大、中、小型机器和微型机器中。
⑤ 页面置换算法的含义，缺页中断P174。
【百度】在地址映射过程中，若发现所要访问的页面不在内存中，则产生缺页中断。当发生缺页中断时，如果操作系统内存中没有空闲页面，则操作系统必须在内存选择一个页面将其移出内存，以便为即将调入的页面让出空间。而用来选择淘汰哪一页的规则叫做页面置换算法。
3.5 输入输出系统
① I/O系统的四个层次，设备驱动程序的含义P193；
(1)用户层I/O软件
实现与用户交互的接口，用户可直接调用该层所提供的，与I/O操作有关的库函数对设备进行操作。
(2)设备独立性软件
用于实现用户程序与设备驱动器的统一接口、设备命名、设备的保护以及设备的分配与释放等，同时为设备管理和数据传送提供必要的存储空间。
(3)设备驱动程序
与硬件直接相关，用于具体实现系统对设备发出的操作指令，驱动I/O设备工作的驱动程序。
- 中断处理程序
用于保存被中断进程的CPU环境，转入相应的中断处理程序进行处理，处理完毕再恢复被中断进程的现场后，返回到被中断的进程。
② I/O通道的含义P200；
【百度】I/O通道是一种特殊的处理机。它具有执行I/O指令的能力，并通过执行通道(I/O)程序来控制I/O操作。
③ I/O设备的控制方式，对比中断驱动I/O方式和直接存储器访问（DMA）方式，如数据传输的基本单位不同P209；
(1)使用轮询的可编程I/O方式
(2)使用中断的可编程I/O方式
(3)直接存储器访问方式
(4)I/O通道控制方式
中断驱动I/O方式和直接存储器访问（DMA）方式的对比
【学小易】
(1)中断I/O方式请求的是CPU处理时间，DMA方式请求的是总线使用权
(2)中断响应发生在一条指令执行结束后，DMA响应发生在一个总线事务完成后
(3)中断I/O方式下数据传送通过软件完成，DMA方式下数据传送由硬件完成
【百度】
中断需要CPU参与，DMA不需要CPU参与。
④ 缓冲区的四个意义P224；
(1)缓和CPU与I/O设备间速度不匹配的矛盾
(2)减少对CPU的中断频率，放宽对CPU中断响应时间的限制。
(3)解决数据粒度不匹配的问题
(4)提高CPU和I/O设备之间的并行性
⑤ 磁盘访问时间由三个部分时间构成，传输时间的相对占比比较小P232。
(1)寻道时间Ts
(2)旋转延迟时间Tτ
(3)传输时间Tt
3.6 文件管理
① 文件管理的基本概念，包括文件名、记录、文件系统P237-242；
文件系统的管理功能是将其管理的程序和数据通过组织为一系列文件的方式实现的。
文件管理系统包括多个文件系统
【百度】文件管理是操作系统中一项重要的功能。其重要性在于，在现代计算机系统中，用户的程序和数据，操作系统自身的程序和数据，甚至各种输出输入设备，都是以文件形式出现的。可以说，尽管文件有多种存储介质可以使用，如硬盘、软盘，光盘，闪存，记忆棒，网盘等等，但是，它们都以文件的形式出现在操作系统的管理者和用户面前。
文件管理是操作系统的五大职能之一，主要涉及文件的逻辑组织和物理组织，目录的结构和管理。所谓文件管理，就是操作系统中实现文件统一管理的一组软件、被管理的文件以及为实施文件管理所需要的一些数据结构的总称(是操作系统中负责存取和管理文件信息的机构)从系统角度来看，文件系统是对文件存储器的存储空间进行组织，分配和回收，负责文件的存储，检索，共享和保护。从用户角度来看，文件系统主要是实现"按名取存"，文件系统的用户只要知道所需文件的文件名，就可存取文件中的信息，而无需知道这些文件究竟存放在什么地方。
② 文件的逻辑结构可以根据结构划分：有结构（或记录式文件）和无结构（或流式文件）P243；
③ 文件的逻辑结构可以根据组织方式划分：顺序文件，索引文件和索引顺序文件P243；
④ 文件的目录可以分为三类：单级目录，二级目录，树形目录★P252-257；
⑤ 路径名的相关概念，包括绝对路径、当前目录P254。