名词解释：

1.信号量:信号量是表示资源的实体，是一个与队列有关的整型变量, 其值仅能由P、V 操作来改变。

2.死锁:死锁是系统中一组进程，该组进程中的每一个进程都占用了某些资源，而又都在无限等待该组中其它进程释放资源，它们都无法向前推进，称此时系统处于死锁状态或系统产生了死锁。

3.系统调用:系统调用是操作系统为了扩充机器功能、增强系统能力、方便用户使用而建立的。它作为操作系统与用户编程时使用的接口。

4.虚拟存储器:根据局部性原理，一个作业在运行之前，没有必要把全部作业装入内存，而仅将那些当前要运行的那部分页面或段,先装入内存便可启动运行,其余部分暂时留在磁盘上程序在运行时如果用到时再装入。这样，便可使一个大的用户程序在较小的内存空间中运行，也可使内存中同时装入更多的进程并发执行。从用户角度看，该系统所具有的内存容量，将比实际内存容量大得多，人们把这样的存储器称为虚拟存储器。

5.设备独立性:为了提高0S的可适应性和可扩展性，目前几乎所有的0S都实现了设备的独立性(也称为设备无关性)。其基本思想是:用户程序不直接使用物理设备名(或设备的物理地址)，而只能使用逻辑设备名;而系统在实际执行时，将逻辑设备名转换为某个具体的物理设备名，实施 I/0 操作。

6.资源:计算机中硬件和软件的总称。

7.多道程序设计:在这种设计技术下，内存中能同时存放多道程序，在管理程序的控制下交替地执行。这些作业共享CPU和系统中的其他资源。

8.并发 :是指两个或多个活动在同一给定的时间间隔中进行，是宏观上的概念。

9.分时 是指多个用户分享使用同一台计算机。多个程序分时共享硬件和软件资源

10.批处理系统：操作员把用户提交的作业分类,把一批作业编成一个作业执行序列,由专门编制的监督程序自动依次处理。其主要特征是用户脱机使用计算机、成批处理以及多道程序运行。

11.实时系统：在被控对象允许时间范围内作出响应。其主要特征是:对实时信息分析处理速度快,要求安全可靠,资源利用率低。

 

 

 

12.吞吐量:在一段给定的时间内，计算机所能完成的总工作量。

13.操作系统, 是控制和管理计算机系统内各种件和软件资源、有效地组织多道程序运行的系统软件(或程序集合)，是用户与计算机之间的接口。为用户提供尽可能多的服务。

操作系统的五大功能：存储管理进程和处理机管理、文件管理、设备管理和用户接口管理。

操作系统的发展过程: 1.手工操作阶段主要用机器语言编程序。2.批处理系统阶段，早期批处理分为脱机和联机两种方式。3.多道程序系统阶段。多道程序运行的特点是多道，宏观上并行，微观上串行。4.分时操作系统阶段，采用分时技术。5.通用操作系统阶段，它兼有多道批处理分时处理实时处理的功能。

基本操作系统类型:单道批处理系统，多道批处理系统，分时系统，实时系统。其他类型操作系统:微机操作系统，网络操作系统，分布式操作系统，嵌入式操作系统。

操作系统的特点:并发性（两个或多个程序在一段时间内同时执行）。共享性（系统资源可供多个并发执行的程序共同使用）。虚拟性（通过软件方式将一个物理资源变成多个虚拟的对等资源）。异步性（多个程序的执行顺序和一个程序的执行与中断次数无法确定，但是其结果始终是确定的）。

 

 

 

14作业：把在一次应用业务处理过程中,从输入开始到输出结束,用户要求计算机所做的有关该次业务处理的全部工作称为一个作业。

作业的组成：作业由程序、数据和作业说明书组成。系统通过作业说明书控制文件形式的程序和数据,使之执行和操作。而且,在批处理系统中,作业是抢占内存的基本单位。也就是说,批处理系统以作业为单位把程序和数据调人内存以便执行。作业由顺序相连的不同作业步组成。

