1、一、选择题BDABD BCCBD ADBDD AABAD DCCAA CCDDD BCCDB C二、简答题1.线程可定义为进程内的一个执行单位，或者定义为进程内的一个可调度实体。 在具有多线程机制的操作系统中，处理机调度的基本单位不是进程而是线程。一个进程可以有多个线程，而且至少有一个可执行线程。进程和线程的关系是：(1)线程是进程的一个组成部分。(2)进程的多个线程都在进程的地址空间活动。(3)资源是分给进程的，而不是分给线程的，线程在执行中需要资源时，系统从进程的资源分配额中扣除并分配给它。(4)处理机调度的基本单位是线程，线程之间竞争处理机，真正在处理机上运行的是线程。(5)线程在执行过
2、程中，需要同步。2.唤醒进程和撤消进程都是要通过 CPU 上运行程序来实现的。一个进程入睡了，它就不可能被调度到 CPU 上运行；一个进程在撤消前必须先进入终止状态，而处于终止状态的进程不可能被调度到 CPU 上运行。因此，进程被唤醒、被撤消都不能由自己来完成，只能由别的进程实现。3.一个进程创建子进程之后，进程与产生的进程之间的关系是父子关系，分别成为进程和子进程。子进程一经产生就与你进程并发执行，子进程共享父进程和子进程。子进程一经产生就与你进程并发执行，子进程共享父进程的正文段和已经打开的文件。4.(1)以线程作为系统调度的基本单位，减少了系统的时空开销。以进程为系统调度的基本单位的系统
3、中，进程的切换是很频繁的。在切换中由于要保留当时的运行环境，还要设置新选中的进程的运行环境，这既花费了处理机的时间，又增加了主存的空间，从而也限制了系统进程的数量和进程的切换速度。(2)引进线程提高了系统的并行能力。线程作为进程内的一个可执行实体，减少了并行粒度。线程作为调度的基本单位而不是资源分配的基本单位，调度更为容易，而且采用线程提高系统的并行能力比采用进程更为有效。(3)同一进程的线程共享进程的用户地址空间，所以同一进程的线程间的通信更容易实现。5.在实际系统中，两种处理办法都是可行的，且各有优缺点。若撤消，则该进程的任务可能还没有完成，这显然是不利的，特别是当该进程的运行结果对其他进
4、程的运行很重要(如该进程是其他进程的前趋进程，没有它的运行结果其他进程无法运行)时；若不撤消，则该进程又可能成为不可控的“孤儿 “，从而产生不可预测的结果。比较好的做法是，当一个进程的父进程被撤消时，可以将该进程“过继“ 给系统内一个级别较高的进程 (如 Unix 中的 1#进程)，让它有一个“ 新的父亲 “，这样既可以继续完成其任务又不会成为不可控的。6.进程同步问题若处理不当，有可能会产生种种“与时间有关性错误“ ，特别是当两个或多个进程共享了公共变量而又没有互斥地使用这些变量时，极有可能导致用户程序运行结果的不正确，这量种灾难性的后果。这种 OS 显然是不成功的，是用户不敢使用的。有以下
5、四条准则：空闲让进、忙则等待、有限等待、让权等待。7.进程间存在着两种相互制约的关系：直接制约关系（即同步问题）和间接制约关系（即互斥问题） 。同步问题是存在逻辑关系的进程之间相互等待产生的制约关系，互斥问题是相互无逻辑关系的进程间竞争使用相同的资源所发生的制约关系。（1）属于互斥关系，因为书的个数是有限的，一本书只能借给一个同学。（2）属于互斥关系，篮球只有一个，两队都要争夺。（3）属于同步关系，各道工序的开始都依赖前道工序的完成。（4）属于同步关系，商品没生产出来，消费无法进行，商品未消费完，生产也无需进行。8.（1）高级调度又称为作业调度。它是批处理系统中使用的一种调度。其主要任务是按照
6、某种算法从外存的后备队列上选择一个或多个作业调入内存，并为其创建进程、分配必要的资源，然后再将所创建的进程控制块插入就绪队列中。（2）低级调度又称进程调度。它是距离硬件最近的一级调度。其主要任务是按照某种算法从就绪队列上选择一个（或多个）进程，使其获得 CPU。（3）引入中级调度的目的是为了提高内存利用率和系统吞吐量。其功能是，让那些暂时不能运行的进程不再占用宝贵的内存资源，而是调其到外存上等候。此时的进程状态为挂起状态。当这些进程重新具备运行条件且内存空闲时，由中级调度选择一部分挂起状态的进程调入内存并将其状态变为就绪状态。9.（1）时间片原则。在轮转算法中，CPU 轮流为诸多进程服务，每个
7、进程运行完自己的时间片后，系统就将 CPU 剥夺过来，交给下一个进程使用。（2）优先级原则。为紧迫的作业赋予较高的优先级，这种作业到达系统或由阻塞状态被唤醒后，若其优先级高于当前运行的进程的优先级，可以剥夺当前运行进程的 CPU。（3）短作业（进程）优先原则。若一个作业（进程）到达系统，其运行长度比当前运行的进程长度明显的短，则剥夺当前运行的进程 CPU。10.1）一个进程运行完毕。（2）一个正在运行的进程被阻塞。（3）在抢占式调度中，一个高优先级的进程被创建。（4）在抢占式调度中，一个高优先级进程由阻塞唤醒。（5）在轮转式调度中，正垢进程运行完一个时间片。11.（1）死锁是指多个进程因竞争资
8、源而造成的一种僵持状态。若无外力作用，这些进程都将永远处于阻塞状态，不能再运行下去。（2）产生死锁的原因有：资源不足、进程推进次序不当。（3）产生死锁的必要条件有：互斥条件、请求和保持条件、非剥夺条件、环路等待条件。比较三种解决死锁的方法：（1）预防死锁方法，主要是破坏产生死锁的必要条件。该方法是最容易实现的，但系统资源利用率较低。（2）避免死锁方法，比较实用的有银行家算法（Banker Algorithm） 。该算法需要较多的数据结构，实现起来比较困难，但资源利用率最高。（3）检测死锁方法是基于死锁定理设计的。定期运行该算法对系统的状态进行检测，发现死锁便予以解除。其中，需要比较一下各咱死锁
9、解除方案的代价，找到代价最小的方案。该方法最难实现，资源利用率较高。12.（1）每个进程实体中包含了程序段和数据段这两个部分，因此说进程是与程序是紧密相关的。但从结构上看，进程实体中除了程序段和数据段外，还必须包含一个数据结构，即进程控制块 PCB。（2）进程是程序的一次执行过程，因此是动态的；动态性还表现在进程由创建而产生、由调度而执行、由撤消而消亡，即它具有一定的生命周期。而程序则只是一组指令的有序集合，并和永久地存放在某种介质上，其本身不具有运动的含义，因此是静态的。（3）多个进程实体可同时存放在内存中并发地执行，也正是引入进程的目的。而程序（在没有为它创建进程时）的并发执行具有不可再现
10、性，因此程序不能正确地并发执行。（4）进程是一个能够独立运行、独立分配资源和独立接受调度的基本单位。而因程序不具有 PCB，所以它是不可能在多道程序环境下独立运行的。（5）程与程序不一一对应。同一个程序的多次运行，将形成多个不同的进程；同一个程序的一次执行也可以产生多个进程；而一个进程也可以执行多个程序。三、应用题1.#define CHAIRS /* 为等候的顾客准备的椅子数 */semaphore customers=0；semaphore barbers=0；semaphore mutex=1； /* 用于互斥 */int waiting=0；void barber()while (1)
11、wait(customers)；wait (mutex)；waiting=waiting-1；signal (mutex)；理发；signal(barbers)；void customers()wait (mutex)；if(waitingCHAIRS)waiting=waiting+1；signal (mutex)：signal (customers)；坐下等待；wait (barbers)；elsesignal (mutex)；2.为了实现计算进程和打印进程之间的同步，并使单缓冲中的每个计算结果都被两个打印进程分别打印一次。可设置四个信号量：full1 表示缓冲中是否有可供 P01 打印的
12、计算结果，full2 表示缓冲中是否有可给 P02 打印的计算结果；emptypl、empty2 则表示计算结果是否已被 P01l、 P02 取走，只有当一个结果被两个打印进程都取走后，缓冲区才变空，计算进程才可将下一个计算结果放入单缓冲。相应的同步算法可描述如下：Var empty1,enpty2,full1,full2: semaphore:=1,1,0,0;beginParbeginPC:beginRepeatcomputrt next number;P(empty1)：P(empty2)；add the number to bufer;V(full1);V(full2);Until f
13、alse;endP01: beginrepeatP(full1)；take from bufer;V(emptyl)：print last number;until flase;endP02：beginRepeatP(full2)；take from buffer;V(empty2);print last number;until falseendparendend3.信号量：nonf1、none1：输入进程与计算进程同步，buf1 是否为空；nonf2 、none1：计算进程与输出进程同步，buf2 是否为空；s1、s2：分别互斥使用 buf1 和 buf2procedure inputbe
14、ginwait(nonf1)wait(s1)put(data); signal(s1);signal(none1);until falseend;procedure computebeginwait(none1);wait(s1);data=get();data=calculate(data);signal(s1);signal(nonf1);wait(nonf2);wait(s2);put(data);signal(s2);signal(none2);until falseend;procedure outputbeginwait(none2);wait(s2);data=get();pri
15、nt(data);signal(s2);signal(nonf2);until falseend;4.（1）利用安全性算法对 T0 时刻的资源分配情况进行分析，结果如下：Work Need Allocation Work + Allocation FinishP3 1 6 3 1 0 0 1 3 5 2 9 8 trueP1 2 9 8 1 2 7 0 0 3 2 9 11 trueP2 2 9 11 0 7 5 1 0 0 3 9 11 trueP4 3 9 11 0 6 4 0 0 2 3 9 13 trueP5 3 9 13 0 6 2 0 0 1 3 9 14 true系统处于安全状态
16、，安全序列为：P3，P1，P2 ，P4，P5。（2）P1 发出请求向量 Request1（1，0，1）,系统按银行家算法进行检查：1) Request1（1，0，1） = Need1(1，2，6)2) Request1（1，0，1）= Available(1，6，3)3) 系统先假定可为 P1 分配资源，并修改 Available、 Allocation1、 Need1 向量，资源变化情况如下：max Allocation Available NeedA B C A B C A B C A B CP1 1 2 10 0 0 4 0 6 2 0 1 6P2 1 7 5 1 0 0 0 7 5P3
17、 2 3 5 1 3 5 1 0 0P4 0 6 4 0 0 2 0 6 2P5 0 6 5 0 0 1 0 6 4剩余资源可满足 P4，分给 P4 给还后（0,6,4）可满足 P5，分配 P5 归还后（0,6,5）不满足其它进程要求，即不能实施分配，因为分配后找不到安全序列，系统将处于不安全状态。5.2. (1 )采用先来先服务(FCFS)算法。作业名 提交时间/h 需执行时间/h 开始运行时间/h 完成时间/hJ1 10.1 0.3 10.1 10.4J2 10.3 0.5 10.4 10.9J3 10.5 0.4 10.9 11.3J4 10.6 0.3 11.3 11.6J5 10.7
18、 0.2 11.6 11.8J1，J2，J3 ，J4，J5T=(10.4-10.1)+(10.9-10.3)+(11.3-10.5)+(11.6-10.6)+(1l.8-10.7)/5=3.8/5=0.76hT=(10.4-10.1)/0.3+(10.9-10.3)/0.5+(11.3-10.5)/0.4+(11.6-10.6)/0.3+(1l.8-10.7)/0.2/5=13.033/5=2.61(2) 短作业优先调度(SJF)算法。作业名 提交时间/h 需执行时间/h 开始运行时间/h 完成时间/hJ1 10.1 0.3 10.1 10.4J2 10.3 0.5 10.4 10.9J3 1
19、0.5 0.4 11.4 11.8J4 10.6 0.3 11.1 11.4J5 10.7 0.2 10.9 11.1J1，J2，J5 ，J4，J3T=(10.4-10.1)+(10.9-10.3)+(11.8-10.5)+(11.4-10.6)+(11.1-10.7)/5=3.4/5=0.68hT=(10.4-10.1)/0.3+(10.9-10.3)/0.5+(11.8-10.5)/0.4+(11.4-10.6) /0.3+ (11.1-10.7)/0.2/5=10.117/5=2.02(3) 高响应比优先调度算法。作业名 提交时间/h 需执行时间/h 开始运行时间/h 完成时间/hJ1
20、10.1 0.3 10.1 10.4J2 10.3 0.5 10.4/10.7 11.0J3 10.5 0.4 10.6/11.5 11.8J4 10.6 0.3 11.2 11.5J5 10.7 0.2 11.0 11.2J1，J2，J3 ，J2，J5，J4，J3T=(10.4-10.1)+(11.0-10.3)+(11.8-10.5)+(11.5-10.6)+(11.2-10.7)/5=3.7/5=0.72hT=(10.4-10.1)/0.3+(11.0-10.3)/0.5+(11.8-10.5)/0.4+(11.5-10.6) /0.3+ (11.2-10.7)/0.2/5=11.15/
21、5=2.236.(1) 执行完序号为 6 的申请时，各进程的状态和已占的资源数如表所示；P 等待 已占用资源 4 个Q 就绪或运行 已占用资源 4 个R 等待 已占用资源 2 个根据单项银行家算法，过程为：1) R 申请 2 个资源时，剩余资源可使各进程运行结束，所以这个分配是安全的，故将2 个资源分给 R；2) 同理，P、Q 分别申请 4，2 个资源时，剩余资源可使各进程运行结束，所以这个分配也是安全的，故将 4、2 个资源分给 P、Q；3) P 申请 2 个资源时，系统此刻剩余资源数为 2，如果将这两个资源分给 P，系统就没有资源了。这时的 P、Q、R 都还需要资源才可运行完，这样，P、Q
22、、R 将都进入阻塞状态，所以 P 申请的这两个资源不能分配。4) 同理，接下来 R 欲申请 1 个资源也是不安全的分配，故不能分给。5) Q 申请 2 个资源时，假定操作系统分给它，Q 进程将运行结束， Q 释放的资源又可使 P 运行结束;P 运行结束，释放的资源又可使 R 运行结束。所以这个分配是安全的，故将2 个资源分给 Q。(2)不会死锁，因为银行家算法在任何时候均保证至少有一个进程能得到所需的全部资源，这样，得到资源的进程能及时归还资源供其他进程使用。7.从概念上讲，系统中各进程在逻辑上是独立的，它们可以按各自的速度向前推进。但由于它们共享某些临界资源，因而产生了临界区问题。对于具有临
23、界区问题的并发进程，它们之间必须互斥，以保证不会同时进入临界区。这种算法不是安全的。因为，在进入临界区的 enter-crtsec（）不是一个原语操作，如果两个进程同时执行完其循环（此前两个 flag 均为 false） ，则这两个进程可同时进入临界区。8. 分配策略为：当进程 Pi 申请 ri 类资源时，检查 ri 中有无可分配的资源：有则分配给 Pi；否则将 Pi 占有的资源全部释放而进入等待状态。(Pi 等待原占有的所有资源和新申请的资源) 资源分配过程： 剩余资源进程 A：(3，2，1) (1 ，0，1)进程 B：(1，0，1) (0 ，0，0)进程 A：(0，1，0)(不满足) (3
24、，2，1)A 的所有资源被剥夺，A 处于等待进程 C：(2，0，0) (1 ，2，1)C，B 完成之后，A 可完成。9.生产者-消费者问题的一个变形，一组生产者 A1，A2.，An 和一组消费者B1，B2，.，Bm 共用 k 个缓冲区，每个缓冲区只要写一次，但需要读 m 次。因此，我们可以把这一组缓冲区看成 m 组缓冲区，每个发送者需要同时写 m 组缓冲区中相应的 m 个缓冲区，而每一个接收者只需读它自己对应的那组缓冲区中的对应单元。设置一个信号量 mutex 实现诸进程对缓冲区的互斥访问；两个信号量数组 emptym和fullm描述 m 组缓冲区的使用情况。 mutex 的初值为 l，数组
25、empty 中元素初值为 k，数组full 中的元素初值为 0。其同步关系描述如下：int mutex,emptym,fullm；int i;mutex=1；for(i=0;i=m-1；i+)emptyi=k；fulli=0；main( )cobeginA1()；A2()；An()；B1()；B2()；Bm()；coendsend() /*发送消息 */in i；for(i=0； i=m-1；i+)P(emptyi)；P(mutex)；将消息放入缓冲区；V(mutex)；for(i=0； i=m-1；i+)V(fulli)；receive(i) /*接收消息 */p(fulli)；P(mutex)；将消息从缓冲区取出；V(mutex)；V(emptyi)；Ai() /*因发送进程 A1，A2， .，An 的程序类似。这里只给出进程 Ai 的描述。*/while(1)send()；Bi() /* 因接收进程 B1，B2，Bm 的程序类似这里只给出进程 Bi 的描述 */while(1)recive(i)；
