Archive: 2020/4

0

Arch linux ์„ค์น˜ํ•˜๊ธฐ

์ด ๊ธ€์€ ์ธํ„ฐ๋„ท์— ์ž‘์„ฑ๋œ Arch linux๋ฅผ ์„ค์น˜ํ•˜๋Š” ๋ฐฉ๋ฒ•์„ ๊ฐœ์ธ์ ์œผ๋กœ ์ •๋ฆฌํ•œ ๊ธ€์ž…๋‹ˆ๋‹ค. ๊ธ€์˜ ๋Œ€๋ถ€๋ถ„์˜ ๋‚ด์šฉ์€ ์•„๋ž˜ โ€˜๋ ˆํผ๋Ÿฐ์Šคโ€™์— ์ถœ์ฒ˜๊ฐ€ ์ž‘์„ฑ๋˜์–ด์žˆ์œผ๋‹ˆ ์ž์„ธํ•œ ๋‚ด์šฉ์„ ์›๋ณธ ๊ธ€์—์„œ ์ฐธ์กฐํ•˜์‹œ๋Š”๊ฑธ ์ถ”์ฒœํ•ด ๋“œ๋ฆฝ๋‹ˆ๋‹ค. Arch Linux๋ฅผ ์„ค์น˜ํ•˜๋ฉฐ ๊ฐ€์ƒ ๋จผ์ € ํ•˜๋Š” ๊ฒƒ์€ ๋‹น์—ฐํžˆ arch linux์˜ ์„ค์น˜ ISO ํŒŒ์ผ์„ ๊ตฌํ•˜๋Š” ๊ฒƒ๋ถ€ํ„ฐ ์‹œ์ž‘๋œ๋‹ค. ๋จผ์ € PC์—์„œ ์„ค์น˜ํ•˜๋Š” ๊ฒƒ๋ณด๋‹จ Virtual Box ๊ฐ™์€ ๊ฐ€์ƒ PC์—์„œ ์„ค์น˜ํ•˜๊ธฐ ์œ„ํ•ด์„œ USB์— ๊ตฝ๋Š” ๊ณผ์ •์„ ์ƒ๋žตํ–ˆ๋‹ค. ๋จผ์ € ํ•œ๊ตญ ๋ฏธ๋Ÿฌ๋ง ์„œ๋ฒ„์—์„œ ๋ฐ›๊ธฐ ์›ํ•œ๋‹ค๋ฉด ์ด๊ณณ์—์„œ ๋‹ค์šด๋กœ๋“œ๋ฐ›์„ ์ˆ˜ ์žˆ๋‹ค. ๋‹ค๋ฅธ ๋‚˜๋ผ๋ฅผ ์ด์šฉํ•˜๊ณ  ์‹ถ๋‹ค๋ฉด ์ด๊ณณ์—์„œ ์›ํ•˜๋Š” ๋‚˜๋ผ์˜ ๋ฏธ๋Ÿฌ๋ง ์„œ๋ฒ„๋ฅผ ํ™•์ธํ•  ์ˆ˜ ์žˆ๋‹ค.

0

64bit ๋ฉ€ํ‹ฐ์ฝ”์–ด OS ์›๋ฆฌ์™€ ๊ตฌ์กฐ - Day 2

