操作系统复试

2017软学

给出操作系统的定义，分别从资源管理，任务调度，用户接口等三个方面论述操作系统的职能

操作系统是位于硬件层之上、所有其他系统软件层之下的一个系统软件，使得管理系统中的各种软件和硬件资源得以充分利用，方便用户使用计算机系统。

什么是页式存储管理技术？
介绍页式存储管理的基本原理（25‘）

将各进程的虚拟空间划分成若干个长度相等的逻辑页面(page)，页式管理把内存空间按页的大小划分成页框（page frame），然后把进程的页式虚拟地址与内存地址建立一一对应页表，并用相应的硬件地址变换机构。页式管理采用请求调页或预调页技术实现了内外存存储器的统一管理。

一般一个进程对应一个页表

页式存储管理基本原理：

1. 内存划分：将内存划分为大小相等的区域，每个区域称为页框。将所有的页框从0开始编号，称为页框号f。每个页框内从0开始编址，称为页内地址d。内存的物理地址=<页框号，页内地址>
2. 进程划分：将进程划分为若干个大小相等的区域，每个区域称为逻辑页面p。其长度与页框长度相等。每个逻辑页面内从0开始编制，称为页内地址d。进程的逻辑地址=<逻辑页号，页内地址>
3. 进程空间和内存空间的对应关系：即确定进程空间内逻辑页面和内存空间内页框的关系。一个逻辑页面对应一个页框。逻辑页面是连续的，但是页框是不一定连续的。
4. 所需表目：
   1. 页表：记录逻辑页号和页框号的关系。页表中某页框号的入口地址 = 页表起始地址 + 逻辑页号（数组名地址 + 偏移量 = a[i]）
   2. 总页表：记录页框的使用情况。
5. 所需寄存器：
   1. 页表长度寄存器：用于保存正在运行进程的页表长度（一般一个进程对应一个页表）
   2. 页表始址寄存器：用于保存正在运行进程的页表的起始地址。
   3. 快表（联想寄存器）：用于保存正在运行进程的页表中的部分项目。
6. 地址映射：<逻辑页号p，页内地址d> → <页框号f，页内地址d>
   

快表的作用

用来保存正在运行中的若干页表项，以加速地址变换的过程。
（地址变换是从进程的逻辑地址到内存的物理地址的转换）

什么是段式存储管理技术？

为了进行段式管理，每道程序在系统中都有一个段（映象）表来存放该道程序各段装入主存的状况信息。段表中的每一项（对应表中的每一行）描述该道程序一个段的基本状况，由若干个字段提供。段名字段用于存放段的名称，段名一般是有其逻辑意义的，也可以转换成用段号指明。由于段号从0开始顺序编号，正好与段表中的行号对应，如2段必是段表中的第3行，这样，段表中就可不设段号（名）字段。装入位字段用来指示该段是否已经调入主存，“1”表示已装入，“0”表示未装入。在程序的执行过程中，各段的装入位随该段是否活跃而动态变化。当装入位为“1”时，地址字段用于表示该段装入主存中起始（绝对）地址，当装入位为“0”时，则无效（有时机器用它表示该段在辅存中的起始地址）。段长字段指明该段的大小，一般以字数或字节数为单位，取决于所用的编址方式。段长字段是用来判断所访问的地址是否越出段界的界限保护检查用的。访问方式字段用来标记该段允许的访问方式，如只读、可写、只能执行等，以提供段的访问方式保护。除此之外，段表中还可以根据需要设置其它的字段。段表本身也是一个段，一般常驻在主存中，也可以存在辅存中，需要时再调入主存。假设系统在主存中最多可同时有N道程序，可设N个段表基址寄存器。对应于每道程序，由基号（程序号）指明使用哪个段表基址寄存器。段表基址寄存器中的段表基址字段指向该道程序的段表在主存中的起始地址。段表长度字段指明该道程序所用段表的行数，即程序的段数。

段式存储管理和页式存储管理的区别

在页式存储管理中，分页对用户是透明的，一个进程由若干个页构成，所有页的长度相同；在段式存储管理中，分段对于用户是可见的，一个进程由若干个段构成，各个段的长度可以不同，一个段恰好对应一个程序单位。

段页式存储技术的优缺点
段页式优点：兼顾了页式存储管理解决碎片的问题，段式存储管理便于实现共享的优点。
页式、段式存储管理中，为获得一条指令或数据，须两次访问内存；而段页式则须三次访问内存

给出进程的定义及进程状态转换关系。

进程是具有一定独立功能的程序关于一个数据集合的一次运行活动。
状态：就绪态、运行态、阻塞态。

三种调度及其概念

