동기화(synchronization)
프로세스들 사이의 수행 시기를 맞추는 것이다.
협력하여 실행되는 프로세스 간 실행 순서와 자원의 일관성을 보장하기 위해 동기화를 해 주어야 한다.
How?
1. 실행 순서 제어: 프로세스 올바른 순서로 실행
2. 상호 배제(mutual exclution)동시에 접근해서는 안 되는 자원 하나의 프로세스만 접근하도록 하기
Consumer / producer problem
생산자 프로세스와 소비자 프로세스가 제대로 동기화 되지 않으면 공유되는 데이터의 값이 손상될 수 있다.
그렇다면 공유된 자원이란?
공유 자원(shared resource): 전역 변수, 파일, 장치 등등
이 공유자원을 통해 동시에 실행하면 문제가 발생하는 자원에 접근하는 코드 영역을 임계 구역(critical section)이라고 한다.
여러 프로세스가 동시 다발적으로 임계 구역의 코드를 실행하면 race condition발생
OS가 race condition을 해결하는 방법
- 상호 배제(mutual exclusion): mutex를 통해 한 프로세스가 임계 구역에 진입했다면 다른 프로세스는 임계 구역에 들어올 수 없다.
- 진행(progress): 임계 구역에 어떤 프로세스도 진입하지 않았다면 임계 구역에 진입하고자 하는 프로세스는 들어갈 수 있어야 한다.
- 유한 대기(bounded wating): 한 프로세스가 임계 구역에 진입하고 싶다면 그 프로세스는 언젠가는 임계 구역에 들어올 수 있어야 한다(임계 구역에 들어오기 위해 무한정 대기해서는 안 된다.)
동기화 기법들
1. mutex lock
임계 구역에 진입하는 프로세스는 임계 구역에 진입한 후 mutex lock을 통해 임계 구역을 잠굴 수 있다.
이를 통해 다른 프로세스는 해당 프로세스의 임계 구역 사용이 끝날 때 까지 임계 구역에 진입 할 수 없다.
간단하게 구현하기
자물쇠 역할(공유 전역 변수 lock)
임계 구역 잠구기(acquire 함수)
임계 구역에 진입할 때 호출되며 변수 lock이 true라면(임계 구역이 사용 중이라면)false가 될 때까지 임계 구역을 반복적으로 확인(이것을 busy wating이라고 부른다.){하고 임계 구역이 열려 있다면 변수를 true로 변경하는 함수이다.
임계 구역의 잠금을 해제하는 역할(release 함수)
임계 구역에서의 작업이 끝나고 호출하는 함수(lock을 false로 바꿈)
2. Semaphore
공유 자원이 여러 개 있는 상황에서 mutex lock은 적용이 힘들기 때문에
이를 보완하기 위해 도입되었다.(binary semaphore, counting semaphore 등등)
wait(){
while( S <= 0) //사용 가능한 자원 개수 루프를 통해 확인
;
S--; //사용 가능한 자원이 생길 경우 루프를 탈출한 뒤 자원 갯수 하나를 사용하면서 임계 구역 진입
}
signal(){
S++ //임계 구역에서의 작업이 끝난 뒤 S를 1 증가
}계속 자원 개수를 조회할 시 CPU 낭비 이슈 -> 자리가 없을 경우 대기 큐에 넣고 진행 중 작업이 끝나면 signal 함수가 이 대기 큐에서 불러오는 방식
wait(){
S--;
if( S < 0){
add this process to queue;
sleep();
}
}
signal(){
S++;
if (S <= 0){
remove a process p from Queue;
wakeup(p);
}
}3. 모니터
공유 자원과 공유 자원에 접근하기 위한 인터페이스를 묶어 관리 -> 프로세스는 반드시 인터페이스를 통해서만 공유 자원에 접근
모니터에 진입하는 위한 큐와
모니터에 이미 진입한 프로세스의 실행 조건이 만족될 때까지 잠시 실행이 중단되어 기다리기 위해 만들어진 큐
condition variable(조건 변수): 모니터가 semaphore처럼 실행 순서 제어를 위한 동기화를 제공할 때 이 조건 변수를 사용한다.
//유튜브 영상 참조
교착 상태(deadlock)
식사하는 철학자 문제(dining philosophers problem)
원탁 위 철학자들이 양쪽의 포크를 사용해야 식사를 할 수 있을 때 모두 동시에 식사를 할 경우 포크가 부족하여 식사를 진행 할 수 없다.
이렇게 일어나지 않을 사건을 기다리며 진행이 멈춰 버리는 현상을 deadlock:교착상태 라고 한다.
deadlock 발생 조건:
1. 상호 배제(mutex)
-> 식사하는 철학자 문제처럼 mutex상태에서 발생
2. 점유와 대기(hold and wait)
-> 자원을 할당받은 상태에서 다른 자원 할당받기를 기다리는 상태
3. 비선점(non-preemptive)
-> 강제로 빼앗지 못해서 교착 상태 발생(철학자들 중 한명이 뺏어서 순서 만들면 해결됬을 것)
4. 원형 대기(circular wait)
-> 꼬리를 무는 형태로 자원 대기가 무한반복되는 형태
Deadlock을 해결하는 방법:
1. deadlock 예방
앞선 발생 조건 4가지의 조건을 피하면서 deadlock을 예방할 수는 있지만
그럴경우 여러 부작용이 따르게 된다.
2. deadlock 회피
deadlock이 발생하지 않을 정도로만 자원을 할당하는 방식
safe sequence라는 deadlock없이 안전하게 프로세스들이 자원을 할당할 수 있는 순서에 따라 배분하게 되면 안전하다.
그러나 이러한 safe sequence가 없는 경우 unsafe state에 빠질 수 있다.
3. deadlock 검출 후 회복
3.1 선점을 통한 회복은 교착 상태가 해결될 때까지 한 프로세스씩 자원을 몰아주는 방식이다.
교착상태가 해결될 때까지 다른 프로세스로부터 자원을 강제로 빼앗고 한 프로세스에 할당하는 방식.
3.2 프로세스 강제 종료를 통한 회복 잠재적 문제를 무시하고 대처하는 방식이기 때문에 위기를 느낄 시 땅에 머리를 박는 타조와 닮아 ostrich algorithm이라고도 부른다.
숙제
1. p. 363의 확인 문제 1번 풀고 인증하기
1. 참
2. 참
3. 참
4. 거짓(PCB대기 큐를 활용함으로써 바쁜 대기를 피할 수 있다.)
정답 4
2. Ch.12(12-1) 임계 구역, 상호 배제 개념을 정리하기
임계 구역(critical section)이란 동시에 실행하면 문제가 발생하는 자원에 접근하는 코드 영역을 지칭한다.
//해당 자원을 shared resource, 공유 자원이라고 부른다.
상호 배제(mutual exclusion)
공유가 불가능한 자원의 동시 사용을 피하기 위해 사용하는 알고리즘이다.
mutex라는 약자로도 부르며 mutex lock등 동기화 기법에 사용된다.
느낀 점 및 차주 목표
운영체제 파트는 대학교 강의를 통해 한번 배웠던 터라 생소했던 부분(동기화 파트의 모니터 기법)위주로 다른 자료도 참조해서 복습하는 느낌으로 가볍게 볼 수 있었다.
오히려 오는 학기에 수강할 컴퓨터구조가 계속 신경쓰여서 1~3주차 컴퓨터구조를 다시 복습하는 중이다. 개강까지 탄탄하게 개념 적립 파이팅!
