Ch5 Concurrency(병렬성): Synchronization(동기화) #운영체제 #임계구역

Concurrency & Critical Section  🐇¸.•*¨*•¸.•*¨*•¸.•*¨*•¸.•*¨*•

해당 자료는 강의 학습자료입니다.

---

병렬처리를 왜 하는 걸까? -> speed & economics 에서 크게 이점을 볼 수 있기 때문이다.

그러나 병렬 프로그램은 디버깅하기도 힘들고 프로그램을 구현하기도 힘들다. 병렬성을 보장하기위한 동기화에 대해 배워보자.

 

Critical Section (병렬성 & 임계구역, 치명적 영역) 

운영체제가 지원하는 동기화 방법의 하나로 “임계 구역” , “치명적 영역” 으로 보호되어야할 영역을 이름. 공유자원의 독점을 보장해주는 역할을 수행한다.

• 커널 오브젝트를 사용하지 않고 동기화 하는 방법
  • 커널 객체를 사용하지 않고 (가볍고 빠르다, 한 프로세스 내의 쓰레드 사이에서만 동기화가 가능하다.)
  • 서로 다른 프로세스 간에 접근이 불가
• 뮤텍스 (mutex)
  • 커널 객체를 사용, 무거움
  • 크리티컬 섹션이 한 프로세스 내의 쓰레드 사이에서만 동기화가 가능한 반면, 뮤텍스는 여러 프로세스의 스레드 사에 동기화가 가능하다.
  • 프로세스 다중 실행을 막을 때
• 세마포어(Semaphore)
  • 세마포어는 지정된 수 만큼 쓰레드가 동시에 실행되도록 동기화하는 것이 가능하다 (ex/ 화장실의 개수)

 

 

• multiple application (다중응용): invented to allow procession time to be shared among active applications : 데이터 베이스에서 하나의 데이터 또는 그 집합이 여러 분야에서 서로 공통으로 사용 되는 것. 여러 프로그램이 동시에 동작

• Structured Application : extension of modular design and structured programming: 프로그램 모듈화 → 구조화가 되어있음

• Operation System Structure : OS themselves implemented as a set of processes or threads: OS 자체도 병렬성을 가지고 여러 프로그램(processes, threads)이 돌아감 (백그라운드)

 

 

• 디버깅이 너무 어려운 단점 : Scheduler의 결과를 예측을 할 수가 없음. Problem : the relative speed of execution of processes cannot be predicted

OS에 따라 Scheduling 다르게 처리할 수도 있음, interrupts → global value의 문제(shared memory)

• Critical Section (교차로, 사거리)
  • shared double balance 을 예로 설명, Race condition: there is a race to execute critical sections

 

(동시에) 출금 내용을 저장하기 전에 입금하면 출금내역이.. 사라진다! 이는 동시에 compile 하기 때문에 발생한다.

바뀐 값을 업데이트하기 전에 예전 값을 불러와 예전 메모리에 store 하기 때문이다.

i++ 과 같은 경우도 동일하게 발생한다. load i, i+=1 store i 의 3단계로 구성되어 있어 i++과 같은 코드에도 값이 사라지는 현상이 일어난다.

 

 

 

Race condition 경쟁상태 : there is a race to execute critical sections

The sections may be defined by different code in different processes : cannot easily detect with analysis.

여러 프로그램이 공유 자원을 사용하기 위해 움직이는 일종의 경쟁 상태를 의미한다.

 

Mutual exclusion  : only one process can be in the critical section at a time

한 프로세스만 실행될 수 있다. 교차로에 차가 1대만 다니게 하기

without mutual exclusion, results of multiple execution are not determinate

상호 배제가 없다면, 결과를 예측할 수 없다. (잠재적인 버그가 발생할 수 있다.)

Need an OS mechanism so programmer can resolve races : 상호 배제, Mutex 동시 프로그래밍에서 공유 불가능한 자원의 동시 사용을 피하기 위해 사용되는 알고리즘, 임계구역으로 불리는 코드 영역에 의해 구현된다.

 

 

 

