### Lecture 07 - Synchronisation and communication

**Terms Introduction**
**Concurrency** - is parallel or so-to-say parallel execution of sequences of commands in processes and threads, replacement of threads is possible at any time by OS without any influence of the application programmer.
**Nuclear action** - are areas of code that must be executed in one piece or atomically to avoid inconsistencies, but an interruption through repression is possible at any time.

##### Conflict Example 1:
Several processes process a common list of objects, a process wants to appends a new object to the front of the list but processes can be interrupted at any time if second process also tries to append an object to the front there may be problems.
![[Pasted image 20240218102601.png|inlR|400]]

When process 1 executes 1st instruction A1.next := B, will make CPU withdrawn
![[Pasted image 20240218102620.png|inlR|400]]
When process 2 executes 1st and 2nd instruction A2.next := B and Anchor := Address(A2), will make CPU withdrawn
![[Pasted image 20240218102637.png|inlR|400]]
When process 1 executes the 2nd instruction, Anchor := Address(A1), will make CPU withdrawn
![[Pasted image 20240218102652.png|inlR|400]]

When process 1 executes 2nd instruction, Anchor := Address(A1), A2 becomes a zombie with lost update anomaly
![[Pasted image 20240218102703.png|inlR|400]]

##### Conflict Example 2:
A shared counter is modified by 2 processes, can cause inconsistencies which are referred as lost updates. In following case counter is initially set to 0

| Less problematic sequence | Error Case |
| ---- | ---- |
| ![[Pasted image 20240218103341.png]] | ![[Pasted image 20240218103348.png]] |

Race condition is a situation in which two or more processes share common resources and the end result of the use depend on the temporal order of operation meaning that final results of processing the shared resources depends on chronological order of command execution.

#### Critical sections and mutual exclusion
Data can processed jointly by several processes or threads and may be accessed arbitrary. Processes/threads needs to work with each other in coordinated use of shared resources therefore the synchronisation is necessary. Therefore the concept that is logically uninterruptible needs to be protected as a critical section where only one process can be in critical section at the time, entering and exiting must be synchronised, the goal is mutual exclusion to guarantee.
![[Pasted image 20240218103916.png]]
**Critical Section Requirements** - (from Djikstra 1965)
- no two processes are allowed at the same time to be in a critical section
- no assumptions about processing speed and the number of processes or processors
- no process outside of the critical section is allowed to control another process, meaning it should not be able to block
- any process waiting at the entrance to a critical section must be allowed to enter it at some point there must be fairness condition and no waiting forever

**Petri net**
$S_{12}$ and $S_{22}$ represent the critical sections of two processes $S_{11}$ and $S_{21}$ are uncritical, the position of $S_0$ is mutual exclusion realised , when $t_{11}$ switch clicks then the Process 1 is in critical section blocking Process 2 to access $S_{22}$
![[Pasted image 20240218104312.png]]

#### Locks, Semaphores and Mutex
Many mechanism has been created for preventing multiple processes from entering critical section, first hardware support for synchronisation is to **Turn Off Interrupts** during the processing in critical section, which in general is bad solution not.

**Variable Lock** - is second mechanism for locking enter to a critical section, value 0 of variable means that lock is not occupied and process can enter critical section while value 1 doesn't allow enter. Variable value is checked each time before entering, at exit of critical section variable is again set to 0, only problem with this implementation must not be interrupted. Locking to ensure lock variable safety uses hardware support for synchronisation like: **atomic instruction sequence** which are uninterruptible machine instructions in a single uninterruptible memory cycle which is important for multiprocessors. Practical examples are:
- **Test and Set Lock** (TSL) or **VALLEY** which does reading and replacing memory cell in one memory cycle.

MyLock_lock: 
	TSLR1, LOCK // LOCK is a memory variable that is 
				// set and read by the TSL instruction in 
				// one memory cycle
	CMP R1, #0 // Read LOCK into R1 and set value to 1 
				// Compare register contents with 0 
				// If comparison applies, then lock is set 
				// Otherwise try again 
				
	JNE MyLock_lock 
	RET         // Critical section can be entered 
	
	MyLock_unlock: 
		MOVE LOCK, #0 //set LOCK to 0 (release) 
		RET     // Critical section can be entered by another process

