프로세스 스케줄링 알고리즘

프로세스란?

메모리에 올려져서 실행 중인 프로그램

 

프로세스라는 용어는 작업, task, job 이라는 용어와 혼용된다.

응용 프로그램이 프로세스는 아니며 응용 프로그램은 여러 개의 프로세스로 이루어질 수 있다.

 

하나의 응용 프로그램은 여러 개의 프로세스로(프로그램)가 상호작용을 하면서 실행될 수도 있다

여러 프로그램을 만들어서, 서로 통신하면서 프로그램을 작성할 수 있다 (IPC 기법)

 

스케줄러와 프로세스의 관계

누가 프로세스 실행을 관리할까 -> 스케줄러

스케줄러가 스케줄링 하는 단위 -> 프로세스

 

스케줄링 알고리즘

어느 순서대로 프로세스를 실행시킬까를 정하는 알고리즘

 

스케줄링 알고리즘의 목표의 예시

시분할 시스템: 프로세스 응답시간을 가능한 짧게

멀티 프로그래밍: cpu 활용도를 최대로 높게

 

스케줄링 알고리즘 종류

1. FIFO 스케줄러
   • 가장 간단한 스케줄러
   • 가장 먼저 들어온 프로세스 실행 (배치 처리 시스템)
   • FCFS (First Come First Served) 스케줄러
2. 최단 작업 우선(SJF) 스케줄러
   • SJF (Shortest Job First) 스케줄러
   • 가장 프로세스 실행시간이 짧은 프로세스부터 실행시키는 스케줄러
3. 우선순위 기반 ( Priority-Based )  스케줄러
   • 정적 우선순위 - 프로세스마다 우선순위를 미리 지정
   • 동적 우선순위 - 스케줄러가 상황에 따라 우선순위를 동적으로 변경
4. Round Robin 스케줄러
   1. FIFO 구조에서 프로세스 실행시 특정 시간이 지나면 프로세스가 끝나지 않아도 큐에 가장 뒤쪽으로 프로세스를 넘긴다
   2. 시분할 시스템을 기반으로 한다.

 

보너스

RealTime OS (RTOS)

응용 프로그램 실시간 성능 보장을 목표로 하는 OS

정확하게 프로그램 시작, 완료 시간을 보장

시간에 민감한 구조 (공정)

HardWare RTOS, Software RTOS

 

General Purpose OS (GPOS)

프로세스 실행시간에 민감하지 않고, 일반적인 목적으로 사용되는 OS

 

프로세스 상태와 스케줄링

프로세스 상태 기반 알고리즘

 

프로세스 상태를 스케줄러가 파악하고 있어야 cpu 활용도를 극대화 (멀티프로그래밍) 할 수 있다.

프로세스 생성 ( new )

프로세스 실행 가능( ready ): cpu에서 실행 가능한 상태 (대기상태)

실행 중 ( running ): 현재 cpu에서 실행중인 상태

대기 ( blocked ): 특정 이벤트 발생 대기 상태 (프린팅이 다 되거나 저장매체에서 파일을 읽은 행위가 다 끝나는 것을 기다리는 상태)

프로세스 종료 ( exit ) 

 

선점형 과 비선점형 스케줄러

선점형: 하나의 프로세스가 다른 프로세스 대신에 프로세서(CPU)를 차지할 수 있음

비선점형: 하나의 프로세스가 끝나지 않으면 다른 프로세스는 프로세서(CPU)를 차지할 수 없음

 

시분할 시스템에서 running 상태의 프로세스를 ready상태로 바꾸고 다음 프로세스를 실행 시키는 것을 선점형이라 한다.

비선점형의 경우 프로세스가 자체적으로 block 또는 exit 상태가 되어야지만 스케줄러가 다음 프로세스를 실행시킬 수 있다.

 

정리

1. FIFO(FCFS) 스케줄링 알고리즘 (배치 처리 시스템)
2. SJF 스케줄링 알고리즘 (최단 작업 우선)
3. 우선순위 기반 스케줄링 알고리즘 - 정적 우선순위, 동적 우선순위
4. Round Robin 스케줄링 알고리즘 - 시분할 시스템을 위한 기본 알고리즘 (선점형 스케줄러)
5. 비선점형의 경우 프로세스가 block 또는 exit 상태가 되기 전까지는 스케줄러가 개입할 수 없다.멀티 프로그래밍을 구현하기 위해 현대 운영체제는 기본적으로 선점형 스케줄러를 지원한다.
6. 실행중인 프로세스를 중단하고 다른 프로세스를 실행시키는 경우에 고려해야 할 부분이 많아 과거 선점형 스케줄러를 지원하지 못하는 경우가 있었기 때문에 선점형과 비선점형을 구분한다.
7. 비선점형의 경우 실행시간이 길지만 block 상태가 되지 않는 프로세스가 있는 경우 응답시간이 길어질 수 있다.
8. 스케줄링 알고리즘 조합
   • 아래와 같이 여러가지 알고리즘을 조합하여 스케줄링을 할 수 있다
   • 프로세스 상태를 확인하여 실행 가능한 프로세스를 실행시킨다 (프로세스 상태 기반)
   • 특정시간마다 Ready State인 프로세스를 확인한다 (시분할 기반)
   • Ready State에서 Running State로 변경시킬때 미리 정해둔 우선순위를 기반으로 변경시킨다(정적 우선순위 기반)
   • 실행 중인 프로세스를 선점하여 스케줄러가 상태를 변경 시킬 수 있다 (선점형 스케줄러)