[OS] icpc

Interprocess Communication

Process State

• New : process가 처음 생성되었을 때.
• Ready :프로세스가 프로세서에 할당되기를 기다릴때.
• Running :프로세스가 할당되어 실행될 때.
• Waiging :프로세스가 이벤트를 기다릴 때.
• Terminated :프로세스가 실행을 마쳤을 때.

Three Issues

• How one process can pass information to another
• Making sure two or more processes do not get into each other's way when engaging in critical activities
• Proper sequencing when dependencies are present
  - If process A produces data and process b prints them, B has to wait until A has produced some data before starting to pring

Race conditions

• Situation where two or more processes are reading or writing some shared data at the same time and the final result depends on who runs precisely when

Critical region

• Mutual Exclusion *
  - If one process is using a shared variable or file, the other processes will be excluded from doing the same thing./ Race condition을 없애기 위해서 제공되는 mechanism이다.
  Critical region
  A part of a program where the shared memory is accessed.

Four conditions of a good solutions to critical-section problem

• No two processes simultaneously in critical region
• No assumptions made about speeds or numbers of CPUs
• No process running outside its critical regio may block other processes(Strict Alternation 위반)
• No process must wait forever to enter its critical region

Mutual Exclusion with busy wating

• disabling interrupts
  - Disalbe all interrupts just after entering its cirtical region and re-enable them just before leaving it. 요점은 Mutual exclusion 다른 process 끼어들지 않게 해야하고 context switches 불가능
• lock variable
  - software solution
  - Use of shared variable
  - when a process wants to enter its critical region, it first tests the lock.
  - If the lock is 0, the process sets it to 1 and enters the critical region.
  - If the lock is already 1, the process just waits until it becomes 0.

context switch

프로세스가 실행되다가 인터럽트가 발생해 운영체제가 개입하여 프로세서에 할당된 프로세스를 바꾸는 것을 말한다. 시스템콜을 사용해야 하는 경우 프로세슷가 자체적으로 처리할 수 없기 때문에 운영체제가 개입해야한다. 컴퓨터 과학에서 컨텍스트는 내 시스템에서 활용 가능한 모니터링된 정보들을 의미한다. 프로세서 입장에서 컨텍스트는 pcb이기 때문에 pcb 정보가 바뀌는 것을 컨텍스트 스위치라고 부른다.

Semaphore (반드시 외우기)

• semaphore
  - New variable type introduced by E.W. Dijkstra
• Usage
  - down(P) operation
  - ciritical region
  - up(V) operation

down(P) operation

• If a semaphotre is greater than 0, it decremetns the value and just continues.
• If the semaphore is 0, the process is put to sleep without completing the down for the moment.

up(V) operation

• If one or more processes were sleeping on that semaphore, unable to complete an earlier operation, one of them is awakened and allowed to complete its down
• Otherwise, incremetns the value of the semaphore addressed.

Each operation above is indivisible atomic action

• Solving the Producer-Consumer Problem using Semaphore
  - Semaphores solve the lost-wakeup prob.
  - For mutual exclusion
  - Mutex
  - makes sure the producer and consumer do not access the buffer at the same time

  		- binary semaphore : initialized to 1 and used by two or more processes to ensure that only one of them can enter its critical region at the same time
  
  	- For synchronization
  		- Guarentees that the producer stops running when the buffer is full, and the consumer stops running when it is empty
  	- full
  	- empty

semaphore and mutext

• semaphore는 공유된 자원의 데이터 혹은 critical region등의 여러 process 혹은 thread가 접근하는 것을 막아준다. 동기화 대상이 하나 이상이다. mutext도 동일하나 동기화 대상이 하나이다.

critical region은 다중 프로그래밍 운영체제에서 여러 프로세스가 데이터를 공유하면서 수행될 때 각 프로세스에서 공유 데이터를 접근하는 프로그램 코드의 부분이다. 공유데이터를 여러 프로세스가 동시에 액세스하면 시간적인 차이 등으로 인하여 잘못된 결과를 만들어 낼 수 있기 때문에 한 프로세스가 위험 부분을 수행하고 있을 때, 공유데이터를 액섹스하고 있을 때는 다른 프로세스들은 절대로 그 데이터를 액세스하지 못하게 한다.

mutex

• simplified version of the semaphore
• A variable that can be in one of two stages
  - Unlock :0
  - Locked :Non-zero
  

Monitors

• problem with semaphores
  - Hard to use
• Monitor
  - High-level synchronization primitive
  - process cannot directly acces the monitor's internal data structures
• Mutual exclusion
• Programming language construct
• condition variables with two operations:
  - wait
  - causes the calling process to block on a cindition variable
  - Allows another process tp enter the monitor
  - signal
  - wakes up the process sleeping on the condition variable

Message passing

• Method of interprocess communication
  - send
  - receive
• Design issues
  - Messages can be lost by the network
  - uses ack
  - ACK를 사용하더라도 만약 전달이 안되면 문제가 발생된다.

use of barrier

• processes approaching a barrier
• 모든 프로세스가 도착을 해서 barrier primitive를 동작 시켜야 리턴될 수 있다.
  

Dining Philosophers