操作系统课程作业答案.pdf

第一次作业 复习题 1.2 定义处理器寄存器的两种主要类别 用户可见寄存器：优先使用这些寄存器，可以使机器语言或者汇编语言的程 序员减少对主存储器的访问次数。对高级语言而言，由优化编译器负责决定把哪 些变量应该分配给主存储器。一些高级语言，如 C 语言，允许程序言建议编译器 把哪些变量保存在寄存器中。 控制和状态寄存器：用以控制处理器的操作，且主要被具有特权的操作系统例 程使用，以控制程序的执行。 习题 1.6 内存层次的各个元素间的特征是什么？ a)CPU 定期检查 FGI.如果 FGI1，CPU 将把数据接收后，被储存在 INPR 里面，PR 里面的内容传送至 AC，并把 FGI 置为 0. 当 CPU 需要传送数据到打 字机时，它会检查 FGO.如果 FGO0，CPU 处于等待.如果 FGO 1，CPU 将 把 AC 的内容传送至 OUTER 并把 FGO 置为 0.当数字符号打印后，打字机将把 FGI 置为 1. b)在 a 描述的过程非常浪费.速度远高于打字机的 CPU 必须反复不断的检查 FGI 和 FGO.如果中 断被使用， 当打字机准备接收或者发送数据时， 可以向 CPU 发出一个中断请求.IEN 计数器可以由 CPU 设置（在程序员的控制下）. 复习题 2.1 操作系统设计的三个目标 方便 Convenience：操作系统使计算机更易于使用. 有效 Efficiency：操作系统允许以更有效的方式使用计算机系统资源. 扩展的能力 Ability to evolve：在构造操作系统时，应该允许在不妨碍服务的 前提下有效地开发、测试和引进新的系统功能. 复习题 2.9 解释单体内核和微内核的区别 单体内核（single kernel）是一个提供操作系统应该提供的功能的大内核， 包 括调度、文件系统、网络、设备驱动程序、存储管理等。内核的所有功能成分都 能够访问它的内部数据结构和程序。典型情况下，这个大内核是作为一个进程实 现的，所有元素都共享相同的地址空间。 微内核（ microkernel ）是一个小的有特权的操作系统内核，只提供包括进 程调度、内存管理、和进程间通信等基本功能，要依靠其他进程担当起和操作系 统内核联系作用。 习题 2.1 习题 2.3 a)简单批处理系统发展为多道批处理系统的原因 I/O 设备的时间相对于处理器速度太慢，在简单批处理系统中，一次只有一个程 序执行处理器大部分时间处于空闲， 效率低下。 多道批处理在多个程序之间切换， 同时处理多个批作业，可以使批处理变得更加有效。 b)多道批处理系统发展为分时系统的原因 分时系统给所有进程一个较短的处理时间，避免多道批处理系统中某 些作业占用处理器时间长而导致其他作业等待，有效减小响应时间。 第二次作业 Review Questions 1.For the processing model of Figure 3.6, briefly define each state. 新建 new：刚刚创建的进程，操作系统还没有把它加入到可执行进程组中。 就绪 ready：进程做好了准备，只要有机会就开始执行。 运行 running：该进程正在执行。 阻塞 blocked ：进程在某些事件发生前不能执行，如 I/O 操作完成。 退出 exit：进程从可执行进程组中释放。 2. List three general categories of information in a process control block. 1）进程标识信息 process identification 2）处理器状态信息 processor state information 3）进程控制信息 process control information 3. What are the steps performed by an OS to create a new process? 1）给进程分配一个唯一的进程标识符 Assign a unique process identifier to the new process. 2）给进程分配空间 Allocate space for the process. 3）初始化进程控制块 Initialize the process control block. 4）设置正确的连接 Set the appropriate linkages. 5）创建或扩充其他数据结构 Create or expand other data structures. 4. What is the difference between a mode switch and a process switch? 模式切换（ mode switch ）是指内核态与用户态之间的切换，发生模式切换可以 不改变当前正处于运行态的进程的状态。发生进程切换（ processswitch ）时， 一个正在执行的进程被中断，操作系统指定另一个进程为运行态。进程切换需要 保存更多的状态信息。 Problems 1. Consider a computer with N processors in a multiprocessor configuration. a. How many processes can be in each of the Ready, Running, and Blocked states at one time? b. What is the minimum number of processes that can be in each of the Ready, Running, and Blocked states at one time? a. 在就绪和阻塞状态的进程数量是没有限制的，只与内存用于存放不同状态进 程的空间有关。而执行中的进程最多有 N 个，每个处理器最多有一个进程在执 行。 b.如果所有进程都处于运行或者就绪态，没有处于阻塞状态的进程，这是可能 的。反过来，也有可能所有进程都处于阻塞状态，等待某个事件的发生，没有就 绪态和执行态的进程 2. Figure 3.9b contains seven states. In principle, one could draw a transition between any two states, for a total of 42 different transitions. a. List all of the possible transitions and give an example of what could cause each transition. b. List all of the impossible transitions and explain why. 3.In PINK89, the following states are defined for processes: Execute (running),Active (ready), Blocked, and Suspend. Aprocess is blocked if it is waiting for permission to use a resource, and it is suspended if it is waiting for an operation to be completed on a resource it has already acquired. In many operating systems, these two states are lumped together as the blocked state, and the suspended state has the definition we have used in this chapter. Compare the relative merits of the two sets of definitions. 假设一个进程已经执行了一段时间， 它需要一个额外的磁带设备来写出一个 临时文件。在它开始写磁带之前，进程必须得到使用某一设备的许可。当它做出 请求时，磁带设备可能并不可用，这种情况下，该进程就处于阻塞态（blocked） 。 假设操作系统在某一时刻将磁带设备分配给了该进程， 这时进程就重新变为活跃 态。 当进程重新变为执行态时要对新获得的磁带设备进行写操作。这时进程变为 挂起态（suspend） ，等待该磁带上当前所进行的写操作完成。 这种对等待某一 设备的两种不同原因的区别，在操作系统组织其工作时是非常有用的。然而这并 不能表明哪些进程是换入的，哪些进程是换出的。后一种区别是必需的，而且应 该在进程状态中以某种形式表现出来。 第三次作业 1.Table 3.5 lists typical elements found in a process control block for an unthreaded OS. Of these, which should belong to a thread control block and which should belong to a process control block for a multithreaded system? 这对于不同的系统来说通常是不同的，但一般来说，进程是资源的所有者， 而 每个线程都有它自己的执行状态。 关于表 3.5 中的每一项的一些结论如下： 进程标识：进程必须被标识，而进程中的每一个线程也必须有自己的 ID。 处理器状态信息：这些信息通常只与进程有关。 进程控制信息：调度和状态信息主要处于线程级；数据结构在两级都可出现； 进程间通信和线程间通信都可以得到支持；特权在两级都可以存在；存储管理通 常在进程级；资源信息通常也在进程级。 2.List reasons why a mode switch between threads may be cheaper than a mode switch between processes. 线程转换（mode switch between threads）包含的状态信息更少。 3.It was pointed out that two advantages of using multiple threads within a process are that (1) less work is involved in creating a new thread within an existing process than in creating a new process, and (2) communication among threads within the same process is simplified. Is it also the case that a mode switch between two threads within the same process involves less work than a mode switch between two threads in different processes? 是的，因为线程转换包含更少的状态信息。 4.In the discussion of ULTs versus KLTs, it was pointed out that a disadvantage of ULTs is that when a ULT executes a system call, not only is that thread blocked, but also all of the threads within the process are blocked. Why is that so? 因为对于用户级线程来说，一个进程的线程结构对操作系统是不可见的，因为对于用户级线程来说，一个进程的线程结构对操作系统是不可见的， 而操作系统的调度是以进程为单位的。所以当一个线程被阻塞，和该线程而操作系统的调度是以进程为单位的。所以当一个线程被阻塞，和该线程 在同一个进程的所有线程都会被阻塞。在同一个进程的所有线程都会被阻塞。 5.Can a multithreaded solution using multiple user-level threads achieve betterperformance on a multiprocessor system than on a single processor system? Explain. 在 ULT 策略中，多线程的应用不能利用多处理器来提高性能。由于内核每次给每 个处理器分配一个进程，在处理器中只有进程的一个线程能执行。 第四次作业 Review Questions 1.What are three contexts in which concurrency arises? 多个应用程序，结构化应用程序，操作系统结构 Multiple applications, structured applications, operating-system structure. 2.What is the basic requirement for the execution of concurrent processes? 加强互斥的能力 The ability to enforce mutual exclusion. 3.List three degrees of awareness between processes and briefly define each. 进程间互相不知道对方 Processes unaware of each other：这是一些独立的进 程，他们不会一起工作。 进程间间接知道对方 Processes indirectly aware of each other：这些进程并不 需要知道对方的进程 ID 号，但他们共享访问某些对象，如一个 I/O 缓冲区。 进程间直接知道对方 Processes directly aware of each other： 这些进程可以通 过进程 ID 号互相通信，用于合作完成某些活动。 4.List the requirements for mutual exclusion. 1.必须强制实施互斥：在具有关于相同资源或共享对象的临界区的所有进程中， 一次只允许一个进程进入临界区。 2.一个在临界区停止的进程必须不干涉其他进程。 3.绝不允许出现一个需要访问临界区的进程被无限延迟的情况，即不会饿死或 饥饿。 4.当没有进程在临界区中时，任何需要进入临界区的进程必须能够立即进入。 5.对相关进程的速度和处理器的数目没有任何要求和限制。 6.一个进程驻留在临界区中的时间是有限的。 5.What operations can be performed on a semaphore? 1）一个信号量可以初始化成非负数。 2）wait 操作使信号量减 1，如果值为负数，那么进程执行 wait 就会受阻。 3）signal 操作使信号量增加 1，如果小于或等于 0，则被 wait 操作阻塞的进程被 解除阻塞。 Problems 1. What are three contexts in which concurrency arises? Consider a concurrent program with two processes, p and q, defined as follows. A, B,C, D, and E are arbitrary atomic (indivisible) statements. Assume that the main program (not shown) does a parbegin of the two processes. void p() void q() A; D; B; E; C; Show all the possible interleavings of the execution of the preceding two processes ABCDE;ABDCE;ABDEC;ADBCE;ADBEC;ADEBC;DEABC;DAEBC;DABEC;DA BCE; 2. Is busy waiting always less efficient (in terms of using processor time) than a blocking wait? Explain. 就一般情况来说是对的,因为忙等待消耗无用的指令周期.然而,有一种特殊情况, 当进程执行到程序的某一点处,在此处要等待直到条件满足,而正好条件已满足, 此时忙等待会立即有结果,然而阻塞等待会消耗操作系统资源在换出与换入进程 上. 3. Now consider a version of the bakery algorithm without the variable choosing. Then we have int numbern; while (true) numberi = 1 + getmax(number, n); for (int j = 0; j =0。换句 话说，如果 SPN 运算法则没被采用，平均反应时间只会增加。 9.16 Five batch jobs,Athrough E, arrive at a computer center at essentially the same time. They have an estimated running time of 15, 9, 3, 6, and 12 minutes, respectively. Their (externally defined) priorities are 6, 3, 7, 9, and 4 respectively, with a lower value corresponding to a higher priority. For each of the following scheduling algorithms, determine the turnaround time for each process and the average turnaround for all obs. Ignore process switching overhead. Explain how you arrived at your answers. In the last three cases, assume that only one job at a time runs until it finishes and that all jobs are completely processor bound. a. round robin with a time quantum of 1 minute b. priority scheduling c. FCFS (run in order 15, 9, 3, 6, and 12) d. shortest job first 第九次作业 10.2 List and briefly define four techniques for thread scheduling. 加载共享：进程不是分配到一个特定的处理器，而是维护一个就绪进程的全 局队列，每个处理器只要空闲就从队列中选择一个线程。这里使用术语加载 共享来区分这种策略和加载平衡方案，加载平衡是基于一种比较永久的分配 方案分配工作的。 组调度： 一组相关的线程基于一对一的原则， 同时调度到一组处理器上运行。 专用处理器分配：在程序执行过程中，每个程序被分配给一组处理器，处理 器的数目与程序中的线程的数目相等。当程序终止是，处理器返回到总的处 理器池中，可供分配给另一个程序。 动态调度：在执行期间，进程中线程的数目可以改变。 Load sharing: processes are not assigned to aparticular processor. Aglobal queue of ready threadsis maintained,and eachprocessor, whenidle, selects a thread from the queue. Gangscheduling:a setof relatedthreads is scheduled torun on aset of processors atthe same time, ona one-to-one basis. Dedicated processorassignment: eachprogram is allocated anumber ofprocessors equal tothe number of threads in the program, for the duration of the programexecution (this is the opposite ofthe load-sharing approach) Dynamic scheduling: the application is responsible for assigning its threads toprocessors. It may alter the number ofthreads during the course of execution. 10.5 What is the difference between periodic and aperiodic real-time tasks? 非周期任务有一个必须结束或开始的最后期限， 或者有一个关于开始时间和结束 时间的约束。而对于周期任务，这个要求描述成“每隔周期 T 一次”或“每隔 T 个 单位”。 A periodic real-time task is any task where there is a set amount of time allocated to a regularly repeated task whereas an aperiodic task is any task that occurs from a randomly occurring event. 10.1 Consider a set of three periodic tasks with the execution profiles of Table 10.5 Develop scheduling diagrams similar to those of figure 10.5 for this set of tasks. ProcessArrival TimeExecution TimeEnding Deadline A(1)01020 A(2)201040 B (1)01050 B (2)5010100 C (1)01550 C (2)5015100 Arrival times, execution times, and deadlines Fixed-priority scheduling: Ahas priority Fixed-priority scheduling: B has priority Fixed-priority scheduling: C has priority A1 DeadlineA2 Deadline B1 DeadlineB2 Deadline C1 DeadlineC2 Deadline A1A2 B1B2 C1C2 0102030405060708090100 A1B1A2C1B2C2 A1A2B1, C1B2, C2 B1A1C1A2B2C2 A1A2B1, C1B2, C2 C1A1 B1A2C2B2 A1A2B1, C1B2, C2 (Missed) Earliest deadline scheduling using completion deadling 10.2 Consider a set of five aperiodic tasks with the execution profiles of Table 10.6 Develop scheduling diagrams similar to those of Figure 10.6 for this set of tasks. ProcessArrival TimeExecution TimeStarting Deadline A1020100 B202030 C402060 A1B1A2C1B2C2 A1A2B1, C1B2, C2 D502080 E602070 Requirement Arrival times Starting Deadline Earliest deadline Arrival times Service Starting deadline Earliest deadline with unforced idle time Arrival times Service Starting deadline First-come first-served (FCFS) 0102030405060708090 100 ABCDE BCEDA 0102030405060708090 100 ABCDE ABCE BCED(missed)A 0102030405060708090100110120 ABCDE BCEDA BCEDA 0102030405060708090 100 ABCDE ABCD Arrival times Service Starting deadline 第十次作业 BCE(missed) DA Review Questions 11.2 What is the difference between logical I/O and device I/O? 逻辑 I/O：逻辑 I/O 模块把设备当作一个逻辑资源来处理，它并不关心实 际控制设备的细节。逻辑 I/O 模块代表用户进程管理的一般 I/O 功能， 允 许它们根据设备标识符以及诸如打开、关闭、读、写之类的简单命令与设 备打交道。 设备 I/O： 请求的操作和数据 （缓冲的数据、 记录等） 被转换成适当的 I/O 指令序列、通道命令和控制器命令。可以使用缓冲技术，以提高使用率。 11.3 What is the difference between block-oriented devices and stream-oriented devices? Give a few examples of each. 面向块的设备将信息保存在块中，块的大小通常是固定的，传输过程中一 次传送一块。 通常可以通过块号访问数据。 磁盘和磁带都是面向块的设备。 面向流的设备以字节流的方式输入输出数据，其末使用块结构。终端、 打 印机通信端口、鼠标和其他指示设备以及大多数非辅存的其他设备，都属 于面向流的设备。 11.4 Why would you expect improved performance using a double buffer rather than a single buffer for I/O? 双缓冲允许两个操作并行处理，而不是依次处理。典型的，在一个进程往 一个缓冲区中传送数据（从这个缓冲区中取数据）的同时，操作系统正在 清空（或者填充）另一个缓冲区。 Problems 11.3 a. Perform the same type of analysis as that of Table 11.2 for the following sequence of disk track requests: 27, 129, 110, 186, 147, 41, 10, 64, 120.Assume that the disk head is initially positioned over track 100 and is moving in the direction of decreasing track number. b. Do the same analysis, but now assume that the disk head is moving in the direction of increasing track number. a FIFOSSTFSCANC-SCAN 下 一 个 被 访 问 的磁道 27 129 110 186 147 41 10 64 120 平 均 寻 道长度 横 跨 的 磁道数 73 102 19 76 39 106 31 54 56 61.8 下 一 个 被 访 问 的磁道 110 120 129 147 186 64 41 27 10 平 均 寻 道长度 横 跨 的 磁道数 10 10 9 18 39 122 23 14 17 29.1 下 一 个 被 访 问 的磁道 64 41 27 10 110 120 129 147 186 平 均 寻 道长度 横 跨 的 磁道数 36 23 14 17 100 10 9 18 39 29.6 下 一 个 被 访 问 的磁道 64 41 27 10 186 147 129 120 110 平 均 寻 道长度 横 跨 的 磁道数 36 23 14 17 176 39 18 9 10 38 b如果磁头沿着增大的方向，只有 SCAN 和 C-SCAN 的结果有变化 SCANC-SCAN 下一个被 访问的磁 道 110 12