操作系统复习
十道大题
信号量机制
必考互斥和前驱图
进程状态和基本概念（比如什么是并发）
并发是指宏观上在一段时间内能同时运行多个程序，而并行则指同一时刻能运行多个指令。 并行需要硬件支持，如多流水线、多核处理器或者分布式计算系统。
进程：程序的一次执行过程；一个具有一定独立功能的程序在一个数据集合上的一次动态执行过程。是系统进行资源分配和调度的一个独立单位。
周转时间 = 作业完成时刻 - 作业到达时刻；
带权周转时间 = 周转时间 / 实际运行时间；
调度算法
先来先服务 FCFS
FCFS调度算法是一种最简单的调度算法。 既可用于作业调度，也可用于进程调度。
从就绪队列中选择最早进入队列的。非抢占式。
FCFS算法比较有利于长作业（进程），不利于短作业（进程）。 有利于CPU繁忙型作业（进程），不利于I/O繁忙型作业（进程）。因为没有抢占机制只能阻塞等待。
短作业优先 SJF / SPF
从就绪队列中选择一个估计运行时间最短的作业，将处理机分配给它，使它立即执行并一直到完成，或发生某事件而被阻塞放弃处理机时，再重新调度。(非抢占式)
优点：
当多个作业同时到达时，SJF算法可使平均周转时间最短。
缺点：
该算法对长作业不利——长作业可能长期不被调度，甚至“饿死”。解决：高响应比优先算法。
未考虑作业的紧迫性，不能保证紧迫作业（进程）会被及时调度。
由于作业（进程）的长短只是根据用户所提供的估计时间而定的，致使该算法不一定能真正做到短作业优先调度。
高优先权优先
非抢占式
系统一旦把处理机分配给就绪队列中优先权最高的进程后，该进程便一直执行下去，直到完成，或因发生某事件使该进程放弃处理机时，系统方可再将处理机重新分配给另一个优先权最高的进程。
抢占式
系统把处理机分配给就绪队列中优先权最高的进程，使之执行，但在其执行期间，只要出现了另一个优先权更高的进程，系统就立即停止当前进程的执行，重新将处理机分配给新的优先权最高的进程。
特点
能更好地满足紧迫作业的要求。常用于实时系统中，以及对实时性能要求较高的批处理系统和分时系统中。
降低进程优先级的合理时机是：进程的时间片用完
时间片轮转
系统把就绪队列中的所有进程，按先来先服务的原则，排成一个队列；
每次调度时，把CPU分配给队首进程，并让它执行一个时间片；
每当执行的时间片用完，调度程序便停止该进程的执行，将其送入就绪队列尾部；然后进行下一次进程调度。
时间片的大小：几ms～几百ms。太大：退化为FCFS；太小：系统开销过大
分页地址结构
31 12 11 0
-------------------
| 页号P | 位移d |
-------------------页号 = 逻辑地址 / 页大小 （向下取整）
页内偏移 = 逻辑地址 mod 页大小
分段地址结构
地址结构：(段号, 段内地址)
段表：段号 --> (段长, 基址)
地址变换：用段号找到基址，加上段内地址。
页面置换算法 (2)
目标：页面更换频率尽可能小
最佳置换算法 OPT
一种理论上的算法。选择以后永不使用的或者是未来最长时间内不再使用的页面淘汰。
先进先出 FIFO
选择在内存中驻留时间最长的页面淘汰。
该算法实现简单，只需把调入内存的页面根据先后次序链接成队列，设置一个指针总指向最早的页面。
最近最久未使用 LRU
选择最近最久未使用的页面进行淘汰。——用“最近的过去”作为“最近的将来”的近似。
该算法为每个页面设置一个访问字段，来记录页面自上次被访问以来所经历的时间，淘汰页面时选择现有页面中值最大的予以淘汰。
用寄存器实现：每个页面配个移位寄存器，访问时把最高位置1。每隔100ms将寄存器右移一位。则最小的寄存器就是最近最久未使用的。
用栈来实现：每当进程访问某页面时，把该页面的页面号从栈中移出，再压入栈顶。因此栈底总是最近最久未使用的页面号。
性能接近于OPT，但是实现起来比较困难，且开销大；
时钟 CLOCK
简单的 CLOCK 算法是给每一页面关联一个附加位，称为访问位(Access bit)。
访问位被置1：
首次装入主存
被访问
在内存中的页面链接成一个循环队列，有一个指针指向最老的页面。
当发生页面失效时，首先检查指针所指的页面，若它的访问位是0就置换该页，并把指针前移一位；若访问位是1，就把访问位置0，并把指针前移一位，重复检查访问位。
由于该算法循环地检查各页面的情况，故称为 CLOCK 算法，又称为最近未用(Not Recently Used, NRU)算法。
改进型Clock
淘汰被修改过的页面时，需将其写回磁盘(置换代价高)，因此应淘汰既未被访问又未被修改的页面。为此，每个页面除了有访问位A外，还增加一个修改位M。由访问位A与修改位M可以组成下面4种类型的页面，从最应该淘汰到最不应该淘汰排列：
1类(A=0,M=0)，是最佳淘汰页；
2类(A=0,M=1)，该页最近未被访问，但已被修改，并不是很好的淘汰页
3类(A=1,M=0) ，最近已被访问， 但未被修改，该页有可能再被访问
4类(A=1,M=1) ，最近被访问且被修改过的页，最不应该淘汰。
(1)从指针当前位置开始，扫描循环队列，寻找A=0且M=0的第1类页面，将所遇到的第一个页面淘汰。
(2)若第1步查找一周后未遇到第1类页面，则寻找A=0且M=1的第2类页面，将所遇到的第一个页面淘汰。第2轮扫描中将所有扫描过的页面的访问位A清0。
(3)若第2轮扫描失败，则返回(1)，若仍失败，再重复第(2)步，此时就一定能找到被淘汰的页。
第六章 输入输出系统 (4)
I/O系统的4个层次：
趋势：减少CPU对I/O操作的干预程度，提高并行度。
程序I/O方式
查询方式：CPU轮询I/O状态，大部分时间在忙等。资源浪费大。CPU完全控制I/O。
中断I/O方式
CPU初始化I/O并启动I/O操作，然后去执行其他程序。当I/O完成时，CPU将被中断。CPU从I/O运数据到内存。
DMA方式
由DMA控制器直接控制总线传递数据块。DMA控制器从I/O运数据到内存。
磁盘调度
目的：使平均寻道时间最少。寻道时间：把磁臂(磁头)移动到指定磁道上所经历的时间。
先来先服务 FCFS
严格按照给定序列依次访问。简单、公平。
最短寻道时间优先 SSTF
优先选择从当前磁头位置所需寻道时间最短的请求。可能存在某些请求的饥饿，因为本次例子我们是静态的序列，看不出问题，假设是一个动态的请求，如果后续来的请求都是小于 183 磁道的，那么 183 磁道可能永远不会被响应，于是就产生了饥饿现象，这里产生饥饿的原因是磁头在一小块区域来回移动。
扫描 SCAN
要求磁头臂仅仅沿一个方向移动，并在途中满足所有未完成的请求，直到它到达这个方向上的最后一个磁道，或者在这个方向上没有别的请求为止。然后倒转服务方向，沿相反方向扫描，同样按顺序完成所有请求。
由于这种算法中，磁头移动的规律颇似电梯的运行，因而又常被称为电梯调度算法。
获得了较好性能，又能防止“饥饿”现象。被广泛应用于大、中、小计算机系统和网络中的磁盘调度
循环扫描 CSCAN
SCAN算法存在这样的问题：当磁头刚从里向外移动而越过某个磁道时，恰好有一个进程请求访问此磁道，这时，该进程必须等待，待磁头继续从里向外，然后再从外向里扫描完所有要访问的磁道后，才处理该进程的请求，致使该进程的请求被大大地延迟。
为了减少这种延迟，CSCAN算法规定磁头单向扫描，例如只是从里向外扫描，当磁头移动到最外磁道并访问后，立即快速移动到最里的欲访问的磁道，亦即将最大磁道号紧接着最小磁道号。
NStepSCAN （重要）
在最短寻道时间优先（SSTF）、扫描算法（SCAN）和循环扫描算法（CSCAN）中，都可能出现磁臂停留在某处不动的情况，例如，有一个或几个进程对某一磁道有较高的访问频率，这些进程反复请求对某一磁道的I/O操作，从而垄断了整个磁盘设备。我们把这现象称为“磁臂粘着”，在高密度磁盘上容易出现这种情况。
N步SCAN算法是将磁盘请求队列分成若干个长度为N的子队列，磁盘调度将按FCFS算法依次处理这些子队列。而每处理一个队列时又是按SCAN算法，对一个队列处理完后，再处理其他队列。当正在处理某子队列时，若又出现新的磁盘I/O请求，将新请求进程放入其他队列，这样就可避免出现粘着现象。
N=1时相当于先来先服务 FCFS 算法，N非常大的时候相当于 SCAN 算法。
FSCAN
FSCAN算法实质上是N步SCAN算法的简化，即FSCAN只将磁盘请求队列分成两个子队列。一个是由当前所有请求磁盘I/O的进程形成的队列，由磁盘调度按SCAN算法进行处理。在扫描期间，将新出现的所有请求磁盘I/O的进程，放入另一个等待处理的请求队列。这样，所有的新请求都将被推迟到下一次扫描时处理。
评论
发表评论