OS Unit2

โปรเซส105คือ มีโอกาสที่โปรเซสท้งั สองจะเขา้ ในเขตวิกฤตพร้อมกนั ซ่ึงไม่ผา่ นคุณสมบตั ิขอ้ แรก คือ การหา้ มอยพู่ ร้อมกนั (mutually exclusion)1.3 Algorithm 3 โดยการรวมแนวคิดของ Algorithm 1 และ 2 เขา้ ดว้ ยกนั จะไดว้ ิธีที่สมบูรณ์แบบสามารถผา่ นคุณสมบตั ิท้งั 3 ประการในปัญหาเขตวิกฤตได้ โดยกาํ หนดให้ ตวั แปรร่วมเป็นดงั น้ีvar flag; array [0..1] of boolean;turn: 0..1;เร่ิมตน้ flag[0] = flag[1] = false และ turn อาจเป็น 0 หรือ 1และโปรแกรมสาํ หรับโปรเซส Pi เป็นrepeatflag[i] = true //โปรเซสแรกกาํ ลงั จะไดเ้ ขา้ เขตวิกฤตturn:= j; //ให้ counter ของอีกโปรเซสหน่ึงเตรียมตวั เขา้ CS เป็นลาํ ดบั ถดั ไปwhile (flag[j] and turn=j) do no-op; //ถา้ มีโปรเซสใดอยใู่ น CS โปรเซสหลงั ตอ้ งรอก่อนcritical sectionflag[i] := false; //โปรเซสแรกออกมาแลว้ ตอ้ ง set ตวั เองเป็น falseremainder sectionuntil false; เมื่อโปรเซส Pi ตอ้ งการเขา้ เขตวกิ ฤต flag[i] = true และให้ turn เป็นของอีกโปรเซสหน่ึง คือ j(turn =j) ถา้ ท้งั สองโปรเซสตอ้ งการเขา้ เขตวิกฤตในเวลาเดียวกนั ค่า turn จะถูกกาํ หนดเป็น i และ jในเวลาใกลเ้ คียงกนั turn จะกลายเป็นค่าสุดทา้ ย (i หรือ j) ซ่ึงจะอนุญาตใหเ้ พียงโปรเซสเดียวเขา้ เขตวกิ ฤต เราจะตอ้ งพสิ ูจนว์ า่ ข้นั ตอน algorithm 3 น้ีสามารถผา่ นคุณสมบตั ิท้งั 3 ประการ คือ 1. การหา้ มอยพู่ ร้อมกนั (Mutually Exclusion) 2. ความกา้ วหนา้ (Progress) 3. การรอคอยอยา่ งมีขอบเขต (Bounded Waiting)จะสงั เกตเห็นวา่ Pi เขา้ เขตวิกฤตไดก้ ต็ ่อเมื่อ flag[j] = false หรือ turn = i และถา้ โปรเซสท้งั สองสามารถอยใู่ นเขตวิกฤตไดพ้ ร้อมกนั แลว้ flag[0] = flag[1] = true จากขอ้ สงั เกต 2 ขอ้ ที่กล่าวมาน้ีสรุปไดว้ า่ P0 และ P1 ไม่สามารถผา่ นประโยค while ในขณะเดียวกนั ได้ เพราะค่าของ turn มีได้เพยี งค่าเดียวเท่าน้นั (0 หรือ 1) ในขณะหน่ึง ๆ ดงั น้นั จะมีเพยี งโปรเซสเดียวเท่าน้นั (สมมติใหเ้ ป็นPi) ที่ผา่ นประโยค while ได้ ขณะท่ี Pj ยงั คงติดใน while เพราะ turn = j และ flag[j] = true และจะ

106 ระบบปฏิบตั ิการติดอยตู่ ราบเท่าท่ี Pi ยงั คงอยใู่ นเขตวิกฤต สรุปไดว้ า่ วิธีน้ีผา่ นคุณสมบตั ิ การหา้ มอยพู่ ร้อมกนั(mutually exclusion) Pi จะติดอยใู่ นประโยค while กต็ ่อเมื่อ flag[j] = true และ turn = j ก่อนที่จะเขา้ เขตวิกฤต ถา้ Pj ไม่ตอ้ งการเขา้ เขตวกิ ฤตแลว้ flag[j] = false Pi กส็ ามารถเขา้ เขตวิกฤตได้ ถา้ Pjตอ้ งการเขา้ โดยให้ flag[j] = true และทาํ คาํ สง่ั while ค่าของ turn จะตอ้ งเป็น i หรือ j ค่าใดค่าหน่ึงเท่าน้นั ถา้ turn = i Pi กจ็ ะเขา้ เขตวิกฤตได้ ถา้ turn = j Pj กจ็ ะเขา้ เขตวิกฤตได้ หลงั จากที่ Pj ออกจากเขตวิกฤต Pj กจ็ ะให้ flag[j] = false ซ่ึงเป็นผลให้ Pi สามารถผา่ น while เขา้ เขตวิกฤตได้ แต่ถา้ Pjทาํ งานเร็วมาก วนไปให้ flag[j] = true (ก่อนเขา้ เขตวิกฤต)ได้ กจ็ ะทาํ ให้ turn = i ดงั น้นั Pi ซ่ึงไม่ได้เปล่ียนค่า turn ในขณะที่ติดอยทู่ ่ี while กจ็ ะเขา้ เขตวิกฤตได้ (ผา่ นคุณสมบตั ิ ความกา้ วหนา้(Progress)) โดยรอคอยอยา่ งมากไม่เกิน 1 รอบที่ Pj เขา้ เขตวิกฤต (ผา่ นคุณสมบตั ิ การรอคอยอยา่ งมีขอบเขต (Bounded Waiting))2. การแก้ปัญหาในระบบทมี่ หี ลายโปรเซส (Multiple-Process Solutions)Algorithm 3 สามารถแกป้ ัญหาเขตวิกฤตได้ แต่ใชไ้ ดเ้ ฉพาะระบบที่มี 2 โปรเซสเท่าน้นั ในหวั ขอ้ น้ีเราจะกล่าวถึงข้นั ตอนวิธี สาํ หรับแกป้ ัญหาเขตวิกฤต ในระบบที่มี n โปรเซสAlgorithm น้ี เรียกว่าbakery algorithm วิธีน้ีมีแนวคิดมาจาก การจดั ลาํ ดบั ลูกคา้ ที่มาใชบ้ ริการในร้านขายขนมปังไอศกรีม เน้ือววั และร้านอื่น ๆ ที่มีลกั ษณะคลา้ ยกนั วธิ ีน้ีเหมาะกบั ระบบแบบกระจายอาํ นาจ แต่เราจะพิจารณาเฉพาะ ในระบบรวมอาํ นาจ หรือ ระบบรวมศูนย์ (Centralized environment) เมื่อลูกคา้ เขา้ มาในร้าน จะไดร้ ับหมายเลขบตั รคิว ลูกคา้ ท่ีมีหมายเลขนอ้ ยท่ีสุด จะไดร้ ับบริการก่อน ในกรณีท่ีลูกคา้ 2 คน อาจไดร้ ับหมายเลขเดียวกนั (เพราะเขา้ ร้านพร้อมกนั ) ให้เรียงลาํ ดบั ดว้ ยช่ือลูกคา้ แทน เช่น ถา้ Pi และ Pj ไดร้ ับหมายเลขเดียวกนั และ i < j แลว้ Pi จะไดร้ ับบริการก่อน วิธีน้ีจะสามารถจดั การไดอ้ ยา่ งเป็นระบบ เพราะโปรเซสแต่ละตวั มีชื่อ (หรือหมายเลขประจาํ ตวั ) ไม่ซ้าํ กนั และมกั เรียงกนั อยแู่ ลว้โครงสร้างขอ้ มูลโดยทวั่ ไปคือvar choosing: array [0..n-1] of boolean;number: array [0..n-1] of integer;ค่าเร่ิมตน้ ของ choosing ท้งั หมดเป็น false และ number = 0เพ่ือความสะดวก เรากาํ หนดสญั ลกั ษณ์ดงั น้ี  (a,b) < (c,d) ถา้ a < c หรือ ถา้ a = c และ b < d  max(a0 , … , an-1) เป็นฟังกช์ นั ใหค้ า่ มากท่ีสุดจาก a0 ถึง an-1โครงสร้างของโปรเซส Pi ท่ีใชใ้ น bakery algorithm แสดงดงั ต่อไปน้ีrepeat

โปรเซส107choosing[i] := true; //โปรเซสแรกจะเขา้ เขตวิกฤตnumber[i] := max(number[0], number[1], … , number[n-1] + 1;//ให้ priority (บตั รคิว) คนถดั ไปchoosing[i] := false; //นงั่ รอก่อนfor j := 0 to n – 1do beginwhile choosing[j] do no-op; //ใครอยใู่ นเขตวกิ ฤตก่อนหนา้ หรือเปล่า ถา้ มีตอ้ งรอก่อนwhile number [j]  0 //โปรเซสที่มาทีหลงั ตอ้ งไม่เป็น 0 ถึงจะไดเ้ ขา้ เขตวิกฤตand (number[j],j) < (number[i],i) do no-op;end;critical sectionnumber[i] := 0; //ออกจากเขตวิกฤตremainder sectionuntil false; เพื่อพิสูจนว์ า่ bakery algorithm ถูกตอ้ ง เราตอ้ งแสดงใหเ้ ห็นวา่ ถา้ Pi อยใู่ นเขตวกิ ฤต และ Pk(k  1) ถูกเลือกให้ number[k]  0 ดงั น้นั (number[i],i) < (number[k],k) ผลลพั ธ์ที่ไดท้ าํ ใหผ้ า่ นคุณสมบตั ิ ห้ามอยู่พร้อมกนั (mutual exclusion) พิจารณา Pi อยใู่ นเขตวกิ ฤต และ Pk พยายามเขา้ เขตวิกฤตของ Pk เมื่อโปรเซส Pk ทาํ งานใน while บรรทดั ท่ี 2 โดยท่ี j = iทาํ ใหเ้ ห็นวา่  number[i]  0  (number[i],i) < (number[k],k)ดงั น้นั การทาํ งานจะวนรอบในบรรทดั while จนกระทง่ั Pi ออกจากเขตวกิ ฤตของ PI ถา้ เราตอ้ งการใหผ้ า่ นคุณสมบตั ิ ความก้าวหน้า (progress) และ การรอคอยแบบมขี อบเขต (bounded-waiting) ตอ้ งรับประกนั ไดว้ า่ โปรเซสเขา้ สู่เขตวิกฤตของมนั ดว้ ยวิธี FCFS2.3.3 เซมมาฟอร์ (Semaphores) วิธีการแกป้ ัญหาเขตวิกฤต ที่กลา่ วมาแลว้ ท้งั หมด ยงั คงไม่สะดวกในการใชง้ านกบั ปัญหาท่ีซบั ซอ้ นมากข้ึน เราจึงตอ้ งหาวิธีใหม่ เรียกวา่ semaphore semaphore S คือ ตวั แปรชนิด integer ซ่ึงสามารถกาํ หนดค่าเร่ิมตน้ ได้ และใชง้ านได้ โดยผา่ นคาํ สงั่ 2 คาํ สงั่ เท่าน้นั คือ wait และ signal (เดิม

108 ระบบปฏิบตั ิการคาํ ส่ัง wait เรียกว่า P ยอ่ มาจาก Proberen ในภาษาดชั แปลวา่ ทดสอบ และเดิมคาํ สงั่ signal เรียกว่าV ยอ่ มาจาก Verhogen ในภาษาดชั แปลวา่ เพม่ิ ข้ึน) คาํ สง่ั ท้งั สองน้ี มีนิยามด้งั เดิมดงั น้ีwait(S): while S  0 do no-op;S := S –1;signal(S): S := S + 1;การปรับปรุงแกไ้ ขค่าของ semaphore ใน wait และ signal จะทาํ แบบแยกกนั คนละส่วนไม่ได้ เม่ือโปรเซสหน่ึงปรับปรุงค่าของ semaphore โปรเซสอ่ืน ๆ จะมาปรับปรุงค่าของ semaphore น้นั ในเวลาเดียวกนั ไม่ได้นอกจากน้นั ในกรณีของ wait(s) การทดสอบค่าของ S (S  0) และการปรับปรุงค่า (S := S – 1)ตอ้ งทาํ โดยปราศจากการขดั จงั หวะ เราจะแสดงการสร้าง semaphore และคาํ สงั่ ท้งั สองน้ี ในหวั ขอ้ต่อไปจะพดู ถึงการใชง้ านเสียก่อน1. การใช้งานเซมมาฟอร์เราสามารถใช้ semaphore กบั ปัญหาเขตวิกฤต ที่มีโปรเซส n โปรเซสได้ โดยใหต้ วั แปรร่วมเป็นvar mutex : semaphore = 1;โปรแกรมสาํ หรับโปรเซส Pi เป็นดงั น้ีrepeatwait(mutex);critical sectionsignal(mutex);remainder sectionuntil false;เรายงั สามารถใช้ semaphore แกป้ ัญหาการประสานงาน (synchronization problem)แบบต่าง ๆ ได้อีก เช่น โปรเซส P1 ทาํ ประโยคคาํ ส่งั S1 และโปรเซส P2 ทาํ ประโยคคาํ สง่ั S2 โดยทาํ งานขนานกนัแต่เราตอ้ งการใหป้ ระโยค S2 ทาํ งานหลงั จากท่ีประโยค S1 เสร็จเรียบร้อยแลว้ เราสามารถใชต้ วั แปรร่วมvar synch : semaphore = 0;และเพมิ่ คาํ สงั่S1;signal(synch);ลงในโปรแกรมของโปรเซส P1 และเพมิ่ คาํ สง่ั

โปรเซส109wait(synch);S2; ลงในโปรเซส P2เนื่องจากค่าเร่ิมตน้ ของ synch เป็น 0 ดงั น้นั P2 จะทาํ ประโยค S2 ได้ กต็ ่อเม่ือ P1 ทาํ คาํ สง่ัsignal(synch); (ซ่ึงหมายความว่า P1 ทาํ ประโยค S1 เสร็จแลว้ )2. การสร้าง semaphore (Implementation) วิธีแกป้ ัญหาเขตวิกฤตท้งั หมดท่ีกล่าวมา มีขอ้ เสียหลกั ตรงที่ มี “การวนเวียนรอคอย” (busywaiting) เมื่อมีโปรเซสหน่ึง อยใู่ นเขตวิกฤต โปรเซสอื่น ๆ ที่ตอ้ งการเขา้ เขตวิกฤตบา้ ง ตอ้ งวนเวียนทดสอบค่าก่อนเขา้ เขตวิกฤตไปเรื่อย ๆ ยอ่ มเป็นเหตุใหเ้ วลาของหน่วยประมวลผลกลางเสียไปโดยเปล่าประโยชน์ (อยา่ ลืมว่า ในระบบของเรา มีหน่วยประมวลผลกลางเพียงตวั เดียว แต่ทาํ งานแบบหลายโปรแกรม โดยแต่ละโปรเซส สลบั กนั ใชห้ น่วยประมวลผลกลาง) ซ่ึงเวลาเหล่าน้ีอาจยกให้โปรเซสอ่ืน ไดใ้ ชป้ ระโยชน์คุม้ ค่ากว่า semaphore ประเภทน้ี เรียกว่า spinlock คือโปรเซสวนเวียนทาํ งาน (spin) อยู่ ขณะที่กาํ ลงั รอคอยให้เปิ ดลอ็ ค spinlock อาจมีประโยชน์มาก ในระบบที่มีหลายหน่วยประมวลผล คือ โปรเซสไม่ต้อง ถูกสลับออกไป (context switch) เมื่อต้องรอคอยล็อคโดยเฉพาะ ล็อคท่ีมีระยะเวลาส้ัน ๆ จะประหยดั เวลาได้มาก (ไม่ต้องเสียเวลา ยา้ ยเขา้ -ออก)เราสามารถปรับปรุงนิยามของคาํ ส่ัง wait และ signal ใหม่ เพ่ือให้ ไม่มีปัญหา การวนเวียนรอคอย(busy waiting) เมื่อโปรเซสทาํ คาํ สั่ง wait และพบว่า ค่าของ semaphore น้อยกว่าหรือเท่ากบั 0 โปรเซสจะตอ้ งรอคอย โดยการหยดุ ชว่ั ขณะ (block) แทนที่จะวนเวยี นรอคอย การหยดุ ชวั่ ขณะน้ี โปรเซสจะเขา้ ไปรอในแถวคอย (waiting queue) ที่เกี่ยวขอ้ งกบั semaphore น้ัน ๆ และเปลี่ยนสถานะเป็ นสถานะรอคอย (waiting state) การควบคุมจะถูกยา้ ยกลบั ไปท่ีตวั จดั ตารางการทาํ งานของหน่วยประมวลผลกลาง เพื่อจดั ใหโ้ ปรเซสอ่ืนทาํ งานต่อไป โปรเซสที่หยดุ ชว่ั ขณะ (block) โดยรอ semaphore S น้ี จะสามารถดาํ เนินต่อได้ เม่ือมีโปรเซสอ่ืนทาํ คาํ สง่ั signal กบั semaphore S ภายในคาํ สงั่ signal จะมีการปลุก (wakeup) ใหโ้ ปรเซส ที่หยดุชว่ั ขณะ กลบั ดาํ เนินการต่อได้ โดยเปล่ียนสถานะของโปรเซสน้นั เป็น สถานะพร้อม (ready state)แลว้ ยา้ ยไปต่อแถวพร้อม (ซ่ึงหน่วยประมวลผลอาจยา้ ยไปทาํ งานในโปรเซสพร้อมตวั ใหม่น้ีทนั ทีหรือเม่ือไรน้นั ข้ึนอยกู่ บั วธิ ีการจดั ตารางการทาํ งาน)การสร้าง semaphore ตามนิยามใหม่น้ี กาํ หนดให้ semaphore เป็น record (struct ในภาษา c)type semaphore = recordvalue: integer;L: list of process;end;

