การทดสอบและตั้งค่า (หรือการดำเนินการ RMW ของอะตอมมิกอื่นๆ) เป็นคำสั่งพิเศษบนสถาปัตยกรรมใดๆ หรือไม่

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

ฉันคิดว่าพวกเขาไม่ได้รับสิทธิพิเศษและสามารถเรียกได้ในพื้นที่ผู้ใช้ แต่ http://faculty.salina.k-state.edu/tim/ossg/IPC_sync/ts.html ดูเหมือนจะแนะนำเป็นอย่างอื่น แต่แล้ว futex(7) สามารถทำการล็อคได้โดยไม่ต้องใช้ระบบภายใต้เงื่อนไขบางประการ call ซึ่งหมายความว่าจะต้องดำเนินการคำสั่ง (เช่น test-and-set) โดยไม่มีสิทธิพิเศษ

ความขัดแย้ง? ถ้าเป็นเช่นนั้นสิ่งที่ถูกต้อง?


person flow2k    schedule 02.09.2018    source แหล่งที่มา
comment
ฉันคิดว่าคุณต้องระบุสถาปัตยกรรม CPU เท่าที่ฉันรู้ Intel ไม่มีคำสั่ง Test_and_Set (TS) Intel CPU มีอะตอมมิก แต่ขาดคำสั่งเฉพาะนั้น อาจเป็นฟิลด์ในรีจิสเตอร์/รีจิสเตอร์ควบคุมเฉพาะเครื่องและการอ่าน/การเขียนได้รับการป้องกันหรือไม่ ปิง @PeterCordes.   -  person jww    schedule 02.09.2018
comment
ใช่ ฉันเชื่อว่า x86 มีคำสั่ง comparison-swap cmpxchg ฉันจะส่ง Ping เขาได้อย่างไร?   -  person flow2k    schedule 02.09.2018
comment
คุณสามารถดึงดูดความสนใจของฉันได้โดยการโพสต์คำถามในแท็ก [assembly] :P   -  person Peter Cordes    schedule 02.09.2018
comment
@jww: x86 มี lock bts ตั้งแต่ 386 bts = ทดสอบบิตและตั้งค่า   -  person Peter Cordes    schedule 02.09.2018
comment
ขอบคุณ @ปีเตอร์ ผู้เขียนระบุคำสั่งโดยเฉพาะคือ ts คุณรู้จักส่วนโค้งที่มาจากหรือไม่? หรือพวกเขากำลังใช้ชุดคำสั่งสมมุติ?   -  person jww    schedule 02.09.2018
comment
@jww: ฉันไม่คิดว่าพวกเขากำลังพูดถึงสถาปัตยกรรมที่เฉพาะเจาะจง พวกเขากำลังพูดถึงการดำเนินการดั้งเดิม (en.wikipedia.org/wiki/Test-and -set) ไม่ว่าจะใช้งานใน asm อย่างไร ใน C ++ 11 เป็นเพียงสิ่งเดียวที่ต้องไม่มีการล็อค: C ++: โครงสร้างข้อมูลที่ไม่มีการล็อคสามารถนำไปใช้ใน C ++ ได้อย่างไรหาก std::atomic_flag เป็นอะตอมประเภทเดียวที่ไม่มีการล็อคใช่ไหม (ฉันไม่รู้คำสั่ง ts ใน ISA ใด ๆ ส่วนใหญ่เป็น LL/SC และไม่มี RMW อะตอมมิกคำสั่งเดียว) มักเรียกว่า TAS เช่นเดียวกับที่ cmpxchg ปกติคือ CAS   -  person Peter Cordes    schedule 02.09.2018
comment
ฉันสงสัยว่าพวกเขากำลังพูดถึง ISA สมมุติหรือไม่ แต่หน้าที่สูงขึ้น/หน้าก่อนหน้าบางหน้าไม่ได้แสดงนัยถึงเรื่องนั้น มันเป็น C ล้วนๆ แต่แน่นอน คุณสามารถมี ISA เส็งเคร็งสมมุติที่มีคำสั่ง TS พิเศษ (และไม่มีอะตอมมิกดั้งเดิมอื่น ๆ ) ซึ่งทำให้เป็นไปไม่ได้ที่จะเขียนโค้ดพื้นที่ผู้ใช้แบบมัลติเธรดแบบไม่มีล็อคที่ดี และยากต่อการมัลติเธรดอย่างมีประสิทธิภาพ   -  person Peter Cordes    schedule 02.09.2018


คำตอบ (1)


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