作业步：是在一个作业的处理过程中计算机所做的相对独立的工作。

作业与进程，和程序的关系（区别）:1.作业是用户向计算机提交任务的任务实体。而进程则是完成用户任务的执行的实体，是向系统申请分配资源的基本单位。任意进程，只要它被创建，总有相应的部分存在于内存中。程序描述计算机要完成独立功能并在时间上按严格次序前后相继的计算机操作序列集合,是一个静态的概念2.一个作业可由多个进程组成，且必须至少由一个进程组成，但反过来不成立。3.作业的概念主要用于批处理系统中，而进程的概念则用在几乎所有的多道系统中。

进程的5种状态转换关系:执行到就绪:执行进程被操作系统强制剥夺CPU，从而变成就绪进程。就绪到执行:就绪进程被操作系统调度，从而变成执行进程。执行到等待:由于申请资源未获准，或开始了I/0操作，执行进程将CPU让给其它就绪进程，从而变成等待进程。等待到就绪:等待进程得到所请求资源，或执行的I/0操作结束，从而变成就绪进程。

 

 

 

15. 进程间的互斥:一组并发进程中的一个或多个程序段,因共享某一公有资源而导致它们必须以一个不许交叉执行的单位执行,即不允许两个以上的共享该资源的并发进程同时进入临界区。

进程间的同步:异步环境下的一组并发进程因直接制约互相发送消息而进行互相合作、互相等待,是各进程按一定的速度执行的过程。

死锁:是指一组并发进程中的每一个进程，都等待其余进程中的某个进程拥有的资源，且这些并发进程在得到自己需要的资源之前不会释放自己拥有的资源，从而造成所有并发进程都想得到资源而又都得不到资源，各并发进程均不能继续向前推进的状态。

产生死锁的必要条件:1.互斥，资源不能同时被两个以上的进程同时使用或操作。2.不可剥夺，进程获得的资源在未使用完毕前不能被其他进程剥夺，只能由自己释放。3.部分分配，进程每次申请他需要的资源，在等待新资源的同时继续占用已分配到的部分资源。4.存在环路，发生死锁的一组进程构成一条循环链，链中的每一个进程也获得的资源同时被下一个进程所请求。 只要是上述四个必要条件中的某一个不满足，则死锁可以消除。

解决死锁的方法:预防，避免，检测和恢复3种。

预存死锁的三种方法:1.消除资源的互斥和不可剥夺这两个条件。2.消除资源的部分分配这个死锁产生的必要条件。3.打破死锁的环路条件。

16. 作业的四种状态及其转化:提交，收容，执行和完成状态。一个作业从输入设备进入外层的过程称为提交状态。收容状态也称为后备状态。

 

 

 

CPU调度的层次划分（4级）:1.作业调度又称为宏观调度或高级调度。其主要任务是按照一定的原则对外存输入井中的大量后备作业进行选择，给选出的作业分配内存，输入输出设备等必要资源，并建立相应的根进程，以使该作业的进程获得竞争CPU的资格。2.交换调度又称作中级调度，交换调度主要涉及内存管理与扩充。3.进程调度，又称为微观调度或低级调度。其主要任务是按照某种策略和方法选取一个处于就绪状态的进程占用CPU，在确定了占用CPU的进程之后，系统必须进行进程上下文切换，以建立与占用CPU的进程相适应的执行环境。4.线程调度。分时系统和实时系统中一般不存在作业调度，只有交换调度，进程调度和线程调度。

作业调度的四个功能:1.记录系统中各作业的状况，包括执行阶段的有关情况。2.从后备作业队列中挑选若干作业投入执行。3.为被选中作业做好执行前的准备工作。4.在作业执行结束时做善后处理工作。

进程调度的三个功能:1.记录系统中所有进程的执行情况。2.选择占有CPU的进程。3.进行进程上下文切换。

