操作系统第二章练习题

刺骨的言语ヽ痛彻心扉 2023-10-12 11:31 56阅读 0赞

**第六部分 解析题**

1、进程的定义是什么？它最少有哪几种状态？

答:进程是一个具有一定功能的程序关于某个数据集合的一次运行活动。一个进程至少 就绪、执行和阻塞三种状态。就绪状态是指进程已获得了除处理机以外的所有资源,一旦获得处理机就可以立即执行。执行状态是指进程获得必要的资源并正在处理机上执行。阻塞状态是指进程由于发生某事件而暂时无法执行下去,此时即使把处理机分配给该进程,它也无法运行。

2、进程与线程的主要区别是什么？

线程具有许多传统进程所具有的特征，故又称为轻型进程或进程元；而把传统的进程称为重型进程，它相当于只有一个线程的任务。在引入了线程的操作系统中，通常一个进程都有若干个线程，至少也需要有一个线程。下面从调度、并发性、系统开销、拥有资源等方面，来比较线程与进程。 (1) 调度。在传统操作系统中，拥有资源的基本单位和独立调度、分派的基本单位都是进程。而在引入线程的操作系统中，则把线程作为调度和分派的基本单位，而把进程作为资源拥有的基本单位，使传统进程的两个属性分开，线程便能轻装运行，从而提高系统的并发程度。在同一进程中，线程的切换不会引起进程的切换，在由一个进程中的线程切换到另一进程中的线程时，将会引起进程切换。 (2) 并发性。在引入线程的操作系统中，不仅进程之间可以并发执行，而且在一个进程中的多个线程之间，亦可并发执行，因而使操作系统具有更好的并发性，从而能更有效地使用系统资源和提高系统的吞吐量。 (3) 拥有资源。不论是传统的操作系统，还是设有线程的操作系统，进程都是拥有资源的一个独立单位，它可以拥有自己的资源。一般来说，线程不拥有系统资源(也有一点必不可少的资源)，但它可以访问其隶属进程的资源。亦即，一个进程的代码段、数据段以及系统资源，如已打开的文件、I/O设备等，可供同一进程的所有线程共享。 (4) 系统开销。在创建或撤销进程时，系统都要为之分配或回收资源，如内存空间、I/O设备等。因此，操作系统所付出的开销将显著地大于在创建或撤消线程时的开销。类似地，在进行进程切换时，涉及整个当前进程CPU环境的保存以及新被调度运行的进程CPU环境的设置。而进程切换只需保存和设置少量寄存器的内容，并不涉及存储器管理方面的操作。可见，进程切换的开销也远大于线程切换的开销。此外，由于同一进程中的多个线程具有相同的地址空间，使两者之间的同步和通信的实现也变得比较容易，在有的系统中，线程的切换、同步和通信都无须需操作系统内核干预。

3、什么是进程的互斥与同步？同步和互斥这两个概念有什么联系和区别？

解：

（1） 同步：两个事件的发生有着某种时序上的关系，进程间的同步关系是指系统中往往有几个进程共同完成一个任务；

（2） 互斥是进程间的另外一种关系。由于各进程要共享资源。而有些资源往往要求排他性地使用；

（3） 互斥是一种特殊的同步关系。

4、下图给出了4个进程合作完成某一任务的前驱图，试说明这4个进程间的同步关系，并用P、V操作描述它。

![f2c93580d9d84499a0adaa62ee78a83a.png][]

解：图说明任务启动后S1先执行。当S1结束后，S2、S3可以开始执行。S2、S3完成后，S4才能开始执行。为了确保这一执行顺序，设3个同步信号量b2、b3、b4分别表示进程S2、S3、S4是否可以开始执行，其初值均为0。进程同步描述如下：