์ด ๊ธ€์€ โ€˜64๋น„ํŠธ ๋ฉ€ํ‹ฐ์ฝ”์–ด OS ์›๋ฆฌ์™€ ๊ตฌ์กฐ - ํ•œ์Šนํ›ˆ ์ €์žโ€™์„ ๊ณต๋ถ€ํ•˜๋ฉฐ ์ •๋ฆฌํ•œ ๋‚ด์šฉ์„ ์ž‘์„ฑํ–ˆ์Šต๋‹ˆ๋‹ค. ์ด๋ฏธ์ง€ ๋กœ๋”ฉ ๊ตฌํ˜„์ฑ…์—์„œ ๊ตฌํ˜„ํ•˜๊ฒŒ ๋  OS๋Š” ๋ถ€ํŠธ ๋กœ๋”, ๋ณดํ˜ธ ๋ชจ๋“œ ์ปค๋„, IA-32e ๋ชจ๋“œ ์ปค๋„๋กœ ๊ตฌ์„ฑ๋˜๊ณ  ์„นํ„ฐ ๋‹จ์œ„๋กœ ์ •๋ ฌ๋˜ ํ•˜๋‚˜์˜ ๋ถ€ํŒ… ์ด๋ฏธ์ง€๋กœ ๋งŒ๋“ค์–ด์ง€๋ฉฐ ๋‘ ๋ฒˆ์งธ ์„นํ„ฐ๋ถ€ํ„ฐ ์ฝ์–ด ๋ฉ”๋ชจ๋ฆฌ์— ๋ณต์‚ฌํ•˜๋ฉด ์ด๋ฏธ์ง€ ๋กœ๋”ฉ์ด ๋๋‚˜๊ฒŒ ๋œ๋‹ค. ์ฑ…์—์„œ ๊ตฌํ˜„ํ•˜๋Š” OS๋Š” ๋ฉ”๋ชจ๋ฆฌ 0x10000๋ฒˆ์ง€์— ๋ณต์‚ฌํ•˜๊ฒŒ ๋˜๋ฉฐ, ์ด ์ฃผ์†Œ๋Š” ์ •ํ•ด์ง„๊ฒŒ ์•„๋‹ˆ๋ผ ๋ถ€ํŠธ ๋กœ๋” ์ดํ›„์— ๋ฐ”๋กœ ๋ณต์‚ฌํ•ด๋„ ๋˜์ง€๋งŒ, ์ฑ…์˜ ๋’ท์žฅ์—์„œ 0x10000 ์ดํ•˜ ๋ฒˆ์ง€๋ฅผ ๋‹ค๋ฅธ ์šฉ๋„๋กœ ์‚ฌ์šฉํ•˜๊ธฐ ์œ„ํ•ด์„œ ๋น„์›Œ๋‘”๋‹ค. x86 ํ”„๋กœ์„ธ์„œ๋Š” ์Šคํƒ๊ณผ ๊ด€๋ จ๋œ ๋ ˆ์ง€์Šคํ„ฐ๊ฐ€ 3๊ฐœ ์žˆ๋Š”๋ฐ SS, SP, BP๊ฐ€ ์žˆ๋‹ค. ์ด๋•Œ SS๋ฅผ ์–ด๋–ป๊ฒŒ ์„ค์ •ํ•˜๋Š๋ƒ์— ๋”ฐ๋ผ์„œ ์Šคํƒ์˜ ํฌ๊ธฐ๊ฐ€ ๋‹ฌ๋ผ์ง€๋Š”๋ฐ ์˜ˆ๋ฅผ ๋“ค์–ด SS๋ฅผ 0x0000์œผ๋กœ ์„ค์ •ํ•œ๋‹ค๋ฉด 0x00000~0x0FFFF SS๋ฅผ 0x1000์œผ๋กœ ์„ค์ •ํ•˜๋ฉด 0x010000~0x01FFFF๊นŒ์ง€ ๋œ๋‹ค. ์ด๋ ‡๊ฒŒ SS๋ฅผ ํ†ตํ•ด์„œ ์Šคํƒ์˜ ๋ฒ”์œ„๋ฅผ ์ง€์ •ํ•  ์ˆœ ์žˆ์ง€๋งŒ, ์Šคํƒ์˜ ํฌ๊ธฐ๋Š” ์ •ํ•˜์ง€ ๋ชปํ•˜๋Š”๋ฐ 32bit์˜ ์Šคํƒ ํ•œ ์นธ์˜ ํฌ๊ธฐ๋Š” 4byte์ด๋‹ค. ๋ฆฌ์–ผ ๋ชจ๋“œ์—์„œ ๋ณดํ˜ธ ๋ชจ๋“œ๋กœ์˜ ์ „ํ™˜๋ณดํ˜ธ ๋ชจ๋“œ๋กœ ์ „ํ™˜ํ•˜๋Š” ๋‹จ๊ณ„๋Š” ํฌ๊ฒŒ 6๋‹จ๊ณ„๋ผ๊ณ  ํ•  ์ˆ˜ ์žˆ๋‹ค. 2๋‹จ๊ณ„๋Š” ๋ณดํ˜ธ ๋ชจ๋“œ ์ „ํ™˜์„ ์œ„ํ•œ ์ž๋ฃŒ๊ตฌ์กฐ ์ƒ์„ฑ, ๋‚˜๋จธ์ง€ 4๋‹จ๊ณ„๋Š” ์ƒ์„ฑ๋œ ์ž๋ฃŒ๊ตฌ์กฐ๋ฅผ ํ”„๋กœ์„ธ์„œ์— ์„ค์ •์„ ํ•œ๋‹ค. 2๋‹จ๊ณ„์—์„œ ์ƒ์„ฑํ•  ํ•„์ˆ˜ ์ž๋ฃŒ๊ตฌ์กฐ๋Š” ์„ธ๊ทธ๋จผํŠธ ๋””์Šคํฌ๋ฆฝํ„ฐ์™€ GDT์ด๋‹ค. ์ด ๋‘ ์ž๋ฃŒ๊ตฌ์กฐ๋Š” ์ „ํ™˜ ์ฆ‰์‹œ ํ”„๋กœ์„ธ์„œ์— ์˜ํ•ด ์ฐธ์กฐ๋˜๋ฏ€๋กœ ๋ฏธ๋ฆฌ ์ƒ์„ฑํ•ด์•ผ ํ•œ๋‹ค.

