บทที่ 2 · Memory Management ออก

บทนี้เรียนเรื่องอะไร (ภาพรวม)

โปรแกรมจะรันได้ต้องอยู่ใน RAM แต่ RAM มีก้อนเดียว และต้องใส่หลายโปรแกรมพร้อมกัน OS จึงต้องตอบ 3 คำถาม:

1. โปรแกรมอ้างข้อมูลด้วยเลข address แบบไหน แล้วแปลงเป็นตำแหน่งจริงใน RAM อย่างไร → 2.1 address binding, 2.2 logical vs physical
2. จะวางโปรแกรมไว้ตรงไหนของ RAM ถ้าที่ไม่พอทำยังไง → 2.3–2.7 (loading/linking, overlay, swapping, partition, fit)
3. พอวางไปเรื่อยๆ แล้วที่ว่างแตกเป็นชิ้นเล็กๆ จะแก้ยังไง → 2.8 compaction และคำตอบที่ดีที่สุดคือ 2.9 paging

🤔 คืออะไร

ตอนเราเขียนโปรแกรม เราอ้างข้อมูลด้วยชื่อ เช่น ตัวแปร x หรือฟังก์ชัน sum() (เรียกว่า symbolic address) แต่ CPU ไม่รู้จักชื่อ CPU รู้จักแค่เลขช่องใน RAM (physical address)
Address binding = ขั้นตอนที่ตัดสินใจว่า "ชื่อนี้จะไปอยู่ที่ address เลขอะไร"

❓ ทำไมต้องสนใจ

เพราะตอนเขียนโปรแกรม เราไม่รู้ว่าโปรแกรมจะถูกวางไว้ตรงไหนของ RAM (ขึ้นอยู่กับว่าตอนนั้นมีที่ว่างตรงไหน) จึงต้องเลือกว่าจะ "กำหนดเลขจริง" ในจังหวะไหน ยิ่งกำหนดช้า ยิ่งยืดหยุ่น

⚙️ เส้นทางของโปรแกรม ตั้งแต่เขียนจนรัน (รูป 3.1.A)

• Compiler = แปลภาษาโปรแกรมเป็นภาษาเครื่อง ได้ object module (ยังไม่สมบูรณ์ เพราะยังเรียกฟังก์ชันของไฟล์อื่นไม่ได้)
• Linkage editor / linker = เอา object หลายไฟล์ + library มารวมเป็นไฟล์เดียวที่รันได้ (load module)
• Loader = โหลด load module จากดิสก์เข้า RAM
• ช่วงซ้ายเรียก compile time ช่วง linker/loader เรียก load time และตอนรันเรียก execution time (run time)

🔍 3 จังหวะของ binding — ใช้ตัวอย่างเดียวกัน: ตัวแปร x อยู่ห่างจากต้นโปรแกรม 200 ช่อง

ระบบปัจจุบันใช้แบบ execution time เกือบทั้งหมด เพราะยืดหยุ่นที่สุด และเป็นพื้นฐานของ swapping, paging, virtual memory ในหัวข้อต่อๆ ไป

🤔 คืออะไร

• Logical address = เลข address ที่โปรแกรม/CPUคิดว่าตัวเองใช้ ทุกโปรแกรมนับจาก 0 ของตัวเอง (เช่น x อยู่ที่ 346)
• Physical address = ตำแหน่งจริงใน RAM ที่ข้อมูลนั้นอยู่
• MMU (Memory Management Unit) = ฮาร์ดแวร์ที่แปลง logical → physical ให้อัตโนมัติทุกครั้งที่ CPU อ้าง

❓ ทำไมต้องแยกสองแบบ

1. ย้ายโปรแกรมได้: โปรแกรมไม่ต้องรู้ว่าตัวเองอยู่ตรงไหนจริง
2. ป้องกันกัน: แต่ละโปรแกรมเห็นแค่ช่วงของตัวเอง อ้างข้ามไปช่วงของโปรแกรมอื่นไม่ได้

⚙️ ทำงานยังไง (relocation register + limit register, รูป 3.1.E และ 3.1.H)

1. OS วางโปรแกรมไว้ที่ตำแหน่งเริ่ม เช่น 14000 แล้วตั้ง base (relocation) register = 14000 และตั้ง limit register = ขนาดโปรแกรม
2. CPU อ้าง logical address เช่น 346
3. ฮาร์ดแวร์ตรวจ 346 < limit ? ถ้าไม่ใช่ → trap: addressing error (กันอ้างเกินช่วงตัวเอง)
4. ถ้าผ่าน → physical = base + logical = 14000 + 346 = 14346 แล้วไปอ่าน RAM ช่องนั้น

💡 เทียบให้เห็นภาพ: หอพัก

