โ† Articles

๐Ÿฆ• ๊ณต๋ฃก์ฑ…์œผ๋กœ ์ •๋ฆฌํ•˜๋Š” ์šด์˜์ฒด์ œ Ch.5

Process Scheduling

Table of Contents

์šด์˜์ฒด์ œ๊ฐ€ ์–ด๋–ค ํ”„๋กœ์„ธ์Šค๋ฅผ ํ”„๋กœ์„ธ์„œ์— ํ• ๋‹นํ•  ๊ฒƒ์ธ๊ฐ€ ์ •ํ•˜๋Š” ํ”„๋กœ์„ธ์Šค ์Šค์ผ€์ค„๋ง(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+103=6.33 \text{Average wating time} = {0 + 9 + 10 \over 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+04=7 \text{Average wating time} = {3 + 16 + 9 + 0 \over 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+24=26 \text{Average wating time} = {9 + 0 + 15 + 2 \over 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+53=4 \text{Average wating time} = {4 + 3 + 5 \over 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+15=5 \text{Average wating time} = {4 + 0 + 9 + 11 + 1 \over 5} = 5

์šฐ์„ ์ˆœ์œ„์— ๋”ฐ๋ผ ํ”„๋กœ์„ธ์Šค๊ฐ€ ํ• ๋‹น๋˜์—ˆ๋‹ค. ์‚ฌ์šฉ์ž๊ฐ€ ์ž์ฃผ ์‚ฌ์šฉํ•˜๋Š” ํ”„๋กœ์„ธ์Šค์˜ ์šฐ์„ ์ˆœ์œ„๋ฅผ ๋†’๊ฒŒ ๋ถ€์—ฌํ•˜๋Š” ์‹์œผ๋กœ ๊ธฐ์ค€์„ ๋งŒ๋“ค ์ˆ˜ ์žˆ๋‹ค. ๋‹ค๋งŒ ํŠน์ • ํ”„๋กœ์„ธ์Šค์˜ ์šฐ์„  ์ˆœ์œ„๊ฐ€ ๊ณ„์† ๋ฐ€๋ ค ๊ธฐ์•„๊ฐ€ ๋ฐœ์ƒํ•  ์ˆ˜ ์žˆ์œผ๋ฏ€๋กœ, ์‹œ๊ฐ„์ด ์ง€๋‚  ๋•Œ๋งˆ๋‹ค ํ”„๋กœ์„ธ์Šค์˜ ๋‚˜์ด๋ฅผ ์ฆ๊ฐ€์‹œ์ผœ ์˜ค๋ž˜ ๋Œ€๊ธฐํ•œ ํ”„๋กœ์„ธ์Šค์˜ ์šฐ์„ ์ˆœ์œ„๋ฅผ ๋†’์—ฌ์ฃผ๋Š” ์กฐ์น˜๊ฐ€ ํ•„์š”ํ•˜๋‹ค.

โ†

๐Ÿฆ• ๊ณต๋ฃก์ฑ…์œผ๋กœ ์ •๋ฆฌํ•˜๋Š” ์šด์˜์ฒด์ œ Ch.6

Synchronization

โ†’

๐Ÿฆ• ๊ณต๋ฃก์ฑ…์œผ๋กœ ์ •๋ฆฌํ•˜๋Š” ์šด์˜์ฒด์ œ Ch.4

Multithreaded Programming

โ† Articles