110 ระบบปฏิบตั ิการ semaphore จะประกอบดว้ ย ตวั เลขจาํ นวนเตม็ (ตวั แปร value) และแถวคอยของโปรเซส (ตวัแปร L) เมื่อโปรเซสหน่ึงตอ้ งคอย semaphore น้ี มนั กจ็ ะถกู ใส่ช่ือลงในแถวคอย L การใชค้ าํ สง่ัsignal จะดึงโปรเซสออกจากหวั แถวคอยน้ี และปลุกโปรเซสท่ีได้ ใหก้ ลบั ไปทาํ งานต่อ เราจึงแกไ้ ขโปรแกรมคาํ สงั่ เป็นดงั น้ีwait(S): S.value := S.value – 1;if S.value < 0then beginadd this process to S.L;block;end;signal(S): S.value := S.value + 1;if S.value  0then beginremove a process P from S.L;wakeup(P);end; คาํ ส่งั block จะทาํ ใหโ้ ปรเซสท่ีทาํ คาํ สงั่ น้ี หยดุ ชวั่ ขณะ และคาํ สง่ั wakeup(P) จะปลกุโปรเซส P ใหก้ ลบั ทาํ งานต่อ คาํ สง่ั ท้งั สองน้ี เป็นคาํ สั่งเรียกระบบ อยา่ งหน่ึง จะสงั เกตไดว้ า่ นิยามด้งั เดิมของ semaphore ซ่ึงมีการวนเวียนรอคอยน้นั ค่าของ semaphore จะไม่ติดลบ แต่ในนิยามใหม่น้ี ค่าของ semaphore มีค่าเป็นลบได้ ค่าท่ีเป็นลบแสดงถึงจาํ นวนโปรเซสที่รอคอย semaphore ตวัน้นั ๆ ดว้ ย ท้งั น้ีเน่ืองมาจากการลดค่า semaphore ลง ก่อนการทดสอบค่าในคาํ สง่ั wait แถวคอยของโปรเซส เป็น link list ของขอ้ มูลจาํ เพราะของโปรเซส (PCB) ดงั น้นั semaphore แต่ละตวั จะมีค่าตวั เลข และตวั ช้ีไปยงั แถวคอยน้ี เพ่อื ที่จะใหแ้ น่ใจวา่ การรอคอยในแถวจะเป็น “การรอคอยอยา่ งจาํ กดั ” เราอาจกาํ หนดให้ แถวคอยน้ีเป็นแบบ มาก่อน-ออกก่อน (FIFO) (เหมือนกบั FCFS) หรือแบบอ่ืน ๆ กไ็ ด้ เราตอ้ งไมใ่ หม้ ีโปรเซสสองตวั ทาํ คาํ สงั่ wait และ signal บน semaphore ตวั เดียวกนัในเวลาเดียวกนั ซ่ึงกรณีน้ี กค็ ือ ปัญหาเขตวิกฤตแบบหน่ึงนนั่ เอง โดยสามารถเลือกวิธีจดั การได้ 2วธิ ี คือ

โปรเซส111 1. ถา้ เป็นระบบที่มีหน่วยประมวลผลเพยี งตวั เดียว เรากเ็ พยี งแต่หา้ มขดั จงั หวะ (interrupt) ขณะที่กาํ ลงั ทาํ งานคาํ สง่ั wait และ signal ดงั น้นั โปรเซสอื่น จะไม่สามารถมาขดั จงั หวะ การทาํ งานได้ 2. ถา้ เป็นระบบที่มีหน่วยประมวลผลหลายตวั การหา้ มขดั จงั หวะ จะไม่เพยี งพอเพราะโปรเซส อ่ืน อาจทาํ งานอยใู่ นหน่วยประมวลผล คนละตวั กบั โปรเซสที่หา้ มขดั จงั หวะ (นอกเสียจาก วา่ มีคาํ สง่ั พเิ ศษ ที่สามารถหา้ มขดั จงั หวะไดท้ ุก ๆ หน่วยประมวลผลพร้อมกนั ) เราอาจ จดั การ โดยใชข้ ้นั ตอนวิธี ในหวั ขอ้ 6.2 (critical section) แลว้ เอาคาํ สงั่ wait และ signal ใส่ ไวใ้ นเขตวกิ ฤต กจ็ ะสามารถป้องกนั ได้จะเห็นไดว้ า่ วิธีหลงั น้ี เราไม่สามารถกาํ จดั การวนเวียนรอคอย (busy waiting) ไปไดห้ มด เพยี งแต่กาํ จดั การวนเวยี นรอคอยของโปรแกรม ก่อนจะเขา้ เขตวกิ ฤตของตน แต่เน่ืองจากคาํ สงั่ wait และsignal ค่อนขา้ งส้นั (ไม่ควรเกิน 10 คาํ สงั่ ในฮาร์ดแวร์) เขตวิกฤตน้ี จึงมกั วา่ งตลอดเวลาเสมือนวา่ไม่มีการวนเวียนรอคอย เกิดข้ึนเลย หรือเกิดข้ึนกเ็ พยี งเวลาส้ันมาก เม่ือเทียบกบั เขตวกิ ฤตของโปรแกรมอื่น ๆ ทวั่ ไป การครอบครองเขตวิกฤต อาจกินเวลานานมาก (เป็นชว่ั โมงกไ็ ด)้ จึงไม่ควรใชก้ ารป้องกนั แบบมี การวนเวียนรอคอย (busy waiting)3. วงจรอบั และการแช่เยน็ (Deadlock and Starvation)การใช้ semaphore อาจทาํ ให้ โปรเซสต่างรอกนั เอง อยา่ งไม่มีท่ีสิ้นสุด โดยต่างรอใหอ้ ีกโปรเซสหน่ึงทาํ คาํ สงั่ signal เหตุการณ์น้ีเราเรียกวา่ วงจรอบั (deadlock) ลองพจิ ารณา ระบบท่ีมีโปรเซส P0และ P1 ใช้ semaphore S และ Q มีค่าเริ่มตน้ เป็น 1 P0 P1 wait (S); wait(Q); wait (Q); wait(S); .. .. .. signal(S); signal(Q); signal(Q); signal(S);

112 ระบบปฏิบตั ิการสมมติว่า P0 ทาํ คาํ สงั่ wait(S) แลว้ P1 ทาํ คาํ สง่ั wait(Q) ต่อจากน้นั เม่ือ P0 ทาํ คาํ สง่ั wait(Q) P0 ก็จะตอ้ งรอจนกระทงั่ P1 ทาํ คาํ สง่ั signal(Q) ส่วน P1 ต่อมาทาํ คาํ สัง่ wait(S) กจ็ ะตอ้ งหยดุ รอจนกระทง่ั P0 ทาํ คาํ สงั่ signal(S) จะเห็นไดว้ า่ ท้งั P0 และ P1 อยใู่ น วงจรอบั เรากล่าววา่ กลุ่มของโปรเซสตกอยใู่ นสถานะวงจรอบั เมื่อทุก ๆ โปรเซสในกลุ่มต่างรอเหตุการณ์บางอยา่ ง ท่ีจะทาํ ให้เกิดข้ึนได้ โดยโปรเซสในกลุ่มน้ีเท่าน้นั เหตุการณ์ท่ีวา่ น้ีคือการถือครอง และการปล่อยทรัพยากร ปัญหาอีกอยา่ งหน่ึงที่ใกลเ้ คียงกบั ปัญหาวงจรอบั คือ ปัญหา การแช่เยน็ โปรเซสหน่ึงอาจตอ้ งรอคอย semaphore อยา่ งไม่มีท่ีสิ้นสุด ถา้ เราจดั การแถวคอยใน semaphore เป็น แบบมาหลงั -ออกก่อน (LIFO)1. Binary Semaphores semaphore ท่ีผา่ นมาเป็น counting semaphore ค่าของมนั เป็นเลขจาํ นวนเตม็ แบบไม่จาํ กดั แต่binary semaphore มีค่าอยรู่ ะหวา่ ง 0 กบั 1 เราจะแสดงถึงวธิ ีใช้ counting semaphore ใหเ้ ป็นแบบbinary semaphore ไดโ้ ดย ให้ S แทน counting semaphore ตามโครงสร้างของขอ้ มลู ดงั น้ีvar S1: binary-semaphore;S2: binary-semaphore; C: integer;เร่ิมตน้ ให้ S1 = 1, S2 = 0 ค่าของ C ถูกกาํ หนดเป็นค่าเร่ิมตน้ ของ counting semaphore Sการใชค้ าํ สง่ั wait บน counting semaphore S ทาํ ไดด้ งั น้ีwait(S1);C := C – 1;if C < 0then beginsignal(S1);signal(S2);endsignal(S1);การใชค้ าํ สงั่ signal บน counting semaphore S ทาํ ไดด้ งั น้ีwait(S1);C := C+ 1;if C  0then signal(S2)

โปรเซส113else signal(S1);2.3.4 ชนิดของปัญหาการซิงโครไนซ์ (Classical Problems of Synchronization) ในหวั ขอ้ น้ี เราจะกล่าวถึงปัญหาในการประสานงาน ท่ีเป็นแม่แบบด้งั เดิม ซ่ึงใชเ้ ป็นตวั แทนปัญหาต่าง ๆ ในระบบการทาํ งานแบบขนาน แม่แบบเหล่าน้ี ยงั สามารถใชเ้ ป็นตวั ทดสอบข้นั ตอนวิธีใหม่ ๆ ท่ีสร้างข้ึนเพื่อจดั การปัญหาการประสานงาน ไดเ้ ป็นอยา่ งดีอีกดว้ ย1. ปัญหาทพ่ี กั ข้อมูลขนาดจาํ กดั (The Bounded-Buffer Problem) กาํ หนดให้ ที่พกั ขอ้ มูลมีขนาด n ช่อง แต่ละช่องเกบ็ ขอ้ มูลได้ 1 ตวั ให้ semaphore mutex มีค่าเริ่มตน้ เป็น 1 ตวั ป้องกนั การใชท้ ี่พกั ขอ้ มูลคือ semaphore empty และ full เป็นตวั นบั วา่ ท่ีพกั ขอ้ มูลมีจาํ นวนช่องวา่ ง และ ช่องเตม็ (มีขอ้ มูลอย)ู่ ก่ีช่อง โดย empty มีค่าเริ่มตน้ เป็น n และ full มีค่าเริ่มตน้เป็น 0repeat…produce an item in nextp…wait(empty);wait(mutex);…add nextp to buffer…signal(mutex);signal(full);until false;โครงสร้างของโปรเซสผู้ผลติrepeatwait(full);wait(mutex);

114 ระบบปฏิบตั ิการ…remove an item from buffer to nextc…signal(mutex);signal(empty);…consume the item in nextc…until false;โครงสร้างของโปรเซสผู้ใช้จะสงั เกตเห็นวา่ โปรแกรมท้งั สองสมมาตรกนั (เหมือนกนั ) คือ เราสามารถใชเ้ ป็นโปรแกรมร่วมกนั ไดว้ ่า ผผู้ ลิต ผลิต full buffer ใหผ้ ใู้ ช้ หรือ ผใู้ ชผ้ ลิต empty buffer ใหผ้ ผู้ ลิต2. ปัญหาผู้อ่าน-ผู้เขยี น (The Readers and Writers Problem) โปรเซสต่าง ๆ มกั มีการใชข้ อ้ มูลร่วมกนั (เช่นใชแ้ ฟ้มขอ้ มูลเดียวกนั ) บางโปรเซสตอ้ งการอ่าน บางโปรเซสตอ้ งการแกไ้ ข เราแบ่ง กลุ่มของโปรเซสเหล่าน้ี ออกเป็น 2 พวก คือ พวกท่ีตอ้ งการอ่านอยา่ งเดียว เรียกวา่ “ผอู้ ่าน” (readers) ส่วนพวกที่เหลือ เรียกวา่ “ผเู้ ขียน” (writers) จะเห็นไดว้ า่ผอู้ ่านหลายคน อาจอา่ นขอ้ มูลร่วมกนั ไดพ้ ร้อม ๆ กนั โดยไม่เสียหาย แต่ผเู้ ขียน 1 คน กบั อีกคนหน่ึง(ซ่ึงอาจเป็น ผอู้ ่าน หรือ ผเู้ ขียนกไ็ ด)้ ไม่อาจทาํ การพร้อม ๆ กนั บนขอ้ มูลร่วมน้ีได้ (อาจทาํ ได้ แต่อาจมีขอ้ ผดิ พลาดเกิดข้ึนตามมา) เพอ่ื ป้องกนั ปัญหาน้ี เราตอ้ งใหผ้ เู้ ขียน ใชข้ อ้ มูลร่วม เพียงคนเดียวในขณะหน่ึง ๆ ปัญหาการประสานงานแบบน้ี เราเรียกวา่ ปัญหาผอู้ า่ น-ผเู้ ขียน (Readers-Writers Problem)หมายความวา่ ถา้ ขอ้ มูลร่วม มีผอู้ ่านคนอ่ืน กาํ ลงั อ่านอยู่ ผทู้ ่ีเขา้ มาใหม่สามารถใชข้ อ้ มูลร่วมไดเ้ ลยแมว้ า่ จะมีผเู้ ขียนรอใชอ้ ยกู่ ต็ าม แบบที่ 2 เม่ือผเู้ ขียนพร้อม ผเู้ ขียนจะสามารถใชข้ อ้ มูลร่วมไดเ้ ร็วที่สุดเท่าท่ีจะทาํ ได้ หมายความวา่ เม่ือมีผเู้ ขียนรออยู่ ผอู้ ่านใหม่หา้ มเขา้ ไปอ่านร่วม (ตอ้ งรอหลงั จากผเู้ ขียน)จะสงั เกตไดว้ า่ ท้งั สองแบบอาจทาํ ใหเ้ กิด “การแช่เยน็ ” ได้ แบบแรกผเู้ ขียนอาจถูกแช่เยน็ แบบที่ 2ผอู้ ่านอาจถูกแช่เยน็ จึงตอ้ งมีแบบท่ี 3 ท่ี 4 อีก แต่ในที่น้ี จะแสดงวิธีแกป้ ัญหาเฉพาะแบบแรกในการแกป้ ัญหาผอู้ ่าน-ผเู้ ขียนแบบแรก กาํ หนดใหต้ วั แปรร่วมเป็นดงั น้ีvar mutex, wrt : semaphore =1;readcount : integer = 0;

โปรเซส115ตวั แปร readcount เป็นตวั นบั จาํ นวน ผอู้ ่านทีก่าํ ลงั อ่านอยู่ semaphore mutex ใชป้ ้องกนั ตวั แปรreadcount semaphore wrt ใชป้ ้องกนั ผเู้ ขียน ผอู้ ่านคนแรก และคนสุดทา้ ย ท่ีเขา้ และออกจากเขตวกิ ฤตตอ้ งใช้ semaphore wrt ดว้ ย ส่วนผอู้ ่านคนกลาง ๆ ไม่ตอ้ งใช้ semaphore wrtwait(wrt);…writing is performed…signal(wrt);โครงสร้างของกระบวนการผเู้ ขียนwait(mutex);readcount := readcount + 1;if readcount = 1 then wait(wrt);signal(mutex);…reading is performed…wait(mutex);readcount := readcount – 1;if readcount = 0 then signal(wrt);signal(mutex);โครงสร้างของกระบวนการผอู้ ่านสงั เกตวา่ ถา้ ผเู้ ขียนอยใู่ นเขตวกิ ฤต และมีผอู้ ่านรออยู่ n คน ผอู้ ่าน 1 คนจะรออยทู่ ี่ semaphore wrtส่วนผอู้ ่าน n – 1 คน จะรออยทู่ ่ี semaphore mutex และเมื่อผเู้ ขียนทาํ คาํ สงั่ signal(wrt) อาจไปปลุกผอู้ ่านท้งั หมด หรือผเู้ ขียน 1 คน ซ่ึงรออยกู่ ไ็ ด้ ข้ึนอยกู่ บั การออกแบบตวั จดั ตารางแถวคอย3. ปัญหาอาหารเยน็ ของนักปราชญ์ (The Dining-Philosopher’ s Problem)มีนกั ปราชญ์ 5 คน วนั ๆ มีแต่นง่ั คิด และกก็ ิน โดยนกั ปราชญ์ 5 คน จะนง่ั อยรู่ อบโตะ๊ กลมตวั หน่ึงร่วมกนั มีชามขา้ ว 5 ใบ ของแต่ละคน แต่มีตะเกียบอยู่ 5 อนั วางอยรู่ ะหวา่ งชาม ดงั รูป

116 ระบบปฏิบตั ิการ รูปท่ี 2.39 อาหารเยน็ ของนักปราชญ์ปราชญแ์ ต่ละคน จะนง่ั คิด จนกระทงั่ หิว กจ็ ะพยายามหยบิ ตะเกียบ 2 ดา้ ม จากซา้ ยมือ และ ขวามือที่ใกลต้ วั ท่ีสุด อาจจะมีนกั ปราชญค์ นหน่ึงไดต้ ะเกียบมาขา้ งเดียว ถา้ ตะเกียบไม่วา่ ง เขากจ็ ะรอนกั ปราชญจ์ ะกินขา้ วจนอิ่ม แลว้ จึงวางตะเกียบลง จากน้นั กจ็ ะนงั่ คิดต่อไปปัญหาอาหารเยน็ ของนกั ปราชญน์ ้ีนบั เป็น ปัญหาแม่แบบปัญหาหน่ึง เพราะสามารถใชแ้ ทนปัญหาต่าง ๆ ในระบบการทาํ งานแบบขนานไดม้ ากมาย การแกป้ ัญหาน้ี ทาํ ไดโ้ ดยการกาํ หนด ตวั แปรร่วมดงั น้ี  ใหน้ กั ปราชญน์ งั่ ในโตะ๊ ได้ ไม่เกิน 4 คน  ใหน้ กั ปราชญห์ ยบิ ตะเกียบได้ กต็ ่อเม่ือ ตะเกียบท้งั สองขา้ งเขา วา่ งท้งั คู่ (ตอ้ งทาํ ใน เขตวกิ ฤตดว้ ย)  ใชว้ ิธีแกป้ ัญหาแบบ asymmetric (สลบั กนั ) โดยให้นกั ปราชญค์ นที่เลขคี่ หยบิ ตะเกียบขา้ งซา้ ย ก่อนขา้ งขวา นกั ปราชญค์ นท่ีเลขคู่หยบิ ขา้ งขวาก่อนขา้ งซา้ ยนอกจากน้ีเรายงั ตอ้ งคาํ นึงถึง ปัญหาการแช่เยน็ (starvation) ดว้ ยระบบที่ปราศจากปัญหาวงจรอบัไม่ไดห้ มายความวา่ จะปราศจากปัญหาการแช่เยน็ นกั ปราชญบ์ างคนอาจถูกแช่เยน็ จนตายไปในที่สุด2.3.5 อาณาเขตวกิ ฤต (Critical Region) แมว้ า่ การใช้ semaphore จะสะดวกและไดผ้ ลดี ในการประสานงานระหวา่ งโปรเซส แต่ถา้ ใช้วธิ ีผิด กอ็ าจเกิดขอ้ ผดิ พลาดข้ึนได้ และขอ้ ผดิ พลาดท่ีเกิดข้ึน กย็ ากท่ีจะตรวจพบ เพราะจะเกิดในบางสถานะการณ์เท่าน้นั โดยข้ึนอยกู่ บั ลาํ ดบั การทาํ งานของโปรเซสเหล่าน้นัเราอาจเห็นไดจ้ ากการเกิดขอ้ ผดิ พลาด ในปัญหาผผู้ ลิต-ผใู้ ช้ (producer-consumer) ซ่ึงตวั แปรcounter อาจมีค่าผดิ พลาดไปจากท่ีควรจะเป็นเพียง 1 (ทาํ ใหต้ รวจจบั ไดย้ าก เพราะค่าจริงกบั ค่าผดิ พลาด มีค่าใกลเ้ คียงกนั มาก) ท้งั ยงั มีโอกาสท่ีจะเกิดข้ึนนอ้ ยมากอีกดว้ ย ในบางคร้ังอาจไม่เกิดเลย

