Process Synchronization

กระบวนการทำงานของโปรเซสหรือเทรดที่เกิดขึ้นอยู่ภายในระบบปฏิบัติการหลายครั้งที่อาจจะต้องมีการใช้ทรัพยากรร่วมกัน ไม่ว่าจะเป็นหน่วยความจำที่ถูกใช้ร่วมกัน (shared memory) ตัวแปรกลางที่ใช้ร่วมกัน (global variable) หรือไฟล์ที่จะต้องใช้ร่วมกัน (shared file) ซึ่งถ้าเกิดเหตุการณ์ที่โปรเซสมากกว่าหนึ่งตัวต้องการเข้ามาใช้ทรัพยากรตัวเดียวกัน ก็จะขึ้นอยู่กับว่าโปรเซสตัวใดทำงานขึ้นมาก่อนหรือเข้าถึงได้เร็วกว่ากัน ลักษณะการแย่งเข้าใช้หรือแข่งกันเข้าถึงทรัพยากรในลักษณะนี้เรียกว่า “เงื่อนไขแข่งขัน” (Race Conditions) ทำให้ตัวโปรเซสที่เร็วกว่าได้เข้าไปเปลี่ยนแปลงค่าภายในพื้นที่นั้น และถ้าไม่ได้ป้องกันในขณะที่อีกโปรเซสกำลังเข้าไปเปลี่ยนแปลงค่าในพื้นที่ส่วนนั้น แต่มีอีกโปรเซสก็เข้าไปเปลี่ยนแปลงค่าด้วยเช่นกันก็จะยิ่งทำให้เกิดความผิดพลาดของข้อมูลที่โปรเซสอื่นๆ จะได้รับผลกระทบไปด้วย

ตัวอย่างที่เห็นได้ชัดเช่น สร้างตัวแปรกลางสำหรับใช้งานร่วมกัน (int count = 5) เมื่อโปรเซสหนึ่งโดยสมมติให้เป็นผู้ผลิต (producer) ที่จะต้องทำการเพิ่มค่าตัวแปรกลางที่ใช้งานร่วมกัน (count = count + 1) แต่ในขณะที่อีกโปรเซสโดยสมมติให้เป็นผู้ใช้ (consumer) ที่จะทำการลดค่าตัวแปรกลางลง (count = count - 1) ซึ่งเมื่อโปรเซสทั้งสองเริ่มทำงานพร้อมๆกัน ผลการทำงานที่ควรจะเป็นคือ ผู้ผลิตต้องทำงานหรือเพิ่มค่าตัวแปร count ให้เสร็จก่อนที่ผู้ใช้จะทำงาน (ลดค่าตัวแปร count) หากโปรแกรมทำงานอย่างถูกต้อง ผลลัพธ์ของค่าตัวแปร count จะมีค่าเท่ากับ 5 แต่ผลที่ได้ของการรันโปรแกรมแต่ละครั้งอาจจะเป็น 4, 5 หรือ 6 เนื่องจากการทำงานของภาษาเครื่องจะแยกตัวแปรรีจิสเตอร์ (CPU register) ออกจากกันระหว่างคำสั่ง count = count + 1 และคำสั่ง count = count - 1 ดังแสดงข้างล่างนี้

Producer	Consumer
count = count + 1	count = count - 1
register1 = count	register2 = count
register1 = register1+ 1;	register2 = register2 - 1;
count = register1	count = register2

ซึ่งจะเห็นว่าลำดับการทำงานของโปรเซสแบ่งออกเป็น 6 ขั้นตอน (ในบางครั้งการรันอาจจะสลับการทำงานกันได้) ดังนี้

ผลการรัน Producer

1. โปรเซสผู้ผลิตทำงาน register1 = count

2. โปรเซสผู้ผลิตทำงาน register1 = register1 + 1

โปรเซสผู้ผลิตถูกหยุดและนำออกจากหน่วยประมวลผลกลาง

1. โปรเซสผู้ใช้ทำงาน register2 = count

2. โปรเซสผู้ใช้ทำงาน register2 = register2 - 1

โปรเซสผู้ใชถูกหยุดและนำออกจากหน่วยประมวลผลกลาง

1. โปรเซสผู้ผลิตทำงาน count = register1

2. โปรเซสผู้ใช้ทำงาน count = register2 ==> ค่า count สุดท้ายมีค่าเท่ากับ 4

หรือ

ผลการรัน Consumer

1. โปรเซสผู้ใช้ทำงาน register2 = count

2. โปรเซสผู้ใช้ตทำงาน register2 = register2 - 1

