Process Synchronization

Main Content

  • Background
  • The Critical Section 临界区
  • Synchronization Software 软件实现同步
  • Synchronization Hardware 硬件实现同步
  • Mutex Locks 互斥
  • Semaphores 信号两
  • Classic Problems of Synchronization 同步问题
  • Monitors 管程
  • Deadlock and Starvation 死锁与饥饿

Background

Processes can execute concurrently 进程并发地执行

  • May be interrupted at any time, partially completing execution.
    • 如当一个进程时间片用尽，被另一个进程切换
  • Concurrent access to shared data may result in data inconsistency.
    • 如果此时访问相同的数据，将导致数据不一致

进程具有异步性。
异步性：各并发执行的进程以及各自独立的、不可预知的速度向前推进。

To solve this problem, we need to make processes access the same data mutually exclusive 令进程互斥地访问相同数据来解决数据不一致的问题

Race condition:

  • Several processes access and manipulate the same data concurrently
  • Outcome depends on which order each access takes place.

Critical Section 临界区

Critical section problem is to design a protocol that the processes can use to cooperate.

Critical Section
  • The segment of code in a process that modifies shared variables, tables, files
  • When one process is in critical section, other process should not enter their critical sections for these shared data. 互斥访问

一个时间段内只允许一个进程使用的资源称为临界资源。
临界资源只能互斥的访问。

对临界资源的互斥访问，可以在逻辑上分成四部分：

  • Entry section 进入区
    • Ask for Permission 申请权限
  • Critical section 临界区
    • Protect this Section
  • Exit section 退出区
    • Do sth in order to allow other process to enter critical section
  • Reminder section 剩余区
Process with critical section should follow the following steps
  1. execute entry section to ask for permission
  2. then execute critical section
  3. execute exit section to allow other process to enter critical section
  4. then execute remainder section
do {
	entry section
		critical section
	exit section 
		reminder section 
}

Requirements & Solution to Critical Section Problem

Requirement

Requirements to Critical Section Problem
  1. Mutual Exclusion 互斥访问（忙则等待）
    • If process is executing in its critical section, then no other processes can be executing in their critical sections.
  2. Progress 空闲让进
    • If no process is executing in its critical section and if other processes want to enter critical section, one of them must be selected. They cannot be postponed indefinitely.
  3. Bounded Waiting 有限等待
    • If a process has made a request to enter its critical section, then, before that request is granted, there is a bound to the times that others can enter critical section.

Software Synchronization Solution

Solution to Critical Section Problem
  1. 单标志法
  2. 双标志先检查
  3. 双标志后检查
  4. Peterson算法

Solution-I 单标志法

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);

do{
	while(turn==i); // Entry section
		critical section; // turn is i 
	turn = i; // Exit section
		reminder section; 
} while(true);
  • Mutual Exclusion： Yes
  • Progress： No
  • Bounded waiting： Yes

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

Solution-II 双标志先检查（课件未提及）

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

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

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

Solution-III 双标志后检查（课件未提及）

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

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

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

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

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

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

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

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

Peterson’s Solution

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);

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);
  • Mutual Exclusion： Yes
  • Progress： Yes
  • Bounded waiting： Yes

Synchronization Hardware Solution

Software-based solutions are not guaranteed to work on modern computer architecture

Many systems provide hardware support for implementing the critical section code.

Modern machines provide special atomic hardware instructions
Atomic = non-interruptible，the atomic hardware instruction will do the following work

Disable interrupts 中断屏蔽方法

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

  • Too inefficient
Advantage & Disadvantage

Advantage:

  • 简单

Disadvantage:

  • 不适用于多处理机
  • 只适用于操作系统内核进程，不适用于用户进程
    • 因为开/关中断指令只能运行在内核态，这组指令不能让用户随意使用

Solution to Critical-section Problem Using Locks

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

Test and Set Instruction

TS 指令

Definition: TS 指令由硬件实现的，只能一气呵成。

bool test_and_set(bool *target); // Do nothing just wait;
	/*Critical  section*/	
 	bool rv = *target；
 	*target = true;
 	return rv;
  • Using Test and Set:
do {
	while(test_and_set(&lock));
	/*Critical  section*/	
	lock = false;
	/*Reminder Section*/
} while(true);
  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.
Advantage & Disadvantage

Advantage:

  • 实现简单

Disadvantage:

  • 不满足“让权等待”
  • 暂时无法进入临界区的进程会占用CPU并循环执行TSL指令，从而导致 “忙等
  • Mutual Exclusion： Yes
  • Progress： Yes
  • Bounded waiting： No ?

