Scheduling problem in distributed hard real-time computer systems:A simulation approach to dynamic task scheduling using focused addressing and bidding

Abstract

Katı gerçek zamanlı sistemlerin özelliği olan süre sınırlaması, bu sistemleri geleneksel bilgisayar sistemlerinden farklı kılmaktadır, çünkü bu tür sistemlerde talep edilen işler yalnızca görev bakımından doğru olarak değil, aynı zamanda vaktinde yerine getirilmelidirler. Bu tezde dağıtılmış sistemlerde katı gerçek zamanlı işlerin planlanması sorunu ayrıntılı olarak incelenmektedir. Katı gerçek zamanlı işlerin planlanması konusunda şimdiye dek önerilmiş algoritmalar gözden geçirilmektedir. Sadece MIB planlamasını değil, işlerin genel kaynak ihtiyaçlarını da dikkate alan bir buluşsal algoritma değerlendirilmek üzere seçilmiştir. Bu algoritma tarafından kullanılabilinecek bir grup buluşsal fonksiyon, bir seri benzetim çalışması ile incelenmektedir. En iyi performansı verdiği gözlenen buluşsal fonksiyon dağıtılmış planlama algoritmasında kullanılmaktadır. Bu algoritmada yerel olarak garanti edilemeyen iş için hedef düğümün seçiminde pey sürme ve direkt gönderme algoritmalarını birleştiren bir teknik esas alınmaktadır. Algoritmanın performansını gözlemlemek amacı ile çeşitli uygulama şartları için benzetim çalışmaları yapılmaktadır. Algoritmanın performansı başka üç değişik dağıtılmış planlama algoritmasının performansları ile de karşılaştırılmaktadır. Bu algoritmanın, uygulama alanının özelliklerine hassas olmasına rağmen, geniş bir uygulama alanı içinde, diğer algoritmalara kıyasla iyi bir performans gösterdiği gözlenmektedir.

The unique feature, the time constraint, of hard real-time systems makes them different from the traditional computer systems because in such systems the required tasks must be executed not only functionally correctly but in a timely manner. In this thesis, the scheduling problem of hard real-time tasks in distributed systems is examined in detail. Previous work on the algorithms proposed for scheduling in hard real-time systems is reviewed. A heuristic algorithm which considers not only CPU scheduling but also general resource requirements of tasks is chosen to be evaluated. A set of heuristics that can be used by this algorithm is studied through a sequence of simulations. The heuristic function which is observed to perform the best is incorporated in the distributed scheduling algorithm. In this algorithm the determination of a good destination node for a locally nonguaranteed task, is based on a technique that combines bidding and focused addressing algorithms. Simulation studies are conducted in order to evaluate the performance of the algorithm in a wide range of application environments. The performance of the algorithm is also compared to that of three other distributed scheduling algorithms. It is observed that though this algorithm is sensitive to the characteristics of the environments, it performs well in a wide range of environments, compared with the other algorithms.