โปรเซส117กไ็ ด้ แต่เรากย็ งั ถือวา่ อาจมีปัญหาการผดิ พลาด เน่ืองจากการเหล่ือมเวลากนั เราจึงตอ้ งใช้semaphore มาช่วยป้องกนั ขอ้ ผดิ พลาดน้ี และเช่นเดียวกนั แมจ้ ะใช้ semaphore แลว้ กย็ งั อาจเกิดขอ้ ผดิ พลาดได้ ถา้ ใช้ semaphore ไม่รอบคอบ ดงั ตวั อยา่ งต่อไปน้ีกาํ หนดใหต้ วั แปรร่วมเป็นvar mutex : semaphore = 1;ทุกโปรเซสที่จะเขา้ เขตวิกฤต ตอ้ งทาํ คาํ สงั่ wait(mutex) และเม่ือออกจากเขตวิกฤตแลว้ ตอ้ งทาํคาํ ส่ัง signal(mutex) ถา้ การทาํ คาํ สงั่ ท้งั สองน้ี ไม่เป็นไปตามลาํ ดบั หรือขาดหายไป อาจทาํ ใหม้ ีโปรเซส 2 โปรเซส อยใู่ นเขตวกิ ฤตพร้อมกนั ได้  ถา้ มีโปรเซสหน่ึงทาํ คาํ สงั่ wait และ signal บน semaphore mutex สลบั กนั ดงั น้ีsignal(mutex);…critical sectionwait(mutex);เป็นผลให้ อาจมีหลายโปรเซส เขา้ เขตวิกฤตพร้อมกนั ซ่ึงเราอาจตรวจพบได้ เมื่อมีเหตุการณ์เกิดข้ึนจริง (มีหลายโปรเซสอยใู่ นเขตวิกฤต) เท่าน้นั และกจ็ ะแกไ้ ขอะไรไม่ได้ เพราะไม่อาจยอ้ นหลงั ไปทาํ ซ้าํ หรือ หยดุ ระบบแลว้ ทาํ ใหม่ (ผลลพั ธ์จะคลาดเคล่ือนไป)  ถา้ มีโปรเซสหน่ึง ทาํ คาํ สงั่ wait(mutex) เม่ือออกจากเขตวิกฤต แทนที่จะทาํ คาํ สง่ั signal(mutex) ดงั น้ีwait(mutex);…critical sectionwait(mutex);ในกรณีน้ีจะเกิดปัญหาวงจรอบั ข้ึน  ถา้ มีบางโปรเซส ลืมทาํ คาํ ส่ัง wait หรือ signal หรือท้งั คู่ (เนื่องจากเขียนโปรแกรม ผิดพลาด) อาจทาํ ให้มีมากกว่า 1 โปรเซส อยใู่ นเขตวิกฤตพร้อมกนั หรือ เกิดปัญหา วงจรอบั ข้ึนในระบบจากตวั อย่างขา้ งตน้ น้ี จะเห็นไดว้ ่า อาจเกิดขอ้ ผิดพลาดข้ึนได้ หลายแบบ ถา้ เราใช้ semaphore ไม่ถูกวิธี อาณาเขตวิกฤต (Critical Region) บางคร้ัง เรียกวา่ อาณาเขตวกิ ฤตแบบมีเง่ือนไข (Conditional Critical Region)

118 ระบบปฏิบตั ิการรูปแบบภาษาช้นั สูง ท่ีใชใ้ นการประสานงานกนั แบบแรก คือ อาณาเขตวิกฤต (critical region) เรากาํ หนดใหต้ วั แปร v มีชนิดขอ้ มูลเป็น ตวั แปรร่วม T var v : shared T;การอา้ งถึงตวั แปรน้ี ตอ้ งทาํ ภายในประโยค (statement) region เท่าน้นั มีรูปแบบเป็น region v when B do S;หมายความวา่ ขณะท่ีโปรเซสหน่ึงกาํ ลงั ทาํ ประโยค S จะไม่มีโปรเซสอื่นใด ใชต้ วั แปร v ได้ นิพจน์B คือ Boolean ที่ถือครองการใชอ้ าณาเขตวิกฤต เม่ือโปรเซสหน่ึงพยายามเขา้ อาณาเขตวิกฤต นิพจน์B จะถกู ประเมิน ถา้ เป็นจริง ถึงจะทาํ S ถา้ เป็นเทจ็ โปรเซสตอ้ งรอ จนกระทงั่ B เป็นจริง และไม่มีโปรเซสอื่นอยใู่ นอาณาเขตวกิ ฤตของ v หรืออีกนยั หน่ึง ถา้ มี 2 โปรเซส ทาํ ประโยค S1 และ S2พร้อมกนั ดงั น้ีregion v when true do S1;region v when true do S2;ผลกค็ ือ การทาํ งานจริงจะเป็นไปตามลาํ ดบั “ซ่ึงอาจเป็น S1 ตามดว้ ย S2” หรือ “S2 ตามดว้ ย S1” ไม่มีการทาํ งานเหล่ือมกนั ระหวา่ งประโยค การใชอ้ าณาเขตวกิ ฤตน้ี จะสามารถป้องกนั ขอ้ ผดิ พลาดเบ้ืองตน้ ซ่ึงเกิดจากการใช้ semaphore ในการแกป้ ัญหาเขตวิกฤตซ่ึงอาจจะทาํ โดยผเู้ ขียนโปรแกรมได้ (แต่ไม่สามารถป้องกนั ขอ้ ผดิ พลาด ที่เกิดจากผเู้ ขียนโปรแกรมไดท้ ้งั หมด) รูปแบบอาณาเขตวิกฤตน้ี สามารถแกป้ ัญหาการประสานงานทวั่ ๆ ไปได้ ลองพจิ ารณาตวั อยา่ ง โปรแกรมสาํ หรับปัญหาที่พกั ขอ้ มูลขนาดจาํ กดั (bounded-buffer) ดงั น้ีกาํ หนดตวั แปรร่วมvar buffer: shared recordpool: array [0..n - 1] of item;count, in , out: integer;end;โปรเซสผผู้ ลิตแทรก ค่าใหม่ของ nextp เขา้ ในที่พกั ขอ้ มูลร่วม (shared buffer) โดยทาํ ดงั น้ีregion buffer when count < ndo beginpool[in] := nextp;in := (in + 1) mod n;count := count + 1;end;

โปรเซส119และโปรเซสของผใู้ ชจ้ ะลบคา่ จากที่พกั ขอ้ มูลร่วมแลว้ นาํ ไปไวใ้ น nextc โดยทาํ ดงั น้ีregion buffer when count > 0do beginnextc := pool[out];out := (out + 1) mod n;count := count – 1;end;ตวั แปลภาษา (compiler) สามารถแปลประโยค “อาณาเขตวกิ ฤตแบบมีเง่ือนไข” ได้ โดยสร้างsemaphore สาํ หรับตวั แปรร่วม ดงั น้ีvar mutex, first-delay, second-delay: semaphore;first-count, second-count: integer;semaphore mutex เร่ิมจาก 1 , first-delay และ second-delay เร่ิมจาก 0first-count และ second-count เริ่มจาก 0 เราป้องกนั การอยพู่ ร้อมกนั (mutual exclusive) ในเขตวิกฤต ดว้ ย semaphore mutex ถา้โปรเซสไม่สามารถเขา้ เขตวกิ ฤตได้ เพราะเง่ือนไข B เป็นเทจ็ โปรเซสจะตอ้ งรอ อยทู่ ี่ semaphorefirst-delay โปรเซสท่ีรออยใู่ น first-delay จะถูกยา้ ยไปที่ second-delay ก่อนที่จะถูกอนุญาตให้ประเมินเงื่อนไข B อีกคร้ัง เราสามารถนบั จาํ นวนโปรเซสที่รออยใู่ น first-delay และ second-delayดว้ ย first-count และ second-count เมื่อโปรเซสออกจากเขตวกิ ฤต มนั อาจเปล่ียนแปลงค่าเง่ือนไข B บางตวั ใหเ้ ป็นจริง ดงั น้นัเราจึงตอ้ งตรวจดูโปรเซส ซ่ึงรออยทู่ ี่ first-delay และ second-delay โดยใหโ้ ปรเซสแต่ละตวั ทดสอบเง่ือนไข B ของตนเองดูวา่ เป็นจริงหรือไม่ ถา้ โปรเซสใด พบวา่ เงื่อนไข B ของตนเป็นจริง กจ็ ะไดร้ ับอนุญาตใหเ้ ขา้ เขตวิกฤตได้ ไม่เช่นน้นั โปรเซสกต็ อ้ งรออยใู่ น first-delay และ second-delayต่อไปประโยค region x when B do S สามารถนาํ ไปใชด้ งั โปรแกรมขา้ งล่างน้ี จะเห็นว่า การใชง้ านน้ีจาํ เป็นตอ้ งประเมินค่านิพจน์B ของโปรเซสต่าง ๆ ที่รอคอยอยใู่ หม่ ทุกคร้ังท่ีโปรเซสท่ีอยใู่ นอาณาเขตวิกฤตออกมาwait(mutex);while not Bdo beginfirst-count := first-count + 1;if second-count > 0then signal(second-delay)else signal(mutex);

120 ระบบปฏิบตั ิการwait(first-delay);first-count := first-count – 1;second-count := second-count + 1;if first-count > 0then signal(first-delay)else signal(second-delay);wait(second-delay);second-count := second-count – 1;end;S;if first-count > 0then signal(first-delay);else if second-count >0then signal(second-delay);else signal(mutex);2.4 เดตลอ็ ก(DEADLOCK) ในการทํางานแบบ Multiprogramming จะมีหลาย ๆ โปรเซสพยายามที่จะแย่งกันใช้ทรัพยากรของระบบ แต่ละโปรเซส จะร้องขอทรัพยากรจากระบบ และถา้ ในขณะน้นั ทรัพยากรที่ตอ้ งการยงั ไม่ว่าง (มีโปรเซสอ่ืนครอบครองอย)ู่ โปรเซสน้นั จะตอ้ งรอคอย และอาจจะพบว่า การรอคอยน้ันจะเป็ นไปอย่างไม่มีท่ีสิ้นสุด ซ่ึงสถานการณ์เช่นน้ีเราเรียกว่า เดตล็อก(deadlock) ซ่ึงเคยกล่าวถึงอยา่ งยอ่ ๆ แลว้ ในบทท่ี 2 ในหวั ขอ้ semaphore ในบทน้ีจะอธิบายเก่ียวกบั วิธีการจดั การปัญหาเดตลอ็ กโดยส่วนใหญ่แลว้ ระบบปฏิบตั ิการ ท่ีมีอยู่ในปัจจุบนั ยงั ไม่ไดม้ ีการป้องกนั ปัญหาเดตล็อกเพราะเห็นว่า ยงั เป็ นปัญหาที่ไม่สําคญั แต่ในอนาคต ปัญหาวงจรอบั จะมีความสําคญั มากข้ึน เนื่องจากการขยายตัว ของระบบคอมพิวเตอร์รวมท้งั การขยายตวั ของทรัพยากรในระบบ และ โปรเซสที่มีปริมาณมากข้ึนดว้ ย รูปท่ี 2.40 รูปแบบการจาํ ลองสถานะการเดตลอ็ ก

โปรเซส1212.4.1 รูปแบบของเดตลอ็ ก (System Model) ระบบคอมพวิ เตอร์ทว่ั ไป มกั ประกอบไปดว้ ย ทรัพยากรจาํ นวนจาํ กดั ซ่ึงจะตอ้ งแบ่งปันให้โปรเซสต่าง ๆ ในระบบเพื่อใชท้ าํ งาน ทรัพยากรเหล่าน้ี มีหลายชนิด ไดแ้ ก่ เวลาของหน่วยประมวลผลกลาง (CPU-Time) เน้ือที่ในหน่วยความจาํ หลกั (Memory Space) , แฟ้มขอ้ มูล (File) ,และ อุปกรณ์รับส่งขอ้ มูล (I/O device) โดยท่ีทรัพยากรแต่ละชนิด อาจมีจาํ นวนมากกวา่ 1 ตวั การกาํ หนดชนิด หรือ แยกประเภทของทรัพยากร สามารถทาํ ได้ โดยหลกั การง่าย ๆ ดงั น้ี ถา้โปรเซสหน่ึง ร้องขอใชท้ รัพยากรชนิดหน่ึง 1 ตวั แลว้ ระบบสามารถจดั สรร ทรัพยากรชนิดน้นั ตวัใดกไ็ ดใ้ ห้ แสดงวา่ ทรัพยากรเหล่าน้นั เป็นชนิดเดียวกนั (ใชแ้ ทนกนั ได)้ แต่ถา้ ระบบจาํ ตอ้ งจดัทรัพยากร เฉพาะตวั ที่ระบุแลว้ เราจะถือวา่ ทรัพยากรเหล่าน้นั ไม่เหมือนกนั หรือเป็นคนละชนิดกนั เช่น เราอาจกาํ หนดใหเ้ คร่ืองพมิ พ์ 2 เครื่องในระบบ (ซ่ึงเหมือนกนั ทุกประการ) เป็นทรัพยากรชนิดเดียวกนั ได้ กต็ ่อเมื่อ ผใู้ ชไ้ ม่สนใจวา่ ผลลพั ธ์ของเขาจะพมิ พอ์ อกทางเครื่องใด (ใน 2 เครื่องน้ี)แต่ถา้ เครื่องพิมพเ์ ครื่องหน่ึง อยชู่ ้นั ที่ 9 และอีกเคร่ืองอยชู่ ้นั ใตด้ ิน ผใู้ ชอ้ ยบู่ นช้นั ที่ 9 ยอ่ มเห็นวา่เครื่องพิมพท์ ้งั สองน้ี ไม่เหมือนกนั แน่นอน ดงั น้นั เราตอ้ งกาํ หนดใหเ้ คร่ืองพมิ พท์ ้งั สองน้ี เป็นทรัพยากรต่างชนิดกนั โปรเซสหน่ึง ๆ จะตอ้ งร้ องขอใชท้ รัพยากรก่อนที่จะไดใ้ ชท้ รัพยากรน้นั และ จะตอ้ งคืนทรัพยากรน้นั กลบั สู่ระบบเม่ือใชเ้ สร็จ โปรเซสอาจจะร้องขอทรัพยากร ไดม้ ากเท่าที่ตอ้ งการเพื่อที่จะทาํ งานของตนใหเ้ สร็จสมบูรณ์ แต่จาํ นวนทรัพยากรท่ีร้องขอจะตอ้ งไม่มากกวา่ จาํ นวนท่ีมีอยจู่ ริงในระบบ เช่น ในระบบที่มีเคร่ืองพิมพ์ 2 เครื่อง โปรเซส Pi ไม่สามารถที่จะร้องขอเครื่องพิมพ์ 3 เคร่ืองได้เม่ือโปรเซสตอ้ งการใชท้ รัพยากรของระบบ จะตอ้ งทาํ ตามลาํ ดบั ข้นั ตอนต่าง ๆ ดงั น้ี 1. การร้องขอ (Request) ถา้ การร้องขอน้นั ไม่ไดร้ ับการอนุมตั ิจากระบบในทนั ที (เช่น ทรัพยากรที่ตอ้ งการน้นั กาํ ลงั ถูกใชง้ านโดยโปรเซสอ่ืน) ดงั น้นั โปรเซสที่ ร้องขอ จะตอ้ งรอจนกว่าจะไดร้ ับทรัพยากรท่ีตอ้ งการ 2. การใช้งาน (Use) โปรเซสน้นั สามารถใชง้ านทรัพยากรท่ีไดร้ ับ เช่น ในกรณีท่ี ทรัพยากรท่ีร้องขอคือ เคร่ืองพิมพ์ เมื่อไดร้ ับการจดั สรรจากระบบแลว้ โปรเซสน้นั สามารถพมิ พข์ อ้ มูลออกทางเคร่ืองพิมพไ์ ด้ 3. การคืน (Release) โปรเซสตอ้ งคืนทรัพยากรที่ใชเ้ สร็จแลว้ กลบั สู่ระบบ การร้องขอ และการคืนทรัพยากร คือ คาํ ส่ังเรียกระบบ (System calls) ในการใชท้ รัพยากรแต่ละคร้ัง ระบบปฏิบัติการจะตรวจสอบ เพื่อให้แน่ใจว่า โปรเซสไดร้ ้องขอทรัพยากร และได้ถูกจดั สรรทรัพยากรให้เรียบร้อยแลว้ โดยที่ระบบจะมีตารางที่ใชใ้ นการบนั ทึกว่า ขณะน้ีทรัพยากรใดยงั ว่างอยู่ หรือกาํ ลงั ถูกใชง้ าน ถา้ กาํ ลงั ถูกใชง้ าน ก็จะตรวจดูว่าโปรเซสใดเป็ นผูใ้ ชง้ านอยู่ และถา้

