5주차
- Chapter 12 ~ 13
- p. 363의 확인 문제 1번 풀고 인증하기
- Ch.12(12-1) 임계 구역, 상호 배제 개념을 정리하기
12 프로세스 동기화
12-1 동기화란
동기화(synchronization)의 의미
- 특정 자원에 접근할 때 한 개의 프로그세스만 접근하게 하거나, 프로세스를 올바른 순서대로 실행하게 하는 것
- 실행 순서 제어를 위한 동기화: 동시에 실행되는 프로세스를 올바른 순서대로 실행하는 것
- 상호 배제(mutual exclusion)를 위한 동기화: 공유가 불가능한 자원의 동시 사용을 피하기 위해 사용하는 알고리즘
공유 자원과 임계 구역
- 공유 자원: 공동으로 이용하는 변수, 파일, 장치 등의 자원
- 임계 구역: 동시에 실행하면 문제가 발생하는 공유 자원에 접근하는 코드 영역
- 레이스 컨디션(race condition): 잘못된 실행으로 인해 여러 프로세스가 동시 다발적으로 임계 구역의 코드를 실행하여 문제가 발생하는 경우
- 운영체제가 임계 구역 문제를 해결하는 원칙
1) 상호 배제(mutual exclusion): 한 프로세스가 임계 구역에 진입했다면 다른 프로세스는 임계 구역에 들어올 수 었다.
2) 진행(progress): 임계 구역에 어떤 프로세스도 진입하지 않았다면 임계 구역에 진입하고자 하는 프로세스는 들어갈 수 있어야 한다.
3) 유한 대기(bounded waiting): 한 프로세스가 임계 구역에 진입하고 싶다면 그 프로세스는 임계 구역에 들어오기 위해 무한정 대기해서는 안 된다.
12-2 동기화 기법
뮤텍스 락(Mutex lock: MUTual EXclusion lock)
- 동시에 접근해서는 안 되는 자원에 동시에 접근하지 않도록 만드는 도구, 상호 배제를 위한 동기화
- 구현
- 전역변수 lock: 프로세스들이 공유. 자물쇠 역할- acquire 함수: 임계 구역을 잠금
- release 함수: 임계 구역의 잠금을 해제
- 사용할 수 있는 공유 자원이 없는 경우 바쁜 대기 반복(CPU 주기 낭비)
세마포(semaphore)
🤔 예제 코드 세마포 소스 코드(python)가 있는데, import Thread가 되지 않아서 실행해 보지 못했다.
- 공유 자원이 여러개 있는 상황에서도 적용이 가능한 동기화 도구
- 동시에 실행되는 프로세스 or 스레드 간의 상호 배제를 위한 동기화와 실행 순서 제어를 위한 동기화를 할 수 있다.
- 구현
- 전역 변수 S: 임계 구역에 진입할 수 있는 프로세스 개수를 나타냄
- wait 함수: 임계 구역에 들어가도 되는지, 기다려야 할지 알려줌
- signal 함수: 임계 구역 앞에서 기다리는 프로세스에 '이제 가도 좋아' 신호
모니터
- 사용자가 사용하기에 세마포보다 좋음
- 세마포는 임계 구역 앞 뒤로 wait, signal 함수를 명시하므로 코드가 방대해 질 수 있는 단점 - 조건 변수(condition variable): 특정 조건을 바탕으로 프로세스를 실행하고 일시 중단하기 위해, 프로세스나 스레드의 실행 순서를 제어하기 위한 특별한 변수
13 교착 상태
13-1 교착 상태란
식사하는 철학자 문제
다섯 명의 철학자가 하나의 원탁에 앉아 식사를 한다. 각각의 철학자들 사이에는 포크가 하나씩 있고, 앞에는 접시가 있다. 접시 안에 든 요리는 포크를 두개 사용하여 먹어야만 하는 스파게티 이다. 그리고 각각의 철학자는 다른 철학자에게 말을 할 수 없으며, 번갈아가며 각자 식사하거나 생각하는 것만 가능하다. 따라서 식사를 하기 위해서는 왼쪽과 오른쪽의 인접한 철학자가 모두 식사를 하지 않고 생각하고 있어야만 한다. 또한 식사를 마치고 나면, 왼손과 오른손에 든 포크를 다른 철학자가 쓸 수 있도록 내려놓아야 한다. 이 때, 어떤 철학자도 굶지 않고 식사할 수 있도록 하는 방법은 무엇인가?
- 출처: 나무위키
- 일어나지 않을 사건을 기다리며 진행이 멈춰 버리는 현상
교착 상태 발생 조건
- 상호 배제(mutual exclusion)
- 점유와 대기(hold and wait)
- 비선점(nonpreemptive)
- 원형 대기(circular wait)
13-2 교착 상태 해결 방법
교착 상태 예방
- 교착 상태 발생 조건 중 하나를 충족하지 않게 하는 법
- 상호 배제를 충족하지 않게 하자
- 모든 자원을 공유 가능하게 한다 -> 현실적으로 불가능
- 점유과 대기를 없애자.
- 식사하는 철학자 > 포크를 2개 동시에 들거나, 아예 들지 못하게 함.
- 이론적으로 교착 상태 해결
- 자원의 활용률이 낮아질 우려(이유: 자원을 몰아줘야 하는 상황)
- 비선점 조건을 없애자
- 자원을 이용중인 프로세스로부터 자원(포크)을 뺏을 수 있게 됨
- 선점하여 사용할 수 있는 일부 자원에 대해 효과적
- 하지만, 모든 자원이 선점 가능하지 않다.
- 범용성이 떨어짐
- 원형 대기 조건을 없애자.
- 모든 자원에 번호를 붙이고, 오름차순으로 자원 할당
- 단점: 수많은 자원에 번호를 붙이는 일은 현실적으로 힘듦
교착 상태 회피
- 교착 상태가 발생하지 않을 정도로만 자원을 할당하는 방식
- 안전 상태(safe state): 교착 상태가 발생하지 않고 모든 프로세스가 정상적으로 자원을 할당받고 종료될 수 있는 상태
- 불안전 상태(unsafe state): 교착 상태가 발생할 수도 있는 상황
- 안전 순서열(safe sequence): 교착 상대 없이 안전하게 프로세스들에 자원을 할당할 수 있는 순서
교착 상태 검출 후 회복
- 교착 상태 발생을 인정하고 사후에 조치하는 방식
1) 선점을 통한 회복
2) 프로세스 강제 종료를 통한 회복
- 가장 단순하고 확실한 방법
- 경우1) 교착 상태인 프로세스 모두 강제 종료 -> 많은 프로세스들이 작업 내역을 잃게 될 가능성
- 경우2) 교착 상태가 없어질 때까지 한 프로세스씩 강제 종료 -> 작업 내역을 잃는 프로세스들을 최대한 줄일 수 있지만 교착 상태가 없어졌는지 여부 확인 과정에서 오버 헤드 발생
번외. 타조 알고리즘(ostrich algorithm)
까다로운 코딩 문제에 직면했을 때, 문제가 존재하지 않는 척합니다.
😂❓❓❓❓❓❓
눈을 감고 마법의 말을 외칩니다. "나는 타조이고, 이 벌레는 존재하지 않는다!"
그리고 휴식 시간 동안 커피 한 잔을 마시고 동료들과 웃으며 프로그래밍 언어에 대한 친근한 농담을 나눕니다. 휴식은 마음을 상쾌하게 하고, 새로운 에너지로 코드로 돌아가면 놀랍게도 버그가 눈앞에서 풀리기 시작합니다.
참조: The Ostrich Algorithm: Escaping Reality in the World of Programming (and Avoiding Deadlocks!)
숙제
숙제 1: p. 363의 확인 문제 1번 풀고 인증하기
4) 세마포를 이용하면 바쁜 대기 x(이건 뮤텍스 락의 문제), 해당 프로세스 상태를 대기 상태로 만든다.
추가 숙제: Ch.12(12-1) 임계 구역, 상호 배제 개념을 정리하기
- 임계 구역: 동시에 실행하면 문제가 발생하는 공유 자원에 접근하는 코드 영역
- 레이스 컨디션(race condition): 잘못된 실행으로 인해 여러 프로세스가 동시 다발적으로 임계 구역의 코드를 실행하여 문제가 발생하는 경우
- 운영체제가 임계 구역 문제를 해결하는 원칙
1) 상호 배제(mutual exclusion): 한 프로세스가 임계 구역에 진입했다면 다른 프로세스는 임계 구역에 들어올 수 었다.
2) 진행(progress): 임계 구역에 어떤 프로세스도 진입하지 않았다면 임계 구역에 진입하고자 하는 프로세스는 들어갈 수 있어야 한다.
3) 유한 대기(bounded waiting): 한 프로세스가 임계 구역에 진입하고 싶다면 그 프로세스는 임계 구역에 들어오기 위해 무한정 대기해서는 안 된다.
🦖 딱딱한 개념들 사이에 유머있는 <타조 알고리즘>이라니 ㅋㅋㅋㅋ
