概述

操作系统
是管理系统资源、控制程序执行，改善人机界面，提供各种服务，合理组织计算机工作流程和为用户有效使用计算机提供良好运行环境的最基本的一种系统软件。
操作系统中最基础的抽象
进程抽象–是对已进入主存正在运行的程序在处理器上操作的状态集的抽象。
虚存抽象–是对物理主存的抽象，进程可获得一个硕大的连续地址空间来存放可执行程序和数据，可使用虚拟地址来引用物理主存单元。
文件抽象–是对磁盘之类存储设备的抽象。
操作系统的主要特性
并发性
指两个或两个以上的事件或活动在同一时间间隔内发生
发挥并发性能够消除系统中部件和部件之间的相互等待，有效地改善系统资源的利用率，改进系统的吞吐率，提高系统效率
共享性
共享指操作系统中的资源可被多个并发执行的进程所使用
第三个特性–异步性
操作系统的发展和形成
人工操作阶段
缺点：
用户上机独占全机资源，造成资源利用率不高，系统效率低下
手工操作多，浪费处理机时间，也极易发生差错
数据的输入，程序的执行、结果的输出均联机进行，从上机到下机的时间拉得非常长
管理程序阶段
多道程序设计与操作系统的形成
多道程序设计
是指允许多个程序同时进入一个计算机系统的主存储器并启动进行计算的方法
采用多道程序设计提高了效率，即增长了单位时间的算题量，但对每道程序来说，却延长了计算时间。
多道程序设计技术提高资源利用率和系统吞吐率是以牺牲用户的响应时间为代价的。
程序等待I/O操作的时间占其运行时间的比例为p，当主存中有n道程序时，所有程序都等待I/O的概率是pn，那么，
CPU利用率=1-p^n
有点和缺点：
提高了CPU的利用率
提高了主存和I/O设备的利用率
改进了系统的吞吐率
充分发挥了系统的并行性
其主要缺点是: 作业周转时间延长
操作系统的分类
1 批处理操作系统
批处理系统的主要特征：
用户脱机工作
成批处理作业
多道程序运行
作业周转时间长
2 分时操作系统
分时系统的特征
同时性
独立性
及时性
交互性
3 实时操作系统
新一代微机操作系统
具有以下特点：
（1）开放性
（2）通用性
（3）高性能
（4）采用微内核结构
操作接口
又称作业级接口，操作系统为用户提供的操作控制计算机工作和提供服务手段的集合，通常有操作控制命令、图形操作界面(命令)、以及批处理系统提供的作业控制语言(命令)等等。
内核的基本属性
内核是由中断驱动的
内核是不可抢占的
内核部分程序在屏蔽中断状态下执行
内核可以使用特权指令
虚拟机具有的特性
内核和裸机组成的虚拟机具有以下特性：
1）虚拟机没有中断，
2）虚拟机为每个进程提供了一台虚拟处理器，
3）虚拟机为进程或模块提供了功能较强的指令系统。

进程管理

进程控制块PCB,程序段，数据段构成进程镜像（进程实体）。
PCB是进程存在的唯一标志。
进程：进程是进程实体的运行过程，是系统进行资源分配和调度的一个独立单位。
是一个动态的，过程性的概念。
特征：
动态性：进程是程序的一次执行。
并发性：指多个进程实体，同存于内存中，能在一段时间内同时运行。
独立性：进程实体是一个能独立运行，独立获得资源和独立接受调度的基本单位。
异步性：由于进程相互制约，使进程具有执行的间断性。
结构性：每个进程都配置一个PCB对其进行描述，从结构上看，进程实体是由程序段，数据段和进程控制段组成。
状态
运行状态：进程正在处理机上运行。
就绪状态：进程已处于准备运行的状态，即进程获得了除处理机之外的一切所需资源，一旦得到处理机即可运行。
阻塞/等待状态：进程正在等待某一事件而暂停运行。
创建状态：进程正在被创建，尚未转到就绪状态。
结束状态：进程正从系统中消失。
特权指令
是指只能提供给操作系统的核心程序使用的指令，
如启动I/O设备、设置时钟、控制中断屏蔽位、清主存、建立存储键，加载PSW等
中断的定义
中断是指程序执行过程中，遇到急需处理的事件时，暂时中止CPU上现行程序的运行，转去执行相应的事件处理程序，待处理完成后再返回原程序被中断处或调度其他程序执行的过程。
外中断(中断或异步中断)–是指来自处理器之外的中断信号，包括时钟中断、键盘中断、它机中断和设备中断等
内中断(异常或同步中断)–是指来自处理器内部，通常由于程序执行中，发现与当前指令关联的、不正常的、或是错误的事件。
中断和异常的区别
• 中断是由与现行指令无关的中断信号触发的(异步的)，且中断的发生与CPU处在用户模式或内核模式无关，在两条机器指令之间才可响应中断，一般来说，中断处理程序提供的服务不是为当前进程所需的；
• 异常是由处理器正在执行现行指令而引起的，一条指令执行期间允许响应异常，异常处理程序提供的服务是为当前进程所用的。异常包括很多方面，有出错(fault)，也有陷入(trap)等。
进程的定义和性质
进程是可并发执行的程序在某个数据集合上的一次计算活动，也是操作系统进行资源分配和保护的基本单位。
进程是一个既能用来共享资源，又能描述程序并发执行过程的一个基本单位。
操作系统为什么要引入进程概念?
原因1-刻画系统的动态性，发挥系统的并发性，提高资源利用率。
原因2-它能解决系统的“共享性”，正确描述程序的执行状态。
进程的属性
•结构性：
•共享性：
•动态性：
•独立性：
•制约性：
•并发性：
进程三态模型及其状态转换

