单道程序情况下，CPU和设备利用率均为多道程序情况下，CPU和设备利用率均为

内核支持线程是在内核支持下实现的，即每个线程的线程控制块设置在内核中，所有对线程的操作(如创建、撤销和切换等)，都是通过系统功能调用由内核中的相应处理程序完成。而用户级线程仅存在于用户空间中，即每个线程的控制块设置在用户空间中，所有对线程的操作也在用户空间中完成，而无需内核的帮助。
   可从以下几个方面比较内核支持线程和用户级线程：
   (1)内核支持。用户级线程可在一个不支持线程的OS中实现，而内核支持线程则不然，它需要得到OS内核的支持。
   (2)处理器的分配。在多处理机环境下，对纯粹的用户级线程来说，内核一次只为一个进程分配一个处理机，即进程无法享用多处理机带来的好处。而在设置有内核支持线程时，内核可调度一个应用中的多个线程同时在多个处理机上并行运行，从而提高程序的执行速度和效率。
   (3)调度和线程执行时间。对设置有内核支持线程的系统，其调度方式和算法与进程的调度相似，只不过调度的单位是线程。而对只设置了用户级线程的系统，调度的单位则仍为进程。因此，在条件相同的情况下，内核支持的线程通常比用户级线程得到更多的CPU执行时间。
   (4)切换速度。用户级线程的切换，通常发生在一个应用程序的多个线程之间，由于不需陷入内核，而且切换的规则也相当简单，因此切换速度比内核支持线程至少快一个数量级。
   (5)系统调用。在典型的OS中，许多系统调用都会引起阻塞。当一个用户级线程执行这些系统调用时，被阻塞的将是整个进程。而当一个内核支持线程执行这些系统调用时，内核只阻塞这个线程，但仍可调度其所属进程的其他线程执行。

线程可定义为进程内的一个执行单位，或者定义为进程内的一个可调度的实体。
   在具有多线程机制的操作系统中，处理机调度的基本单位不是进程而是线程。一个进程可以有多个线程，而且至少有一个可执行的线程。
   进程和线程的关系是：
   (1)线程是进程的一个组成部分；
   (2)进程的多线程都在进程的地址空间活动；
   (3)资源是分给进程的，而不是分给线程的，线程在执行中需要资源时，系统从进程的资源配额中扣除并分配给它；
   (4)处理机调度的基本单位是线程，线程之间竞争处理机，真正在处理机上运行的是线程；
   (5)线程在执行过程中，需要同步。

执行一条命令或一个应用程序时，进程和程序之间形成一对一的关系；进程在执行过程中可以加载执行不同的应用程序，从而形成一对多的关系；当以不同的参数或数据多次执行同一个应用程序时，形成多对一的关系；当并发地执行不同的应用程序时，形成多对多的关系。

[解析] 从进程的概念、进程与程序之间的关系来考虑问题的解答。进程是程序的执行过程，进程代表执行中的程序，因此进程与程序的差别就隐含在“执行”之中。程序是静态的指令集合，进程是程序的动态执行过程。静态的程序除占用磁盘空间外，不需要其他系统资源，只有执行中的进程才需要分配内存、CPU等系统资源。
   进程的定义说明了两点：
   (1)进程与程序相关，进程包含了程序。程序是进程的核心内容，没有程序就没有进程。
   (2)进程不仅仅是程序，还包含了程序在执行过程中使用的全部资源，没有资源程序就无法执行，因此。进程是执行程序的载体。
   当运行一个程序时，操作系统首先要创建一个进程，为进程分配内存等资源，然后将程序加载到进程中执行。就单个进程某个时刻而言，一个进程只能执行一个程序，进程和程序之间是一对一的关系。但从整个系统中的进程集合以及进程的生命周期而言，进程和程序之间可以形成一对一、一对多、多对一、多对多的关系。

