操作系统第八章.docx

散列结构：
① 基本思想：定义个一个散列函数hash(key)，使得对于给定的键key，散列函数hash(key)将其转换为key所对应的存储地址。
即： hash(key)=addr (在磁盘或文件中的存放位置)
② 散列冲突
③ 解决散列冲突：线性散列法、顺序探查法等。
线性散列法：hi(k)=(h1(k)+di)(mod t)
di=a*i

例题：设散列函数h(n)=(676*l1+26*l2+l3)(mod t)，t＝11，li为键n的第i个英文字母序号。键表长11，键名为英文字母。按线性散列法计算将任意7个键放入链表中所用的计算次数。这里令a＝2，c＝1。
解：设7个关键字分别为：zhl，ouy，lwj，yks，lxz，suy，hls
则有：h(n)=(767*l1+26*l2+l3) mod 11
（1） 线性散列法：
hi(k)=(h1(k)+2i) mod 11
h(zhl)=(676*26+26*8+12) mod 11＝9
h(ouy)=(676*15+26*21+25) mod 11 =8
h(lwj)=(676*12+26*23+10) mod 11=8
h2＝（8+2*2） mod 11＝1
h(yks)=(676*25+26*11+19) mod 11=1
h2＝（1+2*2） mod 11＝5
h(lxz)=(676*12+26*24+26) mod 11=6
h(suy)=(676*19+26*21+25) mod 11=6
h2＝（6+2*2） mod 11＝10
h(hls)=(676*8+26*12+19) mod 11＝8
h2＝（8+2*2）mod 11＝1
h3＝（8+2*3）mod 11＝3
二、某虚拟存储器的用户编程空间共32个页面，每页为1KB，内存为16KB。假定某时刻一用户页表中已调入内存的页面对应的物理块号如下表：
则逻辑地址0A5C（H）所对应的物理地址为 ：125C
答：0A5C＝0000,1010,0101,1100 页号为2，对应块号为4，有：物理地址：0001，0010,0101,1100 即：125C
三、分页式存储空间的分配由于块的大小是固定的，可以用一张位示图来构成主存分配表。
现设主存有8192 块，则可用字长为32 位的256 个字作为位示图。若块号、字号、位号
（从高位到低位）都是从0 开始，试问4999 块对应的字号和位号；129 字的29 位对应
哪一块？
答：【参考答案】依题目所给条件，已知位示图如下所示：
4999÷32=156,余1所以4999 块对应的字号为156，位号为1。 129 字的第29 位对应的块号为：129 * 32 + 29 = 4157 块），即对应内存的第4157 块。
四、某页式存储器用户地址空间有32 个页面，每页1KB，主存16KB。假定某时刻为用户的第0，1，2，3 号页面分配的物理页号为5，10，4，7，试将虚拟地址0A5C 和0D3C 变 化成物理地址。
【参考答案】因为有32 个页面：虚地址中高5 位为页号；由于有1KB 页长，所以虚地
址中低10位为页内地址。
0A5C = 000 1010 0101 1100 虚页号为2，物理页号为4
000 1010 0101 1100 ð 001 0010 0101 1100 =125C
0D3C = 000 1101 0011 1100 虚页号为3，物理页号为7
000 1101 0011 1100 ð 001 1110 0101 1100 =1F3C
四、有两个用户进程A和B，在运行过程中都要使用系统中的一台打印机输出计算结果。
(1) 试说明A、B两进程之间存在什么样的制约关系？
(2) 为保证这两个进程能正确地打印出各自的结果，请用信号量和P、V操作写出各自的有关申请、使用打印机的代码。要求给出信号量的含义和初值。
答：（1）A、B两进程之间存在互斥的制约关系。因为打印机属于临界资源，必须一个进程使用完之后另一个进程才能使用。
（2）mutex：用于互斥的信号量，因为只有一台打印机，所以初值为1。
进程A 进程B
... ...
... ...
P(mutex)； P(mutex)；
申请打印机； 申请打印机；
使用打印机； 使用打印机；
V(mutex)； V(mutex)；… …
五、若干个等待访问磁盘者依次要访问的柱面为20，44，40，4，80，12，76，假设每移动一个柱面需要3毫秒时间，移动臂当前位于40号柱面，请按下列算法分别计算为完成上述各次访问总共花费的寻找时间。
（1）先来先服务算法；
（2）最短寻找时间优先算法。
答：（1）3毫秒×292=876毫秒（4分） （2）3毫秒×120=360毫秒（4分） （注：各算法使移动臂的移动次序和移动的柱面数如下：
（1）40 → 20 → 44 → 40 → 4 → 80 → 12 → 76
（20） （24） （4） （36） （76） （68） （64） 共移动292柱面
（2）40 → 44 → 20 → 12 → 4 → 76 → 80
（4） （24） （8） （8） （72） （4）
共移动120柱面
六、（8分）某系统中有10台打印机，有三个进程P1，P2，P3分别需要8台，7台和4台。若P1，P2，P3已申请到4台，2台和2台。试问：按银行家算法能安全分配吗？请说明分配过程。
答：系统能为进程P3分配二台打印机（3分）。因为尽管此时10台打印机已分配给进程P1 4台，P22台和P34台，全部分配完，但P3已分配到所需要的全部4台打印机，它不会对打印机再提出申请，所以它能顺利运行下去，能释放占用的4台打印机，使进程P1，P2均可能获得乘余的要求4台和5台，按银行家算法是安全的。（5分）
七：若在一分页存储管理系统中，某作业的页表如下所示。已知页面大小为1024字节，试将逻辑地址1011，2148，4000，5012转化为相应的物理地址。
页号
物理块号
0
2
1
3
2
l
3
6
本题中，为了描述方便，设页号为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 ；对于逻辑地址4000；P＝INT(4000／1024)=3；
D=4000 mod 1024＝928；查页表第3页在第6块，所以物理地址为7072。对于逻辑地址5012；P=INT(5012／1024)=4；D=5012 mod 1024=916；因页号超过页表长度，该逻辑地址非法。
八、某虚拟存储器的用户编程空间共32个页面，每页为1KB，内存为16KB。假定某时刻一用户页表中已调入内存的页面的页号和物理块号的对照表如下：
则逻辑地址0A5C（H）所对应的物理地址是什么？
答：页式存储管理的逻辑地址分为两部分：页号和页内地址。由已知条件“用户编程空间共32个页面”，可知页号部分占5位；由“每页为1KB”，1K=210，可知内页地址占10位。由“内存为16KB”，可知有16块，块号为4位。逻辑地址0A5C（H）所对应的二进制表示形式是：000 1010 0101 1100 ，根据上面的分析，下划线部分为页内地址，编码“000 10”为页号，表示该逻辑地址对应的页号为2。查页表，得到物理块号是4（十进制），即物理块地址为：01 00 ，拼接块内地址10 0101 1100，得01 0010 0101 1100，即125C（H）。
九、有一个仓库，可以存放A和B两种产品，但要求：
(1)、每次只能存放一种产品（A或B）;
(2)、-N < A产品数量- B产品数量< M。
其中，N和M是正整数。试用P、V操作描述产品A与产品B的入库过程。
解：在本题中，我们可以设置两个信号量来控制A、B产品的存放数量，sa表示当前允许A产品比B产品多入库的数量，即在当前库存量和B产品不入库的情况下，还可以允许sa个A产品人库;sb表示当前允许B产品比A产品多入库的数量，即在当前库存量和A产品不入库的情况下，还可以允许sb个B产品入库。初始时，sa为M-1，sb为N-1。当往库中存放入一个A产品时，则允许存入B产品的数量也增加1：当往库中存放入一个B产品时，则允许存入A产品的数量也增加1。
产品A、B的入库过程描述如下：
int mutex=1; /* 互斥信号量 */
int sa=M-1;
int sb=N-1;
main()
{
while(1)
{
取一个产品;
if(取的是A产品)
{
p(sa);
p(mutex);
将产品入库;
v(mutex);
v(sb);
}
else /* 取的产品是B */
{
p(sb);
p(mutex);
将产品入库;
v(mutex);
v(sa);
}
}
}
十、有一页式系统，其页表存放在内存中。
(1)、如果对内存的一次存取需要1.5微秒，问实现一次页面访问的存取时间是多少？
(2)、如果系统增加有快表，平均命中率为85%，当页表项在快表中时，其查找时间忽略为0，问此时的存取时间为多少？
答：a.在分页存储管理中,当访问一条指令或数据时需要访问内存至少两次。一次是访问存放在内存中的页表PMT,实现地址变换; 另一次是访问所需的数据。在分段存储管理中,当访问一条指令或数据时,也需要访问内存至少两次。一次是访问存放在内存中的段表SMT,实现地址变换；另一次是访问所需的数据。在段页式存储管理中,当访问一条指令或数据时,需要访问内存至少三次。一次是访问存放在内存中的段表SMT,查找段号所对应的页表; 再一次是访问存放在内存中的页表PMT,实现地址变换; 第三次是访问所需的数据。
b.若快表的命中率是85%,则有效存取时间为:0.85×1+(1-0.85)×(1+1)=1.15μs。若快表的命中率为50%,则有效存取时间为:0.5×1+(1-0.5)×(1+1)=1.5μs(2分)