โปรแกรมพูดว่า "ห้องที่ 346 ของฉัน" (logical) แต่ห้องแรกของมันอยู่ที่ห้องเลข 14000 ของตึก ห้องจริงจึงเป็น 14346 (physical) ส่วน limit คือ "เช่าไว้กี่ห้อง" ถ้าขอห้องเกินที่เช่า จะโดนไล่ (trap)

🤔 Dynamic loading คืออะไร

แทนที่จะโหลดทั้งโปรแกรมเข้า RAM ตั้งแต่แรก ให้โหลด main program ก่อน ส่วน subroutine (ฟังก์ชันย่อย) ค่อยโหลดตอนที่ถูกเรียกจริง ฟังก์ชันที่ไม่เคยถูกเรียก (เช่น โค้ดจัดการ error ที่นานๆ ใช้ที) ก็ไม่ต้องกินที่ใน RAM
เหมือนเกมที่โหลดด่านเฉพาะตอนเราเข้าไปเล่น ไม่ได้โหลดทุกด่านตั้งแต่เปิดเกม

🤔 Linking คืออะไร

โปรแกรมของเรามักเรียกใช้ฟังก์ชันจาก library (ชุดฟังก์ชันสำเร็จรูป เช่น printf) การ "link" คือการเชื่อมการเรียกนั้นเข้ากับโค้ดจริงของ library ซึ่งทำได้ 2 แบบ:

เทียบง่ายๆ: static = ถ่ายเอกสารบทความใส่รายงานของเราเลย ส่วน dynamic = เขียนอ้างอิงว่า "ดูที่ห้องสมุดเล่มนี้"

🤔 Overlay คืออะไร

สมัยที่ RAM เล็กมาก ถ้าโปรแกรมใหญ่กว่า RAM จะใช้วิธีแบ่งโปรแกรมเป็นส่วนที่ไม่ต้องใช้พร้อมกัน แล้วให้ผลัดกันใช้พื้นที่เดียวกัน โดยมีโปรแกรมเล็กๆ ชื่อ overlay driver คอยโหลดส่วนถัดไปทับส่วนเดิม (ผู้เขียนโปรแกรมต้องออกแบบเองว่าส่วนไหนทับกันได้ จึงยุ่งยาก)

⚙️ ตัวอย่างในชีท: two-pass assembler (รูป 3.1.B)

assembler ทำงาน 2 รอบ คือ Pass 1 (70K) แล้วจึง Pass 2 (80K) ไม่ต้องใช้พร้อมกัน ส่วนที่ต้องอยู่ตลอดคือ symbol table 30K, common routine 20K และ overlay driver 10K

ไม่ใช้ overlay = 70 + 80 + 30 + 20            = 200K
ใช้ overlay    = 30 + 20 + 10 + max(70, 80)    = 140K
ขั้นตอน: โหลด Pass1 ลงพื้นที่ overlay → ทำ pass 1 เสร็จ → overlay driver โหลด Pass2 ทับที่เดิม → ทำ pass 2

🤔 Swapping คืออะไร

ถ้า RAM ใส่ทุก process พร้อมกันไม่ได้ OS จะย้ายบาง process ออกไปพักไว้บนดิสก์ชั่วคราว (swap out) แล้วเอาอีกตัวเข้ามาแทน (swap in) พื้นที่บนดิสก์ที่ใช้พักเรียกว่า backing store

⚙️ ทำงานยังไง (ตัวอย่าง RR)

1. P1 กำลังรัน แล้ว time quantum หมด
2. OS save PCB ของ P1 แล้วคัดลอกข้อมูลของ P1 ใน RAM ไปเก็บที่ backing store (swap out)
3. OS คัดลอก P2 จาก backing store เข้า RAM (swap in) แล้ว load PCB ของ P2
4. P2 ทำงานต่อจากที่ค้างไว้ และเมื่อถึงคิวของ P1 ก็ swap กลับเข้ามาใหม่

ข้อเสีย: ช้า เพราะต้องคัดลอกข้อมูลทั้ง process ผ่านดิสก์ (โปรเซสยิ่งใหญ่ยิ่งช้า)

🤔 คืออะไร

Partition = ช่วงของหน่วยความจำที่แบ่งไว้ใช้งาน ส่วน single-partition allocation = RAM แบ่งเป็นแค่ 2 ส่วน คือส่วนของ OS กับส่วนของ user และมี user process ได้ครั้งละ 1 ตัว (แบบคอมพิวเตอร์ยุคแรก)

⚙️ วาง user ได้ 2 แบบ (รูป 3.1.D, memory 0–512K)

Low memory                 High memory
0    [   OS    ]           0    [   OS    ]
     [  User   ]  ← ต่อจาก OS     [  ว่าง   ]
     [  ว่าง   ]                 [  ว่าง   ]
