πŸ¦• κ³΅λ£‘μ±…μœΌλ‘œ μ •λ¦¬ν•˜λŠ” 운영체제 Ch.5

Process Scheduling

μš΄μ˜μ²΄μ œκ°€ μ–΄λ–€ ν”„λ‘œμ„ΈμŠ€λ₯Ό ν”„λ‘œμ„Έμ„œμ— ν• λ‹Ήν•  것인가 μ •ν•˜λŠ” ν”„λ‘œμ„ΈμŠ€ μŠ€μΌ€μ€„λ§(Process scheduling)에 λŒ€ν•΄ λ‹€λ£¨λŠ” 챕터닀. FCFS, SJF, RR λ“± λ‹€μ–‘ν•œ ν”„λ‘œμ„ΈμŠ€ μŠ€μΌ€μ€„λ§μ— λŒ€ν•΄ μ†Œκ°œν•œλ‹€.

Scheduling Criteria

μš΄μ˜μ²΄μ œκ°€ ν”„λ‘œμ„ΈμŠ€λ₯Ό ν”„λ‘œμ„Έμ„œμ— ν• λ‹Ήν•˜λŠ” 것을 λ””μŠ€νŒ¨μΉ˜(Dispatch)라고 ν•œλ‹€. (μ΄λ•Œ ν”„λ‘œμ„ΈμŠ€ μƒνƒœκ°€ readyμ—μ„œ running으둜 바뀐닀.) 그리고 μš΄μ˜μ²΄μ œκ°€ λ ˆλ”” 큐(Ready queue)에 μžˆλŠ” ν”„λ‘œμ„ΈμŠ€λ“€ μ€‘μ—μ„œ μ–΄λ–€ ν”„λ‘œμ„ΈμŠ€λ₯Ό λ””μŠ€νŒ¨μΉ˜ν•  것인가 μ •ν•˜λŠ” 것이 ν”„λ‘œμ„ΈμŠ€ μŠ€μΌ€μ€„λ§(Process scheduling)이닀.

μŠ€μΌ€μ€„λ§ μ•Œκ³ λ¦¬μ¦˜μ—λŠ” λŒ€ν‘œμ μœΌλ‘œ FCFS, SJF, SRF, RR λ„€ 가지 방식이 있고, μ•Œκ³ λ¦¬μ¦˜μ„ 평가할 λ•ŒλŠ” μˆ˜ν–‰ μ‹œκ°„(Burst time)κ³Ό CPU μ‚¬μš©λŸ‰(CPU utilization), λ‹¨μœ„ μ‹œκ°„ λ‹Ή 끝마친 ν”„λ‘œμ„ΈμŠ€μ˜ 수(Throughput), ν•˜λ‚˜μ˜ ν”„λ‘œμ„ΈμŠ€κ°€ λ ˆλ”” νμ—μ„œ λŒ€κΈ°ν•œ μ‹œκ°„λΆ€ν„° μž‘μ—…μ„ 마칠 λ•ŒκΉŒμ§€ κ±Έλ¦¬λŠ” μ‹œκ°„(Turnaround time), ν”„λ‘œμ„ΈμŠ€κ°€ λ ˆλ”” νμ—μ„œ λŒ€κΈ°ν•œ μ‹œκ°„(Wating time), ν”„λ‘œμ„ΈμŠ€κ°€ 처음으둜 CPUλ₯Ό ν• λ‹Ήλ°›κΈ°κΉŒμ§€ κ±Έλ¦° μ‹œκ°„(Response time)을 κΈ°μ€€μœΌλ‘œ ν•œλ‹€.