十一、用P、V操作实现下述问题的解。桌上有一个盘子，可以存放一个水果。父亲总是放苹果到盘子中，而母亲总是放香蕉到盘子中；一个儿子专等吃盘子中的香蕉，而一个女儿专等吃盘中的苹果。
定义信号量：dish:表明盘子中是否为空，初值为1；Apple:表明盘子中是否有苹果，初值为0；Orange:表明盘子中是否有桔子，初值为0；

main ()
{cobegin
father ();
mother ();
son ();
daughter ();
coend
}
father ()
{ P(dish);
…
放苹果
…
V(apple);
}
mother()
{ P(dish);
…
放香蕉
…
V(orange);
}
son ()
{ P(orange);
…
取香蕉
…
V(dish);
}
daughter()
{ P(apple);
…
取苹果
…
V(dish);
}
十二、设公共汽车上，司机和售票员的活动分别是：司机的活动：启动车辆；正常行车；到站停车。
售票员的活动：关车门；售票；开车门。在汽车不断地到站、停站、行驶过程中，这两个活动有什么同步关系？用信号量和P、V操作实现它们的同步。
第一步：确定进程间的关系。售票员关车门后，要向司机发开车信号，司机接到开车信号后才能启动车辆。在汽车正常行驶过程中售票员售票，到站时司机停车，售票员在车停后开车门，让乘客上下车。因此司机启动车辆的动作必须与售票员的动作取得同步；售票员开车门的动作也必须同司机停车取得同步。第二步：确定信号量及其值。由于司机与售票员之间要互通消息，司机进程设置一个私有信号量run，用于判断是否关车门，司机能否启动车辆，初值为1。售票员进程设置一个私有信号量stop，用于判断是否停车，售票员是否能够开车门，初值为0
第三步： 确定P（wait）、V（signal）操作的位置司机操作中，是否关门？没关则等待，这是一个P操作，P(run)；司机操作中，设立停车标志，这是一个V操作，V(stop)；售票员操作中，是否停车？没停则等待，这是一个P操作，P(stop)；售票员操作中，设立关门标志，这是一个V 操作，V(run)
lstop ,run:semaphore
run:=1; //是否关车门
stop:=0; //是否停车
Driver：begin cobegin
driver: begin
L1: P(run);
启动车辆；
正常行车；
到站停车；
V(stop);
goto L1;
end;
Conductor:begin
L2:上乘客；
关车门；
V(run);
售票；
P(stop);
开车门；
下乘客；
goto L2;
end;
coend;
end

