[운영체제] 스케줄러 (Scheduler)

1. 스케줄러란?

: 단기, 중기, 장기스케줄러의 종류가 있으며, 스케줄링하기 위한 Queue에는 Job, Ready, Device Queue가 존재한다

 

2. 선점/비선점 스케줄러

- 선점형 스케줄링: 우선순위가 높은 프로세스가 추가된다면, 진행중인 프로세스를 중단하고 우선순위가 높은 프로세스 수행

- 비선점형 스케줄링: 우선순위가 높은 프로세스가 추가되더라도 현재 진행중인 프로세스 끝까지 진행

 

3. 스케줄링 방향

- Utilization↑: CPU의 일하는 시간

- Throughput↑: 단위 시간당 처리한 양

- Turnaround time↓: 프로세스 처리시간

- Waiting time↓:  Ready Queue에서 기다리는 시간

- Response time↓: 응답시간

 

4. 스케줄링의 종류

• FCFS(First Come First Served)
  1. FIFO 즉, Queue와 같은 형태
  2. 비선점형
  3. 처리시간이 긴 프로세스가 먼저 도착하면 효율성이 낮아진다

• SJF(Shortest Job First)
  1. 수행시간이 짧은 프로세스부터 처리
  2. 비선점형
  3. 처리시간이 긴 프로세스의 경우, Starvation 발생 가능
• SRT(Shortest Remaining Time first)
  1. 프로세스가 도착할 때 마다 스케줄링
  2. 선점형
  3. 처리시간이 많이 남은 프로세스의 경우, Starvation 발생 가능
• Priority
  1. 우선순위가 높은 프로세스부터 처리
  2. 선점형: 더 높은 우선순위를 가진 프로세스가 들어오면 중단 후, 해당 프로세스 처리
  3. 비선점형: 더 높은 우선순위를 가진 프로세스가 들어와도 현재 프로세스 처리
  4. 우선 순위가 낮은 프로세스의 경우, Starvation 발생 가능. Aging으로 해결 가능
• RR
  1. Time quantum이라는 동일 할당 시간을 부여하여 순차적으로 돌아가면서 수행
  2. FCFS의 선점형
  3. TQ가 크다면 FCFS와 같아지고 TQ가 작다면 Context Switching이 너무 자주 발생한다

5. 디스크 스케줄링

 

순번: 1  2  3  4  5  6  7  8  9  10
트랙: 16 11 8  17 2  1  10  9  7  13
트랙의 구간: [0,20]

1) FCFS(First Come First Service)

처리 방법: 들어온 순서대로 처리

처리 순서: 16 → 11 → 8 → 17 → 2→ 1→ 10 → 9 → 7 → 13

헤드 이동 거리: 5+3+9+15+1+9+1+2+6 = 51

 

2) SSTF(Shortest Seek Time First)

처리 방법: 현재 헤드와 가장 가까운 트랙부터 처리. 단, 거리가 같은 경우 먼저 온 트랙부터 처리

처리 순서: 16 → 17 → 13 → 11 → 10 → 9 → 8 → 7 → 2 → 1

헤드 이동 거리: 1+4+2+1+1+1+1+5+1 = 17

 

3) SCAN

처리 방법: 헤드가 움직이는 방향으로 한쪽 끝으로 이동 후, 방향 전환. 동일 트랙을 연속적으로 받으면 아사 현상 발생

처리 순서: 16 → 13 → 11 → 10 → 9 → 8 → 7 → 2 → 1 → 0 → 17

헤드 이동 거리: 3+2+1+1+1+1+5+1+1+17 = 33

 

4) C-SCAN(Circular-SCAN)

처리 방법: SCAN과 유사하지만, 한쪽 끝에 닿으면 헤드를 반대편 끝으로 작업 없이 이동시킨다(방향은 계속 한쪽 방향)

처리 순서:  16 → 13 → 11 → 10 → 9 → 8 → 7 → 2 → 1 → 0 →20 → 17

헤드 이동 거리: 3+2+1+1+1+1+5+1+1+20+3 = 39

 

5) LOOK

처리 방법: 움직이는 방향으로 더 이상 처리할 트랙이 없으면 방향전환

처리 순서:  16 → 13 → 11 → 10 → 9 → 8 → 7 → 2 → 1 → 17

헤드 이동 거리: 3+2+1+1+1+1+5+1+16 = 31

 

6) C- LOOK(Circular LOOK)

처리 방법: 움직이는 방향으로 더 이상 처리할 트랙이 없으면 헤드를 반대 끝으로 작업없이 이동

처리 순서:  16 → 13 → 11 → 10 → 9 → 8 → 7 → 2 → 1  → 17

헤드 이동 거리: 3+2+1+1+1+1+5+1+16 = 31

 

[참고 블로그]

- starrykss.tistory.com/977