프로세스 생명주기, CPU 스케줄러, 스케줄링 알고리즘

프로세스 생명주기 (Process Lifecycle)

연산을 담당하는 CPU는 한정되어 있기 때문에 프로세스는 생명주기를 가지고 CPU를 공유하여 사용한다.

프로세스 생명주기는 다음과 같은 5단계를 가진다.

• new
  • 프로세스가 디스크에서 메모리로 올라간 상태
• ready
  • 다른 프로세스가 CPU를 점유하고 있어 대기하는 상태
• running
  • 프로세스가 CPU를 할당 받아 작업을 수행하는 상태
• waiting
  • I/O 요청, 이벤트 완료까지 기다리는 상태, 완료되면 ready queue로 이동
• terminated
  • 프로세스의 생명주기가 끝나 종료된 상태

CPU 스케줄러

CPU 스케줄러란 OS에서 다중 프로그램을 지원하기 위해 프로세스들을 효율적으로 CPU에 할당하는 역할을 수행하는 운영체제 커널의 모듈이다.

스케줄러에는 단기, 중기, 장기 스케줄러가 존재한다.

• 장기 스케줄러
  • 어떤 프로세스를 디스크에서 가져와 메모리에 올리기 전 상태인 ready queue에 넣을지 결정하는 역할 수행
  • 과거에는 메모리 부족으로 사용했으나, 현대의 OS에서는 장기 스케줄러 없이 디스크에서 바로 메모리로 올림
• 단기 스케줄러
  • 특정 스케줄링 알고리즘을 통해 ready 상태인 프로세스들 중 어떤 프로세스를 running 상태로 CPU에 할당할지 결정하는 역할 수행
  • ms 이하의 시간 단위로 빈번하게 호출되기에 수행 속도가 매우 빠름
• 중기 스케줄러
  • 과도하게 많은 프로세스들을 메모리에 올려 성능 저하가 발생하는 경우를 해결하기 위해 메모리에 적재된 프로세스의 수를 조절하는 역할 수행
  • 프로세스 당 메모리 할당량이 적어지면 디스크 I/O가 빈번히 발생하여 성능 저하가 발생하기 때문에 일부 프로세스의 메모리 영역을 디스크의 swap 영역으로 옮기는 swap out 발생
  • 중지 준비란 ready 상태의 프로세스가 swap out 하는 것, 봉쇄 중지란 waiting(blocked) 상태의 프로세스가 swap out 하는 것

스케줄링 알고리즘

스케줄링 알고리즘이란 ready queue에 있는 ready 상태인 프로세스들 중 어떤 프로세스에 CPU를 할당하여 running 상태로 만들지 결정하는 것에 사용되는 알고리즘이다.

선점형, 비선점형이 존재한다.

• 선점형 스케줄링
  • ready 상태인 프로세스가 running 상태인 프로세스보다 우선순위가 높아지면 context switching 발생
• 비선점형 스케줄링
  • 프로세스가 running 상태가 되면 terminated 혹은 waiting(blocked) 상태가 되기 전까지 계속하여 CPU 할당

OS는 다음과 같은 스케줄링 알고리즘들을 사용한다.

• FCFS(First-Come, Firsy-Served) Scheduling
  • 비선점형 스케줄링
  • CPU를 먼저 요청하는 프로세스가 먼저 running 상태가 되는 것
  • queue를 사용하여 쉽게 구현 가능
• SJF(Simple Job First) Scheduling
  • 비선점형 스케줄링
  • 가장 작은 next CPU burst를 가진 프로세스에 우선적으로 CPU를 할당
  • 최소의 평균 대기시간을 가지지만 next CPU burst를 예측하기 힘듦
  • 프로세스 실행 중 더 작은 next CPU burst를 가진 새로운 프로세스가 들어와도 기다려야 하는 단점 존재
• SRT(Shortest Remaining Time) Scheduling
  • 선점형 스케줄링 (SJF의 선점형 버전)
  • SJF의 단점을 보완하기 위해 등장
  • running 상태인 프로세스보다 더 작은 next CPU burst를 가진 새로운 프로세스가 등장하면 context switching 발생
• RR(Round Robin) Scheduling
  • 선점형 스케줄링
  • time quantum (time slice)라고 불리는 작은 단위의 시간 설정
  • ready queue의 한 프로세스에 한 번의 time quantum 동안 CPU 할당
  • CPU burst가 시간 할당량을 초과하면 프로세스는 ready queue로 되돌아감
• Priority Scheduling
  • 선점형, 비선점형 스케줄링
  • 가장 우선순위가 높은 프로세스 먼저 CPU 할당
  • 선점형은 running 상태인 프로세스보다 우선순위가 더 높은 프로세스가 등장하면 context switching
  • 우선순위가 낮은 프로세스는 CPU를 할당받지 못하는 기아 상태(starvation), 무한 봉쇄 발생(indefinite blocking)
  • 노화(Aging)로 오래 대기하는 프로세스의 우선순위를 높여 해결
• Priority with RR Scheduling
  • Priority 스케줄링을 사용하고, 우선순위가 같은 프로세스는 RR 스케줄링을 사용
• MLQ(Multilevel Queue) Scheduling
  • 
  • 어떤 프로세스냐에 따라서 여러 종류의 queue 사용
  • 예를 들어 interactive는 batch보다 높은 우선순위를 가짐
  • 이때 interactive는 foreground queue, batch는 background queue
  • 각 queue는 서로 다른 스케줄링 알고리즘 사용 가능
• MFQ(Multilevel Feedback Queue) Scheduling
  • 
  • 새로운 프로세스는 모두 낮은 우선순위의 첫번째 queue에 들어감, 가장 하위 queue는 FCFS
  • RR 스케줄링으로 동작하여 running 중 time quantum 지나면 다시 낮은 우선순위 queue에 들어감
  • 노화(Aging)을 사용하여 너무 오래 대기하는 프로세스는 높은 우선순위 queue로 이동