혼자 공부하는 컴퓨터구조 + 운영체제: 4. CPU 스케줄링, 프로세스 동기화, 교착 상태

 

11. CPU 스케줄링

 

CPU 스케줄링 구조

입출력 집중 프로세스(I/O bound process): 비디오 출력, 디스크 백업 등 입출력이 많은 프로세스. 실제 실행보다는 입출력장치를 기다리는 대기 상태에 많이 머무른다.
CPU 집중 프로세스(CPU bound process): 수학 연산, 그래픽 작업 등 CPU 연산이 많이 필요한 프로세스
 
기본적으로 CPU 작업에 비해 입출력장치의 속도가 느리므로, 입출력 집중 프로세스를 먼저 처리하여 입출력 집중 프로세스들을 입출력장치쪽으로 넘기는 것이 좋다.
 
- CPU를 이용하는 작업을 CPU burst, 입출력장치를 기다리는 작업을 I/O burst 라고 한다.
 
+ 프로세스 우선순위 직접 확인하기
리눅스나 macOS의 명령어로 ps -el 을 입력하면 프로세스들의 우선순위(Priority, PRI)를 확인할 수 있다. PRI 숫자가 클수록 우선순위가 높은 것이다.

 
큐
각 프로세스들은 CPU를 할당받기 위해 운영체제에서 관리하는 큐에 순서대로 줄을 선다. 기본적으로 PCB에 프로세스별로 우선순위가 적히지만, 각 프로세스들을 종류별로 큐에 넣어두면 CPU가 일일이 PRI들을 검사할 필요가 없다. 입출력 장치들을 이용하고 싶은 프로세스들은 대기 큐(waiting queue), CPU를 이용하고 싶은 프로세스들은 준비 큐(ready queue)라는 큐에 적재된다. 
 
 

CPU 스케줄링 알고리즘

크게는 두 가지로 나눌 수 있다.

• 선점형 스케줄링(preemptive scheduling): 어떤 프로세스가 CPU를 사용하고 있더라도 운영체제가 이를 중단시키고 더 우선순위가 높은 프로세스에 CPU를 할당. 자원을 골고루 배분할 수 있으나, 문맥 교환으로 인해 오버헤드가 발생할 수 있다.
• 비선점형 스케줄링(non-preemptive scheduling): 하나의 프로세스가 CPU를 사용하고 있다면, 우선순위가 높은 프로세스의 요청이 오더라도 일단 진행 중이던 프로세스를 완료한 이후에 다음 프로세스를 처리하는 방식. 문맥 교환은 적으나 선점한 프로세스가 끝날 때까지 무조건 대기해야한다.

 
알고리즘 예시
종류나 용어 자체가 중요하기보단, 이런 방식들이 있다는 것을 이해하는 것이 중요하다.
 

• 선입 선처리 스케줄링(FCFS, First Come First Served): 준비 큐에 삽입된 순서대로 실행하는 방식. 상대적으로 긴 프로세스가 먼저 삽입되어 시간이 오래 걸리면, 뒤에 들어온 짧은 프로세스에는 호위 효과(convoy effect)가 생겨 실행이 안되고 기다리게 된다.
• 최단 작업 우선 스케줄링(SJF, Shortest Job First Scheduling): CPU 사용 시간이 짧은 프로세스부터 실행하는 방식
• 라운드 로빈 스케줄링(round robin scheduling): 타임 슬라이스 개념을 도입한 방식. 예를 들어 각 프로세스의 소요 시간이 A: 22ms, B: 3ms, C: 7ms 와 같은 경우 5ms로 타임 슬라이스를 줄 수 있다. 이러면 A 프로세스는 5ms만큼 실행 후 큐의 맨 뒤로 보내지고, B는 5ms 전에 모두 처리, C는 5ms 만큼 처리 후 남은 2ms는 다시 큐의 뒤쪽으로 보내지는 방식이다. 타임 슬라이스의 크기가 너무 크면 선입 선처리와 다를 바 없고, 너무 작으면 문맥 교환이 매우 자주 일어나서 좋지 않을 수 있다.
• 최소 잔여 시간 스케줄링(SRT, Shortest Remaining Time): 최단 작업 우선 + 라운드 로빈 스케줄링이 합쳐진 형태. 타임 슬라이스를 적용하되, 다음 프로세스는 남아있는 작업의 소요 시간이 가장 적은 프로세스로 지정하여 처리하는 방식이다.
• 다단계 큐 스케줄링(multilevel queue scheduling): 큐를 여러 개 두어 우선순위를 매겨 처리하는 방식이다. 예컨대 우선순위 0인 큐에는 우선순위가 비교적 높아야하는 CPU 집중 프로세스들을 배치하고, 그 다음 우선순위에는 우선순위가 비교적 낮아도 되는 사용자와의 상호작용을 위한 프로세스를 두어 우선순위별로 처리할 수 있다. 또한 각 큐별로 정책을 달리해서 앞서 나온 선입 선처리, 라운드 로빈 스케줄링 등을 따로 적용할 수 있다.
• 다단계 피드백 큐 스케줄링(multilevel feedback queue scheduling): 우선순위가 높은 프로세스들만 처리하다보면 우선순위가 낮은 프로세스는 계속해서 실행 순서가 밀리는 기아(starvation) 현상이 발생할 수 있다. 이를 해결하기 위해 에이징(aging) 기법을 사용하여 프로세스가 얼마나 오랫동안 실행되지 않았는지 평가하고, 일정 시간이 넘는다면 높은 우선순위 큐로 옮겨서 처리하는 방식이다.

 

 
 
 
 

