Sharing of global resources can create

• Need for mutual exclusion (mutex)
• Deadlock
• Starvation

Sharing of global data may lead to race condition.

race condition

This occurs when two or more process/threads access shared data and they try to change it at the same time. Because thread/process scheduling algorithm can switch between threads, you don't know which thread will access the shared data first. In this situation, both threads are 'racing' to access/change the data.

Operations upon shared data are critical sections that must be mutually exclusive in order to avoid harmful collision between processes or threads.

critical section

A section of code within a process that requires access to shared resources and that must not be executed while another process is in a corresponding section of code

atomic operation

✔️ critical section, semaphore 등을 구현하기 위해 모든 CPU가 atomic 연산을 제공한다.

✔️ "Atomic" means

• Indivible, uninterruptable
• Must be performed atomically, which means either "success" or "failure"
  • Success : successfully change the system state
  • Failure : no effect on the system state

✔️ Atomic operation

• A fuction or action implemented as a single instruction or as a sequence of instructions that appears to be indivisible
  • No other processes can see an intermediate state
• Can be implemented by HW or SW
• HW-level atomic operations
  • Test-and-set, fetch-and-add, compare-and-swap, load-link, store-conditional
• SW-level solutions
  • Running a group of instructions in a critical section

💡 atomic instruction 을 사용하여 lock 변수를 구현하면 process, processor 수에 상관없이 공유자원을 사용할 수 있다. 직관적이고 여러 개의 critical section 을 구현할 수 있다.
그러나 Busy-waiting 해서 비효율적이고, 스케줄링에 의해 Starvation, Deadlock 이 가능하다 라는 단점이 있기에 좀 더 논리적인 mutual exclusive 에 대한 이상적인 SW적 해결방안이 필요했다. 그래서 등장하는 것이 semaphore 이다.

semaphore 🔒

세마포어라는 자료구조가 있다면 우리가 원하는 mutual exclusive critical section 을 구현할 수 있지 않을까 라는 기대!

✔️ A variable that provides a simple abstraction for controlling access to a common resource in a programming environment

✔️ The value if the semaphore variable can be changed by only 2 operations

• V operation (also known as "signal")
  • Increment the semaphore
• P operation (also known as "wait")
  • Decrement the semaphore
• The value of the semaphore S is usually the number of units of the resource that are currently available.

✔️ Type of semaphores

• Binary semaphore
  • 0 (locked, unavailable)
  • 1 (unlocked, available)
• Counting semaphore
  • Can have an arbitrary resource count

✔️ Definition of Counting semaphore

struct semaphore
{
	int count;
    queueType queue;
};

void semWait(semaphore s) // P
{
	s.count--;
    if(s.count<0)
    {
    	/*place this process in s.queue */
        /*block this queue*/
    }
}

void semSignal(semaphore s) // V 
{
	s.count++;
    if(s.count <=0)
    {
    	/*remove a process P from s.queue */
        /*place process P on ready list*/
    }
}

example

Example of Semaphore Mechanism

Mutual Exclusion (critical section) Using Semaphores

 const int n = number_of_processes;
 semaphore s = 1;
 void P(int i)
 {
 	while(true)
    {
    	semWait(s); // P
    	/*critical section*/
        semSignal(s); // V
        /*remainder*/
    }
 }
 
 void main()
 {
 	parbegin( P(1), P(2), ..., P(N) );
 }

---

Message Passing

When processes interact with one another, the following actions must be satisfied by the system

• Mutual exclusion
• Sychronization
• Communication

Blocking/Nonblocking Send/Receive

✔️ Blocking send, blocking receive

• Both sender and receiver are blocked until the message is delivered
• Sometimes referred to as a rendezvous

✔️ Nonblocking send, blocking receive

• The moust useful combination

✔️ Nonblocking send, nonblocking receive

• Neither party is required to wait

Addressing

Direct addressing

Indirect addressing

Synchronization

✔️ Communication of a message between two processes implies synchronization between the two

• The receiver cannot receive a message until it has been sent by another process

✔️ Both sender and receiver can be blocking or nonblocking

• when a send primitive is executed, there are two possibilities
  • Either the sending process is blocked until the message is received, or it is not
• When a receive primitive is executed there are also two possibilities

---

🔗 Reference

[KUOCW] 최린 교수님의 운영체제 강의를 수강하고 정리한 내용입니다. 잘못된 내용이 있다면 댓글로 알려주시면 감사하겠습니다 😊