进程三态模型及其状态转换

具有挂起功能的进程状态及其转换
进程的描述和组成
进程映象
进程控制块
进程程序块
进程核心栈
进程数据块
进程控制块P C B
是操作系统用于记录和刻划进程状态及有关信息的数据结构。也是操作系统掌握进程的唯一资料结构，它包括了进程执行时的情况，以及进程让出处理器后所处的状态、断点等信息。
进程控制块包含三类信息
标识信息
现场信息
控制信息
处于同一状态的所有PCB链接在一起的数据结构称为进程队列。
同一状态进程的PCB既可按先来先到的原则排成队列;也可按优先数或其它原则排成队列。
进程切换
是让处于运行态的进程中断运行，让出处理器，这时要做一次进程上下文切换、即保存老进程状态而装入被保护了的新进程的状态，以便新进程运行
线程的概念
操作系统中引入进程的目的是为了使多个程序并发执行，以改善资源使用率和提高系统效率，
操作系统中再引入线程，则是为了减少程序并发执行时所付出的时空开销，使得并发粒度更细、并发性更好。
线程
是操作系统进程中能够独立执行的实体（控制流），是处理器调度和分派的基本单位。线程是进程的组成部分，每个进程内允许包含多个并发执行的实体（控制流），这就是多线程。
线程的实现
•用户级线程ULT(如Java ,Informix)
•内核级线程KLT(如OS/2)。
•混合式线程(如，Solaris)。
处理机调度的层次
作业从进入系统成为后备作业开始，直到运行结束退出系统为止，需经历不同级别的调度。
•高级调度
•中级调度
•低级调度
选择调度算法的原则
l 资源利用率
CPU利用率=CPU有效工作时间/CPU总的运行时间，
CPU总的运行时间=CPU有效工作时间+CPU空闲等待时间。
2 响应时间
•交互式进程从提交一个请求(命令)到接收到响应之间的时间间隔称响应时间。
•使交互式用户的响应时间尽可能短，或尽快处理实时任务。
•这是分时系统和实时系统衡量调度性能的一个重要指标。
3 周转时间
•批处理用户从作业提交给系统开始，到作业完成为止的时间间隔称作业周转时间，应使作业周转时间或平均作业周转时间尽可能短。
•这是批处理系统衡量调度性能的一个重要指标。
4 吞吐率
单位时间内处理的作业数。
5 公平性
确保每个用户每个进程获得合理的CPU份额或其他资源份额，不会出现饿死情况。
如果作业i提交给系统的时刻是ts，完成时刻是tf，该作业的周转时间ti为：
ti = tf - ts
实际上，它是作业在系统里的等待时间与运行时间之和。
为了提高系统的性能，要让若干个用户的平均作业周转时间和平均带权周转时间最小。
平均作业周转时间 T = (Σti) / n
如果作业i的周转时间为ti，所需运行时间为tk，则称wi=ti /tk为该作业的带权周转时间。
ti是等待时间与运行时间之和，故带权周转时间总大于1。
平均作业带权周转时间W = (Σwi) / n
低级调度的基本类型
第一类称剥夺式：
两种处理器剥夺原则，
一是高优先级进程/线程可剥夺低优先级进程/线程，
二是当运行进程/线程时间片用完后被剥夺。
第二类称非剥夺式：
作业调度和低级调度算法
1 先来先服务算法
三个作业同时到达系统并立即进入调度：作业名/所需CPU时间:作业1/28，作业2/9，作业3/3。采用FCFS算法，平均作业周转时间为35。
若三个作业提交顺序改为作业2、1、3，平均作业周转时间约为29。
若三个作业提交顺序改为作业3、2、1，平均作业周转时间约为18。
FCFS调度算法的平均作业周转时间与作业提交的顺序有关。
2 最短作业优先算法
SJF算法以进入系统的作业所要求的CPU时间为标准，总选取估计计算时间最短的作业投入运行。
算法易于实现，效率不高，主要弱点是忽视了作业等待时间。
会出现饥饿现象。
SJF的平均作业周转时间比FCFS要小，故它的调度性能比FCFS好。
实现SJF调度算法需要知道作业所需运行时间，否则调度就没有依据，要精确知道一个作业的运行时间是办不到的。
四个作业同时到达系统并进入调度：作业名/所需CPU时间:作业1/9，作业2 ，作业3/10，作业4/8。
SJF作业调度顺序为作业2、4、1、3，
平均作业周转时间T = 17，平均带权作业周转时间W= 1.98。
如果施行FCFS调度算法，平均作业周转时间T =19，平均带权作业周转时间
W = 2.61。
3 最短剩余时间优先算法
SRTF把SJF算法改为抢占式的。一个新作业进入就绪状态，如果新作业需要的CPU时间比当前正在执行的作业剩余下来还需的CPU时间短，SRTF强行赶走当前正在执行作业。称最短剩余时间优先算法
此算法不但适用于JOB调度，同样也适用于进程调度。
4 响应比最高者优先算法
FCFS与SJF是片面的调度算法。FCFS只考虑作业等候时间而忽视了作业的计算时问，SJF只考虑用户估计的作业计算时间而忽视了作业等待时间。
HRRF是介乎这两者之间的折衷算法，既考虑作业等待时间，又考虑作业的运行时间，既照顾短作业又不使长作业的等待时间过长，改进了调度性能。
响应比＝1+已等待时间/估计运行时间
•短作业容易得到较高响应比，
•长作业等待时间足够长后，也将获得足够高的响应比，
•饥饿现象不会发生。
时间片轮转调度算法
时间片调度做法是：调度程序每次把CPU分配给就绪队列首进程使用一个时间片，例如100ms，就绪队列中的每个进程轮流地运行一个时间片。当这个时间片结束时，强迫一个进程让出处理器，让它排列到就绪队列的尾部，等候下一轮调度
轮转策略可防止那些很少使用外围设备的进程过长的占用处理器而使得要使用外围设备的那些进程没有机会去启动外围设备
轮转策略与间隔时钟
多级反馈队列调度
又称反馈循环队列或多队列策略。主要思想是将就绪进程分为两级或多级，系统相应建立两个或多个就绪进程队列，较高优先级的队列一般分配给较短的时间片。
处理器调度先从高级就绪进程队列中选取可占有处理器的进程，只有在选不到时，才从较低级的就绪进程队列中选取。
彩票调度算法
基本思想：为进程发放针对各种资源（如CPU时间）的彩票。调度程序随机选择一张彩票，持有该彩票的进程获得系统资源。
进程都是平等的，有相同的运行机会。如果某些进程需要更多的机会，可被给予更多彩票，增加其中奖机会。
实时调度算法
实时系统是那些时间因素非常关键的系统。
实时系统包括监控系统、自动驾驶系统、安全控制系统等，这些系统中，迟到的响应即使正确，也和没有响应一样糟糕。
实时系统通常分为硬实时系统和软实时系统。
前者意味着存在必须满足的时间限制；后者意味着偶尔超过时间限制时可以容忍的。
Linux调度算法
1 进程调度策略
1) policy：
SCHED_OTHER普通类任务
SCHED_FIFO先进先出实时类任务
SCHED_RR轮转法实时类任务
2) priority进程静态优先级
3) nice进程可控优先级因子
4) rt_priority实时进程静态优先级
5) counter进程目前时间片配额，也称进程动态优先级
2 动态优先级的产生和变化
当counter递减到0时，运行进程被迫出让CPU；当可运行队列中所有进程的counter值变为0后，表明一轮调度已经结束。
等待态进程的动态优先级通常会逐渐增加，当所有可运行进程的counter都为0时，系统重新计算所有进程的counter，计算公式为：
p->counter=(p->counter>>1)+NICE_TO_TICKS(P->nice)
对于就绪态进程来说，因其counter都为0，计算结果就是nice转换过来的时钟滴答数；对于等待态进程就不一样，它们的counter都不为0，计算结束后，等待态进程的动态优先级会大于nice值。
进程的顺序性
一个进程在顺序处理器上的执行是严格按序的，一个进程只有当一个操作结束后，才能开始后继操作
顺序程序设计是把一个程序设计成一个顺序执行的程序模块，顺序的含义不但指一个程序模块内部，也指两个程序模块之间。
顺序程序设计特点:
程序执行的顺序性
程序环境的封闭性
程序执行结果的确定性
计算过程的可再现性
进程的并发性
进程执行的并发性：一组进程的执行在时间上是重叠的。
从宏观上看，并发性反映一个时间段中几个进程都在同一处理器上，处于运行还未运行结束状态。
从微观上看，任一时刻仅有一个进程在处理器上运行。
并发的实质是一个处理器在几个进程之间的多路复用，并发是对有限的物理资源强制行使多用户共享，消除计算机部件之间的互等现象，以提高系统资源利用率。
并发程序设计的优点
•对于单处理器系统,可让处理器和各I/O设备同时工作,发挥硬部件的并行能力。
•对于多处理器系统,可让各进程在不同处理器上物理地并行，加快计算速度。
•简化了程序设计任务。
采用并发程序设计的目的：
充分发挥硬件的并行性，提高系统效率。硬件能并行工作仅有了提高效率的可能性，硬部件并行性的实现需要软件技术去利用和发挥，这种软件技术就是并发程序设计。
并发程序设计是多道程序设计的基础，多道程序的实质就是把并发程序设计引入到系统中
与时间有关的错误
结果不唯一
永远等待
进程的交往：竞争与协作
第一种是竞争关系
系统中的多个进程之间彼此无关
系统中的多个进程之间彼此相关
资源竞争的两个控制问题：
一个是死锁(Deadlock)问题，
一个是饥饿(Starvation) 问题，既要解决饥饿问题，又要解决死锁问题。
第二种是协作关系
某些进程为完成同一任务需要分工协作。
进程同步指为完成共同任务的并发进程基于某个条件来协调它们的活动，因为需要在某些位置上排定执行的先后次序而等待、传递信号或消息所产生的协作制约关系。
进程互斥(Mutual Exclusion)
进程互斥是指若干个进程因相互争夺独占型资源时所产生的竞争制约关系。
进程同步
指两个以上进程基于某个条件来协调它们的活动。一个进程的执行依赖于协作进程的消息或信号，当一个进程没有得到来自于协作进程的消息或信号时需等待，直到消息或信号到达才被唤醒。
进程互斥关系是一种特殊的进程同步关系，即逐次使用互斥共享资源，是对进程使用资源次序上的一种协调。
互斥与临界区
并发进程中与共享变量有关的程序段叫“临界区”，共享变量代表的资源叫“临界资源”。
与同一变量有关的临界区分散在各进程的程序段中，而各进程的执行速度不可预知。
如果保证进程在临界区执行时，不让另一个进程进入临界区，即各进程对共享变量的访问是互斥的，就不会造成与时间有关的错误。
一次至多一个进程能够进入临界区内执行；
如果已有进程在临界区，其他试图进入的进程应等待；
进入临界区内的进程应在有限时间内退出，以便让等待进程中的一个进入。
临界区调度原则：
互斥使用、有空让进，忙则等待、有限等待，择一而入，算法可行

