운영체제(6) Synchronization Tools & Examples

 
 

1. 용어 정리

 

By 챗지피티

 
<Atomic operation>
여러 CPU가 공유자원에 접근할 때 프로세스 또는 스레드가 동시에 엑세스하지 않도록 하기 위해,
동시성 제어와 데이터 무결성을 보장하기 위해,
다른 프로세스 또는 스레드가 해당 데이터를 변경할 수 없는 상태로 보호하는 연산이다. 
-> 특정 시기, critical section 시기에는 오직 1개의 스레드만 관여한다. 
-> 하나 이상의 명령 시퀀스로 구현된 기능 또는 동작이다. 
    즉, 다른 프로세스는 중간 상태를 보거나 작업을 중단할 수 없다. 
-> 명령 시퀀스는 그룹으로 실행 or 전혀 실행되지 않으며 시스템 상태에 가시적인 영향을 미치지 않는다. 
-> good 출처 : https://eunjinii.tistory.com/160
 
<Critical section>
공유 자원에 대한 권한이 필요하고 다른 프로세스가 해당 section에 있는 동안에는 실행할 수 없는 section.
 
<Some conditions>
(1) deadlock : 두 개 이상의 프로세스가 서로 작업 수행하길 기다리며, 어떠한 프로세스도 진행하지 않는 상태
(2) livelock : 두 개 이상의 프로세스가 유용한 작업을 수행하지 않고,
     다른 프로세스의 변화에 대응하여 상태를 지속적으로 변경하는 상황 (상태 변경만 주구장창 -> 진행 안됨)
 
<Mutual exclusion>
한 프로세스가 (공유 자원에 access하는) critical section에 있을 때, 그 section엔 다른 프로세스가 없어야 한다.  
 
<race condition>
[여러 스레드 or 프로세스가 공유 데이터 항목을 읽고 쓰는 상황 및 최종 결과]는
그들의 execution(실행)의 상대적인 타이밍에 따라 달라진다. 
 
<starvation>
스케줄러가 실행 가능한 프로세스를 무한정 간과하는 상황. 진행할 수는 있지만, 선택되진 않는다. 
 
 

2. Concurrent execution의 문제점

 
-> 동시 프로세스(또는 스레드)는 종종 데이터와 자원을 공유해야 한다. 
-> 공유 데이터에 대한 access를 제어할 수 없는 경우, 일부 프로세스에서 이 데이터의 일관성 없는 보기를 얻을 수 있다. 
-> 동시 프로세스에 의해 수행되는 작업은 execution이 끼워 넣어지는 순서에 따라 달라진다. 
 
<Problem is at the Lowest level>
대부분의 경우, 스레드는 별도의 데이터에서 작동한다. 따라서 스케줄링은 중요하지 않다. 

x = 1; //Thread A의 코드
y = 2; //Thread B의 코드

 

그러나 아래의 두 가지 경우에서, initial y = 12일 때 각각의 값은 어떻게 할당될까?

x = 1;
x = y + 1; // Thread A의 코드

y = 2; 
y = y * 2; // Thread B의 코드

x = 1; // Thread A의 코드
x = 2; // Thread B의 코드

 
<Problem is at the Lowest level - 2>
아래는 두 개의 스레드 A, B가 서로 경쟁하는 상황이다. 각각 카운터를 증가, 감소시키려 한다. 
누가 이길까? 어느 한쪽의 win이 보장되나? 두 스레드 모두 동일 속도의 CPU라면? 영원히 작동하나?

i = 0;
while (i < 10)
	i = i + 1;
printf("A wins!"); // Thread A의 코드

i = 0;
while (i > -10)
	i = i - 1;
printf("B wins!"); // Thread B의 코드

 
 

3. Concurrent Computing

 
concurrent program을 이해하기 위해선, underlying indivisible operations이 무엇인지 알아야 한다. 
-> Atomic operation : 완료될 때까지 항상 실행되거나, 전혀 실행되지 않는 operation(작업)
    기본 구성 요소, if no atomic operations -> 스레드의 동시 작동 불가.
    분할 불가, 중간에 중지 불가, 중간에 다른 사람이 상태 수정 불가.
-> 최근 CPU는 가능한 많은 Atomic operation을 수행한다. 
-> Race condition : 특정 지역에서 공유 자원이 동시에 존재하는 경우. 
    "Non-deterministic", Hard to detect, Hard to debug하다. -> 버그(heisenbug)를 숨긴다. 
 
<Principles of Concurrency>
-> interleaving과 overlapping : 동시 처리의 예시로 볼 수 있다. same problems을 가진다. 
-> Uniprocessor(단일 프로세서) : 프로세스의 상대적인 실행 속도를 예측할 수 없다. 
    즉 다른 프로세스의 작업, OS가 인터럽트를 처리하는 방식, OS의 스케줄링 정책 등에 따라 달라진다. 
 
<Difficulites of Concurrency>
-> global resources(전역 자원) 공유
-> OS가 자원 할당을 최적으로 관리하기 어렵다. 
-> 결과가 결정론적이고, reproducible하지 않기 때문에 프로그래밍 오류를 찾기 어렵다. 
 
<Critical section problem>
프로세스가 공유 데이터(or 자원)를 조작하는 코드를 실행할 때, 프로세스는 그것의 critical section에 있다. 
critical section의 실행은 상호베타적이어야 한다. 언제든지 하나의 프로세스만 실행할 수 있다. 
각 프로세스는 해당 프로세스의 critical section에 들어갈 수 있는 권한을 요청해야 한다. 
-> 하드웨어와 컴파일러에 따라 atomic일 수도, 아닐 수도 있으므로 Critical section problem이 발생한다. 
-> CS(critical section) 뒤에 종료 섹션이 올 수 있다. 나머지 코드는 RS이다. 
    프로세스가 사용 가능한 프로토콜을 설계, 프로세스의 작업이 인터리브 순서에 따라 달라지지 않게 하자. 
 
 

4. Too Much Milk Problem

 
매우 정리가 잘 되어 있는 링크 : https://rntlqvnf.github.io/lecture%20notes/os-4th-1/
 
1. 아래 표를 보자.
    우유는 한 명이 1개만 사오면 된다. 우유를 그러나 아래 상황은 우유가 2개 생긴다. 

 
2. 이때 사용되는 가장 효율적인 코드의 개념이 'lock'이다. 
-> Lock : 다른 사용자가 어떤 작업을 수행하지 못하도록 한다. 
    critical section에 들어가기 전, 공유 데이터에 access하기 전에 Lock
    공유 데이터에 access한 후에 떠날 때 Unlock
    Wait if locked -> 모든 synchronization(동기화)에는 대기가 포함된다. 
 
3. 우리는 how to make a lock을 아직 모른다. 
    아래 상황처럼 냉장고 자체에 lock을 걸면(= CPU를 못 쓰게 하여, 다른 소프트웨어들도 멈춤) angry

 
4. Condition synchronization by flags
    critical sections에는 더 강력한 synchronization operation이 필요하다. 
    다른 citical section을 만든다.
    Possible to use in simple condition synchronization, but ... 
    몰라.. 무슨 말인지 모르겠어 .. 
 
5. Solution #1
    우유를 너무 많이 사지 않도록 메모를 사용한다. 
    구입하기 전에 메모를 남긴다. (일종의 lock) -> 구입 후 메모를 제거(Unlock). 
    메모가 있다면, 구매하러 가지 않는다. 

    단점 : 메모를 남기는 사이, 상대방이 마트에 갈 수 있다. 즉 context switch 발생 가능.
 
6. Solution #1.5
    메모가 충분히 blocking되지 않았으므로, 메모를 '먼저' 배치한다. 

     단점 : note cannot be distinguished, 즉 컴퓨터는 메모 구별 불가능. 
    
7. Solution #2
    라벨이 붙은 메모를 사용하여, 누가 메모를 남겼는지 알게끔 한다. 

    단점 : 서로 우유를 샀다고 착각, 두 스레드 모두 우유 못사는 상황 발생 가능. 
 
8. Solution #3
    두 개의 메모 solution이다. 다 완벽하다. 

    단점 : 코드가 서로 대칭적이지 않다. 스레드마다 코드 차이가 별로 안 나는 것이 좋다. 
    단점2 : A가 대기하는 동안 CPU 시간을 소비한다. "busy-waiting"이 발생한다. 
 
9. Solution #4
    Lock.Acquire() : 잠금이 해제될 때까지 기다렸다가 붙잡는다. 
    Lock.Release() : 잠금 해제, 대기 중인 사용자를 깨운다. 
    -> atomic operation이다. 둘 중 한 스레드만 lock이 가능하다. 
    -> Acquire()과 Release() 사이의 코드 섹션을 Critical section이라고 한다. 

 
 

5. Semaphores(Dijkstra 1968) : General solution

 

-> 문을 둘러싼 사각형 대괄호 : 작업이 indivisible, atomic operation임을 나타낸다. 
-> first software-oriented primitive to accomplish process synchronization(최초로 프로세스 동기화 달성)
-> P operation : "to test"를 의미
    V operation : "to increment(증분)"을 의미
 

 
매우 좋은 글 : https://spartacodingclub.kr/online/special/chatgpt?origin=shared 
https://m.blog.naver.com/PostView.naver?isHttpsRedirect=true&blogId=nawoo&logNo=80179306072 
 
 

6. Example code

 
정리하자 ~~