러프한 운영체제 기초 2편 | CPU 스케줄링과 교착 상태

시작하기 앞서

이 글은 웹 백엔드 주니어 개발자가 인프런의 그림으로 쉽게 배우는 운영체제 강의를 들으며 공부한 내용을 러프하게 정리한 글입니다. 

 

이전 글

러프한 운영체제 기초 1편: 러프한 운영체제 기초 1편 | 프로세스와 약간의 쓰레드 

---

CPU 스케줄링

CPU 스케줄링이란

어떤 프로세스에 CPU 리소스를 주어야 하는지 결정하는 작업. 컴퓨터 시스템의 효율에 직결되는 중요한 작업으로 운영체제를 공부할 때 가장 중요한 주제 중 하나이다.

 

 

CPU 스케줄링의 고려사항

1. 어떤 프로세스에게 CPU 리소스를 주어야 하는가?
2. CPU를 할당 받은 프로세스가 얼마의 시간 동안 CPU를 사용해야 하는가?

(CPU 스케줄링은 컴퓨터의 성능에 굉장히 많은 영향을 미친다!)

 

 

CPU 스케줄링의 목표

1. 공평성: 가장 큰 목표로 모든 프로세스가 공평하게 CPU의 리소스를 사용할 수 있어야 함 (경우에 따라 공평의 기준은 다를 수 있음. 예를 들어 자율주행의 경우 탑승자의 안전을 위한 프로세스에게 더 많은 우선권을 주는 것이 공평함)
2. 리소스 사용률: CPU의 사용률을 높이거나 I/O 디바이스의 사용률을 높이는 것을 목표로 함
3. 오버헤드 최소화: 스케줄링을 위한 계산이 복잡하거나 과도하게 많은 컨텍스트 스위칭이 발생할 경우 스케줄링에 많은 비용이 발생할 수 있음. 배보다 배꼽이 커지는 꼴로, 이러한 오버헤드를 최소화하는 것을 목표로 함
4. 처리량: 같은 시간 내 더 많은 처리를 할 수 있는 것을 목표로 함
5. 대기시간: 작업을 요청하고 실제 작업이 이루어지기까지 대기하는 시간이 적은 것을 목표로 함
6. 응답시간: 대화형 시스템의 경우 사용자의 요청에 얼마나 빠르게 응답하는지가 중요하기 때문에 응답시간이 빠른 것을 목표로 함

 

 

CPU 스케줄링 알고리즘

CPU 스케줄링은 PCB의 상태 중 준비, 대기, 실행 상태와 관련이 있음. 그 중 준비와 대기 상태는 자료구조 중 QUEUE로 이루어져 있기 때문에 CPU 스케줄링 알고리즘은 기본적으로 선납선출의 성격을 띔.

• 단순한 Queue: FIFO(First In First Out) 즉, 스케줄링 큐에 들어오는 순서대로 CPU를 할당해 작업. 먼저 들어온 프로세스가 완전히 끝나야만 다음 프로세스가 실행될 수 있음. I/O 작업이 있거나 프로세스의 burst 시간에 따라 비효율적일 수 있음. (초기에 사용됨)
• SLF(Shortest Job First) 알고리즘: Queue의 단점 즉, burst 시간에 따른 대기 시간 차이가 심한 것을 해소하고자 도입됨. 원리는 가장 빨리 끝나는 프로세스를 먼저 실행하는 것. Queue보다 이론상 빠르지만 구현상 2가지 심각한 문제가 있음.
  • 어떤 프로세스가 언제 끝날지 알 수 없음 (ex. 인터넷을 켜놓고 사용하는 사용자가 인터넷을 언제 닫을지 알 수 없음)
  • burst 타임이 긴 프로세스가 언제 실행될지 알 수 없음 (중간에 계속 burst 타임이 짧은 프로세스가 유입될 경우 계속 순서가 밀림)
  • 이러한 이유로 SLF는 사용되지 않음.
• RR(Round Robin) 알고리즘: 시분할 방식. 일정 시간만큼만 프로세스에게 CPU 할당권을 주고 실행시간이 종료되면 프로세스를 강제 종료, 큐의 가장 뒤쪽으로 밀어 넣음.
• MLFQ(Multi Level Feedback Queue) 알고리즘: RR을 업그레이드한 알고리즘으로 오늘 날 운영체제에서 가장 일반적으로 사용되는 CPU 스케줄링 알고리즘. 프로세스를 CPU bound process와 I/O bound process로 나누어 각각에 다른 타임 슬라이스를 할당
  • 타임 슬라이스 = CPU를 사용할 수 있는 시간. 타임 슬라이스가 너무 길 경우 스택에서 발생하는 문제가 발생하고 너무 짧을 경우 스케줄링에 필요한 자원이 너무 많이 들어 오버헤드가 커짐 (적당해야 한다)

 

 

