[数据结构与算法]带你搞懂独占资源的占用问题，操作系统生产者消费者算法实操，包含死锁、进程诠释（Java版）

前言：

? ? ? ? 现如今，许多同学的入门课程都已经是Java、python，就算是CS专业的同学，第一门语言学的是C/CPP，也鲜有人能把操作系统的进程调度给了解明白，而操作系统的进程调度的经典模型就是生产者消费者模型，本文笔者将以Java纯面向对象的模式，给各位讲解线程调度及生产者消费者模型。

一、什么是进程？

? ? ? ? “进程，就是操作系统进行资源调度和分配的最小单位。”许多书籍都这样讲，其实还是有些抽象的。初学者可以把进程，看作一个独立运行的“函数”、“任务”，本文有时候将进程写作线程，其实线程本身确实可以看作一个进程，在Linux操作系统中就没有线程这个概念，在windows系统中，有细微区别，碍于篇幅长度，此处暂且不表。

? ? ? ? 但任务有N个，而CPU只有一个（其实现在很多的电脑已经有了多核CPU了，但这个问题我们可以放到后几篇文章讨论），作为CPU，如何去运行这些任务？

? ? ? ? 假设你是CPU，而N个客户是操作者，你应该如何去执行各客户的任务呢？

? ? ? ? 1、执行完A客户的，执行B客户的，执行C客户的......

? ? ? ? 2、执行半个小时A客户的，执行半个小时B客户的，执行半个小时C客户的，再执行半个小时A客户的，再执行半个小时B客户的.......

? ? ? ? 有的同学可能会选择1，有的同学则会选择2，但目前的很多个人CPU工作都是以原理2执行的，这也是CPU很重要的一个性质——并发，为什么？很简单，你不希望你运行你的Java代码的时候，系统表示：不好意思，360安全卫士正在运行，请等它运行完毕哈。? ? ? ?

? ? ? ? 当然，宏观看来，CPU是并发执行N个线程的，但实际上在微观时间尺度下，CPU是A进程执行1时间片，切换B进程执行1时间片，切换C进程执行1时间片（1时间片约20ms），直到运行完毕。

? ? ? ? 这也使得CPU运行有很多的算法，比如时间片轮转算法，安全性检测算法等，都是和CPU轮转时的运行安全和避免死等忙等提高及时性的必要算法。而其中最重要，也是CPU能运行必不可少的就是——避免死锁，也可以说是，避免死等。

? ? ? ? 而如果切换了进程，再切换回来的时候，谁知道你这个进程已经运行到哪一步了？占用了哪些资源？当前什么状态？每个进程就需要一个PCB对象（进程控制块），存储本进程的所有信息。

二、什么是独占资源？

? ? ? ? 由于每个进程的运转，只占用1时间片，那么有些资源就不便于让N个进程同时操作了。否则将会出现以下的情况（此处仅以两个进程举例）：

? ? ? ? A进程：开始写入x文件

? ? ? ? 切换B进程：读取x文件

? ? ? ? 切换A进程：编写文字

? ? ? ??切换B进程：读取了一行

? ? ? ? 切换A进程：确定写入x文件（x文件内容开始改变）

? ? ? ? 切换B进程：读取第二行（和第一行牛头不对马嘴）

? ? ? ? 这就出现了冲突，所以首先，有些资源是仅能一个进程同时占用的。这就被称之为独占资源。

三、死锁

? ? ? ?那么我们要求这些资源必须只能被一个进程同时占有，但有些进程却需要N个（类）共享资源才能完成，并且结束后释放这些资源，那么我们来考虑一下这个场景？

? ? ? ? A进程任务：打开x1文件，读取数据，打开x2文件，写入，关闭x2，关闭x1。

? ? ? ? B进程任务：打开x2文件，读取数据，打开x1文件，写入，关闭x1，关闭x2。

? ? ? ? A进程刚刚读取x1的数据，啪，切换B进程了，B进程读取x2的数据。

? ? ? ? 好家伙，现在A等B释放x2的数据，B等A释放X1的数据，两个就互相等，这就进入了——死锁。

四、死锁的解决方案

? ? ? ? 那么解决方法有什么呢？

? ? ? ? 很简单，等我下一篇文章（点个关注！）

五、生产者消费者问题。

? ? ? ? 假设目前有生产者和消费者两种人（进程），当生产者需要向商品池存放货物时，需要独占商品池。当消费者需要从商品池取出货物时，亦需要独占商品池。而这两者之间，需要并发进行行为（是并发，而非轮流），请模拟它们的运行进展。

