วันนี้ผมได้ลองไปค้นไฟล์เก่าๆ และโปรเจคเก่าๆที่ทำไว้ตอนเรียน และได้พบกับโปรเจคตัวนึง ผมตั้งชื่อว่า Visual Processes Scheduling เป็นโปรแกรมแบบ Windows form  เป็นโปรเจคที่ผมเขียนขึ้นตอนเรียนวิชา Operating System (OS) เป็นช่วงที่เรียนอยู่ปี 3 อาจารย์ให้ทำโปรเจคท้ายเทอม เป็นอะไรก็ได้ที่เกี่ยวกับเนื้อหาในวิชา ผมจึงเขียนโปรแกรมคำนวณค่าออกมา เป็นเนื้อหาในส่วนของ Processes Scheduling ซึ่งโปรเจคตัวนี้ผมคิดว่าน่าจะมีประโยชน์สำหรับคนที่เรียนวิชานี้ จะทำให้เข้าใจเนื้อหาส่วนนี้ได้มากขึ้น ผมจะได้ทบทวนความรู้ด้วย

รู้จักกับ Processes Scheduling

ก่อนอื่นขออธิบายถึงเนื้อหาก่อน เรื่องนี้อยู่ในวิชา OS ซึ่งคนทั่วไปก็จะไม่ค่อยได้เรียนนัก น่าจะต้องเป็นสาย IT จึงจะได้เรียนวิชานี้ ผมจะอธิบายคร่าวๆ ว่ามันคืออะไร โดยปกติแล้ว ในคอมพิวเตอร์จะมี Process หรือเรียกว่างาน เกิดขึ้น จะเกิดจากผู้ใช้หรือการทำงานของคอมพิวเตอร์นี่แหละ และแน่นอนว่ามันมีจำนวนมากพอตัวเลย เป้าหมายที่มันเกิดมา คือมันต้องการประมวลผล โดย CPU ดังนั้นจึงทำให้เกิดการแย่งชิงเพื่อเข้าใช้งาน CPU แต่ทว่าเจ้า CPU เนี่ย มันก็ทำได้ทีละอย่าง บางงานก็ต้องทำนาน บางงานก็ทำแปบเดียว บางงานก็สำคัญมาก บางงานไม่จำเป็นต้องทำตอนนี้ ดังนั้นจึงต้องมีวิธีจัดการอย่างมีประสิทธิภาพ ซึ่ง OS จะต้องเลือก วิธีการจัดการงาน เรียกว่า CPU Scheduler (จัดการงานของ CPU) หลักๆเลย OS มันจะต้องจัดการงาน (Process) ให้กับ CPU ซึ่งมันก็มี วิธีการจัดการ (Scheduling Algorithms) หลายอย่างซึ่งจะเหมาะกับสถานการต่างๆดังที่กล่าวไป

ประเภทของ CPU scheduler

สามารถแบ่ง CPU scheduler ได้ 2 แบบคือ Preemptive scheduling (โดนแทรกแซงได้) กับ Nonpreemptive scheduling (ไม่โดนแทรกแซง) อันนี้เข้าใจได้ง่ายเลยคือ ถ้าเป็นแบบ Preemptive จะถูก process อื่นเข้ามาแย่ง CPU ได้ เช่น CPU เห็นว่ามี process ที่สำคัญกว่ายิ่งยวดมาใหม่ในคิว ก็จะลัดคิวให้เลย process ที่กำลังทำอยู่จะถูกหยุดชั่วคราว คล้ายๆกับ นักเรียน กำลังรอสั่งอาหารแล้วครูมา นักเรียนก็สละให้ครู (ก็ครูปกครอง ไม่สละได้ไง) ส่วนประเภท Nonpreemptive ก็จะไม่มีการลัดคิวเลย ครูก็ต้องไปต่อแถวนั่นเอง

รู้จักกับ Switching context