每个进程有自己独立的地址空间。在操作系统和硬件的地址保护机制下，进程无法访问其他进程的地址空间，所以必须借助于操作系统的系统调用函数实现进程之间的通信。进程通信的主要方式有：
   (1)共享内存区：通过系统调用创建共享内存区。多个进程可以(通过系统调用)连接同一个共享内存区，通过访问共享内存区实现进程之间的数据交换。使用共享内存区时需要利用信号量解决同步互斥问题。
   (2)消息传递：通过发送/接收消息系统调用实现进程之间的通信。当进程发送消息时，系统将消息从用户缓冲区拷贝到内核中的消息缓冲区中，然后将消息缓冲区挂入消息队列中。进程发送的消息保持在消息队列中直到被另一进程接收。当进程接收消息时，系统从消息队列中解挂消息缓冲区，将消息从内核的消息缓冲区中拷贝到用户缓冲区，然后释放消息缓冲区。
   (3)管道通信：管道是一个先进先出(FIFO)的信息流，允许多个进程向管道写入数据，允许多个进程从管道读出数据。在读/写过程中，操作系统保证数据的写入顺序与读出顺序是一致的。进程通过读/写管道文件或管道设备实现彼此之间的通信。
   (4)共享文件：利用操作系统提供的文件共享功能实现进程之间的通信。这时，也需要利用信号量解决文件共享操作中的同步互斥问题。

[解析] 在操作系统中，进程是竞争和分配计算机系统资源的基本单位。每个进程有自己独立的地址空间。为了保证多个进程能够彼此互不干扰地共享物理内存，操作系统利用硬件地址机制对进程的地址空间进行了严格的保护，限制每个进程只能访问自己的地址空间。

进程是程序的执行过程，是竞争和分配计算机系统资源的基本单位。线程是进程中的一个程序执行单元。一个进程可以包含多个线程，进程中的程序可以由多个线程并发地执行，因此线程是进程中的并发执行机制。进程中的多个线程共享进程的地址空间和其他资源。线程和进程之间的最大区别是它们的运行、管理和通信开销。创建进程需要建立进程的地址空间，而线程不需要，因为它共享进程的地址空间。在处理机调度过程中，进程切换包括切换CPU执行现场和进程地址空间，而同一进程下的线程切换只需要切换CPU执行现场。由于共享进程的地址空间，同一进程下的线程之间可以直接进行数据交换，不需要调用操作系统的内核通信函数。
   多线程并行程序适用于共享存储结构的多处理机系统(SMP)，因为这类系统能够很好地支持线程对进程地址空间和资源的物理共享，而多进程并行程序适用于松散耦合的多处理机系统。

[解析] 需要了解和掌握线程、进程的基本概念以及它们之间的关系。操作系统为了支持多道程序的运行和管理，引入了进程概念和进程管理机制。为了加快应用程序的执行速度，提出了并行程序的设计思想。将一个大的应用程序或大作业分解成若干个能够并行处理的子任务，由执行主程序的进程创建多个子进程，每个子进程执行一个子任务。利用进程的并发性，使得多个子进程的I/O过程与CPU计算过程相互重叠，从而提高处理机利用率，加快应用程序的运行速度。
   在多处理机系统中，为了进一步提高并行程序的运行效率。引入了线程概念和线程管理机制。线程是进程中的一个程序执行单元。线程包含CPU执行线程和执行堆栈，可以独立地执行程序。进程中的程序可以由多个线程并发地执行，进程中的多个线程共享进程的地址空间和其他资源，包括程序、数据、文件、通信端口等。正是由于线程对进程的地址空间和资源的共享，明显地减少了并行开销(包括线程创建、切换和通信)，非常有利于并行程序的开发和运行。

阻塞到运行状态是不可能的，因为必须经就绪状态；就绪到阻塞状态是不可能的；就绪到退出状态也是不可能的，中间必须经过执行状态。

第1种情况是因为进程完成I/O后，需要提高优先级，这是一种照顾I/O为主进程的策略；后4种情况均是因为它们长时间没有得到运行的机会，需要提高优先级，这是一种典型的动态优先级策略。

线程并行相对于进程并行可以降低上下文的切换开销。

多CPU的调度依赖于操作系统内核的调度，而ULT不能影响操作系统的调度策略，因此不能实现真正的并行。

提高并行执行的程度。

死锁检测方法可以获得最大并发性。并发性排序：死锁检测方法、银行家算法、资源预分配法。

饥饿是系统并没有死锁，但至少有一个进程被无限期地推迟的现象。饥饿不同于死锁。死锁是这样一种情形：其中某进程正等待一个绝不会发生的事件；而饥饿现象是指某进程正等待这样一个事件：它发生了但总是受到其他进程的影响，以致一直轮不到(或很难轮到)该进程。

因为就像进程队列的平均长度为5，单个RR调度循环周期的时间为：
   4×100+1×400=800(ms)
   A类进程需要20个时间片的执行时间，B类进程需要5个时间片的执行时间(1s=1000ms)。A类进程的平均周转时间为：20×0.8=16(s)
   B类进程的平均周转时间为：5×0.8=4(s)