---

 

12. 프로세스 동기화

 

동기화(synchronization)

 
 프로세스(스레드) 사이의 수행 시기를 맞추는 것. 엄밀한 의미는 아래와 같다.

• 실행 순서 제어: 각 프로세스들을 올바른 순서대로 실행. read와 write가 있을 때 반드시 write후에 read를 해야 의미가 있다.
• 상호 배제: 동시 접근이 허락되지 않는 자원에는 한 개의 프로세스만 접근하게 하기. 계좌 잔고 5만원에서 (2만원 출금 + 잔고 업데이트) 프로세스와 (10만원 입금 + 잔고 업데이트) 프로세스는 동시에 잔고 5만원에 접근하면 안된다. 이럴 경우 5 - 2 + 10 = 13으로 처리되는 것이 아니라, 5 - 2 처리 전, 5 + 10 = 15로 처리되고 프로세스가 종료될 수 있다.

 
 
공유 자원(shared resource)과 임계 구역(critical section)
위 상호 배제의 계좌 예시에서, 각 프로세스가 함께 사용하는 자원을 공유 자원이라 한다. 공유 자원은 단순히 전역 변수가 될 수도 있지만 파일, 입출력 장치, 보조 기억 장치 등도 될 수 있다.
임계 구역은 동시에 접근하면 문제가 발생할 수 있는 코드 영역을 말한다. 임계 구역에는 반드시 한 개의 프로세스만 접근하고 나머지 프로세스들은 해당 프로세스의 작업이 끝날 때까지 대기해야한다. 잘못된 설정으로 인해 임계 구역에 2개 이상의 프로세스가 접근하여 임계 구역의 코드를 실행하는 경우를 레이스 컨디션(Race condition)이라고 한다.
 
 
 

동기화 기법

 
레이스 컨디션을 일으키지 않고 동기화를 하기 위한 운영체제의 원칙은 세 가지로 요약된다.

• 상호 배제(mutual exclusion): 한 프로세스가 임계 구역에 진입했다면 다른 프로세스는 임계 구역에 진입 불가
• 진행(progress): 임계 구역에 어떤 프로세스도 진입하지 않았다면 프로세스가 임계 구역에 진입이 가능
• 유한 대기(bounded waiting): 어떤 프로세스든 언젠가는 임계 구역에 들어올 수 있어야 함

 
 
뮤텍스락(Mutex Lock, MUTual EXclusion lock)
임계 구역에 자물쇠를 걸어두어 특정 프로세스가 임계 구역을 점유하고 있음을 표시하고 상호 배제를 할 수 있도록 하는 기법. 하나의 전역 변수와 두 개의 함수로 구현할 수 있다.

• 프로세스들이 공유하는 전역 변수 lock
• 임계 구역을 잠그는 acquire
• 임계 구역의 잠금을 해제하는 release

간이 코드로는 다음과 같이 구현될 것이다.

acquire()
임계 구역 코드 실행
release()

 

def acquire():
	while(lock=true):
    	계속 lock=true인지 확인
    lock = true  ## 만약 lock=false라면 lock=true로 변경

def release():
	lock = false

 
 