122 ระบบปฏิบตั ิการโปรเซสไดร้ ้องขอทรัพยากรท่ีกาํ ลงั ถูกใชง้ าน โดยโปรเซสอื่นอยู่ โปรเซสท่ีร้องขอจะถูกจดั เขา้ ไปอยใู่ นแถวคอยของโปรเซสที่รอคอยการใชท้ รัพยากรน้นั อยู่ กลุ่มของโปรเซส จะตกอยใู่ นสถานะเดตลอ็ กเมื่อทุก ๆ โปรเซส ที่อยใู่ นกลุ่มน้นั ต่างกก็ าํ ลงัรอคอย ท่ีจะใชท้ รัพยากรที่กาํ ลงั ถูกใช้ โดยโปรเซสอื่นในกลุ่มน้นั สถานการณ์ท่ีเราจะใหค้ วามสนใจ เป็นอยา่ งมากในท่ีน้ีคือ การร้องขอและการคืนทรัพยากร ทรัพยากรอาจจะเป็นทรัพยากรเชิงกายภาพ (เช่น เคร่ืองพมิ พ์ เครื่องขบั เทป เน้ือท่ีหน่วยความจาํ และเวลาของหน่วยประมวลผลกลาง)หรือทรัพยากรเชิงตรรกะ (เช่น แฟ้มขอ้ มูล semaphore เป็นตน้ ) นอกจากน้ียงั มีสถานะการณ์อ่ืนอีกที่อาจเกิดมีวงจรอบั ข้ึนได้ เช่น การส่ือสารระหวา่ งโปรเซสเพ่ือท่ีจะแสดงให้เห็นภาพของสถานะเดตลอ็ กเราจะมาพิจารณา ระบบท่ีประกอบไปดว้ ยเคร่ืองขบัเทป 3 เครื่อง สมมติว่า มีโปรเซสอยู่ 3 โปรเซส และแต่ละโปรเซส กาํ ลังใช้เครื่องขบั เทปอยู่โปรเซสละเคร่ือง ต่อมาถา้ แต่ละโปรเซส ร้องขอเคร่ืองขบั เทปเพิ่มอีกโปรเซสละ 1 เคร่ือง ท้งั 3โปรเซส จะติดอยู่ในวงจรอบั ทนั ที โดยแต่ละโปรเซสกาํ ลงั รอสถานการณ์ที่ “เคร่ืองขบั เทปถูกปล่อยคืนสู่ระบบ” ซ่ึงเป็ นสถานการณ์ท่ีข้ึนกบั โปรเซสอื่น ในวงจร (ที่กาํ ลงั รอคอยทรัพยากรอยู่เช่นกนั ) ตวั อยา่ งท่ียกมาน้ีเป็ นการแสดงภาพของวงจรอบั ท่ีเกิดจากการที่โปรเซสพยายามที่จะแย่งกนั ใชท้ รัพยากรประเภทเดียวกนั วงจรอบั อาจจะเกิดข้ึน กบั ทรัพยากรท่ีต่างประเภทกนั กไ็ ด้ เช่น ระบบมีเคร่ืองพมิ พ์ 1 เครื่องและ เครื่องขบั เทป 1 เครื่อง สมมติวา่ โปรเซส Pi กาํ ลงั ใชเ้ คร่ืองขบั เทปอยู่ ส่วน Pj กก็ าํ ลงั ใช้เครื่องพิมพ์ ถา้ ต่อมา Pi ร้องขอเคร่ืองพิมพ์ เพมิ่ และ Pj ร้องขอเคร่ืองขบั เทปเพมิ่ กจ็ ะเกิดวงจรอบัทนั ทีลกั ษณะของเดตลอ็ ก(Deadlock Characterization) เราพบวา่ วงจรอบั เป็นสถานการณ์ที่ไม่เป็นท่ีตอ้ งการจะใหเ้ กิดข้ึนในระบบ เพราะวา่ เมื่อเกิดวงจรอบั แลว้ จะพบวา่ ไม่มีโปรเซสใด ไดท้ าํ งานจนเสร็จสมบูรณ์ และทรัพยากรของระบบต่างกถ็ ูกครอบครองจนหมด ซ่ึงจะเป็นตวั กนั ไม่ใหง้ านอ่ืนไดท้ าํ งาน ก่อนที่เราจะพดู ถึงวธิ ีต่าง ๆ ท่ีจะใชก้ ารแกป้ ัญหาวงจรอบั น้นั เราจะอธิบายลกั ษณะของวงจรอบั ก่อน1. เง่ือนไขในการตดิ เดตลอ็ ก(Necessary Conditions)วงจรอบั จะเกิดข้ึนไดก้ ต็ ่อเมื่อ1.1 ทรัพยากรเป็ นแบบใช้ร่วมกนั ไม่ได้ (Mutual exclusion) นน่ั คือ จะตอ้ งมีทรัพยากรอยา่ งนอ้ ย 1ตวั จดั อยใู่ นกลมุ่ ทรัพยากรที่ใชร้ ่วมกนั ไม่ได้ นน่ั คือ จะมีเพยี ง 1 โปรเซสเท่าน้นั ท่ีจะใชท้ รัพยากรตวั น้นั ได้ ถา้ มีโปรเซสอื่นร้องขอทรัพยากรที่กาํ ลงั ถูกใชอ้ ยู่ โปรเซสน้นั จะตอ้ งรอ จนกระทง่ัทรัพยากรน้นั ถูกคืนกลบั สู่ระบบแลว้

โปรเซส1231.2 การถือครองแล้วรอคอย (Hold and Wait) คือ มีอยา่ งนอ้ ยหน่ึงโปรเซส ที่กาํ ลงั ถือครองทรัพยากรอยอู่ ยา่ งนอ้ ย 1 ตวั และขณะเดียวกนั กก็ าํ ลงั รอคอยทรัพยากรเพม่ิ อีก แต่เป็นทรัพยากรท่ีกาํ ลงั ถูกถือครอง โดยโปรเซสอื่นอยู่1.3 ห้ามแทรกกลางคนั (No Preemption) เม่ือโปรเซสกาํ ลงั ใชท้ รัพยากรอยู่ จะไม่มีการแทรกกลางคนั หรือ ทรัพยากรท่ีถูกใชง้ าน จะถกู ปล่อยคืนสู่ระบบ โดยความสมคั รใจของโปรเซสน้นั คือเม่ือโปรเซสน้นั ไดท้ าํ งานจนเสร็จสมบูรณ์แลว้1.4 วงจรรอคอย (Circular Wait) คือ เซตของโปรเซส ท่ีกาํ ลงั รอคอยทรัพยากร (P0, P1, … , Pn)ซ่ึง P0 กาํ ลงั รอคอยทรัพยากรท่ีถือครองโดย P1 , P1 กาํ ลงั รอคอยทรัพยากร ท่ีถือครองโดย P2 , … ,Pn-1 กาํ ลงั รอคอยทรัพยากรท่ีถือครองโดย Pn และ Pn กก็ าํ ลงั รอคอยทรัพยากรที่ถือครองโดย P0ตอ้ งมีเง่ือนไขท้งั 4 น้ีครบ จึงจะเกิดวงจรอบั ได้ เราจะเห็นวา่ เง่ือนไขท้งั 4 ไม่ไดเ้ ป็นอิสระต่อกนั อยา่ งแทจ้ ริง เช่น วงจรรอคอย จะเกิดจากการท่ีมีเงื่อนไข การถือครองแล้วรอคอย ในระบบ แต่เราจะเห็นไดใ้ นหวั ขอ้ ท่ี 7.4 วา่ การพิจารณาเงื่อนไขแต่ละขอ้ แยกกนั จะช่วยใหเ้ ขา้ ใจปัญหาไดด้ ีข้ึนมาก2. กราฟการจดั สรรทรัพยากร (Resource-Allocation Graph) เราสามารถอธิบายวงจรอบั ไดช้ ดั เจนมากข้ึน โดยใชก้ ราฟทางเดียว (Direct Graph) ที่เรียกวา่“กราฟการจดั สรรทรัพยากรของระบบ (system resource-allocation graph)” กราฟน้ีจะประกอบดว้ ยเซตของวงกลม (node) V และเซตของลูกศร (Edge) E โดยท่ีเซตของวงกลม V จะถูกแบ่งเป็น 2ประเภท คือ P = { P1, P2, … , Pn} เป็นเซตของโปรเซสท้งั หมดท่ีมีอยใู่ นระบบ และเซต R ={ R0, R1, … , Rn } เป็นเซตของทรัพยากรท่ีมีอยใู่ นระบบ ลูกศรจากโปรเซส Pi ไปยงั ทรัพยากรประเภท Rj ซ่ึงเขียนแทนไดโ้ ดย Pi Rj หมายความวา่ โปรเซส Pi ไดร้ ้องขอใชท้ รัพยากรประเภทRj และกาํ ลงั รอคอยอยู่ ส่วนลูกศรจากทรัพยากรประเภท Rj ไปยงั โปรเซส Pi เขียนแทนไดโ้ ดย Rj Pi หมายความวา่ โปรเซส Pi กาํ ลงั ใชท้ รัพยากร Rj อยู่ (ทรัพยากร Rj ถูกถือครอง โดยโปรเซส Pi)โดยท่ีลูกศรจาก Pi ไปยงั Rj (Pi Rj) น้นั เรียกวา่ “เสน้ ร้องขอ” (Request Edge) และลูกศรจาก Rjไปยงั Pi (Rj Pi) เรียกวา่ “เส้นถือครอง” (Assignment Edge)ในการเขียนกราฟ เราจะใชว้ งกลมแทนโปรเซส และใชส้ ่ีเหล่ียมแทนทรัพยากร และใชจ้ ุด แทนจาํ นวนทรัพยากรแต่ละตวั ซ่ึงจะอยู่ภายในส่ีเหลี่ยม โดยท่ีเส้นร้องขอจะตอ้ งช้ีไปยงั กรอบสี่เหลี่ยม (ทรัพยากร Rj) เท่าน้นั แต่เส้นถือครอง จะตอ้ งช้ีไปยงั จุดใดจุดหน่ึงในส่ีเหลี่ยม เมื่อโปรเซส Pi ร้องขอทรัพยากรประเภท Rj เราก็จะเขียน เส้นร้องขอลงในกราฟการจดั สรรทรัพยากร และเม่ือการร้องขอน้ันไดร้ ับอนุมตั ิจากระบบ เส้นร้องขอก็จะถูกแปลงไปเป็ นเส้นถือครองแทน และหลงั จากที่ โปรเซสปล่อยทรัพยากรคืนสู่ระบบแลว้ เส้นถือครองก็จะถูกลบออกไปจากกราฟเช่นกนั

124 ระบบปฏิบตั ิการ รูปท่ี 2.41 กราฟการจดั สรรทรัพยากรกราฟการจดั สรรทรัพยากรในรูปขา้ งตน้ แสดงสถานะของระบบ ดงั น้ีเซต P = { P1 , P2, P3}เซต R = { R1 , R2 , R3 , R4 }เซต E = { P1  R1, P2  R3 , R1  P2 , R2  P2 , R2  P1 , R3  P3 }  ทรัพยากรในระบบ ทรัพยากรประเภท R1 = 1 ตวั ทรัพยากรประเภท R2 = 2 ตวั ทรัพยากรประเภท R3 = 1 ตวั ทรัพยากรประเภท R4 = 3 ตวั  สถานะของโปรเซส โปรเซส P1 กาํ ลงั ถือครองทรัพยากรประเภท R2 และกาํ ลงั รอคอยที่จะใช้ ทรัพยากรประเภท R1 โปรเซส P2 กาํ ลงั ถือครองทรัพยากรประเภท R1 และ R2 และกาํ ลงั รอคอย ที่จะใชท้ รัพยากรประเภท R3 โปรเซส P3 กาํ ลงั ถือครองทรัพยากรประเภท R3 อยู่

โปรเซส125 จากนิยามของกราฟการจดั สรรทรัพยากร เราอาจพิสูจน์ไดโ้ ดยง่ายว่า “ถา้ ไม่มีวงจร (Cycle)ในกราฟแลว้ ระบบจะไม่อยู่ในสถานะเดตล็อกแต่ในทางตรงขา้ ม ถา้ มีวงจรปรากฏในกราฟแลว้แสดงว่าในระบบอาจมีวงจรอบั เกิดข้ึน” ถา้ เป็นระบบที่ทรัพยากรแต่ละประเภทมีเพยี ง 1 ตวั เม่ือมีวงจรในกราฟ ก็จะตอ้ งมีวงจรอบั ในระบบแน่นอน หรือถา้ ระบบมีทรัพยากรประเภทละหลายตวัและวงจรในกราฟ ลากผ่านเฉพาะทรัพยากรประเภทท่ีมีตวั เดียว ก็จะสรุปไดว้ ่า มีวงจรอบั เกิดข้ึนและทุก ๆ โปรเซสในวงจรของกราฟ ก็จะติดอยู่ในวงจรอบั ดว้ ย ซ่ึงในกรณีน้ีวงจรในกราฟเป็ นเง่ือนไขที่จาํ เป็น และ เพียงพอ ในการเกิดวงจรอบั ในระบบ แต่ถา้ ทรัพยากรแต่ละประเภทมีจาํ นวนมากกว่า 1 ตวั วงจรท่ีเกิดข้ึนในกราฟ ไม่อาจเป็ นตวั บอกไดเ้ สมอไปว่า เกิดวงจรอบั ในระบบ ในกรณีน้ีวงจรที่เกิดในระบบ เป็นเงื่อนไขท่ีจาํ เป็น ในการใชต้ รวจสอบเดตลอ็ กแต่ไม่เพียงพอท่ีจะใช้แสดงว่ามีวงจรอบั เกิดข้ึนจริง ๆ ในระบบ เพ่ือเป็นการแสดงภาพตามแนวคิดที่กล่าวมา เราจะกลบัไปสู่ กราฟการจดั สรรทรัพยากรในรูปก่อนหนา้ น้ี สมมติวา่ โปรเซส P3 ไดร้ ้องขอทรัพยากรประเภท R2 แต่เน่ืองจากไม่มีทรัพยากรตวั ใด ในประเภท R2 วา่ งเลย ดงั น้นั เส้นร้องขอ P3  R2 จึงถูกใส่เพ่ิม เขา้ ไปในกราฟ ซ่ึงแสดงในรูปถดั ไป รูปที่ 2.42 กราฟการจดั สรรทรัพยากรกบั วงจรอบัณ จุดน้ี จะเกิดวงจรอยา่ งนอ้ ย 2 วง ข้ึนในระบบ คือP1  R1 P2 R3 P3 R2 P1P2 R3 P3 R2 P2

126 ระบบปฏิบตั ิการ ทาํ ใหเ้ กิดวงจรอบั กบั โปรเซส P1 , P2 และ P3 โปรเซส P2 กาํ ลงั รอคอย ทรัพยากรประเภท R3ซ่ึงกาํ ลงั ถูกถือครองโดยโปรเซส P3 และโปรเซส P3 กก็ าํ ลงั ร้องขอทรัพยากรประเภท R2 ซ่ึงถูกถือครอง โดยโปรเซส P1 และ P2 หรืออาจกล่าวไดว้ า่ โปรเซส P3 กาํ ลงั รอคอยให้ P1 หรือ P2 คืนทรัพยากรประเภท R2 กลบั สู่ระบบ รูปที่ 2.43 กราฟการจดั สรรทรัพยากรกบั วงจรแต่ไม่ตดิ วงจรอบัเราลองมาพิจารณารูปภาพขา้ งตน้ จะเห็นวา่ มี วงจรP1 R1 P3 R2 P1แต่อยา่ งไรกต็ ามวงจรน้ีจะไม่ก่อใหเ้ กิดเดตลอ็ กโดยสงั เกตวา่ โปรเซส P4 จะปล่อยทรัพยากรประเภท R2 ที่ตนเองถือครองอยู่ เม่ือใชเ้ สร็จ ซ่ึงเมื่อทรัพยากร R2 ถูกปล่อยกลบั สู่ระบบแลว้ ระบบก็สามารถที่จะจดั ทรัพยากรประเภท R2 ใหแ้ ก่โปรเซส P3 ได้ วงจรกจ็ ะขาดทนั ที เราอาจกล่าวโดยสรุปไดว้ ่า ถา้ ไม่มีวงจรในกราฟการจดั สรรทรัพยากรแลว้ ระบบจะไม่อยใู่ นสถานะเดตลอ็ กแต่ในทางกลบั กนั ถา้ มีวงจรในกราฟแลว้ ระบบอาจจะเกิดเดตลอ็ กหรือไม่เกิดกไ็ ด้2.4.2 วธิ ีการจดั การกบั เดตลอ็ ก (Methods for Handing Deadlocks)การจดั การปัญหาวงจรอบั มีอยู่ 3 วธิ ีหลกั ๆ คือ 1. กาํ หนดกฎเกณฑบ์ างอยา่ งในการใชท้ รัพยากร เพ่อื ใหแ้ น่ใจวา่ ระบบจะไม่มีทางเกิดวงจร อบั ได้ 2. ไม่ตอ้ งป้องกนั ใด ๆ เลย ปล่อยใหร้ ะบบเกิดวงจรอบั ข้ึนก่อน แลว้ ค่อยตามแกไ้ ขทีหลงั 3. มองขา้ มปัญหาท้งั หมด แลว้ แสร้งทาํ วา่ วงจรอบั ไม่เคยเกิดข้ึนในระบบ วิธีการแกป้ ัญหาวธิ ี น้ีเป็นวธิ ีการหน่ึงที่ถูกใชใ้ นระบบปฏิบตั ิการส่วนใหญ่ รวมท้งั UNIX ดว้ ย <restart>

