Shortest-Job-First Scheduling, SJF

  
Shortest-Job-First (SJR) Scheduling

Associate with each process the length of its next CPU burst. Use these lengths to schedule the process with the shortest time.
Two schemes:
1.  non pre- emptive – once CPU given to the process it cannot be preempted until completes its CPU burst.
2. preemptive – if a new process arrives with CPU burst length less than remaining time of current executing
                            process, preempt. This scheme is know as the Shortest-Remaining-Time-First (SRTF).
SJF is optimal – gives minimum average waiting time for a given set of processes.
 
                Process          Arrival Time     Burst Time
                    P1                    0.0                         7
                    P2                    2.0                         4
                    P3                    4.0                         1
                    P4                    5.0                         4
SJF (non-preemptive)
 
P1
P3
P2
P4
0                                  7                               8                         12                                     16
 
Average waiting time = [0 +(8-2)+(7-4) +(12-5)] /4 =4
 
Example of Preemptive SJF
 
Proces                        Arrival  Time               Burst Time
P1                                    0.0                               7
P2                                    2.0                               4
P3                                    4.0                               1
P4                                     5.0                              4
 SJF (preemptive)
 
P1
P2
P3
P2
P4
P1
0                   2                       4                     5                         7                      11               16
 
         Average waiting time = (9 + 1 + 0 +2)/4 =3
       Determining Length of Next CPU Burst
 
Can only estimate the length.
Can be done by using the length of previous CPU bursts, using exponential averaging.
 
Prediction of the Length of the Next CPU Burst
             Pn+1 = a tn +(1-a)Pn 
             This formula defines an exponential average
              Pn stores the past history
              tn contents are most recent information
              the parameter “a “controls the relative weight of recent  and past history of  in our prediction
              If a =0 then Pn +1 =Pn
             That is prediction is constant
              If a = 1 then Pn +1 = tn

              Prediction is last cpu burst

Comments

Post a Comment

Popular posts from this blog

Classification of Data-Delivery Mechanisms in mobile computing

Image
Data Dissemination and Broadcasting Systems: Classification of Data-Delivery Mechanisms: ·          Push-based mechanisms (publish–subscribe mode) ·          Pull-based mechanisms (on-demand mode) ·          Hybrid mechanisms (hybrid mod                        Push-based Mechanisms: ·          Server pushes data records from a set of distributed computing systems ·          Examples of distributed computing systems advertisers or generators of traffic congestion, weather reports, stock quotes, and news report A server or computing system pushing the data records from a set of distributed systems : Publish–subscribe mode • In which the data pushed as per the subscription for a push service by a user Pushing Algorithm: Select a structure of data records to be pushed • An algorithm provides an adaptable multi-level mechanism that permits data items to be pushed uniformly or none uniformly after structuring them according to their relative impor
Read more

Client Server Computing with Adaptation

Image
Client Server Computing with Adaptation • Two adapters (adaptation software) at a mobile device • An adapter for standard data format for synchronization at the mobile-device • Another adapter for the backend database copy, which is in a different data format for the API at the mobile-device Adaptation: Software to get data in one format or data governed by one protocol and convert it to another format or to data governed by another protocol ·          Used for interchange between standard data formats and data formats for the API ·          IBM WebSphere Everyplace Access (WEA) provides adapters for synchronization objects (for example, XML format synchronization objects) and the objects of API databases (for example, for the PIM APIs)
Read more

Data Dissemination Broadcast-disk Models

Image
Data Dissemination Broadcast-disk Models: ·          Presumed that all the n records to be broadcast are stored on a circular disk from 0° to 360° ·          A hypothetical disk revolves and the angle changes from 0°to 360° ·          The entire N bits in n records get pushed through a hypothetical reading-head over the disk. ·          The head continuously reads each bit of a record just beneath it and broadcasts it instantaneously on the wireless network ·          During next revolution each bit in the records positioned from 0° to 360° broadcast once again in the same sequence as in earlier revolution Number of adaptations and algorithms for broadcast: 1. Circular Multi-disk Model 2. Flat Disk Model 3. Multi-disk Model with repetition rate proportional to priority 4. Skewed disk model Circular multi-disk model • Each block of records pushed with a repetition rate proportional to its hierarchical level Each rotating disk cycle:
Read more