Change search
ReferencesLink to record
Permanent link

Direct link
Proportional and sporadic scheduling in real-time operating systems
2008 (English)Independent thesis Advanced level (professional degree), 20 credits / 30 HE creditsStudent thesis
Abstract [en]

Real-time systems consist of two different tasks, periodic and aperiodic (sporadic) tasks. Each of these tasks can have a hard or a soft deadline. When a system, containing both non real-time tasks, and real-time tasks, is faced with an overload situation scheduling its tasks is absolutely critical in order to guarantee the correctness of the system. That is, keeping the hard deadlines and also to guarantee good average response time for the soft deadline tasks. One problem that these kinds of systems face under overload is that normal tasks that do not have a real-time priority can suffer from starvation. Two of the possible solutions that can cure this problem are covered by this master thesis. One solution is to have a proportional scheduler, which is a scheduler that can assign a percentage of available CPU time to a task. The other solution is to have a Sporadic Server (SS) scheduler scheduling the tasks of the system. A SS scheduler works by handing out a budget to tasks, this budget represent the minimum guaranteed CPU time that this task have available. This budget will also be replenished within a period from where it was consumed. Under user-space a proportional scheduler, named: SCHED_PROPORTIONAL (SP), have been developed and implemented. It works by letting each task reserve a percentage of the available CPU time. By doing this to all the tasks that are in danger of starving, the problem of starvation is solved. In kernel-space an implementation of the POSIX SCHED_SPORADIC (PSS) has been done. PSS is a sporadic server scheduling algorithm that hands out a budget to tasks, the budget represent the longest time that a task is allowed to have access to the CPU at a certain priority level. The part of this budget that is consumed is replenished within a specified time period from the time that is was consumed in the manner that the algorithm describes. The implementations have been done both in the OpenSUSE Linux and the OpenSolaris operating systems. Performance test have been done in user-space regarding scheduling overhead and introduced thread latency. In kernel-space only functions test have been made since the performance is viewed as good enough in kernel-space and the correctness of the implementation is more important to test. In user-space the test results indicate that a user-space scheduler can provide low overhead and good latency as long as the task using the SP-scheduler does not allocate more than 50% of the CPU time. If in which case the latency will increase rapidly and depending on how sensitive other real-time tasks are to this introduced latency have to rule if this scheduler can be used or not. But typically one would not have over 50% CPU time allocated for background service threads, which is the primary use of this scheduler.

Place, publisher, year, edition, pages
Keyword [en]
Technology, scheduling
Keyword [sv]
URN: urn:nbn:se:ltu:diva-53845ISRN: LTU-EX--08/061--SELocal ID: ad7b7bce-47c9-4aed-918b-1063dd58e5e3OAI: diva2:1027222
Subject / course
Student thesis, at least 30 credits
Educational program
Computer Science and Engineering, master's level
Validerat; 20101217 (root)Available from: 2016-10-04 Created: 2016-10-04Bibliographically approved

Open Access in DiVA

fulltext(1235 kB)0 downloads
File information
File name FULLTEXT01.pdfFile size 1235 kBChecksum SHA-512
Type fulltextMimetype application/pdf

Search outside of DiVA

GoogleGoogle Scholar
The number of downloads is the sum of all downloads of full texts. It may include eg previous versions that are now no longer available

Total: 1 hits
ReferencesLink to record
Permanent link

Direct link