0

64bit ๋ฉ€ํ‹ฐ์ฝ”์–ด OS ์›๋ฆฌ์™€ ๊ตฌ์กฐ - Day 1

์ด ๊ธ€์€ โ€˜64๋น„ํŠธ ๋ฉ€ํ‹ฐ์ฝ”์–ด OS ์›๋ฆฌ์™€ ๊ตฌ์กฐ - ํ•œ์Šนํ›ˆ ์ €์žโ€™์„ ๊ณต๋ถ€ํ•˜๋ฉฐ ์ •๋ฆฌํ•œ ๋‚ด์šฉ์„ ์ž‘์„ฑํ–ˆ์Šต๋‹ˆ๋‹ค. ์„ธ์ƒ์—์„œ ๊ฐ€์žฅ ๊ฐ„๋‹จํ•œ BootLoader๋ถ€ํŠธ ๋กœ๋”๋ฅผ ์ •์ƒ์ ์œผ๋กœ ๋ถˆ๋Ÿฌ์˜ค๊ธฐ ์œ„ํ•ด์„œ๋Š” ํ•œ๊ฐ€์ง€ ๊ทœ์น™์ด ์žˆ๋‹ค. ๋จผ์ € ๋ถ€ํŠธ ์„นํ„ฐ 512Byte์˜ ๋งˆ์ง€๋ง‰ 2Byte๋Š” ๋ฐ˜๋“œ์‹œ 0x55, 0xAA๋ฅผ ๊ฐ€์ ธ์•ผ ํ•œ๋‹ค. ์•„๋ž˜๋Š” ์„ธ์ƒ์—์„œ ๊ฐ€์žฅ ๊ฐ„๋‹จํ•œ ๋ถ€ํŠธ๋กœ๋”๋ฅผ ์ž‘์„ฑํ•œ ์†Œ์Šค ์ฝ”๋“œ์ด๋‹ค. 12345678[ORG 0x00][BITS 16]SECTION .textjmp $times 510 - ($ - $$) db 0x00db 0x55db 0xAA ์œ„ ์ฝ”๋“œ์—์„œ [ORG 0x00]์€ 0x00 ๋ฉ”๋ชจ๋ฆฌ ์ฃผ์†Œ์—์„œ ์‹œ์ž‘ํ•œ๋‹ค๋Š” ์˜๋ฏธ์ด๋ฉฐ, [BITS 16]์€ ์•„๋ž˜ ์ฝ”๋“œ๋Š” 16bit๋ผ๊ณ  ์•Œ๋ ค์ค€๋‹ค. SECTION .text์€ .text ์„น์…˜์˜ ์‹œ์ž‘์„ ์˜๋ฏธํ•˜๊ณ  jmp $์€ ํ˜„์žฌ ์œ„์น˜์—์„œ ๋ฌดํ•œ Loop์„ ํ•˜๋ฉฐ ๋Œ€๊ธฐํ•˜๊ฒŒ ํ•œ๋‹ค. ์—ฌ๊ธฐ๊นŒ์ง€ ์ด ๋ช‡ Byte๊ฐ€ ์ž‘์„ฑ๋œ ์ง€ ์†Œ์Šค ์ฝ”๋“œ๋กœ๋Š” ํ™•์ธ์ด ์–ด๋ ต๊ธฐ์— 510byte (512byte์—์„œ ๋งˆ์ง€๋ง‰ 0x55, 0xAA 2byte๋ฅผ ๋บ€ ์ˆซ์ž)๋งŒํผ ์ฑ„์šฐ๊ธฐ ์œ„ํ•ด์„œ times 510 - ($ - $$) db 0x00์ด๋ผ๊ณ  ํ‘œํ˜„ํ•œ๋‹ค. ์ด ์˜๋ฏธ๋Š” $(ํ˜„์žฌ ์ฃผ์†Œ)์ด์—์„œ $$(์„น์…˜์˜ ์ฃผ์†Œ)๋ฅผ ๋บ€ ๊ฐ’, ๋‹ค์‹œ ๋งํ•ด ์ด ์ƒ์„ฑ๋œ opcode ํฌ๊ธฐ๋ฅผ ๋บ€ ๋‚˜๋จธ์ง€๋ฅผ 0x00์œผ๋กœ ์ฑ„์šฐ๊ฒ ๋‹ค๋Š” ์˜๋ฏธ์ด๋‹ค. ์ดํ›„ 0x55, 0xAA๋ฅผ ์ฑ„์šฐ๋ฉด ์ •ํ™•ํžˆ 512byte ํฌ๊ธฐ์˜ ๋ฐ”์ด๋„ˆ๋ฆฌ ํŒŒ์ผ์ด ์ƒ์„ฑ๋˜๊ฒŒ ๋œ๋‹ค. ํ™”๋ฉด ๋ฒ„ํผ ์ œ์–ด์–ด๋ฆด ์  ์ปดํ“จํ„ฐ๋ฅผ ํ‚ค๋ฉด ๊นœ๋นก์ด๋Š” ์ปค์„œ์™€ ํ•จ๊ป˜ ๋œป ๋ชจ๋ฅผ ์˜์–ด๋“ค์ด ์ฃผ๋ฃฉ์ฃผ๋ฃฉ ๋‚˜์˜ค๋Š” ๊ฑธ ๋ณธ ๊ธฐ์–ต์ด ์žˆ๋‹ค. ํ˜„์žฌ ์ž‘์„ฑ๋œ Boot Loader์— ์œ„์™€ ๊ฐ™์€ ๊ธฐ๋Šฅ์„ ๊ตฌํ˜„ํ•˜๊ธฐ ์œ„ํ•ด์„œ๋Š” ๋น„๋””์˜ค ๋ฉ”๋ชจ๋ฆฌ์— ํ˜•์‹์— ๋งž์ถฐ ๋ฐ์ดํ„ฐ๋ฅผ ๋„ฃ์–ด์ฃผ๋Š” ๊ฑฐ๋กœ ๊ตฌํ˜„ํ•  ์ˆ˜ ์žˆ๋‹ค. ๊ทธ๋Ÿฌ๊ธฐ ์œ„ํ•ด์„  ๋น„๋””์˜ค ๋ฉ”๋ชจ๋ฆฌ์˜ ์‹œ์ž‘ ์ฃผ์†Œ 0xB8000์— ๋ฌธ์ž 1 Byte, ์†์„ฑ 1 Byte ์ด 2 Byte์ธ ํ˜•์‹์— ๋งž์ถฐ ๊ฐ€๋กœ 80, ์„ธ๋กœ 25์ž ์ด 4000 Byte์— ์ž‘์„ฑํ•˜๊ฒŒ ๋œ๋‹ค. 12345678... ์ƒ๋žต ...SECTION .textmov ax, 0xb800mov ds, axmov byte[0x00], 'J'mov byte[0x01], 0x4Ajmp $... ์ƒ๋žต ... ์ด๋ ‡๊ฒŒ ์ž‘์„ฑํ•˜๊ณ  QEMU๋ฅผ ์‹คํ–‰ํ•˜๋ฉด ์ฒซ ๊ธ€์ž๊ฐ€ ๋นจ๊ฐ„ ๋ฐฐ๊ฒฝ์˜ J๊ฐ€ ๋ณด์ด๊ฒŒ ๋œ๋‹ค. ์„ธ๊ทธ๋จผํŠธ ์ดˆ๊ธฐํ™”