? ? ? ? 那么话不多说，即刻开始。

? ? ? ? 编程环境：Java8+（否则不支持lambda表达式），eclipse

? ? ? ? 首先，我们应该先编写如下几个JavaBean：

• 货物类

public class Good {
	public int id;
	public Good(int id) {//货物的构造函数
		this.id=id;
	}
	public int getid() {
		return this.id;
	}
}

• 商品池

public class Pool {
	private boolean condition=true;//当前被占用情况
	public Good[] goods=new Good[5];//货物列表
	public String name;//本商品池名
	public int size=5;//货物列表长度
	public int count=0;//当前已存储的货物数量
	public Pool(String name) {
		this.name=name;
	}
	public Pool(String name,Good[] goods) {
		this.name=name;
		this.goods=goods;
		this.size=goods.length;
	}
	public void setCondition(boolean condition) {//使被占用情况取反
		if(this.condition==condition) {
			System.out.println("炸了");//这部分其实是我最开始编写程序的时候，有个bug，拿来调bug的，可以省略这里的if
		}else {
			this.condition=condition;
		}
	}
	public boolean getCondition() {//获取当前状态
		return this.condition;
	}
	public boolean isempty() {//当前是否有货物？
		if(this.count==0) {
			return true;
		}else {
			return false;
		}
	}
	public boolean isfull() {//当前是否满？
		if(this.count==this.size) {
			return true;
		}else {
			return false;
		}
	}
	public void add(Good good) {//存入货物操作
		this.goods[count]=good;
		this.count++;
	}
	public Good get() {//取货物操作
		Good g=this.goods[count-1];
		this.goods[count-1]=null;
		this.count--;
		return g;

	}
}

• PriLan接口（一个时间片能做的最小操作，我称之为原子操作）

public interface PriLan {
	public void run(Pool pool,Pcb pcb);
}

• Threads类（代表模拟的线程类，是消费者线程和生产者线程的父类）

class Threads {
	public Pcb pcb;
	public ArrayList<PriLan> allPri;
	public Pool p;
	public Threads(Pool p,String name) {//新建线程，传入此线程所拥有的资源
		this.p=p;
		this.pcb=new Pcb(name);
	}
	public void addPriLan(PriLan prilan) {//线程增加原语，pcb保存线程的各种状态
		this.allPri.add(prilan);
	}
	public void run() {//运行本线程的下一原语
		if(this.pcb.count>=this.allPri.size()) {//若本线程的pcb记录的下一原语数大于了原语总数，则从原语0再开始运行
			this.pcb.count=0;
			this.run();//运行当前应该运行的原语
		}else {
		    this.allPri.get(pcb.count).run(this.p,this.pcb);//将pcb和资源给予原语，并且执行原语
		}
	}
}

• Pcb类

public class Pcb {
	public int count=0;//当前执行原语数量
	public Good good;//当前线程的货物资源
	public String name;
	public Pcb(String name) {
		this.name=name;
	}
}

• ProductorThread类（生产者类）

import java.util.ArrayList;

public class ProductorThread extends Threads {
	{
		this.allPri=new ArrayList<PriLan>();//作为生产者线程，原语链表中提前放置好消费者的两个原语
		this.allPri.add((Pool pool,Pcb pcb)->Tool.product(pcb));
		this.allPri.add((Pool pool,Pcb pcb)->Tool.trycondict(pool,pcb));
		this.allPri.add((Pool pool,Pcb pcb)->Tool.addinto(pool,pcb));
	}
	public ProductorThread(Pool p,String name) {
		super(p,name);
	}
}

• ConsumerThread类（消费者类）

import java.util.ArrayList;
public class ConsumerThread extends Threads {
	{
		this.allPri=new ArrayList<PriLan>();//作为消费者线程，原语链表中提前放置好消费者的两个原语
		this.allPri.add((Pool pool,Pcb pcb)->Tool.await(pool,pcb));
		this.allPri.add((Pool pool,Pcb pcb)->Tool.getgood(pool,pcb));
	}
	public ConsumerThread(Pool p,String name) {
		super(p,name);
	}
	
}

• Tool类，存储消费者和生产者所使用的几个原子操作函数

