Preemptive MinithreadsMulti-level Feedback QueuesMulti-level QueuesOur Scheduling AlgorithmAlgorithm ComparisonsSlide 6InterruptsClock Handler and AlarmsLow-level synchronizationWarningsHow to get startedGradingQuestions?Preemptive MinithreadsTom RoederCS415 2005spMulti-level Feedback QueuesQuantum = 2Quantum = 4Quantum = 8Quantum = 16Lowest priorityHighest priorityBorrowed from414 notesMulti-level QueuesJust like a regular queue, except4 levels: can insert into any oneIf a dequeue is requested and there’s no element on this level, try the next. Return which level.returns NULL and -1 if the are no elementsNote: errors inside the queues should cause an exitWe will use this data structure for schedulingYou will want to reuse your queue implOur Scheduling AlgorithmFeedback Queues:4 levels with quantum doubling at eachdemotion: if thread overruns its quantumie. thread has not yielded before preemptionwill happen frequently for CPU-bound procspromotion: by ageassign points upon queue entrypoints accumulate over timewe add a promotion thresholdAlgorithm ComparisonsOur alg: starvation eliminationTries to get SRTF schedulingcurrent level: function of age and past CPU burststhus we are averaging CPU bursts over ageother optionsno promotionsmany jobs float to the bottomvery predictablepoor waiting time and latencyAlgorithm Comparisonsother options (cont’d)weighted levelsalways work with all levels, but visit lower ones rarelyassign weights to each level: 50%, 25%, 15%, 10%still no promotion, so all past history matters!burst measurements for promotionslittle real historyneed to add a weighted averaging to be realisticotherwise very unpredictable, jitteryInterruptsOn minithread_clock_init, you will start receiving interruptsRight now just clock interrupts, but a general interrupt mechanism is present in the codeNetwork packets will later cause interruptsHappen on the current stackControl is wrenched from the current threadGiven to clock handlerDon’t waste time in the clock handler!Clock Handler and AlarmsWhen you receive a clock tick:Don’t use system functions (too slow)Just count the ticks in a variableNeed a structure to keep track of alarmsHint: you probably have already implemented oneA queue normally doesn’t provide fast searchThis is OK, if you assume cancel infrequentYour clock handler will need to run the alarmsalarm functions must be short and not block!Low-level synchronizationCannot block at interrupt time:interrupts may interrupt our synch codefor short synchronization: disable interruptsinterrupt_level_t intlevel = set_interrupt_level(DISABLED);/* your code here */set_interrupt_level(intlevel);Don’t do this too much: hurts performancewill be penalized in gradingWarningsDo not block while interrupts are disabledDo not call system functions in a handlerInterrupts may be called in any contextAvoid disabling interrupts wherever possiblemake any disabled period as short as possibleBeware of nested disable/enable blocksSynchronize all global data!How to get startedFirst implement and test the multi-level Qdequeue should always return a value if possibleThen experiment with clock interruptsslow them down (modify “interrupts.h”)make sure a simple handler worksAdd alarmsChange the schedulermake sure round-robin works on a simple queueadd points and a multi-level queuedo demotion and promotionGradingCorrectnessavoid race conditions (eg. in alarm code)nested interrupt level changesEfficiencyhandlers must be fastidle thread runs only when idledon’t overdo interrupt disablingGood software engineeringclean design, good
View Full Document
Unlocking...