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

1. รายการที่ขยายออกไปสามารถแสดงใหม่ได้ในรูปแบบประวัติลำดับ (สามารถแปลงเป็นรูปแบบอนุกรมได้ )
2. ประวัติลำดับนั้นเป็นส่วนหนึ่งของรายการเดิมที่ยังไม่ได้ขยายความ

โดยไม่เป็นทางการ หมายความว่ารายการเหตุการณ์ที่ไม่ได้แก้ไขสามารถเรียงลำดับได้ก็ต่อเมื่อการเรียกใช้สามารถเรียงลำดับได้ แต่การตอบสนองบางส่วนของกำหนดการเรียงลำดับยังไม่กลับมา^{[ 1 ]}

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

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

วัตถุอะตอมสามารถเข้าใจได้ทันทีและสมบูรณ์จากคำจำกัดความเชิงลำดับของมัน ในฐานะชุดของการดำเนินการที่ทำงานพร้อมกันซึ่งปรากฏว่าเกิดขึ้นทีละอย่างเสมอ โดยไม่มีความไม่สอดคล้องกันเกิดขึ้น โดยเฉพาะอย่างยิ่ง ความสามารถในการทำให้เป็นเชิงเส้นรับประกันว่าค่าคงที่ของระบบจะถูกสังเกตและรักษาไว้โดยการดำเนินการทั้งหมด: หากการดำเนินการทั้งหมดรักษาค่าคงที่ไว้ได้ ระบบโดยรวมก็จะรักษาค่าคงที่นั้นไว้ได้เช่นกัน

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

ประวัติการทำงานคือลำดับของการเรียกใช้และการตอบสนองต่อวัตถุโดยกลุ่มของเธรดหรือกระบวนการ การเรียกใช้สามารถคิดได้ว่าเป็นการเริ่มต้นของการดำเนินการ และการตอบสนองคือสัญญาณสิ้นสุดของการดำเนินการนั้น การเรียกใช้ฟังก์ชันแต่ละครั้งจะมีการตอบสนองตามมา สิ่งนี้สามารถใช้เพื่อจำลองการใช้งานวัตถุใดๆ ก็ได้ สมมติว่าเธรดสองเธรด A และ B ต่างพยายามแย่งชิงล็อก โดยจะถอยกลับหากล็อกนั้นถูกใช้งานอยู่แล้ว สิ่งนี้จะถูกจำลองโดยการที่ทั้งสองเธรดเรียกใช้การดำเนินการล็อก จากนั้นทั้งสองเธรดจะได้รับการตอบสนอง หนึ่งสำเร็จ อีกหนึ่งไม่สำเร็จ

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

ประวัติการดำเนินการจะอยู่ในลำดับเชิงเส้นได้หากการดำเนินการที่เสร็จสมบูรณ์มีลำดับเชิงเส้นดังนี้: ${\displaystyle \sigma }$

1. สำหรับการดำเนินการที่เสร็จสมบูรณ์ทุกครั้งในนั้นการดำเนินการจะส่งคืนผลลัพธ์เดียวกันในการดำเนินการ เช่นเดียวกับการดำเนินการที่จะส่งคืนหากการดำเนินการทั้งหมดเสร็จสมบูรณ์ทีละรายการตามลำดับ${\displaystyle \sigma }$${\displaystyle \sigma }$
2. หากการดำเนินการ op ₁เสร็จสมบูรณ์ (ได้รับการตอบสนอง) ก่อนที่ op ₂จะเริ่มต้น (เรียกใช้) แสดงว่า op ₁มาก่อน op ₂ใน. ^{[ 1 ]}${\displaystyle \sigma }$

กล่าวอีกนัยหนึ่งคือ:

