0
$\begingroup$

I created a program that simulates the fcfs scheduling algorithm. First I implemented it for a single core, then modified it for four homogenoues cpus.

I compared the results with several datasets, and for the most part they are identical.

I understand fcfs is nonpreemtive, so there are no context switches. Then each cpu holds the process until its current cpu burst is finished, from there it either terminates or does IO (goes to wait queue).

Im guessing a multi core system only improves performance if many processes are in the ready queue at the same time, otherwise only one cpu is being used.

Here is the algorithm that I implemented:

while(TRUE)
{
    for(i = 0; i < NUM_CPUS; i++)
    {
        if(!cpu[i].idle)
        {
            if(cpu[i] is finished executing current burst)
            {
                //either move the process from the cpu to the waitQ, or terminate process if finished all bursts
                if(terminatedPrs == numberOfProcess)
                    break;
            }
        }
        if(waitQ->front != NULL)
        {
            //Check if waitQ->front is finished io
            if(waitQ->front finished IO burst)
            {
                //insert waitQ->front to readyQ, then dequeue waitQ 
            }
        }
        if(cpu[i].idle)
        {
            if(readyQ->front != NULL)
            {
                //check if readyQ->front is ready to be executed (that is, arrival time < elapsedTime)
                if(readyQ->front ready to be executed)
                {
                    //move readyQ->front to CPU (begin executing), and dequeue readyQ
                }
            }
        }

    }
    elapsedTime++;
}

Is my algorithm fine? I am getting pretty much the same average waiting time, average turnaround time and average cpu utilization.

$\endgroup$
3
$\begingroup$

Sounds like something's very wrong. My guess is that you are testing with a load that is too small. You should be able to increase the number of processes and at some point the 4-processor system should be able to handle about 4 times as many processes.

Let's try a simple asymptotic analysis:

Suppose we have $N$ processes each of which goes through the following cycle repeatedly (forever):

  1. Wait in the ready queue until a CPU is available.
  2. Run on the CPU for average time $S$.
  3. Request an I/O that takes average time $Z$.
  4. Go back to the ready queue.

What's the minimum average response time $R_{\mathrm{min}}$, for going through this cycle once? $S+Z$. (That's the average time for service at the CPU plus average time for I/O, and no time waiting in the queue.) So

$$ R \geq S+Z. $$

Now Little's Law says that the average response time $R$ is equal to the number of processes in the system, $N$, divided by the system throughput, $X$ (in units of number of times through the entire cycle each second).

$$ R = \frac{N}{X}. $$

What's the maximum throughput this system can achieve. That would happen in the (unrealistic) case that all the processors were busy all the time. There are $P$ processors and each CPU burst consumes average time $S$, so the maximum throughput is $P/S$. That is $X \leq P/S$. So

$$ R \geq \frac{N}{X} = \frac{NS}{P}. $$

That is, when $\frac{NS}{P} \geq S+Z$ you should start to see the average response time increasing linearly as you increase the number of jobs in the system. Below that and you won't see much difference.

$\endgroup$
  • $\begingroup$ I am simulating symmetric multiprocessing, all processes are in a common ready queue. Initially all the processes are in the ready queue, from what I understand the cpu's do not begin executing any of them (even though they are in the ready queue) until the elapsed time equals the process's arrival time. Also, after a process finishes an io burst and goes back to the ready queue, does it go to the back of the ready queue? What if there are still processes in the ready queue that havent executed yet (elapsed time hasnt reached arrival time), wouldnt it be inserted ahead of these? $\endgroup$ – Data Jul 16 '14 at 0:34
  • $\begingroup$ "arrival time" means "time the process arrives at the ready queue." If the process hasn't arrived yet, then it shouldn't be in the ready queue. FCFS means "new arrival gets added at the back of the ready queue, next job served comes off the front of the ready queue." Google "event driven simulation," it sounds like the mechanics of your simulator are getting mixed up with the algorithm you are trying to simulate. They should be completely seperate things. $\endgroup$ – Wandering Logic Jul 16 '14 at 1:29

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.