프로세스 뿐만 아니라 스레드도 스케쥴링, 동기화 대상이다. 모든 흐름을 가진 것은 동기화 대상
프로세스 동기화
자원은 한정됨 : 운영체제는 적재적소에 효율적이고 공정하게 자원을 배분 - 동시다발적으로 실행되는 프로세스(& 스레드) : 실행 순서와 자원의 일관성을 고려하여 보장
동기화의 의미 - 실행 순서 제어: 프로세스를 올바른 순서로 실행하기 - 상호 배제: 동시에 접근해서는 안되는 자원에 하나만 접근하기
실행 순서 제어를 위한 동기화 아래 두개의 프로세스가 동시다발적으로 실행이 되었다면? 1. Book.txt가 없다면 파일을 만들고 값을 쓰고 저장하는 프로세스 2. Book.txt를 읽어들이는 프로세스 : 둘은 실행순서가 중요하다 1->2가 되어야함
상호 배제를 위한 동기화 동시에 실행되는 프로세스 1. 2만원 입금 프로세스 : a. 잔액을 읽어들인다 b. 잔액에 2만원을 더한다 c. 더한 값을 저장한다 2. 5만원 입금 프로세스 : a. 잔액을 읽어들인다 b. 잔액에 5만원을 더한다 c. 더한 값을 저장한다
: 동기화를 고려하지 않으면 (여기서는 잔액이 자원)
: 올바른 예시: 잔액에 접근하기 전 기다려야 한다! (여기서는 잔액이 자원)
공유 자원과 임계 구역 - 공유 자원: 공동의 자원 (e.g. 파일, 전역 변수, 입출력장치, …) - 동시에 접근해서는 안 되는 자원 , 일관성을 지켜야하는 자원 - 임계 구역(critical section) : 동시에 접근하면 문제가 발생할 수 있는 공유 자원에 접근하는 코드 - 레이스 컨디션(race condition) : 임계 구역을 동시에 실행하여 자원의 일관성이 깨지는 현상
생산자와 소비자 문제 (producer-consumer problem) : 프로세스가 동기화 되지 않았을 때 발생되는 문제 - 동기화가 이루어지지 않았을 경우 발생할 수 있는 문제를 보여주는 고전적 문제 - producer: 생산을 하는 프로세스(혹은 스레드) : queue에 데이터 넣기, 기존없었던 자원생산, 변수값 증가 - consumer: 소비를 하는 프로세스(혹은 스레드) : queue에 있는 값 읽기, 없었던 자원읽어드리기, 소비, 변수값 감소
뮤텍스와 세마포어
동기화를 할 수 있는 도구들, 동기화 여러 기법들 중 가장 고전적인 방법
동기화 해결의 세 가지 원칙 - 상호 배제 : 한 프로세스가 임계 구역에 진입했다면 다른 프로세스는 대기해야 함 -진행 : 어떤 프로세스도 임계 구역에 진입하지 않았다면 진입이 가능해야 함 -유한 대기 : 한 프로세스가 임계 구역 진입을 위해 대기하고 있다면 언젠간 진입이 가능해야 함
- 뮤텍스 락의 표현
- 자물쇠 역할: 프로세스들이 공유하는 전역변수 lock - True 잠김, False 안잠김 - 자물쇠 잠그기: acquire 함수 - lock 이 true인지 false인지 계속 반복확인(while 루프, 잠겨있는지 열려있는지 확인), : 바쁜 대기(busy waiting) : while루프를 통해 계속 확인을 하는 작업 - 다른 프로세스에서 lock이 false로 바꾸면(열림), lock=true실행하여 lock을 true로 바꾸고 임계구역으로 진입 - 임계구역에 아무나 들어가면 안 되기에 실행함 - 자물쇠 열기: release 함수 - 작업을 끝내고 나올 때 lock을 false로 바꿈
- 일반적인 상황에서도 사용 할 수 있는 동기화 도구 - 뮤텍스 락은 기본적으로 공유 자원이 하나일 경우 상정한 동기화 도구 : lock이 하나의 경우 - 세마포는 공유 자원이 여러 개 있을 경우도 동기화 (실행 순서 제어, 상호 배제 동기화) 가능
- 어원 : 철도 신호기 - 가도 된다, 안된다를 말해줌 - 가라는 신호를 받으면 (임계 구역에) 진입해도 좋다 - 멈추라는 신호를 받으면 (임계 구역에) 진입해서는 안된다
- 세마포(semaphore) 의 표현 1. 변수 S: 임계 구역에 진입할 수 있는 프로세스의 개수(사용 가능한 공유 자원의 개수) 2. wait 함수: 임계구역에 들어가도 좋은지, 기다려야 할지를 알려주는 함수 - while 함수로 무한루프를 함. : 무한이 진입이 가능한지 확인함 3. signal 함수: 임계구역 앞에서 기다리는 프로세스에게 ‘이제 가도 좋다’고 신호를 주는 함수 - s를 1씩 증가/감소 시키는 함수임
- 프로세스 상태 전이 활용 - busy wait는 너무 cpu자원을 낭비함. 이를 방지하는 방법 - 신호를 기다리는 무한 반복 대신 대기상태로 접어들게 함.
- 실행 순서를 위한 동기화 진행방법 - 먼저 실행할 프로세스 뒤에 signal - 나중에 실행할 프로세스 앞에 wait
- signal이 wait을 깨워줌
조건변수와 모니터
- 동기화를 위한 다른 방안 중 하나
사용 이유 - 세마포 누락 - wait랑 signal 순서를 헷갈림 - wait랑 signal이 중복해서 사용
사용이 간편한 동기화 도구, 모니터 - 공유 자원에 접근하기 위한 인터페이스를 각각 따로 둠 - 정해진 인터페이스를 통해서만 들어와야함 : 다 지정되어있음 -인터페이스를 통해서만 접근(상호 배제)
프로세스는 실행을 위해 자원이 필요하다 : 서로의 자원을 무한히 기다리기만 한다면 -> 교착상태 발생
식사하는 철학자 문제( N명의 철학자, 두 개의 포크로 먹을 수 있는 음식, 원형 테이블) - 계속 생각을 하다가, 왼쪽 포크가 사용 가능하면 집어든다. -> 계속 생각을 하다가, 오른쪽 포크가 사용 가능하면 집어든다. -> 왼쪽과 오른쪽 포크를 모두 집어들면, 정해진 시간동안 식사를 한다. -> 식사 시간이 끝나면, 오른쪽 포크를 내려놓는다. -> 오른쪽 포크를 내려놓은 뒤, 왼쪽 포크를 내려놓는다. -> 1번부터 다시 반복한다. - 모든 철학자들이 동시에 포크를 집어드는 순간 누구도 식사를 할 수 없음 - 철학자 == 프로세스(혹은 스레드) / 포크 == 실행을 위해 필요한 자원 으로 생각하면 이게 교착상태이다.
교착 상태 (deadlock) - 일어나지 않을 사건(필요한 자원의 할당)을 기다리며 무한히 대기하는 현상
- 교착 상태 발생 조건 (***시험에 잘 나옴***) - 상호 배제: 동시에 자원 사용이 불가능한 경우 - 점유와 대기: 자원을 할당받은 채 다른 자원의 할당을 기다리는 경우 - 비선점: 강제로 자원을 빼앗을 수 없는 경우 - 원형 대기: 자원을 원형으로 대기할 경우
교착상태 해결방법 - 교착 상태 예방 교착 상태 발생 조건 네 가지(상호 배제, 점유와 대기, 비선점, 원형 대기)중 하나를 없애는 것 교착 상태가 발생 배경 원천 차단 교착 상태가 발생하지 않음을 보장할 수 있지만, 여러 부작용이 따르는 방식 - 상호 배제 조건 없애기 - 자원을 공유 가능하도록 변경 - 모든 자원에 대해 적용할 수 없음 - 점유와 대기 조건 없애기 - 특정 프로세스에 자원을 모두 할당, 아예 할당하지 않기 -자원의 활용률 저하 - 비선점 조건 없애기 - 자원을 뺏을 수 있게 해버리기. : 선점스케줄 - 선점하여 사용 가능한 자원에 대해서는 효과적 (e.g. CPU) -모든 자원에 대해 적용 가능한 것은 아님 (e.g. 프린터기) - 원형 대기 조건 없애기 - 자원에 번호 매기기 : 자원에 번호를 매길 수 없음, 실행에 얼마나 사용하는지 알 수 없음, 자원의 활용이 떨어짐 - 오름차순으로 자원 할당
- 교착 상태 회피 - 교착 상태가 발생하는 이유를 자원의 무분별한 할당으로 간주 ○ 포크가 무한한 상황에서 한 두개의 자원만을 요구했다면? (교착상태가 절대 발생하지 않음) ○ 포크가 두 개 있는 상황에서 여러 개의 자원을 요구했다면? (이때 교착상태가 발생됨)
- 프로세스가 요구할 수 있는 최대자원의 양, 현재 사용중인 자원의 양, 남은 자원의 양을 고려함 - 가장 적게 추가적인 자원이 필요한 프로세스 순으로 요구를 들어줌 - 작업이 끝나고도 남은 자원이, 다른 프로세스의 요구량을 들어주지 않으면 교착상태가 발생할 수 있음
- 이를 판단하는 알고리즘 == 은행원 알고리즘(banker’s algorithm)
- 교착 상태 검출 후 회복 ( 교착 상태가 발생하면 그때 회복하는 방식) -선점을 통한 회복 - 프로세스 강제 종료를 통한 회복