- **Swap** exchange of two variable values in one storage cycle.
- **Fetch and Add** - which implement reading and incrementing a memory cell in one memory cycle
- **Exchange command XCHG dest/src** (intel command set) - contents of src and dest are exchanged where registers and memory areas are possible to be src and dst.
- **Spinlocks** - when a lock is tried over and over again in queue until it is granted, they are often found in OS like Windows for access to the DPC queue, it is very good for very short waiting times with multiprocessors. Dissadvantage of spinlock are that threads are busy waiting meaning they are actively waiting by trying to enter spinlock until they get granted access which is waste of CPU and very uneconomical, hanse no fairness no orderly waiting area
- **Semaphore concept** - puts process "to sleep" and wake it up again when it is allowed to enter critical area, it is a high level concept for solving the mutual exclusion problem which also allows solving more complex synchronisation problems. Semaphore performs 2 elementary operations:
- P() - which is called when entering critical section it is operation on semaphore which puts other processes in waiting state until other process in critical section
- V() - called when leaving critical section, which wakes up waiting processes to be activated and allowed to enter critical section
![[Pasted image 20240218111310.png]]
Semaphore also implements a counter that determines how many processes are allowed to execute the critical section which can also be controlled, and queue for the processes that have to wait at the entrance to a critical section
![[Pasted image 20240218111751.png|imlR|400]]

. . . 
P(); // critical section occupied? // nuclear action
c = counter.read(); // critical section 
c++; 
counter.write(c); 
V(); // Exit critical section, wake up // nuclear action
// a waiting process

// Seamphore algorithm
void P(){ 
	if(s >= 1) { 
		s = s - 1; // the process executing the P operation continues its 
				// process 
	} else { 
	// the process executing the P operation is initially stopped
	// placed in the waiting state and entered in a waiting list 
	// assigned to the semaphore S 
	} 
}

voidV(){ 
	s = s + 1; 
	if(Waiting list is not empty) { 
		// a process is selected from the waiting list and woken up 
	} 
} // the process executing the V operation continues its execution

![[Pasted image 20240218112118.png|imlR|500]]
Semaphore is simple form of mutex - it implements counting processes in critical zone which can be set as arbitrary. Also Binary implementation of semaphore which is called **mutex** which on counter can only set 0 or 1 they are easy and efficient to implement, and mutex is variable that can only have 2 states locked|unlocked, needing only one bool variable and 2 operations `mutex_lock` and `mutex_unlock`

#### Various Sync Problems
**Philosopher's problem** - (Djikstra and Hoare 1965) - 5 philosophers sit around the table and everyone has plate of spagetti in front of them and there 5 forks between each table, each of them needs 2 forks to eat, when one of they try to eat he tris to take the fork on left and right of his plate in any order when he gets them he eats and puts them back. Algorithm of their action is following

static int n = 5; 
void philosopher(int i) { 
	while (true) { 
		think(); 
		take_fork(i); 
		take_fork((i+1) % n); 
		eat(); 
		put_fork(i); 
		put_fork((i+1) % n); 
	}
}

**Deadlock situation or cycle lock**
![[Pasted image 20240218113832.png|imlR|400]]
Philosopher has locked waiting for other fork to get free while P next to him is doing the same. This is also so called producer-consumer problem, where one or more producers processes to produce and one or more consumer processes consume, finally large buffer areas between processes producer replenishes and consumer takes out. In this problem **flow control** is necessary where producer goes to sleep when the buffer is full and is woken up by the consumer when there is space again, at that time customer goes to sleep when the buffer is empty and is woken up again by the producer when there is something again in it.
![[Pasted image 20240218114141.png]]
This can be solved with 3 semaphores mutex for mutual exclusion during buffer access and free and proven synchronisation

// Producer
while(true) {
	produce(item); 
	P(free); 
	P(mutex); 
	putInBuffer(item); 
	V(mutex); 
	V(occupied);
}
// Consumer
while(true){ 
	P(occupied); 
	P(mutex); 
	getFromBuffer(item); 
	V(mutex); 
	V(free); 
	consume(item); 
}

