[OS] Competing Process

seunghyunยท2023๋…„ 3์›” 7์ผ
0

๐Ÿ’ป

๋ชฉ๋ก ๋ณด๊ธฐ
3/16

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] ์ตœ๋ฆฐ ๊ต์ˆ˜๋‹˜์˜ ์šด์˜์ฒด์ œ ๊ฐ•์˜๋ฅผ ์ˆ˜๊ฐ•ํ•˜๊ณ  ์ •๋ฆฌํ•œ ๋‚ด์šฉ์ž…๋‹ˆ๋‹ค. ์ž˜๋ชป๋œ ๋‚ด์šฉ์ด ์žˆ๋‹ค๋ฉด ๋Œ“๊ธ€๋กœ ์•Œ๋ ค์ฃผ์‹œ๋ฉด ๊ฐ์‚ฌํ•˜๊ฒ ์Šต๋‹ˆ๋‹ค ๐Ÿ˜Š

profile
๐Ÿ‘ฉ๐Ÿปโ€๐Ÿ’ป๐ŸŽฎ

0๊ฐœ์˜ ๋Œ“๊ธ€