Substance:
- What is Scheduling?
- Why should there be Scheduling?
- What are the scheduling categories?
- What are the alternative scheduling?
- First come, first served (fcfs) or First In, First Out (FIFO)
- Shorted Job First Scheduler (SJF)
- Priority Scheduling
- Multiple Feedback Queue (MFQ)
- Shortest Remaining First (SRF)
- Round Robin Scheduling
- Highest Response Ratio Next (HRN)
- Example of Discussion of Alternative Scheduling Questions.
Scheduling Algorithm
1. What is Scheduling?
In a computer system, scheduling is the arrangement of processor time usage for a number of processes that compete with each other to obtain the required resources.
2. Why should there be scheduling?
- So that every process can be served in a balanced / fair manner.
- So that starvation does not occur.
- To be efficient in the use of processor time
- In order to minimize the occurrence of overhead
- So that response time can be met
- In order to maximize throughput
- To avoid deadlock
3. What are the scheduling categories?
- Long-Term Scheduling, which is the decision to add a process to a group of processes to be executed.
- Medium-Term Scheduling is a decision to add a number of processes (partially or completely) to main memory.
- Short-Term Scheduling is a decision to choose which process will be executed among a number of processes that are ready to be executed.
- I/O scheduling is a decision to choose which process will be given the opportunity to use an I/O device among a number of processes that will all use the I/O device.
4. What are the alternative schedules?
There are several types of alternative scheduling, including:
- First Come First Serve (FCFS)
- Round Robin (RR)
- Shortest Process Next (SPN)
- Shortest Remaining Time (SRT)
- Highest Response Ratio Next (HRRN)
- Feedback (FB)
5. First come, first served (fcfs) or First In, First Out (FIFO)
Has the following characteristics:
- Nonpreemptive scheduling
- Scheduling without priority
- Processes are allocated processing time based on arrival time.
- Once a process gets its share of processing time, the process is executed until completion.
- Average Waiting Time (AWT) is quite large
Example 1
| Nama proses | Saat Tiba | Burst Time |
|-------------|-----------|------------|
| P1 | 0 | 22 |
| P2 | 1 | 4 |
| P3 | 2 | 3 |Gantt Chart
| P1 | P2 | P3 |
|----|----|----|Process Table
- Average waiting time : 45/3 = 15
- Average response time = 74/3 = 24.7
- This will have different results if the arrival time is different.
| Nama Proses | Saat Tiba | Burst Time | Saat Mulai | Saat selesai | Waktu Tunggu | Waktu Tanggap |
|-------------|-----------|------------|------------|--------------|--------------|---------------|
| P1 | 0 | 22 | 0 | 22 | 0 | 22 |
| P2 | 1 | 4 | 22 | 26 | 21 | 25 |
| P3 | 2 | 3 | 26 | 29 | 24 | 27 |
| | | | | | 45 | 74 |Example 2
| Nama proses | Saat Tiba | Burst Time |
|-------------|-----------|------------|
| P1 | 0 | 5 |
| P2 | 2 | 4 |
| P3 | 4 | 3 |Gantt Chart
Process Table
- Average waiting time: 8/3 = 2.6
- Average response time = 20/3 = 6.6
| Nama Proses | Saat Tiba | Burst Time | Saat Mulai | Saat selesai | Waktu Tunggu | Waktu Tanggap |
|-------------|-----------|------------|------------|--------------|--------------|---------------|
| P1 | 0 | 5 | 0 | 5 | 0 | 5 |
| P2 | 2 | 4 | 5 | 9 | 3 | 7 |
| P3 | 4 | 3 | 9 | 12 | 5 | 8 |
| | | | | | 8 | 20 |6. Shorted Job First Scheduler (SJF)
Has the following characteristics:
- The process that has the smallest CPU burst is served first
- Nonpreemptive
- With priority, the basis of priority is the shortness of the process.
7. Priority Scheduling
Has the following characteristics:
- Each process is given a priority and the process with the highest priority will get the processing time first.
- Priorities usually concern issues of time, memory required, number of files that can be opened, comparison of average I/O burst to average CPU burst.
- It can be preemptive or nonpreemptive. If process P1 arrives while p0 is running, then the priority of P1 will be looked at. If P1 > P0 in nonpreemptive, P0 will be completed. In preemptive, P0 will be stopped while the CPU is allocated to P1.
8. Multiple Feedback Queues (MFQ)
Or also called Multiple Queue Scheduling, has the following characteristics:
- Used to prevent excessive swapping with very heavy processes using the processor being given more time at one time.
- Preemptive scheduling (by time)
- Scheduling with priority
- Requires priority classes for existing processes
Applicable provision:
- Run the process at the highest class
- If a process uses all of its allocated quanta then its priority class is lowered.
- The process that enters the system for the first time is immediately given the highest class.
9. Shortest Remaining First (SRF)
Or also called Shortest Remaining Time Preferred, has the following characteristics:
- Preemptive scheduling
- Scheduling with priority
- Priority is based on the shortness of the remaining process, the shorter the remaining process the higher the priority.
Steps in implementing this scheduling:
- Must always pay attention when the process arrives or the process is finished
- The remaining process time of all existing processes at that time is calculated. If there is a process with a remaining process that is shorter than the remaining process in the process being worked on, then on a preemptive basis, the process is stopped and replaced by the process with the shortest remaining process.
10. Round Robin Scheduling
Has the following characteristics:
- Preemptive scheduling, not preempted by another process but by the scheduler based on the length of time the process has been running (preempt by time)
- Scheduling without priority
- All processes are considered important and are given a certain amount of processing time called quanta.
Round robin algorithm conditions:
- If the quantity runs out and the process is not finished, the process is ready and processing is transferred to another process.
- If the quantum has not been exhausted and the process is waiting for an event, then the process becomes blocked and processing is transferred to another process.
- If the quantum is not yet exhausted but the process has finished, then the process is terminated and processing is transferred to another process.
The problem that occurs is in determining the quantity:
- If the quanta is too large it causes a large response time and low turn around time.
- If the quanta is too small it causes too many process switches thus reducing the efficiency of the processor.
11. Highest Response Ratio Next (HRN)
Or also called the Highest Preferred Response Ratio, has the following characteristics:
- Nonpreemptive scheduling
- Scheduling with priority, the basis of priority is the size of the response ratio, the highest response time is served first.
- Once a process gets a processing quota, the process runs until completion.
- Priority is calculated based on the formula
Priority = (waiting time + service time) / service time
Netizens
Q1: EMILDA SUHARTO || Apr 26, 2017, 08:28:00 = please explain HRN, I'm really confused about HRN 