大连海事大学操作系统测试题

第一次测试 1. 进程的三种基本状态是什么？处于每种状态的进程各有什么特点？并举例说明每种状态转换在什么情况下发生？ 2．现有两个进程Pi和Pj互斥地使用某临界资源，设S是用作互斥的公用信号量(初值为1)，试利用P－V操作描述此两个进程互斥执行过程的描述算法，并说明S＝1，S＝0和S＝－1时的物理意义。 3. 简述作业调度与进程调度主要完成哪些主要功能？ 4. 在采用等长时间片轮转处理机调度算法的分时操作系统中, 各终端用户所占有处理机的时间总量是相同的. 这种说法对吗? 为什么? 5、有三个用户进程A、B和C在运行过程中都要使用系统中的一台打印机输出计算结果。 （1）试说明A、B、C进程之间存在什么样的制约关系？ （2）为保证这三个进程能正确地打印出各自的结果，请用信号量和P、V 操作写出各自的有关申请、使用打印机的伪代码。要求给出信号量的含义和初值。 1. 答： Semaphore Sa=1, Sb1=0, Sb2=1, Sc=0 Pa：Begin P(Sa) 把数据写入缓冲区S中 V(Sb1) End Pb: Begin P(Sb1) P(Sb2) 把数据从缓冲区S中提取到缓冲区T中 V(Sa) V(Sc) End Pc: Begin P(Sc) 从T中取走数据打印 V(Sb2) End 4. 解：(1) 定义信号量为S，其初始值为20。信号量的初值以及信号量各种取值的含义： 　　S>0，S的值表示可继续进入售票厅的人数 　　S=0，表示售票厅中已有20名顾客(购票者) 　　S<0，|S|的值为等待进入售票厅的人数 　　(2) 上框为P(S)　 　　　 下框为V(S)　 　　(3) S的最大值为20　(1分) 　　　 S的最小值为20－n　(1分) 第二次测试 1. 设系统有R1、R2和R3资源各一个，有三个进程P1，P2和P3并发工作。进程P1需用资源R1和R3；进程P2需用资源R1和R2；进程P3需用资源R2和R3。请回答： (1) 若对资源分配不加限制，会发生什么情况? (2) 为保证进程正确工作，应采用怎样的资源分配策略? 2．系统有四个进程P1，P2，P3，P4，有4类可分配的资源A，B，C，D，假设某时刻的资源分配情况如下表所示。 进程 Allocation A B C D Max A B C D Need A B C D Available A B C D P1 3 0 1 1 4 1 1 1 1 1 0 0 1 0 2 0 P2 0 1 0 0 0 2 1 2 0 1 1 2 P3 1 1 1 0 4 2 1 0 3 1 0 0 P4 1 1 0 1 1 1 1 1 0 0 1 0 (1) 说明当前系统是否处于安全状态 (2) 如果是安全状态，按照银行家算法给出资源的分配与回收过程。 3、某进程P有5页，假设访问页的顺序为：3，2，1，4，2，3，5，3，4，2，5；如果在内存中分配给该进程3个页面（设开始时3个页面都是空的），使用LRU页面置换算法，请回答如下问题： （1）计算缺页中断次数 （2）给出页面的淘汰顺序 4、在单机系统环境下，设有4道作业，它们的提交时间及执行时间如下表所示(时间单位:小时)。当采用最短作业优先调度算法(SJF)时，给出作业的调度顺序，并计算每个作业周转时间和平均周转时间（给出计算过程）。 作业名 提交时间（h） 执行时间（h） Job1 10.0 2.0 Job 2 10.2 1.0 Job 3 10.4 0.5 Job 4 10.5 0.3 解：（1）采用短作业优先调度算法，则其调度顺序为：Job1、Job4、Job3、Job2。 （2）计算每个作业的周转时间和平均周转时间 作业 提交时间 执行时间 开始时间 完成时间 周转时间 Job1 10.0 2.0 10.0 12.0 2.0 Job4 10.5 0.3 12.0 12.3 1.8 Job3 10.4 0.5 12.3 12.8 2.4 Job2 10.2 1.0 12.8 13.8 3.6  平均周转时间= (2.0+1.8+2.4+3.6) = 2.5(h) 或 2.45(h) 解： 页面 3 2 1 4 2 3 5 3 4 2 5 页面1 3 2 1 4 2 3 5 3 4 2 5 页面2 3 2 1 4 2 3 5 3 4 2 页面3 3 2 1 4 2 2 5 3 4 × × × × √ × × √ × × × （1）计算缺页中断次数：9次 （3分） （2）页面淘汰顺序： 3，1，4，2，5，3 （3分） 解： （1）标志位：是否在内存，1表示已经调入内存，0表示不在内存。 访问位：最近一段时间该页是否被访问过，被访问置1，否则置0。 修改位：有没有被修改过。若为1，表明修改过，淘汰时必须写回辅存，否则不需要写回。 （2） A．P=INT(1052/1024) =1，L=1052 MOD(1024) = 28，查页表，可知1页对应的内存块号为7，所以物理地址为8*1024+28=8220。 B．P=INT(5499/1024) = 5，L=5499MOD(1024)=379，查页表，可知其对应块号为9，所以物理地址为9*1024+379=9595。 第三次测试 1. 某虚拟存储器的用户编程空间共32个页面，每页为1KB，内存为16KB。假定某时刻一用户页表中已调入内存的页面的页号和物理块号的对照表如下： 页号 物理块号 0 3 1 7 2 11 3 8 则逻辑地址0A5C(H)所对应的物理地址是什么？要求：写出主要计算过程。 2．某段式 HYPERLINK "http://www.educity.cn/incsearch/search.asp?key=%B4%E6%B4%A2" \t "_blank" 存储管理中采用如表3-6所示的段表。 表3-6 段式存储管理的段表 段  号 段的长度（B） 内存起始地址 0 660 219 1 14 3330 2 100 90 3 580 1237 4 96 1952 （1）给定段号和段内地址，说明段式管理中的变换过程。 （2）计算[0, 430]，[1,10]，[2,500]， [3,400]，[4,20]，[5,100]的内存地址，其中方括号内的第一元素是段号，第二元素是段内地址（判断地址是否合法）。 （3）说明存取主存中的一条指令或数据至少要访问几次主存。 3、现有一个仅460个字节的程序的下述内存访问序列（该序列的下标均从0开始）：10、11、104、170、73、309、185、 245、246、434、458、364。且页面大小为100字节。 （1）写出页面的访问序列。 （2）假设内存中仅有200字节可供程序使用且采用FIFO算法，那么共发生多少次缺页中断？　　 （3）如果采用最近最久未使用的算法LRU，则又会发生多少次缺页中断？ 1．解；(共8分，每个2分) 本题中，为了描述方便，设页号为P，页内位移为D，则： 对于逻辑地址1011 P＝INT(1011／1024)=0 D=1011 mod 1024=1011 查页表第0页在第2块，所以物理地址为3059。 对于逻辑地址2148 P＝INT(2148／1024)=2 D＝2148 mod 1024＝100 查页表第2页在第1块，所以物理地址为11240 对于逻辑地址5012 P=INT(5012／1024)=4 D=5012 mod 1024=916 因页号超过页表长度，该逻辑地址非法。 2【解答】 2．某段式 HYPERLINK "http://www.educity.cn/incsearch/search.asp?key=%B4%E6%B4%A2" \t "_blank" 存储管理中采用如表3-6所示的段表。 表3-6 段式存储管理的段表 段  号 段的长度/B 内存起始地址 0 660 219 1 14 3330 2 100 90 3 580 1237 4 96 1952 （1）给定段号和段内地址，说明段式管理中的变换过程。 （2）计算[0, 430]，[1,10]，[2,500]， [3,400]，[4,20]，[5,100]的内存地址，其中方括号内的第一元素是段号，第二元素是段内地址（判断地址是否合法）。 （3）说明存取主存中的一条指令或数据至少要访问几次主存。 （1）为了实现从逻辑地址到物理地址的变换，在系统中需要设置段表寄存器，存放段表起始地址和段表长度TL。在进行地址变换时，系统将逻辑地址中的段号与段表长度TL进行比较。若 S>=TL，则表示段号太大，是访问越界（段号越界），产生越界中断，若未越界，则根据段表的起始地址和段号，计算出该段对应段表项的位置，从中读出该段在内存中的起始位置和段长SL，再检查段内地址D是否超过该面的段长SL。若超过，即D>=SL，则同样发出越界中断信号（段内地址越界）； 若未越界，则将该段的起始地址与段内地址D相加，即得到要访问的内存物理地址。 （