โปรเซส1272.4.3 การป้องกนั เดตลอ็ ก (Deadlock Prevention)ตามที่ไดก้ ลา่ วมาแลว้ วา่ จะตอ้ งเกิดเง่ือนไขท้งั 4 ขอ้ พร้อมกนั ในระบบจึงจะเกิดวงจรอบั ข้ึนได้ดงั น้นั เพียงเราป้องกนั เงื่อนไขขอ้ ใดขอ้ หน่ึง กจ็ ะสามารถป้องกนั การเกิดวงจรอบั ได้ ซ่ึงสามารถแยกพิจารณาทีละเง่ือนไขไดด้ งั น้ี2.4.3.1 ห้ามใช้ทรัพยากรร่วมกนั (Mutual Exclusion) เง่ือนไขในขอ้ น้ี คือ การที่ระบบ ไม่อนุญาตให้ มีการใชท้ รัพยากรร่วมกนั เช่น เคร่ืองพิมพจ์ ะไม่สามารถ ให้โปรเซสหลาย ๆ โปรเซส ใช้พร้อม ๆ กนั ได้ แต่ถา้ เรายอมให้ในระบบมีการใช้ทรัพยากรร่วมกนั ได้ ปัญหาวงจรอบั ก็จะไม่เกิด เช่น แฟ้มขอ้ มูลที่อ่านไดอ้ ย่างเดียว เป็ นตวั อย่างหน่ึงของทรัพยากรที่สามารถใชร้ ่วมกนั ได้ ถา้ มีโปรเซสหลาย ๆ โปรเซส ร้องขอท่ีจะเปิ ดแฟ้มขอ้ มูลน้ีพร้อม ๆ กนั โปรเซสเหล่าน้นั จะไดร้ ับอนุญาตให้ใชแ้ ฟ้มขอ้ มูลไดพ้ ร้อมกนั โปรเซสหน่ึง ๆ ไม่จาํ เป็ นท่ีจะตอ้ งรอให้โปรเซสอื่น คืนทรัพยากรท่ีตอ้ งการสู่ระบบ แต่สามารถใชท้ รัพยากรตวั น้ันร่วมกนั ไดเ้ ลย อยา่ งไรกต็ าม การท่ีเราจะป้องกนั การเกิดวงจรอบั ในระบบ โดยการป้องกนั เง่ือนไขน้ีไม่สามารถทาํ ไดเ้ สมอไป เพราะยงั มีทรัพยากรบางประเภท ท่ีไม่มีทางใชร้ ่วมกนั ได้2.4.3.2 การถือครองแล้วรอคอย (Hold and Wait)คือ การที่จะไม่ใหเ้ กิด “การถือครองแลว้ รอคอย” ข้ึนในระบบ โดยจะตอ้ งกาํ หนดวา่ เมื่อโปรเซสหน่ึงจะร้องขอทรัพยากร โปรเซสน้นั จะตอ้ งไม่ไดถ้ ือครองทรัพยากรใด ๆ อยใู่ นขณะน้นั ซ่ึงอาจทาํได้ 2 วธิ ีการ คือ 1. ใหโ้ ปรเซสร้องขอทรัพยากรท่ีตอ้ งการใชท้ ้งั หมด (ตลอดการทาํ งาน) ก่อนที่จะเร่ิมตน้ ทาํ งาน เราอาจดาํ เนินการตามวิธีน้ีได้ โดยการกาํ หนดให้ การร้องขอทรัพยากรเป็นคาํ สงั่ เรียกระบบ (system call) ท่ีตอ้ งทาํ ก่อนการทาํ งานใด ๆ ของโปรเซสเสมอ 2. ยอมใหโ้ ปรเซสร้องขอทรัพยากรได้ กต็ ่อเม่ือโปรเซสน้นั มิไดถ้ ือครองทรัพยากรใดไวเ้ ลย ตวั อยา่ งเช่น โปรเซสหน่ึง อาจร้องขอทรัพยากรบางส่วน และใชท้ รัพยากรน้นั ไปก่อน และ เมื่อโปรเซสน้นั ตอ้ งการทรัพยากรเพิ่มอีก โปรเซสน้นั กจ็ ะตอ้ งคนื ทรัพยากรที่ถือครองอยู่ กลบั สู่ระบบเสียก่อน จึงจะร้องขอใหม่ได้เราจะเห็นความแตกต่างของ 2 วธิ ีน้ี โดยการพิจารณาจากตวั อยา่ ง โปรเซสหน่ึงตอ้ งการ1. คดั ลอกขอ้ มูลจากเทปลงไปเกบ็ ที่แฟ้มขอ้ มูลในดิสก์2. เรียงลาํ ดบั ขอ้ มูลของแฟ้มขอ้ มูลในดิสก์

128 ระบบปฏิบตั ิการ3. พมิ พผ์ ลลพั ธ์ออกสู่เครื่องพิมพ์ถา้ ทรัพยากรท้งั หมดตอ้ งถูกร้องขอในตอนเร่ิมตน้ งานของโปรเซส (นน่ั คือใชว้ ธิ ีแรก) แสดงวา่โปรเซสน้ี กจ็ ะถือครองเคร่ืองพมิ พ์ ไวต้ ลอดเวลาท่ีโปรเซสทาํ งานอยู่ ถึงแมว้ า่ โปรเซสน้ี จะใช้เคร่ืองพิมพเ์ ฉพาะในตอนทา้ ยของการทาํ งานเท่าน้นั สาํ หรับวิธีที่ 2 ใหโ้ ปรเซสร้องขอทรัพยากรในตอนเร่ิมตน้ แค่เคร่ืองขบั เทป และแฟ้มขอ้ มูลในดิสก์ โดยเม่ือไดร้ ับทรัพยากรแลว้ โปรเซสจะคดั ลอกขอ้ มูล จากเทปลงไปสู่ดิสกจ์ ากน้นั กจ็ ะคืนท้งั เครื่องขบั เทป และแฟ้มขอ้ มูลในดิสกก์ ลบั สู่ระบบ จากน้นั โปรเซสกจ็ ะตอ้ งร้องขอแฟ้มขอ้ มูลในดิสกแ์ ละเคร่ืองพิมพใ์ หม่อีกคร้ังหน่ึง เม่ือพมิ พเ์ สร็จเรียบร้อยแลว้ โปรเซสกจ็ ะคืนทรัพยากรกลบั สู่ระบบ เป็นอนั สิ้นสุดการทาํ งานของโปรเซส วิธีการแรก มีขอ้ เสียคือ การใชท้ รัพยากรจะมีประสิทธิผลต่าํ มาก เพราะโปรเซสจาํ เป็ นตอ้ งร้องขอและถือครองทรัพยากรไวท้ ้งั หมด ตลอดช่วงเวลาการทาํ งาน ท้งั ๆ ท่ีการใชท้ รัพยากรแต่ละตวั อาจเป็นเพียงช่วงเวลาน้นั ๆ กต็ าม นอกจากน้นั อาจมี ปัญหาการแช่เยน็ (starvation) อีกดว้ ย โดยถา้ มีบางโปรเซสตอ้ งการใชท้ รัพยากร (ที่เป็นที่นิยมใชก้ นั มาก) หลาย ๆ ตวั อาจตอ้ งรอคอย อยา่ งไม่มีท่ีสิ้นสุด เพราะทรัพยากรตวั หน่ึง ในจาํ นวนที่ตอ้ งการอาจมีโปรเซสอ่ืนใชอ้ ยู่ ส่วนวิธีการหลงั ก็มีขอ้ เสียคือ ตอ้ งคืนทรัพยากรท่ีถือครองอยู่ เพื่อท่ีจะร้องขอกลบั มาใหม่อีก ร่วมกบั ทรัพยากรตวั ใหม่ทาํ ใหเ้ สียเวลาโดยเปล่าประโยชน์2.4.3.3 ห้ามแทรกกลางคนั (No Preemption)เราอาจกาํ หนดกฎเกณฑด์ งั น้ีถา้ โปรเซสหน่ึง (ที่กาํ ลงั ถือครองทรัพยากรบางส่วนอยู่) ร้องขอทรัพยากรเพิ่ม และระบบยงั ไม่สามารถจดั ให้ได้ในทันที (แสดงว่าโปรเซสที่ร้องขอจะต้องรอ) เราจะให้ทรัพยากรท้ังหมด ท่ีโปรเซสน้ีถือครองอยู่ ถูกแทรกกลางคนั น่ันคือ ทรัพยากรท่ีโปรเซสน้ีถือครองอยู่ท้งั หมดจะถูกปล่อยคืนสู่ระบบโดยปริยาย โปรเซสท่ีถูกแทรกกลางคนั น้ีจะตอ้ งรอคอยทรัพยากร ท้งั ที่ร้องขอไว้ต้งั แต่แรก และที่ถูกแทรกกลางคนั ไป ก่อนที่จะสามารถทาํ งานต่อไปได้ หรืออาจจะกล่าวไดว้ ่า ถา้ มีโปรเซสหน่ึง ไดร้ ้องขอทรัพยากรบางส่วนจากระบบ ในตอนแรก ระบบจะตรวจสอบว่า ทรัพยากรท่ีร้องขอน้ัน ว่างอยู่หรือไม่ ถา้ ว่างอยู่ระบบก็จะจดั สรรทรัพยากรเหล่าน้ัน ให้แก่โปรเซสแต่ถา้ทรัพยากรที่ถูกร้องขอน้นั ไม่วา่ ง ระบบจะตรวจดูก่อนวา่ ทรัพยากรน้นั ไม่วา่ งเน่ืองจากอะไรถา้ ไม่ว่างเน่ืองจากกาํ ลงั ถูกถือครองโดยโปรเซสอ่ืน ซ่ึงกาํ ลงั รอคอยทรัพยากรเพิ่มอยู่ ระบบจะทาํการแทรกกลางคนั ทรัพยากรท้งั หมดของโปรเซสน้นั และจดั สรรทรัพยากรท่ีไดม้ าแก่โปรเซสที่ร้องขอ แต่ถา้ ทรัพยากรท่ีไม่วา่ งน้นั ไม่ไดถ้ ูกถือครองโดยโปรเซสอ่ืนท่ีกาํ ลงั รออยู่ ระบบกจ็ ะใหโ้ ปรเซส

โปรเซส129ท่ีร้องขอทรัพยากร รอ และขณะที่รออยนู่ ้นั ทรัพยากรท้งั หมดท่ีโปรเซสน้ี ถือครองอยอู่ าจถูกแทรกกลางคนั ได้ เมื่อมีโปรเซสอ่ืนร้องขอ และโปรเซสน้ี จะสามารถกลบั ไปทาํ งานต่อได้ เม่ือได้รับจดั สรรทรัพยากรที่ร้องขอและไดร้ ับทรัพยากรท่ีอาจถูกแทรกกลางคนั ไปคืนท้ังหมดเสียก่อนวิธีการน้ีมกั ใชก้ บั ทรัพยากรที่สามารถเก็บค่าสถานะและติดต้งั ค่ากลบั คืนมาไดง้ ่าย เช่น ค่าในรีจีสเตอร์ (ของหน่วยประมวลผลกลาง) เน้ือที่ในหน่วยความจาํ หลกั เป็ นตน้ แต่จะไม่สามารถใชก้ บัทรัพยากรทวั่ ๆ ไป เช่น เคร่ืองพิมพ์ และ หน่วยขบั เทป เป็นตน้2.4.3.4 วงจรรอคอย (Circular Wait) เราอาจป้องกนั การเกิดเดตลอ็ กโดยการป้องกนั ไม่ใหเ้ กิดเง่ือนไขวงจรรอคอย ซ่ึงสามารถทาํไดโ้ ดย การกาํ หนดลาํ ดบั ของทรัพยากรท้งั หมดในระบบ และกาํ หนดให้ โปรเซสตอ้ งร้องขอใช้ทรัพยากร เรียงตามเลขลาํ ดบั น้ีกาํ หนดให้ R = { R1 , R2, … , Rm } โดย R เป็นเซตของทรัพยากรในระบบ และ กาํ หนดให้ทรัพยากรแต่ละประเภทมี ค่าเลขลาํ ดบั เป็น เลขจาํ นวนเตม็ ท่ีไม่ซ้าํ กนั เขียนแทนดว้ ย F(Ri) เพอื่ ให้เราสามารถเปรียบเทียบทรัพยากร 2 ประเภทไดว้ า่ ตวั ใดมีลาํ ดบั ก่อน-หลงั ตวั อยา่ งเช่น ถา้ เซตของทรัพยากร R ประกอบดว้ ย เคร่ืองขบั เทป เคร่ืองขบั จานบนั ทึก และ เคร่ืองพมิ พ์ ดงั น้นั ค่าเลขลาํ ดบัF(Rj) อาจจะถูกกาํ หนดได้ ดงั น้ีคอื F(เครื่องขบั เทป) = 1 F(เครื่องขบั ดิสก)์ = 5 F(เครื่องพมิ พ)์ = 12และกาํ หนดวธิ ีการในการร้องขอทรัพยากรในระบบดงั น้ีโปรเซสแต่ละตวั สามารถร้องขอทรัพยากรได้ ในลาํ ดบั ที่เพม่ิ ข้ึนเท่าน้นั คือ เริ่มตน้ โปรเซสอาจร้องขอทรัพยากรใด ๆ กไ็ ด้ เช่น ทรัพยากร Ri แต่ต่อจากน้ีโปรเซสจะร้องขอทรัพยากร Rj ไดก้ ต็ ่อเมื่อF(Rj) > F(Ri) ถา้ เป็นการร้องขอทรัพยากร ประเภทเดียวกนั หลาย ๆ ตวั โปรเซสจะตอ้ งร้องขอทรัพยากรทีละตวั จากตวั อยา่ ง เลขลาํ ดบั ทรัพยากรขา้ งตน้ ถา้ โปรเซสหน่ึงตอ้ งการใชเ้ ครื่องขบั เทป(F(R) = 1) และ เคร่ืองพมิ พ์ ( F (R) = 12) โปรเซสน้นั จะตอ้ งร้องขอเครื่องขบั เทปก่อน แลว้ จึงร้องขอเคร่ืองพิมพ์ จะร้องขอกลบั กนั ไม่ได้ (ระบบไม่อนุมตั ิ) ในทางตรงกนั ขา้ ม ถา้ โปรเซสตอ้ งการร้องขอทรัพยากรประเภท Rj โปรเซสจะตอ้ งปลอ่ ยทรัพยากร Ri ซ่ึง F(Ri) F(Rj) คืนสู่ระบบทุกตวัเสียก่อน เช่นถือครอง R5 อยอู่ ยากได้ R1 ตอ้ งคืน R5 ก่อน R5 R1ตามขอ้ กาํ หนดที่กล่าวมา จะเห็นว่า เงื่อนไขวงจรรอคอย จะไม่สามารถเกิดข้ึนได้ เราสามารถพิสูจน์โดยวิธียกสิ่งตรงขา้ มได้ (Proof by Contradiction) ดงั น้ี สมมติใหเ้ กิดวงจรรอคอยในระบบ คือ { P1,P2, … , Pn} โดยท่ีโปรเซส P1 รอคอยทรัพยากร R1 ซ่ึงกาํ ลงั ถูกถือครองโดยโปรเซส Pi+1 ตามลาํ ดบั

130 ระบบปฏิบตั ิการเป็ นวงจร เน่ืองจากโปรเซส Pi+1 ถือครองทรัพยากร R1 อยู่ ขณะท่ีร้องขอทรัพยากร Ri+1 เราจะไดว้ ่าF(Rj) < F(Ri+1) สาํ หรับทุก ๆ ค่าของ i (โดยขอ้ กาํ หนดท่ีต้งั ไว)้ ซ่ึงหมายความว่า F(R0) < F(R1) < …< F(Rn) < F(R0) ดงั น้นั F(R0) < F(R0) เอง ซ่ึงเป็นไปไม่ได้ สรุปวา่ ไม่มีวงจรรอคอยในระบบ พึงสงั เกตวา่ การกาํ หนดค่าเลขลาํ ดบั ของทรัพยากร ควรเรียงตามลาํ ดบั การใชง้ านตามปกติในระบบ เช่น ปกติเรามกั ใชเ้ คร่ืองขบั เทป ก่อนเคร่ืองพิมพเ์ สมอ จึงควรกาํ หนดลาํ ดบั ให้ F(เครื่องขบั เทป) < F(เครื่องพิมพ)์2.4.4 การหลกี เลย่ี งเดตลอ็ ก(Deadlock Avoidance) ในหัวขอ้ ที่ 2.4.3 น้นั เป็ นการป้องกนั เดตล็อกไม่ให้เกิดข้ึน โดยการสร้างขอ้ กาํ หนดในการร้องขอทรัพยากร เพอื่ ใหแ้ น่ใจวา่ เงื่อนไขเพียงขอ้ ใดขอ้ หน่ึง (ที่เป็นส่ิงจาํ เป็นในการเกิดวงจรอบั ) จะไม่เกิดข้ึนอยา่ งแน่นอน การใชข้ อ้ กาํ หนดเหล่าน้ี อาจมีผลกระทบขา้ งเคียงต่อระบบ คือ การใชง้ านอุปกรณ์(ทรัพยากร) ในระบบ อาจมีประสิทธิภาพต่าํ ลงซ่ึงจะเป็นการลด อตั รางานเสร็จต่อหน่วยเวลา (throughput) ของระบบอีกดว้ ย ทางเลือกอีกทางหน่ึงที่จะใชห้ ลีกเลี่ยงในเดตลอ็ กกค็ ือ เราตอ้ งมีขอ้ มูลเก่ียวกบั การร้องขอทรัพยากรในระบบโดยรวม ตวั อยา่ งเช่น ในระบบ มีเครื่องขบั เทป 1 เคร่ือง และเคร่ืองพมิ พ์ 1 เคร่ืองเราอาจทราบวา่ (มีขอ้ มูลวา่ ) “โปรเซส P จะร้องขอเคร่ืองขบั เทป เป็นอนั ดบั แรก และร้องขอเคร่ืองพิมพเ์ ป็นอนั ดบั ต่อไป แลว้ กจ็ ะปล่อยทรัพยากรท้งั 2 ตวั น้ี กลบั คืนสู่ระบบ” และ “โปรเซส Qจะร้องขอเครื่องพมิ พ์ เป็นอนั ดบั แรก แลว้ จึงร้องขอเครื่องขบั เทป” จากขอ้ มูลเหล่าน้ี ทาํ ใหร้ ะบบทราบลาํ ดบั ในการร้องขอทรัพยากรของแต่ละโปรเซส ซ่ึงจะช่วยใหร้ ะบบสามารถตดั สินใจไดว้ า่การร้องขอในแต่ละคร้ังน้นั จะใหโ้ ปรเซสรอหรือไม่ เพอ่ื เป็นการหลีกเล่ียงปัญหาวงจรอบั ท่ีอาจจะเกิดข้ึนได้ มีข้นั ตอนวิธีต่าง ๆ มากมาย ซ่ึงแตกต่างกนั ในดา้ นจาํ นวนและประเภทของขอ้ มูลท่ีตอ้ งการแต่มีวิธีหน่ึงที่ง่ายและเป็ นประโยชน์มาก โดยวิธีน้ีต้องการให้แต่ละโปรเซสประกาศจาํ นยนทรัพยากรสูงสุดในแต่ละประเภทท่ีโปรเซสน้นั ตอ้ งการ จากขอ้ มูลน้ีเราสามารถสร้างข้นั ตอนวิธี ท่ีจะรับประกนั ได้ว่าระบบจะไม่มีทางเขา้ สู่สถานะวงจรอบั ไดเ้ ลย ซ่ึงข้นั ตอนวิธีดงั กล่าวจดั เป็ นวิธีการหลีกเลี่ยงเดตล็อก(Deadlock Avoidance) แบบหน่ึง ข้นั ตอนวิธีน้ีจะคอยตรวจดู สถานะของการจดั สรรทรัพยากร (Resource-Allocation State) ของระบบอยู่เสมอ ว่าจะไม่มีทางเกิดเง่ือนไขวงจรรอคอยข้ึนในระบบได้ โดยที่สถานะของการจัดสรรทรัพยากรน้ีประกอบด้วยจาํ นวนทรัพยากรท้งั หมดในระบบ จาํ นวนทรัพยากรที่จะถูกจดั สรรใหก้ บั โปรเซส และความตอ้ งการสูงสุดของแต่ละโปรเซส ระบบจะอยใู่ นสถานะปลอดภยั (Safe state) ถา้ มีทางเลือกอยา่ งนอ้ ย 1 ทาง ท่ีจะจดั สรรทรัพยากร (จนถึงจาํ นวนสูงสุด) ให้แต่ละโปรเซส จนทาํ งานเสร็จท้งั หมด โดยไม่เกิดวงจรอบั

