[CPU 스케줄링]

 

스케줄링은 한정된 컴퓨터 자원을 여러 작업에 효율적이고 공정하게 나눠주기 위해 꼭 필요한 메커니즘

스레드나 멀티프로세스 등의 다중 프로그래밍을 도입하는 의도는 결국

CPU유휴 시간을 줄여 활용률을 향상시키는데 목적이 있다.

 

 

다중 프로그래밍에서의 2가지 스케줄링

 

✔ 작업 스케줄링

처음에 혹은 프로세스가 종료될때마다 디스크 장치로부터 메모리에 올릴 작업을 선택한다.

 

 

✔  CPU 스케줄링

메모리에 적재된 작업 중 CPU에 실행시킬 프로세스를 선택하는 과정

 

 

CPU 스케줄링이 되는 상황들

1. 스레드가 시스템 호출 끝에 I/O 요청을 하여 블록될때 

- 스레드를 블록상태로 만들고 스케줄링 (레디큐에 있는 스레드 실행)

 

2. 스레드가 자발적으로 다른 스레드에게 실행을 양보할때 (yield)

커널은 현재 스레드를 준비 리스트에 넣고, 새로운 스레드를 선택한다.

 

3. 스레드의 타임 슬라이스가 초과되어 인터럽스 신호가 발생했을 때 

균등한 cpu 자원 사용 분배에 목적이 있다.

 

4. 더 높은 우선순위 스레드가 요청한 입출력 작업을 완료하여 인터럽스 신호가 발생했을 때

현재 스레드를 강제 중단시켜 준비큐에 넣고 높은 순위에 작업을 스케줄링

 

 

실행중인 스레드의 강제 중단에 따른 스케줄링

✔ 비선점 스케줄링 

현재 실행중인 스레드를 강제종료 하지 않고 cpu를 계속 점유

 

✔ 선점 스케줄링

현재 실행중인 스레드를 강제중단 시키고 다른 스레드를 실행한다.

 

현대 컴퓨터에서는 대부분 선점 스케줄링 방식을 채택한다.

 

기아 (starvation)

스레드가 스케줄링에서 선택되지 못한 채 오랫동안 준비리스트에 있는 상황

 

에이징 (aging)

기아의 해결책이다. 스레드가 준비 리스트에 머무르는 시간에 비례하여 스케줄링 순위를 높이는 기법이다.

 

 

 

기본적인 cpu 스케줄링 알고리즘들

 

1. FCFS (First-Come, First-Served)

 먼저 온 순서대로 처리 (선입선출)

• 간단하고 직관적인 방식.
• 프로세스가 CPU를 요청한 순서대로 실행.
• 비선점형(한 번 CPU 잡으면 끝날 때까지 독점)
• 기아가 발생하지 않음
• 효율이 낮음음

 단점: 짧은 작업이 긴 작업 뒤에 있으면 오래 기다릴 수 있음 → "Convoy effect"

 

2. SJF (Shortest Job First)

 실행 시간이 가장 짧은 작업을 먼저 실행

• 효율적인 방식: 평균 대기 시간을 최소화할 수 있음.
• 비선점형 버전과 선점형 버전(= SRTF)이 있음.
• 실행시간의 예측이 불가능하므로 현실에서는 거의 사용하지 않는다.
• 짧은 스레드가 계속오면 긴 실행시간을 가지는 스레드는 기아현상 발생 가능

선점형 SJF = SRTF (Shortest Remaining Time First)
→ 남은 실행 시간이 더 짧은 새 작업이 오면, 지금 실행 중인 작업을 뺏고 새 작업 실행

 단점:

• 실행 시간을 미리 알아야 함 (예측 어려움)
• 짧은 작업만 계속 선택되면 긴 작업은 무한 대기 → "기아(starvation)" 현상 발생 가능

 

3. Priority Scheduling

 우선순위가 높은 작업부터 실행

• 각 프로세스에 우선순위를 부여하고, 그에 따라 스케줄링
• 선점형/비선점형 모두 가능

 단점:

• 낮은 우선순위는 계속 밀릴 수 있음 (기아)
• 해결책: Aging 기법 (대기 시간이 길어질수록 우선순위 점점 높임)

 

4. Round Robin (RR)

 모든 작업에게 일정한 시간만큼 CPU를 순서대로 나눠줌

• 선점형 방식
• 각 프로세스에 "Time Quantum (시간 할당량)"을 줌
• 할당 시간 지나면 다음 프로세스로 넘어감

 장점: 공정함, 응답 속도 빠름 (멀티태스킹 환경에 적합)
 단점: Time quantum이 너무 작으면 → Overhead↑
타임슬라이스가 너무 크면 → FCFS랑 비슷해짐

 

5. Multilevel Queue Scheduling

-작업을 여러 큐로 분류해서 우선순위대로 처리

-프로세스 종류에 따라 큐를 분리해서 스케줄링

-큐마다 우선순위가 다르고, 큐 간에는 절대적인 우선순위를 가짐

-프로세스는 한 번 정해진 큐에 고정돼 있고, 다른 큐로 이동하지 않음

• 예: 인터랙티브 프로세스는 빠른 응답이 필요 → 높은 우선순위 큐
  배치 작업(백그라운드)은 낮은 우선순위 큐
• 각 큐는 독립적인 스케줄링 알고리즘 사용

 

큐 번호큐 이름우선순위스케줄링 방식

 

큐 번호	큐 이름	우선순위	스케줄링 방식
1	시스템/실시간 큐	높음	Round Robin
2	인터랙티브 큐	중간	Round Robin
3	백그라운드/배치 큐	낮음	FCFS

작동 방식

 

• 가장 높은 우선순위 큐에 작업이 있으면 그 큐만 처리
• 낮은 큐에 있는 프로세스는 상위 큐가 비어야 실행 가능
• 각 큐 내부는 독립적인 스케줄링 알고리즘으로 처리

 

 

6. Multilevel Feedback Queue

작업의 행동에 따라 큐를 바꿔가며 스케줄링

CPU를 많이 쓰면 우선순위가 낮은 큐로 내려가고, 짧게 쓰면 높은 큐로 올라가는 구조

• 위의 Multilevel Queue보다 유연함
• CPU를 많이 쓰는 작업은 아래로 내려가고, 짧게 쓰는 작업은 위로 올라감
• 우선순위 큐 구조 + 프로세스 이동 가능

 작동 방식

• 새 프로세스는 가장 높은 우선순위 큐에서 시작
• CPU를 오래 사용하면 → 아래 큐로 이동
• 대기 시간이 길거나, 짧은 CPU 사용 후 I/O 요청 시 → 위 큐로 다시 이동 가능