习题

1.图2-2中给出了三个进程状态。在理论上,三个状态可以有六种转换,每个状态两个。但是,图中只给出了四种转换。有没有可能发生其他两种转换中的一个或两个?

2.假设要设计一种先进的计算机体系结构,它使用硬件而不是中断来完成进程切换。CPU需要哪些信息?请描述用硬件完成进程切换的工作过程。

3.在所有当代计算机中,至少有部分中断处理程序是用汇编语言编写的。为什么?

广告:个人专属 VPN,独立 IP,无限流量,多机房切换,还可以屏蔽广告和恶意软件,每月最低仅 5 美元

4.当中断或系统调用把控制转给操作系统时,通常将内核堆栈和被中断进程的运行堆栈分离。为什么?

5.多个作业能够并行运行,比它们顺序执行完成的要快。假设有两个作业同时开始执行,每个需要10分钟的CPU时间。如果顺序执行,那么最后一个作业需要多长时间可以完成?如果并行执行又需要多长时间?假设I/O等待占50%。

6.在本章中说明的图2-11a的模式不适合用于使用内存高速缓存的文件服务器。为什么不适合?每个进程可以有自己的高速缓存吗?

7.如果创建一个多线程进程,若子进程得到全部父进程线程的副本,会出现问题。假如原有线程之一正在等待键盘输入,现在则成为两个线程在等待键盘输入,每个进程有一个。在单线程进程中也会发生这种问题吗?

8.在图2-8中,给出了一个多线程Web服务器。如果读取文件的惟一途径是正常的阻塞read系统调用,那么Web服务器应该使用用户级线程还是内核级线程?为什么?

9.在本章中,我们介绍了多线程Web服务器,说明它比单线程服务器和有限状态机服务器更好的原因。存在单线程服务器更好一些的情形吗?请给出一个例子。

10.在图2-12中寄存器集合按每个线程中的内容列出而不是按每个进程中的内容列出。为什么?毕竟机器只有一套寄存器。

11.为什么线程要通过调用thread_yield自愿放弃CPU?毕竟,由于没有周期性的时钟中断,线程可以不交回CPU。

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

13.在本习题中,要求对使用单线程文件服务器和多线程文件服务器读取文件进行比较。假设所需要的数据都在块高速缓存中,花费15ms获得工作请求,分派工作,并处理其余必要工作。如果在三分之一时间时,需要一个磁盘操作,要另外花费75ms,此时该线程进入睡眠。在单线程情形下服务器每秒钟可以处理多少个请求?如果是多线程呢?

14.在用户空间实现线程,其最大的优点是什么?最大的缺点是什么?

15.在图2-15中创建线程和线程打印消息是随机交织在一起的。有没有方法可以严格按照以下次序运行:创建线程1,线程1打印消息,线程1结束;创建线程2,线程2打印消息,线程2结束;以此类推。如果有,是什么方法,如果没有请解释原因。

16.在讨论线程中的全局变量时,曾使用过程create_global将存储分配给指向变量的指针,而不是变量自身。这是必需的,还是由于该过程也需要使用这些值?

17.考虑线程全部在用户空间实现的一个系统,其中运行时系统每秒钟得到一个时钟中断。假设在该运行时系统中,当某个线程正在执行时发生一个时钟中断,此时会出现什么问题?你有什么解决该问题的建议吗?

18.假设一个操作系统中不存在类似于select的系统调用来提前了解在从文件、管道或设备中读取时是否安全,不过该操作系统确实允许设置报警时钟,以便中断阻塞的系统调用。在上述条件下,是否有可能在用户空间中实现一个线程包?请加以讨论。

19.在2.3.4节中所讨论的优先级反转问题是否可能在用户级线程中发生?为什么?

20.在2.3.4节中,描述了一种有高优先级进程H和低优先级进程L的情况,导致了H陷入死循环。若采用轮转调度算法而不是优先级调度算法,还会发生同样问题吗?请给予讨论。

21.在使用线程的系统中,若使用用户级线程,是每个线程一个堆栈还是每个进程一个堆栈?如果使用内核级线程情况又如何呢?请给予解释。

22.在开发计算机时,通常首先用一个程序模拟,一次运行一条指令,甚至多处理器也严格按此模拟。在类似于这种没有同时事件发生的情形下,会出现竞争条件吗?

23.两个进程在一个共享存储器多处理器(即两个CPU)上运行,当它们要共享一个公共内存时,图2-23所示的采用变量turn的忙等待解决方案还有效吗?

24.在进程调度是抢占式的情形下,图2-24中展示的互斥问题的Peterson解法能正常工作吗?如果是非抢占式的情况呢?

25.给出一个可以屏蔽中断的操作系统如何实现信号量的框架。

26.请说明计数信号量(即可以保持一个任意值的信号量)如何仅通过二元信号量和普通机器指令实现。

27.如果一个系统只有两个进程,可以使用一个屏障来同步这两个进程吗?为什么?

28.如果线程在内核中实现,可以使用内核信号量对同一个进程中的两个线程进行同步吗?如果线程在用户空间实现呢?假设在其他进程中没有线程必须访问该信号量。请讨论你的答案。

29.管程内的同步机制使用条件变量和两个特殊操作wait和signal。一种更通用的同步形式是只用一条原语waituntil,它以任意的布尔谓词作为参数。例如


waituntil x<0 or y+z<n


这样就不再需要signal原语。很显然这一方式比Hoare或Brinch Hansen方案更通用,但它从未被采用过。为什么?提示:请考虑其实现。

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