• การเรียกและการตอบสนองของมันสามารถจัดเรียงลำดับใหม่เพื่อให้ได้ประวัติความเป็นมาตามลำดับ
• ประวัติลำดับนั้นถูกต้องตามคำจำกัดความเชิงลำดับของวัตถุ
• หากการตอบสนองเกิดขึ้นก่อนการเรียกใช้ในประวัติเดิม การตอบสนองนั้นก็ต้องเกิดขึ้นก่อนการเรียกใช้ในการจัดลำดับใหม่ตามลำดับเช่นกัน

โปรดทราบว่าจุดสองจุดแรกในที่นี้ตรงกับความสามารถในการเรียงลำดับ : การดำเนินการดูเหมือนจะเกิดขึ้นตามลำดับบางอย่าง จุดสุดท้ายเป็นเอกลักษณ์เฉพาะของความสามารถในการเรียงลำดับเชิงเส้น และด้วยเหตุนี้จึงเป็นผลงานหลักของ Herlihy และ Wing ^{[ 1 ]}

ลองพิจารณาสองวิธีในการเรียงลำดับใหม่ของตัวอย่างการล็อกข้างต้น

การจัดลำดับการเรียกใช้ของ B ใหม่หลังจากที่ A ตอบกลับ จะทำให้ได้ประวัติการทำงานแบบเรียงลำดับ ซึ่งเข้าใจได้ง่าย เพราะการดำเนินการทั้งหมดเกิดขึ้นตามลำดับที่ชัดเจน อย่างไรก็ตาม มันไม่ตรงกับนิยามแบบเรียงลำดับของวัตถุ (มันไม่ตรงกับความหมายของโปรแกรม): A ควรจะได้รับล็อกสำเร็จ และ B ควรจะยกเลิกการทำงานในภายหลัง

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

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

ลองพิจารณาประวัติการโต้ตอบระหว่างวัตถุสองชิ้นกับตัวล็อกต่อไปนี้:

ประวัติการทำงานนี้ไม่ถูกต้อง เนื่องจากมีจุดหนึ่งที่ทั้ง A และ B ถือครองการล็อกอยู่ นอกจากนี้ยังไม่สามารถเรียงลำดับใหม่ให้เป็นประวัติการทำงานตามลำดับที่ถูกต้องได้โดยไม่ละเมิดกฎการเรียงลำดับ ดังนั้นจึงไม่สามารถทำให้เป็นลำดับเชิงเส้นได้ อย่างไรก็ตาม ภายใต้หลักการทำให้เป็นลำดับได้ การปลดล็อกของ B อาจถูกย้ายไปอยู่ก่อนการล็อกเดิมของ A ซึ่งเป็นประวัติการทำงานที่ถูกต้อง (โดยสมมติว่าวัตถุเริ่มต้นประวัติการทำงานในสถานะล็อก):

การเรียงลำดับใหม่นี้สมเหตุสมผลหากไม่มีวิธีการสื่อสารอื่นระหว่าง A และ B การทำให้เป็นเชิงเส้นจะดีกว่าเมื่อพิจารณาวัตถุแต่ละชิ้นแยกกัน เนื่องจากข้อจำกัดในการเรียงลำดับใหม่ทำให้มั่นใจได้ว่าวัตถุหลายชิ้นที่สามารถทำให้เป็นเชิงเส้นได้นั้น เมื่อพิจารณารวมกันแล้วก็ยังคงสามารถทำให้เป็นเชิงเส้นได้อยู่

นิยามของความสามารถในการทำให้เป็นเชิงเส้นนี้เทียบเท่ากับสิ่งต่อไปนี้:

• การเรียกใช้ฟังก์ชันทุกครั้งจะมีจุดปรับสมดุลเชิงเส้นณ ช่วงเวลาใดเวลาหนึ่งระหว่างการเรียกใช้และการตอบสนองของฟังก์ชันนั้น
• ฟังก์ชันทั้งหมดดูเหมือนจะเกิดขึ้นทันที ณ จุดการทำให้เป็นเชิงเส้น โดยมีพฤติกรรมตามที่ระบุไว้ในนิยามเชิงลำดับ