进程调度： 又称处理器调度、低级调度，是按照某种方法策略从就绪队列中选取一个进程上处理机运行
内存调度： 又称中级调度，是将那些暂时不能运行的进程调至外存等待，把此时的进程状态称为挂起态。当它们已具备运行条件且内存中有空闲时，由内存调度来决定把外存上的哪些已具有运行条件的就绪进程重新调入内存。
高级调度： 又称作业调度。其主要任务是按照一定的原则从外存上处于后备状态的的作业中挑选一个或多个作业，给他们分配内存，IO设备等资源，并建立相应进程，以获得处理机资源。对于每个作业只调入一次，调出一次。（打开好多应用，哪个先启动）

进程调度算法

• 先到先服务算法
• 短作业优先算法
• 最短剩余时间优先算法
• 最高响应比优先算法
• 循环轮转算法
• 多级反馈队列算法

什么是死锁？ 死锁和饿死状态有何不同？ 为什么会产生死锁？针对死锁问题的解决方案是什么？

死锁： 一组进程中的每个进程均等待此组进程中其他进程所占有的，永远无法得到的资源状态称为死锁。
死锁和饿死的区别：

• 进程状态上：死锁进程都处于等待态，忙等（处于运行态或就绪态）的进程并非处于等待态，但是却有可能会被饿死。
• 死锁进程等待永远不会释放的资源，饿死进程等待会释放但是不会被分配给自己资源，饿死进程的等待时限没有上界（忙等或排队等待）
• 死锁一定循环等待，饿死却不一定。
• 死锁一定涉及多个进程，饿死的进程可能只有一个。

为什么产生死锁?
①竞争资源引起的死锁
这种类型的死锁是由于进程争夺使用系统中有限的资源而引起的，因而称为竞争资源引起的死锁。
②进程通信引起的死锁
假设在一个基于消息的系统中，进程P1等待进程P2发来的消息，进程P2等待进程P3发
来的消息，进程P3等待进程P1发来的消息，如此3个进程均无法继续向前推进，亦即发生死锁.这种类型的死锁在基于消息的系统中比较常见.
③其他原因引起的死锁
除前面所介绍的死锁类型之外，尚有其他类型的死锁。例如，假设有-扇门，此门较小，一次只能通过一个人。又设有两位先生M1和M2,他们都要通过这扇门，显然，门相当于一个独占型资源。如果M1和M2竞争地使用这-资源，则他们都能通过。但是假如他们都很谦虚，在门口处M1对M2说“您先过”，M2对M1说‘‘您先过” ，则二者均无法通过，造成僵持.这就是"After YoulAfter You"问题。如果程序设计得不合理，也可能会发生类似的现象，在广义上也称为死锁。

死锁问题的解决方案:
死锁处理策略可以划分为两大类:一类是不让死锁发生:另一类是允许死锁发生，且当死锁发生时能够将死锁检测出来并加以消除。
不让死锁发生的策略又可以划分为两种:一种是静态的。 称为死锁预防( Drevention);另一种是动态的，称为死锁避免(avoidance)。所谓静态的，是指对于进程有关资源的活动按某种协议加以限制，如果所有进程都遵守此协议，即可保证不发生死锁;所谓动态的，是指对于进程有关资源的申请命令加以实时检测，拒绝不安全的资源请求命令，以保证死锁不会发生。死锁所要研究的问题包括静态预防死锁策略、动态避免死锁策略、动态检测死锁策略以及动态恢复死锁策略。
死锁的检测是靠资源分配图（王P129）。用死锁进程检测算法化简资源分配图后，还连着边的进程为死锁进程。

死锁预防：

1. 破坏互斥条件
2. 破坏不可剥夺条件
3. 破坏请求并保持条件
4. 破坏循环等待条件

死锁避免
银行家算法

2018软学

详细说明如何使用索引文件结构实现文件的顺序访问（P186）

• 将顺序文件中若干记录分为一组
• 为顺序文件建立一张索引表，表中记录每个组的第一个记录，该索引项包含该记录的键值和指向该记录的指针
• 为该组的其他记录设置了溢出区域，在溢出区域内记录按顺序文件方式组织
• 同一组的关键字可以无序，但是组与组之间的关键字必须有序。

**检索方法：**先根据关键字去检索索引表，找到该记录所在组的第一个记录的位置，然后再利用顺序查找法查找主文件，找到所需记录。平均检索效率为√N，N是记录数

2006计学

解释概念：

进程： 具有一定独立功能的程序关于一个数据集合的一次活动
忙式等待： 不进入等待状态的等待称为忙式等待。此时的进程处于运行态
饥饿： 指进程长时间等待不能运行，当等待时间给进程推进和响应带来明显影响时，称发生了进程饥饿。当饥饿到一定程度的进程所赋予的任务即使完成也不再具有实际意义时称该进程被饿死。
缓冲： 为了协调吞吐速度相差很大的设备之间数据传送而采用的技术，用于缓和CPU和I/O设备速度不匹配的矛盾，提高并行性。
工作集： 进程在一段时间内活跃地访问页面的集合。（P168）
驻留集： 请求分页存储管理中给进程分配的内存块的集合。