计算机操作系统期末考试复习重点

一、选择题（2*10）

1、 分时系统：特征1、多路性 2、交互性 3、独立性 4、及时性

实现分时系统的关键问题是什么?应如何解决?

关键问题：及时接收，及时处理; 对于及时接收，只需在系统中设置一多路卡，多路卡作用是使主机能同时接收用户从各个终端上输入的数据；对于及时处理，应使所有的用户作业都直接进入内存，在不长的时间内，能使每个作业都运行一次.

试说明推动分时系统形成和发展的主要动力是什么?

用户的需要.即对用户来说，更好的满足了人-机交互，共享主机以及便于用户上机的需求.

优点：1、为用户提供了友好的接口 2、促进了计算机普遍使用，为多个终端服务 3、便于资源共享和交换信息

2、 计算 (已知两个求另一个）

例、有3个进程，每个进程最多需要4个资源，不会死锁的最小资源是3*3+1=10个

有7个进程，每个进程最多需要8个资源，不会死锁的最小资源是7*7+1=50个

3、 同步机制遵循的规则：1.空闲让进 2、忙则等待 3、有限等待 4、让权等待

4、 产生死锁的必要条件：1）互斥条件：摒弃 2）请求和保持条件：3）不剥夺条件4）环路等待条件

发生死锁的必要条件有四个，要防止死锁的发生，可以破坏这四个必要条件，但破坏互斥条件是不太实际的。 预防死锁：通过破坏四个必要条件之一。分析四个必要条件：1（不可破且要保证） 2，3，4可破（三种方法）。

解决不可剥夺方法：摒弃 便不可剥夺为可剥夺；；请求与保持解决方法：请求时不保持，保持时不摒弃

环路等待解决方法：为设备编号从小号开始申请

请详细说明可通过哪些途径预防死锁?

a. 摒弃"请求和保持"条件，就是如果系统有足够的资源，便一次性地把进程所需的所有资源分配给它；

b. 摒弃"不剥夺"条件，就是已经保持了资源的进程，当它提出新的资源请求而不能立即得到满足时，必须释放它已经保持的所有资源，待以后需要时再重新申请；

c. 摒弃"环路等待"条件，就是将所有资源按类型排序标号，所有进程对资源的请求必须严格按序号递增的次序提出.

5、很好地解决了"零头"问题的存储管理方法是.页式存储管理（无外有内.）B.段式存储管理（无内有外）

C.固定分区管理（严重内零头） D.动态分区管理（无内有外）连续分配分为固定分区分配（存在内零头）和动态分区分配（外零头）。。分段分配（存在外零头）

6.。磁盘调度算法：1）先到先服务（FCFS）：仅适用于请求磁盘I/O的进程数目较少的场合。

2）最短寻道时间优先（SSTF）：其要求访问的磁道与当前磁头所在的磁道距离最近，以使每次的寻道时间最短。但这种算法不能保证寻道时间最短。会导致“饥饿”现象，出现“磁臂黏着”现象。

3）扫描算法（SCAN） ：是改良的SSTF算法，可以避免“饥饿”现象但是会有“磁臂黏着”现象。。

4）循环扫描（CSCAN）：会出现“磁臂黏着”现象。

5）NStepSCAN算法：避免出现“磁臂黏着”现象。

7、设备分配中的数据结构：①、设备控制表DCT；系统为每个设备配置了一张设备控制表，用于记录设备的情况。

②、控制器控制表COCT ；COCT也是每个控制器一张，它反映控制器的使用状态以及和通道的连接情况；

③、通道控制表CHCT；每个通道都配有一张通道控制表，以记录通道的信息；

④、系统设备表SDT；整个系统设置一张SDT，它记录了当前系统中所有设备的情况。每个设备占一个表目，其中包括有设备类型、设备标识符、设备控制表、驱动程序入口、正在使用设备的进程表示等信息。

重点：：表的功能和表与设备独立器的关系。

8、？物理结构/存储结构(是指文件在外存上的存储组织形式) 文件的物理结构也即文件的外存分配方式。

是从系统的角度来看文件，从文件在物理介质上的存放方式来研究文件。

显式链接：在内存的FAT中存放指向链接文件各磁盘块的指针

隐式链接：在文件目录的目录项中，需含有指向链接文件第一个和最后一个磁盘块的指针。而每个盘块中

都要指向下一个盘块的指针

9、分页系统中

二填空题

1、 原语：由若干条指令组成的，用于完成一定功能的过程。它与一般过程的区别在于：它们是“原子操作“，是指一个操作中的所有动作要么全做，要么全不做。他是一个不可分割的基本单位。所以在执行过程中不允许被中断，不可再分。

2、 ？（怎样实现分时系统。。终端）为实现分时系统，必须解决一系列问题。其中最关键的问题是如何使用户能与自己的作业进行交互，即当用户在自己的中断上键入命令时，系统应能及时接收并及时处理该命令，再将结果返回给用户。此后，用户可继续键入下一条命令，即人机交互。主机——多个终端。

3、 进程是由：程序段+相关的数据段+PCB三部分构成的。分页存储管理中，PCB如何和程序结合在一起：当采用分页进程要找到进程的第一个页面，指针指向第一个页面。（进程创建页表，页表中保存数据，PCB关联数据。找到页表首地址，根据页表找到物理块）

4、 优先权调度算法：①抢占式：当前进程在运行过程中，一旦有另一个优先级更高的进程出现在就绪队列中，进程调度程序就停止当前进程的运行，强行将CPU分给那个进程。（当前进程处于临界区内不能剥夺） ②非抢占式：当前占用CPU的进程一直运行下去，直到完成任务或者因等待某事件而主动让出CPU时，系统才让另一个优先级高的进程占用CPU。

A没运行就被B抢 两种一样 A运行结束的话被B抢 抢占非抢占状态不一样

5、 进程通信：高级通信机制分为三大类：共享存储器系统、消息传递系统、管道通信系统。

消息缓冲队列通信机制的数据结构：①消息缓冲区：包含sender：发送者进程标示符 size：消息长度 text：消息正文 next：指向下一个消息缓冲区指针②PCB中有关通信的数据项：包含 mq：消息队列队首指针 mutex：消息队列互斥信号量 sm：消息队列资源信号量

6、？（动态、静态定位在什么时候定位）静态定位：装入时逻辑地址、依次装入 动态定位：简单的装入内存，不做地址映射。

7、SPOOLing技术：共享 利用此技术可将打印机等设备共享，即改造成一台可供多个用户共享的设备，为了提高设备的利用率。

SPOOLing系统的组成：①输入井和输出井②输入缓冲区和输出缓冲区③输入进程SPi和输出进程SP0

SPOOLing技术的特征：①提高了I/O的速度②将独占设备改造为共享设备③实现了虚拟设备功能

8、分页地址 例：已知V地址（位数）20位、页号占8位，页内位移12位，页面大小（页长）：2的12次方（位），，多少个页面：2的8次方（k），进程大小=页面大小*页面个数。。1024k=1m 1024位=1k 2的10次方位=1k

9、文件系统采用二级目录结构，这样可以__解决不同用户之间的文件名冲突问题。

三判断题

1、信号量初值大于0.信号量n，有n个资源可用；信号量0，有0个资源可用；信号量-n，有n个资源在等待。

2、 单缓冲（半双工通信） 双缓冲（双工通信）缓冲池（即可以输入也可以输出）

系统较大时，会有许多的循环缓冲，消耗大量的内存空间，且利用率不高。缓冲池，可供多个进程共享的缓冲区。。缓冲池的组成 ：三种类型的缓冲区： ① 空(闲)缓冲区； ② 装满输入数据缓冲区； ③ 装满输出数据缓冲区 三个缓冲区队列： ①空缓冲队列emq ②输入队列inq ③输出队列outq

四个工作缓冲区： 收容输入（hin） 、收容输出（hout） 、提取输入（sin） 、提取输出（sout）

3、 最佳分区（存储）？算法： 分区大小 从小到大 。。opt最佳，最佳页面置换算法

4、 什么是死锁预防，死锁预防的方法：死锁避免方法银行家算法

5、 进程：拥有资源单位 所有权 运行执行就绪都有。 线程：调度单位 无资源有使用权

6、 操作系统有接口、命令接口、图形接口。要知道那些是命令、那些是图形。。通过键盘操作

7、 快表：功能提高从页号到快号转换的速度。 从物理表中读取数据是一样的

8、 无论基本分页还是请求分页。页面大小均设为2的2次方。

9、 生产者和消费者：生产者P操作和消费者P操作中的代码能否互换顺序？均不能互换，否则会死锁。

四综合题：

1,、最佳置换算法（OPT算法）

2、磁盘调度算法（CSCAN算法）

• 为了减少SCAN算法造成的某些进程的请求被严重推迟，CSCAN算法规定磁头单向移动。

3、银行家算法

1 检查：REQUEST i[j] ≤NEED[i,j];

REQUESTi[j] ≤AVAILABLE[j];

(REQUEST i[j]=k//表示进程i需要k个Rj类的资源 )

2 试探：（把资源分给进程PI）

AVAILABLE[j]= AVAILABLE[j]- REQUESTI[j]；

ALOCATION[i,j]= ALLOCATION[i,j]+ REQUESTI[j]；

NEED[i,j]= NEED[i,j]- REQUESTI[j]；

3 安全性算法—检查安全性 分后是否安全 Y分配 N不分配

银行家算法举例

设系统有五个进程和三类资源，每类资源分别有10、5、7。在T0时刻资源分配情况如图：

1) T0时刻的安全性检查：

T0时刻可以找到一个安全序列{p1,p3,p4,p0,p2}。系统是安全的

(2) T0时刻P1请求资源，请求向量Request1(1,0,2)。

执行银行家算法：

① Request1(1, 0, 2)≤Need1(1, 2, 2)

② Request1(1, 0, 2)≤Available(3, 3, 2)

③系统先假定可为P1分配资源，并修改Available, Allocation1和Need1向量，由此形成的资源变化情况如图一所示。

④ 进行安全性检查：如图二所示。可以找到一个安全序列 { p1, p3, p4, p0, p2 }。故系统是安全的，可以将P1的请求分配给它