교착 상태, 경쟁 조건/상태, 세마포어와 뮤텍스, 메모리 관리

데드락(=교착 상태)이 발생하는 경우

 

Process1, Process 2 모두 Resource 1, Resource 2 사용이 필요한 경우

멀티 프로그래밍 환경에서, 두 프로세스가 서로 원하는 자원이 다른 프로세스에 할당되어 있어서 무한정 기다리고 있을 때 발생한다.

 

데드락 발생 조건

4가지 모두 성립해야 데드락 발생 (하나라도 성립하지 않으면 데드락 문제 해결 가능)

1. 상호 배제(Mutual exclusion)자원은 한번에 한 프로세스만 사용할 수 있음
2. 점유 대기(Hold and wait)최소한 하나의 자원을 점유하고 있으면서 다른 프로세스에 할당되어 사용하고 있는 자원을 추가로 점유하기 위해 대기하는 프로세스가 존재해야 함
3. 비선점(No preemption)다른 프로세스에 할당된 자원은 사용이 끝날 때까지 강제로 빼앗을 수 없음
4. 순환 대기(Circular wait)프로세스의 집합에서 순환 형태로 자원을 대기하고 있어야 함

 

데드락 처리

- 교착 상태를 예방 & 회피

1. 예방(prevention): 교착 상태 발생 조건 중 하나를 제거하면서 해결한다 (자원 낭비 엄청 심함)

1. • 상호배제 부정 : 여러 프로세스가 공유 자원 사용
   • 점유대기 부정 : 프로세스 실행전 모든 자원을 할당
   • 비선점 부정 : 자원 점유 중인 프로세스가 다른 자원을 요구할 때 가진 자원 반납
   • 순환(환형)대기 부정 : 자원에 고유번호 할당 후 순서대로 자원 요구
2. 회피(avoidance): 교착 상태 발생 시 피해나가는 방법
   • 은행원 알고리즘(Banker's Algorithm)
     • 은행에서 모든 고객의 요구가 충족되도록 현금을 할당하는데서 유래함
     • 프로세스가 자원을 요구할 때, 시스템은 자원을 할당한 후에도 안정 상태로 남아있게 되는지 사전에 검사하여 교착 상태 회피
     • 안정 상태면 자원 할당, 아니면 다른 프로세스들이 자원 해지까지 대기

 

- 교착 상태를 탐지 & 회복

1. 탐지(detection): 자원 할당 그래프를 통해 교착 상태를 탐지함
   
   • 자원 요청 시, 탐지 알고리즘을 실행시켜 그에 대한 오버헤드 발생함
2. 회복(Recovery): 교착 상태 일으킨 프로세스를 종료하거나, 할당된 자원을 해제시켜 회복시키는 방법
   • 프로세스 종료 방법
     • 교착 상태의 프로세스를 모두 중지
     • 교착 상태가 제거될 때까지 하나씩 프로세스 중지프로세스 종료 방법
   • 자원 선점 방법
     • 교착 상태의 프로세스가 점유하고 있는 자원을 선점해 다른 프로세스에게 할당 (해당 프로세스 일시정지 시킴)
     • 우선 순위가 낮은 프로세스나 수행 횟수 적은 프로세스 위주로 프로세스 자원 선점

 

Race Condition(경쟁 상태)

공유 자원에 대해 여러 프로세스가 동시에 접근할 때, 결과값에 영향을 줄 수 있는 상태

 

Race Condition이 발생하는 경우

1. 커널 작업을 수행하는 중에 인터럽트 발생
   • 문제점 : 커널모드에서 데이터를 로드하여 작업을 수행하다가 인터럽트가 발생하여 같은 데이터를 조작하는 경우
   • 해결법 : 커널모드에서 작업을 수행하는 동안, 인터럽트를 disable 시켜 CPU 제어권을 가져가지 못하도록 한다.
2. 프로세스가 'System Call'을 하여 커널 모드로 진입하여 작업을 수행하는 도중 문맥 교환이 발생할 때
   • 문제점 : 프로세스1이 커널모드에서 데이터를 조작하는 도중, 시간이 초과되어 CPU 제어권이 프로세스2로 넘어가 같은 데이터를 조작하는 경우 ( 프로세스2가 작업에 반영되지 않음 )
   • 해결법 : 프로세스가 커널모드에서 작업을 하는 경우 시간이 초과되어도 CPU 제어권이 다른 프로세스에게 넘어가지 않도록 함
3. 멀티 프로세서 환경에서 공유 메모리 내의 커널 데이터에 접근할 때
   • 문제점 : 멀티 프로세서 환경에서 2개의 CPU가 동시에 커널 내부의 공유 데이터에 접근하여 조작하는 경우
   • 해결법 : 커널 내부에 있는 각 공유 데이터에 접근할 때마다, 그 데이터에 대한 lock/unlock을 하는 방법

 

공유된 자원은 한번에 하나의 프로세스만 접근할 수 있도록 해야한다 -> 세마포어, 뮤텍스

세마포어

멀티 프로그래밍 환경에서 공유 자원의 데이터는 한 번에 하나의 프로세스만 접근할 수 있도록 제한하는 방법

 

* 세마포어의 P, V 연산

P : 임계 구역 들어가기 전에 수행 (프로세스 진입 여부를 자원의 개수(S)를 통해 결정)

V : 임계 구역에서 나올 때 수행 (자원 반납 알림, 대기 중인 프로세스를 깨우는 신호)

procedure P(S)   --> 최초 S값은 1임
    while S=0 do wait  --> S가 0면 1이 될때까지 기다려야 함
    S := S-1   --> S를 0로 만들어 다른 프로세스가 들어 오지 못하도록 함
end P

--- 임계 구역 ---

procedure V(S) --> 현재상태는 S가 0임
    S := S+1   --> S를 1로 원위치시켜 해제하는 과정
end V

이를 통해, 한 프로세스가 P 혹은 V를 수행하고 있는 동안 프로세스가 인터럽트 당하지 않게 된다. P와 V를 사용하여 임계 구역에 대한 상호배제 구현이 가능하게 되었다.

ex) 최초 S 값은 1이고, 현재 해당 구역을 수행할 프로세스 A, B가 있다고 가정

