一、操作系统概论

1、操作系统的概念 操作系统的定义

操作系统是一套系统软件，是一些程序模块的集合－它们能以尽量有效、合理的方式组织和管理计算机的软硬件资源，合理组织计算机的工作流程，控制程序的执行并向用户提供各种服务功能，使得用户能够灵活、方便、有效的使用计算机，使计算机系统高效运行。

操作系统的基本功能:

操作系统的地位:

操作系统是对裸机的第一次扩充； 操作系统是其他软件的基础；

操作系统是用户与计算机的接口； 操作系统将计算机变成了虚拟机；

2、操作系统的类型 批处理系统

主要特征：

1）用户脱机使用计算机。 2）自动成批处理。（后备作业） 3）单/多道程序运行。

优点：资源利用率高，系统吞吐量大。 缺点：作业周转时间长，交互能力差。

分时系统

分时系统采用时间片轮转方式，多个用户服务。具有特点：

1）交互性：用户可以动态提交与控制程序运行，交互性好。 2）多路性：多个用户同时共享一个计算机，充分发挥系统的效率。 3）独立性：多个用户相互独立，如同自己独占计算机一样。

实时系统

实时系统用于实时控制和实时信息处理领域中。主要特点：

1）即时响应：保证在控制对象要求的严格时间内做出响应。（非用户） 2）高可靠性：系统本身要安全可靠。

实时系统往往具有一定的专用性，因此系统资源利用率可能较低。

分时操作系统与实时操作系统的比较：

设计目标不同：前者为了给多用户提供一个通用的交互型开发运行环境，后者通常为特殊用途提供专用系统；

交互性强弱不同：前者交互性强，后者交互性弱；

响应时间要求不同：前者以用户能接受的响应时间为标准，后者则与受控对象有关，变化范围很大。

3、操作系统的基本特征： 并发性

并发性是指两个或两个以上的事件或活动在同一时间间隔内发生。 采用了并发技术的系统又称为多任务系统

共享性

共享指系统资源可被多个并发进程共同使用，而不是被某个进程独占。 资源共享方式分两种：互斥访问、同时访问。

异步性

异步性，或称随机性，是指进程的执行不是一贯到底的，而是“走走停停”，具有随机性。

虚拟性

虚拟性是指操作系统是把物理上的一个实体变成逻辑上的多个对应物，或把物理上的多个实体变成逻辑上的一个对应物的技术。

前者如多道程序并发占用1个CPU；后者如虚拟内存计数等。

采用虚拟技术的目的是为用户提供易于使用、方便高效的操作环境。

4、操作系统接口： 作业级接口（操作接口） 程序级接口（系统调用）

5、多道程序设计：

多道程序设计（multiprogramming）是指允许多个程序(作业)同时进入内存并进行交替计算的一种设计方法。

多道程序设计的特点:

1) 多道运行：计算机内存中同时存放几道相互独立的程序。

2) 宏观上并行：进入内存的多道程序都处于运行状态中，即它们开始且尚未结束运行。 3) 微观上串行：各道程序轮流使用计算机的单CPU，交替执行。 这种执行方式称为“并发执行”。

二、处理机管理

1.进程：

定义：进程是具有独立功能的程序（段）在某个数据集上的一次运行活动，是系统进行资源分配的独立单位。

由程序块、数据块、进程控制块等多个部分组成。

进程与程序的关系

进程是动态的，程序是静态的；

进程是由程序和数据等多个部分组成的;

多个进程可以对应一个程序；

进程有生命周期，是短暂的；而程序是相对长久的； 进程具有并发性，而程序没有。

2.进程状态及转换：

运行态→等待态：等待使用资源或某事件发生，如等待外设传输。 等待态→就绪态：相应等待事件己经发生，如外设传输结束。（等待结束） 运行态→就绪态：时间片到或出现了更高优先权进程。（落选） 就绪态→运行态：进程被调度程序选中。

3.进程控制块PCB：

PCB中包含三类信息：描述信息、控制信息和现场信息。

