操作系统期末复习

1. 理解CPU执行的两种状态:用户态、核心态

​ 核心态：操作系统程序，特权。

​ 用户态：执行用户应用程序。

2. 操作系统的定义、主要功能(5 个)

操作系统是控制和管理计算机系统内各种硬件和软件资源，有效地组织多道程序运行的系统软件（或程序集合），是用户与计算机之间的接口。

1．存储管理功能

2．处理机管理功能

3．设备管理功能

4．文件管理功能

5．用户接口

3. 理解系统调用的作用

是操作系统内核与用户程序、应用程序间接口。它一般位于操作系统核心的最高层。系统调用类似于过程调用，OS提供了一组系统调用，用户可在自己的应用程序中通过相应的系统调用，来操纵计算机。

区别：过程调用在用户态下，系统调用从用户态进入核心态。

4. 理解批处理系统、分时系统、实时系统的概念和基本特征

批处理系统概念:

基本思想是在内存中同时存放多道程序，在管理程序的控制下交替地执行。这些作业共享CPU和系统中的其他资源。

多道程序的这种交替运行称做并发执行。

在一段给定的时间内，计算机所能完成的总工作量（称为系统吞吐量）。

特征:

多道性；无序性；调度性，共享性。

分时系统:

在这个操作系统下有多个用户终端，分时共享主机资源。

所谓分时，就是对时间的共享，主要是指若干并发程序对CPU时间的共享，分享的时间单位叫时间片。

所谓并行是指在同一时刻有两个或两个以上的活动发生。

特征:

同时性：多用户同时上机使用，多终端。

交互性：人机交互。

独立性：各用户操作互不干扰。

及时性：很短时间相应。

实时系统:

是指系统能及时(或即时)响应外部事件的请求，在规定的时间内完成对该事件的处理，并控制所有实时任务协调一致地运行。

特征:

对时间有严格的限制和要求：实时控制；实时信息处理。

5. 区分并行与并发

多道程序的这种交替运行称做并发执行。

所谓并行是指在同一时刻有两个或两个以上的活动发生。

第二章

1. 进程的概念、 进程存在的唯一标识、 进程与程序的区别(四个:动态性、并发性、非对应性、异步性)

进程的概念:

进程最根本的属性是动态性和并发性。

“进程是进程实体的运行过程，是系统进行资源分配和调度的一个独立单位”。

进程与程序的区别:

（1）动态性:生命周期。例如$date命令显示当前日期时间。

（2）并发性

（3）非对应性：程序和进程无一一对应关系。例如某人输入命令$cc f1.c，另一人输入$ccf1.c，另一人输入cc a1.c，都调用c编译程序等很多程序。

（4）异步性：走走停停。并发执行。

进程标识符用于惟一地标识一个进程。

PCB是进程存在的唯一标识。

2. 进程的三个基本状态及其转换关系。

进程的基本状态:

运行状态（Running）

就绪状态（Ready）

阻塞状态（Blocked）

新建状态（New）

