อัลกอริทึมการกีดกันร่วมกันของ Szymańskiเป็นอัลกอริทึมการกีดกันร่วมกันที่คิดค้นโดยนักวิทยาศาสตร์คอมพิวเตอร์ ดร. Bolesław Szymańskiซึ่งมีคุณสมบัติที่น่าสนใจหลายประการ รวมถึงการรอคอยเชิงเส้น^{[ 1 ] [ 2 ]}และส่วนขยาย^{[ 3 ]}ได้แก้ปัญหาที่เปิดอยู่ซึ่งโพสต์โดยLeslie Lamport ^{[ 4 ]}ว่ามีอัลกอริทึมที่มีจำนวนบิตการสื่อสารคงที่ต่อกระบวนการที่ตรงตามข้อกำหนดด้านความยุติธรรมและความทนทานต่อความล้มเหลวที่สมเหตุสมผลทั้งหมดที่ Lamport คิดไว้หรือไม่ (วิธีแก้ปัญหาของ Lamport ใช้ ตัวแปรการสื่อสารแฟกทอเรียล nเทียบกับ 5 ของ Szymański)

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

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

ตัวแปร แฟล็กจะมีค่า/สถานะใดสถานะหนึ่งจากห้าค่าต่อไปนี้:

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

สถานะของประตูทางเข้าจะถูกคำนวณโดยการอ่านค่าแฟล็กของกระบวนการทั้งNกระบวนการ โค้ดเทียมแสดงอยู่ด้านล่าง:

# แฟล็ก โปรโตคอลการเข้า [ self ] ← 1 # ยืนอยู่นอกห้องรอawait ( all flag [ 1. . N ] ∈ { 0 , 1 , 2 }) # รอประตูเปิดflag [ self ] ← 3 # ยืนอยู่ที่ทางเข้าประตูถ้า flag [ 1. . N ] = 1 : # มีกระบวนการอื่นรอเข้าflag [ self ] ← 2 # รอให้กระบวนการอื่นเข้ามาawait ( any flag [ 1. . N ] = 4 ) # รอให้กระบวนการเข้ามาและปิดประตูflag [ self ] ← 4 # ประตูถูกปิดawait ( all flag [ 1. . self - 1 ] ∈ { 0 , 1 }) # รอให้ทุกคนที่มี ID ต่ำกว่าเสร็จสิ้นขั้นตอนการออก# ส่วนวิกฤต# ...# โปรโตคอลการออกจากห้องรอ await ( all flag [ self + 1. . N ] ∈ { 0 , 1 , 4 }) # ตรวจสอบให้แน่ใจว่าทุกคนในห้องรอทราบแล้วว่าประตูควรจะปิดflag [ self ] ← 0 # ออกไป เปิดประตูอีกครั้งหากไม่มีใครอยู่ในห้องรอแล้ว

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

• อัลกอริทึมของเดกเกอร์
• อัลกอริทึมของ Eisenberg & McGuire
• อัลกอริทึมของปีเตอร์สัน
• อัลกอริทึมเบเกอรี่ของแลมพอร์ต
• สัญญาณไฟ