Loading presentation...

Present Remotely

Send the link below via email or IM

Copy

Present to your audience

Start remote presentation

  • Invited audience members will follow you as you navigate and present
  • People invited to a presentation do not need a Prezi account
  • This link expires 10 minutes after you close the presentation
  • A maximum of 30 users can follow your presentation
  • Learn more about this feature in our knowledge base article

Do you really want to delete this prezi?

Neither you, nor the coeditors you shared it with will be able to recover it again.

DeleteCancel

Make your likes visible on Facebook?

Connect your Facebook account to Prezi and let your likes appear on your timeline.
You can change this under Settings & Account at any time.

No, thanks

Copy of Workflow - Free Prezi Template

Free Prezi template for creating a workflow related presentation. Describe a process and all the necessary steps one has to complete. Download the file from Prezibase.com or save a copy right here
by

Michiko Niña Shibata

on 14 January 2015

Comments (0)

Please log in to add your comment.

Report abuse

Transcript of Copy of Workflow - Free Prezi Template

CPU Scheduling
.
First Come First Serve
Shortest Job First
Priority
Michiko Nina E. Shibata
BSIT-II
PROJECT IN
IT206B

-
amount of time it takes from when a request
was submitted until the first response is produced,
not output (for time-sharing environment)
Scheduling Algorithm Optimization.
CRITERIA OF EFFICIENT PROCESS SCHEDULE
>CPU Process Scheduling
*Arrival Time
*Waiting Time
*Burst Time
*Priority
*Turnaround Time
*Throughput




*First Come First Serve
*Shortest Job First - Preemptive
*Shortest Job First - Non Preemptive
*Priority - Preemptive
*Priority - Non Preemptive
*Round Robin
>Terminology



>Criteria of Efficient Process Schedule
>Kinds of Process Scheduling
CPU PROCESS
SCHEDULING

Non-preemptive scheduling: scheduling occurs only when
a process voluntarily enter the wait state or terminates.
Simple, but very inefficient.
It is the only method that can be used on certain hardware platforms, because it does not require the special hardware(for example, a timer) needed for preemptive scheduling.
Preemptive scheduling: scheduling occurs in all possible cases.
What if the kernel is in its critical section modifying some important data? Mutual exclusion may be violated.
The kernel must pay special attention to this situation and, hence, is more complex.
Types of Scheduling
CPU scheduling deals with the problem of deciding which of the
processes in the ready queue is to be allocated the CPU. There
are many different CPU scheduling algorithms.

The process scheduling is the activity of the process manager that handles the removal of the running process from the CPU and the selection of another process on the basis of a particular strategy.



Why is it important? Because it can have a big effect on resource utilization and the overall performance of the system.

*
Arrival Time
- it is the time which the process arrived.
*
Waiting Time
- the time which the process remains in the ready queue.
*
Burst Time
- the time it estimated to complete(burst) a process or task.
*
Priority
- the right to take precedence or to proceed before others. In terms of scheduling a process, if the number of priority is bigger than
the other processes which arrived in the same time frame, it should be processed first before the other processes.
*
Turnaround Time
- total time between submission of a process and its completion.
*
Throughput
- The total number of processes that completes their execution per time unit.

TERMINOLOGY
*CPU utilization
Scheduling criteria
*Turnaround time –
SCHEDULING CRITERIA
*Response time –
SCHEDULING CRITERIA
-
keep the CPU as busy as possible.
-
number of processes that complete their execution per time unit.
*Throughput –

SCHEDULING CRITERIA
-
amount of time to execute a
particular process.
-
amount of time a process has been
waiting in the ready queue.
*Waiting time –
SCHEDULING CRITERIA
Kinds of Process Scheduling
First come, first served (FCFS) is an operating system process scheduling algorithm and a network routing management mechanism that automatically executes queued requests and processes by the order of their arrival. With first come, first served, what comes first is handled first; the next request in line will be executed once the one before it is complete.

