答：进程中线程是相互协作的，而不是相互独立的。如果放弃了是为了应用程序，那么线程将放弃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算法呢？