[5주차] - 병행 제어

---

1. 알고리즘 측정 방법

• Queuing Models(큐잉 모델)
  • Queue에 도착한 프로세스들을 CPU가 처리하고 처리율을 체크
  • 도착률과 처리율을 통해서 Performance Index를 계산
  • 현재는 이론적으로만 사용한다. 실제로는 직접 돌려보면서 성능을 측정한다.
• Implementation(구현), Measurement(측정)
  • 실제로 알고리즘을 구현하여 실제 작업에 적용해 성능을 측정함
  • 이상적이지만 실제 시스템에 적용하기는 힘듬
• Simulation(모의 실험)
  • 알고리즘을 가상 프로그램으로 돌려 trace를 input해 성능 측정
    • trace : 실제 프로그램을 실행하는 데이터

---

2. Multiple Processor Scheduling

• Homogeneous Processor
  • 프로세스를 한줄서기 해놓고 CPU가 뽑아서 쓰는 형식
  • 특정 CPU에서 실행되어야 하는 프로세스가 있는 경우 문제가 발생
• Load Balancing
  • 요청을 적절히 나누어 CPU들이 밸런스있게 일하게 해야함
• Symmetric Multiprocessing (SMP)
  • CPU들이 스스로 스케줄링을 진행
• Asymmetric multiprocessing
  • 하나의 CPU가 시스템 데이터의 접근과 공유를 책임지고 나머지 CPU는 거기에 따름

---

3. Process Synchronization

• 프로세스 간 통신
  • 프로세스 내부 데이터 통신
    • 하나의 프로세스 내에 2개 이상의 스레드가 존재하는 경우의 통신
    • 프로세스 내부의 스레드는 전역 변수나 파일을 이용하여 데이터를 주고받음
  • 프로세스 간 데이터 통신
    • 같은 컴퓨터에 있는 여러 프로세스끼리 통신하는 경우
    • 공용 파일 또는 운영체제가 제공하는 파이프를 사용하여 통신
  • 네트워크를 이용한 데이터 통신
    • 여러 컴퓨터가 네트워크로 연결되어 있을 때도 통신이 가능
    • 이 경우 프로세스는 소켓을 이용하여 데이터를 주고 받음

---

4. Race Condition

• 여러 프로세스가 하나의 데이터를 공유하고, 연산을 하려고 할 때 경쟁 상태가 생길 수 있음
• 하나의 데이터에 대한 여러 연산 요청이 있을 때는 이를 조절해줘야 한다

---

5. Critical Section

• 공유 자원 접근 순서에 따라 실행 결과가 달라지는 프로그램의 영역을 임계 구역이라 함
• Critical Section 문제를 해결 조건 3가지
  • 상호 배제(Mutual Exclusion)
    • 한 프로세스가 임계구역에 들어가면 다른 프로세스는 임계구역에 들어갈 수 없다
    • 이것이 지켜지지 않으면 임계구역을 설정한 의미가 없다
    • 임계구역 내에는 한 번에 하나의 프로세스만 있어야 한다
  • 한정 대기(bounded waiting)
    • 어떤 프로세스도 무한 대기를 하면 안된다
    • 즉, 특정 프로세스가 임계구역에 진입하지 못하면 안된다
  • 진행의 융통성(Progress flexibility)
    • 한 프로세스가 다른 프로세스의 진행을 방해해서는 안된다는 것을 의미

---

6. Critical Section을 해결하는 3가지 알고리즘

• Synchornization variable
  • 변수를 통해 임계 영역에 들어갈 프로세스를 정해줌

do {
    while (turn != 0)
    critical section
    turn = 1;
    remainder section
} while (1);

• Flag
  • Mutual Exclusion 만족, Progress 만족X
  • 동시에 수행하려 하면 무한대기 가능성 있음

do {
    flag[i] = true;
    while (flag[j]);
    critical section
    flag[i] = false;
    remainder section
} while(1);

• Synchornization variable, Flag 동시 사용(피터슨 알고리즘)
  • 모든 조건 만족
  • Busy waiting

do {
    flag[i]= true;
    turm = j;
    while(flag[j] && turn == j);
    critical section
    flag[i] = false;
    remainder section
} while(1);

---

7. Semaphore

• 세마포어는 임계구역에 진입하기 전에 스위치를 사용 중으로 놓고 임계구역에 들어감
• 이후에 도착하는 프로세스는 앞의 프로세스가 작업을 마칠 때 까지 기다림
• 프로세스가 작업을 마치면 세마포어는 다음 프로세스에 임계구역을 사용하라는 동기화 신호를 보냄

semaphore(n);

P();
(임계구역)
V();

• semaphore(n) : 전역변수 RS를 n으로 초기화함, RS에는 현재 사용 가능한 자원의 수가 저장
• P() : 잠금을 수행하는 코드로, RS가 0보다 크면 1만큼 감소시키고 임계구역에 진입, 만약 0보다 작으면 0보다 커질때까지 기다린다
• V() : 잠금 해제와 동기화를 같이 수행하는 코드로, RS 값을 1 증가시키고 세마포어에서 기다리는 프로세스에게 임계구역에 진입해도 좋다는 wake_up 신호를 보낸다

본 포스팅은 반효경 교수님의 2017 운영체제 강의를 바탕으로 제작되었습니다.