On Intelligent Mitigation of Process Starvation In Multilevel Feedback Queue Scheduling

<p>CPU time-share process schedulers for computer operating systems have existed since Corbato published his paper on the Compatible Time Sharing System in 1962 [8]. With this new type of scheduler came the need to effectively divide CPU time between N processes, where N could be 2 or more processes. Modern time-sharing process schedulers which have been developed in the decades since have been designed to favor shorter, interactive processes over long-running processes, especially when incoming demand for CPU time exceeds supply and process starvation is inevitable. These schedulers, including Linux CFS, FreeBSD Ule, and the Solaris Fair Share Scheduler, are all effective at favoring interactive processes under starvation conditions.</p> <p>Sometimes it’s not desirable that long-running processes be sacrificed altogether, but none of these schedulers have safeguards under starvation conditions. This thesis revisits and extends the research conducted in [13], in which it was demonstrated that starvation of long-running processes could be safely and effectively mitigated without adversely affecting the performance of shorter, interactive processes.</p> <p>The questions this thesis will answer are:</p> <ol> <li>Can MLFQ-NS, proposed in [13], be compared to other modern process schedulers? </li> <li>Can MLFQ-NS be improved? </li> </ol> <p>To answer the first question, a scheduler must be found which is similar enough to MFLQ for a direct comparison. This will require a survey of current schedulers. To answer the second question, the research conducted in [13] must be duplicated MLFQ-NS to ascertain the following:</p> <ol> <li>How much diverted time is actually used? </li> <li>Why does MLFQ-NS become ineffective past a certain system-load threshold, i.e. stop real- locating time to long-runnning processes?</li> </ol> <p>In this research, the original work was duplicated in simulations to validate previous re- sults, and determine why MLFQ-NS became ineffective after incoming CPU time demand exceeds a threshold. Research was conducted in order to determine if starvation mitigation in MLFQ-NS could be compared to other process schedulers used in production, with the conclusion that recent emphasis on priority scheduling and heurstic interactivity determination makes such a comparison impossible. Research then continued with simulations in which MLFQ-NS was given different run- time arguments than original simulations. Investigations into those results led to an algorithmic modification to MLFQ-NS called MLFQ-IM and analysis of simulations of MLFQ-IM. Conclu- sions about the effectiveness of MLFQ-IM will be explored. Finally, ideas for future research are offered.</p>

Name thesis:degree_name

Master of Science in Computer Science (MSCS)

Level thesis:degree_level

Thesis

Discipline thesis:degree_discipline

Computer Science

Year dc:date.available

2017

Author dc:creator

• Brown, Joseph E

Contributors dc:contributor

• Dr. Ken Hoganson
• Dr. Dan Lo
• Dr. Jose Garrido

• mlfq process scheduler starvation
• Computational Engineering

Repository record dc:identifier

https://digitalcommons.kennesaw.edu/cs_etd/8

OAI identifier oai:identifier

oai:digitalcommons.kennesaw.edu:cs_etd-1008