华南理工大学操作系统期末考试卷考点整理.docx
《华南理工大学操作系统期末考试卷考点整理.docx》由会员分享,可在线阅读,更多相关《华南理工大学操作系统期末考试卷考点整理.docx(12页珍藏版)》请在冰点文库上搜索。
华南理工大学操作系统期末考试卷考点整理
第一章1.操作系统扩展的机器资源管理操作系统是由程序模块组成的系统软件,它能够以尽量有效、合理的方式管理计算机底层硬件资源、规划计算机工作流程、控制程序的执行、提供各种服务功能,为用户提供计算机抽象接口,使得用户能够方便、灵活的使用计算机,计算机系统得以高效运行。
2.操作系统的特征并发共享虚拟异步性3.操作系统的功能处理机管理存储管理设备管理信息管理用户接口4.操作系统的设计原则可维护性:
改错性维护、适应性维护、完善性维护。
可靠性:
正确性、稳健性。
可理解性:
易于理解,以方便测试、维护和交流。
性能:
有效地使用系统资源,尽可能快地响应用户请求。
5.操作系统结构1)单体系统:
主过程,服务过程,实用过程
• 特点:
模块由众多服务过程(模块接口)组成,可以随意调用其他模块中的服务过程。
• 优点:
具有一定灵活性,在运行中的高效率。
• 缺点:
功能划分和模块接口难保正确和合理,模块之间的依赖关系(功能调用关系)
复杂,降低了模块之间的相对独立性,不利于修改。
2)层次式系统:
(5)操作员(4)用户程序(3)I/O管理
(2)操作员‐IPC
(1)存储器和磁鼓管理(0)处理器的分配和多道程序设计
· 优点:
功能明确,调用关系清晰(高层对低层单向依赖,调用有序性),有利于保证设计和实现的正确性;低层和高层可分别实现(便于扩充);高层错误不会影响到低层;
避免递归调用。
· 缺点:
降低了运行效率。
3)客户/服务器模型:
把操作系统分成若干分别完成一组特定功能的服务进程,等待客户提出请求;而系统内核只实现操作系统的基本功能(如:
虚拟存储、消息传递)。
优点:
• 良好的扩充性:
只需添加支持新功能的服务进程即可。
• 可靠性好:
调用关系明确,执行转移不易混乱。
• 便于网络服务,实现分布式处理:
以同样的调用形式,在下层可通过核心中的网络传送到远方服务器上。
缺点:
• 消息传递比直接调用效率要低一些 (但可以通过提高硬件性能来补偿 )。
4)微内核(micro‐kernel):
将更多操作系统功能放在核心之外,作为独立的服务进程运行。
第二章进程的特征
• 动态性:
进程具有动态的地址空间(数量和内容),地址空间上包括:
– 代码(指令执行和CPU状态的改变)
– 数据(变量的生成和赋值)
– 系统控制信息(进程控制块的生成和删除)
• 独立性:
各进程的地址空间相互独立,除非采用进程间通信手段;
• 并发性、异步性:
"虚拟"
• 结构化:
代码段、数据段和核心段(在地址空间中);程序文件中通常也划分了代码段和数据段,而核心段通常就是OS核心(由各个进程共享,包括各进程的PCB)
进程与程序的区别
• 进程是动态的,程序是静态的:
程序是有序代码的集合;进程是程序的执行。
通常进程不可在计算机之间迁移;而程序通常对应着文件、静态和可以复制。
• 进程是暂时的,程序的永久的:
进程是一个状态变化的过程,程序可长久保存。
• 进程与程序的组成不同:
进程的组成包括程序、数据和进程控制块(即进程状态信息)。
• 进程与程序的对应关系:
通过多次执行,一个程序可对应多个进程;通过调用关系,一个进程可包括多个程序。
PCB:
进程控制块引入线程的目的是简化线程间的通信,以小的开销来提高进程内的并发程度。
• 线程的优点:
减小并发执行的时间和空间开销(线程的创建、退出和调度),因此容许在系统中建立更多的线程来提高并发程度。
– 线程的创建时间比进程短;
– 线程的终止时间比进程短;
– 同进程内的线程切换时间比进程短;
– 由于同进程内线程间共享内存和文件资源,可直接进行不通过内核的通信进程和线程的比较
• 地址空间和其他资源(如打开文件):
进程间相互独立,同一进程的各线程间共享-
-某进程内的线程在其他进程不可见
• 通信:
进程间通信IPC,线程间可以直接读写进程数据段(如全局变量)来进行通信
--需要进程同步和互斥手段的辅助,以保证数据的一致性
• 调度:
线程上下文切换比进程上下文切换要快得多;
进程间的关系
• 完全无关(异步):
不同进程间无任何关联
• 使用共享数据(互斥):
有效保护各个进程的正确运行
• 存在先后顺序(同步):
保证进程运行顺序的正确1.导致进程创建的事件1) 系统初始化2) 执行进程创建系统调用3) 用户请求创建一个新进程4) 初始化一个批处理作业2.中断发生后操作系统最底层的工作步骤1) 硬件压入堆栈程序计数器等。
2) 硬件从中断向量装入新的程序计数器。
3) 汇编语言过程保存寄存器值4) 汇编语言过程设置新的堆栈5) C中断服务例程运行(典型地读和缓冲输入)
6) 调度程序决定下一个将运行的进程。
7) C过程返回至汇编代码。
8) 汇编语言过程开始运行新的当前进程3.避免竞争条件的关键是不允许多于一个进程同时读写共享数据。
竞争条件:
两个或多个进程读写某些共享数据,而最后的结果取决于进程运行的精确时序,称为竞争条件。
临界区:
对共享内存进行访问的程序片段称作临界区4.避免竞争条件解决方案的四个条件1) 互斥原则:
不允许两个进程同时在临界区2) 通用原则:
对处理的速度和cpu的数量不应当有任何假设3) 有效性原则:
运行于临界区外的进程不能阻塞其他进程4) 合理性原则:
进程不应当无休止地等待临界区,无法进入应放弃CPU资源4.互斥解决1) 屏蔽中断:
则上下文切换不会发生。
因此,允许用户禁止中断是不明智的。
但是,但有时禁止中断是很方便的 (甚至是必需的)(写、读之间可能会有)
2) 锁变量:
设共享(锁)变量,当要进入,测得锁为0方可,并设置为1,否则等到变为0。
(当退出没有置为0,会出现违背原则1)
3) 严格轮换法:
进程分别为0或者1,turn的值也为0或1,相同时进入(违背了条件3。
因为进程必须严格按顺序进入临界区)
4) Peterson解法:
要进入置为自己的turn,同则进入,不同等待。
(满足4个)
5) TSL指令:
使用TSL指令,进入置1,不允许其他,直到退出置0。
5.IPC机制三种模型
• 忙等待模型(只解决互斥问题)
– 进程进入临界区时进行严格的检查
• 睡眠和唤醒模型(互斥与同步)
– 通过改变进程的状态来实现互斥和同步
• 消息传递模型(复杂的IPC机制)
– 以公共的通信机制来控制进程状态变化,实现同步和互斥5.调度算法的评价标准1) 公平性 ‐ 每一个进程得到公平的调度时间。
2) 有效性– 保证CPU忙碌且在执行有效的工作。
3) 响应时间– 对交互式用户最小化其响应时间。
4) 运行时间– 对批处理作业,最小化其运行时间。
5) 吞吐量– 对批处理作业,最大化每小时完成的作业数。
6.调度算法的目标1) 所有系统
‐ 公平
‐ 策略强制执行
‐ 平衡2) 批处理系统
‐ 吞吐量
‐ 周转时间
‐ CPU利用率3) 交互式系统
‐ 响应时间
‐ 均衡性4) 实时系统
‐ 满足截止时间
‐ 可预测性7.批处理系统中的调度1) 先来先服务(FCFS)
2) 最短作业优先(SJR)
两种方案:
非抢占式– 一旦进程获得 CPU,它将不能被抢占,直到主动放弃CPU。
抢占式– 系统中的正在运行的进程永远是优先级最高的。
SJF 是最优的– 对所有进程,系统的平均等待时间最小。
3) 最短剩余时间优先8.交互式系统的调度1) 轮转调度(RR)
2) 优先级调度3) 多级队列调度每一个就绪队列赋予一个不同的优先级类就绪队列分为多个队列:
前台 (交互式作业)
后台 (批处理作业)
每一个队列有自己的调度算法,
前台– RR
后台– FCFS
4) 最短进程优先(老化算法)
a = 估计是采用的权重,当前估计值为:
T1 = a*T0 + (1‐a) *T1
这里T0是先前的估计值,T1是当前的运行时间。
5) 保证调度假定将 CPU的时间分为n份计算比率 = 实际占用CPU的时间/ 整个CPU时间执行比率最小的进程6) 彩票调度(随机)
7) 公平共享调度每个用户分配CPU的一部分,调度器以一种强制的方式选择进程。
9.实时系统中的调度1) 调度器必须保证在任务的死线之前执行完任务。
2) 硬实时和软实时3) 可调度的实时系统假定m 个周期事件事件 i 发生的周期是 Pi ,需要 Ci 处理时间则满足下面条件时,系统时可调度的10.调度机制和调度策略1) 调度机制和调度策略分离2) 实现机制在内核:
算法参数化3) 用户进程设置策略:
用户设置参数8.批处理系统中的调度:
三级调度接纳调度决定哪一个作业被接纳到系统中。
内存调度决定哪一个进程应该装入内存,哪一个应当放在磁盘。
它也决定同时有多少个进程在内存中,这称之为多道程序度。
CPU调度实际选择内存中合适的进程运行。
第三章1. CPU利用率 = 1 ‐ p n
这里,内存中有n个进程,每个进程花费比例p的时间等待I/O.
CPU利用率是n的函数,称之为多道程序的度2.多道程序引入了两个问题– 重定位和保护.
重定位– 不能确定程序装在内存的什么地方代码不应当指定变量的绝对地址必须保证程序不会访问其他进程的分区保护– 使用基址和界限值相对地址加上基址映射为物理地址相对地址大于界限值则产生错误3.内存限制的两种解决方案:
动态内存管理
(设计思想:
为进程动态分配内存,将进程动态调入内存分类:
基于交换技术:
将进程完整的调入内存,运行一段时间后,调出内存。
基于虚拟存储器:
进程只需要比程序空间小的内存就可以正常运行。
分页和分段)
1
1
m
i
i
i
C
P
=
£
å
交换把一个进程在需要时装入内存,不需要时写入磁盘虚拟内存允许程序甚至在只有一部分在内存时就可运行。
交换可能会在内存中制造出多个空闲区, 内存紧缩技术通过移动一些进程,把多个空闲区合并为一个。
4.两种记录内存使用情况的方式:
位示图和链表。
位示图的问题是找到连续的0位是一个较慢的操作。
5.问题:
程序太大不能全部装入内存解决方法:
程序员把程序分为多片,称之为覆盖– 工作量太大虚拟内存– OS只保留程序的一部分放在内存分页是实现虚拟内存的一种技术.
虚地址是程序产生的地址.
MMU (内存管理单元) 把虚地址转换为物理地址.
6.命中率= a
有效访问时间 (EAT)
EAT = a (t + e) + (1 – a) (2t + e)
= a t + ae + 2t + e ‐ 2at ‐ ae
= (2 – a)t + e
7.页面置换算法1) 最优页面置换算法:
替换最远的将来不会用到的页面2) 最近未使用(NRU)页面置换算法:
淘汰一个没有被访问已修改,好过频繁访问未修改。
访问R修改M(有置1,周期置0)
3) FIFO页面置换算法4)
第二次机会页面置换算法:
检查最老,R=0淘汰,R=1置0放到最新,全查完无,用FIFO
5) 时钟页面置换算法:
第二次变环形6) 最近最少使用(LRU)页面置换算法:
访问+1,选最小,周期置0
N个页框:
k*k矩阵,访问k页框,k行置1,k列置0,选行值最小的页软件实现:
7) 最不经常使用(NFU):
修改NFU:
老化NFU‐每次时钟中断:
往右移,竖着在左边加入,结束时选行值最小8) 工作集页面置换算法:
Dº w (k, t) º在t时刻,工作集窗口包含有k个页面的访问检查R位,1置0,0&t>e,淘汰,0&t<=e,记下最后时间,若无1多0弃最久9) 工作集时钟(WSClock)页面置换算法:
工作集变成环形8.由于页表和内部碎片造成的开销
s = 平均进程大小(字节)
p = 页面大小(字节)
e = 页表项大小
(+内部碎片)当最佳:
9.实现方面的问题与分页有关的操作系统与调页有关的事件1.进程创建
- 确定程序的大小2
s e p
overhead
p
×
= +
2 p se =
- 创建页表2.进程执行
- MMU为新进程复位
- TLB刷新3.页故障时
- 确定虚地址是发生故障
- 换出不需要的页,换入需要的页。
4.进程结束时
- 释放页表,页10.缺页中断处理1) 硬件陷入内核2) 保存通用寄存器3) OS 确定需要哪一个虚页4) OS 检查地址的有效性,查找页帧5) 如果选择的页帧是脏的,写回到磁盘6) OS 装入新页7) 更新页表8) 被中断的指令重新开始执行9) 被打断的进程得到调度10) 恢复寄存器11) 程序继续11.内存管理系统可分为三个部分:
底层的MMU处理器页故障处理器(内核的一部分)
运行在用户空间的外部页面调度程序
第四章1.文件的实现1) 连续分配2) 链表分配3) 在内存中采用表的链表分配4) i节点2.改善文件系统性能1) 高速缓存2) 块提前读3) 减少磁盘臂振动影响文件系统安全性的主要因素系统漏洞——提高设计水平进行规避操作失误——建立防护机制进行保护恶意攻击——实施安全策略进行遏制文件系统的可靠性设计
• 坏块管理
– 硬件实现与软件实现:
坏块表和备份扇区
• 备份机制
– 交叉备份和增量存储
• 一致性检查
– 块一致性坚持和文件一致性检查
• 磁盘访问性能
• 高速缓存
第五章1.精确中断4个特性1) PC保存在一个已知的地方2) PC所指向的指令之前的所有指令已经完全执行3) PC所指向的指令之后的所有指令都没有执行4) PC所指向的指令的执行状态是已知的2.I/O管理的任务和目标
• 根据用户请求,控制各类I/O设备实现用户的目标
• 向用户提供方便的I/O设备接口,屏蔽底层硬件细节差别
• 利用各种技术,提高I/O设备的运行效率
• 实现对I/O设备的管理和保护2.I/O软件目标
• 设备独立性
– 程序可以访问任何I/O 设备
– 不必提前指定设备 (软盘, 硬盘或 CD‐ROM)
• 统一命名
– 以一个字符串或整数的形式命名一个文件或设备
– 不依赖于具体的机器
• 错误处理
– 处理尽可能接近硬件
• 同步与异步传输
– 块传输与中断驱动
• 缓冲
– 来自设备的数据并不直接存放到目的地
• 可共享的和独占的设备
– 磁盘是可共享的
– 磁带则不是3.实现I/O的三种方式1) 程序控制I/O
2) 中断驱动I/O
3) 使用DMA的I/O
4) I/O通道机制4.I/O软件系统的层次及功能用户级IO软件:
产生I/O请求;对I/O进行格式化;假脱机与设备无关的操作系统软件:
命名、保护、分块、缓冲、分配设备驱动程序:
设置设备寄存器;检查状态中断处理程序:
当I/O完成时唤醒驱动程序硬件:
执行I/O操作5.中断处理1) 保存没有被中断硬件保存的所有寄存器(包括PWS)
2) 为中断服务过程设置上下文,可能包括设置TL
B.MMU和页表3) 为中断服务过程设置栈4) 应答中断控制器, 允许中断5) 复制寄存器6) 执行服务过程7) 选择下一次运行的进程8) 为下一个要执行的进程设置MMU 上下文9) 装入新进程的寄存器10) 开始运行新进程6.与设备无关的I/O软件1) 设备驱动程序的统一接口2) 缓冲3) 错误报告4) 分配和释放专用设备5) 提供与设备无关的块大小7.读或写一个磁盘块的时间由3因素决定寻道时间(主)
旋转延迟实际传输时间8.磁盘臂调度算法
FCFS
SSF(最短寻道优先)
电梯算法:
一个方向走完后换方向9.错误处理用备用扇区替换坏扇区移动所有扇区以回避坏扇区10.稳定存储器稳定写稳定读崩溃恢复
第六章1.资源分为:
可抢占的资源:
把进程的资源(例如内存)剥夺后不会导致严重错误不可抢占的资源:
把进程的资源(例如CD刻录机)剥夺后将导致严重错误2.使用资源时发生的事件请求资源使用资源释放资源3.死锁的四个必要条件1.互斥条件
• 每一个资源分配给一个进程或是可用的2.占有和等待条件
• 进程占有资源并请求其他资源3.不剥夺条件
• 先前得到的资源不可强制被剥夺4.环路条件
• 2 个以上的进程形成了一个链
• 每一个进程都在等待被链中的下一个进程占有的资源4.处理死锁的策略1) 忽略该问题2) 检测死锁并恢复3) 仔细对资源进行分配,动态地避免死锁4) 通过破坏引起死锁的四个必要条件之一,防止死锁的产生5.从死锁中恢复
• 抢占式恢复
– 抢占其他进程的资源
– 依赖于资源的属性
• 回滚式恢复
– 周期性地检查进程
– 使用保存的状态
– 如果发生死锁,则重启进程
• 杀死进程恢复
– 最粗糙但是最简单打破死锁的方法
– 杀死锁链中的一个进程
– 其它进程得到资源
– 选择可以重新执行的进程6.死锁防止1) 破坏互斥条件:
有些设备(比如打印机) 可被spooled(假脱机)
2) 破坏占有和等待条件:
在开始时就请求全部资源3) 破坏不可抢占条件:
这并不是一个可行的方案4) 破坏环路等待条件:
对所有资源进行编号,请求必须按照编号的顺序。
7.死锁的避免资源轨迹图安全状态和不安全状态:
银行家算法8.死锁的检测单个:
有向图是否有环路多个:
矩阵:
类似银行家