[解析] 时间片轮转调度(RR)是轮流地调度就绪队列中的每个进程，进程每次占用CPU的时间长度限制为时间片的大小。当采用固定的时间片大小时，每个进程按照固定周期被循环地执行。所以，进程的执行速度是由该进程的时间片大小在一个循环周期中所占的比例决定的，比例越高，进程的相对执行速度就越快。

根据“可抢占的最高优先级”调度算法画出进程P1、P2、P3的工作过程。(如下图所示)
   
   进程P₁、P₂、P₃从开始到完成所用的时间分别是90ms、110ms、80ms。这三个进程从开始到全部完成时的时间为110ms，在此期间内：
   CPU的利用率=(30+20+10+10)÷110=63.3%
   IO₁的利用率=(20+30+40)÷110=81.8%
   IO₂的利用率=(30+20+10)÷110=54.5%

[解析] 在“可抢占的最高优先级”调度中，任何时刻内核都将处理机分配给当前最高优先级的就绪进程。也就是说，只有当高优先级进程主动放弃CPU时，低优先级进程才有机会运行，并且，一旦高优先级进程需要使用CPU时，内核就会剥夺低优先级进程的CPU，分配给它使用。
   在本题中，由于进程P₁和P₂在开始执行时先需要进行I/O，所以最低优先级的进程P₃获得了CPU。但是，P₃运行了20ms后就被P₂抢占了CPU，因为P₂刚好完成了I/O，并且P₂的优先级大于P₃。同样的原因，P₂运行了10ms后，就被P₁抢占了CPU。P₁在CPU上运行10ms之后再次需要进行I/O而放弃CPU，于是，P₂、P₁获得继续运行的机会。以此方式，P₁、P₂和P₃相继完成自己的运行过程。

进程进入“阻塞”状态，是因为进程需要等待某种资源。当进程获得资源时，进程被唤醒，变成“就绪”状态。这时提高该进程的优先级可以使进程尽快地完成慢速设备的I/O过程。这样，一方面提高了I/O设备的利用率，另一方面，设备的I/O活动能够与CPU执行其他进程的计算工作充分地并行，从而提高整个系统的性能。

[解析] 在操作系统中，多个进程共享系统的资源必然发生资源的竞争。进程在运行过程中，如果需要使用的资源(如I/O设备)正被其他进程占用，该进程就会进入“阻塞”状态，等待资源的释放。如果某种资源的使用时间比较长(例如慢速的I/O设备)，就会发生许多进程等待该资源的情况，而CPU时常处于空闲状态。这时，慢速的I/O设备成为阻碍系统性能的瓶颈。提高设备的利用率和提高设备与CPU的并行度是解决瓶颈问题的方法之一。

通过使用标志牌flag[0]和flag[1]能够保证满足“互斥”条件。但是，当两个进程按照①②③④的顺序执行程序时，它们各自举起标志牌，同时都因为观察到对方也举起了标志牌而等待在while语句中。由于两个进程都不会放下自己的标志牌，因此都无法进入临界区，不能满足“有限等待”的条件。所以，上述解决双进程临界区问题的算法是错误的。

[解析] 在算法中，两个进程P₁和P₂各自拥有自己的标志牌flag[0]和flag[1]。当进程需要进入临界区时，举起标志牌(设置值为true)。然后观察对方是否举起标志牌，是则等待并继续观察(while语句)，直到对方放下标志牌(设置值为false)。这时，进程才进入临界区。进程退出临界区时，放下标志牌(设置值为false)。

(M-N，M)；N-M。

[解析] 信号量s及其P操作、V操作具有资源管理的内涵：
   s＞0：表示有s个资源可用。
   s=0：表示无资源可用。
   s＜0：表示有|s|个进程在等待资源。
   P(s)：表示申请一个资源。
   V(s)：表示释放一个资源。
   信号量必须置一次且只能置一次初值。互斥信号量的初值为1，同步信号量的初值为0，代表多个资源的信号量的初值为正整数，即为可用的资源总数。
   在本题中，允许M个进程同时进入它们的共享区，可以看作有M个可用的资源总数。信号量s的最大值是可用资源总数M，最小值是当N个进程都需要使用共享区时的值，这时有|M-N|个进程需要等待进入共享区。

