北京理工大学远程教育学院2019-2020学年第二学期 《操作系统》期末试卷（A卷）

admin

(93)  北京理工大学远程教育学院2019-2020学年第二学期
《操作系统》期末试卷（A卷）

教学站               学号                  姓名              成绩            
应用题（每题20分，共100分）
1.        试说明操作系统与硬件、其他系统软件以及用户之间的关系。
2.常见的进程调度算法包括先来先服务算法、短作业优先调度算法、高优先权优先调度算法和基于时间片的轮转调度算法，请简述这几个算法的调度思想。
3．操作系统的主要任务是什么？请论述其基本功能。
4．请论述基本分页系统中将逻辑地址L转化为物理地址的过程。
  


5.某工厂有一个可以存放设备的仓库，总共有8个位置可以存放8台设备。生产部门生产的每一台设备都必须入库。销售部门可以从仓库提出设备供应客户。设备的出库和入库都必须借助运输工具。现在只有一套运输工具，每次只能运输一台设备，系统共使用三个信号量，S代表互斥信号量，表示运输工具；S1和S2均为同步信号量，S1表示仓库中可以存放设备的空闲位置，S2表示仓库中已经被设备占用了的位置。请设计一个能协调工作的自动调度管理系统，并利用记录型信号量写出解决此问题的程序代码，请注明信号量的初值。

(93)  北京理工大学远程教育学院2019-2020学年第二学期
《操作系统》期末试卷（A卷）答题纸

教学站               学号                  姓名              成绩            

1.

操作系统是覆盖在硬件上的第一层软件，他管理计算机的硬件和软件资源，并向用户提供良好的界面。操作系统与硬件密切相关，它直接管理着硬件资源，为用户完成所有与硬件相关的操作，从而极大地方便了用户对硬件资源的使用并提高了硬件资源的利用率。操作系统是一种特殊的系统软件，其他系统软件运行在操作系统的基础之上，可获得操作系统提供的大量服务，也就是说操作系统是其他系统软件与硬件之间的接口。而一般用户使用计算机除了需要操作系统支持以外，还需要用到大量的其他系统软件和应用软件，以使其工作更高效和方便。















2．
先来先服务和短作业优先算法
先来先服务(FCFS)/先进先出(FIFO)调度算法
按照作业/进程进入系统的先后次序进行调度,先进入系统者先调度；即启动等待时间最长的作业/进程。
是一种最简单的调度算法，即可用于作业调度，也可用于进程调度。
先来先服务(先进先出)优缺点
比较有利于长作业(进程)，而不利于短作业(进程)。
有利于CPU繁忙型作业(进程),而不利于I/O繁忙型作业( 进程)。
用于批处理系统，不适于分时系统。
口短作业(进程)优先调度算法SJ(P)F
短作业(进程)优先调度算法SJ(P)F，以要求运行时间长短进行调度，即启动要求运行时间最短的作业。
        可以分别用于作业调度和进程调度。
        短作业优先(SJF)的调度算法，是从后备队列中选择一个或若干个估计运行时间最短的作业，将它们调入内存运行；而短进程优先(SPF)调度算法，则是从就绪队列中选出一估计运行时间最短的进程，将处理机分配给它，使它立即执行并一直执行到完成，或发生某事件而被阻塞放弃处理机时，再重新调度。
SJ(P)F调度算法也存在不容忽视的缺点
        对长作业不利。严重的是，若一长作业(进程)进入系统的后备队列(就绪队列)，由于调度程序总是优先调度那些(即使是后进来的)短作业(进程),将导致长作业(进程)长期不被调度——饥饿
        完全未考虑作业(进程)的紧迫程度，因而不能保证紧迫性作业(进程)会被及时处理。
由于作业(进程)的长短只是根据用户所提供的估计执行时间而定的，而用户又可能会有意或无意地缩短其作业的估计运行时间，致使该算法不一定能真正做到短作业优先调度。
高优先权优先(HPF，Highest Priority First)调度算法
优先权调度算法的类型
        非抢占式优先权调度算法
特点:系统一旦把处理机分配给就绪队列中优先权最高的进程后，该进程便一直执行下去，直至完成，或因发生某事件使该进程放弃处理机时，系统才将处
理机重新分配给另一优先权最高的进程主要用于批处理系统中，也可用于某些对实时性要求不严的实时系统中。
抢占式优先权调度算法
把处理机分配给优先权最高的进程，但在执行期间，只要出现另一个优先权更高的进程，则进程调度程序就立即停止当前进程的执行，并将处理机分配给新到的优先权最高的进程。
注意:只要系统中出现一个新的就绪进程，就进行优先权比较。
该调度算法，能更好地满足紧迫作业的要求,故而常用于要求比较严格的实时系统中，以及对性能要求较高的批处理和分时系统中。
优先权的类型
静态优先权
静态优先权在创建进程时确定，且在进程的整个运行期间保持不变。一般地，优先权是利用某一范围内的一个整数来表示的，例如，0~7或0~255,又把该整数称为优先数。
确定进程静态优先权的依据。
进程类型:系统进程，用户进程。
进程对资源的需求。
用户要求。
问题:用户将优先权设的较高，对其他进程不利! !短进程优先对长进程不利! !
动态优先权
        随进程的推进或随其等待时间的增加而改变，以获得更好的调度性能。