ทางเลือกนี้มักจะพิสูจน์ได้ง่ายกว่ามาก นอกจากนี้ยังง่ายต่อการใช้เหตุผลในฐานะผู้ใช้ ส่วนใหญ่เป็นเพราะสัญชาตญาณ คุณสมบัติของการเกิดขึ้นทันทีหรือแบ่งแยกไม่ได้นี้ นำไปสู่การใช้คำว่าอะตอมิกเป็นทางเลือกแทนคำว่า "linearizable" ที่ยาวกว่า^{[ 1 ]}

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

โปรเซสเซอร์มีคำสั่งที่สามารถใช้ในการใช้งาน อัลกอริทึม การล็อกการล็อกแบบไม่ต้องล็อก และการรอแบบไม่ต้องรอ ความสามารถในการระงับการขัดจังหวะ ชั่วคราว เพื่อให้แน่ใจว่ากระบวนการ ที่กำลังทำงานอยู่ ไม่สามารถสลับบริบทได้ก็เพียงพอแล้วสำหรับโปรเซสเซอร์เดี่ยวคำสั่งเหล่านี้ถูกใช้งานโดยตรงโดย ผู้เขียน คอมไพเลอร์และระบบปฏิบัติการแต่ก็มีการแยกย่อยและเปิดเผยออกมาเป็นไบต์โค้ดและฟังก์ชันไลบรารีในภาษาโปรแกรมระดับสูงด้วยเช่นกัน

• การอ่านและเขียนแบบอะตอมิก;
• การสลับอะตอม (คำสั่ง RDLK ในเมนเฟรม Burroughs บางรุ่น และคำสั่ง XCHG ในสถาปัตยกรรม x86 )
• ทดสอบและตั้งค่า ;
• ดึงข้อมูลและเพิ่ม ;
• เปรียบเทียบและสลับ ;
• โหลดลิงก์/จัดเก็บแบบมีเงื่อนไข

โปรเซสเซอร์ส่วนใหญ่มีการดำเนินการจัดเก็บข้อมูลที่ไม่เป็นอะตอมิกเมื่อเทียบกับหน่วยความจำ ซึ่งรวมถึงการจัดเก็บค่าหลายคำและการดำเนินการกับสตริง หากเกิดการขัดจังหวะที่มีลำดับความสำคัญสูงในขณะที่การจัดเก็บส่วนหนึ่งเสร็จสมบูรณ์ การดำเนินการนั้นจะต้องเสร็จสมบูรณ์เมื่อระดับการขัดจังหวะกลับสู่ระดับเดิม รูทีนที่ประมวลผลการขัดจังหวะจะต้องไม่แก้ไขหน่วยความจำที่กำลังเปลี่ยนแปลง สิ่งสำคัญคือต้องคำนึงถึงเรื่องนี้เมื่อเขียนรูทีนการขัดจังหวะ

เมื่อมีคำสั่งหลายคำสั่งที่ต้องดำเนินการให้เสร็จสมบูรณ์โดยไม่ถูกขัดจังหวะ จะใช้คำสั่งของ CPU ที่ปิดใช้งานการขัดจังหวะชั่วคราว ควรใช้คำสั่งนี้เพียงไม่กี่คำสั่งเท่านั้น และต้องเปิดใช้งานการขัดจังหวะอีกครั้งเพื่อหลีกเลี่ยงเวลาตอบสนองต่อการขัดจังหวะที่ไม่สามารถยอมรับได้ หรือแม้แต่การสูญเสียการขัดจังหวะ กลไกนี้ไม่เพียงพอในสภาพแวดล้อมแบบมัลติโปรเซสเซอร์ เนื่องจาก CPU แต่ละตัวสามารถแทรกแซงกระบวนการได้ไม่ว่าจะมีขัดจังหวะเกิดขึ้นหรือไม่ก็ตาม นอกจากนี้ ในกรณีที่มีไปป์ไลน์คำสั่งการทำงานที่ไม่สามารถถูกขัดจังหวะได้นั้นก่อให้เกิดความเสี่ยงด้านความปลอดภัย เนื่องจากสามารถเชื่อมโยงกันเป็นลูปไม่สิ้นสุดเพื่อสร้างการโจมตีแบบปฏิเสธการให้บริการได้เช่นเดียวกับข้อ บกพร่อง Cyrix coma

