[운영체제] 6장 Synchronization

여기서부터 무척 중요함(이해하기 어려움)

다중프로세스를 사용해야 Synchronization을 이해할 수 있음

Synchronization – 멀티스레드, 멀티프로그래밍 환경에서 일어나는 문제들을 해결하는 방법(두개 이상의 프로세스들이 쉐어드 메모리에 접근을 하려는 경우에 레이스 컨디션이 발생함 이러한 상황을 해결 해줘야함)

 

Synchronization

두개 이상의 멀티 스레드가 사용되는 멀티프로그래밍 환경에서 shared data를 사용하는 경우 동기화가 필요함 -> 스레드들의 실행순서를 조절하기 위한 것임.

Shared data structure에서 동기화는 필수적임

IPC - 프로세스들 간의 통신을 말하는 것

두 개의 프로세스는 직접적으로 데이터를 주고받을 수 없는데 이러한 상황에서 데이터를 주고받기 위한 두가지방법 -> shared memory기법, message passing(수신하는 프로세스에서 신호를 기다렸다가 데이터가 들어오면 수행을 함)기법

Synchronization – 데이터를 주고받을 때 signal(데이터를 보내줄 때 신호를 주는 것)과 wait(데이터를 받기 위해 기다리는 것)을 통해 이루어짐

 

동기화 예시 ATM기 돈 찾기(커플통장공유)

돈을 찾는 과정에서 데이터베이스에 트랜잭션이 발생

 

 

Synchronization Problem

동기화 문제 발생

concurrent threads – CPU하나에 스레드 여러 개가 수행이 되어 마치 동시에 프로세스가 수행되는 것처럼 보이는 것

-> shared resource에서 문제가 발생할 수 있음

parallel threads – CPU가 여러 개이고 여러 개의 프로세스를 병렬적으로 수행함

deterministic – 항상 같은 결과가 나오는 것(ex. 컴퓨터 프로그래밍)

race condition – non-deterministic(실행 때마다 다른 결과가 나올 수 있음)하게 프로세스가 수행됨(디버깅 시에도 이러한 상황을 정확히 알기 어렵다)

-> 여러 프로세스들이 shared data를 마구 access하는 상황

프로듀서 - 데이터를 짚어 넣는 프로세스

컨슈머 – 데이터를 사용

어디서 -> Bounded-Buffer(집어넣는 곳 – shared data) -> shared memory

 

shared data 구현

 

Producer process 구현

 

Consumer process 구현

 

위에 두 가지 프로세스에서 race condition이 발생할 수 있음

 

race condition발생 예시

 

race condition – 프로세스들이 동시에 CPU에 접근하는 상황

 

 

The Critical-Section Problem

Critical-Section(동기화문제) – shared data를 access하는 코드레벨에서의 구간(race condition을 유발하는 코드레벨 영역), 임계영역

문제 발생 이유 – 여러 프로세스가 동시에 CPU에 접근하여 수행되려고 하기 때문에

따라서 Critical-Section에 하나의 프로세스만 접근가능하게 해야 문제를 해결할 수 있음

 

Solution to Critical-Section Problem

Critical-Section 해결 방안

• Mutual Exclusion - Critical-Section에 들어오면 하나의 프로세스만 수행되게 하는 것(상호배제, 나만 사용한다!, 자신의 사용하고 있으면 남은 사용 못하게)
• Progress - 현재 안무도 사용하고 있지 않다면 바로 내가 사용한다.
• Bounded Waiting – 한 프로세스가 독점적 사용을 막는 것

 

위 3가지 조건을 만족시키면 해결할 수 있는 방안

동기화문제 해결방안

• Locks -> Critical-Section에 접근하는 것을 막는 것(제일 간단하면서 이해가 쉬움)
• Very primitive, minimal semantics, used to build others(Critical-Section이 빌 때까지 무한루프를 돌게 하는 것)
• Semaphores
• Basic, easy to get the hang of, hard to program with
• Monitors
• High-level, requires language support, implicit operations
• Easy to program with: Java “synchronized”
• Messages
• Simple model of communication and synchronization based on (atomic) transfer of data across a channel
• Direct application to distributed systems

 

 

Locks함수 구성

Locks함수 사용 예시

lock을 통해 실행하고 unlock을 통해 빠져나감 – 그림예시참고

 

lock(=1)과 unlock(=0) 함수 구현