FCFS is also known as first-in, first-out (FIFO) and first come, first choice (FCFC)
First Come First Serve CPU Scheduling Algorithm is the easiest Scheduling Algorithm, it is very easy to understand and implement but its performance is poor because the waiting time is high.
Process Burst Time
P1 10
P2 3
P3 6
P4 10
Samples with Solutions:
Gantt Chart
0 10 13 19 29
P1 P2 P3 P4
WT: P1=0 ; P2=10 ; P3=13 ; P4=19
AWT: (0+10+13+19)/4 = 10.5 ms
ATT: (10+13+19+29)/4 = 17.8 ms
Throughput: 29/4 = 7.3 ms/p
Note: The Gantt Chart should always start at 0.
Process Burst Time
P1 4
P2 20
P3 3
P4 1
P1 P2 P3 P4
0 4 24 27 28
Gantt Chart
Note: The Gantt Chart should always start at 0.
WT: P1=0 ; P2=4 ; P3=24 ; P4=27
AWT: (0+4+24+27)/4 = 13.8 ms
ATT: (4+24+27+28)/4 = 20.8 ms
Throughput: 28/4 = 27 ms/p
Process Burst Time
P1 3
P2 5
P3 2
P4 9
P5 1
P1 P2 P3 P4 P5
0 3 8 10 19 20
Note: The Gantt Chart should always start at 0.
WT: P1=0 ; P2=3 ; P3=8 ; P4=10 ; P5=19
AWT: (0+3+8+10+19)/5 = 8 ms
ATT: (3+8+10+19+20)/5 = 12 ms
Throughput: 20/5 = 4 ms/p
Gantt Chart
Associate with each process and the length of its next CPU burst.
Preemptive: If a new process arrives with CPU burst length less than the remaining time of the currently executing process then switch them. Also known as
Shortest Remaining Time First.
Non-preemptive: once CPU is given the process, it cannot be preempted until it completes this CPU burst.

Shortest Job First minimizes the average waiting time of each process. (Probably optimal if no preemption allowed). However, it has the potential for process starvation for processes which will require a long time to complete if short processes are continually added. Highest response ratio next is similar but provides a solution to this problem.

Another disadvantage of using shortest job next is that the total execution time of a job must be known before execution. While it is not possible to perfectly predict execution time, several methods can be used to estimate the execution time for a job, such as a weighted average of previous execution times.

Process Arrival Time Burst Time
P1
P2
P3
P4
0 2
1 2
4 5
6 7
Non-preemptive
P1 P2 P3 P4
0 2 4 9 16
Gantt Chart
AWT: P1=(0+0) = 0
P2=(2-1) = 1
P3=(4-4) = 0
P4=(9-6) = 3
---
4/4 = 1 ms
ATT: (2+4+9+16)/4 =7.8 ms
Throughput: 16/4 = 4 ms/p
Process Arrival Time Burst Time
P1
P2
P3
P4
0 5
2 3
5 4
6 2
Process Arrival Time Burst Time
P1 P2 P4 P3
0 5 8 10 14
Gantt Chart
AWT: P1=(0-0) = 0
P2=(5-2) = 3
P3=(10-5) = 5
P4=(8-6) = 2
---
10/4 = 2.5 ms
ATT: (5+8+14+10)/4 = 9.3 ms
Throughput: 14/4 = 3.5 ms/p
Gantt Chart
P2 P1 P3 P4 P6 P5
P1
P2
P3
P4
P5
P6
0 5
0 3
5 2
10 6
15 4
15 2

