Project 2: Preemption in CS 4411 - Spring 2017
Project 2 focuses on addressing issues of selfish threads, starvation, and interruption handling within multi-level feedback queue scheduling. The project introduces clock interrupts, alarms, interrupt handlers, and addresses the importance of performance optimization for handling shared data structures. Students are tasked with fixing bugs from Project 1 and implementing solutions to ensure smooth thread execution in the operating system.
Download Presentation
Please find below an Image/Link to download the presentation.
The content on the website is provided AS IS for your information and personal use only. It may not be sold, licensed, or shared on other websites without obtaining consent from the author. Download presentation by click this link. If you encounter any issues during the download, it is possible that the publisher has removed the file from their server.
E N D
Presentation Transcript
Project 2 Project 2: Preemption CS 4411 Spring 2017 xkcd.com/1542
Project 2 Administrative Information Project 1 is still being graded results should be ready by beginning of next week. Project 2 will be due Fri 3/3.
Project 2 First Step Fix Project 1 Bugs!!!!
Project 2 Purpose Made a major assumption in Project 1 Threads behave nicely and yield CPU Issues? Selfish Threads Starvation Need the ability to interrupt running threads
Project 2 P2 Overview Three main parts of P2: Receive Clock Interrupts Add Alarms Allow threads to sleep Multilevel Feedback Queue Scheduler
Project 2 Introducing Interrupts Every clock tick the interrupt handler will be called. Allows us to schedule a new thread to be run without relying on nice behavior.
Project 2 Disabling Interrupts For operations that must be atomic Typically when working with shared data structures. E.g. Modifying the cleanup queue. Trivial way of achieving correctness: disable interrupts for everything. Why is this a bad idea?
Project 2 Interrupt Handler - Reminder Just a function that runs when an interrupt occurs. Are there problems if the interrupt handler is interrupted? Yes accessing shared data structures Solution disable interrupt in the interrupt handler CANNOT BLOCK
Project 2 Alarms Alarms = Schedule a function for future execution minithread_sleep() Timeouts Each alarms requires a call back function Call back functions might not be executed by the thread that registered the alarm!
Project 2 Performance Matters! Remember, checking alarms will take place inside your interrupt handler. How long does it take to find an element in your Project 1 queue? We need a different approach. You may add extra functionality to your Project 1 queue
Project 2 Scheduling: FIFO Now lets talk about scheduling Suppose our strategy is FIFO (like in P1) What problems can arise? CPU bound vs IO bound
Project 2 Shortest Job First Suppose our strategy is shortest job first What problems can arise?
Project 2 What we want Goals: - Short jobs added later don t starve due to long jobs added earlier - Long jobs don t get perpetually starved if short jobs keep coming in Also, how do we even know how long a job will take????
Project 2 Introducing the Multi Level Queue! Highest Round Robin Round Robin Round Robin Lowest Round Robin
Project 2 Scheduling Total 80 quanta 1 quanta per thread 0 Total 40 quanta 2 quanta per thread 1 2 Total 24 quanta 4 quanta per thread 3 Total 16 quanta 8 quanta per thread Do we achieve our goals?
Project 2 Scheduling If there are no threads in a given level, schedule threads from the next available level Threads are demoted after using up their time for that level Thread level starts at 0 and can only increase throughout its lifetime.
Project 2 Testing There are a lot of parts to this project Multi-level queue Interrupts Alarms Thread levels Common pitfalls Unnecessarily disabling interrupts Not disabling interrupts when necessary Multi-level queue corner cases
Project 2 Questions Questions?
Project 2 Project 2 FAQ All library calls are safe: interrupts are automatically disabled upon calling interrupts will be restored to its original state (enabled/disabled) after the call. Units of time PERIOD is defined as 50 ms, which is 50000 as a constant. Alarm and wakeup delays are specified in milliseconds. You have to convert units; don t blindly subtract PERIOD. Irregular/random clock interrupts This is normal Be careful of introducing heisenbugs because of your debug statements.
