[Computer Science][제로베이스 ]-운영체제 - 프로세스와 스케줄러의 이해 - 스케줄링 알고리즘의 기본

제로베이스 컴퓨터 공학자 따라잡기 온라인 완주반 강의를 듣고 정리한 포스팅

• Process란?
  • 실행 중인 프로그램을 프로세스라고 한다.
  • 메모리에 올려져서 , 실행 중인 프로그램이다.
  • 작업 , task, job 이라는 용어와 혼용되어 사용된다
  • 응용프로그램 ≠ 프로세스
    • 응용프로그램은 여러 개의 process로 이루어질 수 있다.
    • 하나의 프로그램은 여러 개의 process가 상호작용을 하면서 실행될 수도 있다. (unix 철학)
    • 예를 들어, 간단한 C++ 프로그램을 만든다면 하나의 프로세스이지만, 여러 프로그램을 만들어서, 서로 통신하면서 프로그램을 작성할 수도 있다 (IPC 기법)
• 스케줄러와 프로세스
  • 프로세스의 실행은 스케줄러에 의해 관리된다.
  • 스케줄러가 스케줄 하는 단위가 프로세스이다.'
• 스케줄링 알고리즘
  • 스케줄링 알고리즘은 "목표"에 기반하여 스케줄링 알고리즘이 나온다.
    • 시분할 시스템 : 프로세스 응답을 가능한 짧게 스케줄링해야 한다.
    • 멀티프로그래밍 : CPU의 활용도를 최대한 높여서 프로세스를 빨리 실행하는 것이 목표이다.
• FIFO Scheduler
  • 배치 처리 시스템과 유사한 가장 간단한 스케줄러이다.
  • First Come First Served 스케줄러이다.
  • Firt-In-Firt-Out을 하는 QUEUE의 메커니즘과 같다.
• FIFO 스케줄러는 작업이 CPU를 처음부터 끝까지 사용한다는 가정을 한다

그림출처

• 위의 표에서 Burst Time은 CPU 자원을 많이 요구하는 작업이다. (I/O burst는 I/O의 사용이 많은 작업이다.)

위의 표를 보면 P1, P2, P3가 차례대로 들어오고, Burst Time은 24,3,3이다.

Waiting Time을 살펴보면, P1은 0, P2는 P1이 끝나는 기점인 24, P3은 27에서 실행이 된다. 이를 평균으로 구해보면 Waiting 시간은 (0+24+27) /3 = 17이 나온다.

전체적인 Waiting Time이 증가되는 것을 Convoy Effect라고 한다.

• 최단 작업 우선 스케줄러 (SJF)
  • Shortest Job First의 약자로, 가장 실행 시간이 짧은 프로세스부터 먼저 실행을 시키는 알고리즘이다.
  • 실행시간이 긴 프로세스 때문에 나머지 process가 대기하지 않아도 되기 때문에, FIFO 보다는 응답 시간이 짧을 수도 있다.
  • 단점으로는, 실행시간을 다 알 수가 없다는 것이 단점이다.

    

SJF는 CPU Burst Time이 적은 것부터 수행한다.

위의 표를 보면 CPU burst time이 가장 작은 P4가 먼저 들어오고, P1, P3, P2의 순서대로 들어오고 있다.

Waiting Time을 살펴보면, 작업의 순서대로 0,3,9,16 ㅇ이도 이를 평균으로 구해보면 Waiting 시간은 7이 나온다.

• 우선순위 기반 스케줄러 (Priority-Based Scheduler)
  • 정적 우선순위 : 프로세스마다 우선 순위를 미리 지정한다. ⇒ 현실적으로 쉽지 않다.
  • 동적 우선순위 : 스케줄러가 상환에 따라 우선순위를 동적으로 변경한다.
    • 예를 들면, 실행한 지 오래된 process인 경우에는 우선순위가 낮다. 만약 CPU burst time이 된다면 SJF도 우선순위 스케줄링 알고리즘이라고 할 수 있다.
  • 만약, 우선순위가 계속 밀리다가 계속해서 cpu를 할당 받지 못하게 되면, Infinite blocking 상태가 된다. (이러한 문제는 Aging이라는 방법을 사용하여 해결한다)

아래의 그림은 FIFO , SJF , Priority 스케줄러를 간단하게 비교한 그림이다. Prpcess에 Process 1, 2, 3이 있을 때, FIFO는 순서대로 실행을 하고, SJF는 괄호 안의 우선순위에 따라 실행을 한다. 마지막으로 Proority는 우선순위사 2,3,1인 경우 우선수위에 따라 실행을 하게 된다.

• Round Robin 스케줄러
  • 정해진 시간 후에 다른 Process를 시행하는 스케줄러
  • 시분할 시스템을 위해 설계된 알고리즘
  • 시간 할당량(Time quantum) 또는 시간 조각(Time Slice)이라는 작은 단위의 시간을 정의한다.
  • 스케줄러는 큐를 돌면서 시간 할당량 동안 하나의 프로세스에 CPU를 할당한다
  • 
  그림출처
• RealTmeOS(RTOS) 란?
  • 응용 프로그램 실시간 성능 보장을 목표로 하는 OS이다.
  • 프로그램 시작과 완료 시간을 정확하게 보장해야 한다.
  • 시간에 민감한 프로그램이 운영되어야 할 때 사용한다.
  • Hardware RTOS, Software RTOS가 있다.
• General Purpose OS(GPOS)
  • 프로세스 실행시간에 민감하지 않고, 일반적인 목적으로 사용되는 OS이다.
  • 주로 사용하는 Window, Linux 등이 있다.