512K [  ว่าง   ]           512K [  User   ]  ← ไปอยู่ท้ายสุด

• Low memory: OS อยู่ที่ address 0 แล้ว user ต่อจาก OS ทันที ที่ว่างอยู่ท้าย
• High memory: OS อยู่ที่ 0 แต่ user ไปอยู่ท้ายสุด (address สูง) ที่ว่างอยู่ตรงกลาง
• ระบบใช้ base register (execution-time binding) เพื่อย้ายตำแหน่ง user ได้ (รูป 3.1.E)
• การเว้นที่ว่างไว้ตรงกลางมีประโยชน์ เพราะ stack (โตจากบนลงล่าง) กับ heap (โตจากล่างขึ้นบน) จะได้ขยายเข้าหากันได้

🤔 คืออะไร

Multiple-partition allocation = ใส่หลาย processใน RAM พร้อมกัน โดยให้แต่ละ process ได้ช่วงที่ติดกันเป็นก้อนเดียว (contiguous) ช่วงที่ยังว่างเรียกว่า hole

⚙️ ทำงานยังไง

1. OS จดรายการ hole ที่ว่างไว้
2. process ใหม่มา → หา hole ที่ใหญ่พอ แล้ววางลงไป (เลือก hole ตามวิธี first/best/worst fit ในหัวข้อ 2.7) ส่วนที่เหลือของ hole ยังเป็น hole เล็กลง
3. ถ้าไม่มี hole ไหนพอ → process นั้นต้องรอใน job queue
4. process ทำงานจบ → คืนพื้นที่เป็น hole ถ้าติดกับ hole อื่นก็รวมเป็นก้อนเดียว แล้วลองวาง process ที่รออยู่

🔍 ตัวอย่างในชีท

หน่วยความจำ 2560K, OS ใช้ 400K (เหลือ 2160K), low memory, CPU ใช้ RR quantum = 1 ms, job queue: P1 600K/10ms, P2 1000K/5ms, P3 300K/20ms, P4 700K/8ms, P5 500K/15ms

1. เริ่ม: ใส่ P1 (400–1000K), P2 (1000–2000K), P3 (2000–2300K) เหลือ hole 260K → P4 (700K) ใส่ไม่ได้ ต้องรอ และ P5 ข้ามคิว P4 ไม่ได้ (FCFS)
2. RR วน P1, P2, P3 ทีละ 1 ms → P2 ได้รันที่เวลา 1, 4, 7, 10, 13 ครบ 5 ms → P2 จบที่ 14
3. hole 1000–2000K ว่าง → P4 ลง 1000–1700K (เหลือ hole 300K)
4. ทำต่อแบบเดียวกัน → P1 จบที่ 28 → P5 ลง 400–900K → P4 จบ 38, P3 จบ 53, P5 จบ 58

🤔 คืออะไร

เมื่อมีหลาย hole ที่ใหญ่พอ จะเลือก hole ไหน? placement strategy คือกติกาการเลือก

• First-fit: ไล่จากต้น (address ต่ำ) เจอ hole แรกที่พอ ก็ใส่เลย
• Best-fit: เลือก hole ที่เล็กที่สุดที่ยังพอ (เหลือเศษน้อยสุด) ต้องดูทุก hole ก่อน
• Worst-fit: เลือก hole ที่ใหญ่ที่สุด (เพื่อให้เศษที่เหลือใหญ่พอใช้ต่อ) ต้องดูทุก hole ก่อน

⚙️ วิธีทำโจทย์ (hole 100, 500, 200, 300, 600 / process 212, 417, 112, 426)

1. เขียน hole เรียงตาม address
2. รับ process ทีละตัวตามลำดับ แล้วเลือก hole ตามกติกา
3. ลบขนาด process ออกจาก hole นั้น (เศษที่เหลือยังเป็น hole ให้ตัวถัดไปใช้ได้)
4. ทำจนครบ ถ้าตัวไหนไม่มี hole พอ ให้เขียนว่า "ต้องรอ"

เช่น first-fit: 212 → hole 500 (เหลือ 288) · 417 → hole 600 (เหลือ 183) · 112 → hole 288 (เหลือ 176) · 426 → ไม่มีที่ ต้องรอ

🤔 Fragmentation คืออะไร

• External fragmentation = ที่ว่างรวมกันพอ แต่แตกเป็นชิ้นเล็กๆ ไม่ติดกัน จึงใส่ process ใหญ่ไม่ได้ (อาจารย์เรียกว่า "bubble")
  เช่น ว่าง 100K + 300K + 260K = 660K แต่ process ขนาด 500K ใส่ไม่ได้ เพราะไม่มีช่องไหนติดกันถึง 500K
