Process Synchronization

turn’s value is initialized to be either i or j

do{
	while(turn==j); // Entry section
		critical section; // turn is i 
	turn = j; // Exit section
		reminder section; 
} while(true);
Copy

do{
	while(turn==i); // Entry section
		critical section; // turn is i 
	turn = i; // Exit section
		reminder section; 
} while(true);
Copy

• Mutual Exclusion： Yes
• Progress： No
• Bounded waiting： Yes

Can't Satisfy Progress 无法实现，空闲让进

• 在进入临界区前先检查其他进程是否进入临界区
  • 如果存在进程进程进入临界区，则等待
  • 否则，标志自己进入临界区
• 存在问题：当越过判断时发生进程切换，则无法互斥访问数据 违反忙则等待
• 原因：检查上锁无法连贯执行

bool flag[2];
flag[0]=false;
flag[1]=false;
Copy

// For P0 Process
while(flag[1]);
flag[0] = true;
critical section;
flag[0] = false;
reminder section;
Copy

// For P0 Process
while(flag[0]);
flag[1] = true;
critical section;
flag[1] = false;
reminder section;
Copy

• 先上锁后检查以解决 双标志先检查 的问题

• 在进入临界区前先标志自己需要进入临界区，然后检查其他进程是否进入临界区

  • 如果存在进程进程进入临界区，则等待
  • 否则，则进入临界区

• 存在问题：当标记时发生进程切换，多个进程都需要进入临界区---导致死锁

• 违反空闲让进，有限等待

bool flag[2];
flag[0]=false;
flag[1]=false;
Copy

// For P0 Process
flag[0] = true;
while(flag[1]);
critical section;
flag[0] = false;
reminder section;
Copy

// For P0 Process
flag[1] = true;
while(flag[0]);
critical section;
flag[1] = false;
reminder section;
Copy

It is a classic software-based solution to the critical-section problem

• Good algorithmic description of solving the problem

Solution for two processes by using two variables:

• int turn; // indicates whose turn it is to enter the critical section. 表示谦让 最后谦让的无法执行

• boolean flag[2] // indicate if a process is ready to enter the critical section. 表达意愿

  • flag[i] = true implies that process is ready!
  • It is initialized to FALSE.

do{
	flag[i] = true; //ready
	turn = j; //allow pj to enter
	while(flag[j] && turn == j);
	critical section
	falg[i] = false; //exit
	reminder section 
} while(true);
Copy

do{
	flag[i] = true; //ready
	turn = j; //allow pj to enter
	while(flag[j] && turn == j);
	critical section
	falg[i] = false; //exit
	reminder section 
} while(true);
Copy

• Mutual Exclusion： Yes
• Progress： Yes
• Bounded waiting： Yes

Uniprocessors - could disable interrupts 单处理器 禁止中断 实现
Currently running code would execute without preemption

• Too inefficient

Use the idea of locking

• Protecting critical regions via locks
• A process that wants to enter the critical section must first get the lock.
• If the lock is already acquired by another process, the process will wait until the lock becomes available.
  

1. Test memory word and set value
2. Swap contents of two memory words

bool test_and_set(bool *target); // Do nothing just wait;
	/*Critical  section*/	
 	bool rv = *target；
 	*target = true;
 	return rv;
Copy

• Using Test and Set:

do {
	while(test_and_set(&lock));
	/*Critical  section*/	
	lock = false;
	/*Reminder Section*/
} while(true);
Copy

1. This instruction is executed atomically by CPU as a single hardware instruction.
2. In practice, target is a pointer to the lock itself, shared by all the processes that want to acquire the lock.
   • If target if FALSE, the return value of rv is FALSE, means lock is FALSE (available), target’s new value is TRUE
   • If target is true, the return value of rv is TRUE, means lock is TRUE (locked)

• When lock = true, keep while looping.
• When lock = false, process can enter the critical section
• And set lock = true, block other processes to enter.
• After finish the critical section, reset lock = false, to allow other processes to enter the critical section.

• Mutual Exclusion： Yes
• Progress： Yes
• Bounded waiting： No ?

Exchange Instruction /XCHG Instruction

Returns as result the original value of the lock. Similar to test_and_set but with an integer lock and an extra condition.

int compare_and_swap (int *value, int expected, int new_value){
 	
 	int temp = *value;
 	if(*value==expected)
 		*value=new_value;
 	return temp;
 }
Copy

Lock: 上锁

bool 
while(test_and_set(&lock));
lock = false;
Copy

Semaphore S: an integer variable S can only be accessed via two atomic operations

int S=1;

//acquire lock
void wait(int S){
	while(S<=0){
		S-=1;
	}
}
//release lock
void signal(int S){
	S+=1;
}

Copy

• 仍旧Busy waiting
• 无法让权等待

typedef struct{
	int value;
	struct process* L;
} semaphore;

// acquire lock
void wait(semaphore S){
	S.value--;
	if(S.value < 0){
		block(S.L); //阻塞该进程
	}
}

//release lock
void signal(semaphore S){
	S.value++;
	if(s.value<=0){
		wakeup(S.L); //唤醒进程为就绪态
	}
}

Copy

