操作系统

填空题（1*20=20分）简单看看概念

选择题（1*20+ 2 * 5=30分）

简答题（4*5=20分）5道题目，辅修考了：进程的概念，基本特征，中断处理过程

综合题（5*6=30分）6道题目，

考：银行家算法，作业调度算法，PV原语，管程，页面替换算法，存储空间管理，文件索引

[TOC]

绪论

操作系统的定义

操作系统是计算机系统中的一个系统软件，是一些程序模块的集合，它们管理和控制计算机系统中的硬件及软件资源，合理地组织计算机工作流程。以便有效地利用这些资源为用户提供一个具有最够的功能、使用方便、可扩展、安全和可管理的工作环境，从而在计算机与用户之间起到接口的作用。

操作系统的基本类型和特点

批处理操作系统

操作员把用户提交的作业分类，把一批作业编成一个作业执行序列，由专门编制的监督程序自动依次处理

特点：用户脱机使用计算机、成批处理、多道程序运行

分时操作系统

把处理机的运行时间分成很短的时间片，按时间片轮转的方式，把处理机分配给各个进程使用

特点：交互性、多用户同时性、独立性

实时操作系统

在被控对象允许时间范围内做出响应

特征：对实时信息分析处理速度要比进入系统快、要求安全可靠

微机操作系统

单用户单任务OS

只允许一个用户上机，且只允许用户程序作为一个任务运行

最具代表性的是CP/M和MS-DOS

单用户多任务OS

只允许一个用户上机，但允许将一个用户程序分为若干个任务，使他们并发执行

最具代表性的是os/2和MS-WINDOWS

多用户多任务OS

允许多个用户通过各自的终端使用同一台主机，共享主机的各类资源，同时用户程序又可以分成几个任务使它们并发执行

最具代表性的是UNIX OS

操作系统的功能

处理机管理

存储管理

设备管理

文件系统管理（信息管理）

用户接口

程序一级接口

作业一级接口

思考题

问题：鼠标点击“绪论.ppt”图标到屏幕上显示该文件内容

这个过程中，按照先后顺序描述操作系统完成了哪些功能？（尽可能描述细节）

鼠标点击—设备管理，用户接口

启动powerpoint程序—-存储管理，处理器管理

打开绪论.ppt文件—-文件管理，设备管理，存储管理

在屏幕上显示—-设备管理，用户接口

操作系统的特点

并发是两或多个事件在同一时间间隔内发生。

共享性：系统中的所有资源不再为一个程序所独占，而是供同时存在于系统中的多道程序所共同使用

虚拟是指通过某种技术把一个物理实体变为若干个逻辑上的对应物

异步性和不确定性：程序的执行并非“一气呵成”，而是以“走走停停”的方式运行，即程序是以异步方式运行的

作业

是指在一次应用业务处理过程中，从输入开始到输出结束，用户要求计算机所做的有关该次业务处理的全部工作

系统调用

作用：系统调用是系统向编程人员（应用程序，用户程序）提供的唯一接口

实现过程：

（1）用户在源程序中使用系统调用，并给出系统调用名和参数，即产生一条相应的陷阱指令

（2）处理机在执行到这条指令后，引起处理机中断，并发出有关信号给陷阱处理机构

（3）该处理机构收到信号后，启动相关程序保护处理机现场，取系统调用功能号并寻找子程序入口，通过入口地址表找到该系统子程序并执行

（4）执行完毕后，退出中断，返回到用户程序的断点，恢复现场，继续执行用户程序

进程管理

程序顺序执行的特征

顺序性，一个程序开始执行必须要等到前一个程序已执行完成。

封闭性，程序一旦开始执行，其计算结果不受外界因素影响。

可再现性，程序的结果与它的执行速度无关（即与时间无关），只要给定相同的输入，一定会得到相同的结果

程序并发执行的特征

间断性，“走走停停”，一个程序可能走到中途停下来，失去原有的时序关系

失去封闭性，程序在并发执行时，是多个程序共享系统中的各种资源，因而这些资源的状态将由多个程序来改变，致使程序的运行失去了封闭性