선점(Preemptive) 방식과 비선점(Non-Preemptive) λ°©μ‹μœΌλ‘œ λ‚˜λ‰œλ‹€. 선점 μŠ€μΌ€μ€„λ§μ€ μš΄μ˜μ²΄μ œκ°€ κ°•μ œλ‘œ ν”„λ‘œμ„ΈμŠ€μ˜ μ‚¬μš©κΆŒμ„ ν†΅μ œν•˜λŠ” 방식이고, 비선점 μŠ€μΌ€μ€„λ§μ€ ν”„λ‘œμ„ΈμŠ€κ°€ 슀슀둜 λ‹€μŒ ν”„λ‘œμ„ΈμŠ€μ—κ²Œ 자리λ₯Ό λ„˜κ²¨μ£ΌλŠ” 방식이닀. 즉, 선점 μŠ€μΌ€μ€„λ§ λ°©μ‹μ—μ„œλŠ” CPU에 ν”„λ‘œμ„ΈμŠ€κ°€ ν• λ‹Ήλ˜μ–΄ μžˆμ„ λ•Œλ„ μš΄μ˜μ²΄μ œκ°€ κ°œμž…ν•΄ λ‹€λ₯Έ ν”„λ‘œμ„ΈμŠ€μ—κ²Œ CPUλ₯Ό ν• λ‹Ήν•  수 μžˆλ‹€.

FCFS (First-Come, First-Served)

  • λ¨Όμ € λ“€μ–΄μ˜¨ ν”„λ‘œμ„ΈμŠ€λ₯Ό λ¨Όμ € ν”„λ‘œμ„Έμ„œμ— ν• λ‹Ήν•˜λŠ” 방식이닀.
  • Queue의 FIFO(First-In First-Out)와 λ™μΌν•˜λ‹€.
  • κ΅¬ν˜„μ΄ μ‰¬μ›Œμ„œ κ°„λ‹¨ν•œ μ‹œμŠ€ν…œμ— 자주 μ‚¬μš©λœλ‹€.
  • ν”„λ‘œμ„ΈμŠ€ 처리 μˆœμ„œμ— 따라 μ„±λŠ₯이 크게 λ‹¬λΌμ§ˆ 수 μžˆλ‹€.
  • μˆ˜ν–‰ μ‹œκ°„μ΄ 큰 ν”„λ‘œμ„ΈμŠ€κ°€ λ¨Όμ € λ“€μ–΄μ˜€λ©΄ κ·Έ 뒀에 λ“€μ–΄μ˜¨ ν”„λ‘œμ„ΈμŠ€λ“€μ΄ λΆˆν•„μš”ν•˜κ²Œ 였랜 μ‹œκ°„μ„ κΈ°λ‹€λ¦¬κ²Œ λ˜λŠ” 콘보이 효과(Convoy effect)κ°€ λ°œμƒν•œλ‹€.
  • λ¨Όμ € 온 ν”„λ‘œμ„ΈμŠ€κ°€ 끝날 λ•ŒκΉŒμ§€ μš΄μ˜μ²΄μ œκ°€ κ°œμž…ν•˜μ§€ μ•ŠλŠ” 비선점 μŠ€μΌ€μ€„λ§ 방식이닀.
Process Burst time Response time Turnaround time Waiting time
P1 9 0 9 0
P2 1 9 10 9
P3 1 10 11 10
+----+----+----+----+----+----+----+----+----+----+----+
|                     P1                     | P2 | P3 |
+----+----+----+----+----+----+----+----+----+----+----+
0                                            9    10   11

Average wating time = (0 + 9 + 10) / 3 = 6.33

P1, P2, P3 ν”„λ‘œμ„ΈμŠ€κ°€ λ“€μ–΄μ˜¨ μˆœμ„œλŒ€λ‘œ 할당됐닀. P2, P3λŠ” μˆ˜ν–‰ μ‹œκ°„μ΄ μ§§μŒμ—λ„ P1이 끝날 λ•ŒκΉŒμ§€ κΈ°λ‹€λ¦¬κ²Œ λ˜μ–΄ 평균 λŒ€κΈ° μ‹œκ°„μ΄ λŠ˜μ–΄λ‚¬λ‹€.