import java.util.Random;
import java.lang.Thread;
public class Tool {
	static void await(Pool pool,Pcb pcb) {//获取商品的第一个原语
		try {
			if(pool.getCondition()) {//如果商品池没有被占用
				pool.setCondition(false);
				pcb.count++;//pcb下一指向往下指
				System.out.println(pool.name+"空闲,"+pcb.name+"开始占用");
				pcb.bool=true;
				Thread.sleep(1000);
			}else {
				System.out.println("商品池正在被占用，"+pcb.name+"申请占用商品池失败");
				Thread.sleep(1000);
			}
		}catch(Exception e) {
			
		}
	}
	static void getgood(Pool pool,Pcb pcb) {//获取商品的第二个原语
		try {
			if(!pool.isempty()) {
				pcb.good=pool.get();
				System.out.println(pcb.name+"成功获取到商品"+pcb.good.id);
				pool.setCondition(true);//获取商品的所有原语结束
				pcb.count++;
				Thread.sleep(1000);
			}else {
				System.out.println("商品池已无商品，"+pcb.name+"取商品失败");
				pool.setCondition(true);
				pcb.count--;
				Thread.sleep(1000);
			}
		}catch(Exception e) {
			
		}
	}
	static void product(Pcb pcb) {//生产商品
		try {
		Random r=new Random();
		pcb.good=new Good(r.nextInt(1000)*1000);
		pcb.count++;
		System.out.println(pcb.name+"已生产商品"+pcb.good.id);
		Thread.sleep(1000);
		}catch(Exception e) {
			
		}
	}
	static void trycondict(Pool pool,Pcb pcb) {//添加商品的第一个原语
		try {
			if(pool.getCondition()) {//如果商品池没有被占用
				pool.setCondition(false);//设置商品池占用
				pcb.count++;//pcb下一指向往下指
				System.out.println(pool.name+"未被占用,"+pcb.name+"开始占用");
				Thread.sleep(1000);
			}else {
				System.out.println("商品池正在被占用，"+pcb.name+"申请占用商品池失败");
				Thread.sleep(1000);
			}
		}catch(Exception e) {
			
		}
	}
	static void addinto(Pool pool,Pcb pcb) {//添加商品的第二个原语
		try {
			if(!pool.isfull()) {//若pcb记录的bool为真，说明商品池可用
				pool.add(pcb.good);
				System.out.println(pcb.name+"成功存入商品"+pcb.good.id);
				pcb.count++;
				Thread.sleep(1000);
			}else {
				System.out.println("商品池已满，"+pcb.name+"存商品失败");
				Thread.sleep(1000);
				pcb.count=1;
			}
			pool.setCondition(true);//获取商品的所有原语结束
		}catch(Exception e) {
			
		}
	}
}

• Test（运行环境main入口）

public class Test {

	public static void main(String[] args) {
		// TODO Auto-generated method stub
		Pool pool=new Pool("商品共享池");
		ConsumerThread cos=new ConsumerThread(pool,"消费者1");
		ProductorThread prod=new ProductorThread(pool,"生产者1");
		Loop a=new Loop("CPU");
		a.addThread(cos);
		a.addThread(prod);
		a.LoopRun();
	}

}

每一个消费者对象，在被实例化的时候，都会执行代码块：

	{
		this.allPri=new ArrayList<PriLan>();//作为消费者线程，原语链表中提前放置好消费者的两个原语
		this.allPri.add((Pool pool,Pcb pcb)->Tool.await(pool,pcb));
		this.allPri.add((Pool pool,Pcb pcb)->Tool.getgood(pool,pcb));
	}

? ? ? ? 如果这段代码看不懂，我会在下一篇javase基础文章中，重点介绍一下静态代码块和lambda语法。

? ? ? ? 简而言之就是，在消费者线程对象实例化前，给它的allPri属性注入2个原子操作。便于后续run起来，生产者线程同理，

? ? ? ? 代码结果如下，模拟出了抢占机制：

商品共享池空闲,消费者1开始占用
生产者1已生产商品385000
商品池已无商品，消费者1取商品失败
商品共享池未被占用,生产者1开始占用
商品池正在被占用，消费者1申请占用商品池失败
生产者1成功存入商品385000
商品共享池空闲,消费者1开始占用
生产者1已生产商品5000
消费者1成功获取到商品385000
商品共享池未被占用,生产者1开始占用

? ? ? ? 以上就是生产者消费者模拟算法的全部，若对代码有任何意见和不解之处，欢迎在下面留言或者私下找我讨论