[OS]Day5

Scheduling

Ready 상태에 있는 프로세스들 중 언제, 어떤 프로세스에게 CPU를 할당시킬 것인지 정하는 것

Scheduling을 통해 여러 프로세스를 왔다갔다하며 CPU를 최대로 활용할 수 있다.

scheduling은 Kernel Thread에서 실행된다.

 

Preemptive vs Non-Preemptive (선점형, 비 선점형 )

Preemptive: 스케줄러에 의해 실행 중인 프로세스의 CPU 할당을 헤제할 수 있다.

Non Preemptive: 프로세스가 작업을 마치고 릴리스될 때까지 CPU 할당을 유지한다.

 

CPU 스케줄링 결정

1. Running -> waiting (I/O 발생)
2. runnging -> ready (다른 프로세스 할당)
3. waiting -> ready (I/O가 끝남)
4. terminates 

1, 4 = Non preemptive = 실행 중이지 않기 때문에 선점이 필요없다.

2, 3 = preemptive or Non preemptive = 실행 중에 할당을 바꾸기 때문에 선점이 필요하다.

 

Context Switch

실행 중인 프로세스의 CPU 할당을 바꾸는 것

Scheduler에 의해 스위칭 대상이 결정되고, 디스패처에 의해 스위칭 된다.

 

Scheduling 고려사항

CPU Utilization: CPU가 놀지않게 최대한으로 사용해야한다.

Throughput: 단위 시간당 완료되는 프로세스의 수

Turnaround time: 프로세스가 도착한 시간부터 완료된 시간, 즉 하나의 프로세스를 처리하는데 걸리는 시간

waiting time: 프로세스가 Ready Queue에 있는 총 시간

Response time: 사용자가 작업을 요청한 후 첫 번째 응답을 받는 시간, 즉 사용자가 느끼는 지연 시간

 

 

Scheduling 방법

FCFS: First Come First Served

• 먼저 요청한 프로세스를 무조건 먼저 처리
• 먼저 실행한 프로세스의 실행 시간이 길다면 뒤에 있는 프로세스는 너무 오래 기다려야함 (대기 시간 이슈)

SJF: Shortest Job First

• 실행 시간이 가장 짧은 프로세스 먼저 처리
• 짧은 작업을 먼저 하므로 total process waiting time이 줄어듬
• 긴 프로세스가 있는 상황에 짧은 프로세스가 계속해서 들어온다면, 처리시간이 오래 걸리는 작업은 무한 대기를 할 수도 있다.

SRTF: shotest remaining time frist

• 남은 시간이 가장 작은 프로세스가 CPU를 선점하여 Preemptive로 처리.

RR: Round Robin

• 하나의 작업을 다 하는 것이 아닌 작업을 일정 시간 단위로 쪼개서 실행하는 시분할 처리
• 시간을 쪼개서 일정 시간(time quantum) 마다 프로세스를 전환하므로 preemptive이다.
• time quantum을 너무 작게 나누면 잦은 context switching에 의한 오버헤드가 크고, 너무 크게 나누면 FCFS에 가까워진다.

Priority-based: RR에 우선순위를 추가해서 사용

• RR 방식도 SJF처럼 starvation 문제가 발생할 수 있기 때문에 aging 방법을 사용
• 할당을 못 받는 시간이 지속됨에 따라 우선순위를 높여줘서 언젠가는 꼭 실행될 수 있도록 하는 방법

MLQ: Multi Level Queue

• 우선순위 별로 ready queue를 따로 주는 방법
• 우선순위가 가장 높은 큐에 작업이 계속 들어오면 하위 우선순위를 가진 큐에 있는 프로세스들이 Starvation 상태가 될 수 있다.
• 

MLFQ: Multi Level Feedback Queue

• quantum을 주고 할당받은 quantum 시간이 지나면 작업이 남아도 다음 큐로 이동하여 starvation 문제 해결

 

Real Time OS에서의 Scheduling

soft realtime: 작업의 조금 놓쳐도 괜찮다.

hard realtime: 작업을 반드시 deadline 안에 처리해야한다.