[혼공학습단 11기 혼공컴운💿] 컴퓨터구조+운영체제 week5

✍️기본 미션

p. 363의 확인 문제 1번 풀고 인증하기

 

 

✍️선택미션

Ch.12(12-1) 임계 구역, 상호 배제 개념을 정리하기

아래 내용 정리를 확인해 주세요!

---

🗒️내용 정리

Chap12. 프로세스 동기화

12.1 동기화란?

1) 동기화 (synchronization)

- 프로세스 동기화 : 프로세스들 사이의 수행 시기를 맞추는 것
- 협력하여 실행되는 프로세스들의 실행 순서와 자원의 일관성을 보장하기 위해 필수적이다.

• 실행 순서 제어 : 프로세스를 올바른 순서대로 실행하기
• 상호 배제(mutual exlcusion) : 동시에 접근해서는 안 되는 자원에 하나의 프로세스만 접근하게 하기
  • 공유가 불가능한 자원의 동시 사용을 피하기 위해 사용하는 알고리즘
  • 생산자와 소비자 문제

 

2) 생산자와 소비자 문제

- 물건을 계속해서 생산하는 프로세스인 생산자, 물건을 계속해서 소비하는 프로세스인 소비자
- 생산자 프로세스와 소비자 프로세스가 제대로 동기화되지 않을 경우 생산자와 소비자를 동시에 실행 시 총합이 예상과 달라지거나 실행 중 오류가 발생하기도 한다.
 

3) 공유 자원과 임계 구역

- 공유 자원 (shared resorce) : 동시에 실행되는 프로세스들이 사용하는 공동의 자원
- 임계 구역 (critical section) : 동시에 실행하면 문제가 발생하는 자원에 접근하는 코드 영역
- 임계 구역의 진입

• 두 개 이상의 프로세스가 임계구역에 진입하고자 하면 하나를 제외하고 전부 대기해야 한다.
• 레이스 컨디션 (race condition) : 잘못된 실행으로 인해 여러 프로세스가 동시다발적으로 임계 구역의 코드를 실행하여 문제가 발생한다.
• 레이스 컨디션이 발생하는 근본적인 원인 : 여러 줄의 저급언어로 변한된 고급 언어를 실행하는 과정에서 문맥 교환이 발생할 수 있다.

- 상호 배제를 위한 동기화를 위한 세 가지 원칙

• 상호 배제 (mutual exclusion) : 한 프로세스가 임계구역에 진입했다면 다른 프로세스는 임계구역에 들어올 수 없다.
• 진행 (progress) : 임계 구역에 어느 프로세스도 진입하지 않았다면 임계 구역에 진입하고자 하는 프로세스는 들어갈 수 있어야 한다.
• 유한 대기 (bounded waiting) : 임계 구역에 들어오기 위해 무한정 대기해서는 안 된다.

 
 

12.2 동기화 기법

1) 뮤텍스 락 (Mutex lock ; MUTual EXclusion lok)

- 동시에 접근해서는 안 되는 자원에 동시에 접근하지 않도록 만드는 (상호 배제를 위한 동기화) 도구
- 하나의 공유 자원에 접근하는 프로세스 상정
- 뮤텍스 락의 구현 : acquire 함수와 release 함수를 임계 구역 전후로 호출해 하나의 프로세스만 임계 구역에 진입 가능

• 자물쇠 역할 : 프로세스들이 공유하는 전역 변수 lock
  • lock == true : 임계 구역이 잠겨 있다.
  • lock == false : 임계 구역이 열려 있다.
• 임계 구역을 잠그는 역할 : acquire 함수
  • 프로세스가 임계 구역에 진입하기 전에 호출
  • 임계 구역이 잠겨있다면 임계 구역이 열릴 때까지 임계 구역을 반복적으로 확인하고 임계 구역이 열려 있다면 임계 구역을 잠근다. 
  • 바쁜 대기(busy wait) : 임계 구역을 반복적으로 확인
• 임계 구역의 잠금을 해제하는 역할 : release 함수
  • 임계 구역의 작업이 끝나면 호출
  • 임계 구역을 열어주는 함수

acquire() {
    while (lock == true); // 임계 구역이 잠겨있는지 계속 확인
    lock = true;
}