0

Merge sort algorithm

ํ•ฉ๋ณ‘ ์ •๋ ฌ(merge sort)ํ•ฉ๋ณ‘ ์ •๋ ฌ์€ ๋ถ„ํ• ์ •๋ณต ์•Œ๊ณ ๋ฆฌ์ฆ˜์ด๋ฉฐ ๊ธธ์ด๊ฐ€ N์ธ ๋ฆฌ์ŠคํŠธ๋ฅผ ๊ธธ์ด๊ฐ€ 1์ธ ๋ฆฌ์ŠคํŠธ๋กœ ์ชผ๊ฐœ๊ณ  ๋‹ค์‹œ ์ชผ๊ฐœ์ง„ ๊ฐ๊ฐ์˜ ๋ฆฌ์ŠคํŠธ๋ฅผ ์ •๋ ฌํ•˜๋ฉฐ ํ•ฉ๋ณ‘ํ•ด ์ตœ์ข…์ ์œผ๋กœ ์ •๋ ฌ๋œ ๋ฆฌ์ŠคํŠธ๋ฅผ ๊ฐ€์ง€๊ฒŒ ๋œ๋‹ค. ํ•จ์ˆ˜์˜ ๊ตฌ์กฐ๋ฅผ ๋ณด๋ฉด ์•Œ๊ฒ ์ง€๋งŒ, ์ค‘์•™ ์œ„์น˜๋ฅผ ์ฐพ๊ณ  ์ค‘์•™ ์œ„์น˜๋ฅผ ๊ธฐ์ค€์œผ๋กœ ์ขŒ์ธก, ์šฐ์ธก์„ ๋‚˜๋ˆ  ์žฌ๊ท€ ํ˜ธ์ถœ๋œ๋‹ค. ์žฌ๊ท€ ์ข…๋ฃŒ ์กฐ๊ฑด์€ start < end์˜ ์กฐ๊ฑด์— ๋งž์ง€ ์•Š๋Š”๋‹ค๋ฉด ๋” ๋‚˜๋‰  ์ˆ˜ ์—†๋‹ค๊ณ  ํŒ๋‹จํ•˜์—ฌ ์ชผ๊ฐœ๋Š” ๊ณผ์ •์ด ์ข…๋ฃŒ๋œ๋‹ค. ์ตœ์ข…์ ์œผ๋กœ ๋งˆ์ง€๋ง‰ mergeํ•จ์ˆ˜๋ฅผ ์ด์šฉํ•ด ๊ฐ ๋ฆฌ์ŠคํŠธ๋ฅผ ํ•ฉ๋ณ‘ํ•œ๋‹ค. ์ค‘์š”ํ•œ ์ ์€ ์ด๋•Œ ์ž„์‹œ๋ฒ„ํผ๋ฅผ ์‚ฌ์šฉํ•ด์•ผ ํ•˜๋Š”๋ฐ, ๋งŒ์•ฝ ์ž„์‹œ๋ฒ„ํผ๋ฅผ ์‚ฌ์šฉํ•  ์ˆ˜ ์—†๋Š” ์กฐ๊ฑด์ด๋ผ๋ฉด ํ•ฉ๋ณ‘ ์ •๋ ฌ์€ ์‚ฌ์šฉํ•  ์ˆ˜ ์—†๋‹ค.

