Çok işlemcili gerçek zamanlı sistemler için sanal ihmal edilebilirlik güdümlü iş sıralama

Abstract

Bu tezde çok işlemcili sistemler için gerçek zamanlı bir iş sıralama algoritmasısunulmuştur. Çalışmada kullanılan sistemin eş işlemciler içerdiği ve görevkümesinin ise yalnızca örtülü zaman sınırlarına sahip periyodik görevlerden oluştuğu kabul edilmiştir.Bu konuda yapılan güncel çalışmalarda, iş sıralama algoritmaları adil davranmaprensibi üzerine yoğunlaşmış olmasına rağmen önerilen algoritmada bu kısıtlarabağlı kalmadan başarımı daha yüksek iş planları üretilmesi amaçlanmıştır.Tezde önerilen, Sanal İhmal Edilebilirlik Güdümlü (VLDS) iş sıralama algoritmasındaadil davranma sınırları göz ardı edilerek bağlam değişimi sayısı düşürülmüş veişlerin ortalama tepki süreleri iyileştirilimiştir. Bununla beraber VLDS algoritmasıyalnızca adil davranarak çözümlenebilecek görev kümeleri için de iş planlamasıyapabilmektedir.VLDS algoritması iki ana parçadan meydana gelmektedir. Bunlardan ilkiiş sıralama süreci boyunca mevcut görev kümesini belirli zaman aralıklarıiçin alt kümelere ayıran algoritmayı içeren kısım, ikincisi ise bu alt kümeleriçerisinde iş sıralamayı gerçekleştiren kısımdır.VLDS algoritmasın alt görev kümelerinin oluşturulması en yakın zaman sınırına$D_{n}$ göre yapılmaktadır. Amaç iş sıralaması yapılacak olan işlerinaynı zaman sınırına sahip olmasına sağlayabilmektir. Bu sağlandıktan sonraLLF (en az ihmal edilebilir önce) gibi algoritmalarla çözülebilmektedir.Bu çalışmada LLF iş sıralama algoritmasında oluşabilecek yüksek sayıdabağlam değişimini engellemek için LLF algoritmasına kesinti kısıtı eklenmiştir.Kesinti kısıtlı en az ihmal edilebilr önce (LLFPC) algoritması ile oluşturulaniş planlarındaki bağlam değişim sayısı düşürülmüş ve iş sıralama algoritmasınınher kuantumda çalışması gerekliliği ortadan kaldırılmıştır.LLFPC'den önce ilk yapılması gereken sistemde bekleyen işlerden bir alt kümeoluşturulmasıdır. Öncelikle en yakın zaman sınırı $D_{n}$ belirlenir ve buzaman sınırı ile belirlenen aralık için alt iş kümesi oluşturulmaya başlanır.Alt küme oluşturma işleminde tüm işler sahip oldukları zaman sınırına göreiki kümeye ayrılmaktadır. Bu kümelerden ilki Yüksek Öncelikli (HP), zamansınırı $D_{n}$ ile aynı olan işleri içeren görev kümesi; ikincisiDüşük Öncelikli (LP), zaman sınırı $D_{n}$'den yüksek olan işleri içeren görev kümesidir.Oluşturulacak alt iş kümesinde zaman sınırlarının kaçırılmaması için HP'de bulunantüm işlerin bu alt kümeye dahil edilmesi gerekmektedir. Zaman sınırı dahayüksek olduğu halde bu aralık içerisinde zaman sınırını kaçırma riski taşıyan işlerLP kümesi içerisinde bulunabilir. Bu yüzden alt iş kümesinin oluşturulduğu zaman aralığınıngenişliğinden daha düşük ihmal edilebilirlik değerine ($ /left(D_{n} -t /right) > l $)sahip LP görevlerin zaman sınırlarını kaçırmamaları için en az ($D_{n} -t -l$)kadar çalışma süresi kadar işlemciye sahip olmalıdırlar. Buatama da gerçekleştirildikten sonra boş kalan işlemci süresi LP işler arasındaihmal edilebilirlik değerine göre dağıtılmaktadır. Böylece alt iş kümesininoluşturulması tamamlanmaktadır. En yakın zaman sınırına ($D_{n}$) gelindiğinde bu işlem tekrar yapılarakyeni bir alt iş kümesi oluşturulmaktadır.VLDS algoritması, oluşturulan alt iş kümeleri içerisinde kullanılan LLFPC sayesindeişlerin yürütülmesi sırasında oluşabilecek kesilmelerinin sayısını azalttığından vezaman sınırını kaçırma riski bulunmayan LP işler arasında, adil davranma kısıtıgözetmeksizin dağıtım yapabildiğinden oluşturduğu iş planlarındakibağlam değişim sayısını düşürmekte ve işlerin ortalama tepki süreleriniazaltmaktadır.

