CPU Scheduling
26 important questions on CPU Scheduling
How is the maximum CPU utilisation obtained?
-> the CPU switches from one process to another (because we cannot wait for one process to end before we start another)
-> an I/O can tell the processor when to switch to another program
There are 2 types of burst cycles within the CPU - what are they?
- used to execute a process
2. I/O burst
- when the CPU is waiting for the I/O request to complete
- the CPU will switch between CPU burst and I/O burst
What does the short-term scheduler (CPU scheduler) do?
- Higher grades + faster learning
- Never study anything twice
- 100% sure, 100% understanding
For my 1st exam I got a C. Then, I started looking for ways to learn better and I came across Study Smart. Since then I have scored a A+, A, A- and another A. I highly recommend it to everyone who wants to hear it. I am so happy with it!!
I was struggling to finish all my first-year subjects for 3 years. Then I discovered Study Smart, which helped me to finish all of them within 3 months.
Because of StudySmart, things are going well in many ways. Before, I always had study stress and no time for anything. Now I feel calm and confident (because of the program). I used to score a B, now I usually score an A or A+.
Hey Chris, I really want to thank you very much for developing the platform, I usually got around C for my exams, now I scored an A+, an A and a A- !!
Since using Study Smart, my average has increased significantly. I even completed a statistics course with a A+ while I'm bad at statistics. I took on extra courses this year, because of Study Smart. Thanks so much!
Ever since I started studying with StudySmart I passed all my exams !!! No more re-sits!! At first, I was happy with a pass and now I only get good grades. Many thanks!
I aced all the courses I studied with Study Smart. For law, I first scored a D, and now an A! I’m 100% sure that I’ll pass all the courses I study with Study Smart.
I always thought I studied well. My grades were fine. I could never have imagined that applying these study skills would have such a huge and direct impact on my grades, my speed and the pleasure I have in learning.
For the first time, I finally feel totally confident about the way I learn. I have the perfect overview and make great progress in terms of speed and the grades I get. Thanks, Chris!
I immediately started to enjoy learning again, and my grades soared. All of a sudden, everything went better. I highly recommend Study Smart to all students..
Being able to create my materials online made the process of studying so much smoother and quicker. I no longer have to spend a huge amount of my time on creating my summaries.
At first, my notes were a mess. Now I use Study Smart to take my notes in a perfectly structured way. It helps me to save a lot of time and do other things I enjoy.
Students that study with Study Smart get better grades. The system applies all the learning methods in such a way that both well-performing students and students who struggle perform much better.
Hi Chris, I would like to thank you very much. Last year I scored C on a course, and this year I got an A+ thanks to your method! Thank you very much!
The largest effect is that my child is more enthusiastic about school! Every parent wants their children to be happy at school, Study Smart made it happen.
In high school, I failed several exams, and that has really changed now. I actually needed this tool very much back then. Since I started studying with StudySmart, I haven't had any D's. My average score is now an A and those are results I would have never had in the past
With my old method, I passed only 3 out of 8 courses. Since I started taking my notes digitally in Study Smart, I have passed all my courses on the first try. For me, StudySmart takes away the stress of wondering if I will pass or not.
Thanks to StudySmart, I passed all my exams, and with better grades than before! On top of that, I have mastered a very good study method now, which I am confident will help me earn my degree.
When may CPU scheduling decisions take place?
2. Switches from running to ready state (preemptive)
3. Switches from waiting to ready (preemptive)
4. Terminates (nonpreemptive)
Nonpreemptive -> one the CPU has been allocated to a process, the process will be using the CPU until it releases it
Preemptive
- they can be interrupted
- the CPU can switch from one to another
e.g. accessing shared data
What is dispatch latency?
What are the scheduling criteria?
- CPU utilisation - keep the CPU as busy as possible
- Throughput - number of processes that complete their execution per time unit
- Turnaround time - amount of time to execute a particular process
- Waiting time - amount of time a process has been waiting in the ready queue
- Response time - amount of time it takes from when a request was submitted until the first response is produced, not output (for time-sharing environment)
What is the criteria for the optimum scheduling algorithm? Which one is typically used to compare algorithms?
- max CPU utilisation - (40-90% - if 100% the CPU will get too hot and there will be a hardware failure)
- max throughput
- min turnaround time
- min waiting time
- min response time
Average waiting time is used to compare algorithms
What is the CPU burst?
i.e. the time the process takes to complete
What is First-Come, First-Served (FCFS) Scheduling?
- non-preemptive i.e. when a process begins executing, it won't be interrupted until it terminates itself or if it is stopped by an i/o request
What is the problem with the FCFC scheduling algorithm?
We have the convoy effect
What is the convoy effect?
What is the Shortest-Job-First (SJF) scheduling algorithm?
- Associates with each process the length of its next CPU burst
- SJF is optimal - it gives minimum average waiting time for a given set of processes
The difficulty is knowing the length of the next CPU request before its executuion
How does the SJF determine the length of the next CPU burst?
This can be done using exponential averaging
- takes the measured length of previous CPU bursts
IMPORTANT - the result is not 100% accurate but it gives a good approximation of any cpu burst
What is the preemptive version of the SJF algorithm?
We add the arrival times and preemption (i.e. it can be interrupted)
- if a process will take a shorter time (calculated by exponential averaging), then it will interrupt the process currently executing. If the process is longer than the process currently executing, it will not interrupt
What is the priority scheduling algorithm?
- The CPU is allocated to the process with the highest priority number
- Can run in preemptive and nonpreemptive modes
How does priority scheduling compare to SJF?
What is the problem with priority scheduling? What is the solution?
Solution:
- Ageing - as time progresses increase the priority of the process
What is the round robin algorithm?
i.e. each process will get the same time quantum to execute
- after this time, the process is preempted and added to the end of the ready queue
- The timer interrupts every quantum schedule next process
What is the problem with round robin?
- If the q is small, q must be large with respect to context switch, otherwise overhead is too high
i.e. if q is too small compared to the overhead, there will be high overhead
How does the RR algorithm compare to SJF?
What happens when the q is too small?
- this will add up to produce a lot of overhead
What is the multilevel feedback queue
- therefore the multilevel feedback queue fights against starvation
What is a disadvantage with multilevel feedback queue?
How does scheduling happen in a multi-processor system?
- Homogeneous processors within a multiprocessor
1. Asymmetric multiprocessing --> among all the processors, only one processor (the master) accesses the system data structures, alleviating the need for data sharing. The rest of the processors are slaves - only used for executing the processes
2. Symmetric multiprocessing (SMP) - this is the most common
- each processor is completely independent/self-scheduling, each has its own private queue of ready processes
What is the problem with SMP?
- THIS IS THE SAME AS THE CRITICAL SECTION PROBLEM
- so which processor to pick for the execution as a synchronisation problem
How is scheduling done in the Windows OS?
■ The scheduler is called Dispatcher in Windows
■ Windows uses priority-based preemptive scheduling i.e. each thread is given a number which defines its priority -> Highest-priority thread runs next
■ Thread runs until (1) blocks, (2) uses time slice, (3) preempted by higher-priority thread
■ 32-level priority scheme which is divided into a Variable class (those with priority1-15), and a real-time class (16-31)
■ Priority 0 is memory-management thread
■ Queue for each priority
■ If no run-able thread, runs idle thread
The question on the page originate from the summary of the following study material:
- A unique study and practice tool
- Never study anything twice again
- Get the grades you hope for
- 100% sure, 100% understanding
