精华内容
下载资源
问答
  • 实验四 同步与互斥 实验目的和要求 1掌握进程线程的同步与互斥 2掌握生产者消费者问题的实现方法 3掌握多线程编程方法 实验内容 实现生产者消费者问题 1有一个仓库生产者负责生产产品并放入仓库消费者会从仓库中拿走...
  • 主要介绍了Python实现的多线程同步与互斥锁功能,涉及Python多线程及锁机制相关操作技巧,需要的朋友可以参考下
  • 实验四 同步与互斥 实验目的和要求 1掌握进程线程的同步与互斥 2 掌握生产者消费者问题的实现方法 3掌握多线程编程方法 实验内容 实现生产者消费者问题 1有一个仓库生产者负责生产产品并放入仓库消费者会从仓库中拿...
  • 操作系统中P、V操作实现进程的同步与互斥
  • 大连理工大学操作系统大作业, 进程同步与互斥 生产者消费者问题
  • 1)实验准备 要实验的Windows下的多线程实验,应做如下准备: a) 在新建中选”Win32 Console Application”->An empty project b) 选”工程”->”设置”选项,在”设置”中选择“C/C++”标签,在”Project Option”中...
  • 进程的同步与互斥问题总结.doc
  • 进程同步与互斥

    2013-12-19 10:17:14
    有关于进程同步互斥的C语言实现,希望对你们有帮助!
  • 进程的同步与互斥习题(含部分题目的参考答案).doc
  • 在本篇文章里小编给大家整理的是关于linux线程间的同步与互斥的相关知识点,有兴趣的朋友们学习下。
  • Java实现的进程同步与互斥(PV) Hao语言
  • 用java实现多线程并发中的读者写者问题,能够实现多线程对临界资源的同步有序访问。 具体实现为: 给定一个队列A[1-10][1-100000]、元素编号1-10,其中每个元素包含10万个随机数。创建若干个线程,各循环100次;...
  • 进程同步与互斥C++

    2012-02-10 22:16:23
    进程同步与互斥,C++实现,附详细注释,可用于课程设计
  • P、V操作实现进程同步与互斥是《操作系统》教学中的一个难点,通过示例给出了解决这类问题的一般模型。
  • 实验-进程同步与互斥

    2021-07-02 09:37:52
    在Visual C++ 6.0集成开发环境下使用C语言,利用相应的Win32 API函数,以生产者/消费者模型为依据,创建一个控制台进程,在该进程中创建n个进程模拟生产者和消费者,实现进程的同步与互斥。 3.实验原理提示 进程数据...

    实验内容:
    1.实验目的和要求

    (1)理解生产者/消费者模型及其同步/互斥规则。
    (2)了解Windows同步对象及其特性。
    (3)熟悉实验环境,掌握相关API的使用方法。
    (4)设计程序,实现生产者/消费者进程的同步与互斥。

    2.实监内容
    在Visual C++ 6.0集成开发环境下使用C语言,利用相应的Win32 API函数,以生产者/消费者模型为依据,创建一个控制台进程,在该进程中创建n个进程模拟生产者和消费者,实现进程的同步与互斥。
    3.实验原理与提示
    进程数据结构:每个进程有一个进程控制块(PCB)表示。进程控制块可以包含如下信息:进程类型标号,进程系统号,进程状态(本程序未用),进程产品(字符),进程链指针等。系统开辟了一个缓冲区,大小由buffersize指定。程序中有三个链队列,一个链表。一个就绪队列(ready),两个等待队列:生产者等待队列( producer);消费者等待队列(consumer)。一个链表(over),用于收集已经运行结束的进程。
    本程序通过函数模拟信号量的原子操作。
    算法的文字描述:

    (1由用户指定要产生的进程及其类别,存入就绪队列。
    (2)调度程序从就绪队列中提取一个就绪进程运行,如果申请的资源不存在则进入相应的等待队列,调度程序调度就绪队列中的下一个进程﹔进程运行结束时,会检查相应的等待队列,激活等待队列中的进程进入就绪队列;运行结束的进程进人over链表。重复这一过程直至就绪队列为空。
    (3)程序询问是否要继续?如果要继续转至(1)开始执行,否则退出程序。

    参考代码

    
    #include <stdio.h>
    #include <malloc.h>
    #define buffersize 5						//假设有5个缓冲区
    int processnum=0;							//初始化产品数量
    struct pcb									/* 定义进程控制块PCB*/	
    {
    	int flag;
    	int numlabel;
    	char product;
    	char state;
    	struct pcb*processlink;
    }*exe=NULL,*over=NULL;
    typedef struct pcb PCB;
    PCB* readyhead=NULL,* readytail=NULL;
    PCB* consumerhead=NULL,* consumertail=NULL;
    PCB* producerhead=NULL,* producertail=NULL;
    int productnum=0;												//产品数量
    int full=0,empty=buffersize;									//信号量
    char buffer[buffersize];										//缓冲区
    int bufferpoint=0;												//缓冲区指针
    void linklist(PCB * p,PCB* listhead)							//创建就绪队列
    {
    	PCB*cursor=listhead;
    	while(cursor->processlink!=NULL){
    		cursor=cursor->processlink;
    	}
    	cursor->processlink=p;
    }
    void freelink(PCB* linkhead)
    {
    	PCB* p;
    	while(linkhead!=NULL)
    	{
    		p=linkhead;
    		linkhead=linkhead->processlink;
    		free(p);
    	}
    }
    void linkqueue(PCB* process,PCB** tail)				//初始化队列
    {
    	if((*tail)!=NULL)
    	{
    		(*tail)->processlink=process;
    		(*tail)=process;
    	}
    	else{printf("队列未初始化!");}
    }
    PCB* getq(PCB*head,PCB** tail)
    {
    	PCB* p;
    	p=head->processlink;
    	if(p!=NULL)
    	{
    		head->processlink=p->processlink;
    		p->processlink=NULL;
    		if(head->processlink == NULL) (* tail)=head;
    	}
    	else return NULL;
    	return p;
    }
    bool processproc()											//初始化进程
    {
    	int i,f,num;
    	char ch;
    	PCB* p=NULL;
    	PCB** p1=NULL;
    	printf("\n 请输入希望产生的进程个数:");
    	scanf("%d",&num);
    	getchar();
    	for(i=0;i<num;i++)
    	{
    		printf("\n请输入您要产生的进程:输入 1为生产者进程;输入2为消费者进程\n");
    		scanf("%d",&f);
    		getchar();
    		p=(PCB* )malloc(sizeof(PCB));
    		if(!p){printf("内存分配失败");return false;}
    		p->flag=f;
    		processnum++;
    		p->numlabel=processnum;
    		p->state='w';
    		p->processlink=NULL;
    		if(p->flag==1)
    		{
    			printf("您要产生的进程是生产者,它是第%d个进程。请您输入您要该进程产生的字符:\n",processnum);
    			scanf("%c",&ch);
    			getchar();
    			p->product=ch;
    			productnum++;
    			printf("您要该进程产生的字符是%c\n",p->product);
    		}
    		else{printf("您要产生的进程是消费者,它是第%d个进程。\n",p->numlabel);}
    		linkqueue(p,&readytail);
    	}
    	return true;
    }
    bool hasElement(PCB* pro)							//判断队列中是否有进程存在
    {
    	if(pro->processlink== NULL) return false;
    	else return true;
    }
    bool waitempty()										//判断生产者等待队列是否为空
    {
    	if(empty<=0)
    	{
    		printf("进程%d:缓冲区存数,缓冲区满,该进程进入生产者等待队列\n",exe->numlabel);
    		linkqueue(exe,&producertail);
    		return false;
    	}
    	else{empty--; return true;}
    }
    void signalempty()											//唤醒生产者进程
    {
    	PCB* p;
    	if(hasElement(producerhead)){
    		p=getq(producerhead,&producertail);
    		linkqueue(p,&readytail);
    		printf("等待中的生产者进程进入就绪队列,它的进程号是%d\n",p->numlabel);
    	}
    	empty++;
    }
    bool waitfull()										//判断消费者等待队列是否为满
    {
    	if(full<=0)
    	{
    		printf("进程%d缓冲区取数,缓冲区空,该进程进入消费者等待队列\n",exe->numlabel);
    		linkqueue(exe,&consumertail);
    		return false;
    	}
    	else{ full--;  return true;}
    }
    void signalfull()									//唤醒消费者进程
    {
    	PCB* p;
    	if(hasElement(consumerhead)){
    		p=getq(consumerhead,&consumertail);
    		linkqueue(p,&readytail);
    		printf("等待中的消费者进程进入就绪队列,它的进程号是%d\n",p->numlabel);
    	}
    	full++;
    }
    void producerrun()						//生产者进程
    {
    	if(!waitempty()) return;
    	printf("进程%d开始向缓冲区存数%c\n",exe->numlabel,exe->product);
    	buffer[bufferpoint]=exe->product;
    	bufferpoint++;
    	printf("进程%d向缓冲区存数操作结束\n",exe->numlabel);
    	signalfull();
    	linklist(exe,over);
    }
    void comsuerrun()						//消费者进程
    {
    	if(!waitfull()) return;
    	printf("进程%d开始向缓冲区取数\n",exe->numlabel);
    	exe->product=buffer[bufferpoint-1];
    	bufferpoint--;
    	printf("进程%d向缓冲区取数操作结束,取数是%c\n",exe->numlabel,exe->product);
    	signalempty();
    	linklist(exe,over);
    }
    void display(PCB* p)								//显示进程
    {
    	p=p->processlink;
    	while(p!=NULL){
    		printf("进程%d,它是一个",p->numlabel);
    		p->flag==1? printf("生产者\n"):printf("消费者\n");
    		p=p->processlink;
    	}
    }
    void main()
    {
    	char terminate;
    	bool element;
    	printf("你想开始程序吗?(y/n)");
    	scanf("%c",&terminate);
    	getchar();
    	readyhead=(PCB* )malloc(sizeof(PCB));			//初始化队列
    	if(readyhead ==NULL) return;
    
    		readytail=readyhead;
    		readyhead->flag=3;
    		readyhead->numlabel=processnum;
    		readyhead->state='w';
    		readyhead->processlink=NULL;
    		consumerhead=(PCB* )malloc(sizeof(PCB));
    		if(consumerhead==NULL) return;
    		consumertail=consumerhead;
    		consumerhead->processlink=NULL;
    		consumerhead->flag=4;
    		consumerhead->numlabel=processnum;
    		consumerhead->state='w';
    		consumerhead->processlink=NULL;
    		producerhead=(PCB*)malloc(sizeof(PCB));
    		if(producerhead==NULL) return;
    		producertail=producerhead;
    		producerhead->processlink=NULL;
    		producerhead->flag=5;
    		producerhead->numlabel=processnum;
    		producerhead->state='w';
    		producerhead->processlink=NULL;
    		over=(PCB*)malloc(sizeof(PCB));
    		if(over==NULL)return;
    		over->processlink=NULL;
    		while(terminate=='y')
    		{
    			if(!processproc()) break;
    			element=hasElement(readyhead);
    			while(element){
    				exe=getq(readyhead,&readytail);
    				printf("进程%d申请运行,它是一个",exe->numlabel);
    				exe->flag==1? printf("生产者\n"):printf("消费者\n");
    				if(exe->flag==1) producerrun();
    				else comsuerrun();
    				element=hasElement(readyhead);
    			}
    			printf("就绪队列没有进程\n");
    			if(hasElement(consumerhead))
    			{
    				printf("就绪队列没有进程\n");
    				if(hasElement(consumerhead))
    				{
    					printf("消费者等待队列中有进程:\n");
    					display(consumerhead);
    				}
    				else {printf("消费者等待队列中没有进程\n");}
    				if(hasElement(producerhead))
    				{
    					printf("生产者等待队列中有进程:\n");
    					display(producerhead);
    				}
    				else{
    					printf("生产者等待队列中没有进程\n");
    				}
    				printf("你想继续吗?(press 'y'for on)");
    				scanf("%c",&terminate);
    				getchar();
    			}
    			printf("\n\n进程模拟完成.\n");
    			freelink(over);							//释放空间
    			over=NULL;
    			freelink(readyhead);
    			readyhead=NULL;
    			readytail=NULL;
    			freelink(consumerhead);
    			consumerhead=NULL;
    			consumertail=NULL;
    			freelink(producerhead);
    			producerhead=NULL;
    			producertail=NULL;
    			getchar();
    		}
    }
    

    实验结果:
    在这里插入图片描述

    展开全文
  • 这里写目录标题概览临界区临界区的引入临界区的概念进程的同步与互斥的概念解决方法经典同步与互斥问题 概览 临界区 临界区的引入 在系统当中,有些资源允许多个进程共享(磁盘),有些资源只允许进程单独使用...

    概览

    在这里插入图片描述

    临界区
    临界区的引入

    在系统当中,有些资源允许多个进程共享(磁盘),有些资源只允许进程单独使用(打印机,共享变量)。为了让进程单独使用资源而不受其他进程干扰引入了临界区的概念。

    临界区的概念

    在一段时间内只允许一个时间段使用的资源成为临界资源,每个进程访问资源的那段程序称为临界区。
    在这里插入图片描述

    如图进程访问临界区的一般结构
    1.进入区:检查临界资源是否已经被访问,如果临界资源已经被访问,该进程不能进入。
    2.临界区:在临界区做操作
    3.退出区:清除临界区被占用的标志
    4.剩余区:进程与临界区不相关部分的代码
    举个例子
    在这里插入图片描述
    用Bernstein条件考察以上两个进程。
    P1的读集和写集分别是R(P1 ) =(R1,COUNT) 、W(P1) =(R1,COUNT) ; P2 的读集和写集为R(P2)=(R2,count),W(P2) =(R2,COUNT), 而R(P1)交W(P2)不等于空集,所以P1,P2不能并发执行,不符合Bernstein条件, 因此, 必须对进程P1, 和P2, 的执行施加某种限制,否则P1,和P2,将无法并发执行。也就是说,P1,和P2,两个进程在执行时必须等一个进程执行完毕, 另一个进程才可以执行。在这里, 变量COUNT是一个临界资源, P1和P2的两个程序段是临界区。

    • 临界区的进出原则
      空闲让进:没有进程进去临界区,临界资源处于空闲,则允许进程进入。
      忙则等待:已有进程进入临界区时,临界资源已被访问,其他进程进入必须等待。也就是说,没有两个进程能同时在临界区执行。
      有限等待:对于请求访问临界资源的进程,应保证有效的时间内允许进程,避免“死等”,产生饥饿。
      让权等待:当进程不能进入临界区时,应立即释放处理机,米面其他进程“忙等”
    进程的同步与互斥的概念
    • 同步

    进程同步是指多个进程中发生的事件存在某种时序关系,必须协同动作共同完成一个任务。简单来讲同步是一种协作关系。
    举几个例子:
    当两个进程运行时,进程A需要获取进程B此时运行到某一步的运行结果或者信息,才能进行自己的下一步工作,这个时候就得等待进程B与自己通信(发送某一个消息或信号),进程A再继续执行。这种进程之间相互等待对方发送消息或信号的协作就叫做进程同步。或者工厂的流水线,每道工序都有自己特定的任务,前一道工序没有完成或不合格后一道工序就不能进行。再或者ABC三个进程分别负责输入、处理、输出数据,A必须先执行,B次之,最后C。

    • 互斥

    多个进程在运行过程中,都需要某一个资源时,它们便产生了竞争关系,它们可能竞争某一块内存空间,也可能竞争某一个IO设备。当一方获取资源时,其他进程只能在该进程释放资源之后 才能去访问该资源,这就是进程互斥。简单来说,互斥是一种竞争关系。
    举例:假如多个进程同时申请一台打印机,而先申请打印机的一方先使用打印机,当它用完时在给其他进程使用。在一个进程使用打印机期间,其他进程对打印机的使用申请不予满足,这些进程必须等待。

    解决方法
    • 进程同步与互斥的软件实现方法
      (1)单标志法:两个进程在访问完临界区后会把使用的权限转交给另一个进程,也就是说每个进程进入临界区的权限只能被另一个临界区赋予。
      在这里插入图片描述
      如图,turn作为标识,turn=0时,执行P0,P1什么也不做。P0执行完后turn=1,则执行P1,P0不执行。
      缺点:不能保证空闲让进。拿澡堂洗澡举例,P0进入卫生间洗澡当洗完时,P1并不知道P0洗完了,这就造成资源极大浪费。
      (2)双标志先检查法:设置一个布尔型数组flag[],数组中各个元素用来标记各进程想进入临界区的意愿,比如“flag[0] = true”意味着0号进程P0现在想要进入临界区。
      如图:
      在这里插入图片描述
      假设初始时,flag【0】为true,则说明P0进入临界区,此时P1接受到消息P0进入临界区了就什么也不做。P0执行完后,进程p1访问,进入临界区前也传达信息p1进入临界区。
      洗澡的例子:若P0洗澡,则对外开一个指示灯,表示此卫生间有人,则需等待指示灯灭时方可进入。解决了空闲让进的问题,避免资源浪费。
      缺点:假设初始flag都为false,则两个进程同时进入临界区,不符合忙则等待条件。
      (3)双标志先修改后检查法:双标志先检查法得改版,前一个算法的问题是先检查后上锁,但是这两个操作又无法一气呵成,因此导致了两个进程同时进入临界区的问题。因此,人们又想到了先“上锁”,后检查的方法,来避免上述问题。但有可能导致两个进程都无法进入临界区的问题。
      如图:
      在这里插入图片描述
      例子:这就相当于提前声明。p0说我先洗,p1让给p0,等p0执行完后在执行p1.但若是两个都过分谦让,哈哈,两个人就都没有进,资源就会被浪费。

    (4)Peterson算法(先修改,后检查,后修改者等待算法):双标志后检查法中,两个进程都争着想进入临界区,但是谁也不让谁,最后谁都无法进入临界区。Peterson想到了一种方法,如果双方都争着想进入临界区,那可以让进程尝试“孔融让梨”,主动让对方先使用临界区。
    结合算法(1)和算法(3)的概念, 标志flag[0] 为true表示进程P。想进入临界区, 标志turn表示要在进人区等待进程标识。在进入区先修改后检查, 通过修改同一标志turn来描述标志修改的先后; 检查对方标志flag, 如果对方不想进人, 自己再进人。如果对方想进人, 则检查标志turn, 由于turn中保存的是较晚的一次赋值, 因此较晚修改标志的进程等待, 较早修改标志的进程进入临界区,如图3-8所示。
    在这里插入图片描述

    • 信号量和PV操作
      1.定义和执行过程
      荷兰计算机科学家Dijkstra于1965年提出了解决进程同步与互斥问题的信号量机制,收到了很好的效果,被一直沿用至今,广泛应用与单处理机和多处理机系统以及计算机网络中。信号量机制就是说两个或者多个进程通过他们都可以利用的一个或多个信号来实现准确无误不冲突的并发执行。如果临界资源不够,就会有一个信号表示出来,如果进程此时想访问,那么就会阻塞到一个队列中,等待调度。当临界资源使用完毕,一个进程改变信号,并及时唤醒阻塞的进程,这就实现了进程间的同步和互斥问题。
      信号量分为整型信号量,记录型信号量,AND信号量以及信号量集。最初的信号量就是整型信号量,定义信号量为一个整型变量,仅能通过两个原子操作P,V来访问,所谓原子操作就是指一组相联的操作要么不间断地执行,要么不执行。这两个操作又称为wait和signal操作或者down和up操作。之所以叫P,V操作是因为Dijkstra是荷兰人,P指的是荷兰语中的“proberen”,意为“测试”,而V指的是荷兰语中的“verhogen”,意为“增加”。
      Dijkstra最初定义的信号量包括一个整型值S和一个等待队列S.queue,信号量只能通过两个原语P、V操作来访问它,信号量的定义如下:
    srtuct semaphore{
    int value;
    struct PCB *queue;
    }
    

    P原语执行的操作:

    void wait(semaphore s)
    {
     s.value=s.value-1;
     if(s.value<0)
       block(s.queue);
    }
    /*过程说明
    *首先将S.value减1,表示该进程需要一个临界资源,如果S.value<0,那么说明原来的S.value <= 0,即已经没有资源可用了,于是将进程阻塞到与信号量S相关的阻塞队列中去,如果S.value<0,那么|S.value|其实就表示阻塞队列的长度,即等待使用资源的进程数量。*/
    

    V原语执行的操作:

    void signal(semaphore s)
    {
     s.value=s.value+1;
     if(s.value<=0)
       wakeup(s.queue);
    }
    /*过程说明
    *V操作:首先S.value加1,表示释放一个资源,如果S.value <= 0,那么说明原来的S.value < 0,阻塞队列中是由进程的,于是唤醒该队列中的一个进程。那么,为什么S.value > 0时不唤醒进程呢,很简单,因为阻塞队列中没有进程了。*/
    

    P操作相当于“等待一个信号”,而V操作相当于“发送一个信号”,在实现同步过程中,V操作相当于发送一个信号说合作者已经完成了某项任务,在实现互斥过程中,V操作相当于发送一个信号说临界资源可用了。实际上,在实现互斥时,P,V操作相当于申请资源和释放资源。
    2.用信号量解决同步与互斥
    用信号量解决互斥问题
    如果信号量的初值为1,定义mutex为互斥信号量,P1P2两进程共享变量count。那么互斥实现过程如下图。
    在这里插入图片描述
    如此,P1在执行的过程中,P2不能执行,p1p2无论按照怎样的次序进行。count值都为7.
    用信号量解决同步问题
    如图,有4个并发的进程,即P1P2P3P4,它们之间的关系是p1先被执行,p1执行完p2p3在执行,p2执行完后p4在执行。
    在这里插入图片描述
    同步执行过程
    在这里插入图片描述

    经典同步与互斥问题
    • 死锁与饥饿
      具有等待队列的信号量的实现可能导致这样的情况:两个或多个进程无限地等待一个事件, 而该事件只能由这些等待进程之一来产生。这里的事件是signal() 操作的执行。当出现这样的状态时, 这些进程就称为死锁(deadlocked) 。
      举例:
      在这里插入图片描述
      如图,假设P0 执行wait(S) , 接着P1执行wait(Q) 。当P0执行wait(Q) 时, 它必须等待,直到P1执行signal(Q).类似地, 当P1执行wait(S) , 它必等待, 直到Po执行signal(S) 。这两个操作不能同时执行,所以P0和P1死锁。
      与死锁相关的另一个问题程是无限阻塞或饥饿,即进程在信号量内无限期等待。如果对与信号量相关的链表按LIFO顺序来增加和移动进程,那么可能会发生无限期阻塞。
    • AND信号量的引入
      当利用信号量解决单个资源的互斥访问后,用信号量解决就显得十分有效。但是对于多个资源呢?我们先简单分析一下。在有些应用中,一个进程需要先获得两个或更多共享资源后方能执行其任务。假如有两
      个进程P1和P 2, 它们要共享两个全局变量R1和R2, 为此要设置两个互斥信号量mutex1和mutex2, 并令它们的初值为1; 相应地, 两个进程都要包含对信号量mutex1和mutex2的操作,假如操作如下。
      在这里插入图片描述
      如果进程P1和P2,交替地执行P操作,则具体情况如下。
      (1) 进程P1执行P(mutex1) , 于是mutex1=0。
      (2) 进程P2执行P(mutex2 ) , 于是mutex 2=0。
      (3) 进程P1 执行P(mutex 2) , 于是mutex 2=-1, 进程P1 阻塞。
      (4) 进程P2 执行P(mutex 1) , 于是mutex1=-1, 进程P2 阻塞。
      此时,两个进程处于僵持状态,产生死锁现象。
      AND信号量同步机制就是要解决上述问题, 其基本思想是将进程在整个运行期间所需要的所有临界资源一次性全部分配给进程,待该进程使用完后再一起释放。只要尚有一个资源不能满足进程的要求,其他所有能分配给该进程的资源也都不予以分配,为此在P操作上增加一个AND条件, 故称为AND信号量。P操作的原语为S wait, V操作的原语为S signal。在S wait中, 各个信号量的次序并不重要, 尽管会影响进程进入哪个等待队列。由于S wait实施对资源的全部分配,进程获得全部资源并执行之后再释放全部资源,因此避免了前文所述的僵持状态。如图是S wait和S signal的伪代码。
      在这里插入图片描述
    • 生产者与消费者问题
      1.问描述题
      生产者消费者问题是指有两组进程共享一个环形的缓冲池。一组进程为生产者,一组进程为消费者。缓冲池由若干个大小相等的缓冲区组成。 生产者将产品放入缓冲池,消费者从缓冲池取出产品。
      如图为环形缓冲池:
      在这里插入图片描述
      同步过程:当缓冲池满时,生产者进程必须停止生产唤醒消费者进程,同样,缓冲池空闲时,消费者必须唤醒生产者。
      互斥过程:显然缓冲池是一个临界资源,生产者或消费者只能单独使用它。
      2.生产者与消费者伪代码:在这里插入图片描述在这里插入图片描述
      从中可以看到生产者和消费者之间分别都有两对PV操作,且都是成对出现。一对属于互斥信号量,用于实现对临界资源的互斥访问。另一对是资源信号量,用于实现同步过程,即缓冲池满时,通过消费者唤醒生产者阻塞的进程。(注意生产者消费者过程中empty和full的位置)。
      AND信号量解决生产者和消费者问题
      在这里插入图片描述
      如图,程序中用S wait(empty, mutex) 代替了P(empty) 和P(mutex) , 用S signal(mutex, full) 代替了V(mutex) 和V(full) , 用S wait(full, mutex) 代替了P(full) 和P(mutex) , 用S signal(mutex, empty) 代替了V(mutex) 和V(empty) ; 对信号量的操作同时进行, 避免了死锁。
    • 读者写者问题
      1.问题描述
      一个数据库可以为多个并发进程所共享。其中,有的进程可能只需要读数据库,而其他进程可能要更新(即读和写)数据库。为了区分这两种类型的进程,将前者称为读者,而将后者称为写者。显然,如果两个读者同时访问共享数据,那么不会产生什么不利的结果。然而,如果一个写者和其他线程(既不是读者也不是写者)同时访问共享对象,很可能混乱。为了确保不会产生这样的困难,要求写者对共享数据库有排他的访问。这一同步问题
      称为读者-写者问题。
      在读者一写者问题中,任何时刻要求“写者”最多只允许有一个,而“读者”则允许有多个。因为多个“读者”的行为互不干扰,它们只是读数据,而不会改变数据对象的内容。而“写者”则不同,它们要改变数据对象的内容,如果它们同时操作,则数据对象的内容将会变得不可知。所以,对共享资源的读写操作的限制条件如下所述。
      (1)允许任意多读进程同时读。
      (2)一次只允许一个写进程进行写操作。
      (3)如果有一个写进程正在进行写操作,禁止任何读进程进行读操作。
      2.信号量解决读写者问题
      为了解决该问题,只需解决“写者与写者”和“写者与第一个读者”的互斥问题即可,为此引入一个互斥信号量W mutex。为了记录谁是第一个读者, 可以用一个全局整型变量Rcount做一个计数器。而在解决问题的过程中, 由于使用了全局变量Rcount, 该变量又是一个临界资源, 对于它的访问仍需要互斥进行, 所以需要一个互斥信号量R mutex。如图:
      在这里插入图片描述在这里插入图片描述
      3.其他情况(优先权问题)
      对于读者一写者问题,有以下3种优先策略。
      (1)读者优先。即当读者进行读时,后续的写者必须等待,直到所有读者均离开后,写者才可以进入。前面的程序隐含使用了该策略。
      (2)写者优先。即当一个写者到来时,只有那些已经获得授权允许读的进程才被允许完成它们的操作,写者之后到来的新读者将被推迟,直到写者完成。在该策略中,如果有一个不可中断的连续的写者,读者进程会被无限期地推迟。
      (3) 公平策略。以上两种策略, 读者或写者进程中一个对另一个有绝对的优先权, Hoare提出了一种更公平的策略,由如下规定定义。
      ①规则1:在一个读序列中,如果有写者在等待,那么就不允许新来的读者开始执行。
      ②规则2:在一个写操作结束时,所有等待的读者应该比下一个写者有更高的优先权。
    • 哲学家进餐问题
      1.问题描述
      哲学家进餐问题是一个典型的同步问题, 它由Dijkstra提出并解决。有5个哲学家, 他们的生活方式是交替思考和进餐。哲学家们共用一张圆桌,围绕圆桌而坐,在圆桌上有5个碗和5支筷子,平时哲学家进行思考,饥饿时拿起其左、右两支筷子,试图进餐,进餐完毕又进行思考。这里的问题是哲学家只有拿到靠近他的两支筷子才能进餐,而拿到两支筷子的条件是他的左、右邻居此时都没有进餐。
      在这里插入图片描述

    2.用信号量解决哲学家进餐问题
    在这里插入图片描述
    在以上描述中,虽然解决了两个相邻的哲学家不会同时进餐的问题,但是有一个严重的问题,如果所有哲学家总是先拿左边的筷子,再拿右边的筷子,那么就有可能出现这样的情况,就是5个哲学家都拿起了左边的筷子,当他们想拿右边的筷子时,却因为筷子已被别的哲学家拿去,而无法拿到。此时所有哲学家都不能进餐,这就出现了死锁现象。
    3.AND信号量解决哲学家进餐问题
    在这里插入图片描述

    筷子作为临界资源,每个哲学家需要拿到两个筷子才可以进餐,避免了死锁现象。

    展开全文
  • 测试环境:64位ubuntu 13LTS 功能说明:使用互斥锁+条件变量+共享内存的方式实现进程(或线程)间的通信示例
  • 操作系统——进程同步与互斥

    千次阅读 2019-10-21 22:13:19
    文章目录进程同步与互斥简介进程间合作进程间合作的问题竞争条件原子操作临界区相关的几个概念忙等待的互斥基于硬件的同步解决办法:屏蔽中断基于软件的同步解决方法严格轮换法Peterson解法N线程的软件方法基于软件...

    进程同步与互斥

    简介

    多线程并发会导致资源竞争。

    同步即协调多线程对共享数据的访问,保证任何时刻都只能有一个线程执行临界区代码。

    互斥是解决进程同步的方式。

    进程间合作

    独立进程是指一个进程在运行过程中不会与其他进程进行交互的进程。

    但是,进程在运行的过程中不可避免的要进行进程间合作。

    进程合作的优势:

    • 共享资源
      • 一台电脑,多个用户
      • 一个银行存储余额,多台ATM机
      • 嵌入式系统(机器人控制:手臂和手的协调)
    • 加速
      • I / O操作和计算可重叠
      • 多处理机——将程序分成多个部分执行
    • 模块快
      • 将大程序分解成小程序
        • 如编译系统。
      • 视系统易于扩展

    进程间合作的问题

    进程间合作要避免不确定性和不可重现性。由于进程调度的不确定性,因此进程的一个操作可能被打断。

    进程间通信要解决三个问题:

    1. 一个进程如何将信息传递给另一个进程
    2. 确保多个进程在关键活动中不会交叉,即进程互斥问题。
    3. 保证正确的访问顺序,即进程同步问题。

    竞争条件

    竞争条件是说多个进程读写某些共享数据,而最后的结果取决于进程运行的精确时序。

    案例:

    • 通过调用函数fork来创建一个进程。
      • new_pid = next_pid++;
      • 这一条语句翻译成汇编代码会是四句,因此要把他们当成一个原子操作去执行。
    • 两个程序并发执行访问并更改一个变量x。

    原子操作

    原子操作是指一次不存在任何中断或者失败的执行。

    • 该执行成功结束
    • 或者根本没有执行
    • 并且不应该出现任何部分执行的状态

    但是实际上操作往往不是原子的

    • 有些看上去是原子操作,但是实际上不是,如x++,实际上此条语句由三条汇编语言组成。
    • 有时甚至连单条机器指令都不是原子的,如Pipiline、super-scalar、out-of-order、page fault等。

    操作系统需要利用同步机制在进程并发执行的同时保证一些操作是原子操作。

    临界区相关的几个概念

    临界区是指多个程序访问临界资源的一段代码。也可以说是进程访问临界资源的一段需要互斥的代码。

    1. 在进入临界区前检查是否可进入临界区。
    2. 若可以进入,则设置相应标志表示正在访问临界区。
    3. 在访问完成之后将标志恢复为可访问临界区。
    4. 然后去执行非临界区代码。

    要避免竞争条件,即要找出某个途径来阻止多个进程同时读写共享数据,提出一种解决方案为互斥,即以某种手段保证当一个程序在使用一个共享爱那个文件或变量时,其他进程不能做同样的操作。

    互斥是指当一个进程处于临界区并访问共享资源时,没有其他进程会处于临界区并访问任何相同的共享资源。

    死锁是指多个进程相互等待完成特定任务二最终无法将自身任务进行下去。

    饥饿是指一个可执行的进程被调度器持续忽略,以至于虽然处于可执行状态却不被执行。

    避免竞争条件即使临界区中只能有一个进程。

    一个好的解决竞争条件的方案需要满足下列四个条件:

    1. 任何两个进程不能同时处于临界区
    2. 不应对CPU的速度和数量做任何假设
    3. 临界区外执行的进程不得阻塞其他进程
    4. 不得使进程无限期等待进入临界区
    5. 不能进入临界区的进程应该释放CPU资源(可选)。

    忙等待的互斥

    连续测试一个变量直到某个值出现为止称为忙等待,用于忙等待的锁称为自旋锁

    下列几种方式都可以保证任意两个进程不同时处于临界区。

    基于硬件的同步解决办法:屏蔽中断

    单处理器系统中,最简单的方法是使每个进程刚进入临界区后就立即屏蔽所有中断,并在就要离开之前再打开中断。屏蔽中断后,时钟中断也会被屏蔽,而CPU只有发生时钟中断或其他中断时才会进行进程切换,因此在屏蔽中断之后就不会被切换到其他进程。

    但是这种方式有一个问题:若此进程不打开中断的话其他进程就都无法执行。

    而且若是处于多处理器系统中,其他的CPU也可以将进程调度,从而还是无法避免多个进程同时访问临界区的问题。

    因此,屏蔽中断对用户进程不是一种合适的通用互斥机制。

    总结如下:

    • 硬件将中断处理延迟到中断被启用之后
    • 现代计算机体系结构都提供指令来实现禁用中断
      • 首先保存当前CPU状态
      • 然后禁用中断,访问临界区
      • 最后恢复CPU状态

    缺点:

    • 禁用中断之后,进程无法被停止。
      • 整个系统都会为之停下来
      • 可能导致其他进程处于饥饿状态
    • 临界区可能很长
      • 无法确定响应中断所需的时间

    基于软件的同步解决方法

    通过共享一些共有变量来同步进程的行为。

    严格轮换法

    在这里插入图片描述

    turn用来表示哪一个进程进入临界区,假设只有两个进程,进程0执行a代码,进程1执行b代码,此时考虑两种情况:

    1. 一个进程连续两次进入临界区,第一次进入临界区时发现turn是0,因此进入,在执行完临界区代码之后将turn的值设置为1,那么他在下次进入临界区之前发现turn不是0,因此一直循环等待,但此时临界区中是没有进程在执行的。
    2. 进程0先被调度执行,此时turn的值为0,因此进程0进入临界区执行代码,在它执行完临界区代码退出后,将turn的值更改为1,此时进程1被调度进入CPU执行,发现此时turn的值为1,因此执行临界区的代码,当临界区代码执行完毕之后将要更改turn的值时,CPU调度进程0进入CPU执行,但是此时turn的值还是为1,因此进程0不能执行临界区代码,但是此时临界区却没有进程在执行,因为违反了上面的第三条规则:为处于临界区的进程不得阻塞其他进程。

    由此可见,此种方式也不合适。

    Peterson解法

    在这里插入图片描述

    此算法可以解决两个进程的同步问题。

    N线程的软件方法

    进程Pi要等待从turn到i-1的进程都退出临界区后访问临界区。

    进程Pi退出时将turn给下一个想要进入的进程Pj。

    基于软件解决办法的分析

    • 复杂
      • 需要两个进程之间共享数据项
    • 需要忙等待
      • 浪费CPU时间

    更高级的抽象方法

    简介

    硬件提供了一些同步原语

    • 中断禁用,原子操作指令等

    操作系统提供更高级的编程抽象来监护进程同步

    • 如:锁、信号量
    • 用硬件原语来创建。

    原子操作指令

    现代CPU体系结构都提供一些特殊的原子操作指令。

    测试和置位(Test-and-set)指令

    • 从内存单元中读取值
    • 测试该值是否为1,然后返回真与假
    • 内存单元值设置为1

    交换(exchange)指令

    • 交换内存中的两个值。

    锁变量

    锁是一个抽象的数据结构

    • 一个二进制变量(锁定/解锁)
    • Lock::Acquire()
    • Lock::Release()

    使用锁来控制临界区的访问:当进程进入临界区之前先判断锁变量的值,若有锁的话就等待,否则进入临界区并且更改锁变量的值,然后再退出临界区时将锁变量的值再次修改。

    但是这又回到了最开始的问题:读锁变量和修改锁变量时两个操作,在第一个进程读取锁变量时发现可以进入,然后CPU调度第二个进程进入CPU进行执行,此时第一个进程还未将锁变量进行修改,因此第二个进程也发现可以进入,因此更改了锁变量进入临界区,此时又被切换至第一个进程,第一个进程认为此时临界区中没有进程,因此也进入了临界区,所以还是不能解决竞争条件的问题。

    使用TS指令实现自旋锁

    //忙等待,此种方式为自旋锁方式
    class Lock {
    	int value = 0;
    }
    Lock::Acquire() { //若锁被释放,则TS指令读取0并将值设置为1,否则,TS指令读取1并将值设置为1
    	while(test-and-set(value))
    		;
    }
    Lock::Release() {
    	value = 0;
    }
    
    //无忙等待,此种方式为等待队列方式,即阻塞式方法。
    class Lock {
        int value = 0;
        WaitQueue q;
    }
    Lock::Acquire() {
        while(test-and-set(value)) {
            //将当前进程加入等待队列
            add this PCB to wait queue q
            //执行调度
            schedule();
        }
    }
    Lock::Release() {
        value = 0;
        //从等待队列中移除一个进程p,并唤醒他去执行。
        remove one process p from q;
        wakeup(p);
    }
    

    基于原子操作指令锁的特征

    优点:

    • 适用于单处理器或者共享主存的多处理器任意数量的进程同步机制
    • 简单并且容易验证
    • 支持多临界区

    缺点:

    • 忙等待锁会消耗处理器时间
    • 可能导致饥饿
      • 进程离开临界区时有多个进程在等待
    • 死锁
      • 拥有临界区的低优先级进程
      • 请求访问临界区的高优先级进程获得处理器并等待临界区(忙等待的情况)

    参考资料

    清华大学—操作系统原理
    现代操作系统

    展开全文
  • 用C++实现多线程间的同步互斥,模拟读者、写者问题,支持一个读者一个写者、多个读者一个写者以及多个读者多个写者间的同步互斥
  • 进程同步与互斥:System V 信号量,相关使用教程链接如下: http://blog.csdn.net/tennysonsky/article/details/47811201
  • 进程同步与互斥实验

    千次阅读 2020-11-04 17:53:18
    进程同步与互斥实验 #include <stdio.h> #include <pthread.h> #include <unistd.h> #include <stdlib.h> #define true 1 //生产者ID int product_id = 0; //消费者ID int consumer_id = 0;...

    进程同步与互斥实验

    #include <stdio.h>
    #include <pthread.h>
    #include <unistd.h>
    #include <stdlib.h>
    #define true 1
    //生产者ID
    int product_id = 0;
    //消费者ID
    int consumer_id = 0;
    //缓冲区大小
    int N;
    //生产者数目
    int producerNum;
    //消费者数目
    int consumerNum;
    //类型定义 int型 信号
    typedef int semaphore;
    //类型定义 int型 商品
    typedef int item;
    //定义 商品类型的缓冲数组
    item* buffer;
    //头索引,输入索引,头指针,用于标识生产者的输入位置
    int in = 0;
    //尾索引,输出索引,尾指针,用于标识消费者的输出位置
    int out = 0;
    //产品数目
    int proCount = 0;
    //mutex 互斥变量,empty 缓冲区空白大小,full 缓冲区非空白大小,proCmutex 生产者互斥变量
    semaphore mutex = 1, empty , full = 0, proCmutex = 1;
    //pthread_create函数创建进程时,需要一个指针类型的函数作为参数,所以定义为指针类型。
    //producer与consumer作为线程的执行体。
    void * producer(void * a){
    int id = ++product_id;
    while(true){
    int flag = 0;
    //如果缓冲区已满报错
    while(empty <= 0){
    printf(“生产者%d:缓冲区已满!阻塞中……\n”,id);
    flag =1;
    sleep(1);
    }
    if(flag ==1)
    printf(“生产者%d因缓冲区有空位唤醒!\n”,id);
    //如果有其他生产者占用进程则互斥,检查有没有其他生产者生产产品
    flag = 0;
    while(proCmutex <= 0){printf(“生产者%d生产阻塞中……\n”,id);flag = 1;sleep(1);};
    //将互斥变量置0,代表已占用
    proCmutex–;
    if(flag == 1)
    printf(“生产者%d生产唤醒!\n”,id);
    //产品号+1
    proCount++;
    printf(“生产者%d:生产一个产品ID%d!\n”,id,proCount);

        //总互斥变量,检查有没有其他进程修改缓冲区数据
        flag = 0;
        while(mutex <= 0){printf("生产者%d装入阻塞中……\n",id);sleep(1);flag=1;};
        //占用进程
        mutex--;
    
        if(flag == 1)
            printf("生产者%d装入唤醒,装入产品ID%d,缓冲区位置为%d!\n",id,proCount,in);
        else
            printf("生产者%d装入产品ID%d,缓冲区位置为%d!\n",id,proCount,in);
        //否则缓冲区空白大小-1
        empty--;
        //缓冲区头指针放入产品
        buffer[in] = proCount;
        //头指针+1
        in = (in + 1) % N;
    
        //缓冲区非空白大小+1
        full++;
        //解除占用
        mutex++;
        //解除生产占用
        proCmutex++;
        //睡一觉
        sleep(1);
    }
    

    }

    void * consumer(void *b){
    int id = ++consumer_id;
    while(true){
    int flag = 0;
    while(full <= 0){
    printf("\t\t\t\t消费者%d:缓冲区为空!阻塞中……\n",id);
    flag = 1;
    sleep(1);
    }
    full–;
    if(flag ==1)
    printf("\t\t\t\t消费者%d因缓冲区有产品唤醒!\n",id);
    flag = 0;

        while(mutex <= 0){printf("\t\t\t\t消费者%d消费阻塞中……\n",id);sleep(1);};
        mutex--;
        if(flag == 1)
            printf("\t\t\t\t消费者%d消费唤醒!\n",id);
        int nextc = buffer[out];
        buffer[out] = 0;//消费完将缓冲区设置为0
        empty++;
        printf("\t\t\t\t消费者%d:消费一个产品ID%d,缓冲区位置为%d\n",id, nextc,out);
        out = (out + 1) % N;
        mutex++;
        sleep(1);
    }
    

    }

    int main()
    {
    int tempnum;
    //输入生产者数目
    printf(“请输入生产者数目:\n”);
    scanf("%d",&tempnum);
    producerNum = tempnum;
    //输入消费者数目
    printf(“请输入消费者数目:\n”);
    scanf("%d",&tempnum);
    consumerNum = tempnum;
    //输入缓冲区大小
    printf(“请输入缓冲区大小:\n”);
    scanf("%d",&tempnum);
    N = tempnum;
    empty = N;
    buffer = (item*)malloc(N*sizeof(item));
    for(int i=0;i<N;i++)
    {
    buffer[i]=0;
    }
    //pthread_t是线程结构,用来保存线程相关数据,可以理解为线程类型,声明线程对象(这里声明的时线程对象数组)
    pthread_t threadPool[producerNum+consumerNum];//声明了线程数组作为线程池
    int i;
    for(i = 0; i < producerNum; i++){
    pthread_t temp;
    //if语句中,第一个参数是线程指针,第二个是线程属性指针,第三个是函数指针,即线程要执行的代码
    //函数通过producer函数指针创建对象,赋值给temp作为线程执行
    if(pthread_create(&temp, NULL, producer, NULL) == -1)
    {
    printf(“ERROR, fail to create producer%d\n”, i);
    exit(1);
    }
    //将temp作为能够执行的线程放入了进程池
    threadPool[i] = temp;
    }//创建生产者进程放入线程池

    //对于消费者进程也同样创建进程
    for(i = 0; i < consumerNum; i++){
        pthread_t temp;
        if(pthread_create(&temp, NULL, consumer, NULL) == -1){
            printf("ERROR, fail to create consumer%d\n", i);
            exit(1);
        }
        threadPool[i+producerNum] = temp;
    }//创建消费者进程放入线程池
    
    
    void * result;
    for(i = 0; i < producerNum+consumerNum; i++){
        //pthread_join函数用与等待线程的结束
        //等待的是子进程的结束,因为如果主进程不等待子进程而直接结束,子进程将没有执行就被杀死。
        if(pthread_join(threadPool[i], &result) == -1){
            printf("fail to recollect\n");
            exit(1);
        }
    }//运行线程池
    return 0;
    

    }

    远哥是真强啊!帅!

    展开全文
  • 操作系统中进程同步与互斥的实现.pdf 深入理解操作系统
  • 进程的同步与互斥习题(含参考答案).doc
  • 本资源是用可视化界面做的,效果很好,老师那我的当作优秀,你们可以参考一下!
  • 一个简单的有关于生产者和消费者问题的实例程序
  • 进程的同步与互斥

    2018-09-13 20:49:17
    进程的同步互斥  临界资源:多个进程或者线程都能操作的共享资源  临界区:操作临界资源的代码段  同步是一种合作关系:为完成某个任务,多进程和多线程之间形成一种协调,按照约定或条件执行操作临界资源  互斥:...
  • C语言实现进程同步与互斥

    千次阅读 2020-11-17 16:14:14
    进程同步与互斥 实验原理 (1)同步互斥(生产者消费者问题) 同步是一种更为复杂的互斥,而互斥是一种特殊的同步互斥:是指某一资源同时只允许一个访问者对其进行访问,具有唯一性和排它性。但互斥无法限制...
  • 进程(线程)的同步与互斥 二、实验目的 1. 掌握基本的同步与互斥算法,理解生产者消费者模型。 2. 学习使用Windows中基本的同步对象,掌握相关API的使用方法。 3. 了解Windows中多线程的并发执行机制,实现进程的...
  • 进程同步与互斥习题

    2020-08-05 22:31:05
    在这里插入图片描述 答案:B 答案:A 答案:D 答案:D

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 167,014
精华内容 66,805
关键字:

同步与互斥