• Internal fragmentation = ได้พื้นที่เกินที่ขอ แล้วส่วนเกินถูกทิ้งไว้ในก้อนนั้น (เกิดกับ paging: ขอ 4.5 page ก็ต้องได้ 5 page)

🤔 Compaction คืออะไร และทำงานยังไง

Compaction = ย้าย process ทั้งหลายให้ไปชิดกัน เพื่อให้ hole ทั้งหมดมารวมเป็นก้อนใหญ่ก้อนเดียว (ต้องใช้ execution-time binding จึงย้ายได้)

ก่อน (รูป 3.1.I)                   หลัง compaction
0     OS                           0     OS
400K  P5                           400K  P5
900K  ว่าง 100K                    900K  P4
1000K P4                           1600K P3
1700K ว่าง 300K                    1900K ว่าง 660K  ← รวมเป็นก้อนเดียว
2000K P3
2300K ว่าง 260K
2560K                              2560K

❌ ข้อเสีย

ช้ามาก เพราะต้อง copy ข้อมูลของทุก process ที่ย้าย เวลาโตตามปริมาณที่ต้อง copy (อาจารย์พูดถึง O(N×K)) ระหว่างนั้นระบบทำงานอื่นไม่ได้ จึงควรย้ายให้น้อยที่สุด เช่น รูป 3.1.J มี 3 วิธีที่ย้าย 600K, 400K และ 200K (ดีสุด: ย้ายแค่ P3) สุดท้ายจึงมีแนวคิดใหม่คือ paging ที่ไม่ต้องหาที่ว่างติดกันเลย

🤔 คืออะไร

Paging = ตัด logical memory ของโปรแกรมเป็นชิ้นขนาดเท่ากันเรียกว่า page และตัด RAM เป็นช่องขนาดเท่ากันเรียกว่า frame (page กับ frame ขนาดเท่ากัน) แล้วเอา page ไปใส่ frame ว่างช่องไหนก็ได้ ไม่ต้องติดกัน

❓ ทำไมต้องมี

เพื่อแก้ external fragmentation: ไม่ต้องหาที่ว่างติดกันก้อนใหญ่ ขอแค่มี frame ว่างพอก็ใส่ได้ และไม่ต้องทำ compaction

⚙️ แปลง address ยังไง (รูป 3.1.K)

เพราะ page ไปอยู่ frame ไหนก็ได้ OS จึงต้องจดไว้ใน page table ว่า "page ที่ p อยู่ frame ที่ f"

1. แยก logical address เป็น (p, d): p = page number = logical div page_size และ d = offset (ตำแหน่งในหน้า) = logical mod page_size
2. เปิด page table ช่องที่ p → ได้ f (frame number)
3. physical address = (f, d) = f × page_size + d (d เท่าเดิม เพราะตำแหน่งในหน้าไม่เปลี่ยน)

💡 เทียบให้เห็นภาพ: แยกหนังสือเป็นแผ่น

หนังสือ (โปรแกรม) ถูกแยกเป็นแผ่น (page) แล้วนำไปเก็บในช่องลิ้นชัก (frame) ช่องไหนก็ได้ ส่วนสมุดสารบัญ (page table) บอกว่า "แผ่นที่ 2 อยู่ลิ้นชักที่ 1" ถ้าอยากอ่าน "บรรทัดที่ 2 ของแผ่นที่ 2" ก็ไปที่ลิ้นชัก 1 แล้วอ่านบรรทัดที่ 2 (offset เท่าเดิม)

🔍 ตัวอย่างในชีท (รูป 3.1.M): memory 32 byte, page = 4 byte, page table 0→5, 1→6, 2→1, 3→2

logical 0  (A): p = 0 div 4 = 0, d = 0 mod 4 = 0 → f = 5 → 5×4 + 0 = 20
logical 5  (F): p = 1, d = 1                     → f = 6 → 6×4 + 1 = 25   ← ชีทคำนวณข้อนี้
logical 13 (N): p = 3, d = 1                     → f = 2 → 2×4 + 1 = 9

🔍 ระดับบิต (รูป 3.1.N): address 16 บิต, page = 1 KB

1. page = 1024 = 2¹⁰ → d ใช้ 10 บิตขวา และ p ใช้ 16 − 10 = 6 บิตซ้าย → มีได้ 2⁶ = 64 page (p = 0–63, d = 0–1023)
2. แปลง 1502 เป็นฐาน 2 แล้วตัดเป็น 6 | 10 บิต (ดู บทที่ 0.6)

logical 1502  = 000001 | 0111011110  → p = 1, d = 478
page_table[1] = 000110 = 6
physical      = 000110 | 0111011110  = 6×1024 + 478 = 6622