세마포(Semapore)
세마포도 뮤텍스락과 유사하게 자물쇠를 걸어잠근다는 개념이지만, 임계 구역에 있는 사용가능한 공유자원의 개수나 임계 구역에 접근이 가능한 프로세스의 개수를 변수로 두고 처리한다는 점이 다르다. 마치 여러 개의 방에 각각 자물쇠를 걸어두되, 자물쇠의 개수를 바탕으로 공유 자원에 접근이 가능한지를 판단하는 개념이다.
 
-간이 코드

wait()
//임계 구역에서 처리
signal()

def wait():
	while (S <= 0):
    	##반복적으로 확인
    S -= 1 ## 만약 1개라도 가능하면 S-1을 하고 임계구역 진입

def signal():
	S++	## 임계구역에서의 작업을 마치고 S+1

 
-예시
공유자원 2개, 프로세스 A1, A2, A3 일때 
1. A1 wait 호출, S -= 1 후 임계구역 진입
2. A2 wait 호출, S -= 1 후 임계구역 진입
3. A3 wait 호출, S > 0 일때까지 대기
4. A1 종료, signal 호출, S += 1
5. A3 진입, S -= 1 후 임계구역 진입
 
 
wait() 함수에서 계속해서 S 값을 확인하면 CPU의 주기를 낭비한다. 이를 보완하기 위해서 wait 상태의 프로세스가 생성되면 이 프로세스를 대기 큐에 넣고, 다른 프로세스가 signal 함수를 호출할 때 대기 큐의 프로세스를 준비 상태로 만들어주면 된다.
 
이 쯤에서 코드적으로 실제 뮤텍스와 세마포가 어떻게 작동하는지 이해하는 것이 좋다. 아래 해당 책 저자의 참고 문서 링크를 통해 더 잘 이해할 수 있다.
https://github.com/kangtegong/self-learning-cs/blob/main/synchronization/syncronization.md
 
 
모니터
세마포가 매번 임계 구역의 앞뒤로 wait, signal을 표시하는 방식을 개선한 방식이다. 각 임계 구역 로직 앞 뒤로 두 메서드를 일일이 추가해주는 것은 번거롭기도 하고, 잘못된 사용으로 인해 오작동 할수도 있기 때문이다.
 

 
모니터는 공유 자원 영역을 처리하는 연산 부분을 각 공유자원마다 인터페이스로 만든다. 말하자면 "wait()-임계 구역 연산-signal()"을 하나의 묶음으로 묶어서 처리할 수 있도록 인터페이스를 두는 것이다. 그리고 모니터 앞에 큐를 둔 후, 모니터 안에는 항상 하나의 프로세스만 들어올 수 있도록 만든다.
 
실행 순서 기능을 제공하기 위해서 조건 변수(condition variable)를 제공한다. 각 조건 변수별로 큐를 두어 특정 조건이 될 때까지 어떤 프로세스를 기다리게 할 수 있다. 위 그림의 예시에서 먼저 실행된 프로세스가 작업이 중간에 중단되어 x.wait()를 호출하면, 해당 프로세스는 대기 상태에 있다가, 그 다음 모니터에 들어온 프로세스가 x.signal()을 호출하여 조건 변수를 만족시켜주면 그제서야 다시 실행되는 구조이다.
 
 

---

 
 

13. 교착 상태(Deadlock)

 
교착 상태는 2개 이상의 프로세스 등이 각자 공유자원을 점유한 채 다른 공유자원의 사용을 서로 기다릴 때 발생한다. 예를 들어 웹 브라우저 프로세스는 공유자원 1 점유, 공유 자원 2의 사용을 대기 중일때, 게임 프로세스는 공유자원 2 점유, 공유 자원 1의 사용을 대기하는 경우가 있을 수 있다. 이러면 두 프로세스 모두 대기만 하게되어 교착상태가 발생한다.
 
 

교착 상태 발생 조건 4가지

1. 상호 배제(mutual exclusion) : 어떤 프로세스가 한 자원을 사용할 때, 다른 프로세스는 그 자원을 사용할 수 없는 경우에 교착 상태가 발생할 수 있다.
2. 점유와 대기(hold and wait) : 프로세스가 어떤 자원을 할당받은 상태에서 다른 자원의 할당을 기다릴 때 교착 상태가 발생할 수 있다.
3. 비선점(nonpreemptive) : 어떤 프로세스가 강제로 다른 프로세스의 자원을 뺐는다면(선점) 교착 상태는 발생하지 않을 수 있다.
4. 원형대기(circular wait) : 각 프로세스들과 요청 및 할당받은 자원이 원의 형태를 띄면서 대기하는 원형 대기(circular wait)가 발생할 시, 교착상태가 발생할 수 있다.

 
 