不可再现性，程序在并发执行时，由于失去了封闭性，也导致失去了可再现性

并发

概念，一组在逻辑上相互独立的程序或程序段在执行过程中，其执行时间在客观上相互重叠

并发带来的效率提升

进程

概念：在操作系统中进程是一个拥有资源的基本单位，也是一个调度和执行的基本单位

特征：动态性（最基本），并发性，独立性，异步性，结构特性

	区别	联系
作业	用户向计算机提交任务的任务实体	一个作业可由多个进程组成，且必须至少一个
进程	1.完成用户任务的执行实体，具有并发特性。2.进程是竞争计算机系统资源的基本单位，从而其并发性受到系统自己的制约。
程序	静态概念，没有并发特性	不同的进程可以包含同一程序，只要该程序所对应的数据集不同。

进程的静态结构

PCB :OS感知进程的存在的唯一标识

PCB，由进程创建原语创建

程序段

数据结构集

进程状态转换

执行，等待，就绪

思考题

如果系统中有N个进程，运行的进程最多几个，最少几个；就绪进程最多几个，最少几个；等待进程最多几个，最少几个？

答：最多有1个进程运行，最少是0个，就绪进程最多N-1个，最少0个

等待进程最多N个，最少0个（死锁）

原语

概念：是指系统态下执行的某些具有特定功能的程序段

原语又称为“原子操作(Atomic Operation)”过程，作为一个整体而不可分割——要么全都完成，要么全都不做

机器指令级的:执行期间不允许中断

功能级的:作为原语的程序段不允许并发执行

临界区

概念：一个进程访问临界资源的那段程序代码称为临界部分或者称为临界区.即访问公用数据的那段程序

使用准则：

（1）不能假设各并发进程的相对执行速度。即各并发进程享有平等的、独立的竞争共有资源的权利，且在不采取任何措施的条件下，在临界区内任一指令结束时，其他并发进程可以进入临界区

（2）并发进程中的某个进程不在临界区时，它不阻止其他进程进入临界区；放弃处理机

（3）并发进程中的若干个进程申请进入临界区时，只能允许一个进程进入。

（4）从并发进程中的某个进程申请进入临界区时开始，应在有限时间内能够进入其临界区

即：空则让进，等则让权（让权等待），忙则等待，等则有限

信号量

信号量的本质是计数器，一个口袋，P是申请拿球，V是放球

sem>0表示有sem个资源可用

sem=0表示无资源可用

sem<0则| sem |表示sem等待队列中的进程个数

sem的应该初值大于等于零

P(S):表示申请一个资源

V(S):表示释放一个资源

进程互斥的实现

软件法：通过平等协商方式实现进程互斥

单标志算法，双标志、先检查算法，双标志、先修改后检查算法，先修改、后检查、后修改者等待算法

硬件法：关中断，专用指令（testset, swap）

信号量

单个临界资源：整型信号量，记录型信号量

多个临界资源:AND型信号量

管程

条件变量：cwait,csignal

局部变量,操作

实现进程的同步和互斥

进程的互斥：由于共享资源而引起的在临界区内不允许并发进程交叉执行的现象称为由共享公有资源而造成的对并发进程执行速度的间接制约

进程的同步：由于并发进程互相共享对方的私有资源所引起的直接制约

进程的前驱关系（时间同步）

一组有关的并发进程在执行时间上有严格的先后顺序时，就会出现时间上的进程同步问题，或者称为进程的前驱关系

进程通信

低级通信：进程之间控制信息的交换。一般只传送一个和几个字节的信息，达到控制进程执行速度的作用。（进程的同步和互斥）

高级通信：用户可以直接利用操作系统所提供的一组通信命令，高效地传送大量数据的一种通信方式。

方式：主从式 (master-servant system) 　，会话式(dialogue system)，