①P(nonf1)    ②V(none1)    ③P(s1)    ④V(s1)
   ⑤P(none2)    ⑥P(s2)       ⑦V(s2)    ⑧V(nonf2)

[解析] 信号量及其P操作、V操作是解决同步、互斥问题的常用方法。在应用信号量时必须注意两点：
   (1)对信号量只能执行P操作、V操作，且P操作、V操作必须成对出现：当实现互斥时，它们出现在同一进程中；当实现同步时，则出现在不同的进程中。
   (2)同步P操作与互斥P操作在一起时，同步P操作应该放在互斥P操作之前。
   本题是一个生产/消费者类型的同步互斥问题。有两组生产者和消费者，利用不同的缓冲区进行操作。第1组生产者和消费者是输入进程和加工进程，第2组生产者和消费者是加工进程和输出进程。在生产者进程与消费者进程之间存在一种同步关系：生产者不能往“满”的缓冲区中放产品，必须等待消费者取走产品之后(第1个同步点)；消费者亦不能从“空”的缓冲区中取产品，必须等待生产者放入产品之后(第2个同步点)。也就是说，在生产者和消费者的程序中，需要使用两个信号量实现上述两个同步点。另外，还需要实现对缓冲区buf1和buf2互斥访问。
   从列出的程序中可以看出，信号量s1和s2分别用于实现对缓冲区buf1和buf2互斥访问；none1和nonf1用于实现输入进程和加工进程之间的同步，none2和nonf1用于实现加工进程和输出进程之间的同步。

产品A与产品B的入库过程如下：
   Semaphore:Sa,Sb,mutex;
   Sa=m-1;Sb=n-1;mutex=1;
   process_A() {
   While(1) {
   P(Sa);
   P(mutex);
   A产品入库;
   V(mutex);
   V(Sb);
   }
   }
   Process_B() {
   While(1) {
   P(Sb);
   P(mutex);
   B产品入库;
   V(mutex);
   V(Sa);
   }
   }

[解析] 这也是一个生产/消费者类型的同步互斥问题。这里有两个生产者：生产者A放入产品A，生产者B放入产品B，但没有或不考虑消费者。根据本题所给的条件，找出生产者A、B之间的相互制约关系。
   条件1：生产者A和B必须互斥地使用仓库。
   条件2：若只放入A产品，而不放入B产品，则A产品最多可放M-1次便被阻塞。即表示可放入A产品数目的计数器初值为M-1，A进程每放入一个产品就应当将计数器减1，当计数器值为0时，进程A被阻塞；每当放入一个B产品，则可令A产品的计数器增1，表明A进程可以多一次放入产品的机会。
   条件3：若只放入B产品，而不放入A产品，则B产品最多可放N-1次便被阻塞。即表示可放入B产品数目的计数器初值为N-1，B进程每放入一个产品就应当将计数器减1，当计数器值为0时，进程B被阻塞；每当放入一个A产品，则可令B产品的计数器增1，表明B进程可以多一次放入产品的机会。
   因此，需要使用信号量mutex控制两个进程互斥访问临界资源(仓库)。使用同步信号量Sa和Sb(分别代表产品A和产品B的入库计数器)满足条件2和条件3。

程序示意如下：
   Semaphore:S1,S2,mutex;
   int:num1,num2;
   S1=1;S2=1;mutex=1;num1=0;num2=0;
   Process_A() {
   P(S1);
   num1=num1+1;
   if(num1==1) then P(mutex);
   V(S1);
   读文件P;
   P(S1);
   num1=num1-1;
   if(num1==0) then V(mutex);
   V(S1);
   }
   Process_B() {
   P(S2);
   Num2=num2+1;
   if(num2==1) then P(mutex);
   V(S2);
   读文件P;
   P(S2);
   Num2=num2-1;
   if(num2==0) then V(mutex);
   V(S2);
   }

[解析] 这是一个读者/写者类型的同步互斥问题。有A、B两组读者，但没有写者。两组读者相互竞争对文件P的读权限，而读权限在同组进程之间是共享的，因此，在到达临界区(即“读文件P”)的同组进程中，由第一个到达进程负责竞争临界区的入场券(即“读权限”)，由最后一个离开进程负责释放临界区的入场券。因此需要使用一个互斥信号量mutex，实现A、B两组读者互斥地进入临界区。
   为了确定第一个到达的进程和最后一个离开的进程，需要定义两个计数器num1和num2，分别记录A组和B组中需要或正在读文件P的进程数。计数器在同组进程之间是共享资源，需要互斥地访问。因此，每组进程需要使用一个互斥信号量(S1、S2)，保证对计数器进行正确的并发操作。