1. 먼저 도착한 A가 P(S)를 실행하여 S를 0으로 만들고 임계구역에 들어감
2. 그 뒤에 도착한 B가 P(S)를 실행하지만 S가 0이므로 대기 상태
3. A가 임계구역 수행을 마치고 V(S)를 실행하면 S는 다시 1이 됨
4. B는 이제 P(S)에서 while문을 빠져나올 수 있고, 임계구역으로 들어가 수행함

 

뮤텍스(상호 배제, Mutual Exclusion)

임계 구역을 가진 스레드들의 실행시간이 서로 겹치지 않고 각각 단독으로 실행되게 하는 기술

해당 접근을 조율하기 위해 lock과 unlock을 사용한다.

• lock : 현재 임계 구역에 들어갈 권한을 얻어옴 (만약 다른 프로세스/스레드가 임계 구역 수행 중이면 종료할 때까지 대기)
• unlock : 현재 임계 구역을 모두 사용했음을 알림. (대기 중인 다른 프로세스/스레드가 임계 구역에 진입할 수 있음)

뮤텍스는 상태가 0, 1로 이진 세마포어로 부르기도 함

 

1. 데커 알고리즘

flag와 turn 변수로 임계 구역에 들어갈 프로세스/스레드를 결정하는 방식

• flag : 프로세스 중 누가 임계영역에 진입할 것인지 나타내는 변수
• turn : 누가 임계구역에 들어갈 차례인지 나타내는 변수

// 프로세스 i
while(true) {
    flag[i] = true; // 프로세스 i가 임계 구역 진입 시도
    while(flag[j] == true) { // 프로세스 j가 임계 구역에 들어갈 것이라고 선언했다면
        if(turn == j) { // j가 이미 임계 구역에 진입 했다면
            flag[i] = false; // 프로세스 i 임계 영역 진입 취소
            while(turn == j) {} // turn이 j일 동안 대기
            flag[i] = true; // j turn이 끝나면 프로세스 i 다시 임계 영역 진입 시도
        }
    }
    
    // ------- 임계 구역 ---------
    
    turn = j; // 임계 구역 사용 끝나면 turn을 넘김
    flag[i] = false; // flag 값을 false로 바꿔 임계 구역 사용 완료를 알림
}

 

2. 피터슨 알고리즘

데커와 유사하지만, 상대방 프로세스/스레드에게 진입 기회를 양보하는 것에 차이가 있음

while(true) {
    flag[i] = true; // 프로세스 i가 임계 구역 진입 시도
    turn = j; // 이때 다른 프로세스 j 에게 진입 기회 양보
    while(flag[j] == true && turn == j) {} // 다른 프로세스가 진입 시도하면 대기
    
    // 프로세스 j가 끝나면 flag[j] == false, turn == i
    // ------- 임계 구역 ---------
    
    flag[i] = false; // 프로세스 i의 임계 구역 사용 완료를 알림
}

 

3. 제과점 알고리즘

여러 프로세스/스레드에 대한 처리가 가능한 알고리즘. 가장 작은 수의 번호표를 가지고 있는 프로세스가 임계 구역에 진입한다.

