华南理工大学操作系统期末考试卷考点整理
第一章
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 处理时间
则满足下面条件时,系统时可调度的
11m i i i C P =≤∑
10.调度机制和调度策略
1) 调度机制和调度策略分离
2) 实现机制在核:算法参数化
3) 用户进程设置策略:用户设置参数
8.批处理系统中的调度:三级调度
接纳调度 决定哪一个作业被接纳到系统中。
存调度 决定哪一个进程应该装入存,哪一个应当放在磁盘。
它也决定同时有多少个进程在存中,这称之为多道程序度。
CPU 调度 实际选择存中合适的进程运行。
第三章
1. CPU 利用率 = 1 - p n
这里,存中有n 个进程,每个进程花费比例p 的时间等待I/O.
CPU 利用率是n 的函数,称之为多道程序的度
2. 多道程序引入了两个问题 – 重定位和保护.
重定位 – 不能确定程序装在存的什么地方
代码不应当指定变量的绝对地址
必须保证程序不会访问其他进程的分区
保护 – 使用基址和界限值
相对地址加上基址映射为物理地址
相对地址大于界限值则产生错误
3. 存限制的两种解决方案: 动态存管理
(设计思想:为进程动态分配存,将进程动态调入存
分类:基于交换技术:将进程完整的调入存,运行一段时间后,调出存。
基于虚拟存储器:进程只需要比程序空间小的存就可以正常运行。分页和分段)
交换把一个进程在需要时装入存,不需要时写入磁盘
虚拟存 允许程序甚至在只有一部分在存时就可运行。
交换可能会在存中制造出多个空闲区, 存紧缩技术通过移动一些进程,把多个空闲区合并为一个。
4. 两种记录存使用情况的方式:位示图和链表。
位示图的问题是找到连续的0位是一个较慢的操作。
5. 问题: 程序太大不能全部装入存
解决方法:
程序员把程序分为多片,称之为覆盖 – 工作量太大
虚拟存 – OS 只保留程序的一部分放在存
分页是实现虚拟存的一种技术.
虚地址是程序产生的地址.
MMU (存管理单元) 把虚地址转换为物理地址.
6. 命中率= a
有效访问时间 (EAT)
EAT = α (t + ε) + (1 – α) (2t + ε)
= α t + α ε + 2t + ε - 2αt - α ε
= (2 – α) t + ε
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) 工作集页面置换算法:? ≡ w (k, t) ≡ 在t 时刻,工作集窗口包含有k 个页面的访问
检查R 位,1置0,0&t>e ,淘汰,0&t<=e ,记下最后时间,若无1多0弃最久
9) 工作集时钟(WSClock )页面置换算法:工作集变成环形
8. 由于页表和部碎片造成的开销
s = 平均进程大小(字节)
p = 页面大小 (字节)
e = 页表项大小
2s e p overhead p ?=+(+部碎片) 9. 实现方面的问题与分页有关的操作系统
与调页有关的事件
1.进程创建
-确定程序的大小
-创建页表
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软件系统的层次及功能