มาตรฐานCและSUSv3อนุญาตsig_atomic_tให้มีการอ่านและเขียนอะตอมิกแบบง่าย การเพิ่มหรือลดค่าไม่รับประกันว่าจะเป็นแบบอะตอมิก^{[ 3 ]}การดำเนินการอะตอมิกที่ซับซ้อนกว่านั้นมีอยู่ในC11ซึ่งให้stdatomic.hคอมไพเลอร์ใช้คุณสมบัติของฮาร์ดแวร์หรือวิธีการที่ซับซ้อนกว่าในการใช้งานการดำเนินการ ตัวอย่างเช่น libatomic ของ GCC

ชุดคำสั่ง ARMมีคำสั่งLDREXและSTREXคำสั่งที่สามารถใช้เพื่อใช้งานการเข้าถึงหน่วยความจำแบบอะตอมิกโดยใช้มอนิเตอร์พิเศษที่ใช้งานในโปรเซสเซอร์เพื่อติดตามการเข้าถึงหน่วยความจำสำหรับที่อยู่เฉพาะ^{[ 4 ]}อย่างไรก็ตาม หากมีการสลับบริบทเกิดขึ้นระหว่างการเรียกใช้LDREXและSTREXเอกสารระบุว่าSTREXจะล้มเหลว ซึ่งบ่งชี้ว่าควรลองดำเนินการใหม่ ในกรณีของสถาปัตยกรรม ARMv8-A 64 บิต จะมีคำสั่งLDXRและSTXRคำสั่งสำหรับขนาดไบต์ ครึ่งเวิร์ด เวิร์ด และดับเบิลเวิร์ด^{[ 5 ]}

วิธีที่ง่ายที่สุดในการทำให้การประมวลผลเป็นแบบเชิงเส้น (linearizability) คือการรันกลุ่มของการดำเนินการพื้นฐานในส่วนวิกฤต (critical section) จากนั้นจึงอนุญาตให้การดำเนินการที่เป็นอิสระต่อกันสามารถทับซ้อนกันในส่วนวิกฤตได้ โดยต้องไม่ละเมิดความเป็นเชิงเส้น วิธีการดังกล่าวต้องชั่งน้ำหนักระหว่างต้นทุนของการใช้ล็อก จำนวนมาก กับประโยชน์ของการเพิ่มประสิทธิภาพการประมวลผลแบบขนาน

อีกแนวทางหนึ่งซึ่งเป็นที่นิยมในหมู่นักวิจัย (แต่ยังไม่แพร่หลายในอุตสาหกรรมซอฟต์แวร์) คือการออกแบบวัตถุที่สามารถแปลงเป็นเชิงเส้นได้โดยใช้หน่วยพื้นฐานระดับอะตอมที่ฮาร์ดแวร์จัดหาให้ วิธีนี้มีศักยภาพที่จะเพิ่มประสิทธิภาพการประมวลผลแบบขนานให้สูงสุดและลดต้นทุนการซิงโครไนซ์ให้น้อยที่สุด แต่ต้องอาศัยการพิสูจน์ทางคณิตศาสตร์ที่แสดงให้เห็นว่าวัตถุทำงานได้อย่างถูกต้อง

