操作系统第八章.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)，t11，li为键n的第i个英文字母序号。键表长11，键名为英文字母。按线性散列法计算将任意7个键放入链表中所用的计算次数。这里令a2，c1。解：设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 119 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 111 h(yks)=(676*25+26*11+19) mod 11=1 h2（1+2*2） mod 115 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 1110 h(hls)=(676*8+26*12+19) mod 118 h2（8+2*2）mod 111 h3（8+2*3）mod 113二、某虚拟存储器的用户编程空间共32个页面，每页为1KB，内存为16KB。假定某时刻一用户页表中已调入内存的页面对应的物理块号如下表：则逻辑地址0A5C（H）所对应的物理地址为 ：125C答：0A5C0000,1010,0101,1100 页号为2，对应块号为4，有：物理地址：0001，0010,0101,1100 即：125C三、分页式存储空间的分配由于块的大小是固定的，可以用一张位示图来构成主存分配表。 现设主存有8192 块，则可用字长为32 位的256 个字作为位示图。若块号、字号、位号 （从高位到低位）都是从0 开始，试问4999 块对应的字号和位号；129 字的29 位对应 哪一块？ 答：【参考答案】依题目所给条件，已知位示图如下所示： 499932=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转化为相应的物理地址。页号物理块号02132l36本题中，为了描述方便，设页号为P，页内位移为D，则：对于逻辑地址1011；PINT(10111024)=0；D=1011 mod 1024=1011 ； 查页表第0页在第2块，所以物理地址为3059。对于逻辑地址2148；PINT(21481024)=2；D2148 mod 1024100查页表第2页在第1块，所以物理地址为11240 ；对于逻辑地址4000；PINT(40001024)=3；D=4000 mod 1024928；查页表第3页在第6块，所以物理地址为7072。对于逻辑地址5012；P=INT(50121024)=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产品数量进程间的相互制约关系有三类，一是读者之间允许同时读；二是读者与写者之间必须互斥；三是写者之间须互斥写。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);ENGWriter:BEGINP(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 endCP:begin repeatP(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 falseendOP:begin repeat p(full2);P(mutex2);Take a charactor from buffer2;Add to printer controler;start printer;V(mutex2);V(empty2); until falseend二十一、系统中有五个进程P1、P2、P3、P4、P5，有三种类型的资源：R1、R2、和R3。在T0时刻系统状态如表所示。若采用银行家算法实施死锁避免策略，回答下列问题： （共9分，每小题3分）1 T0时刻是否为安全状态？为什么？2 若这时P4请求资源（1，2，0），