设置4个信号量：
   S：代表桥的互斥使用的信号量，初值为1；
   Scounteast：代表由东向西方向的车辆计数器的互斥使用的信号量，初值为1；
   Scountwest：代表由西向东方向的车辆计数器的互斥使用的信号量，初值为1；
   Scount4：代表桥上车辆计数器的信号量，初值为4。
   算法如下：
   Semaphore:S,Scounteast,Scountwest,Scount4;
   int Counteast,Countwest;
   S=1;Scounteast=1;Scountwest=1;Scount4=4;
   Counteast=0;
   Countwest=0;
   Program_east() {
   P(Scounteast);
   if(Counteast==0) then P(S);
   Counteast=Counteast+1;
   V(Scounteast);
   P(Scount4);
   过桥:
   V(Scount4);
   P(Scounteast);
   Counteast=Counteast-1;
   if(Counteast==0) then V(S);
   V(Scounteast);
   {
   Program_west() {
   P(Scountwest);
   if(Countwest==0) then P(S);
   Countwest=Countwest+1;
   V(Scountwest);
   P(Scount4);
   过桥:
   V(Scount4);
   P(Scountwest);
   Countwest=Countwest-1;
   if(Countwest==0) then V(S);
   V(Scountwest);
   }

[解析] 这也是一个读者/写者类型的同步互斥问题。有两组读者或写者：从东向西的车流和从西向东的车流。共享的资源是可双向通行的单车道简易桥，即双向过桥的车辆对桥的使用是互斥的，同方向上允许有多辆车辆同时过桥，但是同时过桥的车辆数目不能大于4辆。因此，可以按照通常的读者/写者问题进行处理，但在同组读者使用资源的过程中需要增加信号量的控制，以满足最大载重负荷为4辆汽车的条件。

在资源分配系统中，死锁发生的原因是因为多个进程共享优先的独占型资源。当多个进程占有了部分资源又需要更多的资源时，就可能形成循环等待链而导致死锁。
   假设系统中的某种资源的个数为M，共享该资源的进程数为N，每个进程对该资源的最大需求量为X。最极端的资源分配情况是，每个进程都已经占有了X-1个资源，同时都需要再分配一个资源。这时，如果要保证不发生死锁，系统中必须至少还有一个可分配的资源。即M满足下面的关系式：
   M≥N(X-1)+1
   因此，保证系统不会发生死锁的最小M值可以从下面的公式获得：
   M=N(X-1)+1
   将M=5，X=2代入公式，可得N=4。即至多允许出现4个进程参与资源竞争。

首先计算每个进程的剩余需求量，也就是在占有部分资源的基础上还需要多少资源。列表如下：
   
   然后，分别计算系统现有的资源量能否满足进程P₁(P₂或P₃)的当前请求量以及满足之后的安全序列。
   P₁的申请被阻塞。因为满足了P₁的申请之后，P₁的剩余需求量为(0，1，3)，而系统的剩余资源量为(0，1，2)，无法继续满足任何进程的剩余需求量，因此不存在安全序列。
   P₂的申请被阻塞。因为申请数量超出了系统现有的资源数量。
   P₃的申请可以满足。因为满足了P₃的申请之后，P₃的剩余需求量为(0，1，1)，而系统的剩余资源量为(0，1，1)，可以继续满足P₃的剩余需求量。可以计算出安全序列＜P₃，P₂，P₁＞或＜P₃，P₁，P₂＞。

[解析] 在分配资源时确保系统处于安全状态，这是一种保守的死锁避免方法。银行家算法就是这样一种资源分配方法。算法的基本思想是：在分配资源时，检查系统中是否存在一个安全序列＜P₁，P₂，…，P_n＞，使得系统按照这个序列分配现有的资源，可以保证所有进程P_i能够运行结束。也就是说，用系统现有的资源满足P₁的全部资源需求，使得P₁能够运行结束并释放所占用的资源；用系统现有资源加上P₁释放的资源满足P₂的全部资源需求，使得P₂能够运行结束并释放所占用的资源；用系统现有资源加上P₁和P₂释放的资源满足P₃的全部资源需求，最终使所有进程运行结束。
   在本题中，应用银行家算法判断，如果满足了进程P₁(P₂或P₃)的资源请求，系统是否存在安全序列。