31.假设有一个使用信箱的消息传递系统,当向满信箱发消息或从空信箱收消息时,进程都不会阻塞,相反,会得到一个错误代码。进程响应错误代码的处理方式为一遍一遍地重试,直到成功为止。这种方式会导致竞争条件吗?

32.CDC 6600计算机使用一种称作处理器共享的有趣的轮转调度算法,它可以同时处理多达10个I/O进程。每条指令结束后都进行进程切换,这样进程1执行指令1,进程2执行指令2,以此类推。进程切换由特殊硬件完成,所以没有开销。如果在没有竞争的条件下一个进程需要T秒钟完成,那么当有n个进程共享处理器时完成一个进程需要多长时间?

33.是否可以通过分析源代码来确定进程是CPU密集型的还是I/O密集型的?如何能在运行时刻进行此项决定?

34.在“何时调度”一节中曾提到,有时一个重要进程可以在选择下一个被阻塞进程进入运行的过程中发挥作用,从而改善调度性能。请给出可以这样做的情形并解释如何做。

35.对某系统进行监测后表明,当阻塞在I/O之前时,平均每个进程运行时间为T。一次进程切换需要的时间为S,这里S实际上就是开销。对于采用时间片长度为Q的轮转调度,请给出以下各种情况中CPU利用率的计算公式:

a)Q=∞

b)Q>T

c)S<Q<T

d)Q=S

e)Q趋近于0

36.有5个待运行作业,估计它们的运行时间分别是9,6,3,5和X。采用哪种次序运行这些作业将得到最短的平均响应时间?(答案将依赖于X。)

37.有5个批处理作业A到E,它们几乎同时到达一个计算中心。估计它们的运行时间分别为10,6,2,4和8分钟。其优先级(由外部设定)分别为3,5,2,1和4,其中5为最高优先级。对于下列每种调度算法,计算其平均进程周转时间,可忽略进程切换的开销。

a)轮转法。

b)优先级调度。

c)先来先服务(按照10,6,2,4,8次序运行)。

d)最短作业优先。

对a),假设系统具有多道程序处理能力,每个作业均公平共享CPU时间,对b)到d),假设任一时刻只有一个作业运行,直到结束。所有的作业都完全是CPU密集型作业。

38.运行在CTSS上的一个进程需要30个时间片完成。该进程必须被调入多少次,包括第一次(在该进程运行之前)?

39.能找到一个使CTSS优先级系统不受随机回车链愚弄的方法吗?

40.a=1/2的老化算法用来预测运行时间。先前的四次运行,从最老的一个到最近的一个,其运行时间分别是40ms,20ms,40ms和15ms。下一次的预测时间是多少?

41.一个软实时系统有4个周期时间,其周期分别为50ms,100ms,200ms和250ms。假设这4个事件分别需要35ms,20ms,10ms和x ms的CPU时间。保持系统可调度的最大x值是多少?

42.请解释为什么两级调度比较常用。

43.一个实时系统需要处理两个语音通信,每个运行5ms,然后每次突发消耗1ms CPU时间,加上25帧/秒的一个视频,每一帧需要20ms的CPU时间。这个系统是可调度的吗?

44.考虑一个系统,在这个系统中为了内核线程调度希望将策略和机制分离。请提出一个实现此目标的手段。

45.在哲学家就餐问题的解法(图2-46)中,为什么在过程take_forks中将状态变量置为HUNGRY?

46.考虑图2-46中的过程put_forks,假设变量state[i]在对test的两次调用之后而不是之前被置为THINKING。这个改动会对解法有什么影响?

47.按照哪一类进程何时开始,读者-写者问题可以有若干种方式求解。请详细描述该问题的三种变体,每一种变体偏好(或不偏好)某一类进程。对每种变体,请指出当一个读者或写者访问数据库时会发生什么,以及当一个进程结束对数据库的访问后又会发生什么?

48.请编写一个shell脚本,通过读取文件的最后一个数字,对之加1,然后再将该数字附在该文件上,从而生成顺序数文件。在后台和前台分别运行该脚本的一个实例,每个实例访问相同的文件。需要多长时间才出现竞争条件?临界区是什么?请修改该脚本以避免竞争(提示:使用In file file.lock锁住数据文件。)

49.假设有一个提供信号量的操作系统。请实现一个消息系统,编写发送和接收消息的过程。

50.使用管程而不是信号量来解决哲学家就餐问题。

51.假设一个大学为了卖弄其政治上的正确性,准备把美国最高法院的信条“平等但隔离其本身就是不平等(Separate but equal is inherently unequal)”既运用在种族上也运在性别上,从而结束校园内长期使用的浴室按性别隔离的做法。但是,为了迁就传统习惯,学校颁布法令:当有一个女生在浴室里,那么其他女生可以进入,但是男生不行,反之亦然。在每个浴室的门上有一个滑动指示符号,表示当前处于以下三种可能状态之一:

·空。

·有女生。

·有男生。

用你偏好的程序设计语言编写下面的过程:woman_wants_to_enter,man_wants_to_enter,woman_leaves,man_leaves。可以随意采用所希望的计数器和同步技术。

52.重写图2-23中的程序,以便能够处理两个以上的进程。

53.编写一个使用线程并共享一个公共缓冲区的生产者-消费者问题。但是,不要使用信号量或任何其他用来保护共享数据结构的同步原语。直接让每个线程在需要访问时就访问。使用sleep和wakeup来处理满和空的条件。观察需要多长时间会出现严重的竞争条件。例如,可以让生产者一会儿打印一个数字,每分钟打印不要超过一个数字,因为I/O会影响竞争条件。