แนวทางผสมผสานที่น่าสนใจระหว่างสองสิ่งนี้คือการสร้าง นามธรรม ของหน่วยความจำแบบธุรกรรมเช่นเดียวกับส่วนวิกฤต ผู้ใช้จะทำเครื่องหมายโค้ดแบบลำดับที่ต้องทำงานแยกต่างหากจากเธรดอื่นๆ จากนั้นการใช้งานจะทำให้มั่นใจได้ว่าโค้ดจะทำงานแบบอะตอมิก นามธรรมแบบนี้พบได้ทั่วไปเมื่อโต้ตอบกับฐานข้อมูล ตัวอย่างเช่น เมื่อใช้Spring Frameworkการใส่คำอธิบายประกอบเมธอดด้วย @Transactional จะทำให้มั่นใจได้ว่าการโต้ตอบกับฐานข้อมูลทั้งหมดที่อยู่ภายในเกิดขึ้นในธุรกรรมฐานข้อมูล เดียว หน่วยความจำแบบธุรกรรมก้าวไปอีกขั้น โดยทำให้มั่นใจได้ว่าการโต้ตอบกับหน่วยความจำทั้งหมดเกิดขึ้นแบบอะตอมิก เช่นเดียวกับธุรกรรมฐานข้อมูล ปัญหาต่างๆ เกิดขึ้นเกี่ยวกับการประกอบธุรกรรม โดยเฉพาะอย่างยิ่งธุรกรรมฐานข้อมูลและธุรกรรมในหน่วยความจำ

แนวคิดทั่วไปในการออกแบบอ็อบเจ็กต์ที่สามารถเรียงลำดับเชิงเส้นได้คือการจัดเตรียมอินเทอร์เฟซแบบ "ทั้งหมดหรือไม่มีเลย" กล่าวคือ การดำเนินการจะสำเร็จอย่างสมบูรณ์ หรือล้มเหลวและไม่ทำอะไรเลย ( ฐานข้อมูล ACIDเรียกหลักการนี้ว่าความเป็นอะตอม ) หากการดำเนินการล้มเหลว (โดยปกติเกิดจากการดำเนินการพร้อมกัน) ผู้ใช้ต้องลองใหม่อีกครั้ง ซึ่งโดยปกติแล้วจะเป็นการดำเนินการที่แตกต่างออกไป ตัวอย่างเช่น:

• การเปรียบเทียบและสลับ (Compare-and-swap)จะเขียนค่าใหม่ลงในตำแหน่งก็ต่อเมื่อค่าในตำแหน่งใหม่ตรงกับค่าเก่าที่ให้มาเท่านั้น วิธีนี้มักใช้ในลำดับการอ่าน-แก้ไข-เปรียบเทียบและสลับ (read-modify-CAS): ผู้ใช้จะอ่านตำแหน่ง คำนวณค่าใหม่ที่จะเขียน และเขียนค่าใหม่ด้วยการเปรียบเทียบและสลับ (CAS) หากค่าเปลี่ยนแปลงในเวลาเดียวกัน การเปรียบเทียบและสลับ (CAS) จะล้มเหลว และผู้ใช้จะต้องลองใหม่อีกครั้ง
• ฟังก์ชัน Load-link/store-conditionalเข้ารหัสรูปแบบนี้โดยตรงยิ่งขึ้น: ผู้ใช้จะอ่านตำแหน่งด้วย load-link คำนวณค่าใหม่ที่จะเขียน และเขียนค่านั้นด้วย store-conditional หากค่ามีการเปลี่ยนแปลงในเวลาเดียวกัน SC (store-conditional) จะล้มเหลวและผู้ใช้จะต้องลองใหม่อีกครั้ง
• ในการทำธุรกรรมฐานข้อมูลหากการทำธุรกรรมไม่สามารถเสร็จสมบูรณ์ได้เนื่องจากการดำเนินการพร้อมกัน (เช่นภาวะติดตาย ) การทำธุรกรรมจะถูกยกเลิก และผู้ใช้จะต้องลองใหม่อีกครั้ง

เพื่อแสดงให้เห็นถึงพลังและความจำเป็นของการทำให้เป็นเชิงเส้น เราจะพิจารณาตัวนับอย่างง่ายที่กระบวนการต่างๆ สามารถเพิ่มค่าได้