信号量机制实现进程互斥、同步、前驱
申请一个资源S, 如果资源不够就阻塞等待
释放一个资源S, 如果有进程在等待该资源，则唤醒一个进程

1. 分析并发进程的关键活动，划定临界区
2. 设置互斥信号量mutex，初值为1
3. 进入区P(mutex) -- 申请资源
4. 退出区V(mutex) -- 释放资源

semaphore mutex=1;

P1(){
	P(mutex);
	...;
	V(mutex);
}

P2(){
	P(mutex);
	...;
	V(mutex);
}

Copy

1. 分析什么地方需要实现“同步关系”，即 “一前一后” 执行的两个操作
2. 设置同步信号量S，初始为0
3. 在前操作之后执行 V(S)
4. 在后操作之前执行 P(S)
   • 前V后P

semaphore S=0;
P1(){
	...;
	V(S);
	...;
}
P2(){
	P(S);
	...;
	...;
}
Copy

保证了只能先执行P1()再执行 P2()

semaphore mutex = 1; // 互斥信号量，实现对缓冲区的互斥访问
semaphore empty = n; // 同步信号量，表示空闲缓冲区的数量
semaphore full = 0; // 同步信号量，表示产品的数量，也即非空缓冲区的数量

producer(){
	while(1){
		...;
		P(empty);//消耗一个空闲缓冲区
		P(mutex);
		...;
		V(mutex);
		V(full); //增加一个产品
	}
}

consumer(){
	while(1){
		P(full); //消耗一个产品
		P(mutex);
		...;
		V(mutex);
		V(empty); //增加一个空闲区
	}
}
Copy

semaphore offer1 = 0;
semaphore offer2 = 0;
semaphore offer3 = 0;
semaphore finish = 0;
int i = 0;

provider(){
	while(1){
		if(i==0){
			...;// put Combination-1
			V(offer1);
		} else if(i==2){
			...;// put Combination-2
			V(offer2);
		} else if(i==3){
			...;// put Combination-3
			V(offer3);
		}
		i=(i+1)%3;
		P(finish);
	}
}

smoker1(){
	while(1){
		P(offer1);
		...;// Get Combination-1
		V(finish);
	}
}


smoker2(){
	while(1){
		P(offer2);
		...;// Get Combination-2
		V(finish);
	}
}


smoker3(){
	while(1){
		P(offer3);
		...;// Get Combination-3
		V(finish);
	}
}

Copy

互斥关系：读进程-写进程，写进程-写进程

semaphore rw=1; // 用于实现对共享文件的互斥访问
int count=0;   // 记录当前有几个读进程在访问文件
semaphore mutex; // 用于保证对count变量的互斥访问
Copy

writer(){
	while(1){
		P(rw);
		...;
		V(rw);
	}
}
Copy

	while(1){
		P(mutex); // 各读进程互斥访问count
		if(count==0) // 第一个读进程关门
			P(rw);
		count++;
		V(mutex);
		P(mutex);
		count--;
		if(count==0) // 最后一个读进程开门
			V(rw);
		V(mutex);
	}
Copy

这样的实现存在问题：
如果一直有读进程进入那么写进程将会 starvation
需要实现读写公平的算法

semaphore rw = 1; // 用于实现对共享文件的互斥访问
int count = 0;   // 记录当前有几个读进程在访问文件
semaphore mutex; // 用于保证对count变量的互斥访问
semaphore w = 1; //实现读写公平 可以理解成排队
Copy

writer(){
	while(1){
		P(w);  //谁先抢到 谁先排队
		P(rw);
		...;
		V(rw);
		V(w);
	}
}
Copy

reader(){
	while(1){
		P(w);
		P(mutex); // 各读进程互斥访问count
		if(count==0) // 第一个读进程关门
			P(rw);
		count++;
		V(mutex);
		V(w);
		P(mutex);
		count--;
		if(count==0) // 最后一个读进程开门
			V(rw);
		V(mutex);
	}
}
Copy

semaphore chopstick[5]={1,1,1,1,1};
Pi (){ //i 号哲学家的进程
	while(1){
		P(chopstick[i]); //Take Left chopstick 
		P(chopstick[(i+1)%5]); //Take Right chopstick 
		...;
		V(chopstick[i]); //Put Left chopstick 
		V(chopstick[(i+1)%5]); //Put Right chopstick 
		...;
	}
}
Copy

如果每个哲学家同时拿起左边的筷子, 将导致死锁

semaphore chopstick[5]={1,1,1,1,1};
semaphore mutex = 1; //互斥地取筷子
Pi (){ //i 号哲学家的进程
	while(1){
		P(mutex);
		P(chopstick[i]); //Take Left chopstick 
		P(chopstick[(i+1)%5]); //Take Right chopstick 
		V(mutex);
		...;
		V(chopstick[i]); //Put Left chopstick 
		V(chopstick[(i+1)%5]); //Put Right chopstick 
		...;
	}
}
Copy

This situation shows how a lower-priority task (in this case ) can indirectly prevent a higher-priority task from progressing by holding onto a needed resource longer due to the intervention of a medium-priority task (). This is problematic in real-time systems where such delays can lead to failures or missed deadlines. Solutions often involve using priority inheritance protocols where would temporarily inherit higher priority to avoid being preempted by , thus resolving the inversion more swiftly.