Project 2: Preemption in CS 4411 - Spring 2017
Project 2: Preemption
CS 4411 Spring 2017
xkcd.com/1542
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.
First Step
Fix Project 1 Bugs!!!!
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
…
P2 Overview
Three main parts of P2:
Receive Clock Interrupts
Add Alarms
Allow threads to sleep
Multilevel Feedback Queue Scheduler
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.
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?
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
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!
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
Scheduling: FIFO
Now lets talk about scheduling
Suppose our strategy is FIFO (like in P1)
What problems can arise?
CPU bound vs IO bound
Shortest Job First
Suppose our strategy is shortest job first
What problems can arise?
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????
Introducing the Multi Level Queue!
Highest
Lowest
Scheduling
0
1
2
3
Total 80 quanta – 1 quanta per thread
Total 40 quanta – 2 quanta per thread
Total 24 quanta – 4 quanta per thread
Total 16 quanta – 8 quanta per thread
Do we achieve our goals?
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.
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
Questions?
Questions
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.
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.If you encounter any issues during the download, it is possible that the publisher has removed the file from their server.
You are allowed to download the files provided on this website for personal or commercial use, subject to the condition that they are used lawfully. All files are the property of their respective owners.
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.
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.