十三、某寺庙，有小、老和尚若干，有一水缸，有小和尚提水入缸供老和尚饮用。水缸可容10桶水，水取自同一井中。水井径窄，每次只能容一个桶取水。水桶总数为3个。每次入、取缸水仅为1桶，且不可同时进行。试给出取水、入水的算法描述。
设置5个信号量：互斥信号量mutex1,用于实现对水井的互斥使用，其初值为1；互斥信号量mutex2，用于实现对水缸的互斥使用，其初值为1；信号量empty，用于记录水缸中还可以装入水的桶数，其初值为10；信号量full，用于记录水缸中已装入水的桶数，其初值为0；信号量count，用于记录可用水桶数目，其初值为3。
Semaphore mutex1=1;
Semaphore mutex2=1;
Semaphore empty=10;
Semaphore full=0;
Semaphore count=3;
Main( )
{ cobegin
Get();
Use();
Coend
}
V(full);
}
}
Use( )
{ while (ture)
{ P(full);
P(count);
Get( )
{ while(ture)
{ p(empty);
P(count);
P(mutex1);
从井中取水；
V(mutex1);
P(mutex2);
将水倒入水缸；
V(mutex2);
V(count);
P(mutex2);
从缸中取水；
V(mutex2);
V(empty);
V(count);

十四、假设有一台计算机，它有1M内存，操作系统占用200K，每个用户进程也占用200K。用户进程等待I/O的时间为80%，若增加1M内存，则CPU的利用率将提高多少？
解：1M内存的情况：1）支持用户进程数：（1024K-200K）/200K=4.12 所以4个用户进程。 2）CPU利用率： 先求CPU空闲（4个用户均处于等待I/O状态）概率P=（80%）4，然后再求CPU利用率1-P =1-（80%）4 = 1-0.84=59%。增加1M内存的情况：1）支持用户进程数：（2*1024K-200K）/200K=9.24 所以9个用户进程。 2）CPU利用率： 先求CPU空闲（9个用户均处于等待I/O状态）概率P（80%）9，然后再求CPU利用率1-P 1-P =1-（80%）9 = 1 -0.89=87%。增加1M内存，CPU的利用率将提高：87% / 59%= 147% 147% - 100%=47%所以若增加1M内存，则CPU的利用率将提高47%。
十五、多个进程共享一个文件，其中只读文件的称为读者，只写文件的称为写者。读者可以同时读，但写者只能独立写。（6分）
（1）说明进程间的相互制约关系，应设置哪些信号量？
（2）用P、V操作写出其同步算法。
1>进程间的相互制约关系有三类，一是读者之间允许同时读；二是读者与写者之间必须互斥；三是写者之间须互斥写。
2> 进程间的控制算法如下：

BEGIN
Integer mutex1,mutex2,rc;
Mutex1:=1;
Mutex2:=1;
Rc:=0;
COBEGIN
Reader:BEGIN
P(mutex1);
Rc:=rc+1;
IF rc=1 THEN P（mutex2）;
V(mutex1);
Reading the file;
P(mutex1);
Rc:=rc-1;
IF rc=0 THEN V(mutex2);
V(mutex1);
ENG
Writer:BEGIN
P(mutex2);
Wrinter the file;
V(mutex2);
END
COEND
END
3> 为了提高写者的优先级，我们增加一个信号量w，用以在写进
程到达时封锁后续的读者进程。相应的控制算法如下：
BEGIN
Integer mutex1,mutex2,rc,w;
Mutex1:=1;
Mutex2:=1;
Rc:=0;
W:=1
COBEGIN
Reader:BEGIN
P(w);

V(mutex1);
ENG
Writer:BEGIN
P(w);
P(mutex2);
Wrinter the file;
V(mutex2);
V(w);
END
COEND
END
十六、某系统有224字节内存，固定分区大小为65536B，进程表中的每个表项最少要用多少位记录分配给进程的分区？
解答：65536=216
把内存总字节数除以分区大小得到分区数，即224/216=28.因此至少要用8位记录才能描述28个表项中的一个。
十七、某段表内容如下：

假如一逻辑地址为（2，154），则其对应的实际物理地址为多少？
解：从逻辑地址（2，154）可知，段号为2；段内地址为154。根据段号查段表可得“段首地址”为“480K”，根据
物理地址=段首地址+段内偏移量可得，物理地址为：480K+154
十八、假定有三个并发进程R，W1和W2共享一个缓冲器B，而B中每次中能存放一个数。当B中无数时，R可以从输入设备上读入数据并将数据存放到B中。若此数是偶数，则允许W1将其取出打印；否则允许W2将其取出打印。进程W1和W2对每次存入缓冲器的数据只能打印一次。W1和W2都不能从空的缓冲器中取数。试用信号量及PV原语完成R、W1、W2的同步操作。（定义信号量时应说明其意义及初值）。
解：信号量初值S1=0，S2=0，S=1

十九、假如系统共有12台磁盘机，有三个进程p1、p2、p3，p1共要求10台，p2共要求4台，p3共要求9台。在T0时刻，设备分配情况如下表所示：

试分析此时系统是否安全？如果在T1时刻，已分配数分别为：p1:5；p2:2；p3:4，此时系统是否安全？
答：（1）系统在T0时刻是安全的。因为分配完后尚有2台可用，而进程p2还需要2台，因此，p2肯定能正常结束，p2释放4台后，正好满足p3所需，p3也能正常结束，p3释放7台，而p1需要5台。所以，存在安全序列：p2 p3 p1，因此系统在T0时刻是安全的。
（2）系统在T1时刻是不安全的。按照p1:5 p2:2 p3:4分配完后，只有1台可用，已不能满足任何进程的需要，所以是不安全的。
二十、1. 这是一个从键盘输入到打印机输出的数据处理流图，其中键盘输入进程通过缓冲区 buf1 把输入数据传送给计算进程，计算进程把处理结果通过缓冲 buf2 传送给打印进程。buf1 和 buf2 为临界资源，试写出键盘输入进程，计算进程及打印进程间的同步算法。（10分）
输入进程 → buf1 → 计算进程 → buf2 → 打印进程
解答：从键盘输入到打印机输出的数据传送过程，可以看作是由键盘输入进程到计算进程，以及由计算进程到打印输出进程这两个数据传送进程所组成。其中，对键盘输入进程而言，计算进程是消费者进程；而对打印输出进程而言，计算进程又是生产者进程。据此可将它们之间的同步问题描述如下：
var：mutex1，mutex2，empty1，empty2，full1，full2：=1，1，1，1，0，0；
IP:begin
repeat
P(empty);
P(mutex1);
input a charcter from keyboard;
Add to buffer;
V(mutex1);
V(full);
until false
end
CP:begin
repeat

P(full);
P(mutex1);
Take a charactor form buffer1;
Add to ch1;
V(mutex1);
V(empty1);
P(empty2);
P(mutex2);
Take a charactor form ch1;
Add to buffer2;
V(mutex2);
V(full2);

until false
end
OP:begin
repeat
p(full2);
P(mutex2);
Take a charactor from buffer2;
Add to printer controler;
start printer;
V(mutex2);
V(empty2);
until false
end
二十一、系统中有五个进程P1、P2、P3、P4、P5，有三种类型的资源：R1、R2、和R3。在T0时刻系统状态如表所示。若采用银行家算法实施死锁避免策略，回答下列问题： （共9分，每小题3分）
1． T0时刻是否为安全状态？为什么？
2． 若这时P4请求资源（1，2，0），是否能实施资源分配？为什么？
在上面的基础上，若进程P3请求资源（0，1，0），是否能实施资源分配？为什么？ 
T0时刻系统状态

已分配资源数量
最大资源需求量
R1
R2
R3
R1
R2
R3
P1
0
0
1
0
0
1
P2
2
0
0
2
7
5
P3
0
0
3
6
6
5
P4
1
1
5
4
3
5
P5
0
3
3
0
6
5

R1
R2
R3
剩余资源数
3
3
0
解：（共9分，每小题3分）
1． T0时刻是安全的，安全序列为：P1，P4，P5，P2，P3
2． P4请求资源（1，2，0），根据银行家算法，预分配后系统是安全的，安全序列为：P1，P4，P5，P2，P3
3． P3请求资源（1，1，0），根据银行家算法，预分配后系统不安全，所以不能实施资源分配。