# Process Synchronization

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

ตัวอย่างที่เห็นได้ชัดเช่น สร้างตัวแปรกลางสำหรับใช้งานร่วมกัน (`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` ดังแสดงข้างล่างนี้

<table><thead><tr><th width="348">Producer</th><th>Consumer</th></tr></thead><tbody><tr><td><code>count = count + 1</code></td><td><code>count = count - 1</code></td></tr><tr><td><code>register1 = count</code></td><td><code>register2 = count</code></td></tr><tr><td><code>register1 = register1+ 1;</code></td><td><code>register2 = register2 - 1;</code></td></tr><tr><td><code>count = register1</code></td><td><code>count = register2</code></td></tr></tbody></table>

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

{% hint style="warning" %} <mark style="color:purple;">**ผลการรัน Producer**</mark>

1. โปรเซสผู้ผลิตทำงาน `register1 = count`&#x20;
2. โปรเซสผู้ผลิตทำงาน `register1 = register1 + 1`&#x20;

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

1. โปรเซสผู้ใช้ทำงาน `register2 = count`&#x20;
2. โปรเซสผู้ใช้ทำงาน `register2 = register2 - 1`&#x20;

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

1. โปรเซสผู้ผลิตทำงาน `count = register1`&#x20;
2. โปรเซสผู้ใช้ทำงาน `count = register2`   <mark style="color:orange;">==> ค่า count สุดท้ายมีค่าเท่ากับ</mark> <mark style="color:orange;"></mark><mark style="color:orange;">`4`</mark>
   {% endhint %}

*หรือ*

{% hint style="warning" %} <mark style="color:purple;">**ผลการรัน Consumer**</mark>

1. โปรเซสผู้ใช้ทำงาน `register2 = count`&#x20;
2. โปรเซสผู้ใช้ตทำงาน `register2 = register2 - 1`&#x20;

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

1. โปรเซสผู้ผลิตทำงาน `register1 = count`&#x20;
2. โปรเซสผู้ผลิตทำงาน `register1 = register1 + 1`&#x20;

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

1. โปรเซสผู้ใช้ทำงาน `count = register2`&#x20;
2. โปรเซสผู้ผลิตทำงาน `count = register1`   <mark style="color:orange;">==> ค่า count สุดท้ายมีค่าเท่ากับ</mark> <mark style="color:orange;"></mark><mark style="color:orange;">`6`</mark>
   {% endhint %}

จากลำดับการทำงานข้างต้นจะเห็นได้ว่าเงื่อนไขแข่งขันของทั้งสองโปรเซสทำให้ผลลัพธ์สุดท้ายมีค่าเท่ากับ 4 และ 6 ซึ่งไม่ถูกต้อง เนื่องจากทั้งสองโปรเซสทำการเขียนข้อมูลตัวเดียวกัน (`count`) ในเวลาที่ขนานกัน แต่ที่ถูกต้องแล้วจะต้องให้โปรเซสผู้ผลิตทำงานให้เสร็จสิ้นโดยที่โปรเซสผู้ใช้จะต้องรอและไม่เข้าไปเปลี่ยนแปลงค่า count แต่อย่างใดก่อน เรียกส่วนพื้นที่ที่มีการถูกใช้งานร่วมกันและอาจมีแนวโน้มที่จะทำให้เกิดปัญหาดังที่กล่าวมาข้างต้นเรียกว่า  เขตวิกฤต (<mark style="color:blue;">**critical section - CS**</mark>) หรือ (<mark style="color:purple;">**critical region - CR**</mark>)&#x20;

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

<figure><img src="https://1856353139-files.gitbook.io/~/files/v0/b/gitbook-x-prod.appspot.com/o/spaces%2F-MClo3nC-1US0rbK8Qau%2Fuploads%2F9wLEJvWveTjZEaYgbT14%2FCR.png?alt=media&#x26;token=abc7d572-de5c-48a3-9fd6-ee5206449101" alt=""><figcaption><p><em>รูปการห้ามอยู่พร้อมกันของโปรเซสภายในพื้นที่วิกฤติ</em></p></figcaption></figure>

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

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

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

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

## SW Solution

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

{% tabs %}
{% tab title="Process 0" %}

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

{% endtab %}

{% tab title="Process 1" %}

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

{% endtab %}
{% endtabs %}

จากตัวอย่างโปรแกรมข้างต้นทั้งสองโปรเซสจะตรวจสอบค่าในตัวแปร <mark style="color:orange;">`turn`</mark> ว่าเป็นรอบของใคร ถ้าค่าตรงกับหมายเลขโปรเซสของตนก็จะเข้าไปใช้ในพื้นที่เขตวิกฤตทันที (`critical_section()`) เมื่อทำงานเสร็จสิ้นแล้วก็จะเปลี่ยนค่าในตัวแปร <mark style="color:orange;">`turn`</mark> ให้เป็นของอีกโปรเซสหนึ่ง โดยทั้งสองโปรเซสจะต่างรออยู่ในพื้นที่ที่ไม่ใช่เขตวิกฤต

## Peterson’s Solution

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

โดยตัวแปร <mark style="color:orange;">`flag[n]`</mark> จะเก็บค่าไม่จริง (True) ก็เท็จ (False) สมมติว่าถ้า `flag[n]` มีค่าเป็นจริง (`true`) หมายความว่าหมายเลขของโปรเซสที่ `n` ต้องการที่เข้าใช้ในเขตวิกฤติ (CR)&#x20;

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

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