หนึ่งในหน้าที่หลักๆ ของระบบปฏิบัติการ (OS) คือควบคุมการใช้เมมโมรี่ของโปรแกรมต่างๆ ที่รันอยู่ในเครื่อง เพราะทุกโปรแกรมล้วนต้องการพื้นที่สำหรับเก็บตัวแปรเวลาทำงานทั้งนั้น

แต่วันนี้ที่เราจะมาพูดถึงหลักๆ กันจะโฟกัสที่เรื่องของ Paging หรือการแบ่งเมมโมรี่ออกเป็นเพจๆ ของOS

Background .. ก่อนเข้าเรื่อง รู้หน่อยก็ดีนะ

ก่อนจะพูดถึงเรื่องเพจกัน มาทบทวนการทำงานระหว่าง CPU - Main Memory (RAM) - Secondary Memory (Hard Disk) กันหน่อย ถือเป็นความรู้พื้นฐานที่ต้องใช้เลยนะ ใครรู้แล้วข้ามๆ ไปหัวข้อถัดไปเลยนะ

โครงสร้างหลักๆ ของคอมพิวเตอร์แบ่งเป็น 3 ส่วนคือ CPU (สมอง) - Memory (ความจำ) - I/O (input/output แต่ในที่นี้จะโฟกัสแค่ HDD)

ทั้งสามส่วนจะทำงานประสานกัน แต่ละอย่างเก่งกันคนละอย่าง ... CPU คิดเก่ง ระ..เร็ว! แต่ความจำปลาทอง ... Memory หน่วยความจำหลัก เก็บข้อมูลได้พอสมควร แต่ความเร็วพอทัดเทียบกับ CPU ... แต่ทั้ง CPU/Memory ก็มีข้อเสียอย่างหนึ่งคือมันต้องการไฟฟ้าในการทำงาน แถมราคาก็แพง ดังนั้นเราเลยต้องการ HDD หน่วยความจำรองราคาถูก (ถูกกว่า!) ที่เก็บข้อมูลได้มากมาย และข้อมูลพวกนั้นไม่หายไปแม้จะไฟดับก็ตาม

ในบทความนี้เราจะพูดถึงเรื่องหน่วยความจำเป็นหลัก งั้นขอเปรียบเทียบขนาดของหน่วยความจำของทั้ง 3 เป็นแบบนี้

เห็นชัดๆ เลยว่าพื้นที่ของ CPU นี่มันห้องเก็บของไซส์มินิชัดๆ ส่วน Main Memory ก็ใหญ่ถึงมาหน่อยเป็นระดับโกดังเล็กๆ ส่วนถ้าอยากได้พื้นที่ใหญ่โตเป็นสนามฟุตบอลก็ต้องนี่เลย HDD (ส่วนความเร็วในการทำงานก็จะกลับกันเลยนะ เพราะในโลกของคอมพิวเตอร์ ยิ่งเก่งอะไรมากๆ เรื่องอื่นๆ ก็จะอ่อนมากๆ เช่นกัน)

เอาล่ะ งั้นขอถามหน่อย เวลาเราจะอินสตอลโปรแกรมลงเครื่อง คิดว่าไฟล์โปรแกรมพวกเนี้ย จะถูกเขียนลงไปในหน่วยความจำไหนกัน?

คำตอบคือ Secondary Memory นะ เหตุผลคือ เพราะถ้าเราวางไว้ใน CPU ที่ขนาดเล็กซะ! คงไม่มีพื้นที่เพียงพอ

จะวางใน Main Memory ก็ไม่ได้เพราะถ้าปิดคอม ไฟฟ้าหาย ไฟล์โปรแกรมก็หายไปด้วย

ดังนั้นเวลาเราลงโปรแกรม ไฟล์พวกนี้จะถูกเขียนลงไปใน HDD นะ

แต่! เราเรียนกันมาตั้งแต่ในวิชา Computer Architecture แล้วว่าการทำงานของโปรแกรม จะต้องโหลดไฟล์โปรแกรมเข้าเมมโมรี่หลักซะก่อน ก็คือการ "Copy" ไฟล์ตรงๆ ชุดเดียวกันเลยนั่นแหละ นี่เป็นเหตุผลว่าทำไมเวลาเราเปิดโปรแกรมใหญ่ๆ เช่น Photoshop, Android Studio อะไรพวกนี้ มันถึงต้องโหลดโปรแกรม น๊าน~นาน

