Thread: When implementing a CPU FCFS algorithm, what does the process do after a I/O Burst?

  1. #1
    Registered User
    Join Date
    Nov 2009
    Posts
    7

    When implementing a CPU FCFS algorithm, what does the process do after a I/O Burst?

    Hi everyone,

    I have searched high and low across google, even throughout my textbook...

    I have this project where you have to design the different types of CPU schedulers and write them in C. If there are three processes (arriving in this order), P1, P2, P3, and each process has a CPU Burst, then an I/O Burst, followed by another CPU Burst, etc, etc...

    My question is in the scenario of a FCFS scheduler:


    So if P1 arrives first, and uses the CPU for 10 seconds during its CPU Burst cycle, and then it has an I/O Burst for 5 seconds, and then it will have another CPU Burst of 15 seconds lets say, I am confused to exactly what occurs.

    As soon as P1 finishes its first CPU Burst, and then has its I/O Burst, the CPU is now free. So would the fcfs scheduler chose the next process, P2 to use the CPU? Or does P1 get to execute until it terminates?

    If P2 uses the CPU while P1 is doing its I/O burst, what happens to P1 when it finishes its I/O Burst? Does it go back to the ready queue, and wait in line all over?

    This is of course assumming that each process is composed of many many many CPU Bursts, and I/O bursts.

    I cannot find any reference to this. Every text and wiki page I read just talks about the "burst". I have kind of got the impression, although extremely indirectly, that when a process is doing an I/O burst, after it finishes this it goes back to the ready queue.

  2. #2
    Registered User
    Join Date
    Oct 2008
    Location
    TX
    Posts
    2,059
    Quote Originally Posted by theonlywalks View Post
    My question is in the scenario of a FCFS scheduler:
    An fcfs scheduler has no notion of context switches so every process executes to completion ie P1 will hog the CPU until it is done with the CPU and I/O.
    Quote Originally Posted by theonlywalks View Post
    So if P1 arrives first, and uses the CPU for 10 seconds during its CPU Burst cycle, and then it has an I/O Burst for 5 seconds, and then it will have another CPU Burst of 15 seconds lets say, I am confused to exactly what occurs.
    P1 will hog the CPU until it is totally done, and then and only then will P2 get it slice of the CPU, and so on and so forth.
    Quote Originally Posted by theonlywalks View Post
    As soon as P1 finishes its first CPU Burst, and then has its I/O Burst, the CPU is now free.
    Nope the CPU is not free because the CPU is actively involved in all I/Os.
    Quote Originally Posted by theonlywalks View Post
    So would the fcfs scheduler chose the next process, P2 to use the CPU? Or does P1 get to execute until it terminates?
    P1 gets to execute and hog the CPU until it terminates. All processes get serviced the same way.
    Quote Originally Posted by theonlywalks View Post
    If P2 uses the CPU while P1 is doing its I/O burst, what happens to P1 when it finishes its I/O Burst? Does it go back to the ready queue, and wait in line all over?
    Iff a context switch happens during an I/O burst, then P1 goes back to the tail of the ready-to-run queue.


    Edit: Some fcfs schedulers do switch from one process to another during the I/O burst and some don't - so you can pick the flavor you want
    Last edited by itCbitC; 03-21-2010 at 10:40 PM.

  3. #3
    Registered User
    Join Date
    Oct 2008
    Location
    TX
    Posts
    2,059
    An fcfs scheduler that switches context during I/O bursts, utilizes the CPU more productively.

  4. #4
    Registered User
    Join Date
    Nov 2009
    Posts
    7
    okay, but one thing i still don't understand, is that isn't the process in a "waiting" state during the I/O Burst?

    Throughout my textbook, and all over the internet, I keep finding this statement everywhere:

    Under non-preemptive scheduling, once the CPU has been allocated to a process, the process keep the CPU until it release the CPU either by terminating or by switching to waiting state.


    So if the process does its CPU Burst, then it needs to display something on the monitor, it sends the appropriate information to the Display Driver Controller, and now the CPU is no longer in use. It has sent the data to the controller, and now it is waiting for some sort of response I am guessing, such as an INT to say it was successful or unsuccessful...

    So if its in the waiting state, even non-premptive processes are still scheduled.

    Some sources say that the CPU is idle while the I/O Burst is completed, and some sources say that the next process in the ready queue gets to utilize the CPU...

  5. #5
    Registered User
    Join Date
    Nov 2009
    Posts
    7
    sorry I didn't see your edit. So I am guessing it can do both, like you said. Is their a special term to tell whether it will do context switches or not? By any chance do you know where you read that information, because I can not find any references anywhere, and when I do my project if I do or don't do context switches I will have a reference.

    I will try and contact my professor to verify, but he may be unavailable until the next class... when it is due. I wish he had been more clear lol

  6. #6
    Registered User
    Join Date
    Nov 2009
    Posts
    7
    I mean like its a 50/50 chance so to speak. Both ways will yield different results, especially when there is multiple processors.

    If there are no context switches, then that would sound like a batch system?

  7. #7
    Registered User
    Join Date
    Oct 2008
    Location
    TX
    Posts
    2,059
    Quote Originally Posted by theonlywalks View Post
    okay, but one thing i still don't understand, is that isn't the process in a "waiting" state during the I/O Burst?
    Yep! the process is blocked during the I/O burst.
    Quote Originally Posted by theonlywalks View Post
    Throughout my textbook, and all over the internet, I keep finding this statement everywhere:

    Under non-preemptive scheduling, once the CPU has been allocated to a process, the process keep the CPU until it release the CPU either by terminating or by switching to waiting state.


    So if the process does its CPU Burst, then it needs to display something on the monitor, it sends the appropriate information to the Display Driver Controller, and now the CPU is no longer in use. It has sent the data to the controller, and now it is waiting for some sort of response I am guessing, such as an INT to say it was successful or unsuccessful...

    So if its in the waiting state, even non-premptive processes are still scheduled.

    Some sources say that the CPU is idle while the I/O Burst is completed, and some sources say that the next process in the ready queue gets to utilize the CPU...
    The job of the scheduler is to ensure that the CPU isn't idling, so when a process that is currently running gets blocked on I/O, the scheduler assigns the CPU to the next process that is at the head of the ready to run queue. The process that was active gets moved to the tail of the ready to run queue. An fcfs scheduler is non-premptive since all tasks have the same priority or no priority at all; and a new task gets scheduled when a process terminates or when it is blocked on something.
    Last edited by itCbitC; 03-23-2010 at 12:26 AM.

  8. #8
    Registered User
    Join Date
    Oct 2008
    Location
    TX
    Posts
    2,059
    Quote Originally Posted by theonlywalks View Post
    sorry I didn't see your edit. So I am guessing it can do both, like you said. Is their a special term to tell whether it will do context switches or not?
    A context switch happens only when a process is blocked because its state needs to be saved somewhere before scheduling the next process at the head of the ready-to-run queue. When a process terminates there is no context switch involved because the scheduler simply puts the next process in line on the CPU.
    Quote Originally Posted by theonlywalks View Post
    By any chance do you know where you read that information, because I can not find any references anywhere, and when I do my project if I do or don't do context switches I will have a reference.
    Give this site a try; and Google with better keywords because it gave me a slew of hits.
    Quote Originally Posted by theonlywalks View Post
    I will try and contact my professor to verify, but he may be unavailable until the next class... when it is due. I wish he had been more clear lol
    Yep! clarification from the professor will be your best bet.

  9. #9
    Registered User
    Join Date
    Oct 2008
    Location
    TX
    Posts
    2,059
    Quote Originally Posted by theonlywalks View Post
    I mean like its a 50/50 chance so to speak. Both ways will yield different results, especially when there is multiple processors.
    There's nothing 50/50 about it. The earliest fcfs schedulers were very primitive and let a task hog the CPU until it terminated. Then came the improvised version where a context switch was performed when a task was blocked and CPU productiveness went up.
    Quote Originally Posted by theonlywalks View Post
    If there are no context switches, then that would sound like a batch system?
    Good question, and one that you should ask the professor as to the kind of scheduler s/he wants you to implement - the primitive or improvised one.

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. implementing an hours counting algorithm
    By droseman in forum C Programming
    Replies: 6
    Last Post: 02-04-2009, 03:59 AM
  2. Almost finished with Round Robin algorithm
    By Shinobi-wan in forum C++ Programming
    Replies: 2
    Last Post: 12-19-2004, 03:00 PM
  3. Binary Search Trees Part III
    By Prelude in forum A Brief History of Cprogramming.com
    Replies: 16
    Last Post: 10-02-2004, 03:00 PM
  4. Request for comments
    By Prelude in forum A Brief History of Cprogramming.com
    Replies: 15
    Last Post: 01-02-2004, 10:33 AM