精华内容
下载资源
问答
  • 操作系统经典问题
    千次阅读 多人点赞
    2019-03-31 13:02:56

    理发师问题描述如下:
    理发店包含一间接待室和一间工作室,有一名理发师,接待室内有n(n≥1)把椅子,而工作室只有1把椅子。如果没有顾客,理发师就去睡觉;如果理发师在睡觉;则顾客会唤醒他;如果理发师在忙且接待室有空闲椅子,那么此顾客会坐在其中1把空闲的椅子上等待;如果来时所有椅子都有人,那么顾客离去。请采用信号量机制解决该理发师问题(用伪代码描述)。

    分析:
    (1)设置理发师的资源信号量为barber,初值为初始状态可用的资源数,故设barber初值为0(因为没有顾客的时候理发师在睡觉呀)。
    (2)设置顾客的资源信号量为customers,初值为0(刚开始没有顾客来)。
    (3)用互斥信号量mutex实现进程互斥。
    (4)用变量waiting来记录等待的顾客数,判断有没有空闲椅子。

    伪代码如下:

    semaphore barber,customers,mutex;
    barber = customers = 0,mutex = 1;
    int waiting = 0;
    parbegin
    process barber{
    	while(true){
    		wait(customers);//barber在等顾客喊他,没有顾客就睡觉
    		wait(mutex);//只能被一个顾客叫醒
    		waiting=waiting-1;//有顾客将得到服务,有等待区的椅子空出来
    		signal(barber);//一个理发师资源被释放
    		signal(mutex);
    		cut_hair();//理发师在工作
    	}	
    }
    process customers{
    	wait(mutex);//一次只能有一个顾客进行以下操作,即访问椅子
    	if(waiting<n){//来了个顾客在门口往店里看了看,如果有空闲的椅子
    		waiting=waiting+1;//进店坐下了
    		signal(customers);//顾客跟理发师打招呼说“我来了”
    		signal(mutex);//访问椅子结束
    		wait(barber);//等待理发师
    		get_haircut();//得到服务
    	}else{//看了看发现店里没有位置
    		signal(mutex);//走了
    	}	
    }
    parend
    

    更新
    最近在考研又看到这题,才发现评论区对于customers这个信号量的设置有很多疑问。首先,空闲椅子的有无影响了等待顾客的数量,而顾客的有无影响了理发师是否开始理发,所以要使用不同的信号量来处理。customers这个信号量的作用,和生产者消费者里面的full的作用差不多。

    更多相关内容
  • 操作系统经典问题

    千次阅读 2014-09-07 13:57:37
    操作系统经典问题
    1、什么是进程(Process)和线程(Thread)?有何区别? 

    进程是具有一定独立功能的程序关于某个数据集合上的一次运行活动,进程是系统进行资源分配和调度的一个独立单位。进程与应用程序的区别在于应用程序作为一个静态文件存储在计算机系统的硬盘等存储空间中,而进程则是处于动态条件下由操作系统维护的系统资源管理实体。线程是进程的一个实体,是CPU调度和 分派的基本单位,它是比进程更小的能独立运行的基本单位。线程自己基本上不拥有系统资源,只拥有一点在运行中必不可少的资源(如程序计数器,一组寄存器和 栈),但是它可与同属一个进程的其他的线程共享进程所拥有的全部资源。一个线程可以创建和撤销另一个线程,同一个进程中的多个线程之间可以并发执行。比如父子进程间的全局变量是独立的,虽然采用了写时复制的策略;但是同一个进程中的线程共享该进程的全局变量,它们的操作相互影响,只有函数中的局部变量才有私有的

    2、进程调度的方法

    完全公平(CFS)调度算法、O(1)调度算法、先来先服务、短执行进程优先算法、最高优先级优先调度算法(核心是确定进程的优先级)、时间片轮转法

    3、进程同步的方法?

    进程间同步的主要方法有原子操作、信号量机制、自旋锁、管程、会合、分布式系统等。

    4、死锁在两个或多个并发进程中,如果每个进程持有某种资源而又都等待别的进程释放它或它们现在保持着的资源,在未改变这种状态之前都不能向前推进,称这一组进程产生了死锁。通俗地讲,就是两个或多个进程被无限期地阻塞、相互等待的一种状态。

    产生死锁的原因主要是(1) 因为系统资源不足。 (2) 进程运行推进的顺序不合适。(3) 资源分配不当等。


    产生死锁的四个必要条件

     (1) 互斥条件:一个资源每次只能被一个进程使用。

    (2) 请求与保持条件:一个进程因请求资源而阻塞时,对已获得的资源保持不放。

    (3) 不剥夺条件:进程已获得的资源,在末使用完之前,不能强行剥夺。

    (4) 循环等待条件:若干进程之间形成一种头尾相接的循环等待资源关系。

    这四个条件是死锁的必要条件,只要系统发生死锁,这些条件必然成立,而只要上述条件之一不满足,就不会发生死锁。


    死锁的预防
    该策略旨在创造条件预防死锁。即破坏产生死锁的四个必要条件之一,就不会出现死锁,但是效果都不理想

    1. 互斥条件

    如果系统中的资源可以由多个进程共享,那么就永远不会发生死锁。然而,这种共享不切实际。例如,磁带机、绘图仪或打印机就不能在多个进程之间共享使用。

    2. 请求与保持条件

    方法一:进程一开始就声明它期望使用的全部资源,但显而易见的是,它不能达到预期效果而且很浪费。

    方法二:操作系统必须让请求某些资源的进程先放弃已经占用的资源,然后再尝试请求所有要用的资源。如果尝试成功,被放弃的资源才可以重新分配给该进程,这样该进程才可以继续运行。如果失败,被放弃的资源恢复空闲,而进程则必须一直等到那些资源可用为止。每次检查后,进程都放弃已占用的资源,这样就永远不会出现死锁。同样地,这种技术可用于表、信号量等共享资源,但不适用于打印机和磁带机这类资源。想象一下,某个进程在打印到一半的时候放弃使用打印机,而某个其他进程占用该打印机将产生什么样的后果。

    3. 非抢占条件

    确保不满足"非抢占"条件很困难。如果允许将资源分配给可以强制夺取该资源的进程,也许可以解决死锁问题,但会出现更糟糕的问题。从一个只处理了部分记录的进程强制性地夺走磁带机--因为其他进程请求使用该资源,由此带来的加载/卸载、定位等问题一定令人无法接受。

    4. 循环等待条件

    解决该问题的一个更好的方法就是对所有的资源编号,任何进程都必须在执行期间按照编号递增的顺序请求所需的资源,从而不会产生死锁。


    死锁避免系统对进程发出每一个系统能够满足的资源申请进行动态检查,并根据检查结果决定是否分配资源,如果分配后系统可能发生死锁,则不予分配,否则予以分配.这是一种保证系统不进入死锁状态的动态策略  。 死锁避免和死锁预防的区别在于: 死锁预防是设法至少破坏产生死锁的四个必要条件之一,严格的防止死锁的出现,而死锁避免则不那么严格的限制产生死锁的必要条件的存在,因为即使死锁的必要条件存在,也不一定发生死锁.死锁避免是在系统运行过程中注意避免死锁的最终发生.

    常用方法:

    1)银行家算法:每个进程申请资源时,系统采用银行家算法先进行判断,即假设我把这些资源分配给该进程,如果后序能找到一个安全区状态(即不会发生死锁的状态),就进行真正的分配,如果找不到,则不分配。具体参考这里

    2)鸵鸟算法:它假设出现死锁的概率很小,并且出现之后处理死锁会花费很大的代价,还不如不做处理,OS中这种置之不理的策略称之为鸵鸟算法。


    4、用户进程间通信主要哪几种方式?

    1)管道(Pipe):管道可用于具有亲缘关系进程间的通信,允许一个进程和另一个与它有共同祖先的进程之间进行通信。

    2)命名管道(named pipe):命名管道克服了管道没有名字的限制,因此,除具有管道所具有的功能外,它还允许无亲缘关系进程间的通信。命名管道在文件系统中有对应的文件名。命名管道通过命令mkfifo或系统调用mkfifo来创建。

    3)信号(Signal:信号是比较复杂的通信方式,用于通知接受进程有某种事件发生,除了用于进程间通信外,进程还可以发送信号给进程本身;linux除了支持Unix早期信号语义函数sigal外,还支持语义符合Posix.1标准的信号函数sigaction(实际上,该函数是基于BSD的,BSD为了实现可靠信号机制,又能够统一对外接口,用sigaction函数重新实现了signal函数)。

    4)消息队列:消息队列是消息的链接表,包括Posix消息队列、system V消息队列。有足够权限的进程可以向队列中添加消息,被赋予读权限的进程则可以读走队列中的消息。消息队列克服了信号承载信息量少,管道只能承载无格式字节流以及缓冲区大小受限等缺

    5)共享内存:使得多个进程可以访问同一块内存空间,是最快的可用IPC形式。是针对其他通信机制运行效率较低而设计的。往往与其它通信机制,如信号量结合使用,来达到进程间的同步及互斥。

    6)信号量(semaphore:主要作为进程间以及同一进程不同线程之间的同步手段。

    7)套接字(Socket:更为一般的进程间通信机制,可用于不同机器之间的进程间通信。起初是由Unix系统的BSD分支开发出来的,但现在一般可以移植到其它类Unix系统上:LinuxSystem V的变种都支持套接字。


    5、系统调用和库函数的区别

    (1)调用形式不同。过程(函数)使用一般调用指令,其转向地址是固定不变的,包含在跳转语句中;但系统调用中不包含处理程序入口,而仅仅提供功能号,按功能号调用。
    (2)被调用代码的位置不同。过程(函数)调用是一种静态调用,调用者和被调用代码在同一程序内,经过连接编辑后作为目标代码的一部份。当过程(函数)升级或修改时,必须重新编译链接。而系统调用是一种动态调用,系统调用的处理代码在调用程序之外(在操作系统中),这样一来,系统调用处理代码升级或修改时,与调用程序无关。而且,调用程序的长度也大大缩短,减少了调用程序占用的存储空间。
    (3)提供方式不同。过程(函数)往往由编译系统提供,不同编译系统提供的过程(函数)可以不同;系统调用由操作系统提供,一旦操作系统设计好,系统调用的功能、种类与数量便固定不变了。
    (4)调用的实现不同。程序使用一般机器指令(跳转指令)来调用过程(函数),是在用户态运行的;程序执行系统调用,是通过中断机构来实现,需要从用户态转变到核心态,在管理状态执行,因此,安全性好。


    6、内核同步(即并发访问)的方法

    1):中断屏蔽
    在单CPU范围内避免竞态的一种简单方法是在进入临界区之前屏蔽系统的中断。由于linux内核的进程调度等操作都依赖中断来实现,内核抢占进程之间的并发也就得以避免了。
    特点:由于linux系统的异步IO,进程调度等很多重要操作都依赖于中断,在屏蔽中断期间所有的中断都无法得到处理,因此长时间的屏蔽是很危险的,有可能造成数据丢失甚至系统崩溃,这就要求在屏蔽中断之后,当前的内核执行路径应当尽快地执行完临界区的代码。中断屏蔽只能禁止本CPU内的中断,因此,并不能解决多CPU引发的竞态,所以单独使用中断屏蔽并不是一个值得推荐的避免竞态的方法,它一般和自旋锁配合使用。
    2):原子操作
    定义:原子操作指的是在执行过程中不会被别的代码路径所中断的操作。
    3):
    自旋锁
    Linux内核中最常见的锁是自旋锁(spin lock),自旋锁最多只能被一个可执行线程持有,如果一个执行线程试图获得一个被争用(已经被持有)的自旋锁,那么该线程就会一直进行忙循环—旋转—等待锁重新可用,要是锁未被争用,请求锁的执行线程便能立刻得到它,继续执行,在任意时间,自旋锁都可以防止多于一个的执行线程同时进入临界区,注意同一个锁可以用在多个位置—例如,对于给定数据的所有访问都可以得到保护和同步。
    一个被争用的自旋锁使得请求它的线程在等待锁重新可用时自旋(特别浪费处理器时间),所以自旋锁不应该被长时间持有,事实上,这点正是使用自旋锁的初衷,在短期间内进行轻量级加锁,还可以采取另外的方式来处理对锁的争用:让请求线程睡眠,直到锁重新可用时再唤醒它,这样处理器就不必循环等待,可以去执行其他代码,这也会带来一定的开销——这里有两次明显的上下文切换,被阻塞的线程要换出和换入。因此,
    持有自旋锁的时间最好小于完成两次上下文切换的耗时,当然我们大多数人不会无聊到去测量上下文切换的耗时,所以我们让持 有自旋锁的时间应尽可能的短就可以了,信号量可以提供上述第二种机制,它使得在发生争用时,等待的线程能投入睡眠,而不是旋转。
    自旋锁可以使用在中断处理程序中(此处不能使用信号量,因为它们会导致睡眠),在中断处理程序中使用自旋锁时,一定要在获取锁之前,首先禁止本地中断(在 当前处理器上的中断请求),否则,中断处理程序就会打断正持有锁的内核代码,有可能会试图去争用这个已经持有的自旋锁,这样以来,中断处理程序就会自旋, 等待该锁重新可用,但是锁的持有者在这个中断处理程序执行完毕前不可能运行,这正是我们在前一章节中提到的双重请求死锁,注意,需要关闭的只是当前处理器上的中断,如果中断发生在不同的处理器上,即使中断处理程序在同一锁上自旋,也不会妨碍锁的持有者(在不同处理器上)最终释放锁。
    其实介绍的几种信号量和互斥机制,其底层源码都是使用自旋锁,可以理解为自旋锁的再包装。所以从这里就可以理解为什么自旋锁通常可以提供比信号量更高的性能。
    4):读写自旋锁
    如 果临界区保护的数据是可读可写的,那么只要没有写操作,对于读是可以支持并发操作的。对于这种只要求写操作是互斥的需求,如果还是使用自旋锁显然是无法满 足这个要求(对于读操作实在是太浪费了)。为此内核提供了另一种锁-读写自旋锁,读自旋锁也叫共享自旋锁,写自旋锁也叫排他自旋锁。
    5):顺序琐
    顺序琐(seqlock)是对读写锁的一种优化,若使用顺序琐,读执行单元绝不会被写执行单元阻塞,也就是说,读执行单元可以在写执行单元对被顺序琐保护的共享资源进行写操作时仍然可以继续读,而不必等待写执行单元完成写操作,写执行单元也不需要等待所有读执行单元完成读操作才去进行写操作。
    但是,写执行单元与写执行单元之间仍然是互斥的,即如果有写执行单元在进行写操作,其它写执行单元必须自旋在哪里,直到写执行单元释放了顺序琐。
    如果读执行单元在读操作期间,写执行单元已经发生了写操作,那么,读执行单元必须重新读取数据,以便确保得到的数据是完整的,这种锁在读写同时进行的概率比较小时,性能是非常好的,而且它允许读写同时进行,因而更大的提高了并发性,注意,顺序琐由一个限制,就是它必须被保护的共享资源不含有指针,因为写执行单元可能使得指针失效,但读执行单元如果正要访问该指针,将导致Oops。
    6):
    信号量
    Linux中的信号量是一种睡眠锁,如果有一个任务试图获得一个已经被占用的信号量时,信号量会将其推进一个等待队列,然后让其睡眠,这时处理器能重获自由,从而去执行其它代码,当持有信号量的进程将信号量释放后,处于等待队列中的哪个任务被唤醒,并获得该信号量。
    7):读写信号量
    类似于自旋锁,信号量也有读写信号量。首先要说明的是所有的读写信号量都是互斥信号量。读锁是共享锁,就是同时允许多个读进程持有该信号量,但写锁是独占锁,同时只能有一个写锁持有该互斥信号量。

    自旋锁和信号量区别

    在驱动程序中,当多个线程同时访问相同的资源时(驱动程序中的全局变量是一种典型的共享资源),可能会引发"竞态",因此我们必须对共享资源进行并发控制。Linux内核中解决并发控制的最常用方法是自旋锁与信号量(绝大多数时候作为互斥锁使用)。

    自旋锁与信号量"类似而不类",类似说的是它们功能上的相似性,"不类"指代它们在本质和实现机理上完全不一样,不属于一类。
    自旋锁不会引起调用者睡眠,如果自旋锁已经被别的执行单元保持,调用者就一直循环查看是否该自旋锁的保持者已经释放了锁,"自旋"就是"在原地打转"。而信号量则引起调用者睡眠,它把进程从运行队列上拖出去,除非获得锁。这就是它们的"不类"。
    但是,无论是信号量,还是自旋锁,在任何时刻,最多只能有一个保持者,即在任何时刻最多只能有一个执行单元获得锁。这就是它们的"类似"。
    鉴于自旋锁与信号量的上述特点,一般而言,自旋锁适合于保持时间非常短的情况,它可以在任何上下文使用;信号量适合于保持时间较长的情况,却只能在进程上下文使用。
    如果被保护的共享资源只在进程上下文访问,则可以以信号量来保护该共享资源,如果对共享资源的访问时间非常短,自旋锁也是好的选择。但是,如果被保护的共享资源需要在中断上下文访问(包括底半部即中断处理句柄和顶半部即软中断),就必须使用自旋锁。至于信号量为什么不能用于中断上下文,是因为中断上下文不能睡眠。至于为什么不能睡眠简单的来说就是中断上下文不是一个进程上下文,其没有一个专门用来描述CPU寄存器等信息的数据结构,所以无法被调度器调度,中断(硬中断、软中断)处理都是些耗时不是很长,对实时性要求很高,执行频度较高的应用,所以,如果采用一个专门的后台daemon对其处理,显然并不合适。


    7、什么是中断?中断时CPU做什么工作?

    中断是指在计算机执行期间,系统内发生任何非寻常的或非预期的急需处理事件,使得CPU暂时中断当前正在执行的程序而转去执行相应的事件处理程序。待处理完毕后又返回原来被中断处继续执行或调度新的进程执行的过程。


    8、内存管理

    8.1:物理地址与虚拟地址

    8.2:虚拟内存

    为了扩充内存空间,引入了虚拟存储器(磁盘空间的一部分),可以将进程的虚拟地址空间映射到磁盘空间中,并且由页表记录映射位置,当访问到某个地址的时候,通过页表的有效位,可以得知数据是否在内存中,如果不是则通过缺页异常,将磁盘对应的数据 拷贝到内存中,如果没有 空闲内存,则选择牺牲页面,替换其他页面。
    事实上,在每个进程创建加载时,内核只是为进程创建了虚拟内存的布局,具体就是初始化进程控制表中内存相关的链表,实际上并不立即就把虚拟内存对应位置的程序数据和代码拷贝到物理内存中,只是建立好虚拟内存和磁盘文件之间的映射就好,叫做内存文件映射,等到运行到对应程序时,才会通过缺页异常来拷贝数据。还有进程在运行过程中,要动态分配内存,比如malloc时,也只是分配了虚拟内存,即为这块虚拟内存对应的页表项做相应设置,当进程真正访问到此数据时,才引发缺页异常。 缺页异常的处理过程,就是把进程需要的数据从磁盘上拷贝到物理内存中,如果内存已经满了,没有空地方了,那就找一个页覆盖,当然如果被覆盖的页曾经被修改过,需要将此页写回磁盘

    好处:

    1)既然每个进程的内存空间都是一致而且固定的,所以链接器在链接可执行文件时,可以设定内存地址,而不用去管这些数据最终实际的内存地址,这是有独立内存空间的好处

    2)当不同的进程使用同样的代码时,比如库文件中的代码,物理内存中可以只存储一份这样的代码,不同的进程只需要把自己的虚拟内存映射过去就可以了,节省内存

    3)在程序需要分配连续的内存空间的时候,只需要在虚拟内存空间分配连续空间,而不需要实际物理内存的连续空间,可以利用碎片。

    8.3:内存映射文件

    虚拟内存使用物理内存或者交换区来保留和提交一个地址空间的区域,而在内存映射文件中,使用的是一个位于磁盘上的文件来映射一个进程的地址空间区域,一旦映射文件,就可以访问这个文件,如同已经把这个文件加载到内存。
    内存映射文件文件可以用于3个目的:
    a、 系统使用内存映射文件来加载和执行可执行文件和动态链接库,这样可以大大节省页面文件空间以及应用程序启动运行所需要的时间。
    b、使用内存映射文件来访问磁盘中的数据文件,这样就不必对文件执行I/O操作,并且不必对文件进行缓存。
    c、使用内存映射文件,在同一台机器上运行的多个进程之间共享数据。windows也提供了其他在进程之间进行通信的方法,不过这些方法都是使用内存映射文件来实现的,这使得内存映射文件成为在单个计算机上的多进程之间进行通信的最好方法。
    8.4: 进程的虚拟地址空间
    每个进程都有自己的虚拟地址空间,32位的是4GB,64位的是16EB。每个进程都拥有自己私有的地址空间,其他进程的内存地址空间被系统隐藏,例如:进程A和B可以在地址0x12345678中存放自己的数据结构,当A访问0x12345678地址时访问的是A的数据结构,B访问地址0x12345678时使用的是B的数据结构
    8.5:分段和分页的区别
    页是信息的物理单位,分页是为实现离散分配方式,以消减内存的外零头,提高内存的利用率;或者说,分页仅仅是由于系统管理的需要,而不是用户的需要。段是信息的逻辑单位,它含有一组其意义相对完整的信息。分段的目的是为了能更好的满足用户的需要。页的大小固定且由系统确定,把逻辑地址划分为页号和页内地址两部分,是由机器硬件实现的,因而一个系统只能有一种大小的页面。段的长度却不固定,决定于用户所编写的程序,通常由编辑程序在对源程序进行编辑时,根据信息的性质来划分。分页的作业地址空间是一维的,即单一的线性空间,程序员只须利用一个记忆符,即可表示一地址。分段的作业地址空间是二维的,程序员在标识一个地址时,既需给出段名,又需给出段内地址。

    9:虚拟文件系统
    虚拟文件系统作为内核子系统,为用户空间应用程序提供了文件和文件系统相关的接口。通过虚拟文件系统,程序可以利用标准的UNIX系统调用对不同的文件系统,甚至不同介质上的文件系统进行读写操作。比如:应用程序调用write(fd,buf,len)系统调用,这个系统调用首先被VFS的通用系统调用sys_write()处理,sys_write()要先找到fd所在的文件系统实际给出的是哪个写操作,然后再调用该文件系统的特殊的写操作进行真正的写动作。

    展开全文
  • 生产者和消费者问题是计算机同步互斥的经典问题,其意思就是生产者把生产出来的产品放在仓库里,消费者把产品从仓库里取出来。仓库属于临界区,生产者和消费者一次只能一个进入临界区中。两个进程之间就有一个同步...

    一、生产者消费者问题

    生产者和消费者问题是计算机同步互斥的经典问题,其意思就是生产者把生产出来的产品放在仓库里,消费者把产品从仓库里取出来。仓库属于临界区,生产者和消费者一次只能一个进入临界区中。两个进程之间就有一个同步互斥问题,下面我将对该问题进行详细介绍。

    二、思路分析

    对于一个仓库,仓库的容量是有限的,对应的临界资源是有限的,假设仓库的容量是n。当仓库装满了,就不能允许生产者进行访问,如果仓库满了,生产者再把产品放进仓库就会导致仓库爆仓。与此同时,当库存为零时也不能允许消费者进入,这个不符合逻辑。基于这种思路,我们设置三个信号量empty、full和一个互斥锁。

    三、代码实现

    semaphore mutex=1;
    semaphore empty=n;
    semaphore full=0;
    //生产者
    producer(){
    	while(1){
    		//生产者生产产品
    		P(empty);//判断仓库是否为空
    		P(mutex);//判断是否可以进入临界区
    		//放产品
    		V(full);//仓库里有多少产品
    		V(mutex);//释放互斥锁
    	}
    }
    
    //消费者
    consumer(){
    	while(1){
    		P(full);//判断仓库是否有产品
    		P(mutex);//判断是否可以进入临界区
    		//放消费产品
    		V(empty);//仓库里增加一个空位
    		V(mutex);//释放互斥锁
    	}
    }
    
    展开全文
  • 和尚打水问题(多生产者多消费者): 问题描述:某寺庙,有小和尚和老和尚若干,有一个水缸,由小和尚提水入缸供老和尚饮用。水缸可以容纳10桶水,水取自同一口井中,由于水井口窄,每次只能容纳一个水桶取水。水桶...

    一、生产者消费者问题

    生产者消费者问题(英语:Producer-consumer problem),也称有限缓冲问题(英语:Bounded-buffer problem),是一个多线程同步问题的经典案例。

    该问题描述了共享固定大小缓冲区的两个线程——即所谓的“生产者”和“消费者”——在实际运行时会发生的问题。

    生产者的主要作用是生成一定量的数据放到缓冲区中,然后重复此过程。与此同时,消费者也在缓冲区消耗这些数据。该问题的关键就是要保证生产者不会在缓冲区满时加入数据,消费者也不会在缓冲区中空时消耗数据。

    要解决该问题,就必须让生产者在缓冲区满时休眠(要么干脆就放弃数据),等到下次消费者消耗缓冲区中的数据的时候,生产者才能被唤醒,开始往缓冲区添加数据。同样,也可以让消费者在缓冲区空时进入休眠,等到生产者往缓冲区添加数据之后,再唤醒消费者。通常采用进程间通信的方法解决该问题。如果解决方法不够完善,则容易出现死锁的情况。出现死锁时,两个线程都会陷入休眠,等待对方唤醒自己。该问题也能被推广到多个生产者和消费者的情形。

    该问题需要注意的几点:

    • 在缓冲区为空时,消费者不能再进行消费
    • 在缓冲区为满时,生产者不能再进行生产
    • 消费者之间互斥,生产者之间互斥,但是生产者和消费者之间不影响
    • 注意条件变量与互斥锁的顺序

    假设缓冲区大小为k,生产者、消费者线程若干。生产者和消费者相互等效,只要缓冲池未满,生产者便可将消息送入缓冲池;只要缓冲池未空,消费者便可从缓冲池中取走一个消息。

    items代表缓冲区已经使用的资源数,spaces代表缓冲区可用资源数
    mutex min,mout代表互斥锁
    Buf[k] 代表缓冲区,其内容类型为item
    in、out代表第一个资源和最后一个资源

    Semahore full,empty;
    full.value = 0 ,empty = k;
    Item Buff[k];
    Mutex min,mout;
    int in = 0,out = 0;
    
    producer {
        while(1) {
            produce(&item);
            P(empty);       // 等待缓冲区有空闲位置, 在使用PV操作时,条件变量需要在互斥锁之前
            P(min);         // 保证在product时不会有其他product访问缓冲区
    
            putitem(Buff,in,item);  // 将新资源放到buf[in]位置 
            in = ( in + 1 ) % k;
            
            V(min);   // 唤醒的顺序可以不同
            V(full);  // 通知consumer缓冲区有资源可以取走
        }
    }
    
    consumer {
        while(1) {
            P(full);        // 等待缓冲区有资源可以使用
            P(mout);        // 保证在consume时不会有其他consumer访问缓冲区
    
            getitem(Buff,out,&item);
            out = ( out + 1 ) % 10;
    
            V(mout);        // 唤醒的顺序可以不同
            V(empty);       // 通知缓冲区有空闲位置
    
            comsum(item);
        }
    }
    

     以上所谈,生产者和消费者之间不影响。接下来请看缓冲区互斥的情况。

    系统中有一组生产者进程和一组消费者进程,生产者进程每次生产一个产品放入缓冲区,消费者进程每次从缓冲区中取出一个产品并使用。(注:这里的“产品”理解为某种数据)

    •  生产者、消费者共享一个初始为空、大小为n的缓冲区。
    • 缓冲区没满→生产者生产
    • 只有缓冲区没满时,生产者才能把产品放入缓冲区,否则必须等待。
    • 缓冲区没空→消费者消费
    • 只有缓冲区不空时,消费者才能从中取出产品,否则必须等待。
    • 缓冲区是临界资源,各进程必须互斥地访问。

    semaphore mutex = 1;        //互斥信号量,实现对缓冲区的互斥访问
    semaphore empty =n;         //同步信号量,表示空闲缓冲区的数量
    semaphore full = 0;         //同步信号量,表示产品的数量,也即非空缓冲区的数量
    producer ( ) 
    { 
        while(1) 
        { 
            生产一个产品 ; 
            P ( empty) ;       //消耗一个空闲缓冲区
            P ( mutex) ;       //实现互斥是 在同一进程 中进行一对 PV 操作
            把产品放入缓冲区 ; 
            V(mutex) ; 
            V(full) ;          //增加一个产品
        };
    };
    
    consumer ( ) 
    { 
        while(1) 
        { 
            P ( full) ;        //消耗一个产品(非空缓冲区)
            P ( mutex) ; 
            从缓冲区取出一个产品 ; 
            V(mutex) ; 
            V(empty) ;         //增加一个空闲缓冲区
            使用产品 ; 
        };
    };

    能否改变相邻P、V操作的顺序?

    若此时缓冲区内已经放满产品,则empty=o,full=n。

    则生产者进程执行①使mutex变为0,再执行②,由于已没有空闲缓冲区,因此生产者被阻塞。由于生产者阻塞,因此切换回消费者进程。消费者进程执行③,由于mutex为0,即生产者还没释放对临界资源的“锁”,因此消费者也被阻塞。

    这就造成了生产者等待消费者释放空闲缓冲区,而消费者又等待生产者释放临界区的情况,生产者和消费者循环等待被对方唤醒,出现“死锁”。

    同样的,若缓冲区中没有产品,即full=0,empty=n。按③④①的顺序执行就会发生死锁。

    因此,实现互斥的P操作一定要在实现同步的P操作之后。

    V操作不会导致进程阻塞,因此两个V操作顺序可以交换


    二、读者写者问题

    问题描述:

    有读者和写者两组并发进程, 共享一个文件, 当两个或两个以上的读进程同时访问共享数据时不会 产生副作用, 但若某个写进程和其他进程(读进程或写进程) 同时访问共享数据时则可能导致数据 不一致的错误。 因此要求: ①允许多个读者可以同时对文件执行读操作; ②只允许一个写者往文件 中写信息; ③任一写者在完成写操作之前不允许其他读者或写者工作; ④写者执行写操作前, 应让 已有的读者和写者全部退出。

    两类进程: 写进程、 读进程

    互斥关系: 写进程 — 写进程、 写进程 — 读进程。 读进程与读进程不存在互斥问题。

     

    其核心思想在于设置了一个计数器count用来记录当前正在访问共享文件的读进程数。

    我们可以用count的值来判断当前进入的进程是否是第一个/最后一个读进程,从而做出不同的处理。

    另外,对count变量的检查和赋值不能一气呵成导致了一些错误,如果需要实现“一气呵成”,自然应该想到用互斥信号量

    最后,还要认真体会我们是如何解决“写进程饥饿”问题的。


    三、哲学家进餐问题

    问题描述:一张圆桌上坐着 5 名哲学家, 每两个哲学家之间的桌上摆一根筷子, 桌子的中间是一碗米饭。 哲学 家们倾注毕生的精力用于思考和进餐, 哲学家在思考时, 并不影响他人。 只有当哲学家饥饿时, 才试图拿起左、 右两根筷子(一根一根地拿起) 。 如果筷子已在他人手上, 则需等待。 饥饿的哲 学家只有同时拿起两根筷子才可以开始进餐, 当进餐完毕后, 放下筷子继续思考。

    由问题描述我们可以知道,一共有五个哲学家,也就是五个进程;五只筷子,也就是五个临界资源;因为哲学家想要进餐,必须要同时获得左边和右边的筷子,这就是要同时进入两个临界区(使用临界资源),才可以进餐。

     因为是五只筷子为临界资源,因此设置五个信号量即可。

    一个错误例子

    定义互斥信号量数组 mutex[5]={1,1,1,1,1} 用于实现对 5 个筷子的互斥访问。

    并对哲学家按 0~4 编号, 哲学家 i 左边 的筷子编号为 i , 右边的筷子编号为 ( i +1)%5 。

    semaphore mutex[5] = {1,1,1,1,1}; 		//初始化信号量
    
    void philosopher(int i){
      do {
        //thinking			//思考
        P(mutex[i]);        //判断哲学家左边的筷子是否可用
        P(mutex[(i+1)%5]);  //判断哲学家右边的筷子是否可用
        //...
        //eat		        //进餐
        //...
        V(mutex[i]);        //退出临界区,允许别的进程操作缓冲池
        V(mutex[(i+1)%5]);  //缓冲池中非空的缓冲区数量加1,可以唤醒等待的消费者进程
      }while(true);
    }
    

    我们来分析下上面的代码,首先我们从一个哲学家的角度来看问题,程序似乎是没有问题的,申请到左右两支筷子后,然后开始进餐。

    但是如果考虑到并发问题,五个哲学家同时拿起了左边的筷子,此时,五只筷子立刻都被占用了,没有可用的筷子了,当所有的哲学家再想拿起右边筷子的时候,因为临界资源不足,只能将自身阻塞,而所有的哲学家全部都会阻塞,并且不会释放自己手中拿着的左边的筷子,每位哲学家循环等待右边的人放下筷子(阻塞), 发生“死锁”。

    回顾避免死锁的四个条件;

    1. 循环等待条件 (互相持有资源而等待彼此的释放)
    2. 请求与保持条件
    3. 不可剥夺条件
    4. 互斥条件

    ​因为,为了解决五个哲学家争用的资源的问题,我们可以采用以下几种解决方法:

    至多只允许有四位哲学家同时去拿左边的筷子,最终能保证至少有一位哲学家能够进餐,并在用餐完毕后能释放他占用的筷子,从而使别的哲学家能够进餐;
    仅当哲学家的左、右两支筷子可用时,才允许他拿起筷子;
    ③ 规定奇数号哲学家先拿他左边的筷子,然后再去拿右边的筷子;而偶数号哲学家则相反。用这种方法可以保证如果相邻的两个奇偶号哲学家都想吃饭, 那么只会有其中一个可以拿起第一只筷子, 另一个会直接阻塞。 这就避免了占有一支后再等待另一只的情况。


    ​下面我们对每种方法给出哲学家进程的伪代码。

    解决哲学家进餐问题的三种方法

    方法一:控制哲学家就餐数量(破坏循环等待条件)

    对于方法一,至多只允许有四位哲学家同时去拿左边的筷子,我们可以简单的通过增加一个信号量实现,通过这个信号量限定哲学家并发去进餐的数量。

    semaphore mutex[5] = {1,1,1,1,1}; 		//初始化信号量
    semaphore count = 4;	//控制最多允许四位哲学家同时进餐
    
    void philosopher(int i){
      do {
        //thinking		//思考
        p(count);		//判断是否超过四人准备进餐
        P(mutex[i]);	//判断缓冲池中是否仍有空闲的缓冲区
        P(mutex[(i+1)%5]);//判断是否可以进入临界区(操作缓冲池)
        //...
        //eat			//进餐
        //...
        V(mutex[i]);//退出临界区,允许别的进程操作缓冲池
        V(mutex[(i+1)%5]);//缓冲池中非空的缓冲区数量加1,可以唤醒等待的消费者进程
        V(count);//用餐完毕,别的哲学家可以开始进餐
      }while(true);
    }
    

    方法二:同时拿起左右的叉子 (破坏请求与保持条件

    semaphore chopstick[5]={1,1,1,1,1}; 
    semaphore mutex = 1 ;            // 互斥地取筷子 
    Pi ( ) {                         //i 号哲学家的进程 
        while(1) 
        { 
            P ( mutex) ; 
            P ( chopstick[i] ) ;     // 拿左 
            P ( chopstick[ ( i+1) %5] ) ; // 拿右 
            V(mutex) ; 
            吃饭 … 
            V(chopstick[i] ) ;       // 放左 
            V(chopstick[ ( i+1) %5] ) ; // 放右 
            思考 … 
        } 
    }

    实际上,这种方法并不能保证 只有两边的筷子都可用时, 才允许哲学家拿起筷子。

    更准确的说法应该是 : 各哲学家拿筷子这件事 必须 互斥的执行 。这就保证了即使一个哲学家在拿筷子拿到一半时被阻塞, 也不会有别的哲学家会继续尝试拿筷子。 这样的话 ,当前正在吃饭的哲学家放下筷子后, 被 阻塞 的哲学家就可以获得等待的筷子了。

    第二种方法,也可以使用AND型信号量,同时对哲学家左右两边的筷子同时申请。下面是伪代码:

    semaphore mutex[5] = {1,1,1,1,1}; 		//初始化信号量
    
    void philosopher(int i){
      do {
        //thinking		//思考
        Swait(mutex[i], mutex[(i+1)%5]);//判断哲学家左边和右边的筷子是否同时可用
        //...
        //eat		
        //...
        Ssignal(mutex[i], mutex[(i+1)%5]);//进餐完毕,释放哲学家占有的筷子
      }while(true);
    }
    

    方法三:限定就餐策略 (破坏死锁的循环等待条件)

    对于第三种,需要在代码中添加个判断,来决定获取左、右筷子的顺序,其伪代码如下:

    semaphore mutex[5] = {1,1,1,1,1}; 		//初始化信号量
    
    void philosopher(int i){
      do {
        //thinking	
        if(i%2 == 1){
          P(mutex[i]);//判断哲学家左边的筷子是否可用
          P(mutex[(i+1)%5]);//判断哲学家右边的筷子是否可用
        }else{
          P(mutex[(i+1)%5]);//判断哲学家右边的筷子是否可用
          P(mutex[i]);//判断哲学家左边的筷子是否可用
        }
        //...
        //eat
        //...
        V(mutex[i]);//退出临界区,允许别的进程操作缓冲池
        V(mutex[(i+1)%5]);//缓冲池中非空的缓冲区数量加1,可以唤醒等待的消费者进程
      }while(true);
    }
    


    四、和尚打水问题(多生产者多消费者)

    问题描述:

    某寺庙,有小和尚和老和尚若干,有一个水缸,由小和尚提水入缸供老和尚饮用。水缸可以容纳10桶水,水取自同一口井中,由于水井口窄,每次只能容纳一个水桶取水。水桶总数为n个。每次入水、取水仅为一桶,且不可同时进行。

    信号量设置:

    1. 1.对于水缸——以一个水桶水为单位,empty=10、full = 0两个计数信号量
    2. 小和尚对缸操作:mutex-jar = 1二元信号量;
    3. 水桶个数(资源数):bucket = n计数信号量
    4. 取水操作(每次入水、取水仅为一桶):互斥mutex-well = 1二元信号量;

    伪代码:


    五、吃水果问题(多生产者多消费者)

    问题描述:桌上有一只盘子,最多可容纳一个水果,每次只能放入/取出一个水果。父亲专向盘子中放苹果(apple),母亲专向盘子中放橘子(orange),儿子专等吃盘子中的橘子,女儿专等吃盘子里的苹果。试设计信号量并使用P、V操作同步父,母、子、女进程。

    互斥关系: 对缓冲区(盘子) 的访问要互斥地进行

    同步关系 ( 一前一后) :

    • 1. 父亲将苹果放入盘子后, 女儿才能取苹果
    • 2. 母亲将橘子放入盘子后, 儿子才能取橘子
    • 3. 只有盘子为空时, 父亲或母亲才能放入水果 (“盘子为空”这个事件可以由儿子或女儿触 发, 事件发生后才允许父亲或母亲放水果)

    注:

    解决 “多生产者 - 多消费者问题”的关键在于理清复杂的同步关系。

    在分析同步问题(一前一后问题)的时候不能从单个进程行为的角度 来分析, 要把 “一前一后”发生 的事看做是两种 “事件” 的前后关系。

    比如, 如果从单个进程行为的角度来考虑的话, 我们会有以下结论:

    如果盘子里装有苹果, 那么一定要女儿取走苹果后父亲或母亲才能再放入水果。如果盘子里装有橘子, 那么一定要儿子取走橘子后父亲或母亲才能再放入水果。这么看是否就意味着要设置四个同步信号量分别实现这四个“一前一后”的关系了?

    正 确的分析方法应该 从“事件”的角度来考虑 , 我 们可以把上述 四对“进程行为的前后关系” 抽象为 一对事件的前后关系:盘子变空事件、放入水果事件。

    “盘子变空事件” 既 可由儿子引发, 也可由女儿引发 ; “放水果事件” 既 可能是父亲执行, 也可能是母亲执行。 这 样的话, 就可以用一个同步信号量解决问题了。

    semaphore mutex = 1 ; // 实现互斥访问盘子(缓冲区) 
    semaphore apple = 0 ; // 盘子中有几个苹果 
    semaphore orange = 0 ; // 盘子中有几个橘子 
    semaphore plate = 1 ; // 盘子中还可以放多少个水果

    思考:可不可以不 用互斥信号量mutex?

    结论: 即使不设置专门的互斥变量 mutex , 也不会出现多个进程同时访问盘子的现象。

    原因在于:本题中的缓冲区大小为1,在任何时刻,apple、orange、plate三个同步信号量中最多只有一个是1。因此在任何时刻,最多只有一个进程的P操作不会被阻塞,并顺利地进入临界区...

    如果缓冲区大小大于 1 , 就必须专门设置一个互斥信号量 mutex 来保证互斥访问缓冲区。

    将上面代码有mutex的删去即可。

    总结:

    在生产者 - 消费者问题中, 如果缓冲区大小为 1 , 那么有可能不需要设置互斥信号量就可以实现 互斥访问缓冲区的功能。

    当然, 这不是绝对的, 要具体问题具体分析。

    建议: 在考试中如果来不及仔细分析, 可以加上互斥信号量, 保证各进程一定会互斥地访问缓冲区。 但 需要注意的是, 实现互斥的P操作一定要在实现同步的P操作之后, 否则可能 引起 “ 死锁 。


    六、吸烟者问题(单生产者多消费者)

    问题描述:

    假设一个系统有三个抽烟者进程和一个供应者进程。每个抽烟者不停地卷烟并抽掉它,但是要卷起并抽掉一支烟,抽烟者需要有三种材料:烟草、纸和胶水。三个抽烟者中,第一个拥有烟草、第二个拥有纸、第三个拥有胶水。供应者进程无限地供三种材料,供应者每次将两种材料放桌子上,拥有剩下那种材料的抽烟者卷一根烟并抽掉它,并给供应者进程一个信号告诉完成了,供应者就会放另外两种材料再桌上,这个过程一直重复(让三个抽烟者轮流地抽烟)。

    可生产多种产品的单生产者以及多消费者问题。

    生产者可生产的产品一共有三种:

        组合一:纸+胶水;

        组合二:烟草+胶水;

        组合三:烟草+纸。

    互斥关系:桌子可以看作是一个容量为1的缓冲区,其访问是互斥的;

    同步关系:(从事件的角度来分析)

        桌上有组合一之后第一个抽烟者取走组合一;

        桌上有组合二之后第二个抽烟者取走组合二;

        桌上有组合三之后第三个抽烟者取走组合三;

        取走东西使用完成后供应者将下一个组合放到桌子上。

    伪代码:

    吸烟者问题可以为我们解决“可以生产多个产品的单生产者”问题提供一个思路。

    值得吸取的精华是: “轮流让各个吸烟者吸烟”必然需要“轮流的在桌上放上组合一、二、三”, 注 意体会我们是如何用一个整型变量 i 实现这个“轮流”过程的。

    如果题目改为“每次随机地让一个吸烟者吸烟”, 我们有应该如何用代码写出这个逻辑呢? random

    若一个生产者要生产多种产品(或者说会引发多种前驱事件), 那么各个V操作应该放在各自对应的 “事件” 发生之后的位置。


    七、理发师睡觉理发(单生产者多消费者)

    问题描述:

    假设有一个理发店只有一个理发师,一张理发时坐的椅子,若干张普通椅子顾客供等候时坐。没有顾客时,理发师就坐在理发的椅子上睡觉。顾客一到,他不是叫醒理发师,就是离开。如果理发师没有睡觉,而在为别人理发,他就会坐下来等候。如果所有的椅子都坐满了人,最后来的顾客就会离开。 

    在出现竞争的情况下问题就来了,这和其它的排队问题是一样的。实际上,与哲学家就餐问题是一样的。如果没有适当的解决方案,就会导致进程之间的“饿肚子”和“死锁”。 
    如理发师在等一位顾客,顾客在等理发师,进而造成死锁。另外,有的顾客可能也不愿按顺序等候,会让一些在等待的顾客永远都不能理发。

    解决方案:
    最常见的解决方案就是使用三个信号量(Semaphore):

    一个给顾客信号量,一个理发师信号量(看他自己是不是闲着),第三个是互斥信号量(Mutual exclusion,缩写成mutex)。

    一位顾客来了,他想拿到互斥信号量,他就等着直到拿到为止。顾客拿到互斥信号量后,会去查看是否有空着的椅子(可能是等候的椅子,也可能是理发时坐的那张椅子)。 
    如果没有一张是空着的,他就走了。如果他找到了一张椅子,就会让空椅子的数量减少一张,这位顾客接下来就使用自己的信号量叫醒理发师。

    这样,互斥信号标就释放出来供其他顾客或理发师使用。如果理发师在忙,这位顾客就会等。理发师就会进入了一个永久的等候循环,等着被在等候的顾客唤醒。一旦他醒过来,他会给所有在等候的顾客发信号,让他们依次理发。
     

    semaphore customers = 0; 
    semaphore barbers = 0;  
    semaphore mutex = 1;  // 椅子是理发师和顾客进程都可以访问的临界区 
    int chair = N;       //所有的椅子数量  
    
    cobegin
    process barber(){  
        While(true){        //持续不断地循环  
              P(customers); //试图为一位顾客服务,如果没有他就睡觉(进程阻塞)  
              P(mutex);     //如果有顾客,这时他被叫醒(理发师进程被唤醒),要修改空椅子的数量  
              chair++;      //一张椅子空了出来  
              V(barbers);  //现在有一个醒着的理发师,理发师准备理发.
                           //多个顾客可以竞争理发师互斥量,但是只有一个顾客进程被唤醒并得到服务  
              V(mutex);   //释放椅子互斥量,使得进店的顾客可以访问椅子的数量以决定是否进店等待 
              cut_hair();
        }  
    }
    
    process customer_i(){   
        P(mutex);     //想坐到一张椅子上  
        if (chair > 0){ 
            chair--;        //顾客坐到一张椅子上了  
            V(customers);   //通知理发师,有一位顾客来了  
            V(mutex);       //顾客已经坐在椅子上等待了,访问椅子结束,释放互斥量  
            P(barbers);     //该这位顾客理发了,如果理发师还在忙,那么他就等着(顾客进程阻塞)  
            get_haircut();  //顾客坐下剪头~
        }
        else  
            V(mutex);       //不要忘记释放被锁定的椅子,没椅子,顾客跑了。 
    }
    coend


    PV 操作题目的解题思路

    1. 关系分析。 找出题目中描述的各个进程, 分析它们之间的同步、 互斥关系。

    2. 整理思路。 根据各进程的操作流程确定P、 V操作的大致顺序。

    3. 设置信号量。 设置需要的信号量, 并根据题目条件确定信号量初值。 (互斥信号量初值一般为 1 , 同步信号量的初始值要看对应资源的初始值是多少) 


    哲学家进餐问题参考来源经典的进程同步问题-----哲学家进餐问题详解_丹丹的后花园-CSDN博客_哲学家就餐问题

    展开全文
  • 操作系统经典例题

    千次阅读 多人点赞 2020-12-27 17:37:28
    由于上课的例题大部分练的都是消费者-生产者问题,哲学家进餐问题与读者-写者问题就不提了。 3.生产者-消费者问题变种 磁盘->pa->缓冲区1->pb->缓冲区2->pc 4.生产者同步问题 第三章处理机调度与...
  • 主宰操作系统经典算法

    万次阅读 多人点赞 2020-07-24 15:22:50
    此篇文章带你梳理一下操作系统中都出现过哪些算法 进程和线程管理中的算法 进程和线程在调度时候出现过很多算法,这些算法的设计背景是当一个计算机是多道程序设计系统时,会频繁的有很多进程或者线程来同时竞争 ...
  • 操作系统经典进程同步问题 一、生产者-消费者问题 1.问题描述:生产者-消费者模型描述的是有一群生产者进程在生产产品,并将这些产品提供给消费者进程并发进行,具备并发程序的典型特征。PCM为使生产者进程和消费...
  • 由浅入深介绍现代操作系统经典理论与方法,结合前沿研究与工业界实践,面向真实场景与真实问题。全新打造 ChCore 微内核系列课程实验,建立对操作系统的第一手实践经验。 这本被称为神书的《深入理解计算机系统》,...
  • 操作系统面试问题汇总(超详细)

    万次阅读 多人点赞 2019-10-04 20:18:32
    操作系统的组成 1、驱动程序是最底层的、直接控制和监视各类硬件的部分,它们的职责是隐藏硬件的具体细节,并向其他部分提供一个抽象的、通用的接口。 2、内核是操作系统之最内核部分,通常运行在最高特权级,负责...
  • /*理发(非临界区操作)*/ } } void customers(void) { down(mutex);/*进入临界区*/ if(waiting ) {/*如果没有空椅子,就离开*/ waiting = waiting + 1;/*等待顾客数加1*/ up(customers); /*...
  • 面试中操作系统常见问题总结

    万次阅读 多人点赞 2018-08-20 23:21:16
    1、操作系统的四个特性 并发:同一段时间内多个程序执行(注意区别并行和并发,并行是同一时刻的多个事件,并发是同一时间段内的多个事件) 共享:系统中的资源可以被内存中多个并发执行的进线程共同使用 ...
  • 操作系统经典PV操作题目

    千次阅读 2021-05-01 22:06:03
    5个经典PV操作题(附答案) 三个进程之间的同步 pv操作经典习题 生产者和消费者 生产者消费者问题 当只有一个生产者和一个消费者的时候,且只有一个缓冲区 要考虑生产者和消费者两个进程的互斥,还有生产者和消费者...
  • 面试/笔试第二弹 —— 操作系统面试问题集锦

    万次阅读 多人点赞 2017-10-21 16:08:50
    本文对面试/笔试过程中经常会被问到的一些关于操作系统问题进行了梳理和总结,一方面方便自己温故知新,另一方面也希望为找工作的同学们提供一个复习参考。关于这块内容的初步了解和整体掌握,建议大家读一读...
  • 实时操作系统(RTOS)是指当外界事件或数据产生时,能够接受并以足够快的速度予以处理,其处理的结果又能在规定的时间之内来控制生产过程或对处理系统作出快速响应,并控制所有实时任务协调一致运行的操作系统。...
  • 大学操作系统期末考试复习经典计算题快速回顾

    千次阅读 多人点赞 2021-03-19 12:59:07
    操作系统期末考试经典计算题(共八道,建议收藏) 1.银行家算法 在银行家算法的例子中,如果出现下述资源分配情况,试问: Process  Allcation   Need   Available P0    0 0 3 2   0 0 1 2   1 6 2...
  • 试用P、V操作实现爸爸、儿子、女儿三个并发进程的同步。 提示:设置一个信号量表示可否向盘中放水果,一个信号量表示可否取桔子,一个信号量表示可否取苹果。 实验目的: 深入掌握进程、线程同步机制——信号量机制...
  • 在进程同步中,经典的同步问题有:生产者-消费者问题、读者-写者问题、哲学家进餐问题。 一、生产者与消费者问题问题描述:使用一个缓冲区来保存物品,只有缓冲区没有满,生产者才可以放入物品;只有缓冲区不为...
  • 操作系统课程设计

    千次阅读 热门讨论 2020-06-05 13:23:36
    操作系统课程设计汇总 来源:网络收集 这次海轰选择是题目二,感觉有点难,得费一点时间 其他的题目以后有时间可以尝试一下 再不写C++,就快凉了 题目一:支持多个进程(线程)并发运行的简单进程(线程)管理模拟...
  • 操作系统_生产者消费者问题

    千次阅读 多人点赞 2020-03-17 21:29:53
    1,生产者消费者问题 问题的提出 初步思考 进程资源共享关系和同步关系分析 问题的具体解决 第一搏 存在的问题 第二搏 多维度思考 1,单生产者、单消费者、多缓冲区 2,多生产者、多消费者、单缓冲 3,单...
  • 现代操作系统第三版高清

    千次下载 热门讨论 2015-06-16 22:20:01
     5.8.2 操作系统问题236  5.8.3 应用程序问题239  5.9 有关输入/输出的研究239  5.10 小结240  习题241  第6章 死锁244  6.1 资源244  6.1.1 可抢占资源和不可抢占资源244  6.1.2 资源获取245  6.2 死锁...
  • 操作系统中PV操作之顾客理发师问题

    万次阅读 多人点赞 2018-03-27 17:40:04
    0,进程被唤醒理发师问题 一个理发师,一把理发椅,n把等候理发的顾客椅子,如果没有顾客则理发师便在理发椅上睡觉 ,当有一个顾客到达时,首先看理发师在干什么,如果理发师在睡觉,则唤醒理发师理发,如果理发师...
  • 在讲解PV操作之前,需要先明白PV操作用来解决什么问题? PV操作用以解决进程间的互斥问题 eg:火车售票问题 。以下就会出现BUG,假设当 x = 1时,如果 p1 , p2 , 同时执行,那么相当于票数为1的这张票售卖两次,这...
  • 操作系统同步互斥问题

    千次阅读 2018-09-29 16:38:08
    一些经典的例子就不列举了,接下来讲一些在学习操作系统课程的过程中所遇到的几个进程同步的题目。 1.取放水果问题 用基本记录型信号量解决如下同步关系:一空盘放一水果,父放梨,母放橘,儿取梨,女取橘,四人如何...
  • 基础了解的信息铺垫是关于使用mutex作为锁实现的核心,那就是原子操作P(wait)和V(singal)的作用及含义。 - P是操作就是使得信号量Semophore的数量减一,当然了前提是信号量的大小是大于0的,如果小于等于0,此...
  • 分时操作系统(20世纪70年代)

    千次阅读 2021-07-18 09:10:00
    多道批处理操作系统的出现使计算机的效率(主要是吞吐率)大大提高。不过这时人们又提出了另外一个问题:将程序制作在卡片上交给计算机管理员来统一运行,将使得用户无法即时获知程序运行的结果。而这是一个大问题。...
  • 操作系统的各种锁

    千次阅读 2020-09-09 11:09:01
    LockOne类的协议看起来挺朴实的,但是存在一个问题:当两个线程都把旗帜升起来,然后等待对方的旗帜降下来就会出现死锁的状态(两个线程都在那傻乎乎的等待对方的旗帜降下来,直到天荒地老:)) LockTwo类 观察LockOne...
  • 操作系统5————进程同步的经典问题:司机售票员&amp;amp;amp;amp;amp;问题生产者消费者问题&amp;amp;amp;amp;amp;哲学家进餐问题&amp;amp;amp;amp;amp;读者写者问题 一. 目录 操作系统...
  • 允许对个进程同属进行读取一个共享对象,因此读操作不会造成数据数据文件的混乱,但不允许reader,writer进行同时对共享文件的访问,因为这种访问会造成文件的数据混乱。所谓读者-写者问题。 读者-写者问题中,读者...
  • Java实现生产者-消费者问题解决方案实验

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 258,779
精华内容 103,511
关键字:

操作系统经典问题