操作系统期末考点

考卷

选择题

某计算机系统中有8台打印机，由K个进程竞争使用，每个进程最多需要3台打印机，该系统发生死锁的K的最小值是_____C_________ 。

A. 2 B. 3 C.4 D.5
操作系统采用缓冲技术，能够减少对CPU的_____A______次数，从而提高资源的利用率。

A.中断 B.访问

C.控制 D.依赖
索引式（随机）文件组织的一个主要优点是_____B_________。

A.不需要链接指针 B.能实现物理块的动态分配

C. 回收实现比较简单 D.用户存取方便

填空题

1.文件的物理结构有，顺序结构、链接结构、和索引结构。

2.磁盘高速缓冲是在内存中为磁盘快设置的一个缓冲区，其主要目的是提高磁盘的I/O速度。

3.位示图是利用二进制的一位来表示文件存储空间中的一个块的使用情况。

4.SPOOLing技术的中文译名为外部设备联机并行操作，它是关于慢速字符设备如何与计算机主机交换信息的一种技术，通常叫作假脱机技术。

编写程序（PV源语）三选一

有三个进程 PA、PB和PC协作解决文件打印问题。PA将文件记录从磁盘读入内存的缓冲区1，每执行一次读一个记录；PB 将缓冲区1的内容复制到缓冲区2中，每执行一次复制一个记录；PC将缓冲区2的内容打印出来，每执行一次打印一个记录。缓冲区的大小与记录大小一样。请用信号量来保证文件的正确打印。

分析：本题又是生产者-消费者问题的一个变形，对缓冲区1来说，PA是生产者，PB是消费者;对缓冲区2来说，PB是生产者，PC是消费者。
需要说明的有两点：
①缓冲区1和缓冲区2都只能存放一个记录，故无须设置in、out 指针，原来生产者一消费者问题中的mutex信号量也因此可以省去；
②PB进程既是消费者，又是生产者。

//该文件打印过程的同步算法可描述为：
semaphore  empty1=1, full=0, empty2=1, full2=0;
PA()
{
	while(1){
		从磁盘读一个记录;
		wait(empty1);
		将记录存放到缓冲区1中;
		signal(full);
	}
}
PB(){
	while(1){
		wait(full);
		从缓冲区1中取出一个记录;
		signal(empty1);
		wait(empty2);
		将记录复制到缓冲区2中;
		signal(full2);
	}
}
PC(){
	while(1){
		wait(full2);
		从缓冲区2中取出一个记录;
		signal(empty2);
		将取出的记录打印出来;
	}
}

main(){
	cobegin PA(); PB(); PC(); coend
}

请用信号量解决以下的“过独木桥”问题：同一方向的行人可连续过桥，当某一方向有人过桥时，另一方向的行人必须等待;当某一方向无人过桥时，另一方向的行人可以过桥。

分析：独木桥问题是读者一写者问题的一个变形，同一个方向的行人可以同时过桥，这相当于读者可以同时读。因此，可将两个方向的行人看做是两类不同的读者，同类读者(行人)可以同时读(过桥)，但不同类读者(行人)之间必须互斥地读(过桥)。

//可为独木桥问题定义如下的变量：
int count A =0, count B = 0; //count A, count B 分别表示A、B两个方向过桥的行人数量
semaphore bridge = 1; //用来实现不同方向行人对桥的互斥共享
semaphore mutex A = mutex B = 1; //分别用来实现对 count A、count B的互斥共享
//A方向的所有行人对应相同的算法，他们的动作的算法可描述为：
PA(){
	wait(mutex A);
		if(count A == 0) wait(bridge);
		count A++;
	signal(mutex A);
	过桥;
	wait(mutex A);
		count A--;
		if(count A == 0)signal(bridge);
	signal(mutex A);
}

请给出一个写者优先的 “读者—写者”问题的算法描述。

分析:与读者优先不同的方案有三种。
第一种是读者和写者的地位是完全平等的，即无论是读者还是写者，都按他们到达的时间先后决定优先次序。
第二种方案中，写者的优先权得到了提高，先于写者到达的读者比写者优先，但当一个写进程声明要进行写操作时，其后续读者必须等写操作完成之后，才能进行读；而且，如果在写完成之前，又有新的写者到达，那新的写者的优先权将高于已在等待的读者。
第三种方案写者的优先权更高，某个写者到达时，即使他是目前唯一的写者，那些先于他到达但还没来得及读的读者都将等待他完成写操作。