0 3 8 10 16 18 22
AWT: P1=(3-0)= 3
P2=(0-0)= 0
P3=(8-5)= 3
P4=(10-10)= 0
P5=(18-15)= 3
P6=(16-15)= 1
---
10/6 = 1.7 ms
ATT: (8+3+10+16+18+22)/6 = 12.8 ms
Throughput: 22/6 = 3.7 ms/p
Preemptive
Process Arrival Time Burst Time
P1
P2
P3
P4
0 8
5 3
5 2
10 5
Gantt Chart
P1 P3 P1 P2 P4
0 5 7 10 13 18
AWT: P1=(0-0)+(7-5) = 2
P2=(10-5) = 5
P3=(5-5) = 0
P4=(13-10) = 3
---
10/4 = 2.5 ms
ATT: (10+13+7+18)/4 = 12 ms
Throughput: 18/4 = 4.5 ms/p
Process Arrival Time Burst Time
P1
P2
P3
P4
0 4
3 5
7 1
8 2
Gantt Chart
P1 P2 P3 P2 P4
0 4 7 8 10 12
AWT: P1=(0-0)= 0
P2=(4-3)+(8-7)= 2
P3=(7-7)= 0
P4=(10-8)= 2
---
4/4 = 1 ms
ATT:(4+10+8+12)/4 = 8.5 ms
Throughput: 12/4 = 3 ms/p
Process Arrival Time Burst Time
P1
P2
P3
P4
P5
P6
P7
0 8
0 3
4 1
10 1
12 2
12 4
15 3
Gantt Chart
P2 P1 P3 P1 P4 P1 P5 P7 P6
0 3 4 5 10 11 13 15 18 22
AWT: P1=(3-0)+(5-4)+(11-10) = 5
P2=(0-0) = 0
P3=(4-4) = 0
P4=(10-10) = 0
P5=(13-12) = 1
P6=(18-12) = 6
P7=(15-15) = 0
---
12/7 = 1.7 ms
ATT: (13+3+5+11+15+22+18)/7 = 12.3 ms
Throughput: 22/7 = 3.1 ms/p
Round Robin
Round robin is the scheduling algorithm used by the CPU during execution of the process . Round robin is designed specifically for time sharing systems . It is similar to first come first serve scheduling algorithm but the preemption is the added functionality to switch between the processes .





It is also known as
cyclic executive
.
The main advantage of round robin algorithm over first come first serve algorithm is that it is starvation free . Every process will be executed by CPU for fixed interval of time (which is set as time slice ) . So in this way no process left waiting for its turn to be executed by the CPU .

Round robin algorithm is simple and easy to implement . The name round robin comes from the principle known as round robin in which every person takes equal share of something in turn .

Process Arrival Time Burst Time
P1
P2
P3
P4
0 5
2 5
3 3
3 1
Gantt Chart
P1 P2 P3 P4 P1 P2
0 3 6 9 10 12 14
AWT: P1=(0-0)+(10-3)= 7
P2=(3-2)+(12-6)= 7
P3=(6-3)= 3
P4=(9-3)= 6
---
23/4 = 5.8 ms
ATT: (12+14+9+10)/4 = 11.3 ms
Throughput: 14/4 = 3.5 ms/p
Process Arrival Time Burst Time
P1
P2
P3
P4
0 2
0 5
3 1
6 4
P1 P2 P3 P2 P4 P2 P4
Gantt Chart
Quantum: 3 ms
Quantum: 2 ms
0 2 4 5 7 9 10 12
AWT: P1=(0-0) = 0
P2=(2-0)+(5+4)+(9-7) = 5
P3=(4-3) = 1
P4=(7-6)+(10-9)=2
---
8/4 = 2 ms
ATT: (2+10+5+12)/4 = 7.3 ms
Throughput: 12/4 = 3 ms/p
Process Arrival Time Burst Time
0 5
0 4
5 3
10 2
11 5
11 3
P1 P2 P3 P4 P5 P6 P1 P5

Gantt Chart
Quantum: 4 ms
P1
P2
P3
P4
P5
P6
0 4 8 11 13 17 20 21 22
AWT: P1=(0-0)+(20-4) = 16
P2=(4-0) = 4
P3=(8-5) = 3
P4=(11-10) = 1
P5=(13-11)+(21-17) = 6
P6=(17-11) = 6
---
36/6 = 6 ms
Throughput: 22/6 = 3.7 ms/p
ATT: (21+8+11+13+17+20)/6 = 15 ms
Each process is assigned a priority. Process with highest priority is to be executed first and so on. Processes with same priority are executed on first come first serve basis. Priority can be decided based on memory requirements, time requirements or any other resource requirement.