spin-lock – 무한 루프를 통해 동기화를 맞추는 것

-> 정확하게 Critical-Section보호가 불가능함 -> 다른 interrupt가 발생하면 다른 프로세스가 접근이 가능해짐

 

위의 문제 해결을 위해 Atomic operation을 적용해야함

-> 더 이상 쪼게 져있는 부분이 없게 만드는 것

해결방법 3가지

> 소프트웨어 알고리즘을 통해 해결(but 오버헤드가 크게 발생...실제 사용x)

> HW atomic instructions – 하나의 명령어로 만들어버리면 CPU에서 하나의 덩어리로 수행을 하기 때문에 해결가능(test-and-set을 많이 사용)

> Disable/re-enable interrupts - 근본적인 문제 context switch가 발생하지 않게 interrupt를 disable시킴(이게 많이 사용됨)

 

 

소프트웨어적으로 문제 해결

Critical-Section 해결 방안 위해선 Mutual Exclusion(프로세스가 사용 중이면 다른 프로세스 접근을 불가능하게 하는 것), Progress(프로세스가 사용 중이지 않다면 다른 프로세스가 바로 사용되게 하는 것), Bounded Waiting(프로세스가 무한히 기다리는 것을 막는 것) 이러한 세 가지 방법이 있음

위 3가지를 고려하여 구현을 해야 함

entry section – 요청을 구현하는 부분(lock구현 필요)

critical section – 진입허가가 나면 이동되는 곳

exit section – 수행이 완료되면 알려주는 코드부분(릴리즈 필요)

remainder section – 그밖에 나머지 코드부분 총칭

 

프로세스 별로 턴을 넘겨주는 방식으로 프로세스 차례를 넘겨주는 방식을 사용함

교대로 프로세스가 들어감 -> Progress부분에 맞지 않음 I가 한번만 들어갈 수 있음

 

다음 방법 flag를 통해 critical section진입을 true로 표시해주고 끝마침을 false로 표시해서 프로세스를 진행시킴 -> 앞 알고리즘의 문제점인 수행하는 프로세스가 없다면 바로 다른 프로세스가 수행될 수 있게 하는 부분을 해결함

but context switch 발생 일어나서 오류가 발생할 수 있음.

-> turn과 flag로는 하나만 고려하면 한계가 있음

 

피터슨 알고리즘

turn과 flag를 같이 생각해주면서 위에 문제들이 발생하는 것을 방지할 수 있음

 

베이커리 알고리즘(Bakery Algorithm)

위에 것들은 두 가지 프로세스만 관리함 하지만 더 많은 프로세스들을 관리하는 알고리즘도 필요함

순서 오름차순으로 분배

 

choosing -> flag와 비슷한 역할을 함

 

베이커리 알고리즘 구현

-> 번호 우선순위 알고리즘(FCFS에 기반 함, 굶주림 문제도 없음)

 

하드웨어적으로 문제 해결

 

Test-and-set

Mutual Exclusion(프로세스가 사용 중이면 다른 프로세스 접근을 불가능하게 하는 것), Progress(프로세스가 사용 중이지 않다면 다른 프로세스가 바로 사용되게 하는 것)이것 두 개는 만족 but Bounded Waiting(프로세스가 무한히 기다리는 것을 막는 것)는 만족x

 

 

Mutual Exclusion with Swap

swap 방식 구현

-> 어떤 프로세스가 수행될지 모르기 때문에 Bounded Waiting는 만족 못함

 

 

Problems with Spinlocks

spinlock -> cpu 점유가 심함...

lock을 이용한 동기화 방법이 많이 사용됨

 

Higher-level로 구현하는 것이 일반적이다.

 

 

Higher-level Synchronization

여러 프로세스가 쉐어드 데이터에 동시 접근하는 것을 방지하기 위해 알고리즘을 도입시킴

피터슨 알고리즘(플래그 변수를 두어 문제해결), 베이커리 알고리즘(프로세스별 번호를 부여하여 순서를 정해줌)

앞에서 말한 3가지 조건을 만족시킴(한 프로세스만 접근할 수 있게 하는 조건들)

 

HW Instruction -> test-and-set(lock을 통한 해결, critical sections 접근을 제한함), swap -> 이 두 가지는 lock변수를 어떻게 두느냐에 따라 차이가 있음

 

하드웨어적으로 동기화 제어 -> disabling - 커널을 통한 제어만 가능(interrupt를 통제함, 오버헤드가 큼)

 

