Scheduling
์ฌ๋ฌ ํ๋ก์ธ์ค๋ฅผ ํ๋์ (๋๋ ๋ช ๊ฐ์) CPU๊ฐ ์ฒ๋ฆฌํด์ผ ํ๋ค. ์ด๋ค ์์๋ก ์ฒ๋ฆฌํ ๊น?
- ๋ค์ด์จ ์์๋๋ก ์ฒ๋ฆฌํ ์ ์๋ค.
- ์ฒ๋ฆฌ๊ฐ ๋นจ๋ฆฌ ๋๋ ์์๋ก ์ฒ๋ฆฌํ ์๋ ์๋ค.
- ์๋๋ฉด ๋ค๋ฅธ ์ฐ์ ์์์ ๋ฐ๋ผ ์ฒ๋ฆฌํ ์๋ ์๋ค.
1. ์ค์ผ์ค๋ง์ ํ๊ฐ
- ๋ฐํ ์๊ฐ: ํ๋ก์ธ์ค์ ์ข ๋ฃ์๊ฐ - ํ๋ก์ธ์ค์ ๋๋ฌ ์๊ฐ
- ์๋ต ์๊ฐ: ํ๋ก์ธ์ค์ ์์์๊ฐ - ํ๋ก์ธ์ค์ ๋๋ฌ ์๊ฐ
์ผ๋ จ์ ์์ ๋ค์ด ์ฒ๋ฆฌ๋ ๋, ํ๊ท ์ ์ธ ๋ฐํ์๊ฐ๊ณผ ์๋ต์๊ฐ์ด ์ ์์๋ก ์ข์ ์ค์ผ์ค๋ง์ด ๋๊ฒ ๋ค.
- ์ฑ๋ฅ: n๊ฐ์ ์์ ์ ์ผ๋ง๋ ๋นจ๋ฆฌ ์ฒ๋ฆฌํ๋๋
- ๊ณต์ ์ฑ: ๊ฐ๊ฐ์ ์์ ์ ์ผ๋ง๋ ๊ท ๋ฑํ๊ฒ ์ฒ๋ฆฌํ๋๋
์๋ฅผ ๋ค์ด ๋ง์ฝ ์์ ์๊ฐ์ด ๋น ๋ฅธ ์์ผ๋ก ์ค์ผ์ค๋งํ๋ค๋ฉด, ์ค๋ ๊ฑธ๋ฆฌ๋ ์์ ์ ๊ฒฝ์ฐ ๊ทธ์ ๋๊ธฐํด์ผ ํ๋ ๊ฒฝ์ฐ๊ฐ ์์ ์ ์๋ค. ์ด๋ ๊ฐ ์์ ์ ๊ณต์ ํ๊ฒ ์ฒ๋ฆฌํ์ง ๋ชปํ๊ณ ์๋ ๊ฒ์ผ๋ก ๋ณผ ์๋ ์๋ค. ์ฑ๋ฅ๊ณผ ๊ณต์ ์ฑ์ ์ผ๋ฐ์ ์ธ ์ค์ผ์ค๋ง ์ ์ฑ ์์ ์ถฉ๋ํ๋ ๋ ์งํ์ผ ์ ์์ผ๋ฉฐ, ์์ชฝ๊ฐ์ ์ ๊ท ํ์ ์ก๋ ๊ฒ์ด ๋ฏธ์ ์ด ๋๋ค. ์ด๋ฅผํ ๋ฉด, ์์ ์ด ๋๊ธฐํ๊ณ ์๋ ์๊ฐ์ด ๊ธธ์ด์ง์๋ก ์ฐ์ ์์๋ฅผ ๋์ด๋ ๊ฒ(aging)๋ ๋ฐฉ๋ฒ์ด ๋ ์ ์๋ค.
๐ ์ ์ ํ/๋น์ ์ ํ ์ค์ผ์ค๋ง?
- ์ ์ ํ preemptive: ์์
์ด ์์ง ์ข
๋ฃ๋์ง ์์์ด๋ ํ์ํ ๊ฒฝ์ฐ ๋ค๋ฅธ ์์
์ผ๋ก context switch๊ฐ ์ด๋ฃจ์ด์ง๋ ๊ฒ.
- ์ธํฐ๋ฝํธ๊ฐ ๋๋ฉด switch, ์๊ฐ(time-slice, tick)์ด ์ง๋๋ switch
- ํ๋์ ๋ชจ๋ ์ค์ผ์ค๋ฌ๋ ์ ์ ํ์ด๋ค.
- ๋น์ ์ ํ non-preemtive: ์์
์ด ํ ๋ฒ ์์๋๊ณ ๋๋ฉด, ์ข
๋ฃ๋๊ฑฐ๋ ์ธํฐ๋ฝํธ๊ฐ ๋ฐ์ํ ๋๊น์ง๋ CPU์ ์ ๋ฅผ ๋ณด์ฅํด ์ฃผ๋ ๊ฒ.
- ์ธํฐ๋ฝํธ๊ฐ ๋๊ฑฐ๋, ์์ ์ด ์ข ๋ฃ๋๋ฉด switch
- ์์ ์ผ๊ด์ฒ๋ฆฌ ์์คํ ์ด ์ด๋ฐ ๊ฑธ ์ผ๋ค..
2. ์ค์ผ์ค๋ง์ ๋ฐฉ๋ฒ
2.1. General Scheduling Problems
2.1.1. ์ ๋์ฐฉ์ ์ฒ๋ฆฌ First In First Served
๋นจ๋ฆฌ ๋ค์ด์จ ์์ ๋ถํฐ ์ฒ๋ฆฌํ๋ค. ๊ทธ๋ ์ง๋ง ์์ ์ ์์๋๋ ์๊ฐ์ ๊ณ ๋ คํ์ง ์๊ธฐ ๋๋ฌธ์, ์์ ์๊ฐ์ด ์งง์ ์ฌ๋ฌ ์์ ๋ค์ด ์ค๋ ๊ฑธ๋ฆฌ๋ ํ๋์ ์์ ์ ๊ธฐ๋ค๋ฆฌ๊ณ ์๋ ์ํฉ์ด ๋ฒ์ด์ง ์ ์๋ค. (์ด๊ฒ์ convoy effect๋ผ๊ณ ํ๋ค..๊ณ ํ๋ค.) ์ด ๊ฒฝ์ฐ ์์ ๋ค์ ํ๊ท ๋ฐํ ์๊ฐ๊ณผ ๋๊ธฐ ์๊ฐ์ด ๋์ด๋๋ค.
2.1.2. ์ต๋จ์์ ์ฐ์ Shortest Job First
๊ฐ์ฅ ์งง์ ์๊ฐ์ด ๊ฑธ๋ฆฌ๋ ์์ ๋ถํฐ ์ฒ๋ฆฌํ๋ค. ๊ทธ๋ฐ๋ฐ ๋ชจ๋ ์์ ๋ค์ด ๋์์ ๋ค์ด์ค๋ ๊ฒ์ ์๋๋ค. ๋ฏธ๋์ ๋ค์ด์ฌ ์์ ์ด ์งง๋ค๋ ๊ฒ์ ์ด๋ป๊ฒ ์ ์ ์์๊น? (๋น์ฐํ ๋ชจ๋ ์์ ์ด ๋์์ ๋์ฐฉํ๋ค๊ณ ๊ฐ์ ํ๋ฉด SJF๊ฐ ์ต์ ์ ์ ํ์ด ๋๊ฒ ๋ค.)
2.1.3. ์ต์์์ฌ์๊ฐ์ฐ์ Shortest Time-to-Completion First
์ ์ ํ ์์ด๋์ด๋ฅผ ๊ฒฐํฉ์ํจ๋ค. ์ฆ, ์คํ ์ค์ธ ํ๋ก์ธ์ค์ ์์ฌ์๊ฐ์ด ์๋ก ๋ค์ด์จ ํ๋ก์ธ์ค์ ์คํ์๊ฐ๋ณด๋ค ๊ธธ๋ฉด ํ์ฌ ํ๋ก์ธ์ค๋ฅผ ์ค๋จํ๊ณ ์๋ก์ด ํ๋ก์ธ์ค๋ฅผ ์คํ์ํค๋ ๊ฒ์ด๋ค.
๐ ์๋ต ์๊ฐ์ ์๋ก์ด ํ๊ฐ๊ธฐ์ค์ด๋ค. ์?
๋ฐํ ์๊ฐ์ ์์คํ
์ด ๋๋ฅผ ์ผ๋ง๋ ๋นจ๋ฆฌ ์ฒ๋ฆฌํ๋๋? ์๋ต ์๊ฐ์ ์์คํ
์ด ๋์๊ฒ ์ผ๋ง๋ ๋นจ๋ฆฌ ์๋ตํ๋๋. I/O๊ฐ ์ค์ํด์ง(ํ๋์ ๋ง์ ์์คํ
์ด ๋ํํ)์ ๋ฐ๋ผ ์์คํ
์ด ์ฆ์ ์๋ตํ๋ ๊ฒ์ด ์ค์ํ ์ค์ผ์ค๋ง ํ๊ฐ ๊ธฐ์ค์ด ๋๋ค. ์๋ถํ ์ปดํจํฐ์ ๋ฑ์ฅ์ด ๋น ๋ฅธ ์๋ต์๊ฐ์ ์ค์์ฑ์ ๋์๋๋ฐ, ์ด๋ ์๋ถํ ์ปดํจํฐ๊ฐ ํ๋์ ์ปดํจํฐ๋ฅผ ์ฌ๋ฌ ์ฌ์ฉ์๊ฐ ๋์์ ์ฌ์ฉํ๋ ๊ฒ์ฒ๋ผ ๋ณด์ด๊ฒ๋ ๋ง๋ค์๋ค๋ ๊ฒ๊ณผ ๊ด๋ จ์ด ์๋ค. ์๋ถํ ์ด์ ์๋ ์ผ๊ด ์ฒ๋ฆฌ ๋ฐฉ์์ด์๋๋ฐ, ์ด๋ ์์
์ ํ์ ๋ชจ์๋๊ณ ํ๋ฒ์ ์ฒ๋ฆฌํ๋ ๋ฐฉ์์ด๋ฏ๋ก ์ฌ์ฉ์์ ๊ฐ๋ณ ์
๋ ฅ๋ง๋ค ์ฆ์ ์๋ต์ ์ฃผ๊ธฐ ์ด๋ ค์ ๋ค. ํ์ง๋ง ์๋ถํ ์ปดํจํฐ์ ๋ฑ์ฅ์ผ๋ก, ์ฌ์ฉ์์ ์์ฒญ์ ๋น ๋ฅด๊ฒ ์ฒ๋ฆฌํ ์ ์๊ฒ ๋๋ฉด์ ์ฌ์ฉ์์์ ์ค์๊ฐ ์ํธ์์ฉ์ด ๊ฐ๋ฅํด์ก๋ค. (์๋ถํ ์์คํ
์ ๊ตฌ์กฐ์ ์์น ์์ฒด๊ฐ ์ฌ๋ฌ ์ฌ์ฉ์์์ ์ค์๊ฐ ์ํธ์์ฉ์ ์ง์ํ ์ ์๋๋ก ์ค๊ณ๋์๋ค.)
2.1.4. ๋ผ์ด๋ ๋ก๋น Round-Robin
์๋ต ์๊ฐ์ ๋์ด๋ ค๋ฉด, ํ๋ก์ธ์ค์ ์คํ ์๊ฐ๊ณผ ๊ด๊ณ์์ด ์ผ๋จ ๋ค์ด์ค๋ฉด ๋น ๋ฅด๊ฒ ์คํํ ์ ์๋๋ก ํด์ผ ํ๋ค. ์ดํ ๋ค์ ํ๋ก์ธ์ค์ ์ํด ์ค๋จ๋๋๋ผ๋. ๊ทธ๋์ ํ๋ก์ธ์ค๋ง๋ค ๋์ผํ ์๊ฐ ๋จ์ (time-slice)๋ก ๋๋ ์, ์ด ์๊ฐ๋งํผ ์คํํ ํ ์ค๋จํ์ฌ ์คํ ํ์ ๋ง์ง๋ง์ ๋ฃ๊ณ , ์คํ ํ์ ๋ค์ ์์ ์ผ๋ก ์ ํํ๋ ๊ฒ์ ๋ผ์ด๋ ๋ก๋น (RR)์ด๋ผ๊ณ ํ๋ค. ์ด๋์ ์๊ฐ ๋จ์๋ฅผ time-slice๋๋ ์ค์ผ์ค๋ง ํํ scheduling quantum์ด๋ผ๊ณ ํ๋ค. ํ๋ก์ธ์ค๊ฐ ๋๋ฌํ ๊ฒ ๋๋น ์ผ๋ง๋ ๋นจ๋ฆฌ ์คํ๋๋๋๊ฐ ์ค์ํ๋ฏ๋ก, time-slice๊ฐ ์งง์์๋ก ์๋ต์๊ฐ์ ์ต์ํํ๋๋ฐ๋ ์ข๋ค. ํ์ง๋ง context switching์ ํ์ํ ๋น์ฉ์ด ์ฆ๊ฐํ ์ ์๊ธฐ ๋๋ฌธ์ ๊ท ํ์ ์ ์ก์์ผ ํ๋ค.
๊ทธ๋ฐ๋ฐ ๋๋ค๋ฅธ ํ๊ฐ ๊ธฐ์ค์ธ ๋ฐํ ์๊ฐ์ ์๊ฐํด๋ณด๋ฉด, ๋ผ์ด๋ ๋ก๋น์ ๊ฒฝ์ฐ ํ๋ก์ธ์ค์ ์คํ์๊ฐ๊ณผ ๊ด๊ณ์์ด ๋์ผํ ๊ธธ์ด๋ก ๋๋๊ธฐ ๋๋ฌธ์ ํ๋ก์ธ์ค ์ข ๋ฃ๊น์ง ์๊ฐ์ด ์ง์ฐ๋๋ค. (๋์์ N๊ฐ์ ํ๋ก์ธ์ค๊ฐ ๋ค๋ค๋ค.. ์จ ์ต์ ์ ๊ฒฝ์ฐ๋ฅผ ์๊ฐํด๋ณด์.) RR์ ๊ณต์ ํ ์ค์ผ์ค๋ง์ด๊ธด ํ์ง๋ง, ์ด๋ก ์ธํด ์ ์ฒด์ ์ธ ์ฑ๋ฅ์ ๋ฎ์์ง ์ ์๋ค. ํ์ง๋ง ๊ทธ๋๋ ์ฐ๊ธด ์ด๋ค. (๋ฆฌ๋ ์ค์ ๊ด๋ จ๊ฐ์ด ์๋ค.)
๐ ๋ผ์ด๋ ๋ก๋น ํ์ ์ฌ๋ผ์ด์ค์ ๊ธธ์ด
๋ค์ํ ์ ์ฑ
์ ๋ฐ๋ผ ๊ฒฐ์ ๋๋ค. ์ผ๋ จ์ ํ๋ก์ธ์ค๋ ์ค๋ ๋ ๋จ์๋ง๋ค ๋ฌ๋ผ์ง ์๋ ์๋ค. ์๋๋ ๋ฆฌ๋
์ค์์ ๊ธฐ๋ณธ ์ค์ ๋ ํ์ ์ฌ๋ผ์ด์ค ๊ฐ์ ํ์ธํ๋ ๋ช
๋ น์ด 2๊ฐ. ํ์ง๋ง ๋ชจ๋ ํ๋ก์ธ์ค๊ฐ 100ms๋จ์๋ก ์ฌ๋ผ์ด์ฑ์ด ์ด๋ฃจ์ด์ง๊ณ ์๋ ๊ฒ์ ์๋๋ค. (๊ทธ๋ฆฌ๊ณ ํ์ ์ฌ๋ผ์ด์ค๋ ์คํ์ ์ต๋์๊ฐ์์ ๊ธฐ์ตํด์ผ ํ๋ค.)
cat /proc/sys/kernel/sched_rr_timeslice_ms
sysctl kernel.sched_rr_timeslice_ms
// 100
๐ I/O interrupt์ ์ฒ๋ฆฌ
ํ๋์ ํ๋ก์ธ์ค๊ฐ 10ms ์คํ ํ I/O ์ธํฐ๋ฝํธ๊ฐ ๋ฐ์ํ๋ค๋ฉด, ๊ทธ ์๊ฐ์ CPU๋ฅผ ๋ค๋ฅธ ํ๋ก์ธ์ค๊ฐ ์ ์ ํ๋๋ก ํ์ฌ ์ฐ์ฐ์ ์ค์ฒฉ์ํฌ ์ ์๋ค. CPU๊ฐ ๊ฒฐ์ฝ ์ฌ์ง ์๊ฒ ๋์๊ฐ๋๋ก ํ์ฌ ์ด์ฉ๋ฅ ์ ๋์์ผ๋ก์ ์ต์ ํ๋ฅผ ์ํํ๋ค.
๐ ์์ฝํ์๋ฉด..
General Problems์์ ์์๋ณธ ๋ฐฉ๋ฒ๋ค ์ค SJF, STCF๋ ๋ฐํ์๊ฐ์ ์ฐ์ ํ๋ ์๊ณ ๋ฆฌ์ฆ์ด์๋ค. (FIFS๋ ์ ์ธํ๊ณ ..) ํ์ง๋ง ํ๋ก์ธ์ค์ ์๋ต์๊ฐ์ด ๋ฆ์ด์ง๋ค๋ ๋จ์ ์ด ์๋ค. ๋ฐ๋ฉด, RR์ time-slicing์ผ๋ก ์ธํด ์ต์ด๋ก CPU๋ฅผ ์ ์ ํ๋ ์๊ฐ์ ์งง์์ง์ง๋ง, ๊ฒฐ๊ตญ ์ฒ๋ฆฌ๊น์ง ์ค๋ ๊ฑธ๋ฆฐ๋ค๋ ๋จ์ ์ด ์๋ค. ์ด ์ฌ์ด๋ฅผ.. ์ ๊ท ํ์ ์ก์ ์๋ ์์๊น? Time slicing์ ์ฅ์ ์ ์ด๋ฆฌ๋ฉด์๋ ์ค์ผ์ค๋ง์ ์ฑ๋ฅ์ ๋์ผ ์๋ ์์๊น? ๊ทธ๋ฆฌ๊ณ ๋ฌด์๋ณด๋ค๋, ๊ฐ ํ๋ก์ธ์ค์ ์คํ ์๊ฐ์ ์ ์ ์๋๋ฐ ์ด๋ป๊ฒ ์ค์ผ์ค๋ง์ ์ํํ ๊น? ์ ๋ฌธ์ ๊ฐ ๋จ์ ์๋ค. ์ด๋ฅผ Multi Level Feedback Queue๋ก ํด๊ฒฐํ ์ ์๋ค.
2.2. Multilevel Feedback Queue
์ฌ๊ธฐ์์ ์ค๋ช ํ๋ mlfq๋ PintOS์ Advanced Scheduler๋ฅผ ๊ธฐ๋ฐ์ผ๋ก ํ๋ฏ๋ก 4.4BSD Scheduler์ ์ ์ฌ์ ์ ๊ณต์ ํ๋ค.
2.2.1 What is mlfq?
mlfqs๋ CPU๋ฅผ ์ต๋๋ก ํ์ฉํ๊ธฐ ์ํ ์ค์ผ์ค๋ง ์๊ณ ๋ฆฌ์ฆ์ ์ผ์ข ์ผ๋ก, ๋ค์๊ณผ ๊ฐ์ ์๊ตฌ์ฌํญ์ ๊ฐ์ง๋ค.
- ํ๋ก์ธ์์ ๋ํ ์๊ตฌ์ ๊ธฐ๋ฐํ์ฌ (์ฐ์ ์์์ ๊ธฐ๋ฐํ์ฌ) ๊ฐ ํ๋ก์ธ์ค๋ฅผ ์ฌ๋ฌ ๊ฐ์ ์ค๋น ํ๋ก ๋๋๋ค.
- ์งง์ CPU burst๋ฅผ ๊ฐ์ง ํ๋ก์ธ์ค๋ฅผ ์ฐ์ ํ๋ค.
- ๋์ I/O burst๋ฅผ ๊ฐ์ง ํ๋ก์ธ์ค๋ฅผ ์ฐ์ ํ๋ค.
multilevel queue ์๊ณ ๋ฆฌ์ฆ์ด ํ๋ก์ธ์ค๋ฅผ ์ด๊ธฐ ์ฐ์ ์์๋๋ก ์ ์งํ๋ ๋ฐ๋ฉด, multilevel feedback queue ์๊ณ ๋ฆฌ์ฆ์ ํ๋ก์ธ์ค๋ฅผ ํ๋์ ํ์์ ๋ค๋ฅธ ํ๋ก ์ฎ๊ธด๋ค. ์ฆ, ์ค์ผ์ค๋ง ์ค์ ์ฐ์ ์์์ ๋ณ๋์ด ์ผ์ด๋๋ค.
- ํ๋ก์ธ์ค๊ฐ CPU๋ฅผ ๋๋ฌด ๋ง์ด ์ฐ๋ฉด, ๋ฎ์ ์ฐ์ ์์์ ํ๋ก ์ฎ๊ฒจ์ง๋ค.
- ํ๋ก์ธ์ค๊ฐ I/O-bound์ด๊ฑฐ๋, interactiveํ๋ฉด ๋์ ์ฐ์ ์์์ ํ๋ก ์ฎ๊ฒจ์ง๋ค.
- ํ๋ก์ธ์ค๊ฐ ๋ฎ์ ์ฐ์ ์์์ ํ์์ ๋๋ฌด ์ค๋ ๊ธฐ๋ค๋ฆฌ๋ ๊ธฐ์(starvation)๊ฐ ๋ฐ์ํ๋ฉด, ๋์ ์ฐ์ ์์์ ํ๋ก aging๋๋ค.
๐ I/O bound? ํ๋์ ๊ณ์ฐ์ ์๋ฃํ๋ ๋ฐ ๊ฑธ๋ฆฌ๋ ์๊ฐ์ด input๊ณผ output์ด ์๋ฃ๋๊ธฐ๋ฅผ ๊ธฐ๋ค๋ฆฌ๋ ์๊ฐ์ ์ํด ๊ฒฐ์ ๋๋ ์กฐ๊ฑด. ๋ฐ์ดํฐ๊ฐ ์์ฒญ๋๋ ์๋๊ฐ ๋ฐ์ดํฐ๊ฐ ์๋น๋๋ ์๋๋ณด๋ค ๋๋ฆด ๋ ์ด๋ฌํ ํ์์ด ๋ฐ์ํ๋ค. (opps. CPU bound)
mlfq๋ ์์์ ์ ๊ธฐํ ์์ ์ ์คํ ์๊ฐ์ ์ ์ ์๋ ์ํฉ์์, ์๋ต ์๊ฐ๊ณผ ๋ฐํ ์๊ฐ์ ์ด๋ป๊ฒ ์ค์ผ ์ ์์๊น? ๋ผ๋ ๋ฌธ์ ์ ๋ค์๊ณผ ๊ฐ์ ๋ต์ ์ ์ํ๋ค.
- ๋ชจ๋ ์์ ์ด ์ต์ด๋ก ์คํ๋ ๋๋ ์ผ๋จ ๊ฐ์ฅ ๋์ ์ฐ์ ์์๋ก ์ธํ ๋๊ณ , ํ์ ์ฌ๋ผ์ด์ค ๋ด์์ CPU๋ฅผ ์ ์ ํ๋ ์๊ฐ์ด ๊ธธ์ด์ง์๋ก ์ฐ์ ์์๊ฐ ๋ฎ์์ง๋ค. ๋ฐ๋ผ์, ์คํ ์๊ฐ์ด ์งง์ ์์ ์ด ์๋์ ์ผ๋ก ๋์ ์ฐ์ ์์๋ฅผ ์ป๊ณ ์ฒ๋ฆฌ๋๋ค. ์ฆ, SJF์ ์ ์ฌํ ํจ๊ณผ๋ฅผ ๋ณด์ด๊ฒ ๋๋ค.
- I/O๋ ์งง์ ์์
, ์ฆ ํ์ ์ฌ๋ผ์ด์ค๋ณด๋ค ์งง๊ฒ ์คํ๋๊ณ (์ข
๋ฃ๋๊ฑฐ๋) CPU๋ฅผ ์๋ํ๋ ์์
์ ๊ฒฝ์ฐ ์ฐ์ ์์๊ฐ ๋ณ๊ฒฝ๋์ง ์๋๋ค. ๋ฐ๋ผ์ ๋์ ์ฐ์ ์์๋ฅผ ์ ์งํ๊ณ , ์ด๋ก ์ธํด ๋ฐ๋ณต์ ์ผ๋ก I/O๋ฅผ ์ํํ๋ ์์
์ ๊ฒฝ์ฐ์๋ ๋น ๋ฅธ ์๋ต ์๊ฐ์ ๊ฐ๊ฒ ๋๋ค.
=> ๋ฐ๋ผ์ mlfq๋ ์งง์ ์์ ๊ณผ I/O bound๋ฅผ ์ฐ์ ํ๋ค๋ ๋ชฉํ๋ฅผ ๋ฌ์ฑํ๋ค. - ๋ํ์ฌ, ๋๊ธฐ ํ์์ ์ค๋ ๋๊ธฐํ๋ ์์ , ์ฆ ์ต๊ทผ์ cpu๋ฅผ ํ ๋น๋ฐ์ง ๋ชปํ ์์ ์ ์ฐ์ ์์๋ฅผ ๋์ ์ผ๋ก ๋์ฌ์ค์ผ๋ก์ ๊ธฐ์ starvation์ ์๋ฐฉํ ์ ์๋ค. ์ด๋ฅผ ํตํด ์์ ๋ค์ด ์ต๋ํ ๊ณต์ ํ๊ฒ CPU๋ฅผ ์ ์ ํ ์ ์๋๋ก ํ๋ค. (๊ณต์ ์ฑ๊ณผ ์๋ ์ฌ์ด์ ๊ท ํ)
2.2.2. How to implement mlfq
์๋์ ๊ฐ์ ์์์ ์ํด mlfqs์ ๊ตฌํ์ด ๋ฌ๋ผ์ง ์ ์๋ค.
- ํ์ ๊ฐ์๋ ๋ช ๊ฐ๋ก ํด์ผ ํ ๊น?
- ํ๋์ ํ์์์ ์ค์ผ์ค๋ง ์๊ณ ๋ฆฌ์ฆ (FIFO๊ฐ ์๋ ์๋ ์์)์ ์ด๋์ผ ํ ๊น?
- ํ ๋น ํ์ ์ฌ๋ผ์ด์ค์ ํฌ๊ธฐ๋ ์ด๋์ผ ํ ๊น?
- ํ๋ก์ธ์ค์ ์ฐ์ ์์ (ํ)๋ฅผ ๋ณ๊ฒฝํ๋ ์ฃผ๊ธฐ๋ ์ธ์ ์ฌ์ผ ํ ๊น?
...
์ฌ๋ฌ ์์ ๋ค์ด ๋จ์ ์๋ค. ๊ทธ ์ค, pintos์์ ์ ์ํ๋ 4.4BSD ์ค์ผ์ค๋ฌ๋ ํ๋ก์ธ์ค๊ฐ ์ฌ์ฉํ๋ cpu ์๊ฐ์ ์ง์ ๊ฐ์ค ์ด๋ ํ๊ท ๊ณผ ๊ฐ์ ๊ฐ์ ์ฌ์ฉํด ์ฐ์ ์์๋ฅผ ์ฃผ๊ธฐ์ ์ผ๋ก ์ฌ๊ณ์ฐํ๋ค.
nice
nice๋ ์์
์ ์ฐ์ ์์๋ฅผ ์กฐ์ ํ๊ธฐ ์ํด ์ฌ์ฉ์๊ฐ ์ง์ ์ ์ผ๋ก ์ ์ดํ๋ ๊ฐ์ผ๋ก, -20๋ถํฐ 20๊น์ง์ ๋ฒ์๋ฅผ ๊ฐ๋๋ค. ๊ฐ์ด ๋ฎ์์๋ก ์ฐ์ ์์๋ฅผ ๋๊ฒ ์กฐ์จํ๋ค. (๋ค๋ฅธ ์ค๋ ๋์๊ฒ CPU๋ฅผ ์๋ณดํ ์๋ก niceํด์ ๋ถ์ ์ด๋ฆ์ธ ๊ฒ ๊ฐ๋ค.) OSTEP์์๋ ์ด์์ฒด์ ์๊ฒ ์ด๋ค ์์
์ ์ฐ์ ํด์ผ ํ๋์ง ํํธ๋ฅผ ์ ๊ณตํ ์ ์๋ ์ฌ์ฉ์ ์ธํฐํ์ด์ค๋ก์ nice๋ฅผ ์ค๋ช
ํ๊ณ ์๋ค.
priority
์ฐ์ ์์๋ nice, recent_cpu์ ์ง์ ์ ์ผ๋ก ์์กดํ๋ฉฐ, ๋ค์๊ณผ ๊ฐ์ด ๊ณ์ฐ๋๋ค. ์ฌ๊ธฐ์ ํฌ์ธํธ๋ (์ฌ์ฉ์์ ์ํด ๋ช
์์ ์ผ๋ก ์ ์ด๋๋ nice๋ฅผ ์ ์ธํ๋ค๋ฉด) recent_cpu๊ฐ ๋ฎ์์๋ก ์ฐ์ ์์๊ฐ ๋์์ง๋ค๋ ์ ์ด๋ค. ์ฆ, ์ต๊ทผ๊น์ง CPU๋ฅผ ํ ๋น๋ฐ์ง ์์๋ ์ค๋ ๋์ผ์๋ก ๋์ ์ฐ์ ์์๋ก ์ด๋ํ๊ฒ ๋๋ค.
priority = PRI_MAX - (recent_cpu / 4) - (nice*2)
recent_cpu
recent_cpu๋ ์์
์ด ์ต๊ทผ ์ ์ ํ๋ CPU์ ์๊ฐ์ ๋ํ๋ธ๋ค. ๋งค tick๋ง๋ค ํ์ฌ ์์
์ recent_cpu๊ฐ 1์ฉ ์ฆ๊ฐํ๊ณ , ๋งค ์ด๋ง๋ค ๋ค์ ๊ณต์์ ์ด์ฉํด ์ด๊ธฐํ๋๋ค.
recent_cpu = (load_avg * 2) / (load_avg * 2 + 1) * recent_cpu + nice
์ ๊ณต์์ ์ต๊ทผ์ ์ธํ ๋ recent_cpu ๊ฐ์ ๊ฐ์ค์น๋ฅผ ๋ถ์ฌํ๋ฉด์, ์ต๊ทผ์ ์ ์ ํ cpu ์ฌ์ฉ๋ฅ ์ ๊ณ์ฐํ๋ค. (์ญ์ ์ฌ์ฉ์์ ์ํด ์ ์ด๋ ์ ์๋ nice๊ฐ์ ์ ์ธํ๊ณ ) ๋จ์ผ ์์ ์ recent_cpu๋ฅผ ๊ณ์ฐํ๋ ๊ฒฝ์ฐ๋ฅผ ์๊ฐํด ๋ณด์. (๋จ์ผ์ด๋ฏ๋ก load_avg = 1.0)
ํ๋์ ์์ ์ด ๋งค $i$ ์ด๋ง๋ค ๋์ ํ tick์ $T_i$๋ผ๊ณ ํ์.
$rc_1 = 0.66 \times T_0$
$rc_2 = 0.66 \times (T_1 + rc_1) = 0.66 \times T_1 + 0.44 *\times T_0$
$rc_3 = 0.66 \times (T_1 + rc_2) = 0.66 \times T_2 + 0.44 *\times T_1 + 0.30 \times T_0$
$rc_4 = 0.66 \times T_3 + \cdots + 0.19 \times T_0$
์ด๋ฐ ์์ผ๋ก ์ด์ ์๊ฐ์ ๋์ ๋ tick์ ๊ฐ์ ์ํจ๋ค. ์ฆ, ์ต๊ทผ์ ๋์ ๋ tick (CPU ์ ์ ์๊ฐ)์ ๊ฐ์ค์น๋ฅผ ๋ถ์ฌํด CPU ์ฌ์ฉ๋ฅ ์ ๊ณ์ฐํ๋ ๊ฒ์ด๋ค. ๋ฐ๋ผ์, ์ต๊ทผ์ CPU ํ ๋น์ ๋ชป ๋ฐ์ ์์ ์ผ์๋ก ์ฐ์ ์์๋ฅผ ๋์ฌ์ฃผ๋ aging์ ํ๊ธฐ ๋๋ฌธ์ ๊ธฐ์๋ฅผ ์๋ฐฉํ ์ ์๋ค.
load_avg
1๋ถ ๋์ ready ๋๋ running์ธ ์์
์ ์ถ์ ์น์ด๋ค.
load_avg = (59/60) * load_avg + (1/60) * ready_threads,
priority๋ nice์ recent_cpu์ ์์กดํ๊ณ , recent_cpu๋ nice์ load_avg๊ฐ์ ์์กดํ๋ค. load_avg๋ ํ์ฌ ์คํ ๋๋ ๋๊ธฐ์ค์ธ ์์ ์ ์์ ์์กดํ๋ค. ๋ฐ๋ผ์ ๋๊ธฐ์ด์ ์๋ ์์ ์ด ๋ง์์๋ก, ์ฆ CPU๋ฅผ ์ ์ ํ๋ ค๋ ๊ฒฝ์์ด ๋์์๋ก recent_cpu์ ๊ณ์๊ฐ ์ปค์ ธ์ ๋ ๋น ๋ฅด๊ฒ ๊ฐ์ ํ๊ฒ ๋๋ค. ์ด๋ ์ฐ์ ์์๋ฅผ ๋ ํฐ ํญ์ผ๋ก ๋ณ๋์์ผ ๋ ๋ง์ ์์ ์ด ์คํ๋ ์ ์๋๋ก ํ๋ค.
'DevLog ๐จ' ์นดํ ๊ณ ๋ฆฌ์ ๋ค๋ฅธ ๊ธ
[DevLog][PintOS] PRJ2 User Program/Out of Memory Test (0) | 2023.10.10 |
---|---|
[DevLog][PintOS] PRJ1 Threads/PintOS ์ค๋ ๋๋ ์ด๋ป๊ฒ ๋์๊ฐ๊น? (0) | 2023.10.03 |
[DevLog][PintOS] PRJ1 Threads/Priority Scheduling (0) | 2023.09.27 |
[DevLog][CSAPP] 10์ฅ ์์คํ ์์ค ์ ์ถ๋ ฅ (10.1~10.5) (0) | 2023.09.24 |
[DevLog][CSAPP] 9์ฅ 9.9 malloc lab ๋์ ํ ๋น๊ธฐ ๊ตฌํ (0) | 2023.09.24 |