系统利用PCB来控制和管理进程，PCB是系统感知进程存在的唯一标志。 进程与PCB是一一对应的。

5.进程调度算法

（1）先来先服务算法 （2）时间片轮转法

轮转法的基本概念是将CPU的处理时间分成固定大小的时间片。 如果一个进程在被调度选中之后用完了系统规定的时间片，但未完成要求的任务，则它自行释放自己所占有的CPU而排到就绪队列的末尾，等待下一次调度。 该算法一般仅适用于进程调度，不适用于作业调度。

（3）优先数算法

优先级法可被用作作业或进程的调度策略。

首先，系统或用户按某种原则为作业或进程指定一个优先级来表示其优先权。 该算法的核心是确定进程或作业的优先级。确定优先级的方法可分为静态法和动态法。

8.作业调度算法: （综合应用） （1）先来先服务算法 （2）短作业优先法算法 （3）最高响应比法算法

9.进程间制约关系： 互斥

不允许两个以上的共享资源的并发进程同时进入临界区称为互斥。 显然，临界资源的访问是互斥的，即临界区的执行是互斥的。

同步

指系统中多个进程中发生的事件存在某种时序关系，需要相互合作，共同完成一项任务。

10.信号量：

11.PV定义： P(s)

{

s.value = s.value --; if (s.value < 0)

{

改当前进程状态为等待状态；

将其PCB插入相应等待队列末尾s.queue; }

}

V(s) {

s.value = s.value ++; if (s.value < = 0)

{

唤醒等待队列s.queue中的1个进程； 改被唤醒进程的状态为就绪态； 并将其插入就绪队列； } }

信号量变量赋初始值Si=1；

14.死锁： 所谓死锁，是指各并发进程彼此互相等待对方所拥有的资源，且这些并发进程在得到对方的资源之前不会释放自己所拥有的资源。从而造成多进程都想得到资源而又都得不到资源，各并发进程不能继续向前推进的状态，这种现象称为死锁。

产生死锁的根本原因在于系统资源数少于并发进程所要求的资源数，且资源访问是互斥的。 （1）并发进程的资源竞争； （2）程序设计中的错误；

产生死锁的4个必要条件 (1) 互斥条件。 (2) 不剥夺条件。 (3) 占有且等待条件。

(4) 环路条件。

只要破坏其中一个条件，死锁就可防止。

15.解决死锁的方法：预防、避免、检测、恢复；银行家算法，按序分配、静态分配

16.进程通信：含义及其分类

进程之间互相交换信息称为进程通信IPC

低级通信与高级通信机制

低级通信一般只传送一个或几个字节的信息，以达到控制进程执行速度的作用。 高级通信要传送大量数据。高级通信的目的不是为了控制进程的执行速度，而是为了交换信息。

三、存储管理

1.存储管理的功能 内存分配与回收 (1) 分配结构： (2) 放置策略： (3) 交换策略： (4) 调入策略： (5) 回收策略：

内存保护

上下界保护法

界限寄存器与CPU状态结合法

地址映射、内存扩充；

2.地址重定位：

目标程序中的地址是一个从0开始的地址，并不是内存的实际地址。 把用户目标程序使用的地址称为逻辑地址。

一个用户作业的目标程序的逻辑地址集合称为该作业的逻辑地址空间。

我们把主存中的实际存储单元称为物理地址（绝对地址），物理地址的总体相应构成了用户程序实际运行的物理地址空间。

为了保证程序的正确运行，必须把程序和数据的逻辑地址转换为物理地址，这一工作称为地址转换或重定位。

静态重定位：发生在作业执行前一次完成，多由软件独立完成；

动态重定位：发生在程序执行过程中，通常借助于地址转换机构硬件与软件共同实现。

3.单一连续分区： 概念

也称单用户分区，适用于单道系统的情况。 系统将主存空间分为系统区和用户区，系统区存放操作系统常驻代码和数据，用户区全部归1个用户作业所占用。

在这种管理方式下，任一时刻主存储器中最多只有一道程序。

不足

管理方案简单；但仅适合于单道系统！内存利用率低！

4.固定分区存储管理： 概念