การที่ CPU เปลี่ยนไปเป็นอีกงานหนึ่ง คือ การสลับ เรียกว่า switching context ซึ่งทั้ง preemptive หรือ nonpreemptive ก็เกิดการสลับได้ทั้งนั้น (ไม่สลับก็ทำได้งานเดียวสิ) แต่ Preemptive scheduling (โดนแทรกแซงได้) อาจจะทำให้เกิดการสลับไปสลับมาของ process ได้ เข้าๆออกๆ จำนวนมากได้ ค่า switch นี้ยิ่งมีค่ามากก็จะแสดงว่า CPU ต้องสลับงานบ่อยนั่นเอง

รู้จักกับ Scheduling Criteria

OS จะต้องจัดการงานต่างๆให้กับ CPU ดังนั้นจึงต้องมีการประเมินความสามารถของกระบวนการพวกนี้เพื่อจะสามารถบอกได้ว่า ที่ทำอยู่ว่าดีแค่ไหน ดีที่สุดหรือยัง โดยจะมีการคำนวณค่าดังนี้

CPU utilization คือ ความสามารถใช้งาน CPU ได้อย่างเต็มประสิทธิภาพ มีค่าเป็น % ถ้าทำงานเต็ม 100 คือ ทำงานเต็มประสิทธิภาพที่มันทำได้ แต่ถ้าทำ 100 ตลอด มันก็จะเหนื่อยทำให้อายุการใช้งานสั้นลง (เหมือนคนเลย) ดังนั้น OS จึงให้ประมวลผลเต็มประสิทธิภาพที่สุดโดยที่ไม่กระทบกับ CPU จนเกินไปด้วย

Throughput คือ จำนวนงานที่ทำได้ในช่วงเวลาหนึ่ง ยิ่งมากก็ยิ่งดี เพราะจะหมายความว่าทำงานได้เยอะ

Turnaround time คือ เวลาทั้งหมดที่ process หนึ่งต้องใช้ นับตั้งแต่เริ่มต้นทำงานจนเสร็จเลย นับเวลารอด้วย ดังนั้นบางงานได้ทำแรกสุด แต่ก็อาจต้องรอ จนทำเสร็จอันสุดท้ายก็ได้เพราะโดนงานอื่นมาแทรก (น่าสงสาร)

Waiting time คือ เวลาที่ process ต้องรอ เช่น พอมาถึง ก็ไม่สามารถประมวลผลได้ เพราะต้องรองานที่มาก่อนทำเสร็จก่อน

Response time คือ เวลามีผลลัพธ์ออกมาครั้งแรก หลังจาก process แรกเข้าไป

จะเห็นว่าค่าด้านบนนี้สามารถนำมาบ่งบอกได้ว่า การจัดการงานที่ OS จะใช้มีประสิทธิภาพหรือไม่

รู้จักกับ Scheduling Algorithms

มาถึงพระเอกของเรื่องแล้วละ จากที่ OS เลือกว่าจะอนุญาตให้ งานอื่นมากแทรกได้มัย (preemptive VS nonpreemtive) OS ก็จะต้องเลือกกระบวนการ (Algorithm) ด้วย ซึ่งจะมีกระบวนการหลายแบบ ให้เลือกสรรเลยละ แต่ละแบบก็มีข้อดี ข้อเสียต่างกัน เหมาะกับสถานการณ์ต่างๆกันไป แต่บาง Algorithm ก็ต้องใช้กับ nonpreemtive หรือ preemptive เท่านั้นนะ โดยทั่วไปจะมีที่นิยมยกตัวอย่างอยู่ 4 แบบ

First Come First Served Scheduling (FCFS)

สำหรับตัวแรกง่ายมาก คือมาก่อนก็ได้ก่อน อันนี้จะไม่มีการแทรกแซงของงานอื่นเลย (nonpreemtive) จัดเป็นวิธีที่ง่ายที่สุดแล้วละ แค่มี Queue สักตัวก็ทำได้แล้ว ซึ่งเป็นข้อดีของมัน แต่ว่าถ้ามี process นึงมาถึงก่อน แต่ทำงานนานมาก จะทำให้ process อื่นๆที่มารอ ต้องคอยนานมากด้วย ส่งผลให้ค่า Waiting time สูงไปด้วย แบบว่า ครูขึ้นลิฟท์ไปชั้น 40 นักเรียนจะขึ้นลิฟท์ไปชั้น 4 นี่เอง ต้องรอซะนานเลย ส่งผลให้ นักเรียนที่มาต่อแถวก็ต้องรอเพิ่มขึ้นไปอีก