ใครจำ Architect ไม่ได้ยกมือขึ้นซิ! ถ้าอยากจำได้กลับไปอ่านที่ http://www.tamemo.com/post/98/ เลยนะ

Process vs. Program

สำหรับคนทั่วๆ ไป เราก็เรียกว่าโปรแกรมธรรมดาแหละ แต่ในวิชา OS เราจะแยกมันออกเป็น Program และ Process โดย

• Program - คือข้อมูลไฟล์โปรแกรมต้นฉบับ ที่ได้มาจากการกดอินสตอล
• Process - คือข้อมูลไฟล์โปรแกรมเหมือนกันนั่นแหละ แต่เราจะเรียกว่าโปรเซสก็ต่อเมื่อมันถูก copy เข้าไปอยู่ใน Main Memory แล้วเท่านั้น (แปลว่าพร้อมรัน ทำงานได้ไงล่ะ)

เมื่อไฟล์โปรแกรมมาอยู่ในเมมโมรี่หลักแล้วมันก็พร้อมที่จะทำงานแล้ว การทำงานก็จะเอาข้อมูลสลับๆ วิ่งไปวิ่งมาระหว่างเมมโมรี่หลักและ CPU ไปเรื่อยๆ จนกว่าจะจบโปรแกรม ... อ้อ ลืมบอกไปไฟล์ข้อมูลโปรแกรมในที่นี้รวมทั้ง data (ก็คือพวกตัวแปร) และ instruction (คือคำสั่งโปรแกรม)

จบพาร์ทรีวิวทวนความจำ! ต่อไปเราจะมาเข้าเนื้อหากัน!! (เพิ่งจะเข้าเรอะ?)

How CPU access data...เอาตัวแปร X มาซิ!

ตัวแปรทุกตัวที่เราประกาศเวลาเขียนโปรแกรม ต้องการที่อยู่ ส่วนต้องการขนาดไหนก็ถึงอยู่กับ type ของตัวแปรและภาษาโปรแกรม เช่น

int x; - การสั่งแบบนี้ในภาษาซี (Turbo C Compiler) หมายความว่าต้องเตรียมพื้นที่จำนวน 2 bytes (16-bits) ไว้ให้มัน แต่ถ้าเป็นภาษาจาว่าต้องเตรียมถึง 4 bytes (32-bits) เลยนะ

นอกจากขนาดของตัวแปรที่เราต้องรู้ (เมมโมรี่จะได้จัดช่องให้ถูก) มันยังต้องการอื่นอย่าง นั่นคือ...

address (หรือ index)

address ทำหน้าที่อะไร? มันคงไม่ดีมั้ง ถ้าคุณบอก RAM ว่าฉันต้องการพื้นที่ 4 bytes สำหรับเก็บตัวแปร x, RAM บอกว่า โอเค ส่งมาเลย ฉันเก็บให้ แต่ฉันไม่รู้นะ ว่าค่าที่ฉันเก็บเข้าไปเนี่ย มันชื่อว่าอะไร ... ดังนั้นงานเลยเข้าเมื่อ CPU อยากได้ตัวแปร x กลับไปใช้อีกรอบ แต่เมื่อบอก RAM ไปว่า "ขอ x หน่อยซิ" RAM ดันบอกว่า "ฉันไม่รู้จักหรอก เอ็กซ์เอิ๊กซ์อะไรกัน บอกมาเป็น address ได้มั้ย"

สรุปคือ CPU เลยต้องมีอะไรบางอย่างที่เอาไว้บอก RAM ว่าข้อมูลที่มันอยากได้น่ะ อยู่ในตำแหน่ง address ไหนกัน

เราเรียกเจ้าสิ่งที่ใช้บอกตำแหน่งซึ่งเป็น Register ตัวหนึ่งนี้ว่า

"MAR (Memory Address Register)"

แต่สำหรับคอมพิวเตอร์ การบอกแค่ว่ามีรีจิสเตอร์สำหรับจัดการค่า address หนึ่งตัวนั้นยังไม่พอ เพราะมันต้องบอกด้วยว่าต้องการกี่ช่อง

ก่อนจะไปถึงต้องนั้น มาคิดกันแบบง่ายๆ ก่อนนะ สมมุติว่าเราจะส่งจดหมายไปหาบ้านหลายๆ หลัง ถ้ามีช่องให้เรากรอกบ้านเลขที่อยู่ 3 ช่อง มีบ้านกี่บ้านที่เราสามารถอ้างถึงได้มากที่สุด?

 