โปรเซส1312.4.4.1 สถานะปลอดภัย (Safe State) ระบบจะอยใู่ นสถานะปลอดภยั (Safe State) กต็ ่อเมื่อมีลาํ ดบั การจดั สรรทรัพยากรอยา่ งปลอดภยั แก่โปรเซส (Safe Sequence) โดยเราจะถือวา่ ลาํ ดบั ของโปรเซส <P1, P2 , … , Pn> เป็นลาํ ดบั ท่ีปลอดภยั สาํ หรับสถานะของการจดั สรรทรัพยากรปัจจุบนั ถา้ แต่ละโปรเซส Pi สามารถไดร้ ับทรัพยากรที่อาจร้องขอ(ตอ้ งการ) จากทรัพยากรท่ียงั วา่ งอยใู่ นระบบรวมกบั ของท่ี Pj ถือครองอยู่ (j < i) นน่ั คือ ถา้ โปรเซส Pi ตอ้ งการทรัพยากรที่ไม่อาจไดร้ ับในทนั ที เน่ืองจากมีโปรเซส Pj ถือครองอยู่ จะทาํ ให้ Pi ตอ้ งรอจนกระทงั่ Pj ใชง้ านเสร็จ ซ่ึงเม่ือ Pj ใชง้ านเสร็จแลว้ Pi กส็ ามารถไดร้ ับทรัพยากรท้งั หมดท่ีตอ้ งการ เพ่ือที่จะใชท้ าํ งานจนเสร็จสมบูรณ์ได้ และ Pi จะปลอ่ ยทรัพยากรท่ีใช้เสร็จแลว้ ท้งั หมดกลบั คืนสู่ระบบเม่ือสิ้นสุดการทาํ งาน เม่ือ Pi ทาํ งานเสร็จแลว้ โปรเซส Pi+1สามารถไดร้ ับทรัพยากรท้งั หมดท่ีตอ้ งการ และจะเป็นไปในทาํ นองเดียวกนั กบั โปรเซสอ่ืน ๆ แต่ถา้ไม่สามารถหาลาํ ดบั โปรเซสท่ีปลอดภยั ในระบบได้ แสดงวา่ ระบบอยใู่ นสถานะไม่ปลอดภยั(unsafe state)สถานะปลอดภยั เป็นสถานะท่ีไม่มีเดตลอ็ กและในทางกลบั กนั สถานะไม่ปลอดภยั เป็นสถานะท่ีอาจเกิดวงจรอบั ได้ แต่กไ็ ม่ไดห้ มายความวา่ สถานะไม่ปลอดภยั ท้งั หมดจะก่อใหเ้ กิดวงจรอบั เสมอไปดงั รูปท่ี 2.44 รูปท่ี 2.44 แสดงสถานะทปี่ ลอดถยั และไม่ปลอดภัย

132 ระบบปฏิบตั ิการตราบใดที่ระบบอยใู่ นสถานะปลอดภยั ระบบจะสามารถหลีกเลี่ยงการเขา้ สู่สถานะไม่ปลอดภยั ได้(ซ่ึงหมายถึง การหลีกเล่ียงวงจรอบั ไดด้ ว้ ย) แต่ถา้ ระบบอยใู่ นสถานะไม่ปลอดภยั แลว้ ระบบจะไม่อาจป้องกนั โปรเซสร้องขอทรัพยากรจนทาํ ใหเ้ กิดวงจรอบั ได้ ตวั อยา่ งเช่น ระบบหน่ึงมีเครื่องขบั เทป 12 เครื่อง และมีโปรเซส 3 โปรเซสอยใู่ นระบบ คือP0 , P1 และ P2 โดยโปรเซส P0 , P1 และ P2 ตอ้ งการใชเ้ คร่ืองขบั เทปสูงสุด 10 , 4 และ 9 เครื่องตามลาํ ดบั ถา้ ณ เวลา T0 โปรเซส P0 , P1 และ P2 ไดร้ ับเครื่องขบั เทป โปรเซสละ 5 , 2 และ 2 เครื่องตามลาํ ดบั (แสดงวา่ ณ เวลาน้นั มีเคร่ืองขบั เทปวา่ อยู่ 3 เครื่อง)โปรเซส ความตอ้ งการสูงสุด ความตอ้ งการปัจจุบนั(Process) (Maximum Needs) (Current Needs) 5 P0 10 2 P1 4 2 P2 9 ณ เวลา T0 ลาํ ดบั โปรเซส <P1, P0 , P2> แสดงวา่ ระบบอยใู่ นสถานะปลอดภยั จะเห็นไดว้ า่ระบบสามารถจดั สรรทรัพยากรใหโ้ ปรเซส P1 ไดท้ นั ที ซ่ึงทาํ ให้ P1 ทาํ งานเสร็จและคืนทรัพยากรท้งั หมดแก่ระบบ (ขณะน้ีระบบจึงมีเคร่ืองขบั เทปวา่ รวม 5 เครื่อง) ดงั น้นั เมื่อโปรเซส P0 ตอ้ งการเคร่ืองขบั เทปเพมิ่ อีก 5 เคร่ืองกส็ ามารถทาํ ได้ โปรเซส P0 จึงสามารถทาํ งานเสร็จได้ และคืนเครื่องขบั เทปท้งั หมด สู่ระบบเม่ือใชเ้ สร็จ (จะทาํ ใหร้ ะบบมีเครื่องขบั เทปวา่ ง 10 เครื่อง) ดงั น้นั โปรเซสP2 ซ่ึงตอ้ งการเครื่องขบั เทปอีก 7 เครื่อง จะสามารถทาํ งานจนเสร็จสมบูรณ์ได้ เช่นกนั และในท่ีสุดเม่ือโปรเซส P2 ทาํ งานเสร็จ กจ็ ะคืน เครื่องขบั เทปท้งั หมดสู่ระบบ (ณ จุดน้ีระบบจะมีเคร่ืองขบั เทปวา่ ง 12 เคร่ือง) บางคร้ังระบบอาจจะเปล่ียนจะสถานะปลอดภยั ไปเป็นสถานะไม่ปลอดภยั ได้ เช่น สมมติวา่ณ เวลา T1 โปรเซส P2 ร้องขอเคร่ืองขบั เทปเพมิ่ อีก 1 เครื่อง และไดร้ ับการจดั สรรจะทาํ ใหส้ ถานะของระบบกลายเป็นสถานะไม่ปลอดภยั ทนั ที เนื่องจาก ณ จุดน้ี จะมีโปรเซส P1 เพยี งโปรเซสเดียวท่ีสามารถไดร้ ับทรัพยากรท้งั หมดที่ตอ้ งการ (4 เคร่ือง) โดยการร้องขอเคร่ืองขบั เทปท่ีวา่ งอยู่ ขณะน้ี 2เคร่ือง และเมื่อใชง้ านเสร็จกจ็ ะคืนเคร่ืองขบั เทปกลบั สู่ระบบทาํ ใหร้ ะบบ มีเครื่องขบั เทปวา่ งอยู่ 4เครื่อง ซ่ึงไม่เพยี งพอสาํ หรับท้งั โปรเซส P0 และ P2 (P0 อาจร้องขอไดอ้ ีก 3 เคร่ือง ส่วน P2 อาจร้องขอไดอ้ ีก 7 เคร่ือง) ทาํ ใหเ้ ราไม่สามารถหาลาํ ดบั ของโปรเซสที่ปลอดภยั ได้ แมแ้ ต่เพียงทางเดียว ความผดิ พลาดน้ี เกิดจากการท่ีเราจดั สรรเคร่ืองขบั เทปให้ P2 เพม่ิ อีก 1 เครื่อง ถา้ เราปล่อยให้โปรเซส P2 รอจนกระทงั่ โปรเซส P0 หรือ P1 ทาํ งานเสร็จ และคืนเคร่ืองขบั เทปกลบั สู่ระบบ จากน้นัค่อยจดั สรรใหโ้ ปรเซส P2 ตามท่ีขอ เราจะสามารถหลีกเลี่ยงสถานะไม่ปลอดภยั ไดโ้ ดยใชแ้ นวคิด

โปรเซส133ของสถานะปลอดภยั น้ี เราสามารถสร้างข้นั ตอนวิธีการหลีกเล่ียงวงจรอบั ซ่ึงจะประกนั ไดว้ า่ จะไม่เกิดวงจรอบั ข้ึนในระบบ โดยเม่ือใดกต็ ามที่โปรเซสร้องขอทรัพยากรเพม่ิ และทรัพยากรยงั มีวา่ งพอระบบตอ้ งตดั สินใจวา่ จะใหท้ รัพยากรตามที่ร้องขอทนั ทีหรือไม่ให้ (ใหโ้ ปรเซสรอไปก่อน) โดยพจิ ารณาจากวา่ ถา้ จดั สรรใหต้ ามที่ร้องขอแลว้ ระบบจะยงั คงอยใู่ นสถานะปลอดภยั หรือไม่ จะเห็นไดว้ า่ ข้นั ตอนวิธีน้ีอาจทาํ ใหก้ ารใชท้ รัพยากรของระบบมีประสิทธิผลต่าํ กวา่ ท่ีควรจะเป็น เนื่องจากโปรเซสยงั คงตอ้ งรอ ถึงแมว้ า่ จะมีทรัพยากรวา่ งอยกู่ ต็ าม2.4.4.2 อลั กอริทมึ ของกราฟการจดั สรรทรัพยากร (Resource-Allocation Graph Algorithm)ข้นั ตอนวธิ ีน้ีจะใชก้ ราฟการจดั สรรทรัพยากรในหวั ขอ้ 2.4.4.1 ในการพิจารณาการร้องขอจากโปรเซส โดยข้นั ตอนวธิ ีน้ีจะเพ่มิ เส้นความตอ้ งการ (Claim Edge) ข้ึนมาในกราฟการจดั สรรทรัพยากร (แต่เดิมมี 2 เสน้ คือ เสน้ ร้องขอ และ เส้นถือครอง) โดยเสน้ ความตอ้ งการท่ีลากจาก Piไปยงั Rj (Pi Rj) หมายถึง ในอนาคตโปรเซส Pi อาจจะร้องขอทรัพยากรประเภท Rj จะเห็นวา่เสน้ ความตอ้ งการมีทิศทางเดียวกนั กบั เส้นร้องขอ (จาก Pi ไป Rj) แต่จะต่างกนั ตรงท่ีเส้นความตอ้ งการในกราฟการจดั สรรทรัพยากร จะแสดงดว้ ยเส้นประ แต่เส้นร้องขอแสดงดว้ ยเส้นทึบ และเม่ือโปรเซส Pi ร้องขอทรัพยากรประเภท Rj ระบบจะเปล่ียนเส้นความตอ้ งการ Pi Rj (เส้นประ)ไปเป็น (เสน้ ทึบ) และในทาํ นองเดียวกนั เมื่อโปรเซส Pi คืนทรัพยากรกลบั สู่ระบบ เส้นถือครอง RjPi กจ็ ะถูกเปล่ียนไปเป็นเสน้ ความตอ้ งการ Pi Rj สมมติว่าโปรเซส Pi ไดร้ ้องขอทรัพยากรประเภท Rj ระบบจะอนุมตั ิการร้องขอน้ี ถา้ การเปลี่ยนเส้นร้องขอ (Pi Rj) ไปเป็นเส้นถือครอง (Rj Pi) ไม่ทาํ ใหเ้ กิดวงจรข้ึน แต่ถา้ พบวา่ เสน้ถือครองที่เกิดใหม่ทาํ ใหเ้ กิดวงจร โปรเซสน้นั จะตอ้ งรอจนกวา่ ในระบบจะมีทรัพยากรวา่ งมากข้ึนและเส้นถือครองของโปรเซสที่ร้องขอจะไม่ก่อใหเ้ กิดวงจรในกราฟการจดั สรรทรัพยากรจะสงั เกตเห็นวา่ เสน้ ความตอ้ งการทรัพยากรจะตอ้ งเกิดข้ึนก่อนในระบบ หมายความวา่ ก่อนที่โปรเซสPi จะเร่ิมตน้ ทาํ งาน เส้นความตอ้ งการท้งั หมดของ Pi จะตอ้ งมีอยใู่ นกราฟก่อนแลว้ เราอาจลดเส้นความตอ้ งการ Pi Rj ในกราฟลง โดยการหยอ่ นกฎของความตอ้ งการลง ใหม้ ีเส้นความตอ้ งการ PiRj ในกราฟ เฉพาะเมื่อเสน้ ลูกศรท้งั หมดของโปรเซส Pi เป็นเสน้ ความตอ้ งการทุกเสน้สมมติว่าโปรเซส Pi ร้องขอทรัพยากร Rj ระบบจะอนุมตั ิกต็ ่อเม่ือการแปลงเสน้ ร้องขอ Pi Rj ไปเป็นเส้นถือครอง Rj Pi แลว้ ไม่เกิดวงจรข้ึน ในกราฟการจดั สรรทรัพยากร เราสามารถตรวจดูสถานะปลอดภยั โดยใชข้ ้นั ตอนวธิ ีตรวจหาวงจรในกราฟ ซ่ึงข้นั ตอนวิธีน้ีคือ n2 เมื่อ n เป็นจาํ นวนโปรเซสในระบบถา้ ไม่มีวงจรในกราฟ การอนุมตั ิทรัพยากรจะทาํ ใหร้ ะบบอยใู่ นสถานะปลอดภยัถา้ เกิดมีวงจรในกราฟแลว้ การอนุมตั ิทรัพยากร จะทาํ ใหร้ ะบบอยใู่ นสถานะไม่ปลอดภยั เราจะแสดงข้นั ตอนวธิ ีดงั กลา่ วโดยพิจารณากราฟการจดั สรรทรัพยากร ดงั รูปที่ 2.45

134 ระบบปฏิบตั ิการ รูปที่ 2.45 กราฟการจดั สรรทรัพยากรสมมติว่า P2 ร้องขอ R2 ระบบจะไม่อนุมตั ิการร้องขอดงั กลา่ ว ถึงแมว้ า่ ทรัพยากร R2 จะวา่ งอยกู่ ต็ ามเพราะวา่ ถา้ ระบบอนุมตั ิ การร้องขอดงั กล่าวแลว้ เส้นถือครอง R2 P2 จะก่อใหเ้ กิดวงจรในกราฟการจดั สรรทรัพยากร ดงั รูปที่ 2.46 รูปที่ 2.46 แสดงการเกดิ วงจรในกราฟการจดั สรรทรัพยากรซ่ึงจะทาํ ใหร้ ะบบอยใู่ นสถานะไม่ปลอดภยั โดยอาจเกิดวงจรอบั ข้ึนในระบบ ถา้ โปรเซส P1 เกิดร้องขอทรัพยากรประเภท R2 และ P2 ร้องขอ R12.4.4.3 อลั กอริทมึ ของนายธนาคาร (Banker’s Algorithm)

