搜索
•总复习•2015-11•2013级软件3-4•考试时间与题型•考试时间：12.3，第14周周四上午10：10-12：00•考试题型：–选择题（20分），20个选择，每个选择1分–填空题（20分），20个空，每空1分–简答题（30分），6道题，每题5分，每章1题–综合题（30分），3道题，•第二章：用信号量解决进程同步、互斥问题•第三章：处理机调度/银行家算法•第四章/第五章：地址变换/页面置换算法–总分：100分（闭卷，考试允许带计算器，所有计算结果精确至小数点后2位）•考试范围•第一章操作系统引论•第二章进程的描述与控制•第三章处理机调度与死锁•第四章存储器管理•第五章虚拟存储器•第六章输入输出系统•第七章文件管理•第八章磁盘存储器的管理•第1章操作系统引论•操作系统的目标–有效性、方便性、可扩展性、开放性•操作系统的作用–用户观点、资源管理者、虚拟机•操作系统的发展过程–脱机/联机输入输出技术–多道程序设计技术，解决了哪二对矛盾–为什么引入分时系统–为什么引入实时系统•操作系统四大特征–并发、共享、虚拟、异步–并发与并行概念•五大功能–处理机管理、存储器管理、设备管理、文件管理、提供接口–接口类型：用户接口（CLI、GUI）、程序员接口（API/系统调用）•OS结构–微内核结构：所采用的技术，微内核中包括什么内容•第2章进程的描述与控制•程序并发执行时的特征（间断、失去封闭、不可再现）•并发与并行的概念•进程相关的概念–为什么要引入进程–进程由什么组成的（程序段+数据段+PCB）–为什么说PCB是进程存在的唯一标志–进程的三种基本状态，它们之间如何进行转换•进程的同步与互斥–临界资源、临界区的概念–忙等的概念–信号量：记录型信号量的含义、信号量集–应用信号量机制解决进程的同步与互斥问题（前趋图、生产者与消费者、哲学家进餐、读者-写者）•进程通信（4种高级通信）•管程–管程的组成（4部分）–线程–线程的特点•第3章处理机调度与死锁•调度层次–低级调度：进程调度–高级调度：作业调度–中级高度：内存调度•处理机调度算法–FCFS、SJF、高响应比优先调度、RR，要求知道每种算法的调度规则、调度方式与偏好性，会计算周转时间与带权周转时间•实时调度算法–实时系统调度能力–最低松弛度优先算法（调度规则、松弛度）•死锁的相关概念–死锁的定义与产生死锁的原因–产生死锁的4个必要条件•预防死锁的方法–静态资源分配法、资源剥夺法、有序资源分配法•避免死锁–银行家算法–并非所有不安全状态都是死锁状态，但只要系统处于安全状态便可避免死锁状态。–检测并解除死锁–检测死锁：资源分配图完全简化法–解除死锁：剥夺资源与撤消进程•第4~5章（虚拟）存储器管理•程序的装入与链接–装入：绝对、可重定位、动态运行–链接：静态、装入时动态、运行时动态–重定位：重定位、静态重定位、动态重定位•地址空间：作业地址空间与物理地址空间•动态分区分配算法–首次适应–循环首次–最佳–最坏–空闲分区的分配与回收算法•基本分页存储管理–页面、页框、页表的概念–逻辑地址结构–地址变换机构–快表•基本分段存储管理–为什么要引入分段存储管理方式–逻辑地址结构–地址变换机构•虚拟存储器基本概念–引入虚拟存储器的目的–虚拟存储器的特征–整体对换VS虚拟存储器•请求分页存储管理–系统需要的硬件支持–系统需要的软件支持–物理块分配与置换的策略–缺页中断与一般中断的不同–抖动–页面置换算法（OPT、FIFO、LRU、CLOCK）•第6章输入输出系统•I/O系统•设备控制器–设备控制器是CPU与I/O设备之间的接口–功能：完成设备与主机间的连接和通信–分类：字符设备与块设备，典型的设备是什么•通道–概念，作用：实现内存与外设之间的信息传输•I/O控制方式：程序、中断、DMA、通道–中断、DMA控制方式适用于何种类型的设备•缓冲管理–引入缓冲区的目的•设备独立性的概念–什么是设备独立性，如何实现•设备驱动•设备的分配–数据结构–独占设备的分配–SPOOLing技术及组成•磁盘存储器的调度–磁盘调度算法（FCFS；SSTF；SCAN；CSCAN）•第7章文件管理•文件系统的目标•文件的逻辑结构–逻辑结构：概念及分类（顺序文件、索引文件、索引顺序文件）•目录管理–对目录管理的要求•第8章磁盘存储器的管理•文件的物理结构–物理结构：概念及分类（连续分配方式、链接分配、索引分配）•文件存储空间的管理–位示图法•磁盘容错技术–第一、二级容错技术第1章作业一、选择题1.操作系统中采用多道程序设计技术提高了CPU和外部设备的A.利用率B.可靠性C.稳定性D.兼容性2.在操作系统中，并发性是指若干事件发生。A.在同一时刻B.一定在不同时刻C.在某一时间间隔内D.依次在不同时间间隔内3.订购机票系统处理各个终端的服务请求，处理后通过终端回答用户，所以它是一个。A.分时系统B.多道批处理系统C.计算机网络D.实时信息处理系统4.下列选择中，不是操作系统关心的主要问题。A.管理计算机裸机B.设计、提供用户程序与计算机硬件系统的界面C.管理计算机系统资源D.高级程序设计语言的编译器5.在操作系统中，处理机负责对进程进行管理和调度，对系统中的信息进行管理的部分通常称为。A.数据库系统B.软件系统C.文件系统D.检索系统二、简答题1、设计现代OS的主要目标是什么？2、何谓脱机I/O和联机I/O？3、实现分时系统的关键问题是什么？应如何解决？4、OS有哪几大特征？其最基本的特征是什么？5、是什么原因使操作系统具有异步性特征？6、何谓微内核技术？在微内核中通常提供了哪些功能？三、综合题1、设内存中有三道程序A、B、C，它们按A、B、C的优先次序执行。它们的计算和I/O操作时间如表所示（单位：ms）。三道程序的操作时间程序操作ABC计算306020I/O403040计算101020假设三道程序使用相同设备I/O操作，即程序是以串行方式使用设备，调度程序的执行时间忽略不计，试计算出在单道和多道两种情况下，完成这三道程序各要花多少时间？要求画出多道运行的时序图。（假定在多道方式下采用的是基于优先级的非抢占调度程序）第2章作业1、进程之间存在着哪几种制约关系？各是什么原因引起的？下列活动分别属于哪种制约关系？（1）若干同学去图书馆借书；（2）两队举行篮球比赛；（3）流水线生产的各道工序；（4）商品生产和社会消费。2、已知一个求值公式(A2＋3B)/(B+5A)，若A、B已赋值，试画出该公式求值过程的前趋图，并使用信号量描述这些前趋关系。3、试用信号量实现课件中司机与售票员进程的同步关系课后作业一、简答题：1、什么是前趋图？为什么要引入前趋图？2、程序并发执行时为什么会失去封闭性和可再现性？3、试说明PCB的作用，为什么说PCB是进程存在的唯一标志？4、同步机构应遵循哪些基本准则？5、何谓“忙等”？它有什么缺点？6、试从物理概念上说明记录型信号量wait和signal。7、在生产者—消费者问题中，分别分析如果缺少了signal(full)或signal(empty)，对执行结果将会有何影响？8、我们为某临界资源设置一把锁W，当W=1时表示关锁；当W=0时表示锁已经打开，试写出开锁和关锁原语，并利用它们去实现互斥。9、试说明管程由哪几部分组成，为什么要引入条件变量？10、为什么要引入信号量集?信号量集中有哪两种操作？11、当前有哪几种高级通信机制？12、为什么引入进程？为什么引入线程？13、试说明线程具有哪些属性？14、何谓用户级线程和内核支持线程？综合题：1、如图所示，有一计算进程和一打印进程，它们共享一个单缓冲区，计算进程不断地计算出结果并将它放入单缓冲区中，打印进程则负责从单缓冲区中取出每一个结果进行打印。请用信号量来实现它们的同步关系。2、试用信号量解决读者—写者问题，使得写者与读者优先级根据到达顺序确定（读写平等）。在该解决方案中，请加入阅览室最多只许多N位读者的限制条件。然后用到达序列：R1,R2,W1,R3,R4,W2进行测试列出类似如下测试结果进程行为rmutex=1wmutex=1Readcount=0状态备注R1到达rmutex=0rmutex=1wmutex=0Readcount=1执行/就绪第1位读者3、请给出一个写者优先的“读者—写者”问题的算法描述，实现比较温和的写者优先策略。然后用到达序列：R1,R2,W1,R3,R4,W2进行测试列出类似如下测试结果进程行为rmutex=1wmutex=1Readcount=0状态备注R1到达rmutex=0rmutex=1wmutex=0Readcount=1执行/就绪第1位读者4、桌上有一只能容纳一个水果的盘子；爸爸专向盘子中放苹果(apple)，妈妈专向盘子中放桔子(orange)，一个儿子专等吃盘子中的桔子，一个女儿专等吃盘子里的苹果，1）试用信号量实现他们的同步关系；2）如果有两个家庭的爸爸、妈妈、儿子、女儿和二只盘子呢？会需要专门的实现吗？5、请用counter作为临界资源的方案解决生产者消费者问题？这种解决方案与书本上的解决方案相比，有何缺点第三章1、某进程被唤醒后立即投入运行，我们就说这个系统采用的是剥夺调度方法，对吗？为什么？10”2、什么是高响应比优先调度算法，它采用何种调度方式？10”3、假设一个系统中有4个进程，它们的到达时间和服务时间如表所示，忽略I/O以及其他开销时间，若分别按先来先服务（FCFS）、非抢占及抢占的短进程优先（SPF）、高响应比优先（HRRN）、时间片轮转（RR，时间片=1）、多级反馈队列调度算法（MFQ，第i级队列的时间片=2i-1）进行CPU调度，请给出各进程的完成时间、周转时间、带权周转时间、平均周转时间和平均带权周转时间，填入下表中（抢占式算法要求画出调度时序图，HRRN算法要求列出调度时的响应比）。30”进程到达时间服务时间A05打印进程单缓冲区计算进程算法时间进程平均时间ABCDFCFS完成时间周转时间带权周转时间SPF（非抢占）完成时间周转时间带权周转时间SPF（抢占）完成时间周转时间带权周转时间RR（q=1）完成时间周转时间带权周转时间MFQ（q=2i-1）完成时间周转时间带权周转时间4、在一个软实时系统中有四个周期性任务，任务A、B、C、D分别要求每50ms、100ms、200ms、250ms执行一次，假定A、B、C、D的执行时间分别为35ms、20ms、10ms与xms，那么要使得这个实时系统为可调度的，x的最大值为多少？（要求列出计算公式）10”5、什么是最低松弛度优先调度算法？它采用何种调度方式？抢占时机是什么？10”6、若有4个周期性任务，任务A要求每30ms执行一次，执行时间为15ms；任务B要求每50ms执行一次，执行时间为5ms；任务C要求每50ms执行一次，执行时间为15ms；任务D要求每100ms执行一次，执行时间为10ms，应如何按最低松弛度优先算法对它们进行CPU调试？（要求画出0-150ms时段的调度时序图，并列出每次切换时每个任务的松弛度）20”7、何谓死锁？产生死锁的原因和必要条件是什么？10”8、3个进程共享4个同类型的资源，每个进程最大需要2个资源，请问该系统是否会因为竞争该资源而死锁？10”B12C39D67作业号到达时间运行时间开始时间完成时间周转时间带权周转时间调度依据平均周转时间为：平均带权周转时间为：9、不安全状态是否必然导致系统进入死锁状态？举例说明。10”10、在银行家算法中，若出现下面的资源分配情况：30”ProcessAllocationNeedAvailableP0003200121522P110001650P213542356P301320552P400140658试问：1）该状态是否安全（要求列出安全性算法检查表）？2）若进程P2提出请求Request(1,2,2,2)后，系统能否将资源分配给它（要求根据分配算法列出检查过程）？3）如果系统立即满足P2的上述请求，请问，系统是否立即进入死锁状态，请说明原因？11、进程资源的使用情况和可用情况如