การกำหนดตำแหน่ง (Address Binding)
- โปรแกรมจะต้องนำเข้ามาในหน่วยความจำหลักและวางไว้ภายในกระบวนการที่เป็นตัวแทนของมันเพื่อให้มันจะทำงาน
- มีการเรียนการสอนเครื่องที่ใช้อยู่หน่วยความจำเช่นเดียวกับข้อโต้แย้งยกตัวอย่างเช่น
คำแนะนำสาขา
คำแนะนำการอ้างอิงข้อมูล
- ที่อยู่ผูกพันของคำสั่งและข้อมูลที่อยู่ในหน่วยความจำสามารถเกิดขึ้นในสามขั้นตอนที่แตกต่างกัน
Compile time: ถ้าตำแหน่งหน่วยความจำที่รู้จักกันในเบื้องต้นรหัสแน่นอนสามารถสร้างขึ้น; ต้องคอมไพล์รหัสของการเริ่มต้นที่ตั้งการเปลี่ยนแปลง
Load time: ต้องสร้างรหัส relocatable ถ้าตำแหน่งหน่วยความจำไม่เป็นที่รู้จักที่รวบรวมเวลา
Execution time: ผลผูกพันล่าช้าจนเวลาทำงานถ้ากระบวนการสามารถเคลื่อนย้ายระหว่างการดำเนินการจากหน่วยความจำส่วนหนึ่งไปยังอีก ต้องการการสนับสนุนฮาร์ดแวร์สำหรับแผนที่ที่อยู่
Logical vs. Physical addresses
- logical addressสร้างขึ้นโดย CPU,
- physical addressเป็นอยู่เห็นได้จากหน่วยหน่วยความจำ
- ที่อยู่ตรรกะและทางกายภาพเดียวกันในเวลารวบรวมและโหลดเวลาที่อยู่รูปแบบที่มีผลผูกพัน; logical (virtual) และที่อยู่ทางกายภาพที่แตกต่างกันในการดำเนินการเวลาที่อยู่โครงการที่มีผลผูกพัน
- อ้างอิงเพื่อlogical addressesที่มีการแปลโดยฮาร์ดแวร์เป็นphysical addresses
- ขนาดของพื้นที่ที่อยู่ที่โดดเด่นด้วยจำนวนบิตที่มีความจำเป็นที่จะเป็นตัวแทนอยู่ที่ใหญ่ที่สุด
- บางระบบต้นเช่นDEC PDP-11/70 สนับสนุนพื้นที่ที่อยู่ที่มีขนาดเล็กกว่าหน่วยความจำกายภาพ
- ด้วยวิธีนี้เป็นกระบวนการที่สามารถเติมให้เต็มพื้นที่ที่อยู่และจะมีห้องพักเพียงพอในหน่วยความจำหลักที่จะถือไว้ทั้งหมด
- ระบบสมัยใหม่มักจะสนับสนุนทั้ง 32 บิตหรือพื้นที่ที่อยู่ 64 บิตซึ่งมักจะมีขนาดใหญ่กว่าหน่วยความจำกายภาพ
- ในกรณีนี้เทคนิคที่เรียกว่าหน่วยความจำเสมือนเป็นสิ่งจำเป็น
- กระบวนการแต่ละคนมีพื้นที่ที่อยู่ของตัวเองเป็นอิสระจากผู้ที่เป็นกระบวนการอื่น ๆ (ยกเว้นในกรณีพิเศษบางอย่างที่กระบวนการต้องการที่จะแบ่งปันพื้นที่อยู่ของพวกเขา)
Assumption
- พื้นที่ที่อยู่ของกระบวนการมีขนาดเล็กกว่าที่มีอยู่จริงหน่วยความจำ
- กระบวนการดำเนินการต้องโหลดทั้งหมดในหน่วยความจำหลัก(ไม่มีหน่วยความจำเสมือน)
Simple Memory Management
- เทคนิคการจัดการหน่วยความจำง่ายคือ
- การจัดสรรติดกัน
- เพจง่าย
- การแบ่งกลุ่มที่เรียบง่าย
- แม้ว่าเทคนิคเหล่านี้ถูกนำมาใช้อีกต่อไปในคอมพิวเตอร์เดสก์ทอป
- พวกเขาจะยังคงใช้ใน palmtop บางฝังตัวและระบบสมาร์ทการ์ด
- พวกเขาวางพื้นสำหรับการอภิปรายที่เหมาะสมของหน่วยความจำเสมือน(บทต่อไป)
การจัดสรรที่อยู่ติดกัน(Contiguous Allocation)
- หน่วยความจำหลักมักจะแบ่งออกเป็นสองพาร์ทิชัน
ระบบปฏิบัติการถิ่นที่มักจะจัดขึ้นในหน่วยความจำน้อยinterrupt vector
ผู้ใช้กระบวนการจัดขึ้นแล้วในหน่วยความจำสูง
- กระบวนการที่ผู้ใช้แต่ละคนจะได้รับการจัดสรรว่าหน่วยความจำมากที่สุดเท่าที่จะต้องใช้
- หลุมในที่สุดจะเกิดขึ้นในหน่วยความจำ
- ระบบปฏิบัติการเก็บรักษาข้อมูลเกี่ยวกับ:
พาร์ทิชันจัดสรร
พาร์ทิชันฟรี (หลุม)
- ต้องใช้การบดอัดที่จะเปลี่ยนกระบวนการเพื่อให้พวกเขามีความต่อเนื่องกันและหน่วยความจำฟรีทั้งหมดเป็นหนึ่งในบล็อก
- ใช้ในไอบีเอ็ม OS / MVT (Multiprogramming มีจำนวนตัวแปรของงาน)
Example
หลุมปรากฏเป็นกระบวนการที่มีการสร้างและการยกเลิก ในตัวอย่างนี้เรามีทั้งหมด 6M ของหน่วยความจำฟรี แต่ไม่มีภูมิภาคที่อยู่ติดกันมีขนาดใหญ่พอสำหรับกระบวนการใหม่ นี้เรียกว่าการกระจายตัวภายนอก เราจำเป็นต้องดำเนินการบดอัด
Compaction
- เป้าหมาย
เพื่อสับเปลี่ยนหน่วยความจำเนื้อหาที่จะวางหน่วยความจำฟรีทั้งหมด
ร่วมกันในบล็อกขนาดใหญ่หนึ่ง
- ความต้องการ
กระบวนการเป็นแบบไดนามิก relocatable
- ปัญหา
ค่าใช้จ่าย
กลยุทธ์การบดอัดที่เหมาะสมเป็นเรื่องยาก(NP)
Placement Algorithm(ขั้นตอนวิธีการจัดตำแหน่ง)
- ใช้ในการตัดสินใจที่บล็อกมีอิสระที่จะจัดสรรให้กับกระบวนการ
- เป้าหมาย: เพื่อลดการใช้งานของcompaction(เสียเวลา)
ครั้งแรกพอดี: ใช้บล็อกแรกที่มีขนาดใหญ่พอ
ถัดไปพอดี: ใช้บล็อกแรกมีขนาดใหญ่พอหลังจากที่ตำแหน่งสุดท้าย
ที่ดีที่สุดพอดี: ออกจากHOLD
Comments
- ถัดไปพอดีมักจะนำไปสู่การจัดสรรบล็อกที่ใหญ่ที่สุดในตอนท้ายของหน่วยความจำ
- แรกพอดีจัดสรรโปรดปรานใกล้จุดเริ่มต้นที่มีแนวโน้มที่จะสร้างการกระจายตัวน้อยกว่าถัดไปพอดี
- การค้นหาที่ดีที่สุดเหมาะสำหรับบล็อกเล็กที่สุด: ส่วนทิ้งไว้ข้างหลังที่มีขนาดเล็กที่สุดเท่าที่ทำได้
- หน่วยความจำหลักหลุมรูปแบบได้อย่างรวดเร็วขนาดเล็กเกินไปที่จะถือกระบวนการใด ๆ : การบดอัดโดยทั่วไปที่ต้องทำบ่อยขึ้น
Hardware Support for Dynamic Partitioning
- เมื่อกระบวนการที่ได้รับมอบหมายให้ทำงานลงทะเบียนฐานได้รับเต็มไปด้วยที่อยู่ทางกายภาพเริ่มต้นของกระบวนการ
- ทะเบียนขีดจำกัด ได้รับเต็มไปด้วยช่วงของที่อยู่ตรรกะ
- เมื่อญาติที่อยู่ที่พบก็จะถูกลงทะเบียนเมื่อเทียบกับขีดจำกัด;ถ้าถูกต้องก็จะถูกเพิ่มเนื้อหาของฐานลงทะเบียนจะได้รับที่อยู่ทางกายภาพ
Simple Segmentation
- แต่ละโปรแกรมจะแบ่งออกเป็นบล็อกที่มีขนาดไม่เท่ากันเรียกว่า กลุ่ม
- ส่วนเป็นหน่วยตรรกะเช่น:
- โปรแกรมหลัก
- ขั้นตอน
- ฟังก์ชั่น
- วิธี
- วัตถุ
- สแต็ค
- อาร์เรย์
- local variables
- global variables
- บล็อกที่พบบ่อย
- ตารางสัญลักษณ์
- การแบ่งกลุ่มให้เป็นความสะดวกสบายในการจัดระเบียบเหตุผลโปรแกรมที่เป็นกลุ่ม (เช่นข้อมูลในส่วนหนึ่งของรหัสในส่วนอื่น)
การแบ่งกลุ่มจะมองเห็นโปรแกรมเมอร์
- เมื่อกระบวนการได้รับการโหลดลงในหน่วยความจำส่วนที่แตกต่างกันสามารถอยู่ที่ใดก็ได้
- แต่ละส่วนจะเต็มไปเต็มไปด้วยคำแนะนำ / ข้อมูล: ไม่มีการกระจายตัวของภายใน
- มีการกระจายตัวของภายนอก; มันจะลดลงเมื่อใช้กลุ่มเล็ก ๆ
Logical Address Used in Segmentation
- ระบบปฏิบัติการรักษาsegment tableสำหรับแต่ละขั้นตอน แต่ละรายการจะประกอบด้วย:
ฐาน - มีที่อยู่ทางกายภาพเริ่มต้นที่กลุ่มที่อาศัยอยู่ในหน่วยความจำ
ขีด จำกัด - ระบุความยาวของส่วน (สำหรับการป้องกัน) คำ
- เมื่อกระบวนการเข้าสู่รัฐวิ่งลงทะเบียน CPU ได้รับเต็มไปด้วยที่อยู่เริ่มต้นของตารางส่วนของกระบวนการ
- นำเสนอกับที่อยู่ตรรกะ (หมายเลขส่วนชดเชย) = (n, m) ดัชนี CPU (มี n) ตารางส่วนที่จะได้รับที่อยู่ทางกายภาพและเริ่มต้น k ลิตรความยาวของส่วนที่ว่า
- ที่อยู่ทางกายภาพได้โดยการเพิ่มม k (ในทางตรงกันข้ามกับเพจจิ้ง)
ฮาร์ดแวร์ยังเปรียบเทียบเมตรชดเชยลิตรกับความยาวของส่วนที่เพื่อตรวจสอบว่าที่อยู่ที่ถูกต้อง
Hardware Support for Segmentation
กระบวนการแต่ละคนมีตารางส่วนของตัวเอง
ตารางส่วนงานจะถูกเก็บไว้ในหน่วยความจำ
ฮาร์ดแวร์ MMU มี
Segment ตารางฐานลงทะเบียน (STBR): คะแนนในตารางส่วน
Hardware for Address Translation in a Segmentation System
Sharing in Segmentation Systems(ร่วมกันในระบบการแบ่งกลุ่ม)
- ส่วนที่ใช้ร่วมกันเมื่อรายการในส่วนของตาราง 2 กระบวนการที่แตกต่างชี้ไปที่สถานที่ทางกายภาพเดียวกัน
- Ex:รหัสเดียวกันของโปรแกรมแก้ไขข้อความที่สามารถใช้ร่วมกันโดยผู้ใช้หลายคน
- สำเนาเดียวเท่านั้นจะถูกเก็บไว้ในหน่วยความจำ
- แต่ผู้ใช้แต่ละคนจะยังคงต้องมีส่วนข้อมูลส่วนตัว
Sharing of Segments: A Text Editor
Placement Policy
- ที่กำหนดในหน่วยความจำจริงกระบวนการชิ้น segmentations อาศัยอยู่
- สำหรับระบบการแบ่งส่วนบริสุทธิ์
- แรกพอดีพอดีต่อไป ... เป็นไปได้ที่เป็นตัวเลือก
Advantage & Disadvantage(ข้อดีข้อเสีย)
- ข้อดี
มุมมองตรรกะ (มุมมองของโปรแกรมเมอร์) ของหน่วยความจำ
ไม่มีการกระจายตัวของภายใน
ไม่จำเป็นต้องมีการจัดสรรหน่วยความจำที่อยู่ติดกันสำหรับแต่ละขั้นตอน (cf จัดสรรที่อยู่ติดกัน)
กระบวนการอาจใช้มากกว่าหนึ่งพาร์ติชัน (เช่นส่วน)
และพาร์ทิชันเหล่านี้ไม่จำเป็นต้องต่อเนื่องกัน
- ข้อเสีย
การกระจายตัวภายนอกต้องบดอัด
Simple Paging
- แต่ละขั้นตอนจะถูกแบ่งออกเป็นชิ้นขนาดเดียวกันที่เรียกว่าหน้า
- หน่วยความจำหลักยังเป็นพาร์ทิชันคงเป็นชิ้นขนาดเท่ากัน (ที่มีขนาดค่อนข้างเล็ก) ที่เรียกว่าframes หรือ page frames
- หน้ากระบวนการจึงสามารถกำหนดให้กรอบที่มีอยู่
- ผล: กระบวนการที่ไม่จำเป็นต้องที่จะครอบครองส่วนของหน่วยความจำที่อยู่ติดกัน
- จำเป็นที่จะต้องตั้งค่าpage tableในการแปลตรรกะหน้าทางกายภาพ / ที่อยู่
- การกระจายตัวที่เป็นไปได้ภายใน (สำหรับหน้าสุดท้าย)
- ต้องการเรียกใช้กระบวนการของหน้า n ขนาดต้องไปหาเฟรมฟรี n ใด ๆ และโหลดหน้าเว็บทั้งหมด
- OS ดังนั้นความต้องการที่จะติดตามเฟรมฟรีทั้งหมดในหน่วยความจำกายภาพ
- ตอนนี้สมมติว่ากระบวนการ B เสร็จสมบูรณ์ในงานของตน
- เมื่อกระบวนการ A และ C จะถูกบล็อกเพจเจอร์โหลดกระบวนการใหม่ D ประกอบด้วย 5 หน้า
- กระบวนการ D ไม่ได้ครอบครองเป็นส่วนหนึ่งของหน่วยความจำที่อยู่ติดกัน
- ไม่มีการกระจายตัวภายนอก
- การกระจายตัวของภายในประกอบด้วยเดียวของหน้าสุดท้ายของแต่ละขั้นตอน
- ระบบปฏิบัติการในขณะนี้ต้องการที่จะรักษา (ในหน่วยความจำ) ตารางหน้าสำหรับแต่ละขั้นตอน
- การเข้ามาของตารางเพจแต่ละประกอบด้วยจำนวนเฟรมที่สอดคล้องกันหน้าตั้งอยู่ทางร่างกาย
- ตารางหน้าการจัดทำดัชนีจากจำนวนหน้าเพื่อให้ได้จำนวนเฟรม
- รายการกรอบฟรีสามารถใช้ได้สำหรับหน้าจะยังคงอยู่
Logical Address Used in Paging
- ภายในแต่ละโปรแกรมแต่ละที่อยู่ตรรกะต้องประกอบด้วยหมายเลขหน้าและชดเชยภายในหน้า
- ลงทะเบียน CPU เสมอถือที่อยู่ทางกายภาพเริ่มต้นของตารางหน้าของกระบวนการที่กำลังทำงานอยู่
- นำเสนอด้วยที่อยู่ตรรกะ (หมายเลขหน้า offset) โปรเซสเซอร์เข้าถึงตารางหน้าจะได้รับที่อยู่ทางกายภาพ (หมายเลขกรอบชดเชย)
- Ex: ถ้า 16 บิตที่อยู่มีการใช้และขนาดหน้า = 1K เราต้อง 10 บิตสำหรับ และมีการชดเชย 6 บิตสามารถใช้ได้สำหรับหมายเลขหน้า
- แล้วที่อยู่ 16 บิตที่ได้รับมีน้อยอย่างมีนัยสำคัญ 10 บิตเป็นชดเชยและ 6 บิตที่สำคัญที่สุดเป็นหมายเลขหน้าเป็นสถานที่ที่มีความสัมพันธ์กับจุดเริ่มต้นของกระบวนการ
- โดยใช้ขนาดหน้าของการใช้พลังงานของ 2, หน้าเว็บที่มองไม่เห็นโปรแกรมเมอร์คอมไพเลอร์ / ประกอบและลิงเกอร์
- การแปลที่อยู่ที่ใช้เวลาเป็นแล้วง่ายต่อการใช้ในฮาร์ดแวร์
- อยู่ตรรกะ(n,m) ได้รับการแปลเป็นที่อยู่ทางกายภาพ (k,m) โดยการจัดทำดัชนีตารางหน้าและท้ายเดียวกันชดเชยเมตรจำนวนเฟรม k
Address Translation Example
Hardware Support for Paging
กระบวนการแต่ละคนมีตารางเพจของตัวเอง
ตารางหน้าจะถูกเก็บไว้ในหน่วยความจำ
- ฮาร์ดแวร์ MMU มี
หน้าตารางฐานลงทะเบียน (PTBR): จุดตารางหน้า
Hardware for Address Translation ina Paging System
Translation Lookaside Buffer
- เพราะตารางหน้าอยู่ในหน่วยความจำหลักอ้างอิงแต่ละหน่วยความจำเสมือนเป็นสาเหตุอย่างน้อยสองหน่วยความจำกายภาพเข้าถึง
หนึ่งสามารถดึงข้อมูลรายการตารางหน้า
หนึ่งที่จะดึงข้อมูล
- ที่จะเอาชนะปัญหานี้แคชเป็นพิเศษคือการตั้งค่าสำหรับรายการตารางเพจ
เรียกว่า TLB - แปล Look aside บัฟเฟอร์
-มีรายการตารางเพจที่มีการใช้มากที่สุดเมื่อเร็ว ๆ นี้
-การทำงานคล้ายกับหน่วยความจำแคชหลัก
ค้นหาขนาน
การแปลที่อยู่
หากหน้า # ในทะเบียนสมาคม (TLB ตี) ได้รับกรอบ # ออก
มิฉะนั้น(TLB พลาด) รับกรอบ # จากตารางหน้าในหน่วยความจำ
Paging Hardware With TLB
Use of a TLB
TLB จะต้องล้างทุกครั้งที่เข้าสู่กระบวนการใหม่รัฐทำงาน
บางทีเก็บ / การโหลดข้อมูลใน TLB / จาก PCB
การปฏิบัติงานของ TLB
- กำหนดโดย
อัตราส่วนตี (%) อัตราร้อยละของเวลาที่มีจำนวนหน้าจะพบใน TLB
- หน่วยความจำที่มีประสิทธิภาพเวลาในการเข้าถึง
อัตราส่วนตี: H%
ใช้เวลาในการค้นหา TLB: และ
เวลาในการเข้าถึงหน่วยความจำ: M ns การ
Effective access time =
Actual Implementation
Motorola 68030 : 22 registers
Intel 80486, Pentium : 32 registers (claims 98% hit ratio)
- การดำเนินงานที่เกิดขึ้นจริง
โมโตโรล่า 68030: 22 ลงทะเบียน
Intel 80486, Pentium: 32 ลงทะเบียน (อ้างว่า 98% อัตราส่วนตี)
Sharing Pages
ถ้าเราแบ่งปันรหัสเดียวกันในหมู่ผู้ใช้ที่แตกต่างกันก็จะเพียงพอที่จะเก็บเฉพาะสำเนาในหน่วยความจำ
รหัสที่ใช้ร่วมกันจะต้อง reentrant (คือไม่ใช่ตัวเองแก้ไข) เพื่อให้สองหรือกระบวนการอื่น ๆ สามารถรันรหัสเดียวกัน
ถ้าเราใช้เพจจิ้งขั้นตอนการใช้งานร่วมกันแต่ละคนจะมีตารางเพจที่มีจุดเข้าเฟรมเดียวกันเพียงหนึ่งสำเนาอยู่ในหน่วยความจำหลัก
แต่ผู้ใช้แต่ละคนจะต้องมีหน้าข้อมูลส่วนตัว
โปรแกรมแก้ไขข้อความ
Placement Policy(นโยบายการจัดตำแหน่ง)
- ที่กำหนดในหน่วยความจำจริงกระบวนการ 'หน้าเว็บอาศัยอยู่
- ที่ไหนที่จะวางหน้าไม่เกี่ยวข้องตั้งแต่เฟรมหน่วยความจำทั้งหมดจะเทียบเท่า (ไม่เป็นปัญหา)
ข้อดี&ข้อเสีย
- ข้อดี
ไม่มีการกระจายตัวภายนอก
ไม่จำเป็นต้องมีการจัดสรรหน่วยความจำที่อยู่ติดกันสำหรับแต่ละขั้นตอน
กระบวนการอาจใช้มากกว่าหนึ่งพาร์ติชัน (เช่นหน้า) และพาร์ทิชันเหล่านี้ไม่จำเป็นต้องต่อเนื่องกัน
- ข้อเสีย
ยังคงมีการกระจายตัวภายใน แต่เฉพาะในหน้าสุดท้าย
Simple Segmentation and Paging Comparison(การแบ่งกลุ่มที่เรียบง่ายและเพจเปรียบเทียบ)
- การแบ่งกลุ่มต้องใช้ฮาร์ดแวร์ที่มีความซับซ้อนมากขึ้นสำหรับการแปลที่อยู่
- การแบ่งส่วนทนทุกข์ทรมานจากการกระจายตัวภายนอก
- เพจเพียงการกระจายตัวของผลผลิตภายในขนาดเล็ก
- การแบ่งกลุ่มจะมองเห็นโปรแกรมเมอร์เพจในขณะที่มีความโปร่งใส
- การแบ่งส่วนสามารถมองได้ว่าสินค้าที่นำเสนอให้กับโปรแกรมเมอร์ที่มีเหตุผลในการจัดระเบียบโปรแกรมออกเป็นกลุ่มและการใช้ที่แตกต่างกันของการป้องกัน (เช่นการดำเนินการเท่านั้นรหัส แต่อ่านเขียนข้อมูล)
สำหรับวันนี้เราต้องใช้บิตการป้องกันในรายการตารางส่วน
Combined Segmentation and Paging(รวมการแบ่งกลุ่มและเพจ)
- การรวมข้อดีของพวกเขาประมวลผลและระบบปฏิบัติการส่วนหน้า
- รวมกันอยู่หลายคน นี่คือง่ายๆ
- กระบวนการแต่ละคนมี:
ตารางส่วนหนึ่ง
หน้าตารางหลายตารางหน้าต่อหนึ่งส่วน
- ที่อยู่เสมือนประกอบด้วย:
A segment number: ใช้ในการดัชนีตารางที่มีส่วนช่วยให้รายการที่อยู่เริ่มต้นของตารางหน้าสำหรับส่วนที่
A page number: ใช้ในการดัชนีตารางหน้าเว็บที่จะได้รับจำนวนเฟรมที่สอดคล้องกัน
An offset:ใช้ในการค้นหาคำที่อยู่ในกรอบ
Address Translation in a (Simple) Combined Segmentation/Paging System(แปลที่อยู่ใน (แบบง่าย)รวมการแบ่งกลุ่ม / ระบบเพจ)
