北方工业大学《操作系统》课程考试计算(简答)题复习材料

《操作系统》课程考试计算（简答）题复习材料2015-2016学年版本（根据宋丽华老师讲义整理）北方工业大学计算机学院2015年12月30日北方工业大学《操作系统》课程考试计算题复习材料目录一、同步与互斥问题................................................................................................................................13.6.4生产者—消费者问题............................................................................................................1二、作业调度..............................................................................................................................................2★作业调度算法—FCFS（Firstcomefirstserve）................................................................2★短作业优先算法—SJF（shortestjobfirst）......................................................................2★最高响应比优先—HRN（highestresponse-rationext）..............................................2三地址映射..............................................................................................................................................35.4.1页式管理的基本原理............................................................................................................3四、页面置换..............................................................................................................................................45.4.4请求页式管理的置换算法..................................................................................................4★先进先出算法(FIFO-FirstInputFirstOutput）,.......................................................4★最优淘汰算法（OPT-Optimalreplacementalgorithm）：...................................4五死锁避免..............................................................................................................................................5银行家算法实例................................................................................................................................5验证T0时刻的安全性...........................................................................................................5P2请求资源{1，0，1}............................................................................................................6验证P2分配资源后的安全性.............................................................................................6P1请求资源{1，0，1}............................................................................................................6P3请求资源{0，0，1}............................................................................................................6P3分配资源后的安全性........................................................................................................7P2请求资源{1，0，1}............................................................................................................7六磁盘调度算法.....................................................................................................................................75.6.2磁盘调度...................................................................................................................................8★先来先服务FCFS(FirstComeFirstServed).................................................................8★最短寻道时间优先SSTF(ShortestSeekTimeFirst)..................................................8★扫描(SCAN)算法(又称电梯算法)....................................................................................8★循环扫描(CSCAN)算法（也称单向扫描算法）........................................................9（适用于：计算机科学与技术专业、信息安全专业、数字媒体专业）北方工业大学《操作系统》课程考试计算题复习材料1/9一、同步与互斥问题分析题意，确定同步、互斥或同步与互斥问题。设信号量，给出信号量表示的含义（公用，私用）和初始值。描述算法，注意死锁问题。3.6.4生产者—消费者问题把一个长度为n的有界缓冲区(n＞0)与一群生产者进程P1，P2，…，Pm和一群消费者进程C1，C2，…，Ck联系起来设生产者进程和消费者进程是互相等效的，其中，各生产者进程使用的过程deposit(data)和各消费者使用的过程remove(data)可描述如下：1.首先生产者—消费者问题是一个同步问题。即生产者和消费者之间满足如下条件：1)消费者想接收数据时，有界缓冲区中至少有一个单元是满的2)生产者想发送数据时，有界缓冲区中至少有一个单元是空的2.由于有界缓冲区是临界资源，因此，各生产者进程和各消费者进程之间必须互斥执行。★公用信号量mutex，保证生产者进程和消费者进程之间的互斥，表示可用有界缓冲区的个数，初值为1；★信号量avail为生产者进程的私用信号量，表示有界缓冲区中的空单元个数，初值为n；★信号量full为消费者进程的私用信号量，表示有界缓冲区中非空单元个数，初值为0。从而有：deposit(data)：beginP(avail)P(mutex)送数据入缓冲区某单元V(full)V(mutex)Endremove(data)：beginP(full)P(mutex)取缓冲区中某单元数据V(avail)V(mutex)end北方工业大学《操作系统》课程考试计算题复习材料2/9二、作业调度画表格计算周转时间和带权周转时间给出作业（进程）调度序列计算平均周转时间和平均带权周转时间★作业调度算法—FCFS（Firstcomefirstserve）思想：按作业和就绪进程来到的次序进行调度。这种算法优先考虑在系统中等待时间最长的作业，而不管它要求运行时间的长短。优点：算法简单，公平，容易实现缺点：对于短作业或短进程，等待时间长下面是4个作业在系统中从提交、运行的信息。平均周转时间：T=1.725平均带权周转时间W=6.875★短作业优先算法—SJF（shortestjobfirst）思想：比较作业缓冲区中的作业预计的运行时间，选择预计时间最短的作业进入运行状态。优点：算法简单，可得到最大系统吞吐率，效率高。缺点：主要问题是对长作业不利，如果系统不断地接收短作业，就会使长作业长时间等待。平均周转时间：T=1.55平均带权周转时间W=5.15★最高响应比优先—HRN（highestresponse-rationext）响应比=响应时间/预计执行时间----响应时间=等待时间+预计执行时间----所以响应比为：1+作业等待时间/预计执行时间思想：当需要从就绪队列中选择进程投入运行时，先计算每个进程的响应比，选北方工业大学《操作系统》课程考试计算题复习材料3/9择响应比最高的进程运行优点：短作业响应比高，执行时间短；长作业响应比随着等待时间增加而提高，不会过长等待。既照顾了短作业、也考虑到了长作业。缺点：每次调度前计算响应比增加了系统开销。平均周转时间：T=1.625W=5.675三、地址映射根据公式计算逻辑地址的页号和页内地址p=int[A/L]d=[A]modL根据页表查找页面号。页面号乘以页长，加上位移量（d）计算逻辑地址多次计算直到找到数据、指令为止。5.4.1页式管理的基本原理★逻辑空间上的地址为：页号+页内地址，页内的地址空间是连续的，页之间不必连续。★如果给定的逻辑地址是A，页面大小是L，则页号p和页内地址d可以按以下公式求得：p=int[A/L]d=[A]modL例：逻辑地址100页面大小1k★地址变换：根据逻辑空间的页号，查找页表对应项找到对应的物理页面号，页面号乘以页长，加上位移量（页内地址）就是物理地址。每个作业的逻辑地址是连续的，重定位到内存空间后就不一定连续了。变换过程全部由硬件地址变换机构自动完成。北方工业大学《操作系统》课程考试计算题复习材料4/9四、页面置换根据引用页面序列画出页面置