โปรเซส135 ท่ีเรียกชื่อน้ีเพราะเป็นข้นั ตอนวิธีที่สามารถใชส้ าํ หรับการเบิกจ่ายเงินของธนาคาร เพอื่ป้องกนั ไม่ให้ ธนาคารจดั สรรเงินสดไปทางอ่ืน จนมีไม่เพียงพอท่ีจะแบ่งจ่ายใหก้ บั ลูกคา้ ทุกคนที่มาเบิกเม่ือมีโปรเซสใหม่เกิดข้ึนในระบบ โปรเซสน้นั จะตอ้ งประกาศจาํ นวนทรัพยากรสูงสุดที่ตอ้ งการในแต่ละประเภท โดยจาํ นวนท่ีตอ้ งการน้ีจะตอ้ งไม่เกินกวา่ จาํ นวนท่ีมีอยจู่ ริงในระบบ และเมื่อโปรเซสร้องขอทรัพยากร ระบบจะตอ้ งพิจารณาวา่ เม่ือจดั สรรทรัพยากรใหแ้ ต่ละโปรเซสแลว้จะทาํ ใหร้ ะบบอยใู่ นสถานะปลอดภยั หรือไม่ ถา้ อยรู่ ะบบกจ็ ะจดั สรรทรัพยากรใหต้ ามท่ีขอ แต่ถา้ ไม่โปรเซสที่ร้องขอกจ็ ะตอ้ งรอจนกวา่ โปรเซสอ่ืนไดค้ ืนทรัพยากรบางส่วนใหแ้ ก่ระบบจนเพยี งพอระบบตอ้ งเกบ็ โครงสร้างขอ้ มูลหลายตวั เพอื่ ใชใ้ นข้นั ตอนวธิ ีแบบนายธนาคาร โครงสร้างขอ้ มูลเหล่าน้ี เป็นตวั บอกสถานะของการจดั สรรทรัพยากรในระบบกาํ หนดให้ n เป็นจาํ นวนโปรเซสในระบบ และ m เป็นจาํ นวนของประเภททรัพยากรโครงสร้างขอ้ มูลที่จาํ เป็นมีดงั น้ี  Available : เป็นเวคเตอร์ขนาด m ซ่ึงใชเ้ กบ็ ค่าจาํ นวนทรัพยากรที่วา่ งของ ทรัพยากรแต่ละประเภท เช่น Available[j] = k หมายถึง ทรัพยากรประเภท Rj มี จาํ นวนทรัพยากรวา่ งอยู่ k ตวั  Max : เป็นเมทริกซ์ขนาด n x m ซ่ึงใชเ้ กบ็ ค่าจาํ นวนสูงสุดของทรัพยากรแต่ละ ประเภทที่โปรเซสแต่ละตวั ตอ้ งการใช้ เช่น Max[i,j] = k หมายถึง โปรเซส Pi ตอ้ งการทรัพยากรประเภท Rj มากท่ีสุด k ตวั  Allocation : เป็นเมทริกซข์ นาด n x m ซ่ึงใชเ้ กบ็ ค่าจาํ นวนทรัพยากรแต่ละประเภท ที่โปรเซสแตล่ ะตวั กาํ ลงั ถือครองอยู่ เช่น Allocation[i,j] = k หมายถึง โปรเซส Pi กาํ ลงั ถือครองทรัพยากรประเภท Rj อยู่ k ตวั  Need : เป็นเมทริกซ์ขนาด n x m ซ่ึงใชเ้ กบ็ ค่าจาํ นวนทรัพยากรแต่ละประเภทที่ โปรเซสแต่ละตวั อาจร้องขอเพมิ่ อีกได้ เช่น Need[i,j] = k หมายถึง โปรเซส Pi อาจ ร้องขอทรัพยากรประเภท Rj ไดอ้ ีก k ตวั จะเห็นวา่ Need [i,j] = Max[i,j] – Allocation[i,j]เราอาจเขียน Allocationi เป็นเวคเตอร์แสดงจาํ นวนทรัพยากรแต่ละประเภท ท่ีโปรเซส Pi ถือครองอยู่ และเขียน Needi เป็นเวคเตอร์แสดงจาํ นวนทรัพยากรแต่ละประเภทที่โปรเซส Pi อาจจะร้องขอเพม่ิ อีกได้1. ข้นั ตอนวธิ ีตรวจดูสถานะปลอดภัย (Safety Algorithm)ข้นั ตอนวิธีในการตรวจสอบวา่ ระบบจะอยใู่ นสถานะปลอดภยั หรือไม่ เป็นดงั น้ี 1. กาํ หนดให้ Work และ Finish เป็นเวคเตอร์ขนาด m และ n ตามลาํ ดบั และกาํ หนดค่าเร่ิมตน้ ดงั น้ี

136 ระบบปฏิบตั ิการ Work := Available; For i := 1 TO n DO Finish[i] := FALSE;2. ให้ i = 1 WHILE i  n DO BEGIN IF Finish[i] = FALSE AND Need[i]  Work THEN BEGIN Work := Work + Allocation[i]; Finish[i] := TRUE; i := i +1; END ELSE i := i+1; END;3. IF some Finish[i] = FALSE THEN “unsafe” ELSE “safe”อลั กอริทึมน้ีตอ้ งใชส้ ูตร m x n2 เพือ่ หาวา่ อยใู่ นสถานะปลอดภยั หรือไม่2. อลั กอริทมึ ร้องขอทรัพยากร (Resource-Request Algorithm)ให้ Requesti เป็นเวคเตอร์ แสดงคาํ ร้องขอของโปรเซส Pi โดยท่ี Requesti หมายถึง โปรเซส Pi ได้ร้องขอทรัพยากรประเภท Rj เป็นจาํ นวน k ตวั เม่ือโปรเซส Pi ร้องขอทรัพยากร ระบบจะจดั การดงั น้ี 1. ถา้ Requesti > Needi แลว้ ระบบจะแจง้ ขอ้ ผดิ พลาดวา่ “โปรเซสขอทรัพยากรมากกวา่ ท่ี ระบุ” แลว้ โปรเซสจะถกู ขบั ออกจากระบบ แต่ถา้ Requesti  Needi แลว้ จะไปทาํ งานใน ข้นั ตอนท่ี 2 2. ถา้ Requesti > Available แลว้ ให้ Pi รอจนกว่าทรัพยากรท่ีร้องขอจะวา่ ง จากน้นั จึงไป ทาํ งานในข้นั ตอนท่ี 3 แต่ถา้ Requesti  Available แลว้ จะไปทาํ งานในข้นั ตอนที่ 3 ทนั ที 3. ระบบจะสมมติวา่ ไดจ้ ดั สรรทรัพยากรใหต้ ามที่โปรเซส Pi ร้องขอมา โดยระบบจะมี สถานะเปล่ียนไป ดงั น้ี Available := Available – Requesti; Allocationi := Allocationi + Requesti;

โปรเซส137 Needi := Needi – Requesti;แลว้ ตรวจสอบดูวา่ สถานะของการจดั สรรทรัพยากรขณะน้ีเป็นสถานะปลอดภยั หรือไม่ ถา้ เป็นระบบกจ็ ะจดั สรรทรัพยากรใหต้ ามท่ีสมมติทนั ที แต่ถา้ ระบบอยใู่ นสถานะไม่ปลอดภยั แลว้ ระบบก็จะใหโ้ ปรเซส Pi รอ และ ถอยกลบั ไปอยใู่ นสถานะเดิม (ก่อน การสมมติค่า Available , Allocationiและ Needi เป็นค่าเดิม)3. ตวั อย่าง (An Illustrative Example)ระบบหน่ึงมีโปรเซสอยู่ 5 ตวั คือ P0 , P1 , P2 , P3 และ P4 มีทรัพยากรอยู่ 3 ประเภท คือ A , B และ Cโดยที่ในแต่ละประเภท มีจาํ นวนทรัพยากร 10 , 5 และ 7 ตวั ตามลาํ ดบั Allocation Max Available ABC ABC ABC P0 0 1 0 7 5 3 3 3 2 P1 2 0 0 3 2 2 P2 3 0 2 9 0 2 P3 2 1 1 2 2 2 P4 0 0 2 4 3 3 และเนื่องจาก เมทริกซ์ Need เกิดจาก Max – Allocation ดงั น้นั จะไดว้ า่ Need ABC P0 7 4 3 P1 1 2 2 P2 6 0 0 P3 0 1 1 และ เราพบวา่ ระบบอยใู่ นสถานะปลอดภยั เนื่องจากโปรเซสอาจทาํ งานไดต้ ามลาํ ดบั<P1, P3, P4 , P2 , P0> ซ่ึงเป็นไปตามเง่ือนไขของสถานะปลอดภยัสมมติว่า โปรเซส P1 ร้องขอทรัพยากรประเภท A และ C เพ่มิ อยา่ งละ 1 และ 2 ตวั ตามลาํ ดบั ดงั น้นัRequest1 = (1,0,2) ระบบจะตดั สินใจวา่ จะอนุมตั ิทรัพยากรให้ ตามที่ร้องขอหรือไม่ตามข้นั ตอนดงั น้ี

138 ระบบปฏิบตั ิการ 1. Request1  Need1 เนื่องจาก (1,0,2)  (1,2,2) 2. Request1  Available เน่ืองจาก (1,0,2)  (3,3,2)เม่ือผา่ น 2 ข้นั แรกแลว้ ระบบกจ็ ะสมมติวา่ ไดจ้ ดั สรรทรัพยากรใหต้ ามท่ีร้องขอ ทาํ ใหร้ ะบบมีสถานะใหม่ดงั Allocation Need Available ABC ABC ABC P0 0 1 0 743 230 P1 3 0 2 020 P2 3 0 2 600 P3 2 1 1 011 P4 0 0 2 431จากน้นั กจ็ ะตรวจสอบวา่ สถานะใหม่น้ีจะเป็นสถานะปลอดภยั หรือไม่ โดยใชข้ ้นั ตอนวิธีสถานะปลอดภยั (safety algorithm) ตรวจสอบ และเราจะพบวา่ โปรเซสอาจทาํ งานได้ ตามลาํ ดบั <P1, P3,P4, P0, P2> ซ่ึงเป็นไปตามเงื่อนไข ของสถานะปลอดภยั เมื่อเป็นเช่นน้ี ระบบจะสามารถอนุมตั ิการร้องขอของ P1 ได้ในบางกรณี ระบบอาจไม่อนุมตั ิการร้องขอของโปรเซส เช่น จากตวั อยา่ งเดิมขา้ งตน้ ถา้ P4 ร้องขอทรัพยากร (3,3,0) เพ่มิ ระบบไม่อาจอนุมตั ิใหไ้ ด้ เพราะมีทรัพยากรไม่พอ หรือถา้ P0 ร้องขอทรัพยากร (0,2,0) เพ่ิม ระบบกจ็ ะไม่อนุมตั ิ แมว้ า่ จะมีทรัพยากรพอ เพราะวา่ เมื่อระบบลองสมมติวา่ไดจ้ ดั สรรทรัพยากรใหต้ ามท่ีขอแลว้ พบวา่ สถานะใหม่เป็นสถานะไม่ปลอดภยั2.4.5 การตรวจหาเดตลอ็ ก(Deadlock Detection)ถา้ ในระบบปฏิบตั ิการไม่มีการป้องกนั หรือหลีกเล่ียงวงจรอบั แลว้ ในที่สุดระบบกอ็ าจจะตกอยใู่ นสถานะวงจรอบั ได้ ดงั น้นั ระบบจึงจาํ ตอ้ งมีวิธีอื่นทดแทนคือ  ข้นั ตอนวธิ ีท่ีจะตรวจหาวงจรอบั ในระบบวา่ เกิดข้ึนแลว้ หรือยงั  ข้นั ตอนวิธีในการแกไ้ ขเดตลอ็ ก2.4.5.1 ระบบทม่ี ที รัพยากรแต่ละประเภทเพยี งตวั เดยี ว (Single Instance of Each Resource Type) โดยนาํ กราฟการจดั สรรทรัพยากรมาแปลงสภาพเลก็ นอ้ ยเป็น กราฟการรอคอยทรัพยากร(Wait-for-Graph) การแปลงสภาพทาํ โดยเอาส่ีเหล่ียมท่ีแทนทรัพยากรออก และยบุ รวมลูกศรเขา้ดว้ ยกนั ดงั น้ี

โปรเซส139 ถา้ มีลูกศรจาก Pi ไป Pj ในกราฟการรอคอยทรัพยากร แสดงวา่ Pi กาํ ลงั รอทรัพยากรซ่ึง Pj ถือครองอยู่ หรืออาจกล่าวไดว้ า่ จะมีลูกศร Pi  Pj ในกราฟการรอคอยทรัพยากร ท่ีแปลงมา กต็ อ่ เม่ือมีลูกศร Pi  Rq และ Rq  Pj ในกราฟการจดั สรรทรัพยากรตน้ แบบตวั อยา่ งเช่น รูปท่ี 2.47 (a) เป็ นต้นแบบกราฟการจดั สรรทรัพยากร (b) แปลงเป็ นกราฟการรอคอยทรัพยากร ถา้ ในกราฟการรอคอยทรัพยากรมีวงจรแลว้ กจ็ ะเกิดเดตลอ็ กและในทางกลบั กนั ถา้ เกิดวงจรอบั แลว้ กจ็ ะมีวงจรในกราฟการรอคอยทรัพยากร ระบบตอ้ งเกบ็ ขอ้ มูลของกราฟการรอคอยทรัพยากรไว้ และใชข้ ้นั ตอนวิธีการตรวจหาวงจรในกราฟ เพอ่ื ตรวจหาวงจรอบั ในระบบ โดยคอยตรวจดูทุกๆ ช่วงเวลา2.4.5.2 ระบบทมี่ ที รัพยากรแต่ละประเภทหลายตัว (Several Instances of a Resource Type)

140 ระบบปฏิบตั ิการข้นั ตอนวธิ ีในการตรวจหาวงจรอบั น้ีคลา้ ยกบั Banker’s Algorithm ซ่ึงจาํ เป็นตอ้ งใชโ้ ครงสร้างขอ้ มูลดงั ต่อไปน้ี  Available : เป็นเวคเตอร์ขนาด m แสดงจาํ นวนทรัพยากรแต่ละชนิด ท่ียงั ว่างอยู่ (ไม่ไดถ้ ูกโปรเซสใดถือครองอย)ู่  Allocation : เป็นเมทริกซ์ n x m ใชเ้ กบ็ ค่าจาํ นวนทรัพยากรแต่ละชนิดท่ีโปรเซส แต่ละตวั ถือครองอยู่  Request : เป็นเมทริกซ์ n x m ใชเ้ กบ็ ค่าจาํ นวนทรัพยากรแต่ละชนิดที่โปรเซสแต่ ละตวั กาํ ลงั ร้องขอการกาํ หนดเคร่ืองหมายกเ็ หมือนในหวั ขอ้ ท่ี 10.3.3 ข้นั ตอนวธิ ีในการตรวจหาวงจรอบั น้ี เริ่มท่ีการหา ลาํ ดบั การอนุมตั ิทรัพยากรที่อาจเป็นไปได้ ในการทาํ ใหโ้ ปรเซสทาํ งานจนเสร็จ (ลองเปรียบเทียบวิธีน้ีกบั banker’s algorithm ดู) 1. Work := Available; 2. FOR i:= 1 TO n DO IF Allocation[i]  0 THEN Finish[i] := FALSE ELSE Finish[i] := TRUE; 3. i := 1; WHILE i  n DO BEGIN IF Finish[i] = FALSE AND Request[i]  Work THEN BEGIN Work := Work + Allocation[i]; Finish[i] := TRUE; i := i+1; END ELSE i := i+1; END; 4. FOR i=1 TO n DO IF Finish[i] = FALSE THEN process Pi is in a deadlocked. 5. IF Finish[i] = TRUE ท้งั หมด แสดงวา่ ขณะน้ีระบบไม่เกิดวงจรอบั .

โปรเซส141 คุณอาจสงสยั วา่ ทาํ ไมเราจึงคืนทรัพยากรท่ีโปรเซส Pi ถือครองอยใู่ หก้ บั ระบบ เมื่อเราทราบวา่ Request[i]  Work ท้งั น้ีเป็นเพราะวา่ เรารู้วา่ ขณะน้ี Pi ไม่ไดอ้ ยใู่ นเดตลอ็ ก(เพราะ Request[i] Work) ดงั น้นั เราจึงอาจสมมติวา่ Pi ยอ่ ม มีทางทาํ งานจนเสร็จ และเมื่อเสร็จกย็ อ่ มคืนทรัพยากรที่ถือครองอยสู่ ู่ระบบ ถา้ ไม่เป็นไปตามน้ีในอนาคตกอ็ าจเกิดวงจรอบั ได้ ซ่ึงเรากจ็ ะสามารถตรวจดูได้เม่ือเราดาํ เนินการตามข้นั ตอนวธิ ีตรวจหาเดตลอ็ กในคร้ังต่อไป ตวั อยา่ ง ใหร้ ะบบมี 5 โปรเซส P0 , P1 , P2 , P3 และ P4 และมีทรัพยากรชนิดA 7 ตวั , ชนิด B 2 ตวั , ชนิด C 6 ตวั ณ เวลา T0 ระบบอยใู่ นสถานะดงั น้ี Allocation Request Available ABC ABC ABC P0 0 1 0 0 0 0 0 0 0 P1 2 0 0 2 0 2 P2 3 0 3 0 0 0 P3 2 1 1 1 0 0 P4 0 0 2 0 0 2เราจะสรุปไดว้ า่ ขณะน้ีไม่มีวงจรอบั เกิดข้ึนหรือระบบไม่ไดอ้ ยใู่ นสถานะเดตลอ็ กโดยการดาํ เนินตามข้นั ตอนวิธีตรวจหาเดตลอ็ ก(Deadlock Detection) ดงั กล่าวขา้ งตน้เราจะพบวา่ มีลาํ ดบั การทาํ งานหน่ึง คือ <P0 , P2 , P3 , P1 , P4> ซ่ึงจะให้ Finish[i] = TRUE ท้งั หมดสมมติวา่ โปรเซส P2 ร้องขอทรัพยากรประเภท C เพมิ่ อีก 1 ตวั สถานะของระบบจะกลายเป็น Request ABC P0 0 0 0 P1 2 0 2 P2 0 0 1 P3 1 0 0 P4 0 0 2

