现代操作系统--作业题整理 下载本文

答:进程中线程是相互协作的,而不是相互独立的。如果放弃了是为了应用程序,那么线程将放弃CPU。毕竟,通常是同一个程序员写的代码。(操作系统第二版中文答案)

12、线程可以被时钟中断抢占吗?如果可以,在什么情形下可以?如果不可以,为什么不可以?

答:用户级线程不能被时中断抢占,除非整个进程的时间片用完。内核级线程可以单独地被剥夺。在后一种情况下,如果线程运行过久,时钟将的中断当前的进程,因而当前线程也被中断。内核可以自由地从同一个进程中选取其他线程运行。(操作系统第二版中文答案) 20、在2.3.4节中,描述了一种有高级优先级进程H和低级优先级进程L的情况,导致了H陷入死循环。若采用轮换调度算法而不是优先级调度算法,会发生同样的问题吗?请给予讨论。

答:对于时间片轮转调度,该方法不会出现问题。L迟早会运行,而且最终将离开其临界区。对于优先级调度,L永远得不到运行;而对于时间片轮转,它将周期性地得到一时间片,因此就有机会离开其临界区。(操作系统第二版中文答案)

23、两个进程在一个共享存储器多处理器(即两个CPU)当它们要共享一个公共内存时,图2-23所示的采用变量turn的忙等待解决方案有效吗? 答:是的,它还是会有用的。当然,它依然是忙等待。(操作系统第二版中文答案) 27、如果一个系统只有两个进程,可以使用一个屏障来同步这两个进程吗?为什么? 答:如果程序是操作按阶段进行,直到两个进程都完成当前阶段才能进入下一个阶段,这时就应该使用屏障。(操作系统第二版中文答案) 28、如果线程在内核中实现,可以使用内核信号量对同一个进程中的两个线程进行同步吗?如果线程在用户空间安实现呢?假设在其他进程中没有线程必须访问该信号量。请讨论你的答案。

答:对于内核线程,线程可以在信号量上阻塞,而内核可以运行该进程中的其他线程。因而,使用信号量没有问题。而对于用户级线程,当某个线程在信号量上阻塞时,内核将认为整个进程都被阻塞。而且不再执行它。因此,进程失败。(操作系统第二版中文答案)

30、一个快餐店有四类雇员:(1)领班,接收顾客点的菜单;(2)厨师,准备饭菜;(3)打包工,将饭菜装在袋子里;(4)收银员,将食品袋交给顾客并收钱。每个雇员可被看作一个进行通讯的顺序进程。它们采用的进程间通信方式是什么?请将这个模型与UNIX中进程联系起来。

答:雇员之间通过消息传递进行通信:在该例中,消息为订单、食物和袋子。在UNIX中,该4个进程通过管道连接。(操作系统第二版中文答案)

1、为了使A、B两个进程互斥地访问单个缓冲区,应为之设置一个互斥信号量S,初值为1,相应在的P(S),V(S)操作必须分别安排在( )的两端。 A、该单缓冲区 B、两进程的临界区 C、两进程的程序段 D、两进程的控制块 2、一个进程可以包含多个线程,各线程( )

A、必须串行工作 B、共享分配给进程的主存地址空间 C、共享进程的PCB D、是独立的资源分配单位 3、PV操作所处理的变量是( )

A、锁变量 B、整型信号量 C、记录型信号量 D、控制变量 4、为了使两个进程能同步运行,最少需要( )个信号量。 A、1 B、2 C、3 D、4 5、共享变量是指( )访问的变量。

A、只能被系统进程 B、只能被多个进程互斥访问的变量 C、只能被用户进程 D、可被多个进程

6、临界区是指并发进程中访问共享变量的( )。

A、管理信息 B、数据 C、信息存储 D、程序 7、多项选择:线程是操作系统的概念,已具有线程管理的操作系统有( )。 A、WINDOWS32 B、OS/2 C、Windows NT D、DOS6.22 E、Mach

8、多项选择:一个进程向其他进程发送消息时,应组织好一封信件,内容包括( )。

A、接收者名 B、发送者名 C、具体信息 D、等不等回信标志 E、回信存放地址 9、在具有n个进程的系统中,允许m个进程(n≥m≥1)同时进入它们的临界区,其信号量S的值的变化范围是_________,处于等待状态的进程数最多________个。 10、线程与进程的根本区别是把进程作为______单位,而线程是_________单位。

答案:

1、B 2、B 3、B 4、B 5、B 6、D 7、BCE 8、BCDE

9、n-m≤S≤m n-m

10、资源分配 调度和执行

第三章:存储管理(P139)

2、交换系统通过紧缩来消除空闲区。假设有很多空闲区和数据段随机分布,并且读或写32位长的字需要10ns的时间,紧缩128MB大概需要多少长时间?为了简单起见,假设空闲区中含有字0,内存中最高地址处含有有效数据。

答:几乎整个内存都必须复制,也就是要求读出每一个内存字,然后重写到不同的位置。读4个字节需要10nsec,因此读1个字节需2.5nsec,而还要话费2.5nsec用于重写,因此,对于每个字节的压缩需要5nsec。其速率为200,000,000字节

/sec。为了复制128MB(2^27 字节,也就是大约1.34*10^8字节),该计算机需要2^27 / 200,000,000sec,也就是大约671msec。该数字是稍微悲观的因为如果内存地步的最初的空间为k字节,那么该k字节无需复制。不过,如果有许多空间和许多数据碎片,因此空洞将非常小,k也就非常小,而误差也非常小。(操作系统第二版中文答案)

