อัลกอริทึมของปีเตอร์สัน

อัลกอริทึมของปีเตอร์สัน (หรือวิธีแก้ปัญหาของปีเตอร์สัน ) เป็น อัลกอริทึม การเขียนโปรแกรมแบบขนานสำหรับการกีดกันร่วมกันที่อนุญาตให้กระบวนการสองกระบวนการขึ้นไปใช้ทรัพยากรแบบใช้ครั้งเดียวร่วมกันได้โดยไม่มีข้อขัดแย้ง โดยใช้เพียงหน่วยความจำที่ใช้ร่วมกันสำหรับการสื่อสาร เท่านั้น อัลกอริทึม นี้ได้รับการคิดค้นโดยแกรี่ แอล. ปีเตอร์สันในปี 1981 ^{[ 1 ]}อัลกอริทึมดั้งเดิมของปีเตอร์สันใช้งานได้กับกระบวนการเพียงสองกระบวนการเท่านั้น แต่สามารถขยายให้ครอบคลุมมากกว่าสองกระบวนการได้^{[ 2 ]}

อัลกอริทึม

อัลกอริทึมนี้ใช้ตัวแปรสองตัวคือflagและturnค่าflag[n]ของtrueแสดงว่ากระบวนการnต้องการเข้าสู่ส่วนวิกฤตการเข้าสู่ส่วนวิกฤตจะได้รับอนุญาตสำหรับกระบวนการ P0 หาก P1 ไม่ต้องการเข้าสู่ส่วนวิกฤตของตนเอง หรือหาก P1 ได้ให้สิทธิ์ลำดับความสำคัญแก่ P0 โดยการตั้งค่าturnเป็น0

volatile bool flag [ 2 ] = { false , false }; volatile int turn ;