โปรเซสผู้ผลิตถูกหยุดและนำออกจากหน่วยประมวลผลกลาง

1. โปรเซสผู้ผลิตทำงาน register1 = count

2. โปรเซสผู้ผลิตทำงาน register1 = register1 + 1

โปรเซสผู้ใชถูกหยุดและนำออกจากหน่วยประมวลผลกลาง

1. โปรเซสผู้ใช้ทำงาน count = register2

2. โปรเซสผู้ผลิตทำงาน count = register1 ==> ค่า count สุดท้ายมีค่าเท่ากับ 6

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

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

รูปการห้ามอยู่พร้อมกันของโปรเซสภายในพื้นที่วิกฤติ

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

1. ต้องไม่มีโปรเซสมากกว่าหนึ่งโปรเซสที่จะสามารถเข้าไปในเขตวิกฤตพร้อมกันได้ (mutual exclusion)

2. ต้องไม่ให้โปรเซสที่อยู่นอกเขตวิกฤติไปขัดขวางไม่ให้โปเซสอื่นเข้าถึงเขตวิกฤตไม่ได้ (progress)

3. ต้องไม่ให้โปรเซสต้องทำการรอแบบไม่มีวันสิ้นสุดเพื่อที่จะเข้าถึงเขตวิกฤต (bound waiting)

ในทางปฏิบัติการแก้ปัญาการเข้าใช้ทรัพยากรในเขตวิกฤตนั้นมีด้วยกัน 3 แนวทางคือ

1. นักพัฒนาโปรแกรมเขียนส่วนของควบคุมเองเพื่อไม่ให้แต่ละโปรเซสแย่งกัน (Application layer)

2. รองรับในระดับฮาร์ดแวร์ (Hardware support)

3. นักพัฒนาโปรแกรมเขียนส่วนของการควบคุมโดยใช้ API ที่ระบบปฏิบัติการเตรียมไว้ให้ (OS support)

SW Solution

ตัวอย่างของการใช้ SW Solution โดยการสร้างตัวแปรที่ระบุว่าเป็นคราวของโปรเซสหมายเลขใดที่จะได้เข้าใช้งานในเขตวิกฤติ

Process 0

while(TRUE) {
	while(turn!=0); // wait
	critical_section(); 
	turn = 1; 
	noncritical_section();
}

Process 1

while(TRUE) {
	while(turn!=1); // wait
	critical_section();
	turn = 0;
	noncritical_section();
}

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

Peterson’s Solution

อัลกอริทึมของปีเตอร์สัน (Peterson’s Algorithm) ซึ่งนิยมเรียกกันว่า Peterson’s solution ถูกสร้างโดยนาย Gary L. Peterson ในปี ค.ศ. 1981 เป็นแนวทางการเขียนโปรแกรมในลักษณะที่ทำงานคู่ขนานเพื่อแก้ปัญหาการแย่งชิงทรัพยากรโดยจะยอมให้ทั้งสองโปรเซสสามารถเข้าไปใช้งานทรัพยากรร่วมกันได้ โดยการกำหนดตัวแปรขึ้นมาสองตัวได้แก่ตัวแปรอาเรย์ชนิดตรรกะชื่อว่า flag[ ] และตัวแปรชนิดจำนวนเต็ม turn

โดยตัวแปร flag[n] จะเก็บค่าไม่จริง (True) ก็เท็จ (False) สมมติว่าถ้า flag[n] มีค่าเป็นจริง (true) หมายความว่าหมายเลขของโปรเซสที่ n ต้องการที่เข้าใช้ในเขตวิกฤติ (CR)

bool flag[0] = false;
bool flag[1] = false;
int turn;  

จากตัวอย่างโปรแกรมข้างต้น เมื่อโปรเซสหมายเลขศูนย์ (0) กำลังเข้าใช้งานภายในเขตวิกฤติอยู่ แล้วมีโปรเซส หมายเลขหนึ่ง (1) ต้องการจะเข้าถึงเขตวิกฤติด้วยเช่นกัน ก็จะต้องตรวจสอบว่า flag[0] เป็นจริงหรือไม่ และตรวจสอบว่าเป็นรอบของใคร (turn=?) ถ้าออกมาแล้วยังเป็นเท็จอยู่ ก็จะต้องวนรออยู่ภายในลูป while (busy wait) แต่ถ้าโปรเซสศูนย์ออกจากเขตวิกฤติแล้วก็จะกำหนดค่า flag[0] ให้เป็นเท็จทันทีเพื่อบอกกับอีกโปรเซสว่าไม่ได้เข้าใช้แล้ว