可规定，在就绪队列中的进程，随其等待时间的增长，其优先权以速率a提高。
具有相同优先权初值的进程，则最先进入就绪队列，其将因其动态优先权变得最高而优先获得处理机，此即FCFS算法。
        具有各不相同的优先权初值的就绪进程，则优先权初值低的进程，在等待了足够的时间后，其优先权便可能升为最高，从而可以获得处理机。
        当采用抢占式优先权调度算法时，如果再规定当前进程的优先权以速率β下降，则可防止一个长作业长期地垄断处理机。
HRF总结
        等待时间相同的作业，则要求服务的时间愈短，其优先权愈高,——对短作业有利。
要求服务的时间相同的作业，则等待时间愈长，其优先权愈高,——是先来先服务。
长作业，优先权随等待时间的增加而提高，其等待时间足够长时，其优先权便可升到很高，从而也可获得处理机，——对长作业有利。
是一种折衷，既照顾了短作业，又考虑了作业到达的先后次序，又不会使长作业长期得。
缺点:要进行响应比计算，增加了系统开销。
基于时间片的轮转调度算法
简单的时间片轮转法(RR-Round Robin)
系统将所有的就绪进程按先来先服务的原则排成一个队列，每次调度时，把CPU分配给队首进程，并令其执行一个时间片。
当执行的时间片用完时，由一个计时器发出时钟中断请求，调度程序便停止该进程的执行，并将其放就绪队列尾;然后，再把处理机分配给就绪队列中新的队首。
时间片的大小从几ms到几百ms。
缺点:紧迫任务响应慢。
UNIX中采用:时间片+优先权
分时系统中常用时间片轮转法
时间片选择问题
        固定时间片
        可变时间片
        时间片大小
与时间片大小有关的因素
        系统响应时间
        就绪进程个数
         CPU能力
多级队列调度
前台的就绪队列是交互性作业的进程，采用时间片轮转。
后台的就绪队列是批处理作业的进程，采用优先权或短作业优先算法。
调度方式有两种:
(1)优先调度前台，若前台无可运行进程，才调度后台。
(2)分配占用CPU的时间比例，如:前台80%,后台20%。
多级反馈队列调度算法
        多个就绪队列，进程所属队列可变，即进程可以在不同的就绪队列之间移动。
        设置多个就绪队列，分别赋予不同的优先级，如逐级降低，队列1的优先级最高。每个队列执行时间片的长度也不同，规定优先级越低则时间片越长，如:逐级加倍。
队列优先级逐级降低，而时间片长度逐级递增。
特点
短进程和新进程优先于长进程和老进程。运行时间短的进程在经过前面几个队列之后便已经执行完，而这些队列中的进程被优先调度。
        响应速度快:交互式进程反应及时。
设备资源利用率高。因为与设备打交道的进程可能经常会由于下面原因而进入等待状态:所申请的资源被占用，启动了I/O传输。当等待事件发生时，它将进入最高优先级就绪队列，尽快获得处理机并使用资源。
        系统开销小。因为运行时间长的进程最后进入低优先级的队列，这些队列的时间片较长，因而进程的调度频率较低。





















3．
操作系统的知主要任务是处理诸如：管理与配置内存、决定系统资源供需的优先次序、控制输入与输出设备、操作网络与管理文道件系统等基本事务。
操作系统是一个庞大的管理控制回程序，大致包括5个方面的管理答功能：进程与处理机管理，作业管理，储存管理，设备管理，文件管理。
处理机管理的主要功能是：进程管理、进程同步、进程通信和处理机调度； 进程管理：为作业创建进程，撤销已结束进程，控制进程在运行过程中的状态转换。 进程同步：为多个进程（含线程）的运行进行协调。 进程通信：用来实现在相互合作的进程之间的信息交换。 处理机调度： （1）作业调度。从后备队里按照一定的算法，选出若干个作业，为他们分配运行所需 的资源（首选是分配内存）。 （2）进程调度：从进程的就绪队列中，按照一定算法选出一个进程，把处理机分配给 它，并设置运行现场，使进程投入执行。  内存管理的主要功能有：内存分配、内存保护、地址映射和内存扩充。 内存分配：为每道程序分配内存。 内存保护：确保每道用户程序都只在自己的内存空间运行，彼此互不干扰。 地址映射：将地址空间的逻辑地址转换为内存空间与对应的物理地址。 内存扩充：用于实现请求调用功能，置换功能等。  设备管理主要功能有: 缓冲管理、设备分配和设备处理以及虚拟设备等。 主要任务: 完成用户提出的I/O 请求，为用户分配I/O 设备；提高CPU 和I/O 设 备的利用率；提高I/O速度；以及方便用户使用I/O设备.  文件管理的主要功能是文件存储空间的管理，目录管理，文件的读写管理和文件的共享与保护。主要任务是对用户文件和系统文件进行管理，以方便用户使用，并保证文件的安全性。















4.






















5．
（1）定义信号量，说明各信号量的含义并赋初值：

mutex，full，empty：semaphore;

mutex：=1;运输工具是否空闲，初值为1

empty：=8;仓库中尚可存放多少设备，初值为8

full：＝0;仓库中的设备数，初值为0

（2）PV操作实现如下

begin

mutex，full，empty：semaphore;

mutex：=1;empty：=8;full：＝0;

cobegin．

processor producerprocessor consumer

beginbegin

生产设备；P（full）;

P（empty）; P（mutex）;

P（mutex）;将设备从仓库取出；

将设备送入仓库；V（mutex）;

V（mutex）; V（empty）;

V（full）;把设备销售给用户；

end;end;

coend;

end．