Unformatted text preview:

Project ScopeImplementation detailsInterruptsAdding synchronizationMore on interruptsAlarmsSleeping with timeoutMultilevel SchedulingConcluding Thoughts (Grading)Project 2Project 2Adding PreemptionRobert EscrivaSlide heritage: Previous TAs → Krzysztof OstrowskiCornell CS 4411, September 20, 2010Project 2AnnouncementsProject 1 due Wednesday at 11:59PM.Project 2 no sooner than one week from today at11:59PM.Web page is being updated frequently; check forupdates.Email [email protected] help.Project 21 Project Scope2 Implementation detailsInterruptsAdding synchronizationMore on interruptsAlarmsSleeping with timeoutMultilevel Scheduling3 Concluding Thoughts (Grading)Project 2Project ScopeWhat are does adding preemption involve?1 Make your code threadsafe.2 Install the interrupt handler.3 ???4 Profit!∗∗Profit will come in the form of gradesProject 2Project ScopeDeliverablesAdd preemption to your scheduler.You will use clock interrupts for preemption.All code you wrote before must be made (mini)thread-safe.Alarms; sleeping with a timeout.Multilevel feedback scheduling policy.Assign priorities to threads.Round-robin between threads of the same priority.Scheduler will change thread priority based on feedbackfrom thread behavior.Project 2Project ScopeImplementation plan1 Start receiving clock interrupts.Register interrupt handler.Start measuring time in ticks.2 Add preemption.Synchronize access to global structures.Interrupts may come at any time.Our synchronization method of choice: disabling interrupts.†Switch threads in the interrupt handler.†You only really need to disable interrupts in minithread.cProject 2Project ScopeImplementation plan3 Add alarms.Create software structure(s) to track pending alarms.Use the software clock to measure elapsed time.Start firing alarms from the clock interrupt handler.4 Add sleeping.minithread_sleep_with_timeout(int delay);Register alarms, block/unblock threads.Project 2Project ScopeImplementation plan5 Add multi-level feedback scheduling.Implement multilevel feedback queues.Use a regular queue as the underlying structure.Add a cyclic search for dequeue.Extend your scheduler to use the new policy.Switch to the new data structure.Cycle through all four levels (to avoid starvation).Add feedback and move threads between levels.Project 2Implementation detailsInterruptsInteracting with InterruptsDefinitions:typedef void (*interrupt_handler_t)(void*);void minithread_clock_init(interrupt_handler_t clock_handler);Sample clock handler:void clock_handler(void*arg) {}Project 2Implementation detailsInterruptsWriting an Interrupt HandlerThe interrupt handler is interruptible!You should disable interrupts (temporarily) while inthe handler.Interrupt handlers should be fast:System functions, printf, etc. are all too expensive.You definitelyCANNOT BLOCK!.Project 2Implementation detailsInterruptsEnabling/Disabling InterruptsDefinitions for changing interrupts:typedef int interrupt_level_t;#define ENABLED 1;#define DISABLED 0;interrupt_level_t set_interrupt_level(interrupt_level_t newlevel);Strongly recommended usage:interrupt_level_t intlevel =set_interrupt_level(DISABLED)do_something();set_interrupt_level(intlevel);Project 2Implementation detailsInterruptsKeeping TimeChange the PERIOD in interrupts.h:#define SECOND 1000000#define MILLISECOND 1000#define PERIOD (100*MILLISECOND)Measuring elapsed timeSystem functions are way too slow.Software clock: just count interrupts.extern long ticks;Project 2Implementation detailsInterruptsHow are interrupts processed?Always execute in the context of a thread...... that happened to be running when the interruptwas triggered.The process of an interrupt:Current state is saved on the stack of the running thread.Handler is called.After the handler completes, the saved state is restored.Project 2Implementation detailsInterruptsInterrupts and System CallsWindows’ system libraries are not (mini)thread-safe...... so interrupts are disabled (underneath, not by you)while the process is inside system calls.What happens if e.g. a thread spends a lot of timeprinting to the screen?Most interrupts are missed.Scheduler cannot promptly switch between processes.Software clock drifts; alarms don’t fire on time.Project 2Implementation detailsAdding synchronizationWhy the need to synchronize?Clock interrupts may arrive at any (unprotected) placein your code.Any thread may be preempted while reading/writingthe scheduler’s data-structures.Multiple threads could concurrently try accessing thesame structures.The clock handler needs to access the same globalstructures (so that it may preempt threads).Project 2Implementation detailsAdding synchronizationSynchronization StrategiesWhat not to use: spin locksCannot use with interrupts disabled.Active waiting is time consuming.If we’re consuming processor time, who will unlock the lock?What to use: disabling interruptsWorks well on uniprocessors.Critical sections must be short (interrupts should not bedisabled for long).Disabling interrupts unnecessarily will be penalized.Follow the recommended pattern of usage.Project 2Implementation detailsMore on interruptsInformation so important that it has its own sectionUnmatched enabling/disabling.Your function could be called with interrupts disabled(enabling them would compromise your system’s safety).Application code should never run with interrupts disabled.Disabling interrupts unnecessarily.You should use better synchronization methods outsideminithreads.cDisabling interrupts for too long.Project 2Implementation detailsAlarmsImplementing AlarmsWhat you need to implement:int register_alarm(int delay,void (*func)(void*),void*arg);void deregister_alarm(int alarmid);What you need behind the scenes:Some structure to keep information about registeredalarms.Code in the interrupt handler to fire alarms.Use ticks to calculate elapsed time.Project 2Implementation detailsAlarmsUsing AlarmsAlarms are fired in the interrupt handler.Interrupts are disabled in the interrupt handler.You cannot spend much time in your callback.You cannot block.Alarm handler is called in the context of the currentlyexecuting thread...... which is likely to be different from the thread thatregistered the alarm.Project 2Implementation detailsSleeping with timeoutImplementing thread sleepingWhat you need to implement:void minithread_sleep_with_timeout(int delay);Expected behavior:Block the caller (and relinquish the CPU).The caller should not be on the ready


View Full Document

CORNELL CS 4410 - Study Notes

Download Study Notes
Our administrator received your request to download this document. We will send you the file to your email shortly.
Loading Unlocking...
Login

Join to view Study Notes and access 3M+ class-specific study document.

or
We will never post anything without your permission.
Don't have an account?
Sign Up

Join to view Study Notes 2 2 and access 3M+ class-specific study document.

or

By creating an account you agree to our Privacy Policy and Terms Of Use

Already a member?