调度算法中的轮转法：轮转法只能用在进程调度里面，轮转法的基本思路是让每个进程在就绪队列中的等待时间与享受服务的时间成正比，轮转法只能用来分配那些可以抢占的资源，将他们随时剥夺，再分配给别的进程。由于作业调度室对除了CPU之外的所有系统硬件资源的分配，其中包括不可抢占资源，所以作业调度不使用轮转法。在轮转法中时间片长度的选取非常重要，如果时间片长度过短，则调度程序剥夺CPU的次数增多，使得系统开销大，如果时间片长度过长，轮转法会变成先来先服务法。

 

 

 

17.实现虚拟地址到内存地址重定位的方法有两种:静态地址重定位和动态地址重定位。

动态地址重定位的主要优点:1.可以对内存进行非连续分配。2.动态地址重定位提供了实现虚拟内存的基础。3.有利于程序段的共享。

分区管理:把内存划分成若干大小不等的区域，除操作系统占用一个区域外，其余的区域有多道环境下的各并发进程共享。分区管理是满足多道程序设计要求的最简单的内存管理方法。

分区管理的基本原理:给内存中的每一个进程划分一块适当大小的内存区，已连续存储各个进程的程序和数据，使各进程得以并发执行。分区管理可以分为。固定分区和动态分区有两种方法。

分区管理的优缺点:优点:1.实现了多个作业或进程对内存的共享，有助于多道程序设计，从而提高系统的资源利用率。2.该方法要求的硬件支持少，管理算法简单，因而实现容易。缺点:1.内存利用率不高。2.作业或进程的大小受分区大小限制。3.无法实现各分区间的信息共享。

覆盖与交换技术:是在多道环境下用来扩充内存的两种方法。覆盖技术主要用在早期的操作系统中。交换技术则在现代操作系统中具有较强的生命力。交换是指先将内存某部分的程序或数据写入外层交换区，在从外从交换区中调入指定的程序或数据到内存中并让其执行的一种内存扩充技术。与覆盖技术相比，交换技术不要求程序员给出程序段之间的覆盖结构。交换主要在作业或进程之间进行，而覆盖主要在同一个作业或进程内进行。采用覆盖技术只能覆盖与换入的程序段无关的程序段。

 

 

 

 

 

分页管理的优缺点:优点:有效的解决了碎片问题，动态分页管理提供的内存和外存统一管理的虚拟内存实现方式，提高了内存的利用率，有利于组织多道程序并发执行。缺点:要求有相应的硬件支持，增加了硬件成本，增加了系统开销 ，有可能出现抖动现象。

段式管理的优缺点:优点:与动态分页管理一样，段式管理也提供了内外从统一管理的虚拟内存实现。在段式管理中，段长可根据需要动态增长。便于对具有完整逻辑功能的信息段进行共享。便于实现动态连接。缺点:需要更多的硬件支持，提高了硬件成本。在碎片问题上以及为了消除碎片所进行的合并的问题上，较分页管理要差。在段式管理中，每个段的长度受内存可用分区大小的限制。也可能出现抖动现象。

段页式管理是段式管理和分页管理结合而成，具有他们的优点，由于管理软件规模的增大，复杂性和开销也随之增加。执行速度大大下降。

内存管理的主要功能：(1)在硬件的支持下实现统一管理内存和外存之间数据和程序段自动交换的虚拟内存功能。(2)将多个虚拟内存的一维线性空间或多维线性空间变换到内存的唯一的一维物理线性地址空间。(3)控制内外存之间的数据传输。(4)实现内存的分配和回收。(5)实现内存信息的共享和保护。

虚拟内存及其特点：由进程中的目标代码、数据等的虚拟地址组成的虚拟空间称为虚拟内存。虚拟内存不考虑物理内存的大小和信息存放的实际位置,只规定每个进程中相互关联的信息的相对位置。每个进程都拥有自己的虚拟内存,虚拟内存的容量由计算机的地址结构和寻址方式确定。实现虚拟内存要求有相应的地址转换机构,以便把指令的虚拟地址变换为实际的物理地址;另外,由于内存空间较小,进程只有部分内容存放于内存中,待执行时根据需要再调人内存。

 

 

 

 