그렇다면 어떻게 병렬성을 보장할 수 있을까?

 

1. Disabling Interrupts : 원인인 인터럽트를 제거하자.

disableInterrupts();
balance = balance + amount;
enableInterrupts();

인터럽트를 임의로 비활성화 할 수 있지만 언제까지 이를 막아야 하는지도 모르고 우선순위에 밀리면 아예 실행되지 않을 수도 있다. 또한 인터럽트를 중지하면, 다른 인터럽트도 중지되기 때문에 시스템 전체가 블락될 수 있다.

2. Using a Lock Variable : Lock 변수를 사용하자

사용할 때 Lock으로 잠구고 사용하면 푸는 방법을 이용한다.

while(lock); // do nothing, busy wait

lock = True 면 누군가가 일을 하고 있는것!

 

Busy Wait Condition : 스케줄링에 의해 넘어갔지만 lock이 걸려 아무것도 하지 않는 상태

 

 

Unsafe Solution

자원을 사용하려고 진입한후 lock을 true로 만들기도 전에 time interrupt를 받아 다른 프로세스로 넘어간다면 다른 프로세스도 lock이 걸려있지 않아 두 프로세스 모두 동시에 자원을 사용하여 오류가 발생한다.

따라서 lock도 공유변수이기 때문에 새로운 critical section이 생길 수 있다. 

 

 

Atomic Lock Manipulation - System call, 쪼개지지 않는 함수(time interrupt로 쪼개지지않음)

OS에 의해서만 block되는 system call 함수이고 enter(), exit() 함수로 정의하여 항상 동일한 코드를 수행한다. interrupts가 비활성화되는 시간이 제한되어 있어 몇개의 명령어가 수행되는 동안만 block된다.

lock 할당해도 되는지 확인하는 코드 추가도 가능하다.

 

Deadlock : 두 개의 요소를 처리할 때 서로의 자원이 필요해 무한히 기다리는 상황

윗 상황은 deadlock이 발생하는 경우이다. lock1 변수가 true로 바뀌면 잠기게 되어 다른 process도 막아버린다.

 

 

 

Semaphore : 데드락 해결법

Dijkstra sepaphore : 다이엑스트라가 운영체제에 필요한 개념적인 메커니즘을 제공했다. 개념일 뿐이지만 최신 운영체제의 메커니즘이 기본이 된다.

Critical Section : 문제 해결을 위한 기본 조건 4가지

- mutual Exclusion : only one process at a time in the CS : 오직 한 번에 한 프로세스만 사용한다.

- Only processes competing for a CS are involved in resolving who enters the CS : 외부의 간섭(관리자)없이 프로세스 내에서 규칙을 정하여 경쟁해서 해결한다.

- Once a process attempts to enter its CS, it cannot ve postponed indefinitely : 무한정 연기(지연) 금지

- After requesting entry, only a bounded number of other processes may enter before the requsting process : 요청하기 전에 대기중이던 프로세스(쌓여있는 프로세스)는 한정된 개수만 대기 가능하다.

 

 

위의 4가지 조건을 만족하여 해결한 것을 세마포어라고 한다.

세마포어 : Semaphore

s is a nonnegaive integer variable that can only be changes or tested by these two indivisible functions:

음이 아닌 정수 (1,2,3..)로 이루어진 변수이며, 체크하는 함수, 시그널을 주는 함수 두 가지가 있다.

Verhogen : increase(증가, 정수를 +) / Proberen : try(testing) 사용해도 되는지 확인

P는 0인 동안에는 기다려야한다. (초깃값이 1이면 들어와서 -1로 0으로 잠구고 사용한다.)

 

semaphore mutex =1; // 세마포어 변수이름이 mutex이다.

 

P()

진행할 코드

V()

 

fork(proc_0,0); // run

fork(proc_1,0); // run

 

Sharing Two variables

V로 신호를 주면 P로 받는다.

proc_A(){
	while(TRUE){
    update(x);
    V(s1);
    
    P(s2);
    retrieve(y);
    }
}

 