名词解释

解释并发与并行，并说明两者关系。
若干个事件或活动在同一时刻发生称为并行；若干个事件或活动在同一时间间隔内发生称为并发。
关系：并行是并发的特例，并发是并行的扩展。
解释模式切换与进程切换，并说明两者关系。
模式切换：进程运行中，当执行系统调用或发生中断时，CPU 模式从用户态切换到内核态，
去执行操作系统例程的过程，或者在完成系统处理后，通过逆向 CPU 状态切换来继续执行
被中断进程的过程。进程切换：是将 CPU 的使用权从一个进程转给另一个进程。(1)
关系：模式切换不一定产生进程切换，但进程切换必定有模式切换伴随。
解释硬中断和软中断，并说明两者关系。
通过硬件设施来产生中断请求，称作硬中断。
利用硬件中断的概念，用软件方式进行模拟，实现宏观上的异步执行效果的中断称作软中断。
关系：两者在中断请求、中断屏蔽、中断触发、中断服务等概念与设施方面十分相似。
解释“死锁”与“饥饿”，并说明两者关系。
如果在一个进程集合中的每个进程都在等待只能由该集合中的其他进程才能引发的事件，而无限期僵持的局面称死锁。
一个可运行进程由于其他进程总是优先于它，而被无限期拖延而不能被执行的现象称饥饿。
死锁进程必然处于饥饿状态，但处于饥饿状态的进程未必陷入死锁。
列出操作系统中常用的安全机制(中文及其英文名)。
认证机制(authentication)
授权机制(authorization)
加密机制(encryption)
审计机制(audit 或 auditing)
解释自主访问控制机制与强制访问控制。
前者指资源属主可按照自已意愿指定系统中的其他用户对其资源的访问权限的访问控制机制。
后者指将系统中的信息分密级和范畴进行管理，保证用户只能够访问那些被标明能够由他访问的信息的访问控制机制。

