ออบเจ็กต์สแนปช็อตที่ใช้ร่วมกัน

Q: ข้อมูลสำคัญเกี่ยวกับ ออบเจ็กต์สแนปช็อตที่ใช้ร่วมกัน

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

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

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

ทั่วไป

หน่วยความจำร่วม (Shared Memory)ถูกแบ่งออกเป็นหลายส่วน แต่ละส่วนเก็บค่าข้อมูลเพียงค่าเดียว ในกรณีผู้เขียนคนเดียวผู้อ่านหลายคน (Single-writer multi-reader) แต่ละกระบวนการPi ได้รับตำแหน่งหน่วยความจำi ที่กำหนดให้ และมีเพียงกระบวนการนี้เท่านั้นที่ได้รับอนุญาตให้เขียนไปยังตำแหน่งหน่วยความจำนั้น อย่างไรก็ตาม ทุกกระบวนการสามารถอ่านตำแหน่งใดก็ได้ในหน่วยความจำ ในกรณีผู้เขียนหลายคนผู้อ่านหลายคน (Multi-writer multi-reader ข้อจำกัดจะเปลี่ยนไป และกระบวนการใดก็ได้สามารถเปลี่ยนแปลงตำแหน่งใดก็ได้ในหน่วยความจำ $\in$ {1,..., n } ใน ระบบที่มี nโปรเซส สามารถดำเนินการสองอย่างกับอ็อบเจ็กต์สแนปช็อตได้ คือscan()และupdate(i,v)การ ดำเนินการ scanไม่มีอาร์กิวเมนต์และส่งคืนมุมมองที่สอดคล้องกันของหน่วยความจำ การดำเนินการ update(i,v) จะอัปเดตหน่วยความจำ ที่ตำแหน่งiด้วยค่าv

การดำเนินการทั้งสองประเภทถือว่าเกิดขึ้นแบบอะตอมิก (แยกกัน) ระหว่างการเรียกโดยกระบวนการและการส่งกลับโดยหน่วยความจำ โดยทั่วไปแล้ว ในเวกเตอร์ข้อมูล ${\overline {d}}$ แต่ละรายการd สอดคล้องกับอาร์กิวเมนต์ของ การดำเนินการ อัปเดตเชิงเส้น ครั้งสุดท้าย ซึ่งจะอัปเดตส่วนkของหน่วยความจำ^[¹^]

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

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

การดำเนินการ

มีหลายวิธีในการใช้งานออบเจ็กต์สแนปช็อตที่ใช้ร่วมกัน อัลกอริทึมที่นำเสนอเป็นครั้งแรกนั้นเป็นการใช้งานหลักของออบเจ็กต์สแนปช็อต อย่างไรก็ตาม การใช้งานนี้ให้คุณสมบัติเพียงแค่ไม่ต้องล็อก เท่านั้น การใช้งานที่นำเสนอเป็นอันดับสองโดย Afek et al. ^{[ 1 ]}มีคุณสมบัติที่แข็งแกร่งกว่าที่เรียกว่าไม่ต้องรอ Fich ^[²^]ได้ให้ภาพรวมของการใช้งานอื่นๆ ไว้

อัลกอริทึมสแนปช็อต SWMR พื้นฐาน

แนวคิดพื้นฐานของอัลกอริธึมนี้คือ ทุกกระบวนการที่ดำเนินการscan()จะอ่านค่าในหน่วยความจำสองครั้ง หากอัลกอริธึมอ่านเนื้อหาในหน่วยความจำเหมือนกันสองครั้ง และไม่มีกระบวนการอื่นใดเปลี่ยนแปลงค่าในระหว่างนั้น อัลกอริธึมจึงสามารถส่งคืนผลลัพธ์ได้ กระบวนการที่ดำเนินการจะupdate(i,v)อัปเดตค่าของตนเองในหน่วยความจำเท่านั้น

ฟังก์ชัน scan() ในขณะที่เป็นจริง a[1..n] := รวบรวม; b[1..n] := รวบรวม; ถ้า (∀i∈{1, .., n} ตำแหน่ง i ไม่เปลี่ยนแปลงระหว่างการอ่านในระหว่างการเก็บรวบรวมทั้งสองครั้ง) แล้ว return b; // การรวบรวมแบบดับเบิลสำเร็จ สิ้นสุดลูป

ฟังก์ชันอัปเดต(i, v) M[i] := v; จบ

ในรูปแบบพื้นฐานมาก มันรับประกันว่าระบบจะทำงานต่อไปได้ แม้ว่าเธรดแต่ละตัวอาจหยุดทำงานเนื่องจากพฤติกรรมของแต่ละกระบวนการ กระบวนการPiสามารถป้องกันไม่ให้กระบวนการยุติการทำงานได้โดยการเปลี่ยนค่าของมันอยู่เสมอระหว่างการเก็บข้อมูลสองครั้ง ดังนั้น อัลกอริทึมนี้จึงเป็นแบบไร้ล็อกแต่ไม่ใช่แบบไร้การรอคอยเพื่อให้คุณสมบัตินี้แข็งแกร่งยิ่งขึ้น จึงไม่อนุญาตให้กระบวนการใดหยุดทำงานเนื่องจากพฤติกรรมของกระบวนการอื่น ภาพที่ 1 แสดงให้เห็นถึงปัญหา ในขณะที่P1พยายามดำเนินการกระบวนการที่สองP2 ต้องเริ่มต้นการทำงานใหม่เสมอและไม่สามารถยุติและหยุดทำงานได้scan()scan()

การใช้งาน Single-Writer Multi-Reader โดย Afek et al.

แนวคิดพื้นฐานของอัลกอริธึม swmr snapshot โดย Afek และคณะ คือ กระบวนการหนึ่งสามารถตรวจจับได้ว่ากระบวนการอื่นได้เปลี่ยนแปลงตำแหน่งหน่วยความจำของตนหรือไม่ และกระบวนการต่างๆ ช่วยเหลือซึ่งกันและกัน ในการตรวจจับว่ากระบวนการอื่นเปลี่ยนแปลงค่าหรือไม่ จะมีการแนบตัวนับไว้กับแต่ละรีจิสเตอร์ และกระบวนการจะเพิ่มค่าตัวนับทุกครั้งที่มีการอัปเดต แนวคิดที่สองคือ ทุกกระบวนการที่อัปเดตตำแหน่งหน่วยความจำของตน จะทำการดำเนินscan()การบางอย่างและให้ "มุมมองของหน่วยความจำ" ในรีจิสเตอร์ของตนแก่กระบวนการอื่นๆ กระบวนการที่กำลังสแกนสามารถยืมscanผลลัพธ์นี้และส่งคืนได้

อิงตามหน่วยความจำที่ไม่จำกัด

Using this idea one can construct a wait-free algorithm that uses registers of unbounded size. A process performing an update operation can help a process to complete the scan. The basic idea is that if a process sees another process updating a memory location twice, that process must have executed a complete, linearized, update operation in between. To implement this, every update operation first performs a scan of the memory and then writes the snapshot value atomically together with the new value v and a sequence number. If a process is performing a scan of the memory and detects that a process updated the memory part twice, it can "borrow" the "embedded" scan of the update to complete the scan operation.^[1]

function scan() // returns a consistent view of the memory for j = 1 to n do moved[j] := 0 endwhile true do a[1..n] := collect; // collects (data, sequence, view) triples b[1..n] := collect; // collects (data, sequence, view) triples if (∀j∈{1, ..., n}) (a[j].seq = b[j].seq) thenreturn (b[1].data, ..., b[n].data) // no process changed memory else for  j = 1 to n doif a[j].seq ≠ b[j].seq then // process moved if moved[j] = 1 then // process already moved before return b[j].view; else moved[j] := moved[j] + 1; endendend function

procedure update(i,v) // updates the registers with the data-values, updates the sequence number, embedded scan s[1..n] := scan; // embedded scan r := (v, r.seq = r.seq + 1, s[1..n]); end procedure

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

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

อิงตามหน่วยความจำที่มีขอบเขตจำกัด

ข้อจำกัดอย่างหนึ่งของอัลกอริธึมที่นำเสนอคือ มันอาศัยหน่วยความจำที่ไม่จำกัดเนื่องจากหมายเลขลำดับจะเพิ่มขึ้นอย่างต่อเนื่อง เพื่อเอาชนะข้อจำกัดนี้ จำเป็นต้องนำเสนอวิธีการที่แตกต่างออกไปในการตรวจจับว่ากระบวนการหนึ่งได้เปลี่ยนตำแหน่งหน่วยความจำสองครั้งหรือไม่ สำหรับทุกคู่ของกระบวนการ $\langle P_{i},P_{j}\rangle$ สื่อสารโดยใช้รีจิสเตอร์แบบเขียนตัวเดียวอ่านตัวเดียว (swsr) สองตัว ซึ่งประกอบด้วยบิตอะตอมิกสองบิต ก่อนที่กระบวนการจะเริ่มดำเนินการ "double collect" กระบวนการจะคัดลอกค่าของกระบวนการคู่ค้าไปยังรีจิสเตอร์ของตนเอง หากกระบวนการสแกนเนอร์P สังเกตเห็นหลังจากดำเนินการ "double-collect" ว่าค่าของกระบวนการคู่ค้าP เปลี่ยนแปลงไปในระหว่างนั้น แสดงว่ากระบวนการได้ดำเนินการอัปเดตบนหน่วยความจำ^{[ 1 ]}

ฟังก์ชัน scan() // ส่งคืนมุมมองที่สอดคล้องกันของหน่วยความจำสำหรับ j=1 ถึง n ทำ moved[j] := 0 สิ้นสุดในขณะที่เป็นจริงทำสำหรับ j=1 ถึง n ทำ q  := r  .p สิ้นสุด a[1..n] := collect; // รวบรวม (ข้อมูล, บิตเวกเตอร์, สลับ, มุมมอง) สามรายการ b[1..n] := collect; // รวบรวมทริปเปิล (ข้อมูล, บิตเวกเตอร์, สลับ, มุมมอง) ถ้า (∀j∈{1, ...,n}) (a[j].p  = b[j].p  = q  ) และ a[j].toggle = b[j].toggle แล้วส่งคืน (b[1].data, ..., b[n].data) // ไม่มีกระบวนการใดเปลี่ยนแปลงหน่วยความจำมิฉะนั้นสำหรับ j=1 ถึง n ทำถ้า (a[j].p  ≠ q  ) หรือ (b[j].p  ≠ q  ) หรือ (a[j].toggle ≠ b[j].toggle) แล้ว// กระบวนการ j ทำการอัปเดตถ้า moved[j] = 2 แล้ว // กระบวนการ นั้นได้ย้ายมาก่อนแล้วส่งคืน b[j].view; มิฉะนั้น moved[j] := moved[j] + 1; สิ้นสุดฟังก์ชัน

อัปเดต ขั้นตอน ( i , v ) // อัปเดตรีจิสเตอร์ด้วยค่าข้อมูล "สถานะการเขียน" ของรีจิสเตอร์ทั้งหมด กลับบิตสลับ และสแกนแบบฝังสำหรับ j = 1 ถึง n ทำ f[j] := ¬q สิ้นสุด s[1..n] := scan; // สแกนแบบฝัง r  := (v, f[1..n], ¬r  .toggle, s[1..n]); สิ้นสุดขั้นตอน

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

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

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

การใช้งานระบบเขียนหลายคนอ่านหลายคนโดย Afek และคณะ

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

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

หากการเรียกใช้ double-collect ล้มเหลว จำเป็นที่กระบวนการหนึ่งจะต้องเห็นกระบวนการอื่นเคลื่อนไหวสามครั้งก่อนที่จะยืมการสแกนแบบฝังตัว ภาพที่ 3 แสดงให้เห็นถึงปัญหา การเรียกใช้ double-collect ครั้งแรกล้มเหลว เนื่องจากupdateกระบวนการที่เริ่มต้นก่อนการดำเนินการสแกนเสร็จสิ้นการเขียนหน่วยความจำในระหว่างการเรียกใช้ double-collect ครั้งแรก อย่างไรก็ตาม การสแกนแบบฝังตัวของการเขียนนี้ได้ถูกดำเนินการและบันทึกไว้ก่อนที่P1 เริ่มสแกนหน่วยความจำ ดังนั้นจึงไม่มีจุด Linearization ที่ถูกต้อง การเรียกใช้ double-collect ครั้งที่สองล้มเหลว เนื่องจากกระบวนการP2 เริ่ม เขียนครั้งที่สองและอัปเดตบิต handshake ในสถานการณ์ swmr เราจะยืมการสแกนแบบฝังตัวและส่งคืน ในสถานการณ์ mwmr สิ่งนี้เป็นไปไม่ได้ เนื่องจากสแกนแบบฝังตัวจากครั้งที่สองwriteยังไม่ได้รับการทำให้เป็นเชิงเส้นภายในช่วงเวลาการสแกน (เริ่มต้นและสิ้นสุดของการดำเนินการ) ดังนั้น กระบวนการจะต้องเห็นการเปลี่ยนแปลงครั้งที่สามจากกระบวนการอื่นเพื่อให้แน่ใจอย่างสมบูรณ์ว่าอย่างน้อยหนึ่งการสแกนแบบฝังตัวได้รับการทำให้เป็นเชิงเส้นในช่วงเวลาการสแกนแล้ว หลังจากการเปลี่ยนแปลงครั้งที่สามโดยกระบวนการหนึ่ง กระบวนการสแกนสามารถยืมค่าหน่วยความจำเก่าได้โดยไม่ละเมิดเกณฑ์การทำให้เป็นเชิงเส้น

ความซับซ้อน

การใช้งานพื้นฐานของอ็อบเจ็กต์สแนปช็อตที่ใช้ร่วมกันซึ่งนำเสนอโดย Afek et al. จำเป็นต้องมี $O(n^{2})$ การดำเนินการหน่วยความจำ^{[ 1 ]}การใช้งานอีกแบบหนึ่งโดยAndersonซึ่งพัฒนาขึ้นโดยอิสระ ต้องใช้การดำเนินการจำนวนเลขชี้กำลัง $O(2^{n})$ [ ⁵^]นอกจากนี้ยังมีการใช้งานแบบสุ่มของวัตถุสแนปช็อตโดยอิงจากรีจิสเตอร์ swmr โดย^ใช้ $O(n\log ^{2}n)$ การดำเนินการ^{[ 6 ]}การใช้งานอีกแบบหนึ่งโดยชาวอิสราเอลและชิราซี โดยใช้หน่วยความจำไม่จำกัด ต้องใช้ $O(n^{3/2}\log ^{2}n)$ การดำเนินการบนหน่วยความจำ^{[ 7 ]}^{[ 8 ]} Israeli และคณะแสดงให้เห็นในงานอื่นถึงขอบเขตล่างของการดำเนินการระดับต่ำสำหรับการดำเนินการอัปเดตใดๆ ขอบเขตล่างคือ $\โอเมก้า (\min\{w,r\})$ โดยที่wคือจำนวนตัวอัปเดต และrคือจำนวนตัวสแกน Attiya และ Rachman นำเสนออัลกอริทึมสแนปช็อตแบบกำหนดได้โดยอิงจากรีจิสเตอร์ swmr ซึ่งใช้ $O(n\log n)$ การดำเนินการต่อการอัปเดตและการสแกน^{[ 8 ]}การใช้วิธีทั่วไปโดย Israeli, Shaham และ Shirazi ^{[ 9 ]}สามารถปรับปรุงให้เป็นอัลกอริทึมสแนปช็อตแบบไม่จำกัด ซึ่งต้องการเพียง $O(n\log n)$ การดำเนินการต่อการสแกนและ $O(n)$ การดำเนินการต่อการอัปเดต มีการปรับปรุงเพิ่มเติมที่นำเสนอโดย Inoue et al. ^{[ 10 ]}โดยใช้การดำเนินการอ่านและเขียนเพียงจำนวนเชิงเส้นเท่านั้น ในทางตรงกันข้ามกับวิธีการอื่นๆ ที่นำเสนอ วิธีนี้ใช้รีจิสเตอร์ mwmr และไม่ใช่รีจิสเตอร์ swmr

แอปพลิเคชัน

มีอัลกอริธึม หลายตัว ในการประมวลผลแบบกระจายซึ่งสามารถทำให้ง่ายขึ้นในการออกแบบและ/หรือการตรวจสอบโดยใช้วัตถุสแนปช็อตที่ใช้ร่วมกัน^{[ 1 ]}ตัวอย่างเช่น ปัญหาการยกเว้น^{[ 11 ]}^{[ 12 ]}^{[ 13 ]}ระบบประทับเวลาพร้อมกัน^{[ 14 ]}ข้อตกลงโดยประมาณ^{[ 15 ]}ฉันทามติแบบสุ่ม^{[ 16 ]}^{[ 17 ]}และการใช้งานโครงสร้างข้อมูลอื่นๆ ที่ไม่ต้องรอ^{[ 18 ]} ด้วยวัตถุสแนปช็อต mwmr ยังสามารถสร้าง รีจิสเตอร์ แบบหลายผู้เขียนหลายผู้อ่านแบบอะต อมิกได้อีกด้วย

ดูเพิ่มเติม

[ 1 ]

[ 2 ]

[ 3 ]

[ 4 ]

5

[ 6 ]

[ 7 ]

[ 8 ]

[ 9 ]

[ 10 ]

[ 11 ]

[ 12 ]

[ 13 ]

[ 14 ]

[ 15 ]

[ 16 ]

[ 17 ]

[ 18 ]