자원 할당 그래프(resource allocation graph)

교착 상태를 표현하는 방법. 규칙은 아래와 같다.

• 프로세스는 원으로, 자원은 사각형으로 그린다.
• 사용할 수 있는 자원의 개수는 자원 사각형 내 점으로 표시한다.
• 프로세스가 어떤 자원을 받아 사용 중이라면 자원에서 프로세스를 향해 화살표를 표시한다.
• 프로세스가 어떤 자원을 기다리고 있다면 프로세스에서 자원으로 화살표를 표시한다.

 

 
 

교착 상태 해결 방법

 
교착 상태 예방
교착 상태 발생 필요 조건 4가지 중 하나를 충족하지 못하게 하면 된다. 전반적으로 예방 방식은 이론적으로는 가능하나 모두 단점이 있어서 실제로 사용하기는 어려운 방법이다.
 

• 상호 배제 제거 : 공유 자원에 대한 상호 배제를 제거하면 공유 자원을 같이 쓰다가 생기는 부작용이 더 크므로 현실적으로 어려운 방법이다.
• 점유와 대기 제거 : 한 프로세스가 점유를 한다면, 다른 자원에 대해 대기를 못하게 하는 방식. 이럴 경우 한 프로세스에 필요한 자원들을 몰아주고, 그 다음 순차적으로 다른 프로세스가 자원들을 할당받도록 해야한다. 자원의 활용률이 낮아진다.
• 비선점 제거 : 앞선 글에서 설명한대로 CPU는 선점 방식으로 할당이 가능하다. 그러나 프린터와 같은 자원은 작업 진행 중 다른 프로세스에게 프린터 자원을 빼앗기면 문제가 될 수 있다.
• 원형 대기 제거 : 진행 중인 프로세스에 번호를 붙이고 오름차순으로 진행되도록 하면 된다. 예를 들어 1~5번까지의 프로세스가 있다면 5번 프로세스는 1번 프로세스를 요구하지 못하도록 만들면 된다. 그러나 실제로 진행 중인 수많은 프로세스에 일일이 번호를 붙이고 구별하는 것은 부담이 되며, 또 어떤 번호를 어떻게 붙이느냐에 따라 자원 활용률이 크게 달라질 수 있다.

 
 
교착 상태 회피
교착상태가 발생하지 않는 안전 상태에서만 자원을 할당하는 방식이다. 자원의 수와 프로세스의 수를 비교하여 안전/불안전 상태를 판별한다.
 
상황 1
할당 가능한 자원 : 12개
프로세스 P1 : 최대 요구량 10, 현재 사용량 5
프로세스 P2 : 최대 요구량 4, 현재 사용량 2
프로세스 P3 : 최대 요구량 9, 현재 사용량 2
 
상황 1에서 할당 가능한 자원 12개 중 9개를 사용하고 있다. 즉 3개가 남아있다. 이 상태에서 교착상태가 발생하지 않으려면, 먼저 P2에 자원을 2개 할당하여 P2 프로세스를 끝내야한다. 이후 반환된 4개의 자원과 남아있던 3개의 자원에서 5개를 P1에 할당하고, P1 완료 후 P3를 처리하는 방식으로 진행해야만 교착상태가 발생하지 않는다. 이렇게 P2 -> P1 -> P3로 교착상태가 발생하지 않도록 처리하는 순서열을 안전 순서열(safe sequence)이라고 한다.
 
안전 순서열의 예시에서 짐작할 수 있듯이, 교착 상태 회피는 할당 가능한 자원의 수 대비 자원을 요구하는 프로세스가 많을수록 위험하다고 판단한다.
 
 
교착 상태 검출 후 회복
사후 조치 방식이다. 프로세스가 자원을 요구할 때마다 모두 할당 후, 교착상태가 발생했는지 주기적으로 검사한다.
 

• 선점을 통한 회복 : 교착 상태가 해결될 때까지 하나의 프로세스에 자원을 몰아주는 방식. 다른 프로세스에서 자원들을 빼앗아온다.
• 프로세스 강제 종료를 통한 회복 : 교착 상태에 빠진 프로세스를 한 번에 강제 종료 하는 방법 또는 프로세스를 하나씩 종료해가며 교착 상태를 해결하는 방식이 있다. 강제 종료 시 작업 내용을 잃을 가능성이 있다.