90 lines
2.8 KiB
Markdown
90 lines
2.8 KiB
Markdown
|
Lecture Topic: Scheduling
|
||
|
|
|
||
|
|
Scheduling Criteria:
|
||
|
|
- CPU Utilization
|
||
|
|
- Throughput
|
||
|
|
- Turnaround Time
|
||
|
|
- Waiting Time: Time spent in ready queue
|
||
|
|
- Response Time
|
||
|
|
|
||
|
|
Multiprocessing Scheduler Design Choices:
|
||
|
|
- One Queue for all processes
|
||
|
|
- A queue per process
|
||
|
|
|
||
|
|
CPU: Homogeneous or heterogenous
|
||
|
|
|
||
|
|
| CPU 0 | CPU 1 |
|
||
|
|
| ----- | ----- |
|
||
|
|
| Cache | Cache |
|
||
|
|
| ISA | ISA |
|
||
|
|
|
||
|
|
Affinity:
|
||
|
|
Soft - May be scheduled on multiple CPUs
|
||
|
|
Hard - Has to be scheduled on a designated CPU
|
||
|
|
|
||
|
|
Load Balancing: Keeping jobs evenly distributed
|
||
|
|
- Job pushing: Jobs may be pushed to another CPU
|
||
|
|
- Job stealing: Unused CPU may steal jobs from the queue
|
||
|
|
|
||
|
|
CPU alternates between computation and input output
|
||
|
|
|
||
|
|
Load stalls minimization
|
||
|
|
A load stall is when the CPU is idle when memory access is being performed
|
||
|
|
|
||
|
|
Instruction reordering
|
||
|
|
The CPU may perform operations out of order to better align with CPU computation and input output cycles, to minimize load stalls
|
||
|
|
|
||
|
|
Hyper threading:
|
||
|
|
|
||
|
|
CPU bursts are most frequently short
|
||
|
|
|
||
|
|
There are different kinds of algorithms that solve a few kinds of problems:
|
||
|
|
- First Come First Serve: When job arrives it immediately gets worked on
|
||
|
|
- Tie Breaker: When two jobs arrive at the same time
|
||
|
|
|
||
|
|
So, P0 comes first, but since we have a tie between P1 and P2. In the first come first serve case:
|
||
|
|
|
||
|
|
| Process | Arrival | Duration | Wait Time | Response Time | Turnaround |
|
||
|
|
| ------- | ------- | -------- | --------- | ------------- | ---------- |
|
||
|
|
| P0 | 0 | 3 | 0 | 0 | 3 |
|
||
|
|
| P1 | 1 | 20 | 2 | 2 | 22 |
|
||
|
|
| P2 | 1 | 5 | 22 | 22 | 27 |
|
||
|
|
|
||
|
|
So the average wait time is
|
||
|
|
(0 + 2 + 22)/3 = 8
|
||
|
|
|
||
|
|
If there are different arrival times:
|
||
|
|
|
||
|
|
| Process | Arrival | Duration | Wait | Turnaround |
|
||
|
|
| ------- | ------- | -------- | ---- | ---------- |
|
||
|
|
| P0 | 0 | 3 | 0 | 3 |
|
||
|
|
| P1 | 2 | 20 | 6 | 26 |
|
||
|
|
| P2 | 1 | 5 | 2 | 7 |
|
||
|
|
|
||
|
|
In this case the average wait time is
|
||
|
|
(0 + 6 + 2)/3 = 2.666666...
|
||
|
|
|
||
|
|
Much better.
|
||
|
|
We can reorder jobs to reduce the wait time for jobs
|
||
|
|
|
||
|
|
The turnaround time also improves (do the calculation in your head dummy)
|
||
|
|
|
||
|
|
The throughput remains the same however
|
||
|
|
|
||
|
|
|
||
|
|
Kinds of algorithms:
|
||
|
|
Shortest Job first
|
||
|
|
|
||
|
|
| Process | Arrival | Duration | Wait Time | Response Time | Turnaround |
|
||
|
|
| ------- | ------- | -------- | --------- | ------------- | ---------- |
|
||
|
|
| P0 | 0 | 9 | | | |
|
||
|
|
| P1 | 1 | 15 | | | |
|
||
|
|
| P2 | 1 | 7 | | | |
|
||
|
|
|
||
|
|
The Gantt Chart
|
||
|
|
|
||
|
|
| | P0 | | P2 | | P3 | |
|
||
|
|
| --- | --- | --- | --- | --- | --- | --- |
|
||
|
|
| 0 | | 9 | | 16 | | 31 |
|
||
|
|
|
||
|
|
The problem with this kind of algorithm is determining the duration of jobs
|