(คิดในมุมมองของเลขฐาน10นะ) มีช่อง 3 ช่อง ถ้าเราไล่เลขทุกความน่าจะเป็น เราจะได้เลขตั้งแต่ 000, 001, 002, 003, 004, 005, 006, 007, 008, 009, 010, 011, 012, 013, ... 997, 998, 999 รวมทั้งหมด 1000 ตัวเลข แปลว่าในระบบตัวเลข 3 ช่องจะมีบ้านแค่หนึ่งพันหลังเท่านั้นที่เราอ้างถึงได้ ในเคสนี้ถ้าจะอ้างถึงบ้านหลังที่ 1032 จะไม่สามารถทได้เลย

โอเค ด้านคอมพิวเตอร์ก็คิดคล้ายๆ กันแบบนี้นั่นแหละ แต่ระบบเลขจะเป็นฐาน2แทน ส่วน "ช่อง" ทีพูดถึงเมื่อกี่เราจะเรียกใหม่ว่า "bit" แทน

• 1-bit: อ้างเลขได้ 0, 1 รวม 2 ตัว
• 2-bits: อ้างเลขได้ 00, 01, 10, 11 รวม 4 ตัว
• 3-bits: อ้างเลขได้ 000, 001, 010, 011, 100, 101, 110, 111 รวม 8 ตัว

ถ้าลองไล่เลขดูจากเคสพวกนี้เราจะได้สูตรความสัมพันธ์ระหว่างจำนวน bit กับสิ่งที่มันอ้างถึงได้

x-reference-bit ---> อ้างถึงสิ่งของได้ 2^x ชิ้น

bit กับ byte

มาถึงตรงนี้ต้องอธิบายเรื่อง หน่วย (unit) กันหน่อย เพราะสำหรับ MAR การนับว่าต้องใช้กี่ช่องจะนับกันเป็น bit

แต่หน่วย bit เนี่ยมันเล็กมากนะ ก็คิดง่ายๆ ว่า 1-bit เก็บได้แค่ 0 กับ 1 สองตัวเท่านั้น หน่วยสำหรับ Main Memory เลยนิยมใช้ใหญ่กว่านั้นซึ่งส่วนใหญ่จะใช้หน่วย byte (8-bits = 1 byte) ดังนั้นวิธีการวาง address ของเมมโมรี่จะอ้างทีละ byte เช่นเราบอก RAM ว่าขอข้อมูล address=0 ออกมาซิ สิ่งที่เราจะได้ไม่ใช่ข้อมูลแค่ 1-bit แต่จะได้ออกมา 1 byte เลย

Note: การเขียนตัวย่อหน่วย bit/byte จะใช้ตัว b (bit) และตัว B (byte) เช่นการบอกว่า 32MB หมายความว่า 32-mega byte แต่ถ้าบอกว่า 32Mb หมายถึง 32-mega bit นะ

 

ตัวอย่าง1 มีเมมโมรี่ขนาด 100 bytes ต้องใช้ MAR ขนาดกี่ bit เพื่อจะให้ reference ไปยังเมมโมรี่ทุก address ได้ครบ?

- ถ้าใช้ MAR ขนาด 6-bits เราจะอ้างเมมโมรี่ได้ทั้งหมด 2⁶ = 64 address แปลว่ายังไม่พอ!

- ถ้าใช้ MAR ขนาด 7-bits เราจะอ้างเมมโมรี่ได้ทั้งหมด 2⁷ = 128 address นั่นเกิน 100 ช่องที่เราต้องการไปแล้ว แต่ถ้าจะใช้ ก็ต้องใช้ 7 นี่แหละ

 

ตัวอย่างที่2 MAR ขนาด 32-bits สามารถ reference เมมโมรี่ได้ทั้งหมดกี่ address ?

- อันนี้ง่ายหน่อย ก็ตามสูตรเลย คือ 32-reference-bit = 2³² reference points --> 2³² bytes --> 4GB

วิธีแปลง 2 ยกกำลังแบบง่ายๆ ให้คิดแบบนี้ ... 32 คือ 30 + 2

• 10 มีค่าเท่ากับ K
• 20 มีค่าเท่ากับ M
• 30 มีค่าเท่ากับ G
• 40 มีค่าเท่ากับ T

