操作系统课程设计：实现进程间的同步。 有问题留言
import java.util.concurrent.Semaphore; /******** 信号量 *******/  class Sign {  final static int NUMS = 6; // 进程的数目  final static int RUN = 1; // 运行完  final static int STOP = 0; // 阻塞态  static int[] status = new int[NUMS]; // 进程的状态 不运行 则阻塞 默认为禁止  static Semaphore s[] = null; // 信号量  final static int[] times = new int[6]; //运行的次数    static Semaphore mutex = new Semaphore(1);// 信号量：控制对临界区的访问    static {  s = new Semaphore[NUMS];  for (int i = 0; i < NUMS; i++) {  s[i] = new Semaphore(1); // 初始化  }  for (int j = 0; j < times.length; j++) {  times[j] = 10; // 每个进程执行10次则结束  }  }  }    /*********线程***********/  class process6 implements Runnable {// 进程线程  private int id;    public process6(int id) {  super();  this.id = id;  }    void test(int id) throws InterruptedException { // 测试当前进程是否可以运行  // 当自己没有运行，前置条件满足时 可以运行  switch (id) {  case 0:    if (Sign.times[0] > 0) {  Sign.s[0].release();  Sign.times[0]--;  System.out.println("I am thread P" + (id + 1) + "。。。。。"  + Sign.times[id]);  }  ;  break;  case 1:    if (Sign.status[0] == Sign.RUN && Sign.times[1] > 0) { // 如果进程1  // 已经运行完，进程2可以直接运行    Sign.s[1].release();  Sign.times[1]--;  System.out.println("I am thread P" + (id + 1) + "。。。。。"  + Sign.times[id]);  }  ;  break;  case 2:    if (Sign.status[0] == Sign.RUN && Sign.times[2] > 0) { // 如果进程1  // 已经开启，进程3可以直接运行    Sign.s[2].release();    Sign.times[2]--;  System.out.println("I am thread P" + (id + 1) + "。。。。。"  + Sign.times[id]);  }  ;  break;  case 3:    if (Sign.status[1] == Sign.RUN && Sign.times[3] > 0) { // 如果进程2已经开启，进程4可以直接运行    Sign.s[3].release();  Sign.times[3]--;  System.out.println("I am thread P" + (id + 1) + "。。。。。"  + Sign.times[id]);  }  ;  break;  case 4:    if (Sign.times[4] > 0  && (Sign.status[1] == Sign.RUN || Sign.status[2] == Sign.RUN)) {// 如果进程2、或3已经运行完，进程5可以直接运行    Sign.s[4].release();  Sign.times[4]--;  System.out.println("I am thread P" + (id + 1) + "。。。。。"  + Sign.times[id]);  }  ;  break;  case 5:    if (Sign.times[5] > 0  && (Sign.status[4] == Sign.RUN || Sign.status[3] == Sign.RUN)) {// 如果进程4或5已经运行完，进程6可以直接运行    Sign.s[5].release();  Sign.times[5]--;  System.out.println("I am thread P" + (id + 1) + "。。。。。"  + Sign.times[id]);  }  ;  break;  }  }    void print() {// 打印 每个进程的状态  for (int i = 0; i < Sign.NUMS; i++) {  System.out.println("Thread P" + (i + 1) + " ：" + Sign.status[i]);  }  }    @Override  public void run() {  try {  while (true) {  // print(); //先打印全部进程状态  Sign.mutex.acquire();  // System.out.println("P" + id + " is testing!");  test(id);  Sign.mutex.release();  // 判断当前进程运行的状况，不能运行 则 阻塞  Sign.s[id].acquire();    // 唤醒其他进程 不能运行 则阻塞  if (Sign.times[id] == 0 || Sign.times[id] < 0) {  Sign.status[id] = Sign.RUN;  // System.out.println("P" + (id+1) + " run out!");    Sign.mutex.acquire();  test((id + 1) % 6);  test((id + 2) % 6);  test((id + 3) % 6);  test((id + 4) % 6);  test((id + 5) % 6);  Sign.mutex.release();    } else {  // System.out.println(+"前置条件不够！");  Thread.currentThread().sleep((100));  }  }  } catch (Exception e) {  e.printStackTrace();  }    }    }    public class SYSV {    /**  * 任务3 进程/线程同步  */  public static void main(String[] args) {  new Thread(new process6(0)).start();  new Thread(new process6(1)).start();  new Thread(new process6(2)).start();  new Thread(new process6(3)).start();  new Thread(new process6(4)).start();  new Thread(new process6(5)).start();  }  }

//一般信号量解决进程同步问题
typdef struct semaphore {
	int value;           
	 /*value>0表示可用资源数；
	 value<0表示等待资源进程数；
	 value=0表示现在没有可用资源，也没有等待使用资源的进程*/
	struct pcb* list;
	}
void P(semaphore s)
{
	s.value--;
	 /*执行P操作后信号量小于0，表示已没有资源可用，
	 当前进程进入等待队列，CPU转向执行调度进程*/
	if(s.value<0)      
		sleep(s.list);
}
void S(semaphore s)
{
	s.value++;
	 /*执行V操作前，若信号量小于0，表明有进程正在等待该资源，
	 执行V操作后释放了一个资源，应唤醒队列中第一个等待进程，使其进入就绪态*/
	if(s.value<=0)
		wakeup(s.list);
}

/* Cosumer and Producer model(Incorrect) */

/* Producer */
int nextProduced;
while(true){
	while(count == n);
	buffer[in] = nextProduced;
	in = (in + 1) % BUFFER_SIZE;
	count++;
}

/* Consumer */
int nextConsumed;
while(true){
	while(count == 0);
	nextConsumed = buffer[out];
	out = (out + 1) % BUFFER_SIZE; 
	count--;
}


/* Peterson's solution */
do{
	flag[i] = true;
	turn = j;
	while(turn == j && flag[j] == true);
	//critical section
	flag[i] = false;
	//remainder section
}while(true);

/* TestAndSet solution*/
bool waiting[n];
bool lock;

do
{
	waiting[i] = true;
	key = true;
	while(waiting[i] && key){
		key = TestAndSet(&lock);
	}
	waiting[i] = false;

	// critical section

	j = (i+1) % n;
	while(j!=i && !waiting[j]){
		j = (j+1) % n;
	}
	if(j == i){
		lock = false;
	}
	else{
		waiting[j] = false;
	}

	// remainder section
} while (true);


/* Mutex implementation */
semaphore mutex;
do{
	waiting(mutex);
	// critical section
	signal(mutex);
	// remainder section
}while(true);


/* Semaphore implemantation */
typedef struct {
	int value;
	struct process* list;
} semaphore;

wait(semaphore* s){
	s->value--;
	if(s->value < 0){
		add this process to s->list
		block();
	}
}

signal(semaphore* s){
	s->value++;
	if(s->value <= 0){
		remove a process P from s->list
		wakeup(P);
	}
}

/* The bounded buffer problem: mutex solution*/
semaphore mutex = 1;
semaphore full = 0;
semaphore empty = n;

// Producer
do{
	wait(empty);
	wait(mutex);

	// add to buffer
	signal(mutex);
	signal(full);
}while(true);

// Consumer
do{
	wait(full);
	wait(mutex);

	// remove an item from buffer
	signal(mutex);
	signal(empty);
}while(true);


/* read write problem */
semaphore mutex, wrt;
int readcount;

// writer
do{
	wait(wrt);
	//writing is performed
	signal(wrt);
}while(true);

// reader
do{
	wait(mutex);
	readcount++;
	if(readcount == 1){
		wait(wrt);
	}
	signal(mutex);

	// reading is performed

	wait(mutex);
	readcount--;
	if(readcount == 0){
		signal(wrt);
	}
	signal(mutex);

}while(true);

进程同步
进程同步
背景
临界区问题
Perterson 算法
信号量
用法
两种实现方式
死锁和饥饿
原子事务
系统模型
基于日志的恢复

进程同步
背景
生产者代码：
while(true)
{
	// produce an item in nextProduced
	while(counter == BUFFER_SIZE);
	buffer[in] = nextProduced;
	in = (in + 1) % BUFFER_SIZE;
	counter++;
}

消费者代码：
while(true)
{
	while(counter == 0);
	nextConsumed = buffer[out];
	out = (out + 1) % BUFFER_SIZE;
	counter--;
}

虽然生产者和消费者程序各自正确，但是当并发执行时，他们可能不能正确运行。
举例来说，对于生产者代码中的 counter++ ，可以拆成以下三步：
register1 = counter;
register1 = register1 + 1;
counter = register1;

同理，对于消费者代码中的 counter–，可以拆成以下三步：
register2 = counter;
register2 = register2 - 1;
counter = register2;

当生产者代码和消费者代码并发时，可能会产生如下情况：
register1 = counter;
register1 = register1 + 1;
register2 = counter;
register2 = register2 - 1;
counter = register1;
counter = register2;

这样会导致 counter 的状态（值）不正确。
多个进程并发访问和操作统一数据且执行结果与访问发生的特定顺序有关，称为竞争条件（race condition）。为了避免竞争条件，需要确保一段时间内只有一个进程能执行代码。为了实现这种保证，要求进行一定形式的进程同步。

临界区问题
假设某个系统有n个进程{P1，P2，…，Pn}。每个进程有一个代码段称为临界区（critical section），在该区种进程可能改变共同变量、更新一个表、写一个文件等。这种系统的重要特征是当一个进程进入临界区，没有其他进程可被允许在临界区内执行，即没有两个进程可同时在临界区内执行。
每个进程必须请求允许进入临界区。实现这一请求的代码段称为进入区（entry section），临界区之后有退出区（exit section），其他代码为剩余区（remainder section）。
临界区问题的解答必须满足如下三项要求：

1.互斥（mutual exclusion），如果进程Pi在其临界区内执行，那么其他进程都不能在其临界区内执行。

2.前进（progress），如果没有进程在其临界区内执行且有进程需要进入临界区，那么只有那些不在剩余区内执行的进程可选择参加，这种选择不能无限推迟。

3.有限等待（bounded waiting），从一个进程做出进入临界区的请求，直到该请求允许为止，其他进程进入其临界区的次数有上限。

Perterson 算法
Perterson 算法适用于两个进程在临界区与剩余区间交替执行。
Perterson 算法需要在两个进程之间共享两个数据项：
int turn;
bool flag[2];

变量 turn 表示哪个进程可以进入临界区。数组 flag 表示哪个进程想要进入临界区。
Pi 的代码：
while(true)
{
	flag[i] = true;
	turn = j
	while(flag[j] && turn == j);
	// 临界区
	flag[i] = false;
	// 剩余区
}

Pj的代码：
while(true)
{
	flag[j] = true;
	turn = i;
	while(flag[i] && turn == i);
	// 临界区
	flag[j] = false;
	// 剩余区
}


信号量
信号量是个整数变量，除了初始化外，它只能通过两个标准原子操作：wait() 和 signal() 来访问。这两个操作原来分别被称之为 P 和 V，信号量操作也可以称为PV操作。
在 wait() 和 signal() 操作中，对信号量整型值的修改必须不可分地执行。
用法
通常操作系统区分计数信号量和二进制信号量。计数信号量地值域不受限制，而二进制信号量的值只能为0或1。
二进制信号量有时也被称为互斥锁，因为它们可以提供互斥。可以使用二进制信号量来处理多进程的临界区问题。
计数信号量可以用来控制访问具有若干个实例的某种资源（如打印机等）。该信号量初始化为可以用资源的数量，然后用 wait() 和 signal() 操作来获取和释放相应资源。
信号量还能用来处理进程间的同步问题。
两种实现方式
当进程执行 wait() 操作，但信号量不为正时，会出现两种情况：

1.进程进行忙等待（busy waiting）。

2.进程阻塞自己（进程进入到 waiting 状态，将 CPU 分给其他进程）。
进行忙等待的信号量也称为自旋锁（spinlock），自旋锁常用于多处理器系统中。
为了实现第二种信号量，每个信号量都会有一个整型值和一个进程链表。当一个进程必须等待信号量时，就加入到进程链表上。每当有进程执行了 signal() 操作后，内核会修改信号量的整型值并从进程链表上选择一个进程放入到就绪队列中去，进程链表可以采取任一排队策略（要保证有限等待）。
信号量的关键之处是它们原子地执行。这属于临界区问题，在单处理器环境下，可以在执行 wait() 和 signal() 时简单地禁止中断来实现对信号量的原子操作，但在多处理器环境下，单一处理器的中断禁止并不能保证信号量操作原子地执行，因此必须提供其他加锁技术。
死锁和饥饿
具有等待队列地信号量的实现可能导致这样的情况：两个或多个进程无限地等待一个时间，而该事件只能由这些等待进程之一来产生。
举例来说，有两个进程P1、P2，如下（S、Q均为二进制信号量）：
// P1进程
wait(S);
wait(Q);

signal(S);
signal(Q);

// P2进程
wait(Q);
wait(S);

signal(Q);
signal(S);

假设P1进程执行完 wait(S) 后中断，由P2进程执行 wait(Q)，那么接下来两个进程都会阻塞在第二步，形成死锁。
饥饿的发生跟进程链表的排队策略有关，若排队策略不当，可能使得某些进程无限地等待信号量。

原子事务
系统模型
执行单个逻辑功能的一组指令或操作称为事务（transaction）。处理事务的主要问题是不管出现什么计算机系统的可能失败，都要保证事务的原子性。
可以认为事务是访问且可能更新各种驻留在磁盘文件中的数据项的程序单元。从用户观点来看，事务知识一系列的read和write操作，并以commit操作或abort操作终止。
被终止的事务可能所改了它访问的数据，因此该事务必须回退（rolled back）。
基于日志的恢复
确保原子性的一种方法是在稳定存储上记录有关事务对其访问的数据所做各种修改的描述信息。实现这种形式记录最常用的方法是先记日志后操作。
每个日志记录描述了一个事务写出的单个操作，并具有如下域：

1.事务名称

2.数据项名称

3.旧值

4.新值