while(true) {
    
    isReady[i] = true; // 번호표 받을 준비
    number[i] = max(number[0~n-1]) + 1; // 현재 실행 중인 프로세스 중에 가장 큰 번호 배정 
    isReady[i] = false; // 번호표 수령 완료
    
    for(j = 0; j < n; j++) { // 모든 프로세스 번호표 비교
        while(isReady[j]); // 비교 프로세스가 번호표 받을 때까지 대기
        while(number[j] && number[j] < number[i] && j < i);
        
        // 프로세스 j가 번호표 가지고 있어야 함
        // 프로세스 j의 번호표 < 프로세스 i의 번호표
    }
    
    // ------- 임계 구역 ---------
    
    number[i] = 0; // 임계 구역 사용 종료
}

 

 

메모리 관리

다중 프로그래밍 시스템에 여러 프로세스를 수용하기 위해 주기억장치를 동적 분할하는 메모리 관리 작업이 필요

즉, 어떻게 하드디스크에 있는 프로그램을 어떻게 메모리에 적재할 것인지 판단해야 한다.

 

1. 연속 메모리 관리

프로그램 전체가 하나의 커다란 공간에 연속적으로 할당되어야 함

• 고정 분할 기법 : 주기억장치가 고정된 파티션으로 분할 (내부 단편화 발생)
• 동적 분할 기법 : 파티션들이 동적 생성되며 자신의 크기와 같은 파티션에 적재 (외부 단편화 발생)

* 단편화 : 기억 장치의 빈 공간 or 자료가 여러 조각으로 나뉘는 현상

* 내부 단편화: 프로세스가 사용하는 메모리 공간에 남는 부분

* 외부 단편화: 메모리 공간 중 사용하지 못하게 되는 부분

 

2. 불연속 메모리 관리

프로그램의 일부가 서로 다른 주소 공간에 할당될 수 있는 기법. 단편화 문제를 해결하기 위해 나온 기법.

-> 내부 단편화 해결을 위한 세그멘테이션 (가변 크기)

-> 외부 단편화 해결을 위한 페이징 (고정 크기)

페이징

프로세스를 일정한 크기의 페이지로 분할에서 메모리에 적재하는 방식

* 페이지 : 고정 사이즈의 가상 메모리 내 프로세스 조각

* 프레임 : 페이지 크기와 같은 주기억장치 메모리 조각

외부 단편화 X, 소량의 외부 단편화 존재

 

* 페이지 테이블

가상 메모리는 고정 크기의 페이지, 물리 메모리는 고정 크기의 프레임으로 분리되어 있다. 개별 페이지는 순서에 상관 없이 물리 메모리에 있는 프레임에 매핑되어 있다. 모든 프로세스는 하나의 페이지 테이블을 갖고 있으며, 여기에 메인 메모리에 적재되어있는 페이지 번호와 해당 페이지가 위치한 메인 메모리 시작 주소가 있다.

 

 

세그멘테이션

가상 메모리를 서로 크기가 다른 논리적 단위로 분할한 것

세그멘테이션은 프로세스를 물리적 단위인 페이지가 아닌 논리적 단위인 세그먼트로 분할해서 메모리에 적재하는 방식

* 세그먼트 : 서로 다른 크기를 가진 논리적 블록이 연속적 공간에 배치되는 것

내부 단편화X, 메모리 사용 효율 개선, 동적 분할을 통한 오버헤드 감소, but 외부 단편화 존재

 

* 세그먼트 테이블

분할 방식을 제외하면, 페이징과 매핑 테이블 동작 방식도 동일하다. 매핑 테이블은 <segment. offser> 형태가 될 것이다. 

가상 메모리 페이징

필요한 페이지를 전부 로드시키지 않고 필요한 페이지가 있으면 나중에 자동으로 불러들어짐

외부 단편화X, 복잡한 메모리 관리로 오버헤드 발생

 

가상 메모리 세그먼테이션

필요하지 않은 세그먼트들은 로드되지 않았다가, 필요할 때 나중에 자동으로 불러들어짐

내부 단편화X, 복잡한 메모리 관리로 오버헤드 발생

 

 

페이지 교체

메모리 과할당이 발생했을 때, 프로세스 하나를 swap out해서 빈 프레임을 확보하는 것

1. 프로세스 실행 도중 페이지 부재 발생
2. 페이지 결함(page fault)을 발생시킨 페이지 위치를 디스크에서 찾음
3. 메모리에 빈 프레임이 있는지 확인
4. 빈 프레임이 있으면 해당 프레임을 사용
5. 빈 프레임이 없으면, victim 프레임을 선정해 디스크에 기록하고 페이지 테이블을 업데이트함
6. 빈 프레임에 페이지 폴트가 발생한 페이지를 올리고, 페이지 테이블 업데이트