终止状态(terminated)

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-TStx73IQ-1578104882280)(file:///C:\Users\颜美娴\AppData\Local\Temp\ksohtml15760\wps1.jpg)]

3. 进程与线程的关系、各自分工，线程的实现有几种基本方法

现代操作系统中，进程只作为资源拥有者，而调度和运行的属性赋予新的实体——线程。进程拥有资源，线程调度执行,线程（Thread）是进程中实施调度和分派的基本单位。

线程实现的几种基本方式:

1. 在用户空间实现线程(用户级线程)

2. 在核心空间实现线程(核心级线程)

3. 组合方式(两者结合)

4. 结构型信号量值的含义，P、V操作的含义。

结构型信号量一般是由两个成员组成的数据结构。其中一个成员是整型变量，表示该信号量的值；另一个是指向PCB的指针。

P操作最初源于荷兰语proberen，表示测试；

V操作源于荷兰语verhogen，表示增加。

5. 进程的高级通信方式有哪几种?

大致可归并为共享存储器、消息传递和管道文件三类。

6. 理解经典同步问题中的读者/写者、生产者/消费者问题。会用P/V操作写出进程间的同步算法。

//生产者                             
while(true){                          
	p(empty);
	p(mutex);
	产品送往buff(in)；
	in = (in + 1) mod N;
	v(mutex);
	v(full);
}

  //消费者
 while(true) {
  	p(full);
  	p(mtex);
  	从buff(out)中取产品；
  	out = (out + 1) mod N;
  	v(mutex);
  	v(empty)
}

//读者
while(true) {
	p(rmutex);
	readcounter = reacounter +1;
    if(readcounter == 1) {
    p(wmutex);
}
	v(rmutex);
	执行读操作；
	p(rmutex);
	readcounter = readcounter -1;
	if(readcounter == 0) {
		v(wmutex);
	}
	v(rmutex);
	使用读取的数据
	}
	//写着
	while(true) {
	p(mutex);
	执行写操作;
	v(mutex);
}

第三章

1. 死锁的概念

所谓死锁，是指在一个进程集合中的每个进程都在等待仅由该集合中的另一个进程才能引发的事件而无限期地僵持下去的局面。

2. 产生死锁的两个根本原因、死锁发生的4个必要条件

根本原因就是资源有限且操作不当.

4个必要条件:

1．互斥条件

2．占有且等待条件

3．不可抢占条件

4．循环等待条件

3. 破坏死锁必要条件的策略。

破坏占有且等待条件:

一种办法是预分资源策略：静态分配 .

另一种办法是“空手”申请资源策略 .

破坏非抢占条件:

隐式抢占：如果要申请其他资源的进程，当前所占有的全部资源可以被抢占。

另一种方法是抢占等待者的资源。

破坏循环等待条件:
一种方法是实行资源有序分配策略

另一种申请办法也很简单：先弃大，再取小。

4. 掌握银行家算法。

第四章

1. 处理机调度有几级，哪一级必不可少.

处理机调度分为作业调度（高级调度）、进程挂起与对换（中级调度）和进程调度（低级调度）三级。

低级调度必不可少;

2. 进程优先级调整的时机

系统中发生某些事件，要执行进程调度：

① 创建进程。

② 进程终止。

③ 等待事件。

④ 中断发生。

⑤ 运行到时。

3. 理解单处理机系统各调度算法的基本思想和特点，包括:先来先服务(FCFS)、 短作业优先法(SJF)、高响应比优先法(HRRF)、时间片轮转法(RR)、优先级法(HPF)、 多级反馈队列法(MFQ)

先来先服务法FCFS:

在当前正在运行的进程停止执行时，选择在就绪队列中存在时间最长的进程运行，即从就绪队列的头部移走一个进程运行。

FCFS的特点:

非抢占式调度方式。

优点：

简单，易于理解，便于在程序中运用。

缺点：

有利于长进程，不利于短进程。

有利于CPU繁忙型作业，不利于I/O繁忙型作业。

效率较低。

即可用于作业调度，也可用于进程调度。在实际的OS中，FCFS算法与其他算法结合起来使用.

短作业优先法(SJF):

当分配CPU时，选择所需处理时间最短的进程。短进程将越过长进程，跳到队列头。一个进程一旦分得处理机，便执行下去，直到该进程完成或阻塞时，才释放处理机。

这是对FCFS算法的改进，其目标是减少平均周转时间。

SJF的特点:

非抢占式

优点：

对于一组给定的作业，SJF能给出较小的平均等待时间，提高了系统的吞吐量。

缺点：

实现上有困难，需要知道或至少需要估计每个作业/进程所需要的处理时间。

对长作业不利。

不能保证及时处理紧迫作业。

作业调度用的多，进程调度用的少。

优先级法HPF:

优先级调度算法是从就绪队列中选出优先级最高的进程，让它在CPU上运行。

可用于作业调度或进程调度。

轮转法RR:

时间片轮转法（Round-Robin）主要用于分时系统中的进程调度。

时间片是一个小的时间单位，通常为10～100 ms数量级。

将系统中所有的就绪进程按照FCFS原则，排成一个队列。每次调度时将CPU分派给队首进程，让其执行一个时间片。时间片的长度从几个ms到几百ms。在一个时间片结束时，发生时钟中断。

调度程序据此暂停当前进程的执行，将其送到就绪队列的末尾，并通过上下文切换执行当前的队首进程。进程可以未使用完一个时间片，就出让CPU（如阻塞）。

优缺点:

时间片轮转法属于抢占调度方式，其特点是简单易行、平均响应时间短，但不利于处理紧急作业,时间片的大小直接影响轮转法的性能。

多级反馈队列法MFQ:

① 系统中设置多个就绪队列，每个队列对应一个优先级；

② 各就绪队列中进程的运行时间片不同，高优先级队列的时间片小，低优先级队列的时间片大；

③ 新进程进入系统后，先放入第1个队列的末尾，如果在时间片内工作未完成，则转入下一个队列尾，依此类推；

④ 系统先运行第1个队列中的进程,若第1队列为空,才运行第2队列，依次类推；

特点

抢占式调度

动态优先级

需要解决“饥饿”问题

是最通用的CPU调度算法,也最复杂.

高响应比优先法HRRF:

基于过去的历史或用户和配置管理员的某些输入值近似估计服务时间。为每个进程计算一个响应比RR=（w+s）/s。在调度进行时，以各进程的响应比作为其优先级，从中挑选级别最高的进程投入运行。

w是进程等待处理机所用的时间；

s是进程要求的服务时间。

特点

高响应比优先法是一种非抢占方式。

兼顾短进程、长进程。

调度前需要计算进程的响应比，增加系统开销。

对实时系统无法做出及时反应。

4. 熟练掌握:对于给定的一组作业或进程，采用以上前五个调度算法，会画执行时间图给出调度过程，并会计算平均周转时间和平均带权周转时间。

   周转时间=作业完成时间−作业提交时间

   平均周转时间=(作业1的周转时间+…+作业n的周转时间n平均周转时间=作业1的周转时间+…+作业n的周转时间)/n

   带权周转时间=作业周转时间作业/实际运行时间

   平均带权周转时间=(作业1的带权周转时间+…+作业n的带权周转时间n平均带权周转时间=作业1的带权周转时间+…+作业n的带权周转时间)/n

---

第五章

1. 动态重定位与静态重定位的概念

静态重定位:当用户程序被装入内存时，一次性实现逻辑地址到物理地址的转换，以后不再转换（一般在装入内存时由软件完成）作业i在执行前一次性变址，直到该作业完成退出内存为止。

动态重定位:在程序运行过程中要访问数据时再进行地址变换。由地址变换机构进行的地址变换，硬件上需要重定位寄存器的支持。

2. 区分理解逻辑地址和物理地址

用户程序经编译之后的每个目标模块都以0为基地址顺序编址，其余指令中的地址都相对于首地址而编址。这种地址称为相对地址或逻辑地址；

内存中各物理存储单元的地址是从统一的基地址开始顺序编址的，这种地址称为绝对地址或物理地址。

3. 掌握动态分区分配算法的基本思想，包括最先适应算法、最佳适应算法、循环适应算法，注意空闲分区表的排列方式

基本思想：

内存不是预先划分好的，而是当进程装入时，根据进程的需求和内存空间的使用情况来决定是否分配。若有足够的空间，则按需要分割一部分分区给该进程；否则令其等待主存空间。

最先适应法分配算法:

空闲表按位置排列（空闲块地址小，在表中的序号也小）。

分配内存时，在各空闲分区中查找满足大小要求的可用块。找到第一个可满足要求的空闲块就停止查找，并进行分配。

若空闲空间全部占用则从空闲表取消该项，若有剩余，则余下部分仍保留在空闲表中，并更新分区大小和分区地址。

最佳适应算法:

空闲表以空闲块大小为序，按增量形式排列。接到内存申请时，在空闲块表中找到一个不小于请求的最小空闲块进行分配。

为作业选择分区时总是寻找其大小最接近于作业所要求的存储区域。

特点：用最小空间满足要求。

循环适应算法:

接到内存申请时，在空闲块表中，上次找到的可用分区的下一个空闲分区开始查找可满足大小要求的第一个空闲分区。

该算法的分配和释放的时间性能较好，使空闲分区分布得更均匀，但较大的空闲分区不易保留。

4. 虚拟存储器的概念和特征，支撑虚拟存储器的物质基础(二级存储器结构和动态地址转换机构)

借助于外存空间，允许一个进程在其运行过程中部分装入内存。虚拟存储系统将内存和外存有机结合在一起，从而得到一个容量相当于外存，速度接近于内存的存储体系。

虚拟存储器的特征:

① 虚拟扩充。

② 部分装入。

③ 离散分配。

④ 多次对换。

5. 理解分页技术、分段技术、请求分页技术、请求分段技术的基本原理。给出逻辑地址，会计算物理地址。

分页技术基本思想:

允许一个进程的存储空间不必连续，可以分散地放在各个空闲的内存区域中。

分段技术基本思想:

内存以段为单位进行分配，每段单独占用一块连续的内存分区。各分区的大小由对应段的大小决定。

三．分页与分段的主要区别

分页和分段有许多相似之处,比如两者都不要求作业连续存放.但在概念上两者完全不同,主要表现在以下几个方面:

(1)页是信息的物理单位,分页是为了实现非连续分配,以便解决内存碎片问题,或者说分页是由于系统管理的需要.段是信息的逻辑单位,它含有一组意义相对完整的信息,分段的目的是为了更好地实现共享,满足用户的需要.

(2)页的大小固定,由系统确定,将逻辑地址划分为页号和页内地址是由机器硬件实现的.而段的长度却不固定,决定于用户所编写的程序,通常由编译程序在对源程序进行编译时根据信息的性质来划分.

(3)分页的作业地址空间是一维的.分段的地址空间是二维的.

请求分页技术:

当一个进程的部分页面在内存时就可调度它运行；在运行过程中若用到的页面尚未在内存，则把它们动态换入内存。

请求分段技术:

带虚存的段式存储管理技术,一个进程只有部分分段放在内存,仅用到某个段时才进行链接。

6. 理解各种页面置换算法的基本思想。熟练掌握FIFO、LRU、OPT三种页面置换算法，对于给定的地址访问序列能求出简化的页面走向，能画出不同置换算法的页面调度情况，并会计算缺页次数。

先进先出法（FIFO）:

总是淘汰在内存中停留时间最长的一页，即先进入内存的页，先被换出。

最近最少使用置换法(LRU):

思想：当需要置换一页时，选择在最近一段时间里最久没有使用过的页面予以淘汰。

最佳置换法（OPT）:

为调入新页面而必须预先淘汰某个老页面时，所选择的老页面应在将来不被使用，或者是在最远的将来才被访问。

第六章

1. 文件控制块的作用、目录文件和特别文件的概念

② 目录文件—— 由下属文件的目录项构成的文件。花名册。

③ 特别文件—— 特指各种外部设备。分为字符特别文件（输入输出设备），块特别文件（存储信息的设备）。

文件系统内部，给每个文件惟一地设置一个文件控制块。目的是为了便于对文件进行控制和管理。

2. 单级目录结构、二级目录结构、树型目录结构、非循环图目录结构的特点

单级目录结构：

优点是简单，能够实现按名存取。

单级目录结构有以下三个缺点：

① 查找速度慢。

② 不允许重名。

③ 不便于共享。

二级目录结构：

优点是：不同用户可有相同的文件名；提高了检索目录的速度；不同用户可用不同的文件名访问系统中同一文件。

缺点是这种结构仍不利于文件共享。

树型目录结构：

从根目录开始，一层一层地扩展下去，形成一个树形层次结构，每个目录的直接上一级目录称做该目录的父目录，而它的直接下一级目录称做子目录。系统中的每个文件都有唯一的路径名。

非循环图目录结构：

它允许一个文件或目录在多个父目录中占有项目，但并不构成环路。

这种结构方式叫做链接（Link）

3. 常用的文件分配方法有哪几种，理解多重索引文件分配方式的基本原理

常用文件分配方法有:连续分配、链接分配、索引分配三种。

4. 掌握UNIX系统的多重索引文件分配方式，在直接索引、一 次间接、二次间接、三次间接索引方式下，会计算单个文件的最大长度。

   例题：

   设文件索引节点中有7个地址项，此中4个地址 项 为直接地址索引， 2 个地址项是 一 级间接地址索引， 1个地址项二级间接地址索引， 每个地址项的大小为4字节，若磁盘索引块和磁盘数据块大小均为256字节，则可表示的单个文件最大长度。

4个直接索引：4*256 = 1k

2个一级间接索引：264256 = 32k

1个二级间接索引：16464*256 = 1024K

共1057k

第七章

1. 六种I/O控制方式是什么，DMA方式、通道方式的特点和作用

1．程序直接控制方式、程序查询方式、中断控制方式、DMA方式、独立通道方式、I/O处理器方式

DMA方式的特点和作用：

CPU来控制传输的数据块大小、传输的内存位置。在外设和内存之间开辟直接的数据交换通路。DMA控制器具有更强的功能，内存和设备间直接传送一批数据，用DMA控制器只能控制一台设备，适用高速（块）设备。原来的中断每个字节需要CPU干预，DMA每个数据块才需要CPU干预。

通道方式的特点和作用：

通道相当于一台小型的处理机。有运算和控制逻辑，自己的指令系统，但指令类型单一，专门负责输入、输出控制，具有执行I\O指令的能力，控制I\O设备工作；没有自己的内存，与CPU共享。

通道所需CPU干预更少，一个通道可以控制多台设备。可实现CPU、通道、I\O设备的并行操作。

2. I/O软件有哪几层

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-O5kE6QoO-1578104882283)(file:///C:\Users\颜美娴\AppData\Local\Temp\ksohtml15760\wps2.jpg)]

3. 在设备管理中引入缓冲技术的作用

① 缓解CPU与I/O设备间速度不匹配的矛盾。

② 提高它们之间的并行性。

③ 减少对CPU的中断次数，放宽CPU对中断响应时间的要求。

4. 掌握磁盘调度算法:先来先服务(FCFS)、最短寻道时间优先(SSTF)、 扫描法(SCAN)、 巡回扫描法(C SCAN),巡查法(L0OK和C-L00K)，对于给定的磁盘访问序列，能使用以上调度算法给出磁盘调度顺序，并会计算平均寻道长度。

式

DMA方式的特点和作用：

CPU来控制传输的数据块大小、传输的内存位置。在外设和内存之间开辟直接的数据交换通路。DMA控制器具有更强的功能，内存和设备间直接传送一批数据，用DMA控制器只能控制一台设备，适用高速（块）设备。原来的中断每个字节需要CPU干预，DMA每个数据块才需要CPU干预。

通道方式的特点和作用：

通道相当于一台小型的处理机。有运算和控制逻辑，自己的指令系统，但指令类型单一，专门负责输入、输出控制，具有执行I\O指令的能力，控制I\O设备工作；没有自己的内存，与CPU共享。

通道所需CPU干预更少，一个通道可以控制多台设备。可实现CPU、通道、I\O设备的并行操作。

2. I/O软件有哪几层

[外链图片转存中…(img-O5kE6QoO-1578104882283)]

3. 在设备管理中引入缓冲技术的作用

① 缓解CPU与I/O设备间速度不匹配的矛盾。

② 提高它们之间的并行性。

③ 减少对CPU的中断次数，放宽CPU对中断响应时间的要求。

4. 掌握磁盘调度算法:先来先服务(FCFS)、最短寻道时间优先(SSTF)、 扫描法(SCAN)、 巡回扫描法(C SCAN),巡查法(L0OK和C-L00K)，对于给定的磁盘访问序列，能使用以上调度算法给出磁盘调度顺序，并会计算平均寻道长度。

提供一篇磁盘调度算法相关的文章：https://blog.csdn.net/Jaster_wisdom/article/details/52345674