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

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

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

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

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

โครงสร้างข้อมูลแบบขนานนั้นออกแบบและตรวจสอบความถูกต้องได้ยากกว่าโครงสร้างข้อมูลแบบลำดับอย่างมาก

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

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

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

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

.NETมีConcurrentDictionary [ ^{5 ]} ConcurrentQueue ^{[ 6 ]}และConcurrentStack ^{[ 7 ]}ในเนมสเป ^ซ System.Collections.Concurrent

Rust ห่อหุ้มโครงสร้างข้อมูล ด้วยArcและMutexแทน^{[ 8 ]}

let counter = Arc :: new ( Mutex :: new ( 0 ));

• ความปลอดภัยของเกลียว
• การทำงานพร้อมกันในภาษา Java (JSR 166)
• Java ConcurrentMap

• แนนซี ลินช์ "การประมวลผลแบบกระจาย"
• Hagit Attiyaและ Jennifer Welch "การประมวลผลแบบกระจาย: พื้นฐาน การจำลอง และหัวข้อขั้นสูง ฉบับที่ 2"
• Doug Lea , "การเขียนโปรแกรมแบบขนานใน Java: หลักการออกแบบและรูปแบบ"
• มอริซ เฮอร์ลิฮีและนิร์ ชาวิต "ศิลปะแห่งการเขียนโปรแกรมแบบมัลติโปรเซสเซอร์"
• Mattson, Sanders และ Massingil "รูปแบบสำหรับการเขียนโปรแกรมแบบขนาน"

• โครงสร้างข้อมูลแบบมัลติเธรดสำหรับการประมวลผลแบบขนาน ตอนที่ 1 (การออกแบบโครงสร้างข้อมูลแบบพร้อมกัน) โดย อาร์ปัน เซน
• โครงสร้างข้อมูลแบบมัลติเธรดสำหรับการประมวลผลแบบขนาน: ตอนที่ 2 (การออกแบบโครงสร้างข้อมูลแบบพร้อมกันโดยไม่ต้องใช้มิวเท็กซ์) โดย อาร์ปัน เซน
• libcds – ไลบรารี C++ สำหรับคอนเทนเนอร์แบบไร้การล็อกและรูปแบบการเรียกคืนหน่วยความจำที่ปลอดภัย
• Synchrobench – ไลบรารีและเกณฑ์มาตรฐานสำหรับภาษา C/C++ และ Java สำหรับโครงสร้างข้อมูลแบบ lock-free, lock-based, TM-based และ RCU/COW-based