解答题

试述操作系统中最基础的三个抽象，并回答为什么要引入它们?
进程是对处理器的抽象、虚存是对主存的抽象、文件是对设备的抽象。
于是可面向进程而不是处理器、面向虚存而不是主存、面向文件而不是设备，方便了系统对
资源的管理、控制和调度。
试从进程管理、进程通信、中断处理、文件管理、存储管理、设备管理的角度考虑，
列出进程控制块中应包含的主要项目。
从进程管理角度应有：进程标识、进程状态、进程优先级、队列指针等。
从进程通信角度应有：消息队列首指针、访问消息队列互斥信号量、消息计数等。
从中断处理角度应有：现埸信息(上下文)、中断源及类型等。
从文件管理角度应有：保存进程使用文件的 FCB 等。
从存储管理角度应有：保存进程使用的程序和数据的内外存地址或页表位置等。
从设备管理角度应有：保存进程分配到的资源及所需资源情况等。
叙述 LRU、 NRU 和 LFU 三种页面置换算法的基本思想，并各给出一种可能的实现方案。
LRU 选择最近最久未使用过的页面予以淘汰。实现方案：为页面设置访问字段，记录该
页面自上次被访问以来所经历的时间 T，需要淘汰一个页面时，总是选择现有页面面中 T 值
最大的页面淘汰。
NRU 选择在最近一个时期内未被访问过的页面予以淘汰。实现方案：为页面设置访问位，
当某页被访问时其访问位置 1，系统周期性地对所有访问位清 0。需要淘汰页面时，总是从
访问位为 0 的页面中选择一个予以淘汰。
LFU 选择在最近时期使用最少的页面予以淘汰。实现方案：为页面设置访问计数器，页
面被访问时其访问计数器加 1。需要淘汰页面时，总是淘汰计数器值最小的页面，同时，所
有计数器清 0。
简述操作系统虚化技术在设备管理中的应用。
在设备管理中，通过用—类物理设备来模拟另一类物理设备，即通过共享设备磁盘来模拟独
占设备，把一个物理实体变成若干逻辑上的对应物。例如借助 SPOOLing 技术，把独占设备
(纸带、打印机等)虚化出许许多多台逻辑设备供用户使用。
简述逻辑文件和物理文件，及其分类。
逻辑文件是从用户观点出发，考虑信息的组织及配置方式，它分为流式文件和记录式文件。
物理文件是从系统观点出发，考虑文件在物理介质上的组织和存放方式，它分串连文件、连
续文件、索引文件和哈希文件。
I/0 软件分四个层次，试说明以下各个工作是在哪一层完成的？（3 分）
（1）向设备寄存器发写命令。
（2）设备缓冲区管理。
（3）逻辑地址转换为物理地址。
（4）唤醒请求 I/O 的进程。
（5）检查设备状态寄存器内容。
（6）将二进制整数转化成 ASCII 码以便打印。
(1)和(4)在设备驱动程序。
(2)和(3)在操作系统 I/O 软件。
(5)在 I/O 中断处理程序。
(6)在用户层 I/O 软件。
试说明多级反馈队列调度算法的基本思想，为什么说这是一种较好的进程调度算法?
本算法能全面满足不同类型作业的需求，较好实现公平性与资源利用率之间的平衡。
对分时交互型短作业，系统通常可在第一队列(最高优先级队列)规定的时间片内完成工作，
使终端型用户感到满意；
对短批处理作业，通常，只需在第一和第二队列中各执行一个时间片就能完成工作，周转时
间仍然很短；
对长批处理作业，它将依次在第一、第二、第三等各个队列中获得时间片运行，不必担心长
时间得不到处理。因而这是一种较好的进程调度算法。