//可用两种方法来解决
    //S1不必判断能否开始
    //b2、b3、b4起初全部为0，表示都不可开始
    int b2=0;// 表示进程S2是否可以开始执行
    int b3=0;// 表示进程S3是否可以开始执行
    int b4=0;// 表示进程S4是否可以开始执行
    //也可分为b42、b43
    main()
    {
    	cobegin
    		S1();
    S2();
    S3();
    S4();
    Coend
    }
    S1()
    {
    …
    v(b2);
    v(b3);
    }
    S2()
    {
    	p(b2);
    …
    v(b4);  //v(b42)
    }
    S3()
    {
    	p(b3);
    …
    v(b4);  //v(b43)
    }
    S4()
    {//因为在S2及S3完成时均对b4做了v操作，因此这里要用两个p操作
    	p(b4);//p(b42)
    	p(b4);//p(b43)
    …
    }

5、桌上有一空盘，允许存放一只水果。爸爸可向盘中放苹果，也可向盘中放桔子，儿子专等吃盘中的桔子，女儿专等吃盘中的苹果。规定当盘空时一次只能放一只水果供吃者取用，请用P、V原语实现爸爸、儿子、女儿三个并发进程的同步。

解：设置3个信号量S、SO、SA，信号量S表示盘子是否为空，其初值为1；信号量SO表示盘中是否有桔子，其初值为0；信号量SA表示盘中是否有苹果，其初值为0。

同步描述：
    int S=1;
    int SA=0;
    int SO=0;
    main()
    {
    	cobegin
    		father();
    		son();
    		daughter();
    	coend
    }
    father()
    {
    	while(1)
    {
    	p(S);//盘子是否空
    	将水果放入盘中;
    	if(放入的是桔子)v(SO);//变形
    	else  v(Sa) //很少有学生如此做！而这却是本题的关键
    }
    }
    son()
    {
    	while(1)
    {
    	p(SO);//盘子中有无桔子
    	从盘中取出桔子;
    	v(S);
    	吃桔子;
    }
    }
    daughter()
    {
    	while(1)
    {
    	p(SA);//盘子中有无苹果
    	从盘中取出苹果;
    	v(S);
    吃苹果;
    }
    }

6、桌上有一空盘，允许存放一个水果。爸爸可向盘中放苹果(Apple)，妈妈可向盘中放西瓜(Melon)，儿子专等吃盘中的苹果，女儿专等吃盘中的西瓜。规定当盘空时一次只能放一个水果供儿子或女儿取用，请用P、V原语实现爸爸、妈妈、儿子、女儿4个并发进程的同步。

分析：爸爸、妈妈、儿子、女儿共用一个盘子，且盘中一次只能放一个水果。当盘子为空时，爸爸可将一个苹果放入盘中或者妈妈可将一块西瓜放入盘中。若放入盘中的是苹果，则允许儿子吃，女儿必须等待；若放入盘中的是西瓜，则允许女儿吃，儿子必须等待。本题实际上是生产者——消费者问题的一种变形。这里，生产者放入缓冲区的产品有两类，消费者也有两类，每类消费者只消费其中固定的一类产品。

int S=1;
    int SA=0;
    int SM=0;
    main()
    {    
        cobegin
            father();
            mother();
            son();
            daughter();
        coend
    }
    father(){
    while(1)
    {
        wait(S);//盘子是否空
        将苹果放入盘中;
        signal(SA);
    }
    }
    mother(){
    while(1){
        wait(S);//盘子是否空
        将西瓜放入盘中;
        signal(SM);
    }
    }
    son(){
    while(1){
    	wait(SA);//盘子中有无Apple	从盘中取出苹果;
    	signal(S);
    	吃苹果;
    }
    }
    daughter(){
    while(1){
    	wait(SM);//盘子中有无西瓜
    	从盘中取出西瓜;
    	signal(S);
      吃西瓜;
    }
    }

7、2015半个苹果半个橙子

桌上有一盘子，每次只能放入2个不同水果。Father专向盘里放Apple，Mother专向盘里放Orange，一个Son专吃盘中的half Orange and half Apple，一个Daughter专吃盘中的另外half Apple and half Orange。仅当盘没有放2个水果时，Father or Mother才可向盘里放一个水果，而且不允许放2个相同的水果。仅当盘中有自己需要的half Apple and half Orange时，Son or Daughter才可从盘里取出，而且Father,Mother放入一次后，Son,Daughter必须各自取一次。