答:为了使写者优先，可在原来的读优先算法基础上增加一个初值为1的信号量S，使得当至少有一个写者准备访问共享对象时，它可使后续的读者进程等待写完成；初值为0的整型变量writecount，用来对写者进行计数；初值为1的互斥信号量wmutex，用来实现多个写者对writecount的互斥访问。读者动作的算法描述如下:

//第二种方案
reader(){
	while(1){
		wait(S);
		wait(rmutex); //rmutex 用来实现对readcount的互斥访问
			if(readcount == 0) wait(mutex); //mutex用来实现对读写对象互斥访问
				readcount++;
			signal(rmutex);
			signal(S);
			perform read operation;
			wait(rmutex);
				readcount--;
				if(readcount == 0) signal(mutex);
			signal(rmutex);
	}
}
//写者动作的算法描述如下：
writer(){
	while(1){
		wait(wmutex); //wmutex用来实现对writecount的互斥访问
			if(writecount == 0) wait(S);
			writecount++;
		signal(wmutex);
		wait(mutex);
		perform write operation;
		signal(mutex);
		wait(wmutex);
			writecount--;
			if(writecount == 0) signal(S);
		signal(wmutex);
	}
}

clock算法

简答题

什么是进程?由几部分组成?与程序的区别是什么?

定义：

进程是可并发执行的程序在一个数据集合上的运行过程，是系统进行资源分配和调度的一个独立单位。

组成部分：

进程由程序、数据和进程控制块三部分组成: .

程序段：程序段是进程中能被进程调度程序调度到CPU上执行的程序代码段，它能实现相应的特定功能。
数据段：一个进程的数据段，可以是进程对应的程序加工处理的原始数据，也可以是程序执行时产生的中间或最终结果数据。
进程控制块PCB组成：每一个进程均有一个进程控制块PCB。用户进程被创建时，系统为它申请和构造一个相应的PCB。

进程和程序的区别：

程序是静态概念，而进程是动态概念
程序是永久的，而进程是暂时的
进程之间能并发地活动
进程是竞争计算机系统有限资源的基本单位
程序和进程无一一对应关系

何谓死锁?产生死锁的原因和必要条件是什么?

死锁的定义：

死锁是指多个进程在运行过程中因争夺资源而造成的一种僵局，当进程处于这种僵持状态时，若无外力作用，它们都将无法再向前推进。

产生死锁的原因：

产生死锁的原因可归结为竞争资源引起进程死锁和进程推进顺序不当引起死锁两个方面。

产生死锁的必要条件：

互斥条件
请求和保持条件
不剥夺条件
环路等待条件

分页和分段存储管理有何区别?

页是信息的物理单位，分页是为实现离散分配方式，以消减内存的外零头，提高内存利用率。或者说，分页仅仅是由于系统管理的需要而不是用户的需要。

段则是信息的逻辑单位，它含有一组意义相对完整的信息，分段的目的是为了能更好地满足用户的需要。
页的大小固定且由系统决定，由系统把逻辑地址划分为页号和页内地址两部分，是机械硬件实现的，因而在系统中只能有一种大小的的页面；

而段的长度却不固定，决定于用户所编写的程序，通常由编译程序对源程序进行编译时，根据信息的性质来划分。
分页的作业地址空间是一维的，即单一的线性地址空间，程序员只需利用一个记忆符，即可表示一个地址。

分段的作业地址空间则是二维的，程序员在标识一个地址时，既需给出段名，又需给出段内地址。

为什么要引入动态重定位?如何实现?

原因：

在连续分配方式中，必须把一个系统或用户程序装入一连续的内存空间。如果在系统中只有若干个小的分区，即使它们容量的总和大于要装入的程序，但由于这些分区不相邻接，也无法把该程序装入内存。若想把程序装入，可采用的一种方法是：将内存中的所有作业进行移动，使它们全都相邻接，这样，即可把原来分散的多个小分区拼接成一个大分区，这时就可把作业装入该区。这种通过移动内存中作业的位置，以把原来多个分散的小分区拼：接成一个大分区的方法，称为“拼接”或“紧凑”。由于经过紧凑后的某些用户程序在内存中的位置发生了变化，此时若不对程序和数据的地址加以修改(变换)，则程序必将无法执行。为此，在每次“紧凑”后，都必须对移动了的程序或数据进行重定位。