หากเป็นเช่นนั้น จะต้องมี C++11 lock-free atomic read-modify- การดำเนินการเขียนเพื่อคอมไพล์กับการเรียกของระบบ แต่ไม่ได้ใช้บน x86, ARM, AArch64, MIPS, PowerPC หรือ CPU ปกติอื่น ๆ (ลองใช้ที่ https://godbolt.org/)

นอกจากนี้ยังจะทำให้การล็อก "น้ำหนักเบา" (ซึ่งพยายามจะล็อกโดยไม่ต้องมีการเรียกระบบ) เป็นไปไม่ได้ (http://preshing.com/20111124/always-use-a-lightweight-mutex/)

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

การเข้าถึงแบบอ่านอย่างเดียวหรือเขียนอย่างเดียวมักจะเป็นแบบอะตอมมิกตามธรรมชาติในตำแหน่งที่จัดเรียงบน ISA ทั้งหมด จนถึงความกว้างที่กำหนด (เหตุใดจึงมีการกำหนดจำนวนเต็มบนตัวแปร atomic ที่จัดเรียงตามธรรมชาติบน x86) แต่ atomic RMW จำเป็นต้องมีการสนับสนุนด้านฮาร์ดแวร์


บน x86 TAS คือ lock bts ซึ่งไม่มีสิทธิพิเศษ (เอกสารประกอบสำหรับคำนำหน้า lock) x86 มีการดำเนินการอะตอมมิกอื่นๆ ให้เลือก กว้าง เช่น lock add [mem], reg/immediate, lock cmpxchg [mem], reg และแม้กระทั่ง lock xadd [mem], reg ซึ่งจะใช้ fetch_add เมื่อจำเป็นต้องใช้ค่าที่ส่งคืน (num++ สามารถเป็นอะตอมมิกสำหรับ 'int num' ได้หรือไม่)

RISC ส่วนใหญ่มี LL/SC รวมถึง ARM, MIPS และ PowerPC รวมถึง RISC ISA รุ่นเก่าที่ไม่ธรรมดาอีกต่อไป


futex(2) เป็นการเรียกของระบบ หากคุณเรียกมัน ทุกอย่างที่ทำจะอยู่ในโหมดเคอร์เนล

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

(เช่น หมุนในพื้นที่ผู้ใช้สองสามครั้งในกรณีที่การล็อคพร้อมใช้งาน)

นี่คือสิ่งที่ futex(7) man page กำลังอธิบาย แต่ฉันพบว่ามันแปลกนิดหน่อยที่จะเรียกมันว่า "การดำเนินการ futex" หากคุณไม่ได้ทำการเรียกระบบจริงๆ ฉันเดาว่ามันทำงานบนหน่วยความจำที่โค้ดเคอร์เนลอาจดูในนามของเธรดอื่นที่กำลังรออยู่ ดังนั้นความหมายที่จำเป็นสำหรับการแก้ไขตำแหน่งหน่วยความจำในโค้ดพื้นที่ผู้ใช้จึงขึ้นอยู่กับ futex

person Peter Cordes    schedule 02.09.2018
comment
ขอบคุณ @Peter สำหรับคำตอบโดยละเอียดนี้! ถ้า futex(7) ไม่เรียก futex(2) (กล่าวคือ ไม่มีการโต้แย้ง) มันจะต้องใช้ TAS หรือคำสั่งอะตอมมิกอื่นๆ เพื่อดำเนินการล็อค ใช่ไหม ฉันไม่ได้ตรวจสอบรหัสสำหรับ futex(7)... ฉันพูดถึงมันในคำถามเนื่องจาก futex(7) เป็นฟังก์ชันไลบรารี มันทำงานในพื้นที่ผู้ใช้ ดังนั้น TAS ใด ๆ ที่ดำเนินการจะต้องอยู่ในพื้นที่ผู้ใช้ - person flow2k; 02.09.2018
comment
@flow2k: ใช่ RMW อะตอมมิกในพื้นที่ผู้ใช้ แต่ futex(7) กำลังบันทึกแนวคิดทั่วไปของวิธีสร้างการล็อกหรือการดำเนินการอื่นๆ ประมาณ futex(2) ไม่มีฟังก์ชันไลบรารีที่เรียกว่า futex() นอกเหนือจาก wrapper การเรียกของระบบ ถ้ามีก็จะเรียกว่า futex(3) อย่างไรก็ตาม ใช่ ประเด็นทั้งหมดของคำตอบนี้คือ futex(2) เป็นวิธีการนอนหลับของคุณหากคุณพบว่ามีการล็อคในการใช้งานเช่น x86 asm spinlock นี้ (ซึ่งทำงานในพื้นที่ผู้ใช้): ล็อกการจัดการหน่วยความจำผ่านแอสเซมบลีแบบอินไลน์ - person Peter Cordes; 02.09.2018
comment
ฉันไม่เคยเห็นโปรเซสเซอร์ที่การทดสอบบิตและการดำเนินการตั้งค่าเป็นคำสั่งพิเศษ ไม่น่าแปลกใจเลยที่นักเรียน CS จะสับสนมาก - person user3344003; 02.09.2018