อัลกอริทึมการจัดตารางเวลา FCFS: คืออะไร ตัวอย่างโปรแกรม

เมื่อกระบวนการเข้าสู่คิวที่พร้อมใช้งาน PCB (Process Control Block) ของกระบวนการจะเชื่อมโยงกับส่วนท้ายของคิว และเมื่อ CPU ว่าง ก็ควรถูกกำหนดให้กับกระบวนการที่จุดเริ่มต้นของคิว

ลักษณะของวิธี FCFS

• รองรับอัลกอริธึมการตั้งเวลาแบบไม่ยึดเอาเสียก่อนและแบบยึดล่วงหน้า
• งานจะดำเนินการตามลำดับก่อนหลังเสมอ
• มันง่ายในการติดตั้งและใช้งาน
• วิธีการนี้มีประสิทธิภาพต่ำ และเวลารอโดยทั่วไปค่อนข้างสูง

ตัวอย่างการจัดกำหนดการ FCFS

ตัวอย่างในชีวิตจริงของวิธี FCFS คือการซื้อตั๋วหนังที่เคาน์เตอร์จำหน่ายตั๋ว ในอัลกอริธึมการจัดกำหนดการนี้ บุคคลจะได้รับบริการตามลักษณะของคิว ผู้ที่มาถึงก่อนในคิวจะซื้อตั๋วก่อนแล้วจึงซื้อตั๋วใบถัดไป การดำเนินการนี้จะดำเนินต่อไปจนกว่าคนสุดท้ายในคิวจะซื้อตั๋ว เมื่อใช้อัลกอริธึมนี้ กระบวนการ CPU จะทำงานในลักษณะเดียวกัน

FCFS ทำงานอย่างไร? การคำนวณเวลารอโดยเฉลี่ย

นี่คือตัวอย่างของกระบวนการทั้งห้าที่มาถึงในเวลาที่ต่างกัน แต่ละกระบวนการมีเวลาระเบิดที่แตกต่างกัน

กระบวนการ	ระเบิดเวลา	เวลาถึง
P1	6	2
P2	2	5
P3	8	1
P4	3	0
P5	4	4

การใช้อัลกอริธึมการจัดกำหนดการ FCFS กระบวนการเหล่านี้ได้รับการจัดการดังต่อไปนี้

ขั้นตอน 1) กระบวนการเริ่มต้นด้วย P4 ซึ่งมีเวลามาถึง 0

ขั้นตอน 2) เมื่อเวลา=1 P3 มาถึง P4 ยังคงดำเนินการอยู่ ดังนั้น P3 จึงถูกเก็บไว้ในคิว

กระบวนการ	ระเบิดเวลา	เวลาถึง
P1	6	2
P2	2	5
P3	8	1
P4	3	0
P5	4	4

ขั้นตอน 3) ณ เวลา = 2 P1 มาถึงซึ่งถูกเก็บไว้ในคิว

กระบวนการ	ระเบิดเวลา	เวลาถึง
P1	6	2
P2	2	5
P3	8	1
P4	3	0
P5	4	4

ขั้นตอน 4) ณ เวลา = 3 กระบวนการ P4 ดำเนินการเสร็จสิ้น

ขั้นตอน 5) ณ เวลา=4 P3 ซึ่งเป็นลำดับแรกในคิวจะเริ่มดำเนินการ

กระบวนการ	ระเบิดเวลา	เวลาถึง
P1	6	2
P2	2	5
P3	8	1
P4	3	0
P5	4	4

ขั้นตอน 6) ณ เวลา =5 P2 มาถึง และถูกเก็บไว้ในคิว

กระบวนการ	ระเบิดเวลา	เวลาถึง
P1	6	2
P2	2	5
P3	8	1
P4	3	0
P5	4	4

ขั้นตอน 7) ณ เวลา 11 P3 ดำเนินการเสร็จสิ้น

ขั้นตอน 8) ณ เวลา=11 P1 เริ่มดำเนินการ มีเวลาระเบิดเป็น 6 ดำเนินการเสร็จสิ้นในช่วงเวลา 17

ขั้นตอน 9) ณ เวลา = 17 P5 เริ่มดำเนินการ มีเวลาระเบิดเป็น 4 ดำเนินการเสร็จสิ้นเมื่อเวลา = 21

ขั้นตอน 10) ณ เวลา=21 P2 เริ่มดำเนินการ มีเวลาระเบิดเป็น 2 ดำเนินการเสร็จสิ้นในช่วงเวลา 23

ขั้นตอน 11) ลองคำนวณเวลารอโดยเฉลี่ยสำหรับตัวอย่างข้างต้น

Waiting time = Start time - Arrival time

P4 = 0-0 = 0

P3 = 3-1 = 2

ปี่ = 11-2 = 9

P5= 17-4 = 13

P2= 21-5= 16

เวลารอโดยเฉลี่ย

= 40 / 5 = 8

ข้อดีของ FCFS

นี่คือข้อดี/ประโยชน์ของการใช้อัลกอริทึมการตั้งเวลา FCFS:

• รูปแบบที่ง่ายที่สุดของ a อัลกอริธึมการตั้งเวลา CPU
• ง่ายต่อการตั้งโปรแกรม
• มาก่อนเสริฟก่อน

ข้อเสียของ FCFS

นี่คือข้อเสีย/ข้อเสียของการใช้อัลกอริธึมการตั้งเวลา FCFS:

• เป็นอัลกอริธึมการตั้งเวลา CPU แบบไม่ต้องเสียเปรียบ ดังนั้นหลังจากที่กระบวนการได้รับการจัดสรรให้กับ CPU แล้ว กระบวนการจะไม่ปล่อย CPU จนกว่าจะดำเนินการเสร็จสิ้น
• เวลารอโดยเฉลี่ยอยู่ในระดับสูง
• กระบวนการสั้นที่อยู่ด้านหลังคิวต้องรอให้กระบวนการยาวที่ด้านหน้าเสร็จสิ้น
• ไม่ใช่เทคนิคที่เหมาะสำหรับระบบแบ่งเวลา
• เนื่องจากความเรียบง่าย FCFS จึงไม่มีประสิทธิภาพมากนัก

สรุป

• คำจำกัดความ: FCFS เป็นอัลกอริทึมการกำหนดตารางการทำงานของระบบปฏิบัติการที่จะดำเนินการตามคำขอและกระบวนการที่อยู่ในคิวโดยอัตโนมัติตามลำดับการมาถึง
• รองรับการตั้งเวลาแบบไม่ยึดถือและยึดถือล่วงหน้า
• ขั้นตอนวิธี
• FCFS ย่อมาจาก First Come First Serve
• ตัวอย่างในชีวิตจริงของวิธี FCFS คือการซื้อตั๋วหนังที่เคาน์เตอร์จำหน่ายตั๋ว
• มันเป็นรูปแบบที่ง่ายที่สุดของอัลกอริทึมการตั้งเวลา CPU
• เป็นอัลกอริธึมการตั้งเวลา CPU แบบไม่ต้องเสียเปรียบ ดังนั้นหลังจากที่กระบวนการได้รับการจัดสรรให้กับ CPU แล้ว กระบวนการจะไม่ปล่อย CPU จนกว่าจะดำเนินการเสร็จสิ้น