0

Quick sort algorithm

ํ€ต ์ •๋ ฌ ์•Œ๊ณ ๋ฆฌ์ฆ˜ํ€ต ์ •๋ ฌ์€ ํ”ผ๋ฒ—์„ ๊ธฐ์ค€์œผ๋กœ ์ขŒ/์šฐ์— ์ž์‹ ๋ณด๋‹ค ํฐ/์ž‘์€ ๊ฐ’์„ ๋ชฐ๊ณ , ๋ฌธ์ œ๋ฅผ ์กฐ๊ธˆ์”ฉ ๋‚˜๋ˆ ๊ฐ€๋ฉฐ ์ •๋ ฌ์„ ํ•˜๊ฒŒ ๋œ๋‹ค. ์ตœ์•…์˜ ๊ฒฝ์šฐ(ํ•ญ์ƒ ํ”ผ๋ฒ—์ด ๋ชจ๋“  ๊ฐ’ ์ค‘ ๊ฐ€์žฅ ์ž‘์€ ๊ฒฝ์šฐ) O(n^2)๋ฅผ ๊ฐ€์ง€๋Š” ์ƒํ™ฉ์ด ๋‚˜์˜ฌ ์ˆ˜ ์žˆ์ง€๋งŒ, ํ™•๋ฅ ์ ์œผ๋กœ ๊ทธ๋Ÿด ์ผ์€ ์ ๊ธฐ์— ํ‰๊ท ์ ์œผ๋กœ O(NlogN)์˜ ์‹œ๊ฐ„๋ณต์žก๋„๋ฅผ ๊ฐ€์ง„๋‹ค.