系统将用户区域固定划分成若干个大小不等或相等的区域，一个分区可装入一个作业，实现多道程序设计技术。

在执行中，分区个数和大小不发生变化。

优缺点

适合于多道系统，支持多进程并发执行；但内存利用率不高。

5.动态分区存储管理： （1）基本思想

也称动态分区法，在系统初启时，除了操作系统中常驻内存部分之外，只有一个用户空闲分区。随着作业的装入、撤离，主存空间被分成多个分区，部分占用，部分空闲。 具有以下特征:

内存不是预先划分好的；

作业装入时，若有足够空间，则按需要分割分区给该进程；否则等待；

（2）分配：

最先适应法FF

最先适应法要求可用表或自由链按起始地址递增的次序排列。

该算法的最大特点是一旦找到大于或等于所要求内存长度的分区，则结束探索。 即找到第一个满足要求的低地址空闲区，分割分配。

最佳适应法BF

最佳适应算法按照空间从小到大的次序组成空闲区可用表或自由链。 当用户作业或进程申请一个空闲区时，存储管理程序从表头开始查找，当找到第一个满足要求的空闲区时，停止查找。

即找到那个满足大小且是最小的空闲区，分割分配。

最坏适应法WF

最坏适应算法要求空闲区按其空间大小递减的顺序组成空闲区可用表或自由链。

当用户作业或进程申请一个空闲区时，顺序查找到第一个满足要求的空闲区用来分配。 即找到那个满足大小且是最大的空闲区，分割分配。

（3）零头（碎片）：内零头，外零头；

各种管理方式存在的零头类型，并分析解决方案。

不能被再次直接分配的小空闲区称为碎片。

6.分页式存储管理（综合应用） （1）分页式存储管理的基本思想

理解连续分配和不连续分配；

分区式管理属于连续管理方式，尽管方式简单，但存在着严重的碎片问题，使得内存的利用率不高。页式管理正是为了减少碎片而提出的一种非连续的内存管理方案，应用广泛。

页较小，每个作业产生的碎片小于1个页面。

非连续方式不用移动即可实现大作业的装入，增加作业装入数量。

（2）页表的结构与内容 （3）逻辑地址结构的计算 （4）多级页表的计算

（5）地址重定位及其计算

例：在一个分页虚存系统中，用户编程空间32 个页，页长1KB，主存为16KB。如果用户程序有10 页长，若己知虚页0、1、2、3，已分到页框8、7、4、10 ，试把虚地址0AC5H 和1AC5H 转换成对应的物理地址。（构建页表、计算物理地址）

带有快表的请求页式地址地址映射过程

7.虚拟存储管理

（1）虚拟存储器的概念及其优缺点；

（2）请求分页式存储管理页表基本内容；

（3）理解缺页中断、影响因素；

在地址映射过程中，在页表中发现所要访问的页不在内存，则产生缺页中断。

（4）页面淘汰算法 （综合应用） FIFO、LRU算法的应用；

（1）最佳页框算法（OPT）

淘汰以后不再需要的或最远的将来才会用到的页框， 也称Belady 算法。无法实现 （2）先进先出算法（FIFO）

选择在内存中驻留时间最长的页并淘汰之，访问位保存页面装入的时间。简单，效率低 （3）最近最久未用算法（LRU）

选择最后一次访问时间距离当前时间最长的一页并淘汰之，即淘汰没有使用的时间最长的页。

访问位保存最近访问的时间。局部原理 （4）最近最不常用算法（LFU）

选择访问次数最少的页面淘汰之； 访问位保存页框访问次数；软件复用

8.抖动的概念及其原因，解决方法

9.段页式管理

二维逻辑地址；每个进程1个段表，每段1个页表；

例：在某采用分页式虚拟存储管理的系统中，有一用户作业，它依次要访问地址序列是：115，228，120，88，446，102，321，432，260，167。若分配给作业可使用的主存空间共300B，作业的页大小为100B。

假设开始时内存页框是空的，请回答：

按FIFO和LRU页面调度算法分别计算缺页次数和淘汰的页号。