세마포어 초깃값을 이용해 조정할 수 있다.

P,V 순서가 따로 정해져 있지는 않다.

Counting semaphore - interger variable : 여러 정수를 가질 수 있다.

Binary semaphore : 0~1 mutex lock 

 

 

Deadlock and Starvation

Deadlock : two or more processes are waiting indefinitely for an event that can be caused by only one of the waiting processes // 요청한 시그널을 무한 waiting, block 되어 있는 상태

 

Let S and Q be two semaphores initialized to 1

 

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 nedded by higher-priority process

time scheduling에 의해 우선순위 역전 현상이 일어날 수 있다.

역삼각형 모양은 Critical Section인데 즉, 공유메모리이다. 프로세스 t3가 실행되고 우선순위가 높은 t1이 공유변수를 필요로 할때 P()함수로 block이 걸릴 수 있다. 이때 t3 가 제때 공유변수를 돌려주지 않으면 우선순위 역전현상이 이러난다.

 t3는 우선순위가 낮기 때문에 다른 프로세스가 실행되면 끝날때까지 기다려야해서 t3가 공유메모리를 한참 뒤에 돌려주게 되기 때문에 t1은 우선순위가 높아도 가장 늦게 끝나게 된다.

 

따라서 이를 해결하기 위해서 같은 CS를 사용하면 우선순위가 아래인 t3에 t1의 우선순위를 상속한다. 이를 priority inheritance(우선순위상속) 라고 한다.

 

---

 

 

다이엑스트라의 해결법

 

생산자와 소비자 문제

생산자(producer): 정보를 만들어냄, update , ex)print program

소비자(consumer): 정보를 사용함. ex) printer

 

 

한정된 개수의 buffer가 있는데  buffer는 item을 hold 한다. producer가 full pool의 buffer을 사용하면 다시 empty pool에 담는다.

 

여러명이 함께 사용하는 경우 (web)

reader : 독자, update하지 않기 때문에 여러 명이 읽을 수 있다.

writer : 작가, 작성할 때는 한 명만 접근해야한다.

첫번째 독자가 방을 잠구고 (모든 writer 과의 경쟁)

마지막 독자가 signal을 보냄

writer가 모든 reader을 기다려야 하기 때문에 starvation 발생할 수 있다

 

보통은 writing을 더 우선순위를 주거나 권한을 준다.

윗 그림 설명 : 프로세스 1 reader가 화살표까지 실행

프로세스 2 reader가 P(readBlock)까지 실행하고 실행중 0이됨

프로세스 3 writer 접근하여 0이라 이후 실행 못함

프로세스 4 P에 접근하여 0이라 이후 실행 못함

 

프로세스2가 V(readblock)을 두 번 실행해야하는 상황이 발생이라는데 잘 이해가 가지않아 정리하면, 프로세스3이 writer만 순차적으로 실행되거나,  프로세스2가 끝까지 실행되기만 해도 V가 모자라는 경우가 없다. 아무래도 P가 동시 실행되어 lock이 걸린 경우. V로 돌려줄때 하나만 돌려주는건데 이걸 관리하는 관리자가 없어 둘다 자기꺼인줄 알고 받아 결국 키의 총합 개수가 엉키는 거같다.

 

따라서  readblock 조차도 1개씩만 사용하게 만든게 writePending변수를 사용하는 방법이다.

it is imperative that the P and V operations be implemeted as atomic primitives : atoimic으로 구성한다.

소프트웨어뿐만 아니라 하드웨어로 세마포어를 구성할 수도 있다.

Dekker's, Perterson's 알고리즘으로 구현할 수 있는데 세마포어를 구현하면 오버헤드가 굉장히 크게 발생한다.

운영체제에서 세마포어를 지원하고 있다.

 

 

 

철학자들의 저녁식사

철학자 5명, 젓가락 5개로 구성, 철학자들은 thinking, eating 동작을 수행, 양옆의 젓가락 2개를 함께 사용 가능할때만 식사가능 = 이웃한 철학자는 동시에 식사 절대 불가능