实现：

在动态运行时装入的方式中，作业装入内存后的所有地址都仍然是相对地址，将相对地址转换为物理地址的工作，被推迟到程序指令要真正执行时进行。为使地址的转换不会影响到指令的执行速度，必须有硬件地址变换机构的支持，即须在系统中增设一个重定位寄存器，用它来存放程序(数据)在内存中的起始地址。程序在执行时，真正访问的内存地址是相对地址与重定位寄存器中的地址相加而形成的。当系统对内存进行了“紧凑”而使若干程序从内存的某处移至另一处时,不需对程序做任何修改，只要用该程序在内存的新起始地址去置换原来的起始地址即可。

在请求分页系统中，产生“抖动”的原因是什么?

发生“抖动”的根本原因是，同时在系统中运行的进程太多，由此分配给每一个进程的物理块太少，不能满足进程正常运行的基本要求，致使每个进程在运行时，频繁地出现缺页，必须请求系统将所缺之页调入内存。这会使得在系统中排队等待页面调进/调出的进程数目增加。显然，对磁盘的有效访问时间也随之急剧增加，造成每个进程的大部分时间都用于页面的换进，换出，而几乎不能再去做任何有效的工作，从而导致发生处理机的利用率急剧下降并趋于0的情况。我们称此时的进程是处于“抖动”状态。

何谓DMA方式? DMA控制器可采用哪几种方式与CPU分时使用内存?

直接内存访问(DMA)方式是一种完全由硬件执行I/O交换的工作方式。DMA 控制器从CPU完全接管对总线的控制。数据交换不经过CPU,而直接在内存和I/O设备之间进行。

DMA控制器采用以下三种方式：

停止CPU访问内存

当外设要求传送一批数据时，由DMA控制器发一个信号给CPU。 DMA控制器获得总线控制权后，开始进行数据传送。一批数据传送完毕后，DMA控制器通知CPU可以使用内存，并把总线控制权交还给CPU。

周期挪用

当I/O设备没有DMA请求时，CPU按程序要求访问内存: 一旦I/O设备有DMA请求，则I/O设备挪用一个或几个周期。

DMA与CPU交替访内

一个 CPU周期可分为2个周期，一个专供DMA控制器访内，另一个专供CPU访内。不需要总线使用权的申请、建立和归还过程。

银行家算法

段页式存储管理系统的地址转换过程

作业调度算法

磁盘调度算法

SSTF最短寻找时间优先

SCAN电梯算法

移动到最外侧之后，再向内移动。

C-SCAN循环扫描算法

只处理某一单独方向上的请求，返回时直接到始端，不处理任何请求

题型

选择 10分每题一分

填空 10分每题一分

编写程序 10分

clock 算法 10分

4个简答题：重定位、虚拟存储、DMA、软中断、段页式存储概念 20分

PPT中的计算题：磁盘调度算法、预防死锁、思索的判断条件（计算题二选一） 10分

页面调度，物理地址和逻辑地址的换算 10分

多通道调度画图 10分

章节知识点

第三章

进程管理

复习PPT上的笔记

什么是进程？什么是线程？进程和线程的区别？

进程 = 程序段 + 相关的数据段 + PCB

PCB：描述进程的基本情况和活动过程，进而控制和管理进程

线程 = 线程控制表 + 存储上下文的用户栈 + 核心栈

线程是在进程内用于调度和占有处理机的基本单位。
区别：
1. 进程是资源管理的基本单位，拥有自己的地址空间和各种资源。
  
  线程是处理机调度的基本单位，只和其他线程一起共享进程资源，自己没有任何资源。
  
  进程有自己的资源，进程无
2. 进程切换处理机和调度的时候，涉及资源转移，现场保护等，导致处理机切换时间长，资源利用率降低
  
  线程切换时，不发生资源变化，特别是地址空间的变化，所以切换时间短，处理机效率较高
  
  进程切换时涉及资源转移，保护现场，利用率低。线程不涉及，处理机利用率高
3. 多线程可以减少用户等待时间，提高系统响应速度。
4. 线程和进程一样，有自己的状态，相应的同步机制。
  
  但线程没有单独的数据和程序空间，所以不能像进程那样把数据交换到外存，从而没有挂起状态
  
  线程没有挂起状态