c언어와 같은 언어 -> Higher-level language

assembly language -> Low-level language

-> 구분 기준 : 사람이 이해할 수 있는가?

 

Higher-level Synchronization – 사용자와 밀접함(c언어와 같은 언어를 통한 동기화 방법)

-> 언어를 통한 동기화 방법

 

 

Semaphores

Semaphore S(정수 값) – 쉐어드 데이터의(사용할 수 있는) 개수를 체크함

-> wait(쉐어드 데이터를 사용하겠다고 선언-잠김, Semaphore의 개수가 없으면(=0) 대기–queue를 통해 기다리게 함), signal(쉐어드 데이터를 반납함) 이두 개의 함수만 사용가능

 

 

Semaphore 구현 예시

초기 쉐어드 데이터 값 = 1로 초기화

wait, signal은 lock, unlock방식과 유사함

 

Semaphore를 저장 할 수 있는 자료구조가 필요함

value – Semaphore값 저장

Semaphore의 사용가능을 나타내주는 L값을 부여해줌

 

Semaphore 구현

wait과 signal함수 구현

lock과 unlock을 통해 원자단위로 쪼게 지는 것을 방지해줌

Semaphore의 값을 판단해 처리해주는 방법이 중요

 

Semaphore 구현

Pi가 수행이 완료되어야 Pj가 수행이 가능함

-> 동기화 문제 해결은 Semaphore을 통해 가능함 (플래그 값을 0으로 둠)

A까지 사용을 해야 쉐어드 데이터가 생김

플래그 값이 양수가 되어야 다음 단계 수행가능

 

Deadlock and Starvation

Deadlock은 7장에서 다시 배움 여기선 간단히

-> 영원히 아무것도 수행할 수 없는 상황

 

Semaphore 종류

Counting semaphore -> semaphore값이 양수로 존재

• integer value can range over an unrestricted domain

Binary semaphore ->(semaphore를 critical section 보호에만 사용하면) semaphore값이 0과 1만 존재

• integer value can range only between 0 and 1
• can be simpler to implement

 

Synchronization의 고전적 문제 - 3가지

• Bounded-Buffer Problem
• Readers and Writers Problem
• Dining-Philosophers Problem

 

Bounded Buffer Problem

Bounded Buffer 문제

-> 프로듀서와 컨슈머 프로세스 존재

Buffer안에 있는 데이터 사용에 따라 구분

프로듀서 프로세스 - 원형 큐가 꽉 차기 전까지만 수행가능

컨슈머 프로세스 - 데이터 사이즈가 0이면 무한 루프, 꺼낼 데이터가 있으면 사용함

-> 동기화를 제공해주는 요소가 현재 존재x

but 멀티스레드 방식이라 동기화과정이 없으면 count변수가 이상하게 바뀌며 critical section 문제가 발생할 수 있음

 

Bounded Buffer 문제해결

wait과 signal 함수를 추가하여 문제해결(mutex변수를 추가하여 Semaphore변수를 추가해줌)

원형 큐에 빈 공간 체크가 중요함(empty변수로 체크 – 초기 값은 전체 큐의 공간개수로 초기화)

 

 

Readers-Writers Problem

Readers-Writers문제 – 데이터를 사용하는 와중에 읽거나 쓰게 되면 문제가 발생함

-> Reader, Write는 동시 진행되면 안됨, Read와 Read는 동시 진행 가능(데이터 변경이 이루어지지 않기 때문), Write는 Write와 동시 진행되면 안됨

 

Read, Write시 wait와 signal함수를 사용하여 동기화 진행(mutex, wrt 변수 지정)

readcount를 변경 시에도 동기화가 필요하기 때문에 wait와 signal함수를 적용시켜줌

 

 

Dining Philosopher

Dining Philosopher(철학자 다이닝 문제) 문제 – 젓가락(공유 데이터)을 공유하는 문제

각각의 젓가락에 Semaphore를 두어 문제 해결

 

 

Dining Philosopher 문제해결 간단구현

모두 한쪽만 선택하게 되면 deadlock(교착상태)현상이 발생함

 

Deadlock-free version 구현 -> but starvation문제가 발생할 수 있음(한 철학자가 무한히 굶는 일이 벌어짐)

deadlock을 해결하기 위한 방법