SJF (Shortest Job First)

  • ν”„λ‘œμ„ΈμŠ€μ˜ μˆ˜ν–‰ μ‹œκ°„μ΄ 짧은 μˆœμ„œμ— 따라 ν”„λ‘œμ„Έμ„œμ— ν• λ‹Ήν•œλ‹€.
  • FCFSμ—μ„œ λ°œμƒν•˜λŠ” 콘보이 효과λ₯Ό ν•΄κ²°ν•  수 μžˆλ‹€.
  • 졜적 μ•Œκ³ λ¦¬μ¦˜μ΄μ§€λ§Œ μˆ˜ν–‰ μ‹œκ°„μ„ μ •ν™•νžˆ μ•Œ 수 μ—†λ‹€. (μ•žμ„œ μ²˜λ¦¬ν•œ ν”„λ‘œμ„ΈμŠ€λ“€μ˜ 기둝을 보고 μΆ”μΈ‘ν•œλ‹€.)
  • λ²„μŠ€νŠΈ μ‹œκ°„μ΄ 큰 ν”„λ‘œμ„ΈμŠ€λŠ” 계속 λ’€λ‘œ λ°€λ €λ‚˜λŠ” κΈ°μ•„(Starvation)κ°€ λ°œμƒν•œλ‹€.
  • λ²„μŠ€νŠΈ μ‹œκ°„μ΄ 짧은 ν”„λ‘œμ„ΈμŠ€κ°€ 끝날 λ•ŒκΉŒμ§€ μš΄μ˜μ²΄μ œκ°€ κ°œμž…ν•˜μ§€ μ•ŠλŠ” 비선점 μŠ€μΌ€μ€„λ§ 방식이닀.
Process Burst time Response time Turnaround time Waiting time
P1 6 3 9 3
P2 8 16 24 16
P3 7 9 16 9
P4 3 0 3 0
+----+----+----+----+----+----+----+----+----+----+----+----+----+----+----+----+----+----+----+----+----+----+----+----+
|      P4      |              P1             |                P3                |                   P2                  |
+----+----+----+----+----+----+----+----+----+----+----+----+----+----+----+----+----+----+----+----+----+----+----+----+
0              3                             9                                  16                                      24

Average wating time = (3 + 16 + 9 + 0) / 4 = 7

ν”„λ‘œμ„ΈμŠ€μ˜ μˆ˜ν–‰ μ‹œκ°„μ„ μ •ν™•νžˆ μ˜ˆμΈ‘ν–ˆλ‹€λŠ” κ°€μ •ν•˜μ—, μˆ˜ν–‰ μ‹œκ°„μ΄ 짧은 μˆœμ„œλŒ€λ‘œ ν”„λ‘œμ„Έμ„œμ— 할당됐닀.

SRF (Shortest Remaining Time First)

  • ν”„λ‘œμ„ΈμŠ€μ˜ 남은 μˆ˜ν–‰ μ‹œκ°„μ΄ 짧은 μˆœμ„œμ— 따라 ν”„λ‘œμ„Έμ„œμ— ν• λ‹Ήν•œλ‹€.
  • SJFμ—μ„œ λ°œμƒν•˜λŠ” κΈ°μ•„ 문제λ₯Ό ν•΄κ²°ν•  수 μžˆλ‹€.
  • μˆ˜ν–‰ 쀑 λ‹€λ₯Έ ν”„λ‘œμ„ΈμŠ€λ³΄λ‹€ 남은 μˆ˜ν–‰ μ‹œκ°„μ΄ 적어지면 μš΄μ˜μ²΄μ œκ°€ κ°œμž…ν•΄ 자리λ₯Ό λ°”κΎΈλŠ” 선점 μŠ€μΌ€μ€„λ§ 방식이닀.
Process Arrival time Burst time Response time Turnaround time Waiting time
P1 0 8 0 17 9
P2 1 4 1 5 0
P3 2 9 17 24 15
P4 3 5 5 7 2
+----+----+----+----+----+----+----+----+----+----+----+----+----+----+----+----+----+----+----+----+----+----+----+----+----+----+
| P1 |         P2        |           P4           |                P1                |                     P3                     |
+----+----+----+----+----+----+----+----+----+----+----+----+----+----+----+----+----+----+----+----+----+----+----+----+----+----+
0    1                   5                        10                                 17                                           26

Average wating time = (9 + 0 + 15 + 2) / 4 = 26

