스케쥴링 알고리즘

프로세스(process)

• 프로세스의 실행을 관리하는 주체는 CPU다.
• 작업, task, job이라는 용어로 사용되기도 함
• 메모리에 올려져서, 실행중인 프로그램

응용프로그램

• 응용프로그램 ≠ 프로세스
  • 여러개의 프로세스로 이뤄어질 수 있음
• 하나의 응용 프로그램은 여러 개의 프로세스가 상호작용을 하면서 실행 됨
• C/C++ 하나로 만들면 하나의 프로세스 이곘지만 보통 이러진 않음

스케쥴러

• 프로세스 실행을 관리한다.

스케쥴링 알고리즘

• 어느 순서대로 프로세스를 실행시킬까?
• 목표
  • 시분할 시스템 예 : 프로세스 응답 시간을 가능한 짧게 하는것 (대기시간을 짧게하자)
  • 멀티 프로그래밍 예 : CPU활용도를 최대로 높여서, 프로세스를 빨리 실행

FIFO

• 프로세스가 저장매체를 읽는 다든지, 프린팅을 한다든지 하는 작업 없이, 쭉 CPU를 처음부터 끝까지 사용한다고 가정
• 가장 간단한 스케쥴러
• FCFS(First Come First Seved)라고도 함
• 자료구조 Queue와 같다

최단 작업 우선(SJF)

• SJF (Shotrtest Job First)스케쥴러

• 가장 프로세스 실행 시간이 짧은걸 먼저 실행 시킨다.

• FIFO보다 응답 시간이 짧을 수 있다.

• 큰 실행 시간을 요구하는 프로세스 보다 총 시간은 빠를 수 있겠지만 프로세스 마다 실행 시간을 알아야 한다.

• 효율성을 극단적으로 고려했기 때문에 버스트 시간이 긴 프로세는 계속 뒤로 밀린다.

  >  CPU가 하나의 프로세스를 처리하여 완료하는데 걸리는 시간을 CPU버스트 시간이라고 한다.

우선순위 기반 스케쥴러(Priority-Based )

• 정적 우선순위
  • 프로세스마다 우선순위를 미리 지정
  • ex) 웹 브라우저는 높고 카카오톡읕 낮게
• 동적 우선순위
  • 스케쥴러가 상황에 따라 우선순위를 동적으로 변경
  • CPU에서 가장 최근에 실행된 프로세스 일수록 우선 순위가 높도록 스케쥴러가 알아서 관리해줌
• 우선순위가 같다면 FIFO 스케쥴링을 한다.
• SJF도 버스트 시간이 짧을수록 우선순위가 높은 알고리즘이라고 할 수 있다.
• 무기한 봉쇄( Indefinite Blocking)이라고 우선순위가 높은 프로세스가 계속 유입되어 우선순위가 낮은 프로세스가 계속 뒤로 밀리는 현상이 발생 할 수 있다.
  • 프로세스 aging에 따라서 대기한 시간에 따라 우선순위를 높여줌 으로서 해결 할 수 있다.

Round Robin (RR)

• 현대적인 스케쥴링 알고리즘

• 특정 시간동안(Time Quantum) 실행을 하다 끝나지 않으면 queue구조의 맨뒤로 다시 보냄

  > 실행 최소 단위 시간을 Time Quantum 혹은 Time Slice라고 한다.

• 시분할 시스템을 기본으로 함

• 버스트 시간이 각기 다른 복잡한 경우에 효율적이다.

• 할당 시간이 너무 크면 FIFO와 다를바가 없고 너무 작으면 Context switching(아래 있음)이 너무 잦아 Overhead가 발생한다(배보다 배꼽이 더커짐)

쉬어가기

• RealTime OS(RTOS)
  • 응용 프로그램 실시간 성능 보장을 목표로 하는 OS
  • 정확하게 프로그램 시작, 완료 시간을 보장
  • 공정같이 정확한 시간이 요구되는 경우 사용됨
• General Purpose OS(GPOS)
  • 프로세스 실행 시간에 민감하지 않고 일반적인 목적으로 사용되는 OS
  • Window, Linux등