Operating Systems | Scheduling Algorithms : FCFS

-

First Come First Serve(FCFS)

FCFS algorithm schedules first created process among the processes available on main memory in ready state.

Example: Consider the following timing table of processes and calculate completion time, turn around time and waiting time using FCFS algorithm with the following assumptions. Also find average of turn around time and waiting time.

  • No preemption
  • No I/O request will be there from any process
  • Arrival time is relative to CPU on time

Hint

  • TAT= CT- AT
  • WT= TAT- BT

Process Number AT BT
1 1 4
2 2 3
3 3 1
4 4 2
5 5 5

NOTE: In case of non-preemptive algorithms the Response time and Waiting time are same. But in case of preemptive algorithms since the waiting time may shuffled across turn around time it may be different



Convoy Effect

It is a disadvantage of FCFS algorithm which happens due to arrival of process with longer burst time(BT) before shorter jobs, which leads to a larger average waiting time or starvation.

Consider the following pattern of entry of processes.

Table 1

Process Number AT BT CT TAT WT
P1 0 40 40 40 0
P2 1 4 44 43 39
P3 1 3 47 44 41

Average WT = (0+39+41)/3="80/3"

Table 2

Process Number AT BT CT TAT WT
P1 0 40 40 40 0
P2 1 4 44 43 39
P3 1 3 47 44 41

Average WT = (6+0+4)/3="10/3"

  • Average waiting time of process with similar burst time changes with order of creation of processes.
  • The entry of longest job before shorter jobs increases the average waiting time (Convoy effect).


Context Switching Time

While changing state of a process from ready to run state after calling of scheduler, the scheduler has to call dispatcher and dispatcher should change the context. The time taken for theses sequence of procedure is called context switching time

Example : The following table give the arrival time and burst time of process with a unit context switching time

Process Number AT BT
1 1 3
2 2 3
3 3 1
4 4 4

The timing diagram for the processes listed will be as shown. A unit context switching time will be lapsed before execution of every process by FCFS algorithm scheduling algorithm with no preemption.

Comments

Post a Comment

Popular posts from this blog

Theory of Computation | Symbols, Alphabets, Strings and Language

-
Theory of computation or Automata theory mainly deals with abstract modeling of machines and computation. These models embody some of the important complex logical features we encounter, on dealing software as hardware. The following are the basic terminologies, which are frequently used in Theory of Computation Symbol The smallest building entity of Automata Theory( or Theory of Computation) is known as symbol. example: a, 2, i, B... Alphabet A set of symbols forms an alphabet. An alphabet is usually represented by Greek letter sigma( Σ ) example: Σ= { x, y} String A string is a sequence of symbols in a alphabet. example: 'xy' is a string derived from the alphabet Σ= { x, y} Language Collection of strings are called as a language. example: Let an alphabet Σ= { p, q, r} Then if a language L of set of a strings of length 2 over Σ can be represented as L = { pp, pq, pr, qp, qq, qr, rp, rq, rr } ...
Next »

Operating Systems | Types and Functions

-
Image
An operating system is an interface between user and hardware of a system and it controls allocation of resources and its retrieval. The major functions of operating systems are Dynamic handling of available/allocated/free spaces of memory. Controlling of process state transitions efficiently. Maintaining of consistency in resource access by different processes synchronization methods. incorporation of protection and security in the system. The main objectives of an operating systems to, to provide convenient interface to its users and it should be efficient to process complex scientific data. The fundamental operations of an OS can be described as follows: Synchronization of processes What ever you do on your system is a process. Let us say your sending a request to your printer from a word document when your printe...
Next »

Computer Network | Flow control Methods: Stop and Wait

-
Image
Some times sending data packets at higher rate to a less efficient receiver may cause for the discarding of data from the buffer and lead to data loss. Flow control methods are used to avoid this dilemma. Stop and Wait When the data packet from the sender reaches at the receiver it returns a success message and once the sender acknowledges the success return it will go for the the next one. This sequence of protocols are know as stop and wait method of flow control. In theoretical questions T q and T process usually approximates as zero. Generally Transmission delay for the acknowledgement will be negligibly small (about 10 -3 times) compared to transmission delay for the data,which may also can approximate to zero. Piggybacking is a concept where data is send along with acknowledgment and other control information during bidirectional communication. So in Piggybacking acknowledgement time will become equal to that of propagation transmission time. Cases where T ac...
Next »