젓가락 = shared data // CS

 

세마포어를 중첩에서 사용한다. P(0) p(1) 둘다 젓가락이 있어야 eat() 가능

동시에 한쪽 젓가락만 잡으면? -> 모두가 나머지 하나를 기다리는 상태 -> deadlock

짝수 오른쪽부터 들기, 홀수인사람은 왼쪽부터 들기

 

결론 : (Nesting)중첩 세마포어를 사용하면 deadlock이 발생할 수 있다.

서로다른 프로그래머에 의해 작성된 코드라 임의의 순서로 구현한다.

 

-> P연산을 안전한 데이터 사용을 위해서 추상화하여 하나의 연산으로 이용하자.

 

AND synchronization : 여러개 semaphore을 묶어서 처리할 수 있다. => 두개가 모두 가능해야 처리 가능하다.

Psimultaneous(S1,S2...Sn): P 전체 대기블럭

 

Semaphores provide a powerful tool for enforcing mutual exclusion and coordinate processes

But wait and signal are scattered among several processes. Hence, difficult to understand their effects.

Usage must be correct in all the processes

One bad process can fail the entire collection of proecesses

 

---

Event

Exact definitition is specific to each OS:운영체제 마다 다름

a process can wait on an event until another process signals the event : 기다리는 프로세스에게 signal을 줄 수 있다.

 

event descriptor : event control block : signal은 1개만 받음. broadcast x

Active approach

- multiple processes can wait on an event

- exactly one process is unblockes when a signal occurs

- A signal with no waiting process is ignored

 

May have a queue function that returns number of processes waiting on the event.

topOfHour.wait(): 정시가 되면 ㅡ  signal을 보냄.

 

 

Unix signal : it is raised by one process to call nother process's attention to an event

프로세스나 사용자가 신호를 줄때 사용하거나, 시스템상의 오류가 발생할 때 사용된다.

it can be caught by the subject process

 

Justification for including signals was for the OS to inform a user process of an event

Ctrl + C => interrupt, 2 / or 나만의 핸들러를 만들 수도 있다.

Program tried to divided by zero  

	Active semaphore (if)	passive semaphore (while)
발생 시점	signal 발생 시점	발생하고 필요할 때
성능	느림 : target switching -> overhead	빠름 : 병렬컴퓨팅
이름	Hoare semantics	Brinch Hansen semantics

 

 

 

Monitors

Specialized form of ADT(Abstract Data Type) : encapsulates implementation

 

한번에 하나의 balace를 접근할 수 있도록

writer , reader 하나의 책 등 보호가 된다.

 

reader writer 사이의 deadlock이 발생할 수 있다.

suspend 가 필요하겠다.

 

 

 

suspend : 조건이 만족할 때까지 (잠깐의)중지

condition variable : monitor안에서 사용하는 event의 특별한 형태

 

wait() : suspend invoking process until another executes a signal

signal() : resume one process if any are suspended, otherwise do nothing

queue(): return TRUE if there is at least one process suspended on the condition variable : 하나의 프로세스가 suspended라면 true를 반환 아니면 false, 대기하고 있는 동료

 

철학자들의 저녁식사에 적용하기                

                                                                                                                                                                                                                                                                                                                                          

test에서 양쪽으로 signal을 줌 wait였던게 signal 을 받으면 실행된다.

 

 

pthread mutex

 

variables	pthread_mutex_t
initialize	pthread_mutex_init
setting	pthread_mutex_lock
Unsetting	pthread_mutex_unlock
Destroy	pthread_mutex_destroy

mutex를 사용시 최대한 범위는 작게 잡아야한다.

#include <pthread.h>

pthread_mutex_lock(&lck);
balace += dep[i];
pthread_mutex_unlock(&lck);

 

semaphore

 

#include <semaphore.h>

 

int sem_init(sem_t *sem, int pshared, unsigned int value);

int sem_wait(sem_t *sem);

int sem_post(sem_t *sem);

omt sem_destory(sem_t* sem);