An optimal real time scheduling algorithm has been presented in this thesisfor multiprocessor systems. It has been assumed that system consists midentical processors and only contains periodic tasks with implicit deadlines.Despite of the recent studies focus on the notion of fairness,the proposed algorithm improves average response time of the tasks anddecreases the number of the context switches by reducing the fragmentedexecution of the tasks without any fairness constraints.In spite of the common usage of traditional scheduling algorithms such asEarliest Deadline First (EDF) and Least Laxity First (LLF) in singleprocessor systems, it has been shown that they are not suitable formultiprocessor scheduling problems.In this thesis, a new algorithm, Virtual Laxity Driven Scheduling (VLDS), is proposed.The VLDS algorithm ignores fairness for the sake of both fewer context switchesand shorter response times. However, the VLDS algorithm also schedules thetask sets that can only be scheduled by a fair schedulers.The VLDS is composed of two algorithms that would work consequently.One of the algorithms is used to create sub-work sets from GTS,another one is used to schedule these sub-work sets.Basic principal of the VLDS algorithm is to create sub work sets according to the nearestdeadline. All tasks in this sub-work set must share the same deadline.Then the scheduling problem can be resolved over the sub-work set withLeast Laxity First(LLF). But the number of context switches increases dramatically even for asmall scale systems when there exists tasks which have equal laxity values.A simple derivation of the LLF algorithm, whichconstraints preemption operations, has been proposed in order to reduce the number ofcontext switches in the scheduling.With the introduction of preemption constraints toLeast Laxity First (LLF), the number of context switches and the overheadof the scheduling is reduced by removing the necessity of the laxitycalculations on each quantum.LLFPC algorithm assigns least laxity tasks first and defines nextpreemption point according to laxity value of the unassigned task withthe least laxity. This prevents context switches until an unassignedhas no (zero) laxity. When a preemption occurs, algorithm reassigns tasks bytheir new laxity values and define a expected new preemption time.First step in the VLDS algorithm while creating sub-work-set isdetermining the nearest deadline ($D_{n}$). The duration between the currenttime and the $D_{n}$ is called interval and and all calculations are boundedwith this interval. Once the $D_{n}$ is determined, the total number of time slotsprovided by the processors, which is contained by the interval, is calculated.Tasks with deadline $D_{n}$ are scheduled within the interval.However, there might be the additional time slots available within the intervalfor use of other tasks. To distribute these time slots among the tasks,they are grouped as High Priority (HP) and Low Priority (LP) task sets.The deadlines of the HP tasks equal to the $D_{n}$ and their executionshave to completed in the current interval. Therefore remaining execution time ofeach HP tasks must be included in the created work-set to meet deadlines.After the HP tasks, included in the created work-set, remaining idle timeis distributed among the LP tasks. LP tasks that have lower laxitiesthan the interval could miss their deadlines if the tasks have notscheduled in the current interval. In order to prevent negative laxity(deadline miss), at least $( D_{n} - l_{T_{i}} )$ time slots must beassigned for each LP task with laxity lower than the nearest deadline.After these assignments have been made, there have to be additionalremaining idle time to assign LP tasks. It has been shown with the proof of optimalitythat it is impossible to schedule given task set if there is no remaining idletime just after necessary distribution for LP and HP tasks to prevent deadline misses inthe current interval has been made.After the necessary distributions, remaining idle time is distributed amongLP tasks according to their laxity values.Until no idle time is left in the current interval or no waiting task isleft in GTS, maximum idle time that could be assigned to a LP task has beenassigned by starting the LP task with the lowest laxity. This last distributionprovides improvements that algorithm offers. Idle time slots left after thenecessary distribution is assigned to LP tasks without any fairness constraintsand allows to reduce fragmented execution of the tasks i.e, decrease thenumber of context switches.Once all possible distribution of the time slots in the interval among taskshas been performed, LP Tasks which have been assigned the current work setcould be considered as virtually divided into two parts. The first part ofthe task contains the information that is going to be used in the scheduling ofthe current sub work set by LLFPC algorithm. Second part holds the informationthat belongs to the remaining part of the task. Assigning time slots to thetasks could be considered as dividing task into two parts and assigned valueswill define virtual values of that task.In current work-set tasks could be distinguished from each other under twodifferent categories. In first category, tasks have the states of LLFPC algorithm,a task could be in any state such as Ready, Virtual Zero Laxity and Running atany time during the interval which the current work set is created for. Secondcategory depends on the real deadline value of the task. In this category,tasks are belong to the High Priority State or Low Priority State and thereis not going to be any transition between these states until the end of interval.This category has no effect on decisions of the LLFPC algorithm.If there is a condition that the total number of time slots required by theLow Priority tasks is equal or greater than the idle time left in the intervalafter assignment of the High Priorty Tasks has done(totalTimeSlotsRequiredforLPTask $/geq$ idleTime)then the scheduler could not assign the required time to LP tasks.Missing deadlines will be unavoidable. With this assumption, it will be shown thatwhere this condition exists, total utilization of GTS is greater thanthe number of processors.STORM (Simulation TOol for Real time Multiprocessor scheduling ) has beenused to develop and test algorithms. STORM provides discrete time simulationenvironment for multiprocessor systems that may contain periodic and aperiodic tasks.A work conserving and optimal scheduling algorithm, VLDS, has been presented andit has been stated that VLDS when compared fair schedule algorithms decreases thenumber of context switches and improves the average response times of the tasks.This paper shows that fairness could be relaxed or even ignored in some casesto provide better schedules. As future work, cache awareness could be implementedto reduce context switches and migrations at the junctions that one intervalfinishes and begins. Thus, arbitrary assignments of the tasksto the processors could be replaced with assignment decisions that takeinto account the cache contents of the processors.