Does a multi cpu system not improve the first come first serve (fcfs) cpu scheduling algorithm?

Question

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.

Answer 1

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.