18. 文件系统的功能（特点）:1.拥有方便友好的用户接口，用户操作时不需要了解文件结构和物理位置，2.支持多个用户或进程的共享访问。3.支持大量信息的存储，对文件按名存取，对用户透明。

文件的分类:1.按照性质和用途分为三类:系统文件，库文件，用户文件。2.按照组织类型划分为三类:普通文件，目录文件，特殊文件。3.按照信息流向可分为:输入文件，输出文件，输入输出文件。4.按照文件的保护级别可分为:只读文件，读写文件，可执行文件，不保护文件。

文件的存取方法:1.顺序存取，是最简单的文件存取方法。2.随机存取（直接访问）3.关键字存取。

文件存取时控制方式（验证用户权限的四种方法）:1.存取控制矩阵。2.存取控制表，3.访问口令（一种方法是当用户进入系统建立终端进程时，输入获得系统使用权的口令，另一种方法是每个用户在创建文件时为新文件设置口令，并将其置于文件说明中）4.文件加密。

文件系统的层次模型:第一层是用户接口层，该层根据用户对文件的存取要求，把不同的系统调用加工改造成不同的内部调用格式。第二层是符号文件系统层。第三层是基本文件系统层。第四层是存取控制验证层，该层的主要功能是根据存取控制信息和用户访问要求检验文件访问的合法性，从而实现文件的共享，保密和保护。第五层是逻辑文件系统层，主要功能是根据文件的逻辑结构找到要进行操作的数据或记录的相对块号。第六层是物理文件系统层，该层根据文件的物理结构搜索文件的物理地址。第七层是文件存储设备分配模块和设备策略模块。设备策略模块是将物理括号转化为设备要求的地址格式。第八层是启动输入输出层，进行设备管理，有设备处理程序执行具体的读写文件操作。第七层和第八层是文件系统和设备管理程序的接口层。

19. I/O设备和内存之间的数据传输方式:1.轮询，也称为程序直接控制方式，是由用户进程直接控制内存或CPU和I/O设备之间的数据传送。2.中断。3.DMA（直接内存存取方式）4.通道。

中断:计算机在执行一个程序期间，系统内发生任何非寻常的或非预期的急需处理的事件，使得CPU暂时中断当前正在执行的程序，而转去执行相应的事件处理程序，待处理完毕后又返回原来中断处继续执行，这个过程称为中断。

中断处理:CPU执行相应的事件处理程序的过程称为中断处理。

中断响应:CPU收到中断请求后转到相应的事件处理程序，称为中断响应。

中断，陷阱和软中断的异同:1.陷阱指CPU和内存内部产生的中断，包括程序运行引起的各种错误，如地址非法，校验错误和页面失效，存取访问控制错误，从用户态到核心态的切换等，都是陷阱的例子。2.软中断是通信进程之间用来模拟硬中断的一种信号通信方式。3.中断，陷阱和软中断都是用于打断CPU正常执行流程的过程，中断包含陷阱和软中断。陷阱和软中断的区别在于触发方式不同，陷阱是由硬件触发的，而软中断是人为设置在程序中的某个位置的。

中断处理过程:1.判断中断响应条件，CPU检查响应中断的条件是否满足。2.如果CPU响应了中断，则立即关中断。3.保存被中断现场。4.分析中断原因，调用中断处理程序。5.执行中断处理程序。6.退出中断恢复现场。7.开中断CPU继续执行，返回中断点。