shared data 사용 시 동기화를 유의해야하고 해결 시 더불어 deadlock을 유의해줘야 함

젓가락에 Semaphore를 두지 말고 양쪽을 확인하고 두 쪽이 모두 비어있으면 모두 들게 함

Semaphore s를 전역변수로 선언(0으로 초기화됨, 실행이 안됨)

test함수를 통해 밥을 먹을 수 있는지 없는지를 확인함

-> 양쪽 젓가락 점유

Semaphore값을 사람에게 둠

질문 -> 이미지 파일을 켜두고 이동이 가능한 걸 이해하겠는데

HWP역시 켜두고 이동 못하는 것이 수정이 가능하기 때문임

그런데 메모장은 왜 켜두고도 이동이 가능한지(수정이 가능하잖아..?)

프로그램의 구조적 차이임(자세히 알기 어려움)

 

 

 

Problems with Semaphores

잘못 구현 시 전체 시스템에 문제가 생김 -> 사용이 어렵다(읽어볼 것)

위의 문제들로 인해 나온 것이 Critical Region임

 

Critical Regions

쉐어드 데이터 부분에 동시에 접근(Critical Section)하는 과정에서 동기화과정이 필요함

High-level synchronization -> 어플리케이션 레벨에서 일어남

언제 변수들을 설정하고 동기화 함수들을 둘 것인지를 개발자들이 잘 판단해야함!

-> 문제가 많이 일어남

해결을 위해 동기화 부분을 컴파일러부분과 language부분에서 구현되게 하자

방법자체는 앞(Semaphore – 개발자가 구현)과 동일함 -> 하나의 프로세스만 점유하게 하는 방법

문제를 풀어가는 방법이 다름

 

count가 n보다 작아야함 -> 이것을 프로그램 language차원에서 구분함

 

소스코드레벨, 컴파일레벨에서 동기화를 해주는 방법 -> Critical Regions

 

 

Monitors

Monitors – 동기화문제를 해결하는 방법(Critical Regions에 한 단계 발전한 것)

프로그램 언어 수준에서 수행하는 동기화 기법(상호배제를 위함)

내부 안에 shared data가 존재함

한 시점에 하나의 프로세스만 모니터 내부에서 접근이 가능함

shared data -> 프로시저

 

Monitor 코드 예제

안에다 쉐어드 변수를 만들고 접근할 수 있는 방법을 만듦

동시에 접근할 수 없게 만들어 줘야함(각각의 프로시저에 함수처리) -> 이렇게 하지 말고 모니터 함수 자체에서 처리를 하게 해줌(개발자에게 편의를 부여해줌, 이 개념은 자바에만 존재함, C++에는 없음 – 따라서 Semaphore 변수를 만들어 동기화 해주어야함)

 

condition variable – wait과 signal을 제어하기 위한 메커니즘

 

Monitor 구조 – 커다란 방처럼 되어있음(한 프로세스만이 접근을 할 수 있음, 정보 은폐가능)

entry큐 – 모니터에 접근하려는 프로세스들을 줄을 세워두는 큐

 

Monitor 구조 계속

컨디션큐 – 프로세스의 대기실(특정 이벤트(함수)를 기다림)

컨디션변수-> wait과 signal함수만 접근가능

세마모어와 모니터의 차이 Semaphore는 수행되고 있는지를 판단하여 대기를 시킴

모니터의 경우에는 wait함수를 실행하면 곧바로 대기상태에 머물게 됨, signal은 같은 기능을 함

 

Dining Philosophers 예시

배열변수 5개 -> 철학자 5명

각각의 상태 저장 5개

test함수를 통해 상태를 판단함

 

 

 

 

Monitors and Semaphores Comparison

Semaphore는 현재 상태를 파악하는 절차가 추가되어 있음

 

 

Mutex Lock

Mutex Lock을 통해서 구분 앞과 동일 skip

while문을 통한 CPU점유

 

 

Synchronization Mechanisms

Lower-level mechanism

• Disabling interrupts
• Spinlocks  -> Busy waiting -> 무한루프를 통해 대기시킴

Higher-level mechanism -> 상위 단 어플리케이션 레벨에서 구현

• Semaphores -> 변수를 counting 해서 접근을 판단

-Binary semaphore = mutex (lock 유사)

-Counting semaphore

• Monitors -> condition variable를 통해서 동기화 문제를 해결

-Language construct with condition variables

• Mutex + Condition variables