Please enable JavaScript.
Coggle requires JavaScript to display documents.
บทที่3 การประสาน เวลาของโพรเซส - Coggle Diagram
บทที่3 การประสาน
เวลาของโพรเซส
การประสานเวลาของโพรเซส
โดยทั่วไปทุกโพรเซสต้องการให้มีการประมวลผลอย่างเป็นอิสระ เสมือนมีโพรเซสเดียวที่กำลังทำงานอยู่ ลักษณะความเป็นอิสระนี้เรียกว่า
Asynchronous
จำเป็นต้องมีการสื่อสารกันระหว่างโพรเซส
(Inter processcommunication)
จำเป็นต้องให้ทุกโพรเซสทำงานประสานกันเป็นอย่างดีการเข้าจังหวะของโพรเซส แสดงการประสานเวลาของโพรเซส
ปัญหาภาวะ
พร้อมกัน
ทรัพยากรที่ไม่สามารถใช้ร่วมกันได้
Non-dedicated resources
บางครั้งมีความจำเป็นที่ต้องใช้ทรัพยากรร่วมกัน และเป็นทรัพยากรที่ต้องทำงานครั้งละ 1 งาน ไม่สามารถทำงานพร้อมกันได้
ภาวะพร้อมกัน(Concurrency)
โพรเซส A และ โพรเซส B ทำงานพร้อมกัน
โพรเซส B ทำงานเสร็จก่อน โพรเซส A
โพรเซส A ทำงานเสร็จก่อน โพรเซส B
สภาวะการแย่งชิง
สภาวะเงื่อนไขการแย่งชิง (Race condition)
โพรเซสใช้ตัวแปรตัวหนึ่งในหน่วยความจำร่วมกันทั้งสองโพรเซสซึ่งโพรเซสทั้งสองสามารถอ่านหรือเขียนทรัพยากรเหล่านี้ได้พร้อมกัน ทำให้ผลลัพธ์อาจจะเกิด
การผิดพลาดขึ้นได้ ขึ้นอยู่ว่าโพรเซสใดเข้ามาใช้ก่อนทำให้ผลลัพธ์อาจจะเกิดการผิดพลาดขึ้นได้ ขึ้นอยู่
กับว่าโพรเซสใดทำเสร็จก่อนเรียกสภาวะนี้ว่า สภาวะ
เงื่อนไขการแย่งชิง (Race condition)
ป้องกันการเกิดเงื่อนไขการแย่งชิงขึ้นตามตัวอย่าง ระบบต้องแน่ใจว่าในเวลาใดๆ จะมีโพรเซสเดียวเท่านั้นที่ก าลังเข้าจัดการข้อมูลตัวแปร X โดยต้องอาศัยกลไกบางอย่างในการประสานโพรเซสอย่างได้จังหวะกันจึงสามารถรับประกันความถูกต้องได้
การแก้ปัญหา
ส่วนวิกฤติ
การกีดกัน (Mutual exclusion)
ถ้าโพรเซส Pi กำลังปฏิบัติการอยู่ในส่วนวิกฤติแล้ว ต้องไม่มีโพรเซสอื่นใดก าลังอยู่ในส่วนวิกฤติของโพรเซสเหล่านั้นด้วย นั่นคือในขณะใดขณะหนึ่งมีเพียงโพรเซสเดียวเท่านั้นที่อยู่ในส่วนวิกฤติของตน
โครงสร้างภาษาโดยทั่วไปของการดำเนินการของโพรเซสปกติ
ความก้าวหน้า (Progress)
ถ้าไม่มีโพรเซสใดกำลังปฏิบัติการอยู่ในส่วนวิกฤติแล้วมีบาง โพรเซสเข้าสู่ส่วนวิกฤติของตน ในการเลือกว่าโพรเซสใดจะได้เข้าสู่ส่วนวิกฤติของตนต่อไปนั้น ระบบก็จะพิจารณาจากทุก ๆ โพรเซส
ยกเว้นโพรเซสที่กำลังทำงานอยู่ในส่วนที่เหลือนั้น โดยการเลือกนี้ต้องไม่เลื่อนออกไปอย่างไม่มีกำหนด
การรออย่างมีขอบเขต (Bounded waiting)
การรอแบบไม่ว่าง (Preemptive kernels)
ในแต่ละโพรเซสมีการกำหนดเงื่อนไขที่ต้องการใช้ในการตรวจสอบก่อนเข้าสู่ส่วนวิกฤติ ซึ่งถ้าหากไม่สามารถผ่านเงื่อนไขนี้ไปได้
โพรเซสไม่สามารถเข้าสู่ส่วนวิกฤติของตนเองได้และวนเวียนตรวจสอบเงื่อนไขนั้นอยู่ตลอดเวลาจนกว่าจะได้เข้าสู่ส่วนวิกฤตินั่นคือ ในระหว่างรอโพรเซสนั้นยังต้องทำคำสั่งซ้ำทดสอบเงื่อนไขอยู่เรื่อยๆ
การขัด (Non-preemptive kernels)
โพรเซสล่าสุดที่เข้าใช้ส่วนวิกฤติของตนเองได้
ออกจากส่วนวิกฤตินั้นแล้ว จะต้องปลุกหรือใช้คำสั่งบอกให้ระบบทราบเพื่อให้นำโพรเซสที่รออยู่ใน
แถวคอยตามเงื่อนไขที่รอได้กลับเข้ามาทำงานในส่วนวิกฤติของตนเองต่อไป
ซึ่งการบล็อกนี้ระบบจะนำโพรเซสเหล่านั้นไปรออยู่ในแถวของแต่ละเงื่อนไขและตัวแปรที่ใช้ในการตรวจสอบก่อนเข้าสู่ส่วนวิกฤติ ทำให้โพรเซสเหล่านี้ไม่ต้องเข้ามาแย่งชิงกันใช้CPU
การประมวลผลพร้อมกัน
โดยวิธีการทางซอฟต์แวร์
ทำการพัฒนาโปรแกรมที่ประกอบด้วย 2 โพรเซส
โดยสามารถทำงานพร้อมกัน และเกิดคุณสมบัติการไม่เกิดร่วม ตัวอย่างประกอบด้วยโพรเซส P0 และ P1 ที่ทำงานพร้อมกัน
อัลกอริทึมของเดกเกอร์
(Dekker’s algorithm)
โครงสร้างภาษาที่ใช้อัลกอริทึมของเดกเกอร์ของโพรเซส P0 และ P1
//flag[] is boolean array; and turn is an integer
flag[0] = false
flag[1] = false
turn = 0 // or 1
P0
flag[0] = true;
while (flag[1] == true) {
if (turn ≠ 0) {
flag[0] = false;
while (turn ≠ 0) {
// busy wait
}
flag[0] = true;
}
}
// critical section
turn = 1;
flag[0] = false;
// remainder section
P1
flag[1] = true;
while (flag[0] == true) {
if (turn ≠ 1) {
flag[1] = false;
while (turn ≠ 1) {
// busy wait
}
flag[1] = true;
}
}
// critical section
turn = 0;
flag[1] = false;
// remainder section
อัลกอริทึมปีเตอร์สันโซลูชั่น (Peterson’s Solution)
ที่มีโพรเซสหมายเลข P0และ P1 และโพรเซสทั้งสองต้องการข้อมูลสองค่าเพื่อใช้ร่วมกันระหว่างกัน
P0
flag[0] = true;
turn = 1;
while (flag[1] == true && turn == 1)
{
// busy wait
}
// critical section
...
// end of critical section
flag[0] = false;
P1
flag[1] = true;
turn = 0;
while (flag[0] == true && turn == 0)
{
// busy wait
}
// critical section
...
// end of critical section
flag[1] = false;
//flag[] is boolean array; and turn is an integer
flag[0] =false;
flag[1] = alse;
turn;
ฮาร์ดแวร์ประสานเวลา
การปิดกั้น (lock)
รูปแบบของคำสั่ง Lock
do {
acquire lock
critical section
release lock
remainder section
} while (TRUE);
การทำงานด้วยวิธีนี้ระบบสามารถมีมากกว่าหนึ่งโพรเซสที่ทำงานพร้อมกันได้ โดยมีคุณสมบัติการไม่เกิดร่วม
การปิดทางขัดจังหวะ (disabling interrupt)
ระบบมัลติโพรเซสเซอร์ไม่สามารถใช้วิธีนี้ได้การห้ามขัดจังหวะบนโพรเซสเซอร์หลายตัวนั้นใช้เวลานาน
มากในการส่งข่าวสารไปยังโพรเซสเซอร์ทุกตัว
ในกรณีที่โพรเซสปิดกั้นการขัดจังหวะ แล้วไม่ได้ปล่อยการขัดจังหวะกลับคืนให้ระบบ อาจทำให้ปัญหาอื่นตามมา
คำสั่งทดสอบและเซ็ต (test and set instruction)
การทำงานของคำสั่งไม่สามารถถูกขัดจังหวะได้การทำงานของวิธีนี้คือ โพรเซสที่ต้องการเข้าไปทำงานในส่วนวิกฤติจะต้องเรียกใช้คำสั่งทดสอบและเซต เพื่อตรวจสอบว่ามีโพรเซสใดทำงานอยู่ในส่วนวิกฤติหรือไม่ หากพบว่าขณะนั้นไม่มีโพรเซสใดทำงานในส่วนวิกฤติโพรเซส
จะเซตค่าล็อค
รูปแบบของคำสั่ง Test-and-Set
boolean test_and_set (boolean *target)
boolean rv = *target;
*target = TRUE;
return rv:
Swap Instruction
คำสั่ง Swap( ) จะตรงกันข้ามกับ
คำสั่ง TestAndSet( ) คำสั่ง Swap( )
จะทำงานในเนื้อหาของคำสองคำ
โครงสร้างพื้นฐาน
สำหรับการซินโครไนซ์
เซมาฟอร์(Semaphore)
วิธีการแก้ปัญหา
เขตวิกฤตที่กล่าวมาแล้วทั้งหมด ยังคงไม่สะดวกในการใช้งานกับปัญหาที่ซับซ้อนมากขึ้น เราจึงต้องหาวิธีใหม่ เรียกว่า เซมาฟอร์ที่
เซมาฟอร์แบบทวิภาค (Binary Semaphore)
ส่วนในเซมาฟอร์
แบบทวิภาค
จะกำหนดให้ใช้ตัวแปรจำนวนเต็มได้ 2 ค่าคือ 0 และ 1เท่านั้น ทำให้สามารถสร้างได้ง่ายกว่าเซมาฟอร์แบบนับ ซึ่งสามารถสร้างเซมาฟอร์แบบนับให้อยู่ในรูปแบบ
รูปแบบของการใช้งาน
Semaphore แบบทวิภาค
การใช้งานเซมาฟอร์
do {
wait(mutex);
critical section
signal(mutex);
remainder section
} while (true);
สามารถนำเซมาฟอร์ไปใช้ในการแก้ไขปัญหาส่วนวิกฤตของโพรเซส n ตัว โพรเซส n ตัวจะร่วมใช้เซมาฟอร์ที่ชื่อ mutex (ใช้แทน Mutual exclusion) เริ่มการทำงานที่ 1 โดยที่แต่ละโพรเซส Pi
การสร้าง Mutual Exclusion ด้วย Semaphore
การสร้างเซมาฟอร์
(Semaphore Implementation)
การสร้างเซมาฟอร์ตามนิยามใหม่นี้ กำหนดให้เซมาฟอร์เป็นตัวแปรประเภท Structure ในภาษาซี
typedef struct {
int value;
struct process *L;
} semaphore;
การติดตายและอดตาย
(Deadlock)
การสร้างเซมาฟอร์ด้วยการให้โพรเซสที่รอการทำงานไปอยู่ในคิว
อาจส่งผลให้เกิดเหตุการณ์ที่สองโพรเซสหรือมากกว่านั้นรอแบบไม่มีที่สิ้นสุด เนื่องจากโพรเซสไปรอการทำงานของโพรเซสที่ยังรอ
ปัญหาพื้นฐานของการประสานเวลา
ปัญหาผู้อ่านและผู้เขียน (The Readers/Writers Problem)
มีพื้นที่ข้อมูลซึ่งใช้ร่วมกันได้ระหว่างกระบวนการทั้งหมด มีโพรเซสจำนวนมากที่ต้องการอ่านพื้นที่ดังกล่าวเพียงอย่างเดียวและมีโพรเซสที่ต้องการเขียนบนพื้นที่ดังกล่าวเพียงโพรเซสเดียวในเวลาเดียวกัน
จึงมีการ
นำเอาเซมาฟอร์
ช่วยในการแก้ไขปัญหาเหล่านี้ โดยให้มีโครงสร้างของการใช้ตัวแปรร่วมกัน
การ Shared Data
Data set
Semaphore mutex initialized to 1.
Semaphore wrt initialized to 1.
Integer readcount initialized to 0.
ปัญหาอาหารเย็นของนักปราชญ์(The Dining Philosophers Problem)
เป็นปัญหาที่ต้องการให้มีการ
จัดการเรื่องการใช้ทรัพยากรที่มีอยู่อย่างจำกัดร่วมกันระหว่างหลายโพรเซส
ปัญหาการติดตาย
จะเกิดเมื่อนักปราชญ์ทั้งห้าหยิบตะเกียบคนละข้างพร้อมกัน ปัญหาการอดตาย การที่นักปราชญ์ทางด้านซ้ายและด้านขวาของนักปราชญ์ผู้โชคร้ายสลับกันทานอาหาร
ปัญหาที่พักข้อมูลขนาดจำกัด (Bounded-Buffer Problem)
เป็นปัญหาที่นิยมใช้
ในการทดสอบประสิทธิภาพของเทคนิคการประสานเวลา
วิธีการแก้ปัญหานี้ทางหนึ่งคือโพรเซสของผู้ผลิตต้อง
Sleep
จนกว่าบัฟเฟอร์จะมีที่ว่างและถ้าบัฟเฟอร์ว่างโพรเซสของผู้บริโภคต้อง Sleep ว่างจนกว่าจะมีข้อมูลเพิ่มเติม