ดังนั้น 30 + 2 จะมีค่าเท่ากับ G + 2² = 4GB

Fragmentation ปัญหาช่องว่างเกมเตอติส

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

ปัญหานี้ ถ้าใครชอบเล่นเกมเตอติส น่าจะพอนึกออกนะ (ฮา) เพราะปัญหา Fragmentation นี้ก็เหมือนกับสิ่งที่ทำให้เรา Game Over ในเกมเตอติสเลย

แบ่งเมมโมรี่ออกเป็นส่วนๆ

ผลจากการเล่นเตอติสจองเมมโมรี่แบบตามใจฉัน ทำให้ OS ปวดหัวกับการจัดการพื้นที่ จึงมีแนวคิดใหม่เกิดขึ้นคือ

"เราจะไม่ขายปลีกแล้ว เราจะขายส่งอย่างเดียว"

ผลก็คือช่องต่างๆ ของเมมโมรี่จะถูกแบ่งออกเป็นส่วนๆ ที่เรียกว่า Frame ซึ่งทุกเฟรมจะมีขนาดเท่ากัน แต่ขนาดเท่าไหร่นั้นขึ้นอยู่กับ OS จะเลือกใช้

ตัวอย่างนี้ เราแบ่งเมมโมรี่ออกเป็นเฟรม เฟรมละ 8 ช่อง (size=8) เรียกว่า เฟรม0 เฟรม1 เฟรม2 ... ไปเรื่อยๆ

ในที่นี้จะมีคีย์เวิร์ดใหม่เพิ่มเข้ามาอีกตัวคือ offset หรือ displacement ซึ่งเป็นตัวแทนของ address แต่อ้างอิงจากภายในตัวเฟรมเป็นหลัก (ดูในรูปนะ)

แต่สำหรับมุมมองของโปรแกรม OS จะสร้างมุมมองที่เรียกว่า Logical Address ขึ้นมา

ตัวอย่างเช่น โปรแกรมของเราต้องการใช้พื้นที่ทั้งหมด 27 byte -> แต่เฟรมหนึ่งเก็บได้แค่ 8 byte เราเลยต้องใช้ 4 เฟรมเพื่อเก็บข้อมูลของโปรแกรมนี้

แต่เพื่อเพิ่มความซับซ้อน (เหรอ?) ถ้าเรียก Frame อย่างเดียวอาจจะมีการสับสนว่าตอนนี้หมายถึงเฟรมใน Physical หรือเฟรมใน Logical เขาเลยเปลี่ยนชื่อเรียกใหม่โดยการเรียกว่า Frame จะเรียกเฉพาะส่วนที่เป็น Physical เท่านั้น ถ้าอยู่ใน Logical (ซึ่งจริงๆ มันก็คือเฟรมนั่นแหละ แต่ว่า) เราจะเรียกมันว่า Page แทน

แล้วจะแบ่งทำไมล่ะ?

พอแบ่งเมมออกเป็น Page/Frame ทำให้ OS สามารถจัดการเมมโมรี่ได้โดยไม่ต้องอิงกับ RAM ที่มีจริงๆ เช่น

• โปรแกรมทั้งหมดต้องการพื้นที่ 7 pages ถ้า RAM จริงๆ มีขนาด 7 frames ก็ไม่มีปัญหา มันเท่ากันพอดี
• โปรแกรมทั้งหมดต้องการพื้นที่ 4 pages ถ้า RAM จริงๆ มีขนาด 10 frames อันนี้ก็ยิ่งไม่มีปัญหา แต่พื้นที่ใน RAM จะเหลือทิ้งไม่ได้ใช้ไปนิดหน่อย
• โปรแกรมทั้งหมดต้องการพื้นที่ 10 pages ถ้า RAM จริงๆ มีขนาด 4 frames อันนี้ล่ะ มีปัญหาแน่นอนเท่าพื้นที่จริงน้อยกว่าพื้นที่ที่โปรแกรมใช้ (วิธีแก้คือ OS จะทำการ "Page Swapping" แต่เราจะยังไม่พูดถึงในบทความนี้)

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

จึงเป็นหน้าที่ของ OS ที่จะตัดส่วนของโปรแกรมพวกนี้ให้อยู่บนพื้นที่ต่างๆ ตามความเหมาะสม (แต่หลอกโปรแกรมว่าข้อมูลของพวกแกน่ะ ยังอยู่ติดกันดีอยู่นะ)