Shortest Job First Scheduling (SJF)

JSF เป็นวิธีที่น่าสนใจ หลักการคือ จะให้งานที่จะใช้เวลาน้อยที่สุดทำงาน ถ้ามีงานมาถึงพร้อมกัน งานที่ใช้เวลาน้อยกว่าก็จะได้ทำก่อน เหมือนคนจะแย่งกันเข้าลิฟท์ คนตัวเล็กก็จะได้เข้าไปก่อนนั่นเอง การทำแบบนี้ทำให้ waiting time มีค่าน้อยกว่าแบบ FCFS มาก ค่าของ turn around time ก็น้อยกว่าอีกด้วย เพราะไม่ต้องรอมากนัก แต่ข้อเสียของมันคือ CPU ไม่มีทางรู้อนาคตว่างานที่มาจะใช้เวลาทำเท่าไหร่ ทำให้ SJF ใช้งานจริงไม่ได้ เป็นเหมือนแนวคิดในอุดมคติ หลักการของ SJF สามารถใช้ได้ทั้งแบบ preemtive และ nonpreemtive นะ

Priority Scheduling

วิธีการนี้จะนำความสำคัญมาจัดการ หากมี process มาพร้อมกัน OS ก็จะให้ process ที่สำคัญกว่าเข้าทำงานก่อน ตัวเลขความสำคัญ (Priority) ที่นิยมใช้คือ 1-5 โดยยิ่งน้อยยิ่งสำคัญ ดังนั้น process ที่มี priority เป็น 1 จะสำคัญที่สุด เรียกว่ายิ่งใหญ่สุดเลยละ ถ้ามาทุกคนต้องหลบ หลักการนี้สามารถใช้ได้ทั้งแบบ preemtive และ nonpreemtive วิธีการนี้ถือว่า ดีพอสมควรเพราะจะได้ค่าเฉลี่ยที่น่าพึ่งพอใจ งานที่ไม่สำคัญก็ทำทีหลังไปเลย แต่ทว่าอาจเกิดปัญหาที่เรียกว่า ถูกแช่แข็ง ได้ (Starvation) ปัญหานี้ก็คือ process ที่ไม่สำคัญรอคิวนานมาก นานจนไม่มีวันได้ทำเลยละ เพราะถูกงานสำคัญๆ มาแย่งตลอด อาจารย์เล่าว่า มีคอมพิวเตอร์สมัยก่อนที่ทำงานมาหลายสิบปี แต่โปรแกรมเมอร์พึ่งพบว่าก็มีงานที่รอคิวอยู่ นานเป็นสิบๆปีเลย (น่าสงสารมากอะ) วิธีการแก้ก็คือ ถ้า process รอนาน ก็เพิ่ม priority ให้มันเรื่อยๆ (เหมือนเพิ่มยศให้มัน) แล้วเดี๋ยวมันจะได้ทำงานเอง

Round Robin Scheduling (RR)

round robin ตอนแรกผมนึกว่าคือชื่อคนคิดค้นซะอีก แต่ความจริงมันแปลว่า รอบวง ใช่แล้วครับ วิธีการนี้คือกำหนดให้ process ทำงานเป็นรอบๆ โดยจะกำหนดเวลาที่เท่าเทียมขึ้นมา เรียกว่า Quantum time โดย process ที่จะเข้าไปทำงาน จะทำงานแค่เวลาที่กำนด ใครทำไม่เสร็จก็ออกมาต่อแถวแล้วทำต่อ ส่วน process ไหนใช้เวลาน้อยกว่า Quantum time ก็จะสบายตัวไปไม่ต้องไปต่อแถวอีก ซึ่งเหมาะกับ CPU มีงานเข้ามาจำนวนมาก สิ่งสำคัญของ round robin คือ Quantum time ซึ่งหากกำหนดมากเกินไปก็จะไม่ต่างกับ FCFS โดยทั่วไปจะมีค่า ประมาณ 10 – 100 ms