把Father、Mother、Son、Daughter看作4个进程，用Wait(),Signal()原语进行管理，使这4个进程能正确地并发执行。

semaphore S1=1;//the dish space to put half apple
    semaphore S2=1;//the dish space to put another half apple
    semaphore S3=1;//the dish space to put half orange
    semaphore S4=1;//the dish space to put another half orange
    semaphore F1=0;//half apple
    semaphore F2=0;//another half apple
    semaphore F3=0;//half orange
    semaphore F4=0;//another half orange
    semaphore mutex=1;//盘子的互斥信号量
    {
    Cobegin
    Father()
    {
        while(1)
        {
         wait(S1);//father tests if the dish have the space to put half apple
         wait(S2);//father tests if the dish have the space to put another half apple
         wait(mutex);
           put apple into dish;
         signal(mutex);
         signal(F1);
         signal(F2);
        }
    }
    Mother()
    {
        while(1)
        {
         wait(S3);//mother tests if the dish have the space to put half orange
         wait(S4);//mother tests if the dish have the space to put another half orange
         wait(mutex);
           put orange into dish;
         signal(mutex);
         signal(F3);
         signal(F4);
        }
    }
    Son()
    {
        while(1)
        {
         wait(F1);//son tests if there is half apple in dish
         wait(F3);//son tests if there is half orange in dish
         wait(mutex);
           get half apple and half orange;
         signal(mutex);
         signal(S1);
         signal(S3);
        }
    }
    Daughter()
    {
        while(1)
        {
         wait(F2);//daughter tests if there is another half apple in dish
         wait(F4);//daughter tests if there is another half orange in dish
         wait(mutex);
           get half apple and half orange;
         signal(mutex);
         signal(S2);
         signal(S4);
        }
    }
    coend
    }

8、三个进程P1、P2、P3互斥使用一个包含N(N>0)个单元的缓冲区。P1每次用produce()生成一个正整数并用put()送入缓冲区某一空单元中；P2每次用getodd()从该缓冲区中取出一个奇数并用countodd() 统计奇数个数；P3每次用geteven()从该缓冲区中取出一个偶数，并用counteven()统计偶数个数。请用信号量机制实现这三个进程的同步与互斥活动，并说明所定义信号量的含义，要求用伪代码描述。

（1）缓冲区是一互斥资源，因此设互斥信号量mutex。
    （2）同步问题：P1、P2因为奇数的放置与取用而同步，设同步信号量odd；P1、P3因为偶数的放置与取用而同步，设同步信号量even；P1、P2、P3因为共享缓冲区，设同步信号量empty。
    Semaphore mutex=1;
    Semaphore odd=0; Semaphore even=0;
    Semaphore empty=N;
    main()
    cobegin
    {
    process P1
    while(1){
        number=produce();
        wait(empty);
        wait(mutex);
        put();
        signal(mutex);
        if(number % 2==0)
              signal(even);
        else
              signal(odd);
    }
    process P2
    while (1){
         wait(odd);
         wait(mutex);
         getodd();
         signal(mutex);
         signal(empty);
         countodd();
    }
    process P3
    while (1){
         wait(even);
         wait(mutex);
         geteven();
         signal(mutex);
         signal(empty);
         counteven();
    }
    }
    coend

9、实现“桌子上有一只盘子，最多可容纳两个水果，每次只能放入或取出一个水果。爸爸专向盘子中放苹果（apple），妈妈专向盘子中放橘子（orange），两个儿子专等吃盘子中的橘子，两个女儿专等吃盘子中的苹果。请用PV操作来实现爸爸、妈妈、儿子、女儿之间的同步与互斥关系。”

10、在单处理机的分时系统中，分配给进程P的时间片用完后，系统进行切换，结果调度到的仍然是进程P。有可能出现上述情形吗？如果可能请说明理由。