P1이 μˆ˜ν–‰λ˜λ˜ 쀑, 1ms에 P2κ°€ λ“€μ–΄μ™”λ‹€. μ΄λ•Œ P1의 남은 μˆ˜ν–‰ μ‹œκ°„μ€ 7ms이고, P2의 남은 μˆ˜ν–‰ μ‹œκ°„μ€ 4ms이기 λ•Œλ¬Έμ— μš΄μ˜μ²΄μ œκ°€ κ°œμž…ν•΄ P1의 μˆ˜ν–‰μ„ μ€‘λ‹¨ν•˜κ³  P2λ₯Ό ν”„λ‘œμ„Έμ„œμ— ν• λ‹Ήν•œλ‹€. P2κ°€ ν”„λ‘œμ„Έμ„œμ— ν• λ‹Ήλœ 사이, 2ms에 P3κ°€ λ“€μ–΄μ™”μœΌλ‚˜ P2의 남은 μˆ˜ν–‰ μ‹œκ°„μ€ 3ms이고, P3의 남은 μˆ˜ν–‰ μ‹œκ°„μ€ 9ms이기 λ•Œλ¬Έμ— ν”„λ‘œμ„Έμ„œλŠ” P2λ₯Ό 계속 μˆ˜ν–‰ν•œλ‹€. μ΄μ–΄μ„œ 3ms일 λ•Œ P4κ°€ λ“€μ–΄μ™”μ§€λ§Œ P2의 남은 μˆ˜ν–‰ μ‹œκ°„μ€ 2ms이고, P4의 남은 μˆ˜ν–‰ μ‹œκ°„μ€ 5ms이기 λ•Œλ¬Έμ— μ—¬μ „νžˆ P2κ°€ μˆ˜ν–‰λœλ‹€. 이후에도 같은 λ°©μ‹μœΌλ‘œ ν”„λ‘œμ„ΈμŠ€μ˜ μž‘μ—…μ΄ λλ‚˜κ±°λ‚˜ μƒˆλ‘œμš΄ ν”„λ‘œμ„ΈμŠ€κ°€ λ“€μ–΄μ˜¬ λ•Œλ§ˆλ‹€ 남은 μˆ˜ν–‰ μ‹œκ°„μ„ 비ꡐ해 자리λ₯Ό λ°”κΏ”μ€€λ‹€.

RR (Round Robin)

  • 일정 μ‹œκ°„ ν• λ‹ΉλŸ‰(Time quantum) λ‹¨μœ„λ‘œ μ—¬λŸ¬ ν”„λ‘œμ„ΈμŠ€λ₯Ό λ²ˆκ°ˆμ•„κ°€λ©° ν”„λ‘œμ„Έμ„œμ— ν• λ‹Ήν•œλ‹€.
  • μ‹œμŠ€ν…œμ˜ time-sharingκ³Ό 같은 방식이닀.
  • λ°˜μ‘μ„±μ΄ μ’‹λ‹€.
  • 주둜 μš°μ„ μˆœμœ„ μŠ€μΌ€μ€„λ§(Priority scheduling)κ³Ό κ²°ν•©ν•΄ ν”„λ‘œμ„ΈμŠ€μ˜ μ‹œκ°„ ν• λ‹ΉλŸ‰μ„ μ‘°μ ˆν•˜λŠ” λ°©μ‹μœΌλ‘œ ν™œμš©ν•œλ‹€.
  • μ‹œκ°„ ν• λ‹ΉλŸ‰μ— 따라 μš΄μ˜μ²΄μ œκ°€ 계속 κ°œμž…ν•˜λŠ” 선점 μŠ€μΌ€μ€„λ§ 방식이닀.
Process Burst time Response time Turnaround time Waiting time
P1 15 0 19 4
P2 2 3 5 3
P3 2 5 7 5
Time quantum = 3ms

+----+----+----+----+----+----+----+----+----+----+----+----+----+----+----+----+----+----+----+
|      P1      |    P2   |    P3   |      P1      |      P1      |      P1      |      P1      |
+----+----+----+----+----+----+----+----+----+----+----+----+----+----+----+----+----+----+----+
0              3         5         7              10             13             16             19