142 ระบบปฏิบตั ิการเราจะพบวา่ ขณะน้ีมีวงจรอบั เกิดข้ึนในระบบ แมว้ า่ P0 อาจทาํ งานเสร็จ แลว้ คืนทรัพยากรชนิด B สู่ระบบ โปรเซสอื่น ๆ กไ็ ม่อาจทาํ งานต่อได้ เพราะทรัพยากรท่ีวา่ งอยู่ ไม่พอตามคาํ ร้องขอ ดงั น้นัระบบจึงตกอยใู่ นสถานะเดตลอ็ กโดยมีโปรเซส P1 , P2 , P3 และ P4 อยใู่ นวงจรอบั2.4.5.3 การใช้วธิ ีการตรวจหาเดตลอ็ ก(Detection-Algorithm Usage)เราจะใชว้ ิธีการตรวจหาเดตลอ็ กเม่ือใดบา้ ง ข้ึนอยกู่ บั 2 ปัจจยั คือ 1. ความถี่ของการเกิดวงจรอบั ในระบบ 2. จาํ นวนโปรเซสท่ีติดอยใู่ นวงจรอบัถา้ เกิดวงจรอบั ในระบบค่อนขา้ งบ่อย เรากต็ อ้ งใชข้ ้นั ตอนวิธีการตรวจหาวงจรอบั บ่อย ๆ ดว้ ย เพราะเมื่อเกิดเดตลอ็ กทรัพยากรและโปรเซสท่ีติดอยใู่ นวงจรอบั จะสูญเปล่าท้งั หมด จนกวา่ เราจะสามารถแกว้ งจรอบั ได้ นอกจากน้ีถา้ ปลอ่ ยไวน้ านวงจรอบั อาจขยายตวั ใหญ่ข้ึนเร่ือย ๆ ได้ เราอาจประมาณการวา่ วงจรอบั จะเกิดข้ึนเม่ือมีเหตุการณ์ท่ีบางโปรเซสร้องขอทรัพยากรแลว้ ระบบไม่สามารถอนุมตั ิใหไ้ ดท้ นั ที เราจึงอาจตรวจหาวงจรอบั โดยตรวจทุกคร้ังที่เหตุการณ์น้ีเกิดข้ึน ซ่ึงนอกจากเราจะตรวจพบไดร้ วดเร็วทนั เหตุการณ์แลว้ ยงั ทาํ ใหส้ ามารถระบุชดั ดว้ ยว่า โปรเซสใดทาํ ใหเ้ กิดวงจรอบั น้ีดว้ ย (ความเป็นจริงแลว้ วงจรอบั เป็นวงจรของโปรเซสซ่ึงผกู ติดกนั เป็นวงกลม ทุก ๆ โปรเซสที่ติดอยยู่ อ่ มเป็นสาเหตุใหเ้ กิดวงจรอบั ไดเ้ ท่าเทียมกนั ) ถา้ การร้องขอแต่ละคร้ังสามารถขอทรัพยากรไดห้ ลายชนิดพร้อม ๆ กนั โปรเซสหน่ึงอาจร้องขอทรัพยากรแลว้ ทาํ ใหเ้ กิดวงจรอบั ข้ึนพร้อม ๆ กนัหลายวงจรกไ็ ด้ การตรวจหาวงจรอบั บ่อยเกินไป ยอ่ มทาํ ใหเ้ สียค่าใชจ้ ่าย(เวลา)มาก เพื่อที่จะประหยดัค่าใชจ้ ่าย เราอาจตรวจหาทุก ๆ ช่วงเวลาแทน เช่น ทุก ๆ 1 ชว่ั โมง หรือ เมื่อประสิทธิผลของการใช้หน่วยประมวลผลกลางลดต่าํ กวา่ 40 % (โดยปกติวงจรอบั จะทาํ ใหร้ ะบบทาํ งานไดน้ อ้ ยลง และเป็นผลใหป้ ระสิทธิผลของการใชห้ น่วยประมวลผลกลางต่าํ ลงดว้ ย) ถา้ เราตรวจหาวงจรอบั โดยวธิ ีสุ่มอาจเกิดวงจรอบั ข้ึนในระบบมากกว่า 1 วงจรได้ และเราอาจไม่สามารถช้ีชดั ไดว้ า่ โปรเซสใดเป็นตวัทาํ ใหเ้ กิดวงจรอบั เหล่าน้นั2.4.6 การคืนสถานะจากเดตลอ็ ก (Recovery from Deadlock)เม่ือตรวจพบวา่ เกิดวงจรอบั ข้ึนในระบบแลว้ ระบบอาจจดั การได้ 2 วธิ ี คือ 1. รายงานใหผ้ คู้ วบคุมเคร่ืองทราบวา่ ขณะน้ีเกิดวงจรอบั ข้ึนในระบบแลว้ และใหผ้ คู้ วบคุม จดั การแกไ้ ขวงจรอบั เอง 2. ระบบแกไ้ ขวงจรอบั เองโดยอตั โนมตั ิ ซ่ึงอาจทาํ ได้ 2 วิธี คือ

โปรเซส143  ยกเลิกโปรเซสที่ติดอยใู่ นวงจรอบั บางโปรเซสเพ่อื ที่จะตดั เดตลอ็ ก  อนุญาตใหม้ ีการแทรกกลางคนั ทรัพยากรบางส่วนที่ติดอยใู่ นวงจรอบั ไดเ้ พ่ือทาํ ให้ ระบบกลบั คืนสู่สภาวะปกติ2.4.6.1 การยกเลกิ โปรเซส (Process Termination)วธิ ีการในการแกไ้ ขเดตลอ็ กโดยการยกเลิกโปรเซสในเดตลอ็ กมีอยู่ 2 วธิ ี (ท้งั 2 วธิ ีน้ี เม่ือโปรเซสถูกยกเลิก ทรัพยากรที่โปรเซสถือครองอยจู่ ะคืนกลบั สู่ระบบ)  ยกเลกิ โปรเซสท้งั หมดทต่ี ิดอยู่ในเดตลอ็ กวธิ ีน้ีจะแกไ้ ขวงจรอบั ไดแ้ น่นอน แต่จะ เสียค่าใชจ้ ่ายสูง เพราะวา่ อาจมีบางโปรเซสท่ีไดเ้ ขา้ มาทาํ งานนานแลว้ แต่กลบั ตอ้ ง ถูกยกเลิกการทาํ งาน โดยผลลพั ธท์ ่ีไดจ้ ากการทาํ งานช่วงแรก ๆ จะถูกยกเลิกหมด และอาจจะตอ้ งกลบั มาทาํ งานใหม่  ยกเลกิ โปรเซสในวงจรอบั ทลี ะโปรเซส จนกระทงั่ ระบบกลบั สู่สภาวะปกติ วธิ ีน้ีก็ อาจมีค่าใชจ้ ่ายสูงเช่นกนั เพราะวา่ หลงั จากท่ียกเลิกโปรเซสหน่ึง ระบบจะตอ้ งทาํ การตรวจจบั วงจรอบั คร้ังหน่ึง เช่นกนั เพอ่ื ตรวจสอบวา่ ระบบยงั คงอยใู่ นสถานะ วงจรอบั หรือไม่ ซ่ึงถา้ ตอ้ งการยกเลิกหลายโปรเซส กต็ อ้ งตรวจจบั วงจรอบั หลาย คร้ังตามไปดว้ ยจะสงั เกตวา่ การยกเลิกโปรเซสไมใ่ ช่เร่ืองท่ีทาํ กนั ง่าย ๆ เช่น ถา้ โปรเซสกาํ ลงั แกไ้ ขแฟ้มขอ้ มูลอยู่การยกเลิกโปรเซส อาจก่อใหเ้ กิดความผดิ พลาดของขอ้ มูลในแฟ้มขอ้ มูล เช่นเดียวกนั กบั โปรเซสกาํ ลงั พิมพข์ อ้ มูลออกสู่เครื่องพมิ พ์ เม่ือโปรเซสน้ีถูกยกเลิก ระบบจะตอ้ งกาํ หนดสถานะของเคร่ืองพมิ พใ์ หม่ใหถ้ ูกตอ้ งเสียก่อนที่จะพมิ พง์ านต่อไป สาํ หรับวิธีการยกเลิกโปรเซสทีละตวั เราจาํ เป็นตอ้ งพจิ ารณาเลือกวา่ โปรเซสใดที่ควรจะถูกยกเลิก เพอ่ื ที่จะทาํ ใหร้ ะบบกลบั สู่สภาวะปกติ ปัญหาการเลือกน้ี คลา้ ยกบั ปัญหาการจดั ตารางการทาํ งานของหน่วยประมวลผลกลาง โดยโปรเซสที่จะถูกยกเลิกจะตอ้ งเป็นโปรเซสท่ีก่อใหเ้ กิดค่าใชจ้ ่ายนอ้ ยที่สุด ซ่ึงการพิจารณาค่าใชจ้ ่ายต่าํ ที่สุด อาจพิจารณาไดจ้ ากหลายปัจจยั ดงั น้ี 1. พิจารณาลาํ ดบั ความสาํ คญั ของโปรเซส (priority) 2. พิจารณาวา่ โปรเซสน้นั ทาํ งานมานานเท่าไรแลว้ และจะใชเ้ วลาอีกนานเท่าไรกวา่ งานจะเสร็จสมบูรณ์ 3. พจิ ารณาวา่ โปรเซสน้นั ไดถ้ ือครองหรือใชท้ รัพยากรประเภทใดไปเท่าไรแลว้ 4. พจิ ารณาวา่ โปรเซสยงั ตอ้ งการทรัพยากรอีกเท่าไร จึงจะทาํ งานจนเสร็จสมบูรณ์ได้ 5. พิจารณาวา่ มีกี่โปรเซสท่ีจะตอ้ งถูกยกเลิก 6. พจิ ารณาวา่ โปรเซสเป็นประเภทใด (แบบโตต้ อบ (interactive) หรือแบบกลุ่ม (batch))

144 ระบบปฏิบตั ิการ2.4.6.2 การแทรกกลางคัน (Resource Preemption) การกาํ จดั เดตล็อกโดยการแทรกกลางคนั น้ันจะกระทาํ โดยยึดเอาทรัพยากรบางส่วนจากโปรเซสที่ติดอยใู่ นเดตล็อกแลว้ นาํ ทรัพยากรน้นั ไปจดั ให้กบั โปรเซสอ่ืนที่ตอ้ งการ โดยการแทรกกลางคนั น้ี จะกระทาํ ไปเร่ือย ๆ จนกว่าระบบจะกลบั สู่สภาวะปกติ (วงจรท่ีก่อให้เกิดวงจรอบัหายไปจากระบบ) ในการเลือกใชว้ ิธีการแทรกกลางคนั เราจะตอ้ งพจิ ารณาผลที่จะเกิด 3 ขอ้ ดงั น้ี 1. การเลือกผู้รับเคราะห์ (Selection a victim) โดยการเลือกวา่ โปรเซสใดในวงจรอบั ท่ีจะถูก แทรกกลางคนั โดยเราจะเลอื กโปรเซสท่ีเม่ือถูกแทรกกลางคนั แลว้ จะเสียค่าใชจ้ ่ายนอ้ ย ที่สุด ปัจจยั ในการพจิ ารณาคา่ ใชจ้ ่าย ไดแ้ ก่ จาํ นวนทรัพยากรที่โปรเซสน้นั ถือครองอยู่ และ ระยะเวลาท่ีโปรเซสน้นั ไดท้ าํ งานมาแลว้ เป็นตน้ 2. การถอยกลบั (Rollback) ถา้ โปรเซสถูกแทรกกลางคนั เราจะทาํ อยา่ งไรกบั โปรเซสน้นั แน่นอนโปรเซสน้นั ไม่สามารถทาํ งานต่อไปได้ เพราะขาดทรัพยากรที่โปรเซสน้นั ตอ้ งการ ดงั น้นั เราจาํ ตอ้ งใหโ้ ปรเซสน้นั ถอยกลบั ไปอยใู่ นจุดที่ปลอดภยั และใหเ้ ร่ิมทาํ งานใหม่อีก คร้ังจากจุดน้ี เน่ืองจากเป็นการยากที่จะพจิ ารณาวา่ จุดใดเป็นจุดที่ปลอดภยั ดงั น้นั วธิ ีที่ง่าย ที่สุด คือ ถอยกลบั ไปจนหมด (ถึงจุดเร่ิมตน้ ) โดยการยกเลิกโปรเซส แลว้ กลบั ไปเริ่ม ทาํ งานใหม่ แต่วิธีท่ีมีประสิทธิภาพมากกวา่ คือ การถอยกลบั ไปเท่าท่ีจาํ เป็นในการแกว้ งจร อบั เท่าน้นั แต่จะมีปัญหาในเร่ืองการเกบ็ ขอ้ มูลเก่ียวกบั สถานะต่างๆ ของโปรเซสท้งั หมดท่ี กาํ ลงั ทาํ งานอยู่ 3. การแช่เยน็ (Starvation) เราจะรับประกนั ไดอ้ ยา่ งไรวา่ จะไม่เกิดการแช่เยน็ เช่น มีโปรเซส หน่ึงถูกแทรกกลางคนั ทรัพยากรที่กาํ ลงั ใชอ้ ยเู่ สมอ ๆในระบบที่มีการเลือกผรู้ ับเคราะห์ โดยอยบู่ นพ้ืนฐานของปัจจยั ทางดา้ นค่าใชจ้ ่าย อาจเป็นไปไดท้ ่ีมีบางโปรเซสถูกเลือกเป็นผรู้ ับเคราะห์เสมอ ๆ ซ่ึงจะส่งผลใหโ้ ปรเซสน้นั ไม่สามารถทาํ งานจนเสร็จสมบูรณ์ได้ ดงั น้นั เราจะตอ้ งทาํ ใหแ้ น่ใจวา่ โปรเซสหน่ึง ๆ จะถูกเลือกเป็นผรู้ ับเคราะห์อยา่ งจาํ กดัคร้ัง (นน่ั คือ จะมีขอบเขตของจาํ นวนคร้ัง ในการถูกเลือกเป็นผรู้ ับเคราะห)์ อาจทาํ ไดโ้ ดยรวมจาํ นวนคร้ังในการถอยกลบั ของโปรเซสใหเ้ ป็นปัจจยั หน่ึงในการคิดค่าใชจ้ ่าย2.4.6.3 การจดั การปัญหาวงจรอบั โดยวธิ ีผสมผสาน (Combined Approach to Deadlock Handling) เป็นที่ทราบกนั ดีวา่ ไม่มีวธิ ีใดวิธีหน่ึงจะเหมาะสมกบั การจดั การปัญหาวงจรอบั ในระบบยอ่ ยต่าง ๆ ของระบบปฏิบตั ิการไดไ้ ม่วา่ จะเป็น วิธีการป้องกนั วิธีการหลีกเลี่ยง และ วิธีการตรวจหา เราจึงอาจใช้ หลายวิธีผสมกนั โดยเลือกวธิ ีที่เหมาะสมกบั ลกั ษณะของระบบยอ่ ยน้นั ๆ เร่ิมจากการเรียง

โปรเซส145ทรัพยากรเป็นพวก ๆ ตามลาํ ดบั ความสาํ คญั (โดยใชว้ ธิ ีการจดั เรียงลาํ ดบั ตามหวั ขอ้ 10.2.4) เพ่ือจดั แบ่งกลุ่มของทรัพยากร และในแต่ละกลุ่ม เราอาจเลือกใชว้ ิธีที่เหมาะสมที่สุดได้เราอาจพิสูจนไ์ ดว้ า่ ระบบที่ใชว้ ธิ ีผสมผสานน้ีจะไม่เกิดเดตลอ็ กดงั น้ีคือ 1. วงจรอบั ไม่อาจจะเกิดขา้ มกลมุ่ ของทรัพยากรได้ เพราะเราใชว้ ิธีการจดั เรียงลาํ ดบั ทรัพยากร 2. ในแต่ละกลุ่มกจ็ ะไม่เกิดวงจรอบั เพราะเราไดเ้ ลือกวิธีจดั การ 1 ใน 3 วธิ ี ท่ีกล่าว มาแลว้ ดงั น้นั ระบบโดยรวมจะไม่เกิดวงจรอบัตวั อยา่ งสมมติวา่ ระบบของเราประกอบไปดว้ ยทรัพยากร 4 ประเภท คือ 1. ทรัพยากรภายในของระบบ (Internal Resources) คือ ทรัพยากรที่ระบบใชเ้ อง เช่น PCB (Process Control Block) 2. หน่วยความจาํ หลกั (Central Memory) ซ่ึงผใู้ ชร้ ะบบตอ้ งใช้ 3. อุปกรณ์ต่าง ๆ ในระบบ (Job Resources) เช่น อุปกรณ์ทางกายภาพ อุปกรณ์ทางตรรกะ 4. หน่วยความจาํ สาํ รอง (Swappable space) พ้ืนท่ีในจานบนั ทึก (Backing Store) สาํ หรับ สาํ รองแต่ละงานเราจดั การปัญหาวงจรอบั ในระบบน้ี โดยจดั แบ่งกลุ่มของทรัพยากรเป็น 4 กลุ่ม ตามที่กล่าวมาและในแต่ละกลมุ่ ใชว้ ิธีจดั การดงั น้ี 1. ทรัพยากรภายในของระบบ ป้องกนั โดยการจัดลาํ ดบั ทรัพยากร เพราะโปรเซสที่ร้องขอ ทรัพยากรเหล่าน้ี ลว้ นเป็นโปรเซสภายในของระบบเอง 2. หน่วยความจาํ หลกั ป้องกนั โดยการใหม้ ีการแทรกกลางคันได้ เพราะอาจยา้ ยงานแต่ละชิ้น ออกจากหน่วยความจาํ หลกั ไปเกบ็ ไวใ้ นหน่วยความจาํ สาํ รอง (Backing Store) ไดโ้ ดยง่าย เมื่อมีโปรเซสตอ้ งการใชห้ น่วยความจาํ เพิม่ และหน่วยความจาํ เตม็ แลว้ 3. อุปกรณ์ต่าง ๆ ในระบบ ใชว้ ธิ ีการหลกี เลยี่ ง เพราะขอ้ มูลเกี่ยวกบั ความตอ้ งการสูงสุดของ แต่ละงานอาจรู้ล่วงหนา้ ได้ เช่น จากบตั รควบคุมงาน (Job Control Card) ในกรณีที่ใช้ บตั รเจาะรู (Punch cards) 4. หน่วยความจาํ สาํ รอง ป้องกนั โดย การจัดสรรล่วงหน้า เพราะจาํ นวนหน่วยความจาํ สาํ รอง สูงสุดของแต่ละงาน มกั จะถูกกาํ หนดไวแ้ ลว้ตวั อยา่ งน้ีแสดงใหเ้ ห็น แนวทางการจดั การปัญหาเดตลอ็ กแบบผสมผสาน ซ่ึงใชว้ ิธีต่าง ๆ ประกอบกนั โดยการจดั แบ่งกลุม่ ของทรัพยากร และเลือกวิธีการที่มีประสิทธิภาพสูงสุด สาํ หรับแต่ละกลุ่ม

146 ระบบปฏิบตั ิการ