페이지 교체가 이루어지면 아무일이 없던것 처럼 프로세스를 계속 수행시켜주면서 사용자가 알지 못하도록 해야 함

이때, 아무일도 일어나지 않은 것처럼 하려면, 페이지 교체 당시 오버헤드를 최대한 줄여야 한다.

* 오버헤드를 감소시키는 해결법

이처럼 빈 프레임이 없는 상황에서 victim 프레임을 비울 때와 원하는 페이지를 프레임으로 올릴 때 두 번의 디스크 접근이 이루어진다. 따라서, 페이지 교체가 많이 이루어지면, 이처럼 입출력 연산이 많이 발생하게 되면서 오버헤드 문제가 발생한다.

방법1)

변경 비트를 모든 페이지마다 두어, victim 페이지가 정해지면 해당 페이지의 비트를 확인한다.

* 해당 비트가 set 상태면? → 해당 페이지 내용이 디스크 상의 페이지 내용과 달라졌다는 뜻이다. (즉, 페이지가 메모리 올라온 이후 한번이라도 수정이 일어났던 것. 따라서 이건 디스크에 기록해야함)

* 비트가 clear 상태라면? → 디스크 상의 페이지 내용과 메모리 상의 페이지가 정확히 일치하는 상황이다. (즉, 디스크와 내용이 같아서 기록할 필요가 없음)

비트를 활용해 디스크에 기록하는 횟수를 줄이면서 오버헤드에 대한 수를 최대 절반으로 감소시키는 방법이다.

방법2)

페이지 교체 알고리즘을 상황에 따라 잘 선택해야 한다.

현재 상황에서 페이지 결함이 발생될 확률을 최대한 줄여줄 수 있는 교체 알고리즘을 사용해야 한다.

 

페이지 교체 알고리즘

페이지 부재 발생 → 새로운 페이지를 할당해야 함 → 현재 할당된 페이지 중 어떤 것 교체할 지 결정하는 방법

=> 가상 메모리는 요구 페이지 기법을 통해 필요한 페이지만 메모리에 적재하고 사용하지 않는 부분은 그대로 둔다.

하지만 필요한 페이지만 올려도 메모리는 결국 가득 차게 되고, 올라와있던 페이지가 사용이 다 된 후에도 자리만 차지하고 있을 수 있어, 메모리가 가득 차면, 추가로 페이지를 가져오기 위해 안쓰는 페이지는 out하고, 해당 공간에 현재 필요한 페이지를 in 시켜야 한다. 여기서 어떤 페이지를 out 시켜야할 지 정하는 알고리즘이다. (이때 out 되는 페이지를 victim page라고 부른다.)

 

 

1. FIFO 알고리즘

First-in First-out, 메모리에 먼저 올라온 페이지를 먼저 내보내는 알고리즘

victim page : 가장 먼저 메모리에 올라온 페이지초기화 코드에 쓰기 적절한 방법 (처음 프로세스시 초기화하는 역할이므로, FIFO 알고리즘으로 실행 후 가장 먼저 내보래는 것이 가능)

 

2. OPT 알고리즘

Optimal Page Replacement 알고리즘, 앞으로 가장 사용하지 않을 페이지를 가장 우선적으로 내보냄

FIFO 보다는 페이지 결함 횟수를 많이 감소시킬 수 있으나, 실질적으로 페이지가 앞으로 잘 사용되지 않을 것이라는 보장이 없기 때문에 수행하기 어려운 알고리즘이다.

 

3. LRU 알고리즘

Least-Recently-Used, 최근에 사용하지 않은 페이지를 가장 먼저 내려보내는 알고리즘

OPT의 경우 미래 예측이지만, LRU의 경우는 과거를 보고 판단하므로 실질적으로 사용이 가능한 알고리즘

OPT보다는 페이지 결함이 더 일어날 수 있지만, 실제로 사용할 수 있는 페이지 교체 알고리즘에서는 가장 좋은 방법 중 하나이다.

 

 

교체 방식

Global 교체

• 메모리 상의 모든 프로세스 페이지에 대해 교체하는 방식

Local 교체

• 메모리 상의 자기 프로세스 페이지에서만 교체하는 방식

다중 프로그래밍의 경우, 메인 메모리에 다양한 프로세스가 동시에 올라올 수 있음

따라서, 다양한 프로세스의 페이지가 메모리에 존재함.

페이지 교체 시, 다양한 페이지 교체 알고리즘을 활용해 victim page를 선정하는데, 선정 기준을 Global로 하느냐, Local로 하느냐에 대한 차이

→ 실제로는 전체를 기준으로 페이지를 교체하는 것이 더 효율적이라고 함. 자기 프로세스 페이지에서만 교체를 하면, 교체를 해야할 때 각각 모두 교체를 진행해야 하므로 비효율적이다.