第3章 处理器管理
(1) 为什么程序并发执行会产生间断性特征，并失去封闭性和可再现性？
解：
之所以产生间断性特征是因为多个程序在并发执行时，需要为了完成同一项任务而相互合作，并发执行的程序间的这种相互制约导致了“暂停—执行—暂停”的间断性运行规律。
失去封闭性是因为程序在并发执行时，多个程序需要共享系统中的多种资源。所以，这些资源的状态是由多个程序改变的，从而使程序的运行失去了封闭性。
失去可再现性是因为程序在并发执行时，由于失去了封闭性，从而导致其失去可再现性。 (2) 什么是进程？为什么要在操作系统中引入进程？
解：
进程是可并发执行且具有独立功能的程序在一个数据集合上的运行过程，它是操作系统进行资源分配和调度的基本单位。“进程”概念是人们为了使程序能够并发执行，并且能对并发的程序加以描述和控制而引入的。
(3) 试从并发性、独立性、动态性上比较程序和进程的不同。
解：
? 并发性是进程的重要特征，同时也是OS 的重要特征。引入进程的目的正是为了
使其程序能和其它进程的程序并发执行，而程序是不能并发执行的。 ? 独立性是指进程实体是一个能独立运行的基本单位，同时也是系统中独立获得资
源和独立调度的基本单位。而对于未建立任何进程的程序，都不能作为一个独立的单位参加运行。
? 动态性是进程最基本的特性，可表现为由创建而产生，由调度而执行，因得不到
资源而暂停执行，以及由撤销而消亡，因而进程有一定的生命期；而程序只是一组有序指令的集合，是静态实体。
(4) 什么是PCB？它具有什么作用？为什么说PCB是进程存在的唯一标识？
解：
进程控制块(Process Control Block，PCB)是操作系统为了管理进程而设置的一个专门的数据结构，用它来记录进程的外部特征，描述进程的运动变化过程。
它的作用是使一个在多道程序环境下不能独立运行的程序(含数据)，成为一个能独立运行的基本单位，一个能和其它进程并发执行的进程.
因为系统利用PCB来控制和管理进程，所以PCB是系统感知进程存在的唯一标志。进程与PCB是一一对应的。
(5) 进程有哪些基本状态？这些状态具有什么特征？
解：
进程的三种基本状态分别是：就绪状态、运行状态、阻塞状态。
? 就绪状态：进程已获取到除CPU之外的所有必要资源，只要再得到CPU，就可
以马上投入运行。
? 运行状态：处于就绪状态的进程被调度程序选中后将得到CPU控制权，此时该
进程就可以使用处理器进行数据运算和处理。 ? 阻塞状态：当一个进程正在等待某个事件的发生(如等待I/O的完成)而暂停执行，
这时，即使分配有CPU时间，它也无法执行。
(6) 为什么要引入挂起状态？该状态有什么特性？
解：
引入挂起状态时为了满足四种需要：调节系统负荷的需要、用户的需要、父进程的需要、系统的需要。
挂起状态的特点：交换到磁盘上的进程，不让其参与进程调度，以达到平衡系统负荷的目的。
(7) 说明进程基本状态的转换关系及引起这些状态间转换的典型原因。
解：
处于就绪状态的进程，在调度程序为之分配了处理器之后，就可以投入运行。同时，进程的状态也由就绪状态转变为运行状态；在采用时间片机制的操作系统中，分配给当前进程的时间片用完之后，它会暂停执行，其状态也由运行状态转换到就绪状态；如果由于某事件发生(比如进程需要访问某I/O设备，而该设备正在被别的进程访问)而使进程运行受阻，不能再继续向下执行时，它的状态会由运行状态转变为阻塞状态；当进程期望的某事件发生时(比如需要访问的I/O设备已可用)，进程将从阻塞状态转变为就绪状态
(8) 说明在加入了挂起状态的操作系统中，进程状态间的转换关系及引发转换的典型原因。
解：
在引入挂起状态的操作系统中，又增加了静止就绪和静止阻塞两个新的进程状态。调用挂起原语把处于活动就绪状态的进程挂起后，该进程就会由活动就绪状态转变为静止就绪状态。调用挂起原语把处于活动阻塞的进程挂起后，它的状态就转换为静止阻塞。调用激活原语激活后又可以转换到活动阻塞状态。 (9) 试说明引起进程创建的典型事件。
解：
引起进程创建的典型事件有：用户登录、作业调度、提供服务、应用请求。 (10) 试说明引起进程撤销的典型事件。
解：
引起进程撤销的典型事件有：正常结束、异常结束、外界干预。 (11) 试说明引起进程阻塞和唤醒的典型事件。
解：
引起进程阻塞和唤醒的典型事件有：请求系统服务、启动某种操作、新数据尚未到达、无新工作可做。.
(12) 试说明进程创建的过程。
解：
创建进程的操作必须调用创建原语来实现。创建原语首先为新进程申请获得惟一的数字标示符，并从PCB集合中获取一个空白PCB；为新进程的程序和数据以及用户栈分配必要的内存空间；然后对PCB进程初始化；最后将新进程插入就绪队列中，等待被调度执行。 (13) 试说明进程撤销的过程。
解：
系统调用进程终止原语来终止进程。首先根据被终止进程的标示符，从PCB集合中查找到该进程的PCB，从中读出该进程的状态，终止该进程的执行，如果该进程还有子孙进程，应该将它的所有子孙进程终止，防止它们成为不可控进程；然后回收进程所拥有的资源；最后将被终止进程(它的PCB)从所在队列(或链表)中移出，等待其它程序来搜集信息。 (14) 什么是线程？请比较它与进程的异同。
解：
线程是进程中的一个实体，是被系统独立分配和调度的基本单位。线程基本上不拥有资源，只需要一些必不可少的资源(如程序计数器、一组寄存器和栈)。
进程和线程的差异：
1. 在传统的OS中，进程是拥有资源和独立调度分派的基本单位，在加入线程的OS
中，线程是代替进程成为独立调度和分派的基本单位，进程则仍是拥有资源的基本单位。
2. 并发粒度不同。除了不同进程的线程之外，同一个进程里的不同线程之间也可以并
发执行，所以线程拥有更好的并发性。 3. 拥有资源数量不同。进程是拥有资源的基本单位，线程除了一些在运行过程中必不
可少的资源外，基本上不拥有系统资源，它可以访问自己所在的进程的资源。 4. 管理开销不同。创建、撤销进程时系统都要为之分配和回收资源，所以进程切换用
的时间开销相对要多于线程。进程间通信很麻烦，而同一进程的线程则通过共享进程的资源很方便地通信和同步，同步开销小得多。
进程和线程有着很多相似的地方：都可以并发执行；都有就绪、执行、阻塞这些基本状态，也都可以在这些基本状态之间转换状态；从创建到撤销都有一定的生命周期；都需要同步工具。
(15) 处理器调度的层次有哪些？各层次的主要工作是什么？
解：
处理器调度的层次分为三级调度：高级调度、中级调度和低级调度。
? 高级调度：它需要做出两个决定，一个是要从驻留在外存后备队列中调入多少个
作业，二是要调入哪几个作业；然后为被选中的作业创建进程，并分配必要的系统资源，如内存、外设等，然后把新创建的进程放入就绪队列中，等待被调度执行。
? 中级调度：中级调度主要涉及进程在内存和外存之间的交换。当系统中的内存使
用情况紧张时，中级调度把内存中暂时不能运行的进程调到外存中等待，等内存有足够的空闲空间时，再由中级调度决定将外存上的某些具备了运行条件的就绪进程调入内存，把其状态修改为就绪状态并挂在就绪队列中，等待进程调度。 ? 低级调度：按照一定的算法从就绪队列中选择一个进程，然后将处理器分配给它。
执行低级调度功能的程序称作进程调度程序，由它实现处理器在进程间的切换。
(16) 抢占式调度的原则是什么？请简要说明。
解：系统使用抢占方式进行进程调度时需要遵循一定的原则，主要有以下几个方面： 1. 时间片原则。各进程按系统分配给的一个时间片运行，当该时间片用完或由于该进
程等待某事件发生而被阻塞时，系统就停止该进程的执行而重新进行调度。 2. 优先级原则。每个进程均被赋于一个调度优先级，通常一些重要和紧急的进程被赋
于较高的优先级。当一个新的紧迫进程到达时，或者一个优先级高的进程从阻塞状态变成就绪状态时，如果该进程的优先级比当前进程的优先级高，OS就停止当前进程的执行，将处理器分配给该优先级高的进程，使之执行。 3. 短进程优先原则。当新到达的作业对应的进程比正在执行的作业对应进程的运行时
间明显短时，系统剥夺当前进程的执行，而将处理器分配给新的短进程，使之优先执行。
(17) 在批处理系统、分时系统、实时系统中，应分别采用哪种作业(进程)调度算法？
解：
批处理系统采用先来先服务调度算法；分时系统采用时间片轮转法；实时系统采用高响应比优先调度算法。
(18) 说明时间片轮转调度算法的基本思路。
解：
在采用时间片轮转调度算法的系统中，将系统中所有的就绪进程按照FCFS原则，排成一个队列。每次调度时将CPU分派给队首进程，让其执行一个时间片。时间片的长度从几个ms到几百ms。在一个时间片结束时，发生时钟中断。调度程序暂停当前进程的执行，将其送到就绪队列的末尾，并通过CPU现场切换执行当前的队首进程，当然，进程可以未使用完一个时间片，就让出CPU(如阻塞)。这样可以保证就绪队列中的所有进程都有机会获得处理器而运行的机会，可以提高进程并发性和响应时间特性，从而提高资源利用率。 (19) 试说明多级反馈队列调度算法思想。
解：多级反馈队列调度算法则不必事先知道各进程的执行时间，又可以满足各种类型进程的调度需要，它是一种目前公认较好的进程调度算法。它的算法思想如下(设采用抢占式调度)：
1. 需要设置多个就绪队列，并且为它们分别赋予不同的优先级。每队列分配不同的时
间片，规定优先级越低则时间片越长。
2. 新进程就绪后，先插入队列1的末尾，按FCFS算法调度。若一个时间片未能执行
完，则降低插入到队列2的末尾；依此类推，降低到最后的队列，则按“时间片轮转”算法调度直到完成。
3. 进程由于等待事件而放弃CPU后, 进入等待队列, 一旦等待的事件发生, 则回到原
来的就绪队列。
4. 只有当较高优先级的队列为空时，才调度较低优先级队列中的进程执行。如果进程
执行时有新进程进入较高优先级的队列，则需要重新调度，抢先执行新进程，并把被抢先的进程插入原队列的末尾。
(20) 什么是静态和动态优先级？如何确定静态优先级？
解：
静态优先级是在系统创建时确定的，一经确定之后在整个进程运行期间不再改变。 动态优先级是在进程运行前先确定一个优先级，进程运行过程中根据进程等待时间的长短、执行时间的多少、输入输出信息量的大小等，通过计算得到新的优先级。
(21) 在一个单道批处理系统中，一组作业的到达时间和运行时间如下表所示。试计算使用先来先服务、短作业优先、高响应比优先算法时的平均周转时间和平均带权周转时间。
作业 1 2 3 4 到达时间 8.0 8.5 9.0 9.1 运行时间 1.0 0.5 0.2 0.1 解：
用T表示周转时间，用W表示带权周转时间 FCFS的作业调度情况如下： 作业 1 2 3 4 提交时间 8.0 8.5 9.0 9.1 运行时间 1.0 0.5 0.2 0.1 开始时间 8.0 9.0 9.5 9.7 结束时间 9.0 9.5 9.7 9.8 周转时间 1.0 1.0 0.7 0.7 带权周转时间 1.0 2.0 3.5 7.0 FCFS的T =（1.0+1.0+0.7+0.7）/ 4 = 0.85 W =（1.0+2.0+3.5+7.0）/ 4 =3.375
SJF的作业调度情况如下： 作业 1 2 3 4 提交时间 8.0 8.5 9.0 9.1 运行时间 1.0 0.5 0.2 0.1 开始时间 8.0 9.3 9.0 9.2 结束时间 9.0 9.8 9.2 9.3 周转时间 1.0 1.3 0.2 0.2 带权周转时间 1.0 2.6 1.0 2.0 SJF的T=（1.0+1.3+0.2+0.2）/ 4 = 0.675 W =（1.0+2.6+1.0+2.0）/ 4 = 1.65 高响应比优先的作业调度情况如下： 作业 1 2 3 4 提交时间 8.0 8.5 9.0 9.1 运行时间 1.0 0.5 0.2 0.1 开始时间 8.0 9.0 9.6 9.5 结束时间 9.0 9.5 9.8 9.6 周转时间 1.0 1.0 0.8 0.5 带权周转时间 1.0 2.0 4.0 5.0 高响应比算法的T=（1.0+1.0+0.8+0.5）/ 4 = 0.825 W =（1.0+2.0+4.0+5.0）/ 4 = 3.0 (22) Linux进程有几个状态，简述各状态的转换条件。
解：1)运行状态2) 可中断睡眠状态 3)不可中断睡眠状态4)暂停状态 5)跟踪状态 6)僵死状态 7)退出状态
进程创建时的状态为不可中断睡眠状态，在do_fork()结束前被父进程唤醒后，变为执行状态，适当时候获得CPU。 获得CPU且正在运行的进程若申请不到某个资源时，进入睡眠状态，如果调用sleep_on()，则其状态变为不可中断睡眠状态，如果调用interruptible_sleep_on()，则其状态变为可中断睡眠状态，当进程获取所申请的资源时，睡眠进程进入运行状态。当系统调用do_exit()时，进程进入僵死状态。若进程通过系统调用设置标志PF_SYSTRACE，则在系统调用返回前进入函数syscall_trace()，状态改为暂停。只有通过其他进程发送的信号SIG_KILL或SIG_CONT，才能把暂停状态进程唤醒，重新进入run-queue队列。
(23) Linux中的线程调度算法有几种，简述之？
解：调度策略有三种：
(1)SCHED_OTHER(普通分时调度策略)：它是缺省调度策略，适用于优先级为0的线程，它为链表中的每个线程分配时间片，保证链表中的每个线程有公平的执行时间。
(2)SCHED_FIFO(先进先出调度策略)：适用于优先级高于0的线程，当SCHED_FIFO中有可运行线程时，该线程会抢先任何当前运行的SCHED_OTHER线程称为当前运行线程。当有优先级更高的线程抢先时，该进程保留在对应链表的头部，在高优先级线程结束后立即投入运行。
(3)SCHED_RR(循环调度策略)：它是SCHED_FIFO策略的简单增强，增加了时间片限制。如果某个SCHED_RR 运行的线程等于或超过分配给它时间片，结束运行，排到对应链表的尾部。
第3章习题答案 (2)