5. 进程的调度、同步等控制大多由操作系统内核完成。
  
  线程既可以操作系统内核，也可以用户控制。

第四章

处理机调度

看PPT笔记

例题：

第五章

什么是虚拟存储器？特点？

由进程中的目标代码、数据等的虚拟地址组成的虚拟空间称为虚拟存储器。
虚拟存储器不考虑物理存储器的大小和信息存放的实际位置，只规定每个进程中相互关联的信息的相对位置。
虚拟存储器的容量由计算机的地址结构和寻址方式来确定。
虚拟存储需要有相应的地址转换机构，把指令的虚拟地址转换为实际物理地址

能否把虚拟空间无限扩大？

不能，虚拟存储器的容量由计算机的地址结构和寻址方式来确定。地址总线的量是有限的，寻址不到，不能超界。

实现地址重定位的方法？

静态地址重定位：

在虚拟空间程序执行之前由装配程序完成地址映射工作。
不需要硬件支持
进行地址变换无法实现虚拟存储器
必须占用连续的内存空间
难以做到程序和数据的共享

动态地址重定位：

在程序执行过程中，在CPU访问内存之前由硬件地址变换机构将要访问的程序或数据地址转换成内存地址。
可以对内存进行非连续分配
动态重定位提供了实现虚拟存储器的基础
有利于程序段的共享

动态分区式管理的常用内存分配算法有哪几种？优缺点？

动态分区式管理的常用内存分配算法有FF（最先适应法）first fit、BF（最佳适应法）best fit、WF（最坏适应法）worst fit

从搜索速度上：FF最好，BF和WF都要求把空闲区按大小进行排队。
从回收过程上：FF最好，因为BF、WF都必须重新调整空闲区的位置。
BF找到的空闲区是最好的，但是会造成内存碎片较多，影响内存利用率。WF碎片最少，但是对内存请求较多的进程可能分配失败。
BF是先找最小的空闲区进行分配。
WF是先找最大的空闲区进行分配。

什么是覆盖？什么是交换？覆盖和交换的区别是什么？

覆盖：

将程序划分为若干个功能上相对独立的程序段
按照程序的逻辑结构让那些不会同时执行的程序段共享同一块内存区的内存扩充技术。

交换：

先将内存某部分的程序或数据写入外存交换区
再从外存交换区中调入指定的程序或数据到内存中来，并让其执行的一种内存扩充技术。

区别：

交换：

不要求给出程序段之间的覆盖结构

主要在进程或作业之间进行

覆盖：

主要在同一个作业或同一个进程内进行

只能对那些与覆盖程序段无关的程序段进行覆盖

什么是页式管理？静态页式管理可以实现虚存吗？

页式管理就是把各进程的虚拟空间划分为若干长度相等的页面，把指令按页面大小划分后存放在内存中执行，或者只在内存中存放那些经常被执行或将被执行的页面。不经常被执行的放在外存，按一定规则调入的一种内存管理方式。
静态页面不能，因为它要求进程或作业在执行前全部装入内存，作业或进程大小仍受内存可用页面数的限制。

能有效提高内存利用率

什么是请求页式管理？

一种动态页式内存管理，进程或作业开始执行前，不把程序段一次性全部装入，只装入反复执行的部分。其他部分在执行过程中动态装入。当需要指令，但又不在内存中时会发生缺页中断，系统再将外存中相应的页面调入内存。

请求页式管理中有哪几种常用的页面置换算法？优缺点？

10分大题，不考概念，考大题，但是还是要懂原理

随机淘汰算法：随机的选择某个用户页面并将其换出。
轮转法RR：循环换出内存可用区里一个可以被换出去的页。无论它是刚被换进还是已经换进很长时间。
先进先出FIFO：淘汰在内存中驻留时间最长的一页
最近最久未使用页面置换算法LRU：淘汰离当前最近时间内，最久没使用过的页面
理想型淘汰OPT：淘汰在访问串中将来再也不出现或是在离当前最远的位置上出现的页面。

什么是段式管理？与页式管理区别？

段式：

将程序按照内容或过程关系分成段，以段为单位分配内存，然后地址映射机构把段式虚拟地址转换为实际的物理地址。也是常用的驻留内存，不常用的放在外存。

更好的满足用户多方面需求

区别：

页式管理是按照线性空间顺序排列的