消息或信箱机制(message)，共享存储区方式(shared memory）

死锁

**概念：**指多个进程因竞争资源而造成的一种僵局，若无外力的作用，这些进程将永远不能再向前推进

产生死锁的必要条件：互斥，部分分配，不剥夺条件，环路等待

Mutual-exclusion - 一个口袋一个球，得到球才能继续
Wait-for - 得到球的人想要更多的球
No-preemption - 不能抢别人的持有的球
Circular-chain - 形成循环等待球的关系

预防死锁

**预防死锁设计思路：**设置某些限制条件，去破坏死锁四个必要条件中的一个或多个，来防止死锁。

防止“互斥条件”：使用Spooling技术来管理设备

防止“不剥夺”条件的出现：一个已经保持了某些资源的进程，当它再提出新的资源要求而不能立即得到满足时，必须释放它已经保持的所有资源，待以后需要时再重新申请

防止部分分配（摒弃请求和保持条件）：系统要求任一进程必须预先申请它所需的全部资源，而且仅当该进程的全部资源要求能得到满足时，系统才能给予一次性分配，然后启动该进程运行

防止“环路等待”条件的出现：把系统中所有资源类型线性排队，并按递增规则赋予每类资源以唯一的编号，进程申请资源时，必须严格按资源编号的递增顺序进行，否则系统不予分配

死锁避免：

安全状态：存在某种资源调度顺序，来为每个进程分配其所需资源，直至最大需求,保证所有进程正常运行完成，则称该状态为安全状态。

不安全状态：不存在可满足所有进程正常运行的资源调度顺序，则称该状态为不安全状态

避免死锁的实质是如何使系统不进入不安全状态

银行家算法

判断是否为安全状态，对于进程的资源请求，判断是否能够进行分配

银行家算法_Banker’s_Algorithm_哔哩哔哩_bilibili

死锁的检测和恢复

死锁的检测：实质是确定是否存在环路等待现象

死锁的恢复：立即结束所有进程的执行,并重新启动操作系统；撤销进程；剥夺资源

线程

线程是调度和执行的基本单位，不作为独立分配资源的单位

引入线程则是为了减少程序并发执行时的所付出的时空开销

线程本身拥有少数资源，多个线程共享所属进程的资源

线程分类：用户级线程，系统级线程

适用范围：多处理机系统，网络与分布式系统

处理器调度

调度的分级

作业调度（宏观调度，高级调度），交换调度（中级调度），内外存的进程交换，进程调度，分配处理机

作业调度的衡量

周转时间：从提交到完成的时间

带权周转时间：周转时间除运行时间

调度算法（考）

先来先服务（FCFS）：将用户作业和就绪进程按提交顺序或变为就绪状态的先后排成队列，并按照先来先服务的方式进行调度处理，它优先考虑在系统中等待时间最长的作业，而不管要求运行时间的长短

轮转法:

把CPU划分成若干时间片。将系统中所有的就绪进程按照FCFS原则，排成一个队列每次调度时将CPU分派给队首进程，让其执行一个时间片

时间片的选择：

时间片长度S＝R/Nmax

R：响应时间;

Nmax：最大进程数

多级反馈轮转法:

系统中设置多个就绪队列

每个就绪队列分配给不同时间片，优先级高的为第一级队列，时间片最小，随着队列级别的降低，时间片加大

优先级法:静态优先级,动态优先级

最短作业优先法

对预计执行时间短的作业（进程）优先分派处理机

比FCFS改善平均周转时间和平均带权周转时间，缩短作业的等待时间；

提高系统的吞吐量

最高响应比优先法:响应比R = 1 +（作业等待时间/ 作业执行时间）

实时系统中的任务分类

按照时限严格程度类型分类

硬实时任务：要求系统必须完全满足任务的时间要求

软实时任务：允许系统对任务的时限要求有一定的延迟，时限要求是一个相对条件

按照时限是周期or时刻分类

周期性任务：要求在周期T内完成或开始进行处理

非周期性任务：存在一个完成或开始进行处理的时间

存储管理

概念

**逻辑地址:**程序经编译或汇编以后形成目标程序，其指令的顺序都是以零作为参考地址，这些地址称为逻辑地址

虚拟地址空间:

虚存容量的扩大是以牺牲CPU工作时间以及内、外存交换时间为代价的（时间换空间）

虚拟存储器的最大容量（用户编程空间）由计算机的地址结构和寻址方式决定

如直接寻址时，若CPU的有效长度为16位，则其地址范围是0～～64K-1(216-1)，最大容量为64K**(确认地址位数)**

静态重定位

在装入一个作业时，把作业中的指令地址和数据地址全部转换为物理地址（地址转换工作是在作业执行前集中一次完成的）在作业执行过程中就无须再进行地址转换工作

动态重定位:地址转换是在作业执行时动态完成

内存保护

上下界保护法

在CPU中设置一对上界寄存器和下界寄存器存放用户作业在内存中的起始地址和终止地址；每当CPU要访问内存时，硬件自动将被访问的内存地址与界限寄存器的内容进行比较，以判断是否越界

保护键法

为每一个被保护存储块分配一个单独的保护键。保护键可设置成对读写同时保护的或只对读、写进行单项保护的；在程序状态字中则设置相应的保护键开关字段, 不同的进程赋予不同的开关代码；

界限寄存器与CPU的用户态或核心态工作方式相结合的保护方式

在这种保护模式下，用户态进程只能访问那些在界限寄存器所规定范围内的内存部分，而核心态进程则可以访问整个内存地址空间

内存扩充

覆盖方式：

一个程序的几个代码段或数据段，按照时间先后来占用公共的内存空间

交换方式：

由操作系统把那些在内存中处于等待状态的进程换出内存，以及把那些等待事件已经发生，处于就绪态的进程换入内存，以及那些即将执行的程序数据调入内存

调入方式：

请求调入方式, 预调入方式

内存管理

常用方法:

分区存储管理,页式管理,段式管理,段页式管理

动态分区分配

最先适应法:要求空闲分区按首址递增的次序组织可用表或自由链

最佳适应法:空闲分区链按照分区容量递增的方式形成

最坏适应法:要求空闲区按大小递减的顺序组织可用表(或自由链)

动态分区回收:

a,与空闲区合并。b,与上空闲区合并。c,与下空闲区合并。d,不合并

缺点：

所谓“碎片”(fragmentation)：就是指不能分配给作业使用的一段无效存贮空间。

固定分区管理存在内碎片，可变分区管理存在外碎片

碎片使得内存的空闲空间得不到充分利用，并且存储每个用户作业都要受到实际存储容量的限制。

页式管理（考计算）

页式管理中给定逻辑地址的组成，页表，将逻辑地址转换为物理地址

计算过程：程序地址/页长

页式管理的问题：CPU要存取一个数据，需访问主存两次

解决：快表

请求（动态）页式管理的实现：

与每个虚页号相对应，除了页面号之外，再增设该页是否在内存的中断位以及该页在外存中的副本起始地址，还应增加一项以记录该页是否曾被改变

段式存储管理（考计算）

给定段表，计算逻辑地址对应的物理地址

	区别
页式管理	页是信息的物理单位，进行分页是出于系统管理的需要；页的大小是固定的。
段式管理	段是信息的逻辑单位，分段是出于用户的需要；段的大小是可变的。

页面置换算法（考）

注意刚开是空页放入也计入表格

FIFO算法：淘汰最早建立的页面，Belady现象

LRU:最近最久没有使用,当需要淘汰时，应淘汰当前时间最近的一段时间内最久没有使用过的页

LFU:最不经常使用,淘汰被访问次数最少的页

NUR：当需要淘汰某一页时，从那些最近一个时期内未被访问的页中任选一页淘汰

理想型页面置换法（OPT）：选择“未来不再使用的”或“在离当前最远位置上出现的”页面被置换

缺页率的计算：缺页次数/访问页面次数

Belady现象

采用FIFO算法时，如果对一个进程未分配它所要求的全部页面，有时就会出现分配的页面数增多，缺页率反而提高的异常现象。

原因：

FIFO算法的置换特征与进程访问内存的动态特征是矛盾的，即被置换的页面并不是进程不会访问的

局部性原理

指程序在执行过程中的一个较短时期，所执行的指令地址和指令的操作数地址，分别局限于一定区域

还可以表现为：

时间局部性，即一条指令的一次执行和下次执行，一个数据的一次访问和下次访问都集中在一个较短时期内；

空间局部性，即当前指令和邻近的几条指令，当前访问的数据和邻近的数据都集中在一个较小区域内

内存抖动问题

定义：

在虚存中，页面在内存与外存之间频繁调度，以至于调度页面所需时间比进程实际运行的时间还多，此时系统效率急剧下降，甚至导致系统崩溃。这种现象称为颠簸或抖动

产生的原因

分配给进程的物理页面数太少

页面淘汰算法不合理

避免的方法

扩大工作集

选择不同的淘汰算法

文件系统

文件的逻辑结构与存取方法

逻辑结构

字符流式的无结构文件：源程序、可执行文件、库函数等

记录式的有结构文件：数据库

存取方法

(1)顺序存取法

⑵ 随机（直接）存取法

⑶ 按关键字存取法

文件的物理结构与存储设备

物理结构

为了有效地管理文件存储器，通常把文件存储空间划分成若干个大小相等的物理块，物理块是分配及传输信息的基本单位

常用的物理结构：连续文件，串联文件，索引文件；

存储设备

顺序存储设备：磁带

直接存储设备：磁盘

磁盘臂调度算法

先来先服务(FCFS):

磁盘驱动程序每次接收一个请求并按照接收顺序完成请求

最短寻道时间优先（shortest seek time first，SSTF）:

下一次总是处理与磁头距离最近的请求以使寻道时间最小化

文件空间管理

空闲文件目录

空闲块链

UNIX中使用成组链法

位视图

文件接口

OPEN, close, create,delete

目录结构

单级目录

结构简单，实现容易

搜索速度较慢，不允许文件重名

二级目录

解决了文件的重名问题和文件共享问题

提高搜索速度，查找时间降低

多级目录

层次结构清晰，便于管理和保护；有利于文件分类；解决重名问题；

查找一个文件按路径名逐层检查，由于每个文件都放在外存，多次访盘影响速度

文件的共享

绕道法

使用绕道法进行文件共享时，用户从当前目录出发向上返回到与所要共享文件所在路径的交叉点再顺序下访到共享文件

链接法

在相应目录表之间进行链接。即将一个目录中的链指针直接指向被共享文件所在的目录

基本文件目录表BFD

把所有文件目录的内容分成两部分：

基本文件目录表BFD：存放除了文件名之外的文件说明信息和文件内部标识符；

符号文件目录表SDF：存放文件名和文件内部标识符

存取权限控制

（1）文件的共享：指不同的用户共同使用一个文件

（2）文件的保护：指文件本身需要防止文件的拥有者或其他用户破坏文件内容。

（3）文件的保密：指未经拥有者许可，任何用户不得访问该文件。（防止窃取）

设备管理

SPOOLNG系统

假脱机真联机技术：设备管理的虚拟技术

它使用直接存取的大容量磁盘作为缓冲，将一个可共享的磁盘空间改造成若干个输入设备和输出设备，并使得I/O设备和CPU并行操作。（在联机情况下实现的同时外围操作）

SPOOLING 系统的组成

（1）输入井和输出井（2）输入缓冲区和输出缓冲区

（3）输入进程和输出进程（输入管理模块、输出管理模块）

特点：

提高了I/O速度

从对低速I/O设备进行的I/O操作变为对输入井或输出井的操作,如同脱机操作一样,提高了I/O速度,缓和了CPU与低速I/O设备速度不匹配的矛盾
设备并没有分配给任何进程

在输入井或输出井中,分配给进程的是一存储区和建立一张I/O请求表.
实现了虚拟设备功能

多个进程同时使用一独享设备,而对每一进程而言,都认为自己独占这一设备,不过,该设备是逻辑上的设备

数据传输控制方式

程序直接控制：由用户进程来直接控制内存或CPU和外设间的信息传送。

中断方式：进程通过CPU发出指令启动外设，该进程阻塞。当输入完成时，I/O控制器通过中断请求线向CPU发出中断信号，CPU进行中断处理。

DMA方式：在外设和内存之间开辟直接的数据交换通路。（成块）

通道控制方式：CPU发出启动指令，指出通道相应的操作和I/O 设备，该指令就可启动通道并使该通道从内存中调出相应的通道指令执行。（成组）

中断技术

中断的概念

指CPU对系统发生的某个事件作出的一种反应：

CPU暂停正在执行的程序，

保留现场后自动转去执行相应的处理程序，

处理完该事件后再返回断点继续执行被“打断”的程序。

中断的处理过程

1、保存被中断程序的现场，其目的是为了在中断处理完之后，可以返回到原来被中断的地方继续执行；

2、分析中断源，判断中断原因；

3、转去执行相应的处理程序；

4、恢复被中断程序现场，继续执行被中断程序。

分类

根据中断源的产生的条件，可把中断分为外中断和内中断

中断和陷阱的主要区别

将中断源按照外界因素的作用程度进行划分，常可分为自愿型中断与强迫型中断两大类

	区别
中断	强迫型中断
陷阱	自愿型中断

缓冲技术

引入缓冲技术的原因

1、改善CPU与I/O设备间速度不匹配的矛盾

2、可以减少对 CPU的中断频率，放宽对中断响应时间的限制

3、提高 CPU和 I／O设备之间的并行性

缓冲的设置

根据位置：专用硬件缓冲器，软件缓冲

根据个数：单缓冲、双缓冲和缓冲池

设备分配数据结构

设备无关性

为了提高系统的可适应性和可扩展性，我们希望所编制的用户程序与实际使用的物理设备无关，这就是所谓与设备无关性。

为此，我们将逻辑设备与物理设备区分，并引入逻辑设备名称和物理设备名称的概念

为了实现与设备的无关性，系统中必须有一张联系逻辑设备名称和物理设备名称的映射表，（ＬＵＴ表）

用户I/O：用户程序通过内核提供的系统调用接口与逻辑I/O层交互

设备无关程序

对设备驱动程序的统一接口——向用户层软件提供一个一致接口

设备命名——设备无关软件负责将设备名映射到相应驱动程序

设备保护——检查是否有权访问申请的设备（个人计算机不提供任何保护）

提供独立于设备块大小——逻辑记录到物理记录的转换

缓冲区管理与块设备的存储分配

独占性外围设备的分配和释放——通过 OPEN 打开相应的设备文件进行申请；关闭独占设备同时将释放该设备

错误报告——关键系统数据结构出错（如读磁盘使用状况位图），操作系统打印出错信息，并终止运行

设备驱动程序的功能

(1) 接收由I/O进程发来的命令和参数，并将命令中的抽象要求转换为具体要求，例如，将磁盘块号转换为磁盘的盘面、磁道号及扇区号。　

(2) 检查用户I/O请求的合法性，了解I/O设备的状态，传递有关参数，设置设备的工作方式。

(3) 发出I/O命令，如果设备空闲，便立即启动I/O设备去完成指定的I/O操作；如果设备处于忙碌状态，则将请求者的请求块挂在设备队列上等待。　

(4) 及时响应由控制器或通道发来的中断请求，并根据其中断类型调用相应的中断处理程序进行处理。

(5) 对于设置有通道的计算机系统，驱动程序还应能够根据用户的I/O请求，自动地构成通道程序。

I/O中断处理程序

通知用户程序输入输出操作推进的程度

通知用户程序输入输出操作正常结束（设备通知通道/控制器→CPU）

通知用户程序发现的输入输出操作异常，及提前中止操作的原因

通知程序外围设备上有重要的异步信号，如设备报到、设备结束等

LINUX操作系统

Linux进程调度原则：

按照进程优先级，调度最高优先级进程

进程优先级随时间动态变化

Linux的进程分为普通进程和实时进程

对于普通进程采用可抢占式动态优先级调度：SCHED_OTHER

对于实时进程，采用两种调度策略：

基于优先级(rt-priority)的先进先出调度：SCHED_FIFO，

基于优先级(rt-priority)的时间片轮转调度：SCHED_RR

Linux系统采用段页式存储管理技术，提供虚拟存储功能

补充

管程

是一种共享的数据结构，内部资源只能由内部函数访问，

基本特征：

各外部进程/线程只能通过管程提供的特定入口才能访问共享数据，

每次仅允许一个进程在管程内执行某个内部进程