[OS] CPU ์ค์ผ์ค๋ง ์๊ณ ๋ฆฌ์ฆ
by rlaehddnd0422OS๋ CPU ์ค์ผ์ค๋ง์ ํตํด Ready Queue์ ์กด์ฌํ๋ ํ๋ก์ธ์ค๋ฅผ ์ ํํ์ฌ CPU๋ฅผ ํ ๋นํฉ๋๋ค.
์ด ๋ ์ด๋ค ํ๋ก์ธ์ค๋ฅผ ํ ๋นํ ๊ฒ์ธ์ง ๊ฒฐ์ ํ๋ ์๊ณ ๋ฆฌ์ฆ์ 'CPU ์ค์ผ์ค๋ง ์๊ณ ๋ฆฌ์ฆ'์ด๋ผ๊ณ ํฉ๋๋ค.
CPU ์ค์ผ์ค๋ง ์๊ณ ๋ฆฌ์ฆ ์ข ๋ฅ
๋จผ์ ์ค์ผ์ค๋ง ์๊ณ ๋ฆฌ์ฆ์ '์ ์ ํ'๊ณผ '๋น์ ์ ํ'์ผ๋ก ๋๋ ์ ์์ต๋๋ค.
- ์ ์ ํ์ ํ๋์ ํ๋ก์ธ์ค๊ฐ CPU๋ฅผ ์ฐจ์งํ๊ณ ์๋ ํ๋ก์ธ์ค๋ฅผ ๋์ ํ์ฌ CPU๋ฅผ ์ ์ ํ ์ ์๋ ๋ฐฉ์.
- ๋น์ ์ ํ์ ์ ์ ํ๊ณผ ๋ฐ๋๋ก ํ๋์ ํ๋ก์ธ์ค๊ฐ CPU๋ฅผ ์ ์ ํ๊ณ ์๋ค๋ฉด, ์ด ํ๋ก์ธ์ค๊ฐ ์ข ๋ฃ๋ ๋ ๊น์ง ๋ค๋ฅธ ํ๋ก์ธ์ค๋ CPU๋ฅผ ์ฌ์ฉํ ์ ์๋ ๋ฐฉ์์ ๋๋ค.
- ์ ์ ํ, ๋น์ ์ ํ์ ์ฐจ์ด๋ฅผ ํท๊ฐ๋ฆฌ์ง ์๋๋ก ์ฃผ์
- ์ ์ ํ์ฌ ๋ค๋ฅธ ํ๋ก์ธ์ค๊ฐ ์ ์ ํ ์ ์๋ค๊ณ ํด์ '์ ์ ํ'์ด ์๋๊ณ , ๋ ๋ ํ์ ์กด์ฌํ๋ ํ๋ก์ธ์ค ๊ด์ ์์ '์ ์ ํ ์ ์๋ค'๋ ์๋ฏธ๋ก '์ ์ ํ', '์ ์ ํ ์ ์๋ค'๋ ์๋ฏธ '๋น์ ์ ํ' ๋ก ์์๋ก์๋ค.
๋น์ ์ ํ ๋ฐฉ์์ CPU๋ฅผ ์ ์ ํ๊ณ ์๋ ๋ค๋ฅธ ํ๋ก์ธ์ค๊ฐ ์ข ๋ฃ๋ ๋ ๊น์ง ํ ๋น์ ๊ธฐ๋ค๋ฆฌ๊ธฐ ๋๋ฌธ์, ๊ฐ์ ๋ก ํ๋ก์ธ์ค๋ฅผ ์ค๋จํ์ง ์์ผ๋ฏ๋ก , ์ธํฐ๋ฝํธ๊ฐ ๋ฐ์ํ์ง ์๊ณ ๋ฐ๋ผ์ Context Switching์ผ๋ก ์ธํ ๋ถํ๊ฐ ๋ฐ์ํ์ง ์์ต๋๋ค.
๋น์ ์ ํ ์๊ณ ๋ฆฌ์ฆ์๋ ๋ํ์ ์ผ๋ก FCFS, SJF, ์ฐ์ ์์ ์๊ณ ๋ฆฌ์ฆ์ด ์์ต๋๋ค.
์ ์ ํ ์๊ณ ๋ฆฌ์ฆ์๋ RR, SRF, ๋ค๋จ๊ณ ํ ์๊ณ ๋ฆฌ์ฆ์ด ์์ต๋๋ค.
๋น์ ์ ํ ์๊ณ ๋ฆฌ์ฆ - FCFS (First Come First Service)
- FCFS๋ ์๊ณ ๋ฆฌ์ฆ ์ด๋ฆ์์ ๋ฐฉ์์ ์ ์ถํ ์ ์์ต๋๋ค. ๋ง ๊ทธ๋๋ก ๋จผ์ ๋ค์ด์จ ํ๋ก์ธ์ค์ ๋จผ์ CPU๋ฅผ ํ ๋นํด์ฃผ๋ ๋ฐฉ์์ ๋๋ค.
- FIFO Queue๋ฅผ ํตํด ํ๋ก์ธ์ค๋ฅผ ๊ด๋ฆฌํ์ฌ ๋จผ์ ๋ค์ด์จ ํ๋ก์ธ์ค์ ๋จผ์ ์์์ ํ ๋นํด์ค๋๋ค.
- FCFS ์๊ณ ๋ฆฌ์ฆ์ Convoy Effect๊ฐ ๋ฐ์ํ ์ ์์.
Convoy Effect : ํ ํ๋ก์ธ์ค๊ฐ ์ค๋ซ๋์ CPU ์์์ ์ ์ ํ์ฌ ๊ทธ ๋ค์ ๋ค์ด์ค๋ ์์ ์ฌ์ฉ ์๊ฐ์ด ์งง์ ํ๋ก์ธ์ค๋ค์ ๋๊ธฐ์๊ฐ์ด ๊ธธ์ด์ ธ ์ ์ฒด์ ์ธ ํ๋ก์ธ์ค์ ์ฑ๋ฅ์ด ์ ํ๋๋ ํ์
๋น์ ์ ํ ์๊ณ ๋ฆฌ์ฆ - SJF (Shortest Job First)
- ๊ฐ ํ๋ก์ธ์ค์ Burst Time(์์ ์ฌ์ฉ ์๊ฐ)์ ๋น๊ตํ์ฌ ์งง์ ์์๋๋ก CPU๋ฅผ ํ ๋นํ๋ ๋ฐฉ์
- ์ด ๋ ๋ ํ๋ก์ธ์ค์ Burst Time์ด ๊ฐ๋ค๋ฉด, ์ ์ ์ ์ถ ์ค์ผ์ค๋ง์ ์ ์ฉ.
- SJF ๋ฐฉ์์ Starvation ํ์์ด ๋ฐ์ํ ์ ์์.
Starvation : ๊ธด ์๊ฐ์ ๊ฐ์ง ํ๋ก์ธ์ค๊ฐ ์ฐ์ ์์์์ ์๊พธ ๋ฐ๋ ค๋ ์คํ๋์ง ์๋ ํ์
+ ์ค์ ํ๋ก์ธ์ค๊ฐ ์ผ๋งํผ ์คํ๋๋์ง ์ ์ ์๊ธฐ ๋๋ฌธ์, ๊ณผ๊ฑฐ ์คํ์๊ฐ์ ํ ๋๋ก ์ถ์ธกํด์ Burst Time์ ์์ธกํ์ฌ ํ ๋นํ๋๋ฐ, ์ด์กฐ์ฐจ๋ ์ ํํ์ง ์๋ค๋ ํ๊ณ๊ฐ ์์ต๋๋ค.
๋น์ ์ ํ ์๊ณ ๋ฆฌ์ฆ - ์ฐ์ ์์
- ๊ธฐ์กด SJF์์ ๋ฐ์ํ๋ Starvation์ ๋ฌธ์ ๋ฅผ ํด๊ฒฐํ๊ธฐ ์ํ ๋ฐฉ์.
- ์ค๋๋ ์์ ์ผ์๋ก ์ฐ์ ์์๋ฅผ ๋์ด๋ ๋ฐฉ๋ฒ(Aging)์ ํตํด SJF์ ๋จ์ ์ ๋ณด์ํ ์๊ณ ๋ฆฌ์ฆ์ ๋๋ค.
- ์ฌ๊ธฐ์ ์ฐ์ ์์๋ aging ๋ฟ๋ง ์๋๋ผ ์์ ์ ์๊ฐ, ํ๋ก์ธ์ค์ ๋ฉ๋ชจ๋ฆฌ ์๊ตฌ์ฌํญ, ์ด๋ฆฐ ํ์ผ ์, ํ๊ท CPU ์ฌ์ฉ๋ ๋ฑ์ ์ข ํฉํ ๋ณตํฉ์ ์ธ ์์๋ฅผ ํตํด ๊ฒฐ์ ๋ฉ๋๋ค.
- ์ฐ์ ์์ ์๊ณ ๋ฆฌ์ฆ์ "SJF + ์ฐ์ ์์"๋ฅผ ๋งํ๋ ๊ฒ ๋ฟ๋ง ์๋๋ผ "FCFS + ์ฐ์ ์์"๋ฅผ ํ์ฉํ์ฌ ๋ง๋ค๊ธฐ๋ ํ๊ณ , CPU ์์์ ์ ์ ํ๊ณ ์๋ ํ๋ก์ธ์ค๋ฅผ ์ค๋จ์ํค๊ณ ์ฐ์ ์์์ ์๊ฑฐํ ํ๋ก์ธ์ค๊ฐ ๊ธฐ์กด ํ๋ก์ธ์ค๋ฅผ ์ค๋จ์ํค๊ณ ์ ์ ํ๋๋ก ํ๋ ์ ์ ํ ๋ฐฉ์๋ ์์ต๋๋ค.
- ex) "SJF + ์ฐ์ ์์ + ์ ์ ํ" = SRTF(Shortest Remaining Time First) ์๊ณ ๋ฆฌ์ฆ : ์๋ก์ด ํ๋ก์ธ์ค๊ฐ ํ์ฌ ์คํ์ค์ธ ํ๋ก์ธ์ค์ ๋จ์ ์๊ฐ๋ณด๋ค Burst Time์ด ์งง์ ๊ฒฝ์ฐ ์ธํฐ๋ฝํธ๋ฅผ ๋ฐ์์์ผ ํ๋ก์ธ์ค๋ฅผ ์ค๋จํ๊ณ Context Switching์ ์ผ์ผ์ผ ์๋ก์ด ํ๋ก์ธ์ค๋ฅผ ํ ๋น.
์ ์ ํ ์๊ณ ๋ฆฌ์ฆ - RR (Round Robin)
ํ๋ ์ด์์ฒด์ ๊ฐ ์ฌ์ฉํ๋ ๋ฐฉ์์ธ ์ ์ ํ ๋ฐฉ์์ ํ์ฌ ์คํ์ค์ธ ํ๋ก์ธ์ค๋ฅผ ์๊ณ ๋ฆฌ์ฆ์ ์ํด ์ค๋จ์์ผ๋ฒ๋ฆฌ๊ณ ๊ฐ์ ๋ก ๋ค๋ฅธ ํ๋ก์ธ์ค์๊ฒ CPU ์์ ๊ถ์ ํ ๋นํ๋ ๋ฐฉ์์ ๋๋ค.
๋จผ์ Round Robin ๋ฐฉ์์ด ์์ต๋๋ค.
- ๊ฐ ํ๋ก์ธ์ค์๊ฒ "CPU๋ฅผ ์ ์ ํ ์ ์๋ ๋์ผํ ํ ๋น ์๊ฐ"์ ์ฃผ๊ณ ๊ทธ ์๊ฐ์์ ํ๋ก์ธ์ค๊ฐ ๋๋์ง ์์ผ๋ฉด ๋ค์ ์ค๋น ํ์ ๋ค์ ๋ค์ด๊ฐ๋ ์๊ณ ๋ฆฌ์ฆ
- ๋ง์ฝ ํ ๋นํ ์๊ฐ์์ ํ๋ก์ธ์ค๊ฐ ๋๋๋ ๊ฒฝ์ฐ ์ค๋น ํ์ ์ ์ผ ์์ ์๋ ๋ค์ ํ๋ก์ธ์ค์๊ฒ CPU ์ ์ ๊ถ์ ๋๊น๋๋ค.
- ๋ก๋๋ฐธ๋ฐ์์์ ํธ๋ํฝ ๋ถ์ฐ ์๊ณ ๋ฆฌ์ฆ์ผ๋ก ์ฌ์ฉ.
RR์ ์ฑ๋ฅ
- ์ฑ๋ฅ์ด ํ ๋น ์๊ฐ์ ๋งค์ฐ ๋ง์ ์ํฅ์ ๋ฐ์ต๋๋ค.
- "ํ ๋น ์๊ฐ"์ด ๋๋ฌด ํผ > (ํ ํ์ ํํ ๋์ ํ๋ก์ธ์ค์ ์คํ์ด ์๋ฃ๋จ) > ๋จผ์ ๋ค์ด์จ ํ๋ก์ธ์ค๊ฐ ๋จผ์ ์์์ ์ ์ ํ๋ FCFS๋ก ์ด์ด์ง ๊ฐ๋ฅ์ฑ ํผ.
- "ํ ๋น ์๊ฐ"์ด ๋๋ฌด ์งง์ > ์ฆ์ Context Switching ๋ฐ์ > ์ฑ๋ฅ ์ ํ, ๋น์ฉ ์ฆ๊ฐ
- ์ผ๋ฐ์ ์ผ๋ก ์ ์ฒด ์์ ์๊ฐ์ ๊ธธ์ด์ง์ง๋ง ํ๊ท ์๋ต์๊ฐ์ ์งง์์ง๋ค๋ ํน์ง์ด ์์ต๋๋ค.
์ ์ ํ ์๊ณ ๋ฆฌ์ฆ - SRTF ( Shortest Remaining Time First )
- ์์ ๋งํ "์ฐ์ ์์ + SJF + ์ ์ ํ" ๋ฐฉ์์ ์๊ณ ๋ฆฌ์ฆ
- ์งง์ ๋ฒ์คํธ ํ์์ ์ฐ์ ์ ์ผ๋ก ํ ๋นํ๋, Aging์ ํตํ ์ฐ์ ์์๋ ํจ๊ป ๋ถ์ฌํ์ฌ ๊ธด ๋ฒ์คํธ ํ์์ ํ๋ก์ธ์ค๊ฐ ์คํ๋์ง ์๋ ๋จ์ ์ ๋ณด์ํ ์ ์๋ ์๊ณ ๋ฆฌ์ฆ.
- ๊ธด ํ๋ก์ธ์ค๊ฐ ์ค๋ซ๋์ ์คํ๋์ง ์๊ณ ์์ผ๋ฉด ํ์ฌ ์คํ๋๊ณ ์๋ ํ๋ก์ธ์ค๋ฅผ ์ค๋จ์์ผ ์ ์ ํ๋๋ก ํจ.
์ ์ ํ ์๊ณ ๋ฆฌ์ฆ - ๋ค๋จ๊ณ ํ
- ์ฐ์ ์์๋ง๋ค ๋ณ๋์ ํ๋ฅผ ์ฌ๋ฌ ๊ฐ ์ฌ์ฉํ์ฌ, ํ๋ง๋ค Round Robin, FCFS ๋ฑ ๋ค๋ฅธ ์ค์ผ์ค๋ง ์๊ณ ๋ฆฌ์ฆ์ ์ ์ฉํ ๋ฐฉ์.
- ํ์ ํ ๊ฐ์ ํ๋ก์ธ์ค ์ด๋์ด ์๋๊ณ ํ๋ก์ธ์ค๋ค์ด ์์คํ ์ง์ ์ ์๊ตฌ์ ์ผ๋ก ํ๋์ ํ์ ํ ๋น.
- ๋ง์ฝ ํ ํ๋ก์ธ์ค๊ฐ ์คํํ๋ ๋์ค ์ธํฐ๋ฝํธ๊ฐ ๋ฐ์ํ์ฌ ์ค๋น ํ๋ก ๋์์๋ค๊ณ ํ์ ๋, ๊ธฐ์กด ์ํ์ค์ด๋ ํ๋ก์ธ์ค๊ฐ ์๋ ํ๋ณด๋ค ๋์ ๋จ๊ณ์ ํ์ ํ๋ก์ธ์ค๊ฐ ํ๋๋ผ๋ ์๋ค๋ฉด ๊ทธ ํ๋ก์ธ์ค์ CPU๋ฅผ ํ ๋นํ๋ ๊ธฐ๋ฒ.
์ ์ ํ ์๊ณ ๋ฆฌ์ฆ - ๋ค๋จ๊ณ ํผ๋๋ฐฑ ํ
- ๋ค๋จ๊ณ ํ์ ๋ฌ๋ฆฌ ํ๋ก์ธ์ค๊ฐ ํ๋ค ์ฌ์ด๋ฅผ ์ด๋ํ๋ ๊ฒ์ ํ์ฉํ๋ ๋ค๋จ๊ณ ํผ๋๋ฐฑ ํ ์ค์ผ์ค๋ง ๋ฐฉ์.
- ํ์ ํํ ์ด๊ณผ : ํ๋ก์ธ์ค๊ฐ ํ ๋น๋ ์๊ฐ ๋ด์ ์์ ์ ์๋ฃํ์ง ๋ชปํ๋ฉด, ๋ค์ ์ฐ์ ์์๊ฐ ๋ฎ์ ํ๋ก ์ด๋ํฉ๋๋ค.
- ํ์ ํํ ๋ด ์๋ฃ : ํ๋ก์ธ์ค๊ฐ ํ ๋น๋ ์๊ฐ ๋ด์ ์์ ์ ์๋ฃํ๋ฉด, Ready Queue๋ก ํ๋ก์ธ์ค๋ฅผ ์ด๋
- CPU Burst๋ ๋ฎ์ ์ฐ์ ์์์ ํ, I/O Burst๋ ๋์ ์ฐ์ ์์์ ํ์ ๋ฐฐ์น
- ๋จ๊ณ๊ฐ ๋ด๋ ค๊ฐ์๋ก ํํ ๋์ด ์ฆ๊ฐํ๋ฉฐ, ๊ฐ์ฅ ํ์ ํ๋ FCFS ์ค์ผ์ค๋ง์ ์ฌ์ฉ.
- ๋งจ ์๋ ํ์์ ๋๋ฌด ์ค๋ ๋๊ธฐํ๋ฉด ๋ค์ ์์ ํ๋ก ์ด๋.
<์ฐธ๊ณ ์๋ฃ>
'๐ CS > OS' ์นดํ ๊ณ ๋ฆฌ์ ๋ค๋ฅธ ๊ธ
๋ธ๋ก๊ทธ์ ์ ๋ณด
Study Repository
rlaehddnd0422