#### Monitors
Use of semaphores is relief but not without the problems, programmers might forget an operation, or can accidentally confuse it. Hoare and Brinch Hanse claimed that creation and ordering of semaphore operation should be left to the compiler and abstract data types for these purposes are created as desginated Monitor, in one monitor shared data are protected through a lock and syncrhonisation variables.
The monitor consist of a lot of **procedures** and **data structures** as well as **operating resources** which are under surveilled. Monitors are accessible to multiple processes but can only be used by one process/thread at time
![[Pasted image 20240218122200.png|imlR|500]]
Monitor for producer-consumer

class MonitorProducerConsumer {
	final static int N = 5; 
	static int count = 0; 
	
	condition not_full;
	condition not_empty;
	void insert(item: integer) { 
		if (count == N) wait(not_full);  // Wait until buffer 
										// is no longer full
		 // Insert item 
		 count+=1; 
		 if (count > 0) signal(not_empty); 
	 }
}
class UseMonitor { 
	ProducerConsumerMon=new ProducerConsumer(); 
	. . . 
	void producer() { 
		while (true) { 
			// Produce item 
			mon.insert(item); 
		} 
	} 
	
	void consumer() { 
		while (true) { 
			// Consume  item
			item = mon.remove(); 
		} 
	} 
}

Scenarios

| Initial State | Consumer 1 wants to consume |
| ---- | ---- |
| ![[Pasted image 20240218122536.png]] | ![[Pasted image 20240218122740.png]] |
Customer 1 wants to consume first but Producer 1 arrives late and has to wait
![[Pasted image 20240218122857.png|imlR|500]]

Then Consumer 1 cannot consume more, then Producer 1 jumps in when Consumer 1 has left the monitor and then enters it
![[Pasted image 20240218123017.png|imlR|300]] ![[Pasted image 20240218123052.png|imlR|300]]

When Producer 1 finished inserting Consumer 1 can again consume
![[Pasted image 20240218123151.png|imlR|300]]![[Pasted image 20240218123203.png|imlR|300]]

Another scenario Producer wants to produce first
![[Pasted image 20240218123239.png|imlR|300]]![[Pasted image 20240218123310.png|imlR|300]]

#### Java Synchronisation
Java have modifier `synchronized` that serves to define critical section which separates it in code block which methods and all objects can use it. **Thread safe** class or method which is used in safely concurrent thread environment, while problematic are class variable and global variables.