release() {
    lock = false; // 임계 구역 작업이 끝났으니 잠금 해제
}

 

2) 세마포 (semaphore)

- 뮤텍스 락과 비슷하지만 좀 더 일반화된 동기화 도구 : 공유 자원이 여러 개 있을 때도 적용 가능하다.
- 공유 자원이 여러 개 있을 경우 여러 개의 프로세스가 각각의 공유 자원에 접근해야 한다.
- 실행 순서 제어를 위한 동기화 제공
- 세마포의 구현 : wait 함수와 signal함수를 임계 구역 전후로 호출

• 전역변수 S : 임계 구역에 진입할 수 있는 프로세스의 개수 (사용 가능한 공유 자원의 개수)
• wait 함수 : 임계 구역에 들어갈 수 있는지, 기다려야 하는지를 알려준다.
• signal 함수 : 임계 구역 앞에서 기다리는 프로세스에게 진입 가능함을 알려준다.

wait() {
    while (S <= 0); // 임계 구역에 진입할 수 있는 프로세스가 없을 때
    S--; // 임게구역에 진입할 수 있는 프로세스가 1개 이상이므로 S를 1 감소시키고 임계 구역 진입
}

signal() {
    S++; // 임계 구역의 작업이 끝나면 S를 1 증가시킴
}

- 더 나은 구현

• 이전 구현의 문제 : 바쁜 대기 → CPU 주기 낭비
• 해결 : wait 함수는 만일 사용할 수 있는 자원이 없을 경우 해당 프로세스 상태를 대기 상태로 만들고, 그 프로세스의 PCB를 세마포를 위한 대기 큐에 삽입

wait() {
    S--;
    if (S < 0) {
    	add this process to Queue; // 해당 프로세스 PCB를 대기 큐에 삽입
    	sleep(); // 대기상태에 접어든다.
    }
}

signal() {
    S++;
    if (S <= 0) {
    	remove a process p from Queue; // 대기 큐에 있는 프로세스 p 제거
        wakeup(p); // 프로세스 p를 대기 상태에서 준비 상태로 만듦.
    }
}

 

3) 모니터

- 세마포에 비해 사용자가 사용하기 편리하다.
- 공유 자원과 공유 자원에 접근하기 위한 인터페이스를 묶어 관리하고, 프로세스는 인터페이스를 통해서만 공유 자원에 접근 가능
- 실행 순서 제어를 위한 동기화 제공

• 조건 변수(condition variable) 사용
• wait과 signal 연산 수행 가능
• wait : 호출한 프로세스의 상태를 대기 상태로 전환하고 일시적으로 조건 변수에 대한 대기 큐에 삽입
• signal : wait를 호출해 큐에 삽입된 프로세스의 실행 재개

 
 

Chap13. 교착 상태

13.1 교착 상태란?

1) 식사하는 철학자 문제 (dining philosophers problem)

- 철학자들이 식사하는 순서

1. 계속 생각하다가 왼쪽 포크가 사용 가능하면 집어든다.
2. 계속 생각하다가 오른쪽 포크가 사용 가능하면 집어든다.
3. 왼쪽과 오른쪽 포크를 모드 집어들면 정해진 시간동안 식사를 한다.
4. 식사 시간이 끝나면 오른쪽 포크를 내려놓는다.
5. 오른쪽 포크를 내려놓은 뒤 왼쪽 포크를 내려놓는다.
6. 1번부터 반복

- 모든 철학자가 동시에 포크를 집어들면 어떤 철학자도 식사할 수 없고 영원히 생각하기만 하는 상황이 발생할 수 있다.
 

2) 교착 상태 (deadlock)

- 일어나지 않을 사건을 기다리며 진행이 멈춰버리는 현상
- 교착 상태를 해결하기 위해 교착 상태가 발생했을 때의 상황을 정확히 표현하고 교착 상태가 발생하는 근본적인 이유에 대해 알아야 한다.
 

3) 자원 할당 그래프 (resource-allocation graph)