เราต้องการสร้างอ็อบเจ็กต์ตัวนับที่หลายกระบวนการสามารถเข้าถึงได้ ระบบทั่วไปหลายระบบใช้ตัวนับเพื่อติดตามจำนวนครั้งที่เหตุการณ์เกิดขึ้น

อ็อบเจ็กต์ตัวนับสามารถเข้าถึงได้โดยหลายกระบวนการ และมีโอเปอเรชันให้ใช้งานสองอย่าง

1. เพิ่มค่า - เพิ่มค่า 1 ให้กับค่าที่เก็บไว้ในตัวนับ และส่งการตอบรับกลับมา
2. อ่าน - ส่งคืนค่าปัจจุบันที่เก็บไว้ในตัวนับโดยไม่เปลี่ยนแปลงค่าเดิม

เราจะพยายามสร้างอ็อบเจ็กต์ตัวนับนี้โดยใช้ รีจิส เตอร์ ที่ใช้ร่วมกัน

ความพยายามครั้งแรกของเรา ซึ่งเราจะเห็นว่าไม่สามารถทำให้เป็นเชิงเส้นได้นั้น มีการใช้งานดังต่อไปนี้ โดยใช้รีจิสเตอร์ร่วมกันหนึ่งตัวระหว่างกระบวนการต่างๆ

การใช้งานแบบพื้นฐานที่ไม่คำนึงถึงอะตอม:

เพิ่มขึ้นทีละ:

1. อ่านค่าในรีจิสเตอร์ R
2. เพิ่มค่าเข้าไปอีกหนึ่ง
3. เขียนค่าใหม่กลับเข้าไปในรีจิสเตอร์ R

อ่าน:

อ่านทะเบียน R

การใช้งานแบบง่ายนี้ไม่สามารถทำให้เป็นเชิงเส้นได้ ดังที่แสดงให้เห็นในตัวอย่างต่อไปนี้

ลองนึกภาพว่ามีกระบวนการสองกระบวนการกำลังทำงานอยู่ โดยแต่ละกระบวนการเข้าถึงอ็อบเจ็กต์ตัวนับเดียวที่ถูกกำหนดค่าเริ่มต้นเป็น 0:

1. กระบวนการแรกจะอ่านค่าในรีจิสเตอร์เป็น 0
2. กระบวนการแรกจะเพิ่มค่าหนึ่งให้กับตัวนับ ค่าของตัวนับควรจะเป็น 1 แต่ก่อนที่จะเขียนค่าใหม่กลับไปยังรีจิสเตอร์เสร็จสมบูรณ์ มันอาจถูกระงับชั่วคราว ในขณะเดียวกันกระบวนการที่สองก็กำลังทำงานอยู่:
3. กระบวนการที่สองจะอ่านค่าในรีจิสเตอร์ ซึ่งยังคงเท่ากับ 0;
4. กระบวนการที่สองจะเพิ่มค่าเข้าไปอีกหนึ่ง
5. ขั้นตอนที่สองจะเขียนค่าใหม่ลงในรีจิสเตอร์ ซึ่งตอนนี้รีจิสเตอร์มีค่าเป็น 1

กระบวนการที่สองเสร็จสิ้นแล้ว และกระบวนการแรกจะดำเนินการต่อจากจุดที่หยุดไป:

1. กระบวนการแรกเขียนค่า 1 ลงในรีจิสเตอร์ โดยไม่รู้ว่ากระบวนการอื่นได้อัปเดตค่าในรีจิสเตอร์เป็น 1 แล้ว

ในตัวอย่างข้างต้น กระบวนการสองกระบวนการเรียกใช้คำสั่งเพิ่มค่า แต่ค่าของวัตถุกลับเพิ่มขึ้นจาก 0 เป็น 1 เท่านั้น แทนที่จะเป็น 2 อย่างที่ควรจะเป็น การดำเนินการเพิ่มค่าครั้งหนึ่งสูญหายไปเนื่องจากระบบไม่สามารถปรับให้เป็นเชิงเส้นได้

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