พาชม Visual Processes Scheduling

ทั้งหมดทั้งกลาวไปเป็นทฤษฎี และเนื้อหาเกี่ยวกับการจัดการ process ของ OS ซึ่งอาจมองเห็นภาพได้ยากพอสมควร ต้องลองทำโจทย์ปัญหาดูก่อน Visual Processes Scheduling คือ โปรแกรมจำลองกระบวนการ Algorithm ดังที่กล่าวไปให้เห็นภาพมากขึ้นครับ

เปิดโปรแกรม (สามารถดาวน์โหลดโปรแกรม ได้ที่ท้ายบทความ)

เมื่อเปิดโปรแกรมจะพบหน้าจอข้างล่างนี้ ให้กด Next

จากนั้น สามารถเลือกจำนวน process ได้ เลือกสูงสุดได้ 10 processes และเลือก Algorithm สำหรับนำมาเปรียบเทียบ โดยจะมีให้เลือก 6 แบบ จากนั้นกด Next

หน้าต่อไปให้ใส่ข้อมูลของ process แต่ละอันลงไป โดย
Arrival time คือเวลาที่ process มาถึง
Burst time คือเวลาที่ process ใช้ทำงาน
Priority คือ ลำดับความสำคัญ (ยิ่งน้อยยิ่งสำคัญมาก)
Quantum time คือ เวลาที่ใช้ในวงรอบของ Round robin
จากนั้นกด Next

โปรแกรมจะประมวลผลและแสดงผลลัพธ์ ออกมา เช่นของ FCFS จะเป็นดังนี้ โดยตารางจะบอก ค่าของ waiting time และ turnaround time ของแต่ละ process ด้วย รวมทั้ง ค่าเฉลี่ย waiting time และ Context switch ทั้งหมดด้วย

ลองเลื่อนมาที่ SJF แบบ Preemptive แน่นอนว่าผลลัพธ์อาจจะต่างจากเดิม

ลองเลื่อนมาที่ SJF แบบ Nonpreemptive

ลองเลื่อนมาที่ Priority แบบ Preemptive

ลองเลื่อนมาที่ Priority แบบ Nonpreemptive ถ้าเราตั้ง ทุก process มี priority เท่ากันหมด ค่าของ Priority preemptive และ nonpreemptive จะเท่ากัน

ลองเลื่อนมาที่ Round Robin โดยเราสามารถปรับค่า Quantum time ที่หน้านี้ก็ได้เช่นกัน

ในกรณีที่ปรับ Quantum time มากเกินไปก็จะไม่ต่างกับ FCFS แต่ถ้าปรับมันต่ำเกินไป ทำให้เกิด context switch สูง มันสลับงานไปสลับงานมานั่นเอง

เมื่อกด Next จะแสดงผลลัพธ์รวมเปรียบเทียบ

จบแล้ว

โปรแกรม Visual Processes Scheduling เป็นโปรแกรมที่ผมจัดทำขึ้นเพื่อให้สามารถมองเห็นภาพเกี่ยวกับ เรื่อง  Processes Scheduling ของ Operating System ได้มากขึ้นนั่นเอง โดยเนื้อหาเกี่ยวกับเรื่องนี้สามารถหาอ่านได้ทั่วไปได้ เป็นเนื้อหาส่วนหนึ่งในวิชา OS ภายในโปรแกรมยังมีให้เลือก 2 ภาษาด้วยนะครับ ไทย-English

สามารถดาวน์โหลดไปลองทดสอบกันดูครับ หากมีข้อแนะนำ ติชม สามารถคอมเม้นได้ครับ

ดาวน์โหลดโปรแกรม (.exe)
Visual Processes Scheduling

ดาวน์โหลด source code (Visual Studio Project)

https://github.com/benznest/ProcessesScheduling

ขอบคุณที่ติดตามครับ (:

*อัพเดทเป็นเวอชัน 1.2 แล้ว แก้บัคไปบางส่วน

Reference
https://msit5.wordpress.com/2013/09/10/scheduling-algorithms-วิธีจัดลำดับการทำง