缓冲技术的种类:根据缓冲器的个数可分为单缓冲，双缓冲，多缓冲以及缓冲池。单缓冲是在I/O设备和CPU之间设置的一个缓冲器，I/o设备和CPU交换数据时，先把被交换数据写入缓冲器，然后需要数据的设备或CPU从缓冲器中取走数据。双缓冲是为两台i/o设备与CPU之间分别设置缓冲器，对端分别将数据放置到对应的缓冲器中，通过分别访问各自的缓冲器达到数据交换的目的。多缓冲是把多个缓冲器连接起来，并分成两部分，一部分专门用于输入，另一部分专门用于输出。缓冲池也是把多个缓冲器连接起来，统一管理，既可用于输入又可用于输出。

 

 

 

 

大题：

1．设有5个哲学家吃饭,。。。试解答以下问题:(1)描述一个保证不会出现两个邻座同时要求吃饭的通信算法。(2)描述一个既没有两邻座同时吃饭,又没有人饿死(永远拿不到筷子)的算法。

在什么情况下,5个哲学家全部吃不上饭?

答：(1)设信号量c[0]~c[4],初始值均为1,分别表示i号筷子被拿(i=0,1,2,3,4)。

send(i):第i个哲学家要吃饭

begin

P(c[i]);

P(c[i+1 mod 5]);

eat;

V(c[i+1 mod 5]);

V（c[i]）;

end

该过程能保证两邻座不同时吃饭,但会出现5个哲学家一人拿一支筷子,谁也吃不上饭的死锁情况。

(2)解决的思路如下:让奇数号的哲学家先取右手边的筷子,让偶数号的哲学家先取左手边的筷子。这样,任何一个哲学家拿到一支筷子以后,就已经阻止了他邻座的一个哲学家吃饭的企图,除非某个哲学家一直吃下去,否则不会有人会饿死。

Send(i):

begin

if i mod 2==0

then

{

P(c[i]);

P(c[i+1] mod 5);

eat;

V(c[i]);

V(c[i+1 mod 5])  }

else

{

P(c[i+1 mod 5]);

P(c[i]);

eat;

V(c[i+1 mod 5]);

V(e[i]);   }

end

 

 

 

2. 银行家算法是经典的死锁避免算法,请简述该算法

答：银行家算法的基本思想是,进程在进入系统时,必须申明在运行过程中可能需要每种资源类型的最大单元数目,其数目不应超过系统拥有的资源总量。当进程请求一组资源时,系统必须首先确定是否有足够的资源分配给该进程。若有,再进一步计算在将这些资源分配给该进程后是否会使系统处于不安全状态。如果不会,才将资源分配给它,否则让该进程等待。

3.调度算法求周转时间:

表中写入作业号进入系统时间，运行时间，开始时间，结束时间，周转时间。

周转时间=实际完成时间-进入系统时间

平均周转时间=周转时间相加/作业数

带权周转时间=周转时间/运行时间

平均带权周转时间=带权周转时间/作业数

先来先服务（按照到达时间先后）。短作业优先（非抢战式按时间短的来）。

4.页面置换算法

计算缺页次数，页面置换次数和缺页率。

最佳置换算法OPT:向后看（后面有的不置换）。

先进先出页面置换算法FIFO:每次置换先来的。

最近最久未使用置换算法LRU:向前看，前面有的不置换。

写了几列就是几个缺页次数，缺页次数/总页数=缺页率

置换了几次就是页面置换次数

命中率=1-缺页率

5.分页式内存分配题

已知页号和块号，已知每页有多少个字节（页面大小），给出逻辑地址，求对应的物理地址。

逻辑地址/页面大小=p（页号）.......d（位移量）。

物理地址=p对应的块号×页面大小+位移量

6.分段式存储内存分配题

已知段号，段长，基址和状态位（0为主存，1为主存）。

求逻辑地址（1，55）对应的主存地址（也就是物理地址）。1为段号，55为段内地址。

答:首先将段内地址与段长（逻辑地址的段号对应的段长）作比较，如果段内地址小于段长，没发生越界中断，物理地址=段内地址+基址。

如果段内地址大于段长，发生越界，逻辑地址非法