동기화 문제

공유자원과 임계구역

• 공유자원: 여러 프로세스가 공동으로 이용하는 변수, 메모리, 파일 등을 말함. 각 프로세스의 접근 순서에 따라 결과가 달라질 수 있음. 운영체제는 컨텍스트 스위칭을 통해 프로세스를 시분할 처리하기 때문에 공유자원을 사용하는 프로세스가 언제 어떻게 실행될지 예측하기 어려움
• 임계구역: 여러 프로세스가 동시에 사용하면 안되는 영역 즉, 공유자원에 대한 프로세스의 접근 순서에 따라 실행 결과가 달라질 수 있는 프로그램 영역을 말함.

 

 

상호배제의 요구사항

상호배제는 임계구역에서 적용되는 원칙으로 다음과 같은 요구사항이 존재.

1. 임계영역엔 동시에 하나의 프로세스만 접근한다.
2. 여러 요청에도 하나의 프로세스의 접근만 허용한다.
3. 임계구역에 들어간 프로세스는 빠르게 나와야 한다.

 

 

동기화 문제와 경쟁조건

• 동기화 문제: 공유자원을 여러 프로세스가 동시에 사용함으로써 발생하는 문제
• 경쟁 조건: 공유자원을 두개 이상의 프로세스가 동시에 사용하려고 할 때 발생하는 조건. 여러 프로세스가 동시에 공유자원에 접근하고자 할 때, 경쟁 조건이 발생했다고 말한다.

 

 

교착 상태(데드락)

• 두 개 이상의 프로세스가 서로의 작업이 끝나기를 기다리고 있는 상황에서 무한정 대기상태에 빠지는 상태.
• 멀티 프로그래밍 환경에서 흔하게 발생할 수 있는 문제이지만 이 문제를 해결하는 일반적인 방법은 아직 없음.

 

 

교착 상태의 조건

교착 상태의 조건에는 총 4가지가 있는데, 이 중 하나라도 충족되지 않으면 교착 상태는 발생하지 않음.

1. 상호배제: 어떤 프로세스가 한 리소스를 점유했다면 다른 프로세스는 그 리소스를 사용하면 안된다.
2. 비선점: 프로세스가 리소스를 사용할 때 다른 프로세스가 그 리소스를 빼앗으면 안된다.
3. 점유와 대기: 프로세스가 리소스 A를 얻은 상태에서 작업을 위해 리소스 B를 동시에 원하는 상태.
4. 원형 대기: 여러 프로세스가 서로 상대 프로세스의 자원을 기다리면서 자기 자신의 리소스를 놓지 않는 상태.

이론상 교착 상태는 위 조건 중 하나라도 충족되지 않으면 발생하지 않지만, 이를 바탕으로 교착상태를 예방하는 것은 비용이 매우 많이 들고 어렵다고 한다! -> 그래서 일반적으로 교착 상태를 발생시키지 않는 것에 초점을 두지 않고 교착 상태가 발생했을 때 어떻게 해결해야 하는지에 더 집중한다고 한다.

 

 

교착 상태를 검출하는 두 가지 방법

1. 가벼운 교착 상태 검출
   1. 타이머를 이용하는 방법.
   2. 프로세스가 일정 시간동안 작업하지 않으면 교착상태가 발생했다고 간주함.
2. 무거운 교창 상태 검출
   1. 자원할당 그래프 사용.
   2. 자원할당 그래프 <- 프로세스가 할당받은 자원, 프로세스에게 필요한 다른 자원 요청 등이 자원할당 그래프에서 운영체제에 의해 관리되고 감시됨
   3. 운영체제는 계속 자원할당 그래프를 관리하다 프로세스간의 자원 할당이 순환 구조를 이루게 되면 교착상태라고 판단하고 프로세스들을 강제종료.

 

교착 상태 검출 후 해결 방법

• 운영체제는 일정시간마다 프로세스들의 작업 내용을 저장함. (체크포인트)
• 교착 상태 발생 시 해당 프로세스를 강제 종료.
• 이후 가장 최신 체크포인트로 롤백
• 프로세스는 체크포인트부터 시작해 작업 내용을 다시 시작한다.