解：有可能出现上述情况。例如，若在进程P时间片用完后，被迫回到就绪队列时，就绪队列为空，这样进程P就是就绪队列中唯一的一个进程，于是调度程序选中的进程必然是进程P；又如在按优先级调度的系统中，就绪队列按进程优先级排列，在进程P时间片用完之后回到就绪队列时，若其优先级高于当前队列中的其他进程，则它将排在就绪队列之首，从而再次被调度程序选中并投入运行。

11、哲学家甲请哲学家乙、丙、丁到某处讨论问题，约定全体到齐后开始讨论问题；在讨论的间隙4位哲学家进餐，每人进餐时都需使用刀、叉各一把，餐桌上的布置如图。请用信号量及P、V操作说明这4位哲学家的同步、互斥过程。

在本题中，应设置4个信号量fork1、fork2、knife1、knife2，其初值均为1，分别表示资源叉1、叉2、刀1、刀2是否可用。同步描述如下：
    int fork1=1;
    int fork2=1;
    int knife1=1;
    int knife2=1;
    main()
    {
    	cobegin
    		Pa();
    		Pb();
    		Pc();
    		Pd();
    	Coend
    }
    Pa()
    {
    	while(1)
    	{
    		p(knife1);
    		p(fork1);
    		进餐；
    		v(knife1);
    		v(fork1);
    		讨论问题；
    	}
    }
    Pb()
    {
    	while(1)
    	{
    		p(knife2);
    		p(fork1);
    		进餐；
    		v(knife2);
    		v(fork1);
    		讨论问题；
    	}
    }
    Pc()
    {
    	while(1)
    	{
    		p(knife2);
    		p(fork2);
    		进餐；
    		v(knife2);
    		v(fork2);
    		讨论问题；
    	}
    }
    Pd()
    {
    	while(1)
    	{
    		p(knife1);
    		p(fork2);
    		进餐；
    		v(knife1);
    		v(fork2);
    		讨论问题；
    	}
    }

12、请用信号量实现对某数据库的读者－写者互斥。

要求：

（1）读者与写者之间互斥，写者与写者之间互斥。

（2）读者之间不互斥。

解：本题是读者－写者问题。在本题中，允许读进程同时读数据库，但写进程正在写数据库时不允许其他进程读该数据库，也不允许其他进程写该数据库。为了解决读、写进程之间的同步，应该设置2个信号量和一个共享变量：读互斥信号量rmutex，用于使读进程互斥地访问共享变量count，其初值为1；写互斥信号量wmutex，用于实现写进程与读进程的互斥及写进程与写进程的互斥，其初值为1；共享变量count，用于记录当前正在读数据库的读进程数目，初值为0。其工作过程描述如下：

Semaphore rmutex=1;
    Semaphore wmutex=1;
    Int count=0;
    Main()
    {
      Cobegin
    Reader();
    Writer();
      Coend
    }
    Reader()
    {
      While(true)
      {
    P(rmutex);
    If(count==0) p(wmutex);
    Count ++;
    V(rmutex);
    读数据库；
    P(rmutex);
    Count --;
    If (count==0) v(wmutex);
    V(rmutex);
      }
    }
    Writer()
    {
      While(true)
    {
    P(wmutex);
        写数据库；
    V(wmutex);
      }
    }

注意：正确理解信号量rmutex的意义是理解读者－写者问题的关键。Rmutex是一个互斥信号量，用于使读进程互斥地访问共享变量count。信号量rmutex并不表示读进程的数目，表示读进程数目的是共享变量count。当一个读进程要读数据库时，应将读进程计数count增加1；如果此前（count加1以前）数据库中无读进程，还应对写互斥信号量wmutex做p操作，这样，若数据库中无写进程则通过p操作阻止后续写进程写，若数据库中有写进程，则通过p操作让读进程等待。同理，当一个读进程完成读数据库操作时，应将读进程计数count减少1；如果此时（count减1以后）数据库中已无读进程，还应对写互斥信号量wmutex做v操作，以允许写进程写。

13、就绪队列中有10个进程，系统将时间片设为200ms，CPU进行进程切换要花费10ms，试问系统开销所占的比率约为多少？