段式是按照内容或过程的函数关系分成段，是一个二维的
段式有内外存统一管理的虚存实现，但是每次交换的是一段有意义的信息。

页式交换固定大小的页，会需要多次缺页中断。
段式管理，段长需要动态增长
段式管理便于有完整逻辑功能的信息段共享
段式管理便于进行动态链接，页式管理进行动态链接很复杂

段式管理可以实现虚存吗？

可以。以段为单位分配内存，通过地址映射机构把段式虚拟地址转换为实际物理地址

什么是段页式存储？

结合页式管理和段式管理即具有分段系统便于实现，分段可共享、易于保护、可动态链接等优点。又有分页，解决内存的外部碎片问题

需要了解一下

段式管理有利于动态增长、共享、内存保护。页式管理解决内存外部碎片问题，提高内存利用率。

段页式访问时间长，执行效率低。

因为在段式的基础上分页，只是为了克服碎片问题，并没有改变段内地址的结构。

存取指令时，需要对内存进行三次以上的访问：1.从段表中取出对应的页表地址 2.访问页表得到数据或指令的物理地址 3. 访问物理单元。降低CPU执行指令的速度

第六章

什么是软中断（概念题，解释题5分）？

软中断是对硬件的一种模拟
发送软中断就是向接收进程的一个相应项发送一个特殊信号
接收到信号后，按照事先规定的区执行一个软中断处理程序
收到信号后不立即启动，要等到接收进程执行时才能生效
可以向自己发软中断信号

第七章

简述虚拟地址到物理内存地址的转换过程(必考，有个计算题)

每个进程对应一个页目录，当操作系统开始执行某一进程时，系统会设置当前进程所对应的页目录
一个进程可有多个页表，通过页目录索引，内存管理器可定位相应的虚拟地址所对应的页表
通过页表和页表索引，内存管理器可定位虚拟地址对应的物理页框号
定位物理页框号后，通过字节索引，可判断虚拟地址对应的物理地址

页表的作用：通过页表查到虚拟地址的页表入口，再通过该入口查到该地址对应的物理地址

第八章

磁盘调度算法

先来先服务（FCFS）

根据请求的先后进行调度

最短寻找时间优先（SSTF）

scan（电梯算法）

移动到最外侧之后，再向内移动。

Look算法

在SCAN的基础上。如果在磁盘移动方向上，没有其他请求，就立即改变磁头方向

循环扫描算法（C-SCAN）

只处理某一单独方向上的请求，返回时直接到始端，不处理任何请求

C-Look算法

在C-SCAN基础上。如果在磁盘移动方向上，没有其他请求，就立即改变磁头方向

文件的物理结构有哪几种？为什么串联不适于随机存取（重要）

连续文件、串联文件、索引文件
串联：非连续的物理块存放信息，没有顺序关系。搜索时只能按队列中的串联指针顺序搜索。不适用于随机存取。

什么是文件目录？文件目录包含哪些信息？

文件目录定义 = 文件名 + 对该文件实施控制管理的说明信息
文件目录内容 = 文件名 + 文件内部标识 + 文件信息在存储设备上第一个物理块的地址信息 + 文件逻辑结构、物理结构、存取控制和管理等

可以减少文件命名冲突
提高搜索速度

符号文件目录表和基本文件目录表是实现文件共享的方法，不是二级目录

第九章

DMA

数据传送控制方式有哪几种？

有程序直接控制法、中断控制法、DMA、通道方式

程序直接控制：用户直接控制内存或CPU和外部设备的数据传输。

优点：控制简单，不需要太多硬件支持

缺点：只能串行工作，无法发现错误
中断I/O控制：向CPU发送中断的方式控制传送。

优点：提高CPU利用率，支持并行

缺点：数据缓冲寄存器较小，中断次数较多，占用CPU大量时间。外部设备多时，造成CPU中断丢失。设备快，出现数据丢失。
DMA：在外部设备和内存之间开辟直接的数据交换通路进行数据传送。

优点：除了开始和结束是需要CPU处理，其他时候不需要CPU的频繁干涉

缺点：设备多时，多个DMA同时使用会引起内存地址的冲突
通道方式：使用通道来控制内存或CPU和外部设备的数据传送。通道是一个独立于CPU的机构，有自己的通道指令。启动和结束时需要CPU。

优点：减轻CPU负担，增加并行工作成都

缺点：增加额外硬件，造价高