// only one thread at allowed time is allowed in sync method and block
// Access syncrhonized method
public synchronized void method1() { // protected code area }

// Access syncrhonized instruction block
XyObject object1 = new XyObject(...); 
synchronized(object1) { // protected code area }

Application of synchronised on whole methods have some limitation such as affected objects are blocked from access by other instances, lock is held until the method is processed. In addition the modifier static is used in the method definition so the whole class blocked until the method is processed.
Synchronised is uses in JVM one lock and one condition variable for synchronisation. In case of object that contains at least one synchronized method JVM adds one its own monitor to facilitate synchronization ensuring that only one thread can enter sensitive section.

**Example Increment counter through multiple threads**

class CounterObject {  // not atomic increment
	private int count = 0; 
	CounterObject() { 
		// Nothing to construct Increment not atomic! 
	} 
	void set(int newCount) { 
		count = newCount; 
	} 
	int get() { return count; }
}

// unsync Thread class

class CountThread1 extends Thread{ 
	private CounterObject myCounter;
	private int myMaxCount;
	
	CountThread1(CounterObject c, int maxCount) { 
		myCounter = c; 
		myMaxCount = maxCount; 
	} 
	
	public void run() { 
		System.out.println("Thread " + getName() + " started"); 
		for (int i=0;i < myMaxCount;i++){ 
			// Critical area 
			int c = myCounter.get(); 
			c++; 
			myCounter.set(c); // End of critical area 
		}
	}
}

// Sync thread class
class CountThread2 extends Thread{ 
	private CounterObject myCounter;
	private int myMaxCount;
	
	CountThread2(CounterObject c, int maxCount) { 
		myCounter = c; 
		myMaxCount = maxCount; 
	} 
	
	public void run() { 
		System.out.println("Thread " + getName() + " started"); 
		for (int i=0;i < myMaxCount;i++){ 
			synchronized (myCounter) {
				// Critical area 
				int c = myCounter.get(); 
				c++; 
				myCounter.set(c); // End of critical area 
			}
		}
	}
}

From example we learn that simple object class manages a counter and multiple threads can access the method `get()` and `set()` towards the counter.
![[Pasted image 20240218131407.png]]

Explicit sync methods are:
- `wait()` - thread that goes into waiting state until `notify()` and `notifyAll()` call is issued to another thread that matches the same critical section - and may only be called within section protected with sync
- `wait(long timeout)` - thread goes into a waiting state for max "timeout" in ms otherwise it is same like `wait()`
- `notify()` - randomly wakes up one of the waiting threads - and may only be called within section protected with sync
- `notifyAll()` - wakes up all waiting threads
- `join()` - thread waits until another thread quits or exists

`wait()` also blocks the thread itself, while the lock for critical section is released
`wait() and notify()` - are runtime critical, where signaling must not come too early otherwise it will be ineffective, the solution would be to call `wait()` in while loop. These method doesn't implement queueing mechanism so it is absolutely not fair

**Thread Possible states according to Java API** - are part of the Enum from class `Thread.State` and they can be:
- **New** - when thread is not started yet
- **Runnable** - thread is running in JVM but may wait for operating system resources
- **Blocked** - thread is blocked and waiting for monitor lock to enter a sync block
- **Waiting** - thread waits for another thread to perform an action, it usually happens when thread has called `wait()` or `join()` without specified time.
- **Timed waiting** - thread waits for specified period of time to expire when called wait, join or sleep with specific long ms
- **Terminated** - thread has completed its work
![[Pasted image 20240218132250.png]]
Example of explicit sync in custom semaphore implementation

class MySemaphore { 
	private int max; // Number of maximum possible threads
		 // in the critical section private 
	 int free; // Number of available places in the critical 
	 // section (how many threads are still allowed in the 
	 // critical section in)
	 private int waiting; 
	 // Number of threads waiting in the P operation 
	 // with wait (this is how many threads currently want to enter the 
	 // critical section) 
	 public MySemaphore() { 
		 this(0); 
	 } 
	 public MySemaphore(int i) { 
		 if (i >=0) { 
			 max = i; 
		 } else { 
			 max = 0; 
		 } 
		 free = max; 
		 waiting = 0; 
	 } 
	 protected void finalize() throws Throwable {...}
	 /** * P operation */ 
	 public synchronized void P() { 
		 while (free <= 0) { 
			 waiting++; 
			 try { 
				 this.wait(); 
			 } catch (InterruptedException e) {} 
			 // Increase the number of waiting threads 
			 waiting--; // Reduce the number of waiting threads 
		 } 
		 free--; // Now reduce the semaphore counter 
	 }
	/** * V operation */ 
	public synchronized void V() { 
		free++; // Semaphore counter increase 
		if (waiting > 0) { 
		// Only if another thread is waiting, 
		// notify it with notify 
		this.notify(); 
		} 
	}
 }

Synchornization threads with sync can be problematic for performance due to the monitor management and waiting times overhead. Additional waiting times are due to suboptimal size of the critical sections. Programming with threads is error prone, through human error. But can be remedied through tread-safe data types like `java.util.concurrent.atomic`

#### Deadlocks
Processes or threads can hinder or even block each other, therefore programs can no longer be executed, the tipical problems are, for example when Process P1 has reserved resource B1 and is waiting for B2 which is reserver by P2 which also waits for release of B1, making both processes waiting forever.
![[Pasted image 20240218133013.png]]
**Deadlock Conditions** - needs to be met in order for deadlock to happen and those are:
1. Mutual exclusion - when each resource involved is either exclusively occupied or free
2. Hold and wait - when processes already exclusively user resources (at least one) and request more, since request for all resources is not made at once
3. No preemption - when it is not possible to withdraw resources, process needs to wait for another process to release it
4. Circular waiting - when two or more processes must wait in closed chain for resource that the next one has reserved

Deadlock can be treated in couple of ways which are:
- Detect and Fix - deadlocks are generally permitted but we can detect deadlocks via occupancy graphs and we can terminate process or partially abort due to roll back, meaning using pre-emption so the one of the processes can finish, and other start again or continue from certain point
- Avoid - to globally enforce order for locks on resources which could be difficult to monitor but no circle could be possible. Request for required resources at once and if one is occupied return them all eliminating option to hold an wait. No mutual exclusion is also rarly possible when consistency is required which brings us to conclusion that at least 1 out of 4 conditions must remain unfulfilled

public class myDeadlock{ 
	public static void main(String[] args) { 
		final Object resource1 = new Object(); // Dummy objects just for demonstration final 
		Object resource2 = new Object(); 
		Thread t1=new Thread() ({ new Runnable() {
			public voidrun() { 
				synchronized(resource1) { 
					// do something 
					synchronized(resource2) { 
						// do something 
					} 
				} 
			} 
		});
		Thread t2=new Thread() ({new Runnable() {
			public voidrun() { 
				synchronized (resource2) { 
					// do something 
					synchronized(resource1) {
					// do something 
					} 
				} 
			} 
		}); 
		t1.start(); 
		t2.start(); 
	}
}

#### Communication
Is the exchange of information between people, man and computer systems, and among machines which can be between processes or threads within a PC (local) or between computers distributed in network. There are many aspects of communication in computer systems, the most important ones are:
- **Memory Based** - when communication is exchanged or shared in common memory, which can be:
- **over address space** - when 2 threads communicate with each other in address space
![[Pasted image 20240218135052.png|imlR|400]]
- **shared memory** - when 2 threads from separate address space communicate via shared memory
![[Pasted image 20240218135146.png|inlR|400]]
- **storage access based via shared file access** - when 2 threads separate address spaces communicate via file exchange
![[Pasted image 20240218141140.png|inlR|400]]
- **Message based** - when 2 threads/processes exchange data over uniform protocol, for example it could be over TCP or UDP even with socket interface
![[Pasted image 20240218141502.png|inlR|400]]
- **Connection Oriented** - before data exchange alogical connection is established and then cleared again after exchange ends, before communication clients needs to know about each other
- **Connectionless** - when data is transferred from the sender to the receiver without connection management, the sender address is included in the message
- **Synchronous communication** - is blocking communication
![[Pasted image 20240218141626.png|inlR|400]]
- **Asynchronous communication** - is non blocking communication when sending the message/request. There are variations like:
![[Pasted image 20240218141716.png|inlR|400]]
- **Publish-subscribe model** - when publisher send message of certain type to several interested parties, and reciepient can register as. subscriber for one or more topic with a message broker/publisher
- **Point-to-point model** - is communication between 2 partners with messages being transmitted via a queue
- **Half duplex** - is communication when only one of the partners sends at a time, with altering operation, which requires a solutions for package collision
![[Pasted image 20240218142039.png|inlR|300]]
- **Full duplex** - is communication when both partners can send independently messages to each other
![[Pasted image 20240218142133.png|inlR|300]]
Variants of recipient addressing can be Unicast: when only one recipient is address and following displayed in figure
![[Pasted image 20240218142302.png]]

#### Local Communication
Methods for local communication under Unix and Windows are:
- **Sockets** with IP loopback mechanism
- **Shared memory**
- **Message Queues**
- **Named pipes** (Pipes and FIFO's) as a messaging channel
Pipes are special unidirectional and bidirectional communication mechanism using multiple pipes, bidirectional communication over two pipes can be operated in both half and full duplex
![[Pasted image 20240218143213.png|imlR|400]]
Pipes are used among other things to connect the standard output of process with the standard input of another process like in unix:
`who | sort | lpr`
![[Pasted image 20240218143303.png|inlR|400]]
They are created in unix with system call `pipe()` or `popen()` while in windows `CreatePipe()`, after their usage they need to be closed so system calls for unix `close()` or `pclose()` and for Windows `closeHandle()` need to be called. Parent process can create pipe and inherit them to the child process.
Pipes can be used as blocking (normal mode - meaning if the pipe is full the sending process blocks, or if the pipe is empty the reading process is blocked) and non blocking
![[Pasted image 20240218143615.png|inlR|400]]

#### Network communication
Networks are needed in wide variety of areas, like public switched telephone network, wireless lan, ARPANET as predecessor to internet, Local networks ... Nowadays internet and mobile networks are increasing the degree of networking immensely.

**Distributed communication between processes/threads** - is provided via OS but it is required access to network
![[Pasted image 20240218144206.png]]
![[Pasted image 20240218144215.png|inlR|300]]![[Pasted image 20240218144227.png|inlR|300]]
![[Pasted image 20240218144244.png|inlR|300]]![[Pasted image 20240218144256.png|inlR|300]]