解：因就绪队列中有10个进程，它们以时间片轮转的方式使用CPU，时间片长度为200ms。当一个时间片用完时，调度进程将当前运行进程设置为就绪状态并放入就绪队列尾，再从就绪队列首选择进程投入运行，这一过程（进程切换）要花费时间10ms。因此系统开销所占比率为：10/（200+10）=4.8%

14、在单CPU和两台输入/输出设备（I1，I2）的多道程序设计环境下，同时投入三个作业Job1、Job2、Job3运行。这三个作业对CPU和输入/输出设备的使用顺序和时间如下所示：

15、试利用Bernstein 条件证明上题中的S2和S3语句是可以并发执行的，而S3和S4语句是不能并发执行的？

（1） ∵R(S2) ∩ W( S3)=\{\}；

W(S2) ∩ R(S3)=\{\}；

W(S2) ∩ W(S3)=\{\}；

∴R(S2) ∩ W( S3)∪ W(S2) ∩ R(S3) ∪ W(S2) ∩ W(S3)=\{\}

∴S2、S3可以并发执行

（2）∵R(S3) ∩ W( S4)=\{\}；

W(S3) ∩ R(S4)=\{c\}；

W(S3) ∩ W(S4)=\{\};

∴R(S3) ∩ W( S4)∪ W(S3) ∩ R(S4) ∪ W(S3) ∩ W(S4)=\{c\}不是空集

∴S3，S4不能并发执行

16、有两个进程P1和P2，它们执行的过程如下：

P1: 10秒CPU操作、20秒I/O操作（设备1）、5秒CPU操作、10秒I/O操作（设备2）、5秒CPU操作、结束

P2: 15秒I/O操作（设备1）、10秒CPU操作、15秒I/O操作（设备2）、10秒CPU操作、结束

1.  如果进程P1和P2顺序执行，请画出进程P1和P2执行情况图；
2.  如果进程P1和P2并发执行，请画出进程P1和P2执行情况图；
3.  分别计算在（1）和（2）情况下，CPU的利用率、设备1和设备2的利用率。

（1）

![e93b934cedbe46edb6991446d3d5a509.png][]

![c2f21dbc60cd4937b822d5b087b2d825.png][]

（2）

![aca71ffca78f404cab04a4ad08631698.png][]

(3)

在情况（1）下，

CPU的利用率=40/100=40%

设备1的利用率=35/100=35%

设备2的利用率=25/100=25%

在情况（2）下，

CPU的利用率=40/55=73%

设备1的利用率=35/55=64%

设备2的利用率=25/55=45%

17、在五状态图中，假如计算机只有一个CPU，如果系统中有N个进程：

（1）运行的进程最多几个，最少几个；就绪进程最多几个最少几个；等待进程最多几个，最少几个？

（2）有没有这样的状态转换，为什么？

等待—>运行 ； 就绪—>等待

（3）一个进程状态的转换是否会导致另一个进程的状态转换，请列出所有的可能。

（1）如果系统中有N个进程，运行的进程最多1个，最少0个；就绪进程最多N-1个最少0个；等待进程最多N个，最少0个。

（2）没有这样的状态转换。

（3） 新建 到 就绪 导致 运行 到 就绪

就绪 到 运行 导致 无

运行 到 就绪 导致 就绪 到 运行

运行 到 等待 导致 就绪 到 运行

等待 到 就绪 导致 就绪 到 等待

运行 到 结束 导致 就绪 到 运行

[f2c93580d9d84499a0adaa62ee78a83a.png]: https://img-blog.csdnimg.cn/f2c93580d9d84499a0adaa62ee78a83a.png
[e93b934cedbe46edb6991446d3d5a509.png]: https://img-blog.csdnimg.cn/e93b934cedbe46edb6991446d3d5a509.png
[c2f21dbc60cd4937b822d5b087b2d825.png]: https://img-blog.csdnimg.cn/c2f21dbc60cd4937b822d5b087b2d825.png
[aca71ffca78f404cab04a4ad08631698.png]: https://img-blog.csdnimg.cn/aca71ffca78f404cab04a4ad08631698.png