Preemptive scheduling: The preemptive scheduling is prioritized. The highest priority process should always be the process that is currently utilized.

Non-Preemptive scheduling: When a process enters the state of running, the state of that process is not deleted from the scheduler until it finishes its service time.
Advantages: Priority scheduling provides a good mechanism where the relative importance of each process may be precisely defined.

Disadvantages: If high priority processes use up a lot of CPU time, lower priority processes may starve and be postponed indefinitely.The situation where a process never gets scheduled to run is called starvation. Another problem with priority scheduling is deciding which process gets which priority level assigned to it.
Non-preemptive
Process
Arrival
Time
Burst Time
Priority
P1 0 5 1
P2 0 6 2
P3 10 3 4
P4 12 4 3
P2 P1 P3 P4
Gantt Chart
0 6 11 14 18
AWT: P1=(6-0) = 6
P2=(0-0) = 0
P3=(11-10) = 1
P4=(14-12) = 2
---
9/4 = 2.3 ms
ATT: (11+6+14+18)/4 = 12.3 ms
Throughput: 18/4 = 4.5 ms/p
2
1
3
Process
Arrival
Time
Burst Time
Priority
P1 0 3 3
P2 0 5 4
P3 3 4 2
P4 12 6 1
Gantt Chart
P2 P1 P3 P4
0 5 8 12 18
AWT: P1=(5-0) = 5
P2=(0-0) = 0
P3=(8-3) = 5
P4=(12-12) = 0
---
10/4 = 2.5 ms
ATT: (8+5+12+18)/4 = 10.8 ms
Throughput: 18/4 = 4.5 ms/p
Process
Arrival
Time
Burst Time
Priority
P1 0 5 1
P2 0 6 2
P3 10 3 4
P4 12 4 3
Gantt Chart
P2 P4 P6 P3 P5 P1
0 7 11 12 21 23 29
AWT: P1=(29-0) =29
P2=(0-0) = 0
P3=(12-3) = 9
P4=(7-5) = 2
P5=(21-10) = 11
P6=(11-11) = 0
---
51/6 = 8.5 ms
ATT: (29+7+21+11+12)/6 = 13.3 ms
Throughput: 29/6 = 4.8 ms/p
Preemptive
Process Arrival Time Burst Time Priority
P1 0 3 1
P2 0 1 2
P3 3 8 4
P4 5 2 3
P2 P1 P3 P4 P1
0 1 3 11 13 14
Gantt Chart
AWT: P1=(1-0)+(13-3) = 11
P2=(0-0) = 0
P3=(3-3) = 0
P4=(11-5) = 6
---
17/4 = 4.3 ms
ATT: (14+1+11+13)/4 = 9.8 ms
Throughput: 14/4 = 3.5 ms/p
1
2
3
P1 0 7 2
P2 0 5 3
P3 6 3 1
P4 10 4 4
Process Arrival Time Burst Time Priority
P2 P1 P4 P1 P3
Gantt Chart
0 5 10 14 16 19
AWT: P1=(5-0)+(14-10) = 9
P2=(0-0) = 0
P3=(16-6) = 10
P4=(10-10) = 0
---
19/4 = 4.8 ms
ATT: (16+5+19+14)/4 = 13.5 ms
Throughput: 19/4 = 4.8 ms/p
P2 P1 P4 P3
P1 0 7 2
P2 0 3 3
P3 3 12 1
P4 10 4 4
Process Arrival Time Burst Time Priority
Gantt Chart
0 3 10 14 26
Awt: P1=(3-0) = 3
P2=(0-0) = 0
P3=(14-3) = 11
P4=(10-10) = 0
---
14/4 = 3.5 ms
ATT= (10+3+26+14)/4 = 13.3. ms
Throughput: 26/4 = 6.5 ms/p
Full transcript