Average wating time = (4 + 3 + 5) / 3 = 4

λͺ¨λ“  ν”„λ‘œμ„ΈμŠ€λ“€μ΄ λ™μΌν•˜κ²Œ 3msμ”© ν”„λ‘œμ„ΈμŠ€μ— ν• λ‹Ήλœλ‹€. P2와 P3의 경우 μˆ˜ν–‰ μ‹œκ°„μ΄ 2ms이기 λ•Œλ¬Έμ— ν• λ‹Ήλœ 3msλ₯Ό λͺ¨λ‘ μ‚¬μš©ν•˜μ§€ μ•Šμ•˜λ‹€.

Priority Scheduling

  • νŠΉμ • κΈ°μ€€μœΌλ‘œ ν”„λ‘œμ„ΈμŠ€μ—κ²Œ μš°μ„ μˆœμœ„λ₯Ό λΆ€μ—¬ν•΄ μš°μ„ μˆœμœ„μ— 따라 ν”„λ‘œμ„Έμ„œμ— ν• λ‹Ήν•œλ‹€.
  • ν”„λ‘œμ„ΈμŠ€λ₯Ό 에이징(Aging)ν•΄μ„œ 였래 λŒ€κΈ°ν•œ ν”„λ‘œμ„ΈμŠ€μ˜ μš°μ„ μˆœμœ„λ₯Ό λ†’μ΄λŠ” λ°©μ‹μœΌλ‘œ μ‚¬μš©λœλ‹€.
  • SRF의 경우 남은 μˆ˜ν–‰ μ‹œκ°„μ„ κΈ°μ€€μœΌλ‘œ μš°μ„ μˆœμœ„λ₯Ό λΆ€μ—¬ν•œλ‹€κ³  ν•  수 μžˆλ‹€.
  • λ‹€λ₯Έ μŠ€μΌ€μ€„λ§ μ•Œκ³ λ¦¬μ¦˜κ³Ό κ²°ν•©ν•΄ μ‚¬μš©ν•  수 μžˆμœΌλ―€λ‘œ 선점, 비선점 λͺ¨λ‘ κ°€λŠ₯ν•˜λ‹€.
Process Priority Burst time Response time Turnaround time Waiting time
P1 3 5 4 9 4
P2 1 1 0 1 0
P3 4 2 9 11 9
P4 5 1 11 12 11
P5 2 3 1 4 1
+----+----+----+----+----+----+----+----+----+----+----+----+
| P2 |      P5      |           P1           |    P3   | P4 |
+----+----+----+----+----+----+----+----+----+----+----+----+
0    1              4                        9         11   12

Average wating time = (4 + 0 + 9 + 11 + 1) / 5 = 5

μš°μ„ μˆœμœ„μ— 따라 ν”„λ‘œμ„ΈμŠ€κ°€ ν• λ‹Ήλ˜μ—ˆλ‹€. μ‚¬μš©μžκ°€ 자주 μ‚¬μš©ν•˜λŠ” ν”„λ‘œμ„ΈμŠ€μ˜ μš°μ„ μˆœμœ„λ₯Ό λ†’κ²Œ λΆ€μ—¬ν•˜λŠ” μ‹μœΌλ‘œ 기쀀을 λ§Œλ“€ 수 μžˆλ‹€. λ‹€λ§Œ νŠΉμ • ν”„λ‘œμ„ΈμŠ€μ˜ μš°μ„  μˆœμœ„κ°€ 계속 λ°€λ € κΈ°μ•„κ°€ λ°œμƒν•  수 μžˆμœΌλ―€λ‘œ, μ‹œκ°„μ΄ 지날 λ•Œλ§ˆλ‹€ ν”„λ‘œμ„ΈμŠ€μ˜ λ‚˜μ΄λ₯Ό μ¦κ°€μ‹œμΌœ 였래 λŒ€κΈ°ν•œ ν”„λ‘œμ„ΈμŠ€μ˜ μš°μ„ μˆœμœ„λ₯Ό λ†’μ—¬μ£ΌλŠ” μ‘°μΉ˜κ°€ ν•„μš”ν•˜λ‹€.