* 이 글은 학부생 시절 개인 Notion에 작성했던 강의 필기 노트를 Velog에 옮긴 글입니다.
📗: 운영체제 [ 제10판 ] | Abraham Silberschatz, Peter Baer Galvin, Greg Gagne 저/박민규 역 | 퍼스트북
6장 동기화 도구들
배경
공유 자료를 병행 접근하면 자료의 불일치를 초래한다. 자료의 일관성을 유지해야함
경쟁 상황
: 여러 개의 프로세스가 동일한 자료를 접근하여 조작하고, 그 실행 결과가 접근이 발생한 특정 순서에 의존하는 상황
→ 한 순간에 하나의 프로세스만이 공유 자료를 조작하도록 프로세스를 동기화 해야함
Ex) 생산자-소비자 문제
count++과 count— 문장을 병행 실행하면 기계어 수준 명령들이 다음과 같이 임의의 순서로 뒤섞여 순차적으로 실행한다.
임계구역 문제
- 각 프로세스는 임계구역을 포함한다
- 이 구역에서 다른 프로세스와 공유하는 변수의 변경, 테이블의 갱신, 파일 쓰기 등의 작업을 수행함
- 한 프로세스가 자신의 임계구역에서 수행하는 동안에는 다른 프로세스들은 그들의 임계구역에 들어갈 수 없음
- 각 프로세스는 자신의 임계구역에 진입하려면 진입 허가 요청을 해야 함
do{ //진입 구역(진입 허가 요청 구현) //임계 구역 //퇴출 구역 //나머지 구역 }while(true);
임계 구역 문제 발생 유형
-
커널에서 인터럽트 루틴 처리
-
프로세스가 커널에서 선점
-
다중 처리기
임계 구역 문제에 대한 해결안은 다음의 세 가지 요구 조건을 충족해야 한다.
- 상호 배제(mutual exclusion): 프로세스 p 가 자기의 임계 구역에서 실행된다면, 다른 프로세스들은 그들의 임계 구역에서 실행될 수 없다.
- 진행(progress): 임계구역에서 실행중인 프로세스가 없고, 임계 구역으로 진입하려는 프로세스들이 있다면 이들 프로세스들 중 임계 구역으로 진입을 선택하고, 이 선택은 무한정 연기될 수 없다.
- 한정된 대기(bounded waiting): 프로세스가 임계 구역에 진입 요청을 한 후부터 그 요청이 허용될 때까지 다른 프로세스들이 그들 자신의 임계 구역에 진입이 허용되는 횟수에는 제한이 있어야 한다.
운영체제의 임계 구역 관리
- 선점형 커널
- 커널 모드에서 실행되고 있는 프로세스가 선점되는 것을 허용
- 비선점형 커널
- 커널 모드 프로세스가 커널 모드를 종료 또는 봉쇄되거나, 자발적으로 CPU의 제어를 양보할 때까지 선점되지 않고 계속 실행
- 커널 모드에서 경쟁 상황이 발생하지 않음(→인터럽이 없기 때문)
선점형 커널은 실시간 프로세스가 현재 커널에서 실행중인 프로세스를 선점할 수 있기 때문에 실시간 프로그래밍에 적합하다. 반대로, SMP(멀티코어)에서는 서로 다른 CPU에서 두 프로세스가 동시에 커널 모드에 있을 수 있기 때문에 선점형 커널 설계가 어렵다.
피터슨의 해결안
load와 store 명령이 원자적이라고 가정한다. 즉 인터럽트 발생 X (현대 컴퓨터 구조에서는 보장 X)
두 프로세스가 공유하는 자료
-
변수 turn
임계구역으로 진입할 순번을 나타냄. trun==i면 프로세스 P(i)가 임계구역에서 실행
-
flag 배열
프로세스가 임계 구역으로 진입할 준비가 되었다는 것을 나타냄. flag[i]가 ture이면 P(i)가 임계 구역으로 진입할 준비가 되었다는 뜻
/*프로세스 i*/
do{
flag[i]=true;
turn=j;
while(flag[j]&&turn==j); /*do nothing*/
/* 임계 구역 */
flag[i]=false;
/* 나머지 구역 */
}while(true);
/*프로세스 j*/
do{
flag[j]=true;
turn=i;
while(flag[i]&&turn==i); /*do nothing*/
/* 임계 구역 */
flag[j]=false;
/* 나머지 구역 */
}while(true);상호 배제 준수, 진행 요구 조건 만족, 대기 시간이 한 없이 길어지지 않음
동기화 하드웨어 지원
많은 시스템에서 임계 구역 코드를 지원하는 하드웨어를 제공한다.
대부분 락킹(locking)에 기반하여 임계 구역 보호
락(Lock)을 사용한 임계영역 문제 해결
프로세스는 임계영역 진입 전 반드시 락(lock)을 획득, 나올때는 락을 방출
do{
//락 획득
//임계영역
//락 방출
//나머지 구역
}while(TRUE);단일 처리기 환경에서는 공유 변수가 변경되는 동안 인터럽트 발생을 허용하지 않음으로써 해결
→ 현재 실행되는 코드가 선점없이 순서적으로 실행됨
현대에는 특별한 원자적 하드웨어 명령어들을 제공
1. test_and_set 명령어
: 한 워드의 내용을 검사하고 변경하는 명령어
boolean test_and_set(boolean *target){
boolean rv=*target; // test: 인수의 원래 값 저장&리턴. false면 진입
*target=true; // set: 인수에 true 값을 지정. 다른 프로세스 진입 방지
return rv;
}✅ test_and_set 명령어로 상호 배제 구현
lock이 false이면 임계영역 진입, true이면 대기
임계영역 수행 후 다른 프로세스의 진입 허용을 위해 lock을 false로 설정
do{
while(test_and_set(&lock))
; /*do nothing*/
/*임계 구역*/
lock=false;
/*나머지 구역*/
}while(true);2. compare_and_swap 명령어
:두 워드의 내용을 원자적으로 교환하는 명령어
int compare_and_swap(int *value,int expected,int new_value){
int temp=*value;
if(*value==expected)
*value=new_value; // swap: 다른 프로세스 진입 방지응 위한 설정
return temp;
}✅ compare_and_swap 명령어로 상호 배제 구현
공유 변수 lock을 선언하고 0으로 초기화
lock==expected인 경우(0인 경우) 임계 영역 진입하면서 lock을 1로 세팅(swap)
임계영역 수행 후 다른 프로세스의 진입 허용을 위해 lock을 0으로 세팅
do{
while(compare_and_swap(&lock,0,1)!=0)
; /*do nothing*/
/*임계 구역*/
lock=0;
/*나머지 구역*/
}while(true);3. 한정된 대기 조건을 만족하는 상호 배제
test_and_set() 명령어를 사용하고, 한정된 대기 조건을 만족하는 상호 배제 구현
한 프로세스 i가 임계 구역을 떠날 때 waiting 배열 순회
순회 중 waiting[j]가 true인 첫 번째 대기 프로세스가 임계 영역에 진입하고 값은 false로 지정
임계 영역에 진입하고자 하는 프로세스는 최대한 n-1 양보
do{
waiting[i]=true;
while(waiting[i]&&key)
key=test_and_set(&lock);
waiting[i]=flase;
/*
임계 구역
*/
j=(i+1)%n;
while ((j!=i)&&!waiting[j])
j=(j+1)%n;
if(j==i) // 대기 중인 프로세스가 없는 경우
lock=false;
else // 첫 번쨰 대기 중인 프로세스인 경우
waiting[j]=false;
/*나머지 구역*/
}while(true);뮤텍스 락
임계 구역 문제를 해결하는 소프트웨어 툴의 하나로 상호 배제를 제공하는 락
먼저 락을 획득(acquire) 한 후에 락을 해제(release)하여 임계 영역을 보호(호출은 원자적이어야 함)
임계 구역 진입 전 바쁜 대기(스핀락) 사용(위에 처럼 while 루프를 이용한 방식)
임계 영역 구현시 바쁜 대기 사용의 장단점
- 구현 코드가 짧음
- 임계 영역의 점유가 드물면 바쁜 대기는 거의 없게 됨
- 많은 시간을 임계 영역에 있는 경우 CPU 시간 낭비
acquire(){
while(!available)
; /*busy wait*/
available=false;
}
release(){
available=true;
}
do{
/*acquire lock*/
/*임계 구역*/
/*release lock*/
/*나머지 구역*/
}while(true);세마포
프로세스를 동기화 시키는 (뮤텍스 락 보다) 좀 더 복잡한 동기화 툴
두 개의 표준 원자적 연산 wait()와 signal()로만 세마포(정수 변수 S) 접근
세마포의 정수 값을 변경하는 연산은 반드시 원자적으로 수행
- 카운팅 세마포: 제한 없는 영역의 정수값
- 이진 세마포: 이진 세마포의 값은 0과 1사이의 값만을 가짐(뮤텍스 락과 동일)
wait()와 signal()의 정의(기본 세마포)
세마포 의 값이 0이 되면 모든 사원이 사용 중임을 나타내고 자원을 사용하려는 프로세스는 세마포 값이 0보다 커질 때까지 기다림
wait(S){
while(S<=0)
; /*busy wait*/
S--;
}
signal(S){
S++;
}바쁜 대기가 없는 세마포 구현
세마포는 바쁜 대기 대신에 프로세스 자신을 봉쇄하고 세마포에 연관된 대기 큐에 삽입한다.
프로세스는 대기 상태로 전환되고 CPU 스케줄러가 다른 프로세스를 실행하기 위해 선택
typedef struct{
int value; // 세마포 값을 나타내는 정수
struct process *list; //대기 큐를 가리키는 포인터
}
wait(semaphore *S){
S->value--; //먼저 빼줘야함. cpu 스케줄링과 관련있기 때문
if(S->value **<** 0){
/*add this process to S->list*/
block(); // 자기를 호출한 프로세스를 중지하고 대기 큐에 삽입
}
}
signal(semaphore *S){
S->value++;
if(S->value **<=** 0){
/*remove a process P from S->list*/
wakeup(P); // 대기 큐에서 봉쇄되었던 프로세스 P 제거하고 준비 완료 큐에 삽입
}
}세마포의 문제점
잘못 사용하면 다양한 유형의 오류가 너무나도 쉽게 발생
→ 상호 배제 요구 조건을 위반하거나, 교착 상태가 발생
ex) 프로세스에서 wait()나 signal() 또는 둘 다 생략한 경우교착 상태와 기아
교착상태
두 개 이상의 프로세스들이, 오로지 하나의 프로세스에 의해서만 유발할 수 있는 이벤트(signal())를 무한정 기다리는 상황
ex) 두 개의 프로세스 P1과 P2에서 1로 초기화된 세마포 S와 Q를 접근
기아
교착 상태와 연관된 무한 봉쇄
프로세스들이 세마포에서 무한정 대기하는 것으로, 프로세스가 중지된 세마포 큐에서 제거되지 않음
모니터
고급 언어 수준의 동기화 구조물
추상화된 데이터 형은 데이터와 이 데이터를 조작하는 함수들을 하나의 단위로 묶어 보호함
모니터 구조물은 모니터 안에 항상 하나의 프로세스만이 활성화 되도록 보장
모니터 내의 프로세스들의 동기화를 위해 condition 변수 선언
condition형 변수에 호출될 수 있는 연산은 오직 wait()와 signal()
condition x,y;
x.wait() //다른 프로세스가 x.signal()을 호출할 때까지 일시 중단
x.signal() //하나의 일시 중단된 프로세스를 재개. 만약 중단된 프로세스가 없으면 효과 x자바 모니터
자바의 기본 스레드 동기화 모델은 모니터와 같은 병행성 기법 제공
모든 객체들은 하나의 락과 연관
메서드 또는 객체의 블록에 synchronized 선언하면 원자적으로 실행됨
synchronized 메서드(블록)가 종료하면 락이 해제되어 다른 스레드가 접근 가능
public synchronized void method(){
// 임계 영역
}
synchronized (참조하는 객체 변수){
// 임계 영역
}하나의 데이터(객체)마다 하나의 모니터를 결합
synchronized 메서드를 호출한 스레드는 봉쇄되어 객체의 락에 설정된 진입 집합에 추가
락이 가용한 경우 호출 스레드는 객체 락의 소유자가 되어 메서드로 진입
스레드가 메서드를 종료하면 락이 해제
자바 모니터는 무명 조건 변수 하나에만 연결 → wait()와 notify() 연산이 하나의 조건 변수에만 적용
스레드가 wait() 메서드 호출 시
- 스레드가 객체의 락을 해제
- 스레드 상태가 봉쇄로 설정
- 스레드가 대기 집합에 삽입되어 대기
스레드가 notify() 메서드 호출 시
- 대기 집합에서 임의의 스레드 T 선택
- 스레드 T를 진입 집합으로 이동
- T의 상태를 봉쇄에서 실행 가능으로 설정