P0 : flag [ 0 ] = true ; P0_gate : turn = 1 ; while ( flag [ 1 ] && turn == 1 ) { // รอแบบวน ลูป } // ส่วนวิกฤต... // สิ้นสุดส่วนวิกฤตflag [ 0 ] = false ;

P1 : flag [ 1 ] = true ; P1_gate : turn = 0 ; while ( flag [ 0 ] && turn == 0 ) { // รอแบบวน ลูป } // ส่วนวิกฤต... // สิ้นสุดส่วนวิกฤตflag [ 1 ] = false ;

อัลกอริทึมนี้ตรงตามเกณฑ์สำคัญสามประการในการแก้ปัญหาส่วนวิกฤต เงื่อนไข while ทำงานได้แม้จะมีการแย่งชิง^{[ 1 ]}

เกณฑ์ทั้งสามประการ ได้แก่การกีดกันซึ่งกันและกันความก้าวหน้า และการรอคอยที่มีขอบเขต^{[ 3 ]}

เนื่องจากturnสามารถรับค่าได้สองค่า จึงสามารถแทนที่ด้วยบิตเดียว ซึ่งหมายความว่าอัลกอริทึมต้องการหน่วยความจำเพียงสามบิตเท่านั้น^{[ 4 ]}^{: 22}

การกีดกันซึ่งกันและกัน

P0 และ P1 ไม่สามารถอยู่ในส่วนวิกฤตพร้อมกันได้ หาก P0 อยู่ในส่วนวิกฤตแล้ว เงื่อนไขต่อไปนี้flag[0]จะเป็นจริง นอกจากนี้ เงื่อนไขต่อไปนี้จะflag[1]เป็นfalse(หมายความว่า P1 ออกจากส่วนวิกฤตแล้ว) หรือturnจะเป็น0(หมายความว่า P1 กำลังพยายามเข้าสู่ส่วนวิกฤต แต่กำลังรออย่างใจเย็น) หรือ P1 อยู่ที่ป้ายกำกับP1_gate(พยายามเข้าสู่ส่วนวิกฤต หลังจากตั้งค่าflag[1]เป็นtrueแต่ก่อนที่จะตั้งค่าturnเป็น0และกำลังรออย่างยุ่งอยู่) ดังนั้น หากทั้งสองกระบวนการอยู่ในส่วนวิกฤตแล้ว เราจึงสรุปได้ว่าสถานะจะต้องเป็นไปตามflag[0]และflag[1]และturn = 0และturn = 1ไม่มีสถานะใดที่สอดคล้องกับทั้งturn = 0และturn = 1ดังนั้นจึงไม่มีสถานะใดที่ทั้งสองกระบวนการอยู่ในส่วนวิกฤตพร้อมกัน (นี่เป็นการเล่าถึงข้อโต้แย้งที่ได้รับการทำให้เข้มงวดใน Schneider 1997 ^{[ 5 ]} )

ความคืบหน้า

ความคืบหน้าถูกกำหนดไว้ดังนี้: หากไม่มีกระบวนการใดกำลังทำงานอยู่ในส่วนวิกฤต และบางกระบวนการต้องการเข้าสู่ส่วนวิกฤต เฉพาะกระบวนการที่ไม่ได้กำลังทำงานอยู่ในส่วนที่เหลือเท่านั้นที่จะมีส่วนร่วมในการตัดสินใจว่ากระบวนการใดจะเข้าสู่ส่วนวิกฤตต่อไป โปรดทราบว่าสำหรับกระบวนการหรือเธรด ส่วนที่เหลือคือส่วนของโค้ดที่ไม่เกี่ยวข้องกับส่วนวิกฤต การเลือกนี้ไม่สามารถเลื่อนออกไปได้เรื่อยๆ^{[ 3 ]}กระบวนการไม่สามารถกลับเข้าสู่ส่วนวิกฤตได้ทันทีหากกระบวนการอื่นได้ตั้งค่าแฟล็กเพื่อบอกว่าต้องการเข้าสู่ส่วนวิกฤต

การรอคอยที่ถูกจำกัด

การรอคอยแบบจำกัด หรือการข้ามแบบจำกัดหมายความว่าจำนวนครั้งที่กระบวนการหนึ่งถูกข้ามโดยกระบวนการอื่นหลังจากที่ได้แสดงความประสงค์ที่จะเข้าสู่ส่วนวิกฤตนั้น จะถูกจำกัดด้วยฟังก์ชันของจำนวนกระบวนการในระบบ^{[ 3 ]}^{[ 4 ]}^{: 11}ในอัลกอริทึมของปีเตอร์สัน กระบวนการจะไม่รอเกินหนึ่งรอบเพื่อเข้าสู่ส่วนวิกฤต

อัลกอริทึมการกรอง: อัลกอริทึมของปีเตอร์สันสำหรับกระบวนการมากกว่าสองกระบวนการ

อัลกอริทึมตัวกรองขยายอัลกอริทึมของ Peterson ไปยังกระบวนการ $N > 2$ ^{[ 6 ]} แทนที่จะใช้แฟล็กบูลีน ต้องใช้ตัวแปรจำนวนเต็มต่อกระบวนการ ซึ่งเก็บไว้ใน รีจิสเตอร์อะตอมิกแบบเขียนตัวเดียว/อ่านหลายตัว (SWMR) และ ตัวแปรเพิ่มเติมอีก $N - 1 ตัว$ ในรีจิสเตอร์ที่คล้ายกัน รีจิสเตอร์เหล่านี้สามารถแสดงในรหัสเทียมเป็นอาร์เรย์ได้ :

ระดับ : อาร์เรย์ของจำนวนเต็ม N ตัว last_to_enter : อาร์เรย์ของจำนวนเต็ม N − 1 ตัว

ตัวแปรระดับจะมีค่าได้ถึง $N - 1$ โดยแต่ละค่าแทน "ห้องรอ" ที่แตกต่างกันก่อนถึงส่วนวิกฤต^{[ 6 ]}กระบวนการจะก้าวหน้าจากห้องหนึ่งไปยังอีกห้องหนึ่ง โดยสิ้นสุดที่ห้อง $N - 1$ ซึ่งเป็นส่วนวิกฤต โดยเฉพาะอย่างยิ่ง เพื่อให้ได้ล็อก กระบวนการ $i$ จะดำเนินการ^{[ 4 ]}^{: 22}

i ← ProcessNo สำหรับ ℓ ตั้งแต่ 0 ถึง N − 1 ไม่รวม ระดับ[i] ← ℓ last_to_enter[ℓ] ← i ในขณะที่ last_to_enter[ℓ] = i และมี k ≠ i อยู่จริง โดยที่ level[k] ≥ ℓ wait

เพื่อปลดล็อกเมื่อออกจากส่วนวิกฤต กระบวนการ $i$ จะตั้งค่า level[i]เป็น −1

สามารถพิสูจน์ได้ว่าอัลกอริทึมนี้ทำให้เกิดการกีดกันซึ่งกันและกันได้ดังนี้ กระบวนการ $i$ ออกจากลูปภายในเมื่อไม่มีกระบวนการใดที่มีระดับสูงกว่าระดับ[i]ดังนั้นห้องรอถัดไปจึงว่าง หรือเมื่อi ≠ last_to_enter[ℓ]ดังนั้นกระบวนการอื่นจึงเข้าร่วมห้องรอของมัน ที่ระดับศูนย์ แม้ว่ากระบวนการทั้ง $N$ กระบวนการจะเข้าสู่ห้องรอศูนย์พร้อมกัน ก็จะมีเพียง $N$ $-$ $1$ กระบวนการเท่านั้น ที่จะดำเนินการไปยังห้องถัดไป โดยกระบวนการสุดท้ายจะพบว่าตัวเองเป็นกระบวนการสุดท้ายที่เข้าสู่ห้อง ในทำนองเดียวกัน ที่ระดับถัดไป จะมี $N$ $-$ $2$ กระบวนการดำเนินการต่อไปเรื่อย ๆจนกระทั่งที่ระดับสุดท้าย มีเพียงกระบวนการเดียวเท่านั้นที่ได้รับอนุญาตให้ออกจากห้องรอและเข้าสู่ส่วนวิกฤต ทำให้เกิดการกีดกันซึ่งกันและกัน^[⁴^]^:^22–24

แตกต่างจากอัลกอริทึม Peterson สองกระบวนการ อัลกอริทึมตัวกรองไม่รับประกันการรอคอยที่มีขอบเขต^{[ 4 ]}^{: 25–26}

ปัญหาในยุคปัจจุบัน

ในเครื่องคอมพิวเตอร์สมัยใหม่ อัลกอริทึมของปีเตอร์สัน (ดังที่แสดงไว้ที่นี่) ไม่สามารถให้การกีดกันร่วมกันได้ การประกาศเพิ่มเติมและ/หรือคำสั่งเพิ่มเติมสามารถทำให้ใช้งานได้ (แม้ว่าวิธีการที่แตกต่างกันโดยใช้คุณสมบัติของภาษาและ/หรือคำสั่งเครื่องใหม่จะสามารถบรรลุการกีดกันร่วมกันได้อย่างมีประสิทธิภาพมากขึ้น) คอมพิวเตอร์มีความซับซ้อนมากขึ้นตั้งแต่ปี 1981 พวกมันไม่ได้ดำเนินการคำสั่งแบบซิงโครไนซ์อีกต่อไป คอมไพเลอร์ส่วนใหญ่เปลี่ยนลำดับการดำเนินการในลักษณะที่สร้างผลลัพธ์เดียวกันได้เร็วขึ้น แต่พวกมันไม่ได้พิจารณาปฏิสัมพันธ์ของการดำเนินการพร้อมกันที่เข้าถึงข้อมูลเดียวกัน ซีพียูจะจัดลำดับคำสั่งใหม่ภายในไปป์ไลน์การดำเนินการ ซีพียูอ่านเนื้อหาหน่วยความจำล่วงหน้า แคชเนื้อหาหน่วยความจำ และหน่วงเวลาและรวมการเขียน คอร์ซีพียูหลายตัวสามารถเข้าถึงหน่วยความจำเดียวกันได้ด้วยความพร้อมกันอย่างแท้จริง ซีพียูหลายตัวสามารถมีแคชแยกต่างหากที่สามารถหน่วงเวลาการซิงโครไนซ์ได้ สิ่งเหล่านี้สามารถทำลายอัลกอริทึมของปีเตอร์สันได้^{[ 7 ]}เพื่อให้สามารถใช้งานการกีดกันร่วมกันได้ในสภาพแวดล้อมใหม่นี้ จึงมีการเพิ่มคำสั่งเครื่อง เช่นตัวกั้นหน่วยความจำและการดำเนินการอ่านและแก้ไขแบบอะตอมิก คำสั่งเหล่านี้ช่วยให้สิ่งต่างๆ "ตามทัน" เมื่อจำเป็น ภาษาโปรแกรมหลายภาษาได้เพิ่มคุณสมบัติที่เรียกใช้คำสั่งเหล่านี้ ในหลายภาษา การประกาศตัวแปรเป็นvolatileจะสร้างโค้ดที่สามารถทำงานได้ ซึ่งจะเข้าถึงตัวแปรนั้นอย่างระมัดระวังมากขึ้น

โดยทั่วไปแล้วไม่จำเป็นต้องใช้อัลกอริทึมของปีเตอร์สันเพื่อรับประกันการเข้าถึงแบบอะตอมิก ในโปรเซสเซอร์และระบบปฏิบัติการรุ่นก่อนๆ การปิดใช้งานการขัดจังหวะทันทีก่อนส่วนวิกฤต และเปิดใช้งานการขัดจังหวะอีกครั้งหลังจากเสร็จสิ้นก็เพียงพอแล้ว โปรเซสเซอร์สมัยใหม่ส่วนใหญ่มีคำสั่งพิเศษที่ให้วิธีการสร้าง พรีมิที ฟการซิง โครไน ซ์ได้อย่างมีประสิทธิภาพมากกว่าวิธีการใช้หน่วยความจำร่วมอย่างเดียว คำสั่งเหล่านี้ โดยการล็อกบัสหน่วยความจำสามารถใช้เพื่อรับประกันความเป็นอะตอมิกและให้การกีดกันร่วมกันในระบบมัลติโปรเซสซิงแบบสมมาตร ตัวอย่างเช่น คำสั่ง test-and-set ( XCHG) และcompare-and-swap ( CMPXCHG) บน โปรเซสเซอร์ x86และload-link/store-conditionalบนAlpha , MIPS , PowerPCและสถาปัตยกรรมอื่นๆ

ซีพียูสมัยใหม่ส่วนใหญ่จะจัดลำดับการเข้าถึงหน่วยความจำใหม่เพื่อปรับปรุงประสิทธิภาพการประมวลผล (ดูการจัดลำดับหน่วยความจำสำหรับประเภทของการจัดลำดับใหม่ที่อนุญาต) โปรเซสเซอร์ดังกล่าวจะมีวิธีการบังคับลำดับในการเข้าถึงหน่วยความจำอย่างต่อเนื่อง โดยทั่วไปผ่าน คำสั่ง memory barrierการใช้งานอัลกอริธึมของ Peterson และอัลกอริธึมที่เกี่ยวข้องบนโปรเซสเซอร์ที่จัดลำดับการเข้าถึงหน่วยความจำใหม่โดยทั่วไปแล้วจำเป็นต้องใช้การดำเนินการดังกล่าวเพื่อให้ทำงานได้อย่างถูกต้อง เพื่อป้องกันไม่ให้การดำเนินการตามลำดับเกิดขึ้นในลำดับที่ไม่ถูกต้อง การจัดลำดับการเข้าถึงหน่วยความจำใหม่สามารถเกิดขึ้นได้แม้บนโปรเซสเซอร์ที่ไม่จัดลำดับคำสั่งใหม่ (เช่น โปรเซสเซอร์ PowerPCในXbox 360 )

ดูเพิ่มเติม

เชิงอรรถ

1 2 G. L. Peterson: "ความเข้าใจผิดเกี่ยวกับปัญหาการกีดกันร่วมกัน"จดหมายการประมวลผลข้อมูล 12(3) 1981, 115–116
↑ตามที่ได้กล่าวไว้ใน Operating Systems Reviewฉบับเดือนมกราคม 1990 ("Proof of a Mutual Exclusion Algorithm", M Hofri)
1 2 3ซิลเบอร์ชาทซ์. แนวคิดระบบปฏิบัติการ: ฉบับที่เจ็ด. จอห์น ไวลีย์ แอนด์ ซันส์, 2005, หน้า 194.
1 2 3 4 5 Raynal, Michel (2012). การเขียนโปรแกรมแบบขนาน: อัลกอริทึม หลักการ และพื้นฐาน Springer Science & Business Media. ISBN 978-3642320279.
↑ FB Schneider, On Concurrent Programming , Springer Verlag, 1997, หน้า 185–196
1 2 Herlihy, Maurice ; Shavit, Nir (2012). ศิลปะแห่งการเขียนโปรแกรมมัลติโปรเซสเซอร์ . Elsevier. หน้า28–31 . ISBN 9780123977953.
↑ อัลกอริทึมในยุค 1980 เพื่อหลีกเลี่ยงสภาวะการแข่งขัน (และเหตุใดจึงล้มเหลว )

ลิงก์ภายนอก

https://elixir.bootlin.com/linux/v5.6.19/source/arch/arm/mach-tegra/sleep-tegra20.S#L120ตัวอย่างของอัลกอริทึมของ Peterson ที่เคยใช้ในเคอร์เนล Linux ( ถูกลบออกในเวอร์ชัน 5.7)

[original-1] 1 2 G. L. Peterson: "ความเข้าใจผิดเกี่ยวกับปัญหาการกีดกันร่วมกัน"จดหมายการประมวลผลข้อมูล 12(3) 1981, 115–116

[2] ตามที่ได้กล่าวไว้ใน Operating Systems Reviewฉบับเดือนมกราคม 1990 ("Proof of a Mutual Exclusion Algorithm", M Hofri)

[Silberschatz.p194-3] 1 2 3ซิลเบอร์ชาทซ์. แนวคิดระบบปฏิบัติการ: ฉบับที่เจ็ด. จอห์น ไวลีย์ แอนด์ ซันส์, 2005, หน้า 194.

[raynal-4] 1 2 3 4 5 Raynal, Michel (2012). การเขียนโปรแกรมแบบขนาน: อัลกอริทึม หลักการ และพื้นฐาน Springer Science & Business Media. ISBN 978-3642320279.

[Schneider.p185-5] FB Schneider, On Concurrent Programming , Springer Verlag, 1997, หน้า 185–196

[art-6] 1 2 Herlihy, Maurice ; Shavit, Nir (2012). ศิลปะแห่งการเขียนโปรแกรมมัลติโปรเซสเซอร์ . Elsevier. หน้า28–31 . ISBN 9780123977953.

[7] อัลกอริทึมในยุค 1980 เพื่อหลีกเลี่ยงสภาวะการแข่งขัน (และเหตุใดจึงล้มเหลว )

[ 1 ]

[ 2 ]

[ 3 ]

[ 4 ]

[ 5 ]

[ 6 ]

[ 7 ]

ไม่มีชื่อบทความ

อัลกอริทึมของปีเตอร์สัน