ตัวอย่างเช่น

- โปรแกรมต้องการพื้นที่เก็บตัวแปร A, B, C, D, E, F, G ทั้งหมด 7 ตัว สมมุติว่าตัวละ 1 byte = 7 bytes

- แปลว่าโปรแกรมนี้จะถูกแบ่งออกเป็น Page รวมทั้งหมดต้องใช้ = 2 pages (7 ตัวไง ... 2 pages เก็บได้ 8 bytes)

- แต่ตอนนี้ OS อาจจะมองว่าไม่มีพื้นที่ใน RAM ขนาดเท่านี้ มันเลยตัดเพจออกจากกัน

- พอตัดออกจากกันแล้ว OS จะต้องเก็บข้อมูลไว้ด้วย ว่าส่วนที่ตัดแย่งกันน่ะ มันอยู่จริงๆ บนตำแหน่งไหนของ RAM --> เราเรียกตารางสำหรับเก็บข้อมูลตัวนี้ว่า Page Table

Ex. จากรูปข้อบน ต้องการจะ access ตัวแปร C ซึ่งในมุมมอง Logical นี้ มันอยู่ที่ตำแหน่ง logical addr: 2 --> อยากรู้ว่า physical addr. ของตัวแปร C คืออะไร

- ตำแหน่ง logical addr:2 คือ --> page: 0 / offset: 2

- อยากรู้ว่าเป็นเฟรมที่เท่าไหร่ ก็ต้องไปเปิด Page Table ดู --> ได้ว่า frame: 3 / offset: 2

- ลองไล่จากรูปข้างบน จะได้ว่า physical addr = 14

 

แต่ตัวอย่างนี้อาจจะง่ายไปหน่อย เพราะเราวาดรูปเพื่อหาคำตอบได้ (เพราะตัวเลขมันน้อยไงล่ะ ฮา) แต่ถ้าเลขมันเยอะๆ จะเกิดอะไรขึ้น ... ดูตัวอย่างต่อไป

Ex. คราวนี้มี โปรเซสอยู่ 3 ตัว อยากรู้ว่า ขนาดของ MAR ที่ใช้ reference ตำแหน่งมีขนาดเท่าไหร่ โดยกำหนดให้..

• page/frame size = 1024 byte
• จำนวนเพจต่อ 1 โปรแกรม = 5 pages
• พื้นที่ RAM จริงๆ มีขนาด 24KB

- เอาล่ะ ขั้นแรก ... หนึ่งเพจมันมีขนาด 1024 bytes --> ต้องใช้ 10-bits สำหรับอ้างอิง (ตามสูตรอ่ะนะ)

- แต่ละโปรเซสมีเพจได้ 5 เพจ --> ต้องใช้ 3-bits ในการอ้างอิง (2² อ้างอิงได้ 4 ตัว 2³ อ้างอิงได้ 8 ตัวไง เลยต้องใช้ 3-bits )

- สรุป --> MAR ของเพจต้องใช้ 3-bits + 10-bits = 13-bits

- ขนาดพื้นที่ RAM จริงๆ มี 24KB ถ้าเฟรมนึงมีขนาด 1KB (1024 bytes) --> มีเฟรมทั้งหมด 24KB / 1KB = 24 เฟรม

- มีทั้งหมด 24 เฟรม --> ต้องใช้ 5-bits ในการอ้างอิง (2⁵ อ้างได้ 32 ตัว)

- สรุป --> MAR ของเฟรมต้องใช้ 5-bits + 10-bits = 15-bits

 

คำถามที่2 - logical addr: 1044 ของ App#0 น่ะ เท่ากับ physical addr จริงๆ มันคือตำแหน่งไหนกัน?

- ในเมื่อเพจหนึ่งเพจมีขนาด 1024 --> 1044 เนี่ยมันก็น่าจะอยู่ในเพจที่ 1 (page 0 เริ่มที่ 0 ถึง 1023, page 1 เริ่มที่ 1024 ถึง 2047) และ offset คือ 20 (1044 - 1024 = 20)

- ดูจาก Page Table แล้ว page 1 -> frame 3

- ลองไล่ดู เฟรม 3 จะเริ่มที่ 3 * frame size = 3 * 1024 = 3072

- แต่เป็น offset ที่ 20 เลยบวกเข้าไปอีก 20 --> 3072 + 20 = 3092

- physical addr = 3092