스케쥴링 알고리즘 기본

 

프로세스란? 

→ 실행 중인 프로그램은 프로세스라고 한다.

 

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

코드 이미지(바이너리) : 실행 파일 (ex.ELF format)

 

응용프로그램 != 프로세스 

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

 

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

 

간단한 C/C++ 프로그램을 만든다면 하나의 프로세스

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

 

스케쥴러와 프로세스

Q. 누가 프로세스를 관리 할까요? 

A. 스케쥴러 

→ 스케쥴러가 스케쥴링하는 단위가 프로세스

 

스케쥴링 알고리즘

Q.어느 순서대로 프로세스를 실행시킬까?

→ 여러개의 프로세스가 있는데 어떤 걸 어느 시점에 실행시켜야 하나? 

프로세스도 프로그램으로 작성되어 있다. 그래서 알고리즘이 필요.

어느시점에 프로세스를 교체할지 어느시점에 실행시킬지 등을 결정

 

스케쥴링 알고리즘의 목표 

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

멀티 프로그래밍 예 : CPU 활용도를 최대로 높혀서 프로세스를 빨리 실행

 

목표를 세우고 해당 목표에 기반해서 여러가지 스케줄링 알고리즘이 나올 수 있다.

 

1. FIFO 스케줄러

: 먼저 들어온 프로세스가 먼저 실행 (First in First out)

 

ex.

프로세스 1 : 1초 걸리는 프로세스

프로세스 2 : 3초 걸리는 프로세스

프로세스 3 : 1초 걸리는 프로세스

 

1-> 2 -> 3  순서대로 실행 요청

FIFO 스케줄러는 첫번째로 들어온 프로세스가 먼저 실행된다.

 

→ 프로세스가 저장매체를 읽거나 프린팅 하는 작업없이 쭉 CPU를 처음부터 끝까지 사용한다.

→ 가장 간단한 스케줄러(배치 처리 시스템)

→ FCFS ( First Come First Served ) 스케줄러  : 먼저 들어온 프로세스가 CPU에 먼저 올려져서 실행

 

2. 최단 작업 우선(SJF-Shortest Job First) 스케줄러

: 가장 프로세스 실행시간이 짧은 프로세스부터 먼저 실행 시키는 알고리즘

 

ex.

1번 프로세스가 제일 먼저 들어옴

 

FIFO 는 들어온 순서대로 실행

SJF 는 짧은 프로세스부터 실행

 

SJF 는 FIFO 보다는 응답시간이 더 짧을 수도 있다. 단, 실행 시간을 모르면 이용할 수 없다.

SJF는 짧은 프로세스 먼저 실행하기 때문에 큰 실행시간을 요하는 프로세스 때문에

나머지 프로세스가 딜레이 되는 경우가 없음.

 

 

Real Time OS(RTOS) : 응용프로그램 실시간 성능 보장을 목표로 하는 OS

• 정확하게 프로그램 언제 시작할지 언제 완료할지 시간을 보장 (공정 등에 사용)
• 시간에 민감한 프로세스들이 동작해야 되는 시스템에서 사용

 

General Purpose OS(GPOS) : 프로세스 실행시간에 민감하지 않고 일반적인 목적으로 사용되는 OS

ex. windows, Linux 등..

 

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

: 프로세스에 우선순위를 미리 매겨 놓는 것

 

• 정적 우선순위 : 프로세스마다 우선순위 미리 지정
• 동적 우선순위 : 스케줄러가 상황에 따라 우선순위 동적으로 지정

빨간색 글자는 정적으로 매겨진 우선순위. 숫자가 높을 수록 우선순위 높은 것임

 

4. Round Robin 스케줄러

프로세스가 들어온 순서대로 실행 

그러나, 특정시간 동안 다 실행이 되지 않으면 중단하고 맨 뒤로 보낸다. (중단된 프로세스는 준비 큐의 맨 뒤에 추가)

시분할 시스템을 기본으로 하고 있다. 

 

프로세스 1번은 1초 실행하고 끝나고 Queue 에서 없애고 

프로세스 2번은 3초를 실행해야하는데 시분할 시스템을 기반으로 하기 때문에 1초 후에 무조건 다른 프로세스인 프로세스 3번으로 바꿔줘야 한다. ( 2번은 Ready Queue 에 맨 뒤로 간다.) 

프로세스 3번도 1초만 실행하고 3번은 Ready Queue 에 맨 뒤로 간다. 

 

 

 

---

 

정리 

• FIFO(FCFS) 스케쥴링 알고리즘 (배치 처리 시스템)
• 최단 작업 우선(SJF) 스케쥴링 알고리즘 : 실행 시간이 짧은 프로세스 먼저 실행
• 우선순위 기반 스케쥴링 알고리즘 : 우선순위가 높은 프로세스 먼저 (정적 우선순위와 동적 우선순위)
•  Round Robin 스케쥴링 알고리즘 : 정해진 시간마다 실행 중인 프로세스 중단하고 준비 큐에 추가하고 다음 프로세스 실행 (시분할 시스템 기반)

 

 

 

제로베이스 컴퓨터 공학 전공자 따라잡기 강의 시청 후 정리한 내용입니다.