ในการสร้างออบเจ็กต์ตัวนับแบบเชิงเส้นหรือแบบอะตอมิก เราจะปรับเปลี่ยนการใช้งานก่อนหน้านี้ของเราเพื่อให้แต่ละกระบวนการ P iใช้รีจิสเตอร์ R i ของตัวเอง ซึ่งคล้ายกับวิธีการทำงานของ CRDT ตัวนับแบบเติบโตอย่างเดียว

แต่ละกระบวนการจะเพิ่มค่าและอ่านค่าตามอัลกอริทึมต่อไปนี้:

เพิ่มขึ้นทีละ:

1. อ่านค่าในรีจิสเตอร์ R i .
2. เพิ่มค่าเข้าไปอีกหนึ่ง
3. เขียนค่าใหม่กลับเข้าไปใน R i

อ่าน:

1. อ่านค่าจากรีจิ สเตอร์ R 1, R 2, ... R n
2. คืนค่าผลรวมของรีจิสเตอร์ทั้งหมด

การใช้งานในรูปแบบนี้ช่วยแก้ปัญหาที่พบในการใช้งานแบบเดิมของเรา ในระบบนี้ การดำเนินการเพิ่มค่าจะถูกทำให้เป็นเชิงเส้นที่ขั้นตอนการเขียน จุดที่การดำเนินการเพิ่มค่าเป็นเชิงเส้นคือเมื่อการดำเนินการนั้นเขียนค่าใหม่ลงในรีจิสเตอร์ R iการดำเนินการอ่านค่าจะถูกทำให้เป็นเชิงเส้นจนถึงจุดหนึ่งในระบบเมื่อค่าที่ส่งคืนโดยการอ่านเท่ากับผลรวมของค่าทั้งหมดที่เก็บไว้ในแต่ละรีจิสเตอร์ R i

นี่เป็นเพียงตัวอย่างง่ายๆ ในระบบจริง การทำงานอาจซับซ้อนกว่า และข้อผิดพลาดที่เกิดขึ้นอาจละเอียดอ่อนมาก ตัวอย่างเช่น การอ่าน ค่า 64 บิตจากหน่วยความจำ อาจถูกนำไปใช้จริงโดยการอ่านค่าจาก ตำแหน่งหน่วยความจำ 32 บิต สอง ตำแหน่งติดต่อกันหากกระบวนการอ่านเพียง 32 บิตแรก และก่อนที่จะอ่าน 32 บิตที่สอง ค่าในหน่วยความจำเกิดการเปลี่ยนแปลง ค่าที่ได้จะไม่มีทั้งค่าเดิมและค่าใหม่ แต่จะเป็นค่าที่ผสมปนเปกัน

นอกจากนี้ ลำดับการทำงานของกระบวนการต่างๆ อาจส่งผลต่อผลลัพธ์ ทำให้การตรวจจับ การจำลอง และการแก้ไขข้อ ผิดพลาดดังกล่าวทำได้ยาก

ระบบส่วนใหญ่มีคำสั่งเปรียบเทียบและสลับค่าแบบอะตอมิก ซึ่งจะอ่านค่าจากตำแหน่งหน่วยความจำ เปรียบเทียบค่ากับค่า "ที่คาดหวัง" ที่ผู้ใช้กำหนด และเขียนค่า "ใหม่" หากค่าทั้งสองตรงกัน พร้อมทั้งส่งค่ากลับว่าการอัปเดตสำเร็จหรือไม่ เราสามารถใช้สิ่งนี้เพื่อแก้ไขอัลกอริทึมตัวนับที่ไม่ใช่อะตอมิกได้ดังนี้:

1. อ่านค่าในตำแหน่งหน่วยความจำ;
2. เพิ่มค่าเข้าไปอีกหนึ่ง;
3. ใช้ฟังก์ชัน compare-and-swap เพื่อเขียนค่าที่เพิ่มขึ้นกลับเข้าไป
4. ลองใหม่อีกครั้งหากค่าที่อ่านได้จากการเปรียบเทียบและสลับไม่ตรงกับค่าที่เราอ่านได้ในตอนแรก

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

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

1. ใช้ฟังก์ชัน fetch-and-increment เพื่ออ่านค่าเดิมและเขียนค่าที่เพิ่มขึ้นแล้วกลับเข้าไป

การใช้ fetch-and-increment จะดีกว่าเสมอ (ต้องการการอ้างอิงหน่วยความจำน้อยกว่า) สำหรับอัลกอริทึมบางอย่าง เช่น อัลกอริทึมที่แสดงไว้ที่นี่ มากกว่า compare-and-swap ^{[ 6 ]}แม้ว่า Herlihy จะพิสูจน์ก่อนหน้านี้แล้วว่า compare-and-swap ดีกว่าสำหรับอัลกอริทึมอื่นๆ บางอย่างที่ไม่สามารถนำไปใช้ได้เลยโดยใช้ fetch-and-increment เพียงอย่างเดียว ดังนั้นการออกแบบ CPUที่มีทั้ง fetch-and-increment และ compare-and-swap (หรือคำสั่งที่เทียบเท่า) อาจเป็นทางเลือกที่ดีกว่าการออกแบบที่มีเพียงอย่างใดอย่างหนึ่ง^{[ 6 ]}

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

1. ทำการล็อกเพื่อป้องกันไม่ให้เธรดอื่นทำงานในส่วนวิกฤต (ขั้นตอนที่ 2–4) ในเวลาเดียวกัน
2. อ่านค่าในตำแหน่งหน่วยความจำ;
3. เพิ่มค่าเข้าไปอีกหนึ่ง;
4. เขียนค่าที่เพิ่มขึ้นกลับไปยังตำแหน่งหน่วยความจำนั้น
5. ปลดล็อก

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

• กรด
• ธุรกรรมอะตอม
• ประเภทข้อมูลที่จำลองแบบโดยปราศจากความขัดแย้ง (CRDT)
• แบบจำลองความสอดคล้อง
• อ่าน-คัดลอก-อัปเดต (RCU)
• อ่าน-แก้ไข-เขียน
• ช่วงเวลาตั้งแต่ตรวจสอบจนถึงเวลาใช้งาน

• Herlihy, Maurice P.; Wing, Jeannette M. (1987). "Axioms for concurrent objects". Proceedings of the 14th ACM SIGACT-SIGPLAN symposium on Principles of programming languages ​​- POPL '87 . หน้า  13–26 . doi : 10.1145/41625.41627 . ISBN 978-0-89791-215-0S2CID 16017451​ ​
• เฮอร์ลิฮี, มอริซ พี. (1990). ระเบียบวิธีสำหรับการนำโครงสร้างข้อมูลที่มีการทำงานพร้อมกันสูงมาใช้เล่มที่ 25 หน้า  197–206 . CiteSeerX  10.1.1.186.6400 . doi : 10.1145/99164.99185 . ISBN 978-0-89791-350-8.{{cite book}}: |journal=ละเลย ( ช่วยเหลือ )
• Herlihy, Maurice P.; Wing, Jeannette M. (1990). "Linearizability: A Correctness Condition for Concurrent Objects". ACM Transactions on Programming Languages ​​and Systems . 12 (3): 463– 492. CiteSeerX  10.1.1.142.5315 . doi : 10.1145/78969.78972 . S2CID  228785 .
• Aphyr. "แบบจำลองความสอดคล้องที่แข็งแกร่ง" . aphyr.com . Aphyr . สืบค้นเมื่อ13 เมษายน 2018 .