0

Dijkstra Algorithm

๋‹ค์ต์ŠคํŠธ๋ผ ์•Œ๊ณ ๋ฆฌ์ฆ˜Dijkstra algorithm(์ดํ•˜ ๋‹ค์ต์ŠคํŠธ๋ผ ์•Œ๊ณ ๋ฆฌ์ฆ˜)์€ ์Œ์˜ ๊ฐ€์ค‘์น˜๊ฐ€ ์—†๋Š” ๊ทธ๋ž˜ํ”„์—์„œ ํ•œ ๋…ธ๋“œ์—์„œ ๋‹ค๋ฅธ ๋ชจ๋“  ๋…ธ๋“œ๊นŒ์ง€์˜ ๊ฐ€์žฅ ์งง์€ ๊ฑฐ๋ฆฌ๋ฅผ ๊ตฌํ•˜๋Š” ์•Œ๊ณ ๋ฆฌ์ฆ˜ ์ค‘ ํ•˜๋‚˜์ด๋‹ค. ์„ ํ˜•๊ตฌ์กฐ๋กœ ๊ตฌํ˜„๋œ ๋‹ค์ต์ŠคํŠธ๋ผ ์•Œ๊ณ ๋ฆฌ์ฆ˜์€ O(N^2)์˜ ์‹œ๊ฐ„๋ณต์žก๋„๋ฅผ ๊ฐ€์ง€์ง€๋งŒ ํž™์„ ์ด์šฉํ•ด ๊ตฌํ˜„ํ•˜๊ฒŒ ๋˜๋ฉด O(NlogN)์˜ ์‹œ๊ฐ„๋ณต์žก๋„๋ฅผ ๊ฐ€์ง€๊ฒŒ ๋œ๋‹ค. ์ตœ๋‹จ ๊ฑฐ๋ฆฌ๋ฅผ ๊ตฌํ•˜๋Š” ๊ฒฝ์šฐ๋Š” ํ˜„์‹ค์—์„œ๋„ ํ”ํ•˜๊ธฐ ๋•Œ๋ฌธ์— ๋งŽ์ด ์‚ฌ์šฉ๋˜๋Š” ์•Œ๊ณ ๋ฆฌ์ฆ˜์ด๋‹ค.