操作系统第八章

《操作系统第八章》由会员上传分享，免费在线阅读，更多相关内容在应用文档-天天文库。

1、散列结构：①基本思想：定义个一个散列函数hash(key)，使得对于给定的键key，散列函数hash(key)将其转换为key所对应的存储地址。即：hash(key)=addr(在磁盘或文件中的存放位置)②散列冲突③解决散列冲突：线性散列法、顺序探查法等。线性散列法：hi(k)=(h1(k)+di)(modt)di=a*i例题：设散列函数h(n)=(676*l1+26*l2+l3)(modt)，t＝11，li为键n的第i个英文字母序号。键表长11，键名为英文字母。按线性散列法计算将任意7个键放入链表中所用的计算次数。这里令a＝2，c＝1。解：设7个关键字分别为：zhl，ouy，

2、lwj，yks，lxz，suy，hls则有：h(n)=(767*l1+26*l2+l3)mod11（1）线性散列法：hi(k)=(h1(k)+2i)mod11h(zhl)=(676*26+26*8+12)mod11＝9h(ouy)=(676*15+26*21+25)mod11=8h(lwj)=(676*12+26*23+10)mod11=8h2＝（8+2*2）mod11＝1h(yks)=(676*25+26*11+19)mod11=1h2＝（1+2*2）mod11＝5h(lxz)=(676*12+26*24+26)mod11=6h(suy)=(676*19+26*21+25)m

3、od11=6h2＝（6+2*2）mod11＝10h(hls)=(676*8+26*12+19)mod11＝8h2＝（8+2*2）mod11＝1h3＝（8+2*3）mod11＝3二、某虚拟存储器的用户编程空间共32个页面，每页为1KB，内存为16KB。假定某时刻一用户页表中已调入内存的页面对应的物理块号如下表：则逻辑地址0A5C（H）所对应的物理地址为：125C答：0A5C＝0000,1010,0101,1100页号为2，对应块号为4，有：物理地址：0001，0010,0101,1100即：125C三、分页式存储空间的分配由于块的大小是固定的，可以用一张位示图来构成主存分配表。现

4、设主存有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变化成物理地址。【参考答案

5、】因为有32个页面：虚地址中高5位为页号；由于有1KB页长，所以虚地址中低10位为页内地址。0A5C=000101001011100虚页号为2，物理页号为4000101001011100ð001001001011100=125C0D3C=000110100111100虚页号为3，物理页号为7000110100111100ð001111001011100=1F3C四、有两个用户进程A和B，在运行过程中都要使用系统中的一台打印机输出计算结果。(1)试说明A、B两进程之间存在什么样的制约关系？(2)为保证这两个进程能正确地打印出各自的结果，请用信号量和P、V操作写出各自的有关申请、使

6、用打印机的代码。要求给出信号量的含义和初值。答：（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号柱面，请按下列算法分别计算为完成上述各次访问总共花费的寻找时间

7、。（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台。若