Need help with CPU scheduling algorithms

[BobGoolay]

we have a project due that involves reading in data from a file which is a 30x20 grid consisting of 30 processes each of which have 10 CPU bursts and IO bursts. From this we are supposed to implement FCFS, SJF, RR and a multi-level feedback queue in C++. From this we solve throughput, CPU utilization, Ave. turnaround time, etc. A process goes until an IO burst and then gives way to the next process. This is done til all 30 processes are complete. I completely understand the algorithms for each scheduler, and despite being horrible at coding could do this if the IO bursts werent involved.

My idea, and the one im currently implementing is to send all of the processes into a ready queue at time=0. Add the CPU burst of the first process to the system clock and then send this process into a waiting queue. Here it will wait until the system clock has the IO bursts amount of time added onto it from the next processes CPU burst. Then it will be popped and pushed back onto the ready queue. It's easy for me to say, unfortunately nowhere near that easy to code for me. Any ideas how to make this simpler? Or any FCFS code at all? i cant seem to keep track of all the variables for each process. Sorry if this is overlong or confusing sounding, its my first post ;)

[Chainsaw]

I never know how much help to give on homework problems (CSGAL, Are there guidelines?), but let me give you some juice for the brain to think about organization....

I'm not sure what the acronyms FCFS, SJF, RR, and "multi-level feedback queue" mean, but a scheduler is generally a few queues. Here's where I'd start:

I'd have a queue for processes READY to run and waiting for the CPU. Perhaps the FRONT of that queue is by definition the 'currently running process'.

I'd have another queue for processes currently BLOCKED. This is where processes hang out waiting for their I/O time to elapse.

So, initially all 30 processes are on the READY queue (are they in any particular order? Are there priorities involved?). The FRONT process is 'running' for however long your grid says, and then it is removed from the front of the READY queue and placed at the rear of the BLOCKED queue. Then the newly first process on the READY queue is 'running'.

I guess if it were me, I'd order the BLOCKED queue by the 'time when it should be unblocked' for simplicity, though that isn't a real-world thing (in the real world you wouldn't know how long I/O was going to take). But, heck, school isn't real. :-)

What is on the queues? I'd want the process number, of course, and maybe the time it got onto the queue, maybe some totals (number of delays, total delay time, whatever) so you can do your calculations later.

You didn't specify whether the I/O device all these processes are waiting on is the same device, and so whether if one processes is waiting for the I/O, then the other processes wait in line. If so, you might need some structure that simulates the I/O device (current task using it maybe, when that started or when it should finish).

so, a couple of classes, a couple of structs, "no big deal" :-)

[kc0arf]

Hello,

The guidelines are rather simple: the student needs to show some work and effort, meaning code and talking the problem out. All are welcome to discuss the theory (like you did chainsaw), but we generally do not offer code until the student puts some on paper, and then we can go through it as a group. We strongly discourage someone else posting the answer "working code", as then the student didn't learn.

Bob, what I suggest is your next step is to plot out the code on how you think this should work. You mentioned you understand the algorithms, but do not know how to encode them properly. You might want to consider PsuedoCode

// Bob's Program
 // Date
 
 // This is what my program does
 // Goal is to obtain this
 
 // Here are some Variables that the whole program needs
 
 // This function does one schedule means
 
 // This function does something else
 
 // This is the main part of the program
 // Read in data from disk
 // While !done, do this
 //	   function 1
 //	   function 2

You get the idea. Build out your Outline of the code, and we can go from there.

Christian

[BobGoolay]

/*ill throw out some pseudo code added to what i know for First Come First       Serve Scheduling Algorithms

#include<iostream>
#include<queue>
#include <string>
#include<fstream>
using namespace std;

int CS=10;

struct PCB
{
    int CPUbursts[10];
    int IObursts[10];
    int waitTime;
    int completionTime;
    int arrivalTime;
    int startTime;
    int CPUcount; 
    int IOcount;
};

int main()
{
    int processesDone=0;
    int busyTime=0;
    int CScount=0;
    int systemClock=0;
    int n;
    PCB processes[30];
    queue<PCB> rdyQueue;
    queue<PCB> waitQueue;
    ifstream inData;
    string fileName;

    cout << "Enter the filename: ";
    cin >> fileName;
    cout << endl;

    inData.open(fileName.c_str());

    for(int i=0;i<30;i++)
    {
        for(int j=0;j<10;j++)
        {
                inData>>processes[i].CPUbursts[j];
                inData>>processes[i].IObursts[j];
        }
    }  //enter the bursts into processes 1-30's respective arrays.

    cout<<endl<<"Enter the degree of multiprogramming."<<endl;
    cin>>n;  //the amount of processes the CPU can handle at one time.

    while(processesDone<30)
    {
               //ok here is where im not really sure what to code so ill throw out                 //some ugly pseudocode
               //for(count = 0; count < n; count++)
               //push processes[i] onto rdyqueue.
               //make their arrivalTimes = systemClock;
               //systemClock = processes[0].CPUburst[CPUcount]+10 second                     //context switch;
               //compute all the other numbers and add 1 to the counters, this i                 //know how to do.  make sure to add IOburst[0] to processes[0]                  //wait time.
               //now pop this guy from the rdyQueue and push him onto a                          //waitingQueue.
               //now i know i have to push the next processes onto the ready                    //queue add his burst to the system clock and add the pointers                    //etc.
               //now this is where i get confused, i want to get processes[0]                     //back into the rdyQueue but in order to do that i have to make                   //sure (processes[1].CPUburst+context switch)>=processes[0].                    //wait.  How can i add and subtract two different struct values                    //which are on two different queue data structures? 
*/

[Chainsaw]

Remembering that this is just the way *I* would approach it, I'd have a table of the CPU and IO bursts separate from everything else.

int CPU_Bursts[MAX_PROCESSES][MAX_BURSTS];
int IO_Delays[MAX_PROCESSES][MAX_BURSTS];

(I'm assuming 'bursts' means 'time to spend doing it')

And the records in the queues would contain the process number (0..29) and burst number (0..9) and use those to index into the above arrays when you need to. My thinking is that the data (the arrays) is sort of the 'sample data set' and not really part of the algorithm per se.

It sounds like you want to do a bunch-o-stats gathering, so I think the process record needs to know when it entered the current queue it is on, and then buckets for the total waits and the like. So, for example, the LAST process is on the ready queue, just like all the others, at time 0. It has to wait for all the other CPU bursts on all the other processes before it gets its crack. So, when you go to process that LAST entry, he has been waiting for <current time> - <placed on queue time> clock ticks. Use that for your stats.

Then for the main driver, something like:

put all processes on the rdyQueue.
while not-done,
    if the rdyQueue is not empty,
        add front process' burst time onto the clock 
            (to pretend the burst has elapsed);
        do any other bookkeeping with this process
            (like figure out his delay in waiting for the CPU);
        move this process to the waitQueue if it has more work to do
            (else terminate the process and remove it from the queues)
            (put the current clock time into the process record
             as 'when I entered this queue').
    Similarly, process the waitQueue if it isn't empty
    If both are empty, you are done!

For simplicity, too, it might be easiest to have the process records in an array and just put the POINTERS on the queue, that way you can still iterate the array when all processes are off the queues (when the processes are 'done').

[BobGoolay]

thanks for your help, the idea of making the CPU bursts and IO bursts into double subscripted arrays made keeping track of the variables easier. I wasnt able to figure out everything i needed for the project, but your info helped much. thanks.

[lucier]

i need help in c++ program about the sjf,fcfs and priority algorithms in cpu.....

[Narue]

Please don't resurrect two year old threads.