3、请比较用位图和链表两种方法来记录空闲内存所需的存储空间。128MB的内存以n字节为单元分配。对于链表,假设内存中数据段和空闲区交替排列,长度均为64KB。并假设链表中的每个结点需要32位的内存地址、16位长度和16位下一个结点域。这两种方法分别需要多少字节的存储空间?哪种方法更好? 答:位图:128MB(2^27 字节)的内存以n字节为单元分配,则可以分成(128*2^20)/n = 2^27 /n 个单元,8个单元需要1字节的位图,即总需要 2^27 /8n字节的位图。所以记录内存需要的存储空间大小为:2^27 + 2^27 /8n = 2^27 (1 + 1/8n) 字节;

链表:128MB的内存可有(128MB/64KB = 2^11)个区域,一个节点需要(32 + 16 +16)/8 = 8 字节,所以记录内存需要的存储空间大小为:2^11 * 8 + 2^27 = 2^27 (1 +1/2^13 ) = 2^27 (1 +1/(8*2^10) );

当n < 2^10字节(即1KB)时,位图 > 链表,则使用链表;当n > 1KB时,位图 < 链表,则使用位图。

4、在一个交换系统中,按内存地址排列的空闲区大小是:10KB、4KB、20KB、18KB、7KB、9KB、12KB和15KB。对于连续的段请求:a)12KB,b)10KB,c)9KB。使用首次适配算法,将找出哪个空闲区?使用最佳适配、最差适配、下次适配算法呢? 答:首次适配:20KB,10KB,18KB; 最佳适配:12KB,10KB,9KB; 最差适配:20KB,18KB,15KB; 下次适配:20KB,18KB,9KB。(操作系统第二版中文答案)

7、考虑下面的C程序: int X[N];

int step = M;//M是某个预定义的常量

for(int i = 0;i < N;i +=step)X[i] = X[i] +1;

a)如果这个程序运行在一个页面大小为4KB且有64个TLB表项的机器上时,M和N取什么值会使得内层循环的每次执行都会引起TLB失效? b)如果循环重复很多遍,结果会和a)的答案相同吗?请解释。

答:a)M的最小值是4096,才能使内层循环的每次执行时都引起TLB失效,N的值只会影响到X的循环次数,与TLB失效无关。

b)M的值应该大于4096才能在内层循环每次执行时引起TLB失效,但现在N的值要大于64K,所以X会超过256KB。

10、假设一个机器有48位的虚拟地址和32位的物理地址。

a)假设页面大小是4KB,如果只有一级页表,那么在页表里有多少页表项?请解释。

b)假设同一系统有32个TLB表项,并且假设一个程序的指令正好能放入一个页,

并且该程序顺序地从数千个页的数组中读取长整型元素。在这种情况下TLB的效果如何? 答:a)

b)TLB访问的命中率达100%。在指令访问下一个页面之前读取数据的命中率是100%,一个4KB大小的页面包含1024个长整型数据,每访问1024个数据就会有一次TLB失效。

12、一个32位地址的计算机使用两级页表。虚拟地址被分成9位的顶级页表域、11位的二级页表域和一个偏移量,页面大小是多少?在地址空间中一共有多少个页面?

答:偏移量=32 - 9 - 11 = 12(位),所以页面大小为:2^12 = 4KB,页面数为:2^20。

13、假设一个32位虚拟地址被分成a、b、c、d四个域。前三个域用于一个三级页表系统,第四个域d是偏移量。页面数与这四个域的大小都有关系吗?如果不是,与哪些因素有关及与哪些因素无关?

答:页面数只依赖于a,b和c的和,至于它们之间是如何划分是无关的。(操作系统第二版中文答案)

19、一个计算机的页面大小为8KB,内存大小为256KB虚拟地址空间为64GB,使用倒排页表实现虚拟内存。为了保证平均散列链的长度小于1,散列表应该多大?假设散列表的大小为2的幂。

答:内存有2^28(256KB) / 2^13(8KB) = (2^15)32768页。32K的哈希表的平均链长为1。为了使之小于1,必须使用下一个尺寸(2^16)65536项。将32768项放入65536格中使其平均链长为0.5,以保证快速的查询。(操作系统第二版中文答案)

21、假设虚拟页码索引流中有一些长的页码索引序列的重复,序列之后有时会是一个随机的页码索引。例如,序列0,1,?,511,431,0,1,?,511,332,0,1,?中包含了0,1,?,511的重复,以及跟随在它们之后的随机页码索引431和332.

a)在工作负载比该序列短的情况下,标准的页面置换算法(LRU、Clock、FIFO)在处理换页时为什么效果不好?

b)如果一个程序分配了500个页框,请描述一个效果优于LRU、Clock或FIFO算法的页面置换方法。 答:a)标准的页面置换算法是针对已经在内存中的页面研究的。当工作负载比序列短时,会出现内存容量不够而长生颠簸,这种情况下LRU、Clock、FIFO算法达不到预期的效果。

b)如果分配了500个页框,那么0~498号页框是固定的,只有一个页框进行页面置换。

22、如果将FIFO页面置换算法4个页框和8个页面上,若初始时页框为空,访问字符串为0172327103,请问会发生多少次缺页中断?如果使用LRU算法呢?