การแปลงแผนภาพเวลาเป็นไทมด์ออโตมาตาสำหรับการจัดกำหนดการเชิงพรีเอ็มทีฟ

Abstract

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

กฎการจับคู่สำหรับการแปลงแผนภาพเวลาที่เป็นอิสระต่อกันเป็นไทมด์ออโตมาตาที่ได้รับการออกแบบในวิทยานิพนธ์นี้ และยังมีเครื่องมือซอฟต์แวร์ที่ได้รับการพัฒนาเพื่อแปลงไฟล์ต้นทางนำเข้าสกุลไฟล์ XML ของแผนภาพเวลาเป็นไฟล์ไทมด์ออโตมาตา สามารถจำลองแผนภาพไทมด์ออโตมาตาด้วยเครื่องมือ UPPAAL ซึ่งผลลัพธ์ของไทมด์ออโตมาตาจะแสดงกรอบเวลาโดยรวมของงานที่เกิดขึ้นพร้อมกันอันเป็นผลกระทบของการจัดกำหนดการเชิงฟรีเอ็มทีฟ การจำลองไทมด์ออโตมาตาจะจัดเตรียมตัวแปรนาฬิกาและสถานะโดเมนพิเศษเพิ่มเติม จากนั้นจึงนำไทมด์ออโตมาตาที่แปลงมาทวนสอบคุณสมบัติ TCTL ว่าการทำงานนั้นถูกต้อง เครื่องมือซอฟต์แวร์ของเราจะดำเนินการแปลงไดอะแกรมสำหรับการจัดกระบวนการเชิงพรีเอ็มทีฟ และใช้กรณีศึกษาสามกรณีเพื่อแสดงกระบวนการแปลงและการจำลองขั้นตอนกระบวนการทำงาน