计算机操作系统 作业答案.doc

第一章作业1.1. 设计现代OS的主要目标是什么?方便性，有效性，可扩充性和开放性. 1.2. OS的作用可表现为哪几个方面?a. OS作为用户与计算机硬件系统之间的接口；b. OS作为计算机系统资源的管理者；c. OS实现了对计算机资源的抽象. 第二章作业2.2. 试画出下面4条语句的前趋图:S1: a:=x+y; S2: b:=z+1; S3: c:=a-b; S4: w:=c+1; S1 其中，语句S3必须在语句S1和语句S2都执行S4S3后才能执行，这样S2语句 S4也只能在c赋值后才能执行。对应的前驱图如右所示：2.6. 试从动态性，并发性和独立性上比较进程和程序?a. 动态性是进程最基本的特性，可表现为由创建而产生，由调度而执行，因得不到资源而暂停执行，以及由撤销而消亡，因而进程由一定的生命期；而程序只是一组有序指令的集合，是静态实体。b. 并发性是进程的重要特征，同时也是OS的重要特征。引入进程的目的正是为了使其程序能和其它建立了进程的程序并发执行，而程序本身是不能并发执行的。c. 独立性是指进程实体是一个能独立运行的基本单位，同时也是系统中独立获得资源和独立调度的基本单位。而对于未建立任何进程的程序，都不能作为一个独立的单位来运行。第三章作业3.2. 为什么进程在进入临界区之前应先执行“进入区”代码？而在退出前又要执行“退出区”代码？2. 如何利用Test-and-set指令来实现互斥？它有何缺点？为了实现多个进程对临界资源的互斥访问，必须在临界区之前加一段用于检查临界资源是否正在被访问的代码，如未被访问，该进程可进入临界区对此临界资源进行访问；如正被访问，则该进程不能进入临界区访问临界资源。在退出临界区后，执行恢复访问标志的代码为“退出区”，而在退出前执行“退出区”代码主要是为了使其它进程能再访问此临界资源。3.4. 如何利用Test-and-set指令来实现互斥？它有何缺点？Test-and-set指令是一种借助于一条硬件指令，即测试并建立指令TS（Test-and-set）来实现互斥的方法。利用TS实现进程互斥：每个临界资源设置一个公共布尔变量lock，初值为FALSE在进入区利用TS进行检查：有进程在临界区时，重复检查；直到其它进程退出时，检查通过。所有要访问临界资源的进程的进入区和退出区代码都是相同的。缺点：利用硬件指令能有限实现进程互斥，但不能满足让权等待的准则，造成处理器时间的浪费，而且也很难用于解决较复杂的进程同步问题。3.7. 如何利用信号量机制来实现多个进程对临界资源的互斥访问？并举例说明。为了使多个进程能互斥访问某临界资源，只需为该资源设置一互斥信号量mutex,并设其初始值为1，用于表示临界资源未被访问，然后将各进程访问该资源的临界区CS置于wait(mutex)和signal(mutex)操作之间即可。这样，每个欲访问该临界资源的进程，在进入临界区之前，都要先对mutex执行wait操作，若该资源此刻未被访问（mutex的值为1），本次wai操作必然成功，进程便可以进入自己的临界区。这时，若有其他进程也想进入自己的临界区，由于对mutex执行wait操作定会失败（mutex的值已为-1），因而该进程被阻塞，从而保证了该临界资源能被互斥地访问。举例：Var mutex:semaphore:=1；beginparbeginprocess 1: begin repeat wait(mutex)； critical section signal(mutex)； remainder seetion until false； end process 2: begin repeat wait(mutex)； critical section signal(mutex)； remainder section until false； end parend3.8. 试写出相应的程序来描述图2-17所示的前驱图。 a. Var a, b, c, d, e, f, g, h; semaphore:= 0, 0, 0, 1, 0, 0, 0, 0; begin parbegin begin S1; signal(a); signal(b); end; begin wait(a); S2; signal(c); signal(d); end; begin wait(b); S3; signal(e); end; begin wait(c); S4; signal(f); end;begin wait(d); S5; signal(g); end;begin wait(e); S6; signal(h); end;begin wait(f); wait(g); wait(h); S7; end; parend end b. Var a, b, c, d, e, f, g, h, i, j; semaphore:= 0, 0, 0, 0, 0, 0, 0, 0, 0, 0; begin parbegin begin S1; signal(a); signal(b); end; begin wait(a); S2; signal(c); signal(d); end; begin wait(b); S3; signal(e); signal(f); end; begin wait(c); S4; signal(g); end;begin wait(d); S5; signal(h); end;begin wait(e); S6; signal(i); end;begin wait(f); S7; signal(j); end;begin wait(g); wait(h); wait(i); wait(j); S8; end; parend end3.11. 为某临界资源设置一把锁W，当W=1时表示关锁；当W=0时表示锁已打开，试写出开锁和关锁原语，并利用它们去实现互斥。 整型信号量：lock(W): while W=1 do no-op W:=1; unlock(W): W:=0; 记录型信号量：lock(W): W:=W+1; if(W1) then block(W.L) unlock(W): W:=W-1; if(W0) then wakeup(W.L) 例子： Var W:semaphore:=0； begin repeat lock(W); critical section unlock(W); remainder section until false; end3.13. 试利用记录型信号量写出一个不会出现死锁的哲学家进餐问题的算法。（课堂练习）Var chopsiick array of semaphore：=（1,1,1,1,1）；prosessi repeat think； Sswait(chopstick(i+1)mod 5, chopsticki)； Eat； Ssignal(chopstick(i+1)mod 5, chopsticki) until false;第四章作业4.1. 高级调度与低级调度的主要任务是什么？为什么要引入中级调度？高级调度的主要任务：用于决定把外存上处于后备队列中的哪些作业调入内存，并为它们创建进程，分配必要的资源，然后，再将新创建的进程插入就绪队列上，准备执行。低级调度的主要任务：用于决定就绪队列中的哪个进程应获得处理机，然后再由分派程序执行将处理机分配给该进程的具体操作。引入中级调度的主要目的：是为了提高系统资源的利用率和系统吞吐量。4.12. 试比较FCFS和SPF两种进程调度算法相同点：两种调度算法都是既可用于作业调度，也可用于进程调度；不同点：FCFS调度算法每次调度都是从后备队列中选择一个或是多个最先进入该队列的作业，将它们调入内存，为它们分配资源，创建进程，然后插入到就绪队列中。该算法有利于长作业/进程，不利于短作业/进程。 SPF调度算法每次调度都是从后备队列中选择一个或若干个估计运行时间最短的作业，将它们调入内存中运行。该算法有利于短作业/进程，不利于长作业/进程。4.13.在时间片轮转法中，如何确定时间片的大小？a系统对响应时间的要求；b就绪队列中进程的数目；c系统的处理能力。4.30.在银行家算法的例子中，如果P0发出的请求向量由Request0(0,2,0)改为Request0(0,1,0),问系统可否将资源分配给它?可以。首先，Request0(0,1,0)=Need0(7,4,3), Request0(0,1,0)=Available(2,3,0);分配后可修改得一资源数据表(表略),进行安全性检查，可以找到一个安全序列P1,P4,P3,P2,P0,或P1,P4,P3,P0,P2,因此，系统是安全的，可以立即将资源分配给P0. 4.31. 在银行家算法中，若出现下述资源分配情：ProcessAllocationNeedAvailableP0003200121622P110001750P213542356P303320652P400140656试问： 该状态是否安全？ 若进程P2提出请求Request(1，2，2，2)后，系统能否将资源分配给它？该状态是安全的，因为存在一个安全序列。下表为该时刻的安全序列表。资源情况进程WorkNeedAllocationWork+AllocationFinishP0P3P4P1P21 6 2 21 6 5 41 9 8 71 9 9 112 9 9 110 0 1 20 6 5 20 6 5 61 7 5 02 3 5 60 0 3 20 3 3 30 0 1 41 0 0 01 3 5 41 6 5 41 9 8 71 9 9 112 9 9 113 12 14 17truetruetruetruetrue 若进程P2提出请求Request(1，2，2，2)后，系统不能将资源分配给它，若分配给进程P2，系统还剩的资源情况为（0，4，0，0），此时系统中的资源将无法满足任何一个进程的资源请求，从而导致系统进入不安全状态，容易引起死锁的发生。第五章作业5.11令buddyk(x)表示大小为2k地址为x的块的伙伴系统地址，试写出buddyk(x)的通用表达式。令buddyk(x)表示大小为2k地址为x的块的伙伴系统地址，则buddyk(x)的通试为：伙伴系统又称为堆分配系统5.21在分页系统中是如何实现地址变化的? 利用地址变换机构实现从逻辑地址到物理地址的转变换，通过页表来实现从页号到物理块号的变换，将逻辑地址中的页号转换为内存中的物理块号。第六章作业6.6. 在请求分页系统中，其页表项中包含那些数据项? 它们的作用是什么?a. 在请求分页系统中，其页表项中包含的数据项有页号，物理块号，状态位P，访问字段A，修改位M和-外存地址；b. 其中状态位P指示该页是否调入内存，供程序访问时参考；c. 访问字段A用于记录本页在一段时间内被访问的次数，或最近已有多长时间未被访问，提供给置换算法-选择换出页面时参考；d. 修改位M表示该页在调入内存后是否被修改过；e. 外存地址用于指出该页在外存上的地址，通常是物理块号，供调入该页时使用. 6.13在一个请求分页系统中，采用FIFO页面置换算法时，假如一个作业的页面走向为4、3、2、1、4、3、5、4、3、2、1、5，当分配给该作业的物理块数M分别为3和4时，试计算在访问过程中所发生的缺页次数和缺页率，并比较所得结果。4 3 2 1 4 3 5 4 3 2 1 5M=3M=44441115553334442222233314444555511333344445222233331111222M=3时，采用FIFO页面置换算法的缺页次数为9次，缺页率为75%；M=4时，采用FIFO页面置换算法的缺页次数为10次，缺页率为83%。由此可见，增加分配给作业的内存块数，反而增加了缺页次数，提高了缺页率，这种现象被称为是Belady现象。6.15. 试说明改进型Clock置换算法的基本原理。基本原理：在将一个页面换出时，如果该页已被修改过，便须将该页重新写回到磁盘上；但如果该页未被修改过，则不必将它写回磁盘上。在改进型算法中，除需考虑页面的使用情况外，还须再增加一个因素，即置换代价，这样，选择页面换出时，既要是未使用过的页面，又要是未被修改过的页面。第八章作业8.1. 何谓数据项、记录和文件？a.数据项是最低级的数据组织形式，可分为基本数据项和组合数据项。基本数据项是用于描述一个对象某种属性的字符集，是数据组织中可以命名的最小逻辑数据单位，即原子数据，又称为数据元素或字段。组合数据项则由若干个基本数据项构成。b.记录是一组相关数据项的集合，用于描述一个对象某方面的属性。C.文件是指有创建者所定义的、具有文件名的一组相关信息的集合提。8.7. 按文件的物理结构，可将文件分为哪几类？按文件的物理结构，可将文件分为三类：（1）顺序文件，指把逻辑文件中的记录顺序地存储到连续的物理盘块中；（2）链接文件，指文件中的各个记录可以存放在不相邻的各个物理块中，但通过物理块中的链接指针，将它们链接成一个链表；（3）索引文件，指文件中的各个记录可以存放在不相邻的各个物理块中，但通过为每个文件建立一张索引表来实现记录和物理块之间的映射关系。8.12 试说明关于索引文件和索引顺序文件的检索方法。对索引文件进行检