Compare and Swap Instruction

Exchange Instruction /XCHG Instruction

Swap 指令

Definition: TS 指令由硬件实现的，只能一气呵成。

  1. In practice, value is a pointer to the lock itself, shared by all the processes that want to acquire the lock.
  2. Set *value (the lock) to the value of the passed parameter new_value but only if *value == expected. That is, the swap takes place only under this condition.

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;
 }

Lock: 上锁

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

Mutex Lock 互斥锁

Previous hardware-based solutions are complicated and generally inaccessible to application programmers

OS designers build high level software tools to solve critical section problem

Mutex Lock
  • Use mutex lock to protect a critical section by first
    • acquire() a lock then release() the lock
  • Assumption: Calls to acquire() and release() must be atomic
    • Usually implemented via hardware atomic instructions
acquire (){
	while(!available);
	available = false;
}

release (){
	available = true;
}

This solution still requires busy waiting This lock therefore is called a spin lock

  • 忙等待 违反让权等待
  • spin lock TSL, SWAP, 单标志法

需忙等，进程时间片用完才下处理机，违反让权等待
一般用于多处理器，一个核忙等，其他核照常工作，并快速释放临界区
不太适用于单处理机系统、忙等的过程中不可能解锁

Semaphore 信号量

Background

Semaphore is a synchronization tool more sophisticated than mutex locks

  • 用户进程可以通过使用操作系统提供的一对原语来对信号量进行操作，从而很方便的实现了进程互斥、进程同步。
    • 从而很方便的实现了进程互斥、进程同步。

信号量其实就是一个变量(可以是一个整数，也可以是更复杂的记录型变量)，可以用一个信号量来表示系统中某种资源的数量

  • 比如:系统中只有一台打印机，就可以设置一个初值为1的信号量

原语是一种特殊的程序段，其执行只能一气呵成，不可被中断。原语是由关中断/开中断指令实现的。 软件解决方案的主要问题是由 “进入区的各种操作无法一气呵成”，因此如果能把进入区、退出区的操作都用“原语”实现，使这些操作能“一气呵成”就能避免问题。

  • 一对原语:wait(s)原语和signal(s)原语，可以把原语理解为我们自己写的函数，函数名分别为wait和signal，括号里的信号量S其实就是函数调用时传入的一个参数。
  • Wait、signal 原语常简称为P、V操作(来自荷兰语proberen和verhogen)。

POSIX Named Semaphore Normally used among different processes
POSIX Named Semaphore Normally used among different threads within a process

整型信号量

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;
}
  • 仍旧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); //唤醒进程为就绪态
	}
}

Semaphore mechanism implements process mutual exclusion, synchronization and precursor

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

Process mutual exclusion 信号量机制实现进程互斥

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

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

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

Process synchronization 信号量机制实现进程同步

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

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

Process precursor 信号量机制实现进程前驱

Process precursor

Classic Problems of Synchronization

  • Producer consumer problem Bounded-Buffer Problem
  • Readers Writers Problem
  • Dining Philosophers Problem

Producer consumer problem 生产者消费者问题

Producer-Consumer problem
  • n buffers, each holds one item
  • Semaphore mutex initialized to the value 1
  • Semaphore full initialized to the value 0
  • Semaphore empty initialized to the value n
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); //增加一个空闲区
	}
}
同步关系在线程之间实现，互斥关系在线程内实现

Multi-Producer and Consumer Problem

Multi-Producer and Consumer Problem

Smokers Problem 吸烟者问题

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

Readers Writers Problem

Readers-Writers Problem
  • Allow multiple readers to read at the same time
  • Only one single writer can access the shared data at the same time

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

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

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

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

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

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

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

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);
	}
}
Case Analysis
  1. 读者1 --> 读者2
    读者2会被阻塞在P(w), 直到读者1 V(w)
  2. 写者1 --> 写者2
    写者2会被阻塞在写者线程的P(w), 直到写者1 V(w)
  3. 写者1--> 读者1
    读者1会被阻塞在读者线程的P(w), 直到写者1 V(w)

总的来说，新增的 w 信号量实现了一个排队的功能，读者和写者都可以排队

Dining Philosophers Problem

Dining Philosophers Problem
  1. Philosophers spend their lives alternating thinking and eating Don’t interact with their neighbors, occasionally try to pick up 2 chopsticks (one at a time) to eat from bowl
  2. Need both chopsticks to eat, then release both when done In the case of 5 philosophers
  • Shared data
    - Bowl of rice (data set)
    - Semaphore chopstick [5] initialized to 1
    Dining Philosophers Problem
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 
		...;
	}
}

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

Solution
  1. 每次只允许4个哲学家拿筷子，这样最后至少会有一个哲学家可以进餐。
    新定义一个等于4的信号量
  2. 奇数号哲学家拿左边筷子，偶数号拿右边筷子
  3. 仅当一个哲学家左右两双筷子都可以使用时才能拿起筷子
解释仅当一个哲学家左右两双筷子都可以使用时才能拿起筷子

更准确的说法应该是:各哲学家拿筷子这件事必须互斥的执行。

  • 这就保证了即使一个哲学家在拿筷子拿到一半时被阻塞，也不会有别的哲学家会继续尝试拿筷子。
  • 这样的话，当前正在吃饭的哲学家放下筷子后，被阻塞的哲学家就可以获得等待的筷子了。
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 
		...;
	}
}

Deadlock and Starvation 死锁与饥饿

Deadlock - Processes wait for each other
Starvation – indefinite blocking

A process may never be removed from the semaphore queue in which it is suspended

Priority Inversion – Scheduling problem when lower-priority

Process holds a lock needed by higher-priority process

Priority Inversion

Priority Inversion Example Explained:
  1. Process Priorities and Resource Requirement:
    • Assume three processes: , , and with priorities .
    • Process requires a resource which is currently held by process .
  2. Scenario Development:
    • Process must wait for to finish using the resource because has it locked.
    • However, process becomes runnable and, due to its higher priority compared to , it preempts .
  3. Consequence of Priority Inversion:
    • Process (with middle priority) has affected how long process must wait for to relinquish resource .
    • Even though does not need , its operation delays release of , thereby delaying further, which is a clear instance of priority inversion.

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.

Solution: Priority-Inheritance Protocol Explained:
  1. Protocol Basics:
    • All processes accessing resources needed by a higher-priority process inherit the higher priority until they are finished with the resources in question.
    • When these processes complete their tasks involving the resource, their priorities revert to their original values.
  2. Problem Resolution:
    • By allowing lower-priority processes (like process in the earlier example) to inherit the higher priority of a blocked higher-priority process (like process ), the system reduces the chance that a medium-priority process (like process ) will preempt them.
    • This inheritance ensures that the lower-priority process can complete its use of the resource more quickly, thereby freeing up the resource for the higher-priority process.
  3. Effectiveness:
    • This protocol effectively resolves the problem where a lower-priority process blocks a higher-priority one by holding a needed resource, as seen in the previous examples.
    • It reduces the wait time for high-priority processes, ensuring they can proceed with minimal delay, thus adhering more closely to their intended scheduling priorities.

Monitors 管程

Monitors 管程
  • A high-level abstraction that provides a convenient and effective mechanism for process synchronization
    • Abstract data type, internal variables only accessible via procedures
    • Only one process may be active within the monitor at a time
    • Can utilize condition variables to suspend or resume processes
monitor monitor-name { // shared variable declarations
	procedure P1 (...) {...} 
	procedure Pn (...) {...} 
	Initialization code (...) {...}
}
  • A programmer who needs to write a tailor-made synchronization scheme can define one or more condition variables.
Table Of Contents
Process Synchronization
Main Content
Background
Critical Section 临界区
Requirements & Solution to Critical Section Problem
Requirement
Software Synchronization Solution
Solution-I 单标志法
Solution-II 双标志先检查（课件未提及）
Solution-III 双标志后检查（课件未提及）
Peterson’s Solution
Synchronization Hardware Solution
Disable interrupts 中断屏蔽方法
Solution to Critical-section Problem Using Locks
Test and Set Instruction
Compare and Swap Instruction
Mutex Lock 互斥锁
Semaphore 信号量
整型信号量
纪录型信号量
Semaphore mechanism implements process mutual exclusion, synchronization and precursor
Process mutual exclusion 信号量机制实现进程互斥
Process synchronization 信号量机制实现进程同步
Process precursor 信号量机制实现进程前驱
Classic Problems of Synchronization
Producer consumer problem 生产者消费者问题
Multi-Producer and Consumer Problem
Smokers Problem 吸烟者问题
Readers Writers Problem
Dining Philosophers Problem
Deadlock and Starvation 死锁与饥饿
Priority Inversion
Monitors 管程