- 프로세스는 원으로, 자원의 종류는 사각형으로 그린다.
- 사용할 수 있는 자원의 개수는 자원 사각형 내 점으로 표현한다.
- 프로세스가 어떤 자원을 할당받아 사용 중이라면 자원에서 프로세스를 향해 화살표를 표시한다. (자원 반납 시 화살표 삭제)
- 프로세스가 어떤 자원을 기다린다면 프로세스에서 자원으로 화살표를 표시한다. 

예시

- 교착 상태가 발생한 상황은 자원 할당 그래프가 원의 형태를 띤다.
 

4) 교착 상태 발생 조건

- 상호 배제, 점유와 대기, 비선점, 원형 대기의 조건을 모두 충족하면 교착 상태가 발생할 수 있다.
- 상호 배제 (mutual exclusion) : 한 프로세스가 사용하는 자원을 다른 프로세스가 사용 불가
- 점유와 대기 (hold and wait) : 자원을 할당받은 상태에서 다른 자원을 할당받기를 기다리는 상태
- 비선점 (nonpreemptive) : 어떤 프로세스이든 다른 프로세스의 자원을 강제로 빼앗지 못한다.
- 원형 대기 (circular wait) : 프로세스들이 원의 형태로 자원을 대기한다.
 
 

13.2 교착 상태 해결 방법

1) 교착 상태 예방

: 교착 상태 발생 필요 조건 중 하나를 충족하지 못하게 한다.
- 자원의 상호 배제 제거

• 모든 자원을 공유 가능하게 한다.
• 현실적으로 무리가 있다.

- 점유와 대기 제거

• 운영체제는 특정 프로세스에게 자원을 모두 할당하거나 아예 할당하지 않는다.
• 자원의 활용률이 매우 낮아진다. 
• 많은 자원을 사용하는 프로세스에 대해 기아 현상이 발생할 수 있다.

- 비선점 제거

• 자원을 이용 중인 프로세스로부터 해당 자원을 빼앗을 수 있다.
• 모든 자원이 선점적인 것은 아니므로 범용성이 떨어진다. 

- 원형 대기 제거

• 모든 자원에 번호를 붙이고 순서대로 자원 할당
• 모든 컴퓨터 내에 존재하는 자원에 번호를 할당하는 것이 간단하지 않다.
• 번호에 따라 특정 자원의 활용률이 떨어질 수 있다. 

 

2) 교착 상태 회피

- 시스템 상태의 종류

• 안전 상태 (safe state)
  • 교착 상태가 발생하지 않고 모든 프로세스가 정상적으로 자원을 할당받고 종료될 수 있는 상태
  • 안전 순서열 (safe sequence) : 교착 상태 없이 안전하게 프로세스들에 자원을 할당할 수 있는 순서
  • 안전 순서열이 있는 상태
  • 안전 순서열대로 프로세스들에 자원을 배분하여 교착 상태가 발생하지 않는 상태
• 불안전 상태 (unsafe state)
  • 교착 상태가 발생할 수 있는 상황
  • 안전 순서열이 없는 상황

- 교착 상태 회피 : 시스템이 안전 상태에서 안전 상태로 움직이는 경우에만 자원 할당
 

3) 교착 상태 검출 및 회복

- 교착 상태의 발생을 인정하고 사후에 조치
- 운영체제는 프로세스들이 자원을 요구할 때마다 모두 할당하고 교착 상태 발생 여부를 주기적으로 검사한다.
- 선점을 통한 회복 : 교착 상태가 해결될 때까지 한 프로세스씩 자원을 몰아준다.
- 프로세스 강제 종료를 통한 회복

• 교착 상태에 놓인 프로세스들을 모두 강제 종료
  • 교착 상태를 해결하는 가장 확실한 방법
  • 많은 프로세스들이 작업 내역을 잃을 수 있다.
• 교착 상태에 놓인 프로세스들을 하나씩 종료
  • 작업내역을 잃는 프로세스를 최대한 줄일 수 있다.
  • 교착 상태가 없어졌는지 여부를 확인하는 과정에서 오버헤드를 야기한다.

- 타조 알고리즘 (ostrich algorithm) : 교착 상태 무시
 
 

---

🤔느낀 점

새롭게 배운 내용이 많았던 한 주였습니다. 이제 다음 주면 끝나네요. 끝까지 힘내보겠습니다!