操作系统大题整理
- 解答题
- 简答题
解答题
1、一个进程的大小占5个页面，每页的大小为1K，系统为它分配了3个物理块。当前进程的页表如表所示：
⑴有哪些页面不在内存？
⑵请分别计算进程中逻辑地址为3B7H、12A5H、1432H 单元的物理地址（用十六进制表示)，并说明理由。
解答：
答:不在内存的是第2和4页（按页号)。
(3B7)16=(001110110111)2 , 1页为 1K ,所以页内地址为低10位(1110110111)2，页号为 OH，对应物理块号为1CH ，物理地址拼接为(000111001110110111)2=(73B7)16
3B7H的物理地址=73B7H
(12A5)16=(0001001010100101)2，1页为1K，所以页内地址为低10位(1010100101)2，页号为4H，缺页换出3H页，物理地址拼接为(010111011010100101)2=(176A5)16
12A5H的物理地址=176A5H ，缺页，换出3H页。
(1432)16=(0001010000110010)2 ，1页为 1K，所以页内地址为低10位(0000110010)2，页号为5H，地址越界，出错。
2、设正在处理器上执行的一个进程的页表如下面所示，表中的虚页号和物理块号是十进制数，起始页号（块号）均为0，所有的地址均是存储器字节地址，页的大小为1024字节。
（注释：访问位——当某页被访问时，其访问位被置1。）
问：下列虚地址对应于什么物理地址：⑴5499，⑵2221。
解答：
虚地址（虚页号，页内地址） 物理地址 （物理块号，块内地址） 5499=1024*5+379 （5，379） （0,379） 2221=1024*2+173 （2,173） （不在内存） 3、(1) 某页式存储系统页表如下，设每页1KB，请写出逻辑地址为8300时所对应的页号和页内地址，以及在内存中对应的物理地址。（请详细写出运算过程）
系统页表：
页号 0 1 2 3 4 5 6 7 8 块号 3 5 6 10 8 7 1 2 4 （2）已知如下段表：
段号 0 1 2 3 4 基址 219 2300 90 1327 1952 长度 600 14 100 580 96 在分段存储管理下系统运行时，下列逻辑地址（第一位表示段号，第二位表示段内位移）的物理地址是什么？
（a）:（1，10）
（b）:（4，112）
解答：
⑴
页号P=INT[A/L]=[8300/1024]=8
页内地址d=[A] MOD L=[8300] MOD 1024=108
物理地址 4×1024+108=4204
⑵
(a)：地址(1，10)的段号为1，查表得基址为2300，段长为14，
物理地址为：2300 + 10 = 2310。
(b)：地址(4，112)的段号为4，查表得基址为1952, 段长为96；
地址(4，112)的段内位移为112，大于段长96，发生段越界，产生越界中断。
4、某请求分页的存储管理系统，且页面大小为120字节。考虑一仅580个字节的程序的下述内存访问序列(该序列的下标均从0开始)：080，119，384，270，173，199，025，245，186，334，458，355。
⑴写出页面的访问序列。
⑵假设内存中仅有360字节可供程序使用且采用FIFO算法，那么共发生多少次缺页中断？
⑶假设内存中仅有360字节可供程序使用且采用LRU算法，则又会发生多少次缺页中断？
⑷假设内存中仅有360字节可供程序使用且采用OPT算法，则又会发生多少次缺页中断？
解答：
⑴页面访问序列：
0，0，3，2，1，1，0，2，1，2，3，2
⑵采用FIFO算法的情况如下：
采用FIFO算法产生的缺页次数7次。
⑶采用LRU算法的情况如下：
采用LRU算法产生的缺页次数6次;
⑷采用FIFO算法的情况如下：
采用FIFO算法产生的缺页次数5次。
5、若干个等待访问磁盘者依次要访问的磁道为20 , 44 , 40 , 4 , 80 , 12 ，76 ，假设每移动一个磁道需要3毫秒时间，移动臂当前位于40号柱面，请按下列算法分别写出访问序列并计算为完成上述各次访问总共花费的寻道时间。
⑴先来先服务算法
⑵最短寻道时间优先算法
⑶扫描算法（当前磁头移动的方向为磁道递增)
⑷循环扫描算法
解答：
⑴磁道访问顺序为：20，44，40，4，80，12，76
寻道时间=( 20+24+4+36+76+68+64 ) 3=2923=876
⑵磁道访问顺序为：40，44，20，12，4 ，76，80
寻道时间=(0+4+24+8+8+72+4 ) 3=1203=360
⑶磁道访问顺序为：40，44，76，80，20，12，4
寻道时间= (0+4+32+4+60+8+8 ) 3=1163=348
⑷磁道访问顺序为：40，44，76，80，4，12，20
寻道时间=（0+4+32+4+76+8+8）3=1323=396
6、若干个等待访问磁盘的进程依次要访问的磁道为27，63，57，24，107，35，106，当前磁头的位置为57号磁道，根据下面的磁盘调度算法，请给出磁头移动顺序、磁头移动距离（以磁道数计)及平均寻道长度。
⑴先来先服务算法
⑵最短寻道时间优先
⑶扫描算法（当前磁头移动的方向为磁道递增）
⑷循环扫描算法（当前磁头移动的方向为磁道递增）
解答：
27，63，57，24，107，35，106
⑴先来先服务FCFS
磁头访问次序：27，63，57，24，107，35，106
磁头移动距离：30，36，6，33，83，72，714
平均寻道长度：47.29
⑵最短寻道时间优先
磁头访问次序：57，63，35，27，24，106，107
磁头移动距离：0，6，28，8，3，82，1
平均寻道长度：18.29
⑶扫描算法SCAN
磁头访问次序：57，63，106，107，35，27，24
磁头移动距离：0，6 ，43，1，72，8，3
平均寻道长度：19
⑷循环扫描算法CSCAN
磁头访问次序：57，63，106，107，24，27，35
磁头移动距离：0，6，43，1，83，3，8
平均寻道长度：20.57
7、在一个两道作业的操作系统中。设在一段时间内先后到达4个作业。它们的提交时刻和运行时间由下表给出。
若作业调度采用短作业优先的调度算法。进程调度采用优先权调度算法(数值越小，优先级越高)
⑴完成下列表格
⑵计篇平均周转时间、平均带权周转时间（小数点后保留两位) 。
解答：
⑴
⑵平均周转时间=(5+6+10+11) ÷4=8
平均带权周转时间=(1+2+2+5.5)÷4=2.625
8、利用信号量机制，根据如下的前趋图定义信号量并写出可并发执行的程序实现前趋关系。
解答：
p1(){S1;signal(a);singal(b);} p2(){wait(a);S2;singal(c);} p3(){wait(b);S3;singal(d);singal(e);} p4(){wait(c);S4;singal(f);} p5(){wait(d);S5;singal(g);} p6(){wait(e);S6;singal(h);} p7(){wait(f);wait(g);wait(h);S7;} void main(){samephore a,b,c,d,e,f,g,h; a.value = b.value = c.value = d.value = e.value = f.value = g.value = h.value = 0; cobegin p1();p2();p3();p4();p5();p6();p7(); coend } }9、Jruassic公园有一个恐龙博物馆和一个公园。有m个旅客和n辆车，每辆车只能容纳一个旅客。旅客在博物馆逛了一会儿，然后排队乘坐旅行车。当一辆车可用时，它载入一个旅客﹐然后绕公园行驶任意长的时间。如果n辆车都已被旅客乘坐游玩，则想坐车的旅客需要等待；如果
一辆车已经就绪，但没有旅客等待，那么这辆车等待。请回答下列问题：
⑴用P、V操作管理这些并发进程时,使用信号量同步m个旅客和n辆车的进程，应定义哪几个信号量？每个信号量的含义是什么？并给出每个信号量的初值。
⑵根据所定义的信号量，把应执行的P、V操作填入下述空格中，以保证进程能够正确地并发执行。
解答：
⑴semaphore visitors=m，cars=n，mutex=1 ;
其中 visitors、cars为资源信号量，visitors表示等待坐车的游客数量；cars表示等能够载客的空车数量；mutex为互斥信号量，实现诸游客对车辆的互斥使用，mutex=1表示该车辆空闲，mutex=0表示该车辆忙。
⑵
10、在一个多道作业的操作系统中，设在一段时间内先后到达4个作业，它们的提交时刻和运行时间由下表给出。进程调度采用时间片轮转调度算法，时间片大小为2。
⑴完成下列表格
⑵计算平均周转时间、平均带权周转时间（小数点后保留两位)
解答：
⑴
⑵平均周转时间=(7+13+11+6) /4=9.25
平均带权周转时间=(2.33+2.6+2.75+3) /4=2.67
平均带权周转时间=(2.33+2.6+2.75+3) /4=2.67
11、设有一单纯分页系统，某作业的逻辑地址空间为4页(每页2048字节)，已知该作业的页表如下：
⑴试借助地址变换图（即要求画出地址变换图)，求逻辑地址3658所纣应的物理地址。
⑵访问逻辑地址3658对应内存单元内容时，需访问几次内存？为什么？
解答：
⑴
⑵每条指合都必须两次访问内存储器，一次是访问页表，由页号找到对应的物理块号；另一次是在物理地址中实际存取所要的数据或指合。
12、系统中有五个进程P0、P1、P2、P3、P4，有三种类型的资源：R1、R2和R3在T0时刻系统状态如表所示，请回答下列问题：
⑴求此刻可用资源数及各进程对各类资源的需求数目。
⑵完成下表，并判断T0时刻是否安全。·
⑶若这时P4请求资源(1，2，0)，是否能实施资源分配？为什么？
解答：
⑴
⑵T0时刻安全。
⑶若这时P4请求资源(1，2，0 )，不能实施资源分配，因为如果分配，可用资源变成（0，0，4)不能满足任何进程的需求，系统进入不安全状态。
13、某系统共有2种资源，在T0时刻P1、P2、P3、P4这4个进程对资源的占用和需求情况如表所示，考虑如下资源分配状态：
⑴画出T0时刻的资源分配图RAG。
⑵化简资源分配图RAG，判断是否会产生死锁。
解答：
⑴
⑵
能完全化简，所以不会发生死锁。
14、系统中的空闲分区表如下，现有三个作业A、B、C分别申请内存空间100K、30K及7K。
⑴给出按最佳适应算法的内存分配情况及分配后空闲分区表。
⑵假设T0时刻B作业完成，请给出回收为B作业分配的分区后，分区空闲表。
解答：
⑴按最佳适应算法，分配前的空闲分区表如上表。
申请作业100k，分配3号分区，剩下分区为20k，起始地址160K；
申请作业30k，分配1号分区，剩下分区为2k，起始地址50K；
申请作业 7k，分配2号分区，剩下分区为1k，起始地址59K；
其内存分配图及分配后空闲分区表如下：
⑵
15、如下图所示的是高级通讯原语SEND和RECEIVE不完整的框图。请填充适当的P，V操作，并说明所用信号量的意义和初值。
解答：
描述消息缓冲队列通信机制中，发送者将消息写到空缓冲块中后，把消息缓冲块链入接收者的消息缓冲队列的过程。
S：同步信号量，用于消息队列中的消息计数，初值为0；
S1：消息队列互斥信号量，初值为1；
①P(S) ；② V(S)； ③ P(S1) ； ④P(S) ； ⑤V(S)
16、有一只铁笼子，每次只能放入一只动物，猎手向笼子里放入老虎，农民向笼子里放入猪；动物园等待取笼子里的老虎，饭店等待取笼子里的猪。现请用wait和 signal操作写出能同步执行的程序。请回答下列问题:
⑴用P、V操作管理这些并发进程时，应定义哪几个信号量，每个信号量的含义是什么；并给出每个信号量的初值。
⑵根据所定义的信号量，把应执行的P、V操作填入下述空格中，以保证进程能够正确地并发执行。
解答：
⑴定义3个信号量
Var Sempty，Stiger，Spig: semaphore:= 1，0，0；
意义：Sempty为互斥信号量，
Sempty =1表示笼子为空，允许放猪或放老虎，
Sempty =0笼子被占用。
Stiger为资源信号量，Stiger的值表示笼中老虎的个数。
Spig为资源信号量，Spig的值表示笼中猪的个数。
⑵①wait(Sempty); ②signal(Stiger);
③wait(Sempty); ④signalSpig);
⑤wait(Stiger); ⑥signal(Sempty);
⑦wait(Spig); ⑧signal(Sempty);
简答题
1、页式存储管理的优缺点是什么？
答：
优点：有效地解决了碎片问题。
缺点：程序的最后一页会有浪费空间的现象开且个能应用在分段编与的非连续存放的大型程序中。
2、访问逻辑地址对应内存单元内容时，需访问几次内存？为什么？
答：
每条指令都必须两次访问内存储器，一次是访问页表，由页号找到对应的物理块号；另一次是在物理地址中实际存取所要的数据或指令。
3、在存储管理中，分页与分段的主要区别是什么?
答：
⑴页是信息的物理单位。 采用分页存储管理方式是为了实现离散分配方式，以消减内存的外零头，提高内存的利用率。或者说，分页只是系统管理上的需要，完全是系统的行为，对用户是不可见的。分段存储管理方式中的段，则是信息的逻辑单位，它通常包含的是一组意义相对完整的信息。分段的目的主要在于能更好地满足用户的需要。
⑵页的大小固定且由系统决定。 在采用分页存储管理方式的系统中，在硬件结构上就把用户程序的逻辑地址划分为页号和页内地址两部分，也就是说该管理方式是直接由硬件实现的，因而在每个系统中只能有一种大小的页面。而段的长度则不固定，其取决于用户所编写的程序，通常由编译程序在对源程序进行编译时根据信息的性质来划分。
⑶分页的用户程序地址空间是一维的。 分页完全是系统的行为，故在分页系统中，用户程序的地址属于单一的线性地址空间，程序员只须利用一个标识符即可表示一个地址。而分段是用户的行为，故在分段系统中，用户程序的地址空间是二维的，程序员在标志一个地址时,既须给出段名，又须给出段内地址。
4、比较进程调度和作业调度的不同点。
答：
⑴作业调度是宏观调度，它决定了哪个作业能进入内存。
进程调度是微观调度，它决定了各作业中哪个进程占有 CPU。
⑵作业调度能选符合条件的收容态作业装入内存。
进程调度能选从就绪态选一个占有CPU。
5、并发程序执行的Bemstein条件是什么？怎么应用？
答：
并发程序执行的 Bernstein条件是：
若P1与P2并发执行，当且仅当(R(P1) ∩ W(P2)) ∪ (R(P2) ∩ W(P1)) ∪ (W(P1) ∩ W(P2))= {}时才满足。
应用：
S1: a=x+y；
S2: b=z+1；
S3: c=a-b；
S4: w=c+1；
则对应的读集和写集分别是：
R(S1)={x,y} ，W(S1)= {a}
R(S2)={z}，W(S2)={b}
R(S3)={a,b}，W(S3)={c}
R(S4)={c}，W(S4)={w}
- 操作系统框架总结内容↑