CPU scheduling simulator in C

Question

I have the following program that I wrote as an exercise for learning C. It simulates the scheduling of processes according to round-robin, first-come-first-served, shortest-job-first, and priority-scheduling policies. It reads a list of processes from a file, which are represented with the format [id] [cpu burst length] [io burst length] [number of repetitions] [priority].

Here is an example input file:

1 10 3 5 5
2 29 1 5 10
3 3 4 5 15
4 7 2 5 20
5 12 5 5 25

I tried to make it as clean and easy to read as possible. I would appreciate feedback on my style and organization.

#include <stdio.h>
#include <string.h>
#include <stdlib.h>

#define NUM_JOBTYPES 4
#define RR_QUANTUM_LENGTH 10

enum states {
    RTR, CPU, IO, DONE
};

enum algs {
    FCFS, PS, SJF, RR
};

typedef struct job {

    int id;
    int priority;

    int start_time;
    int end_time;
    int wait_time;

    int state;
    int burst_countdown;

    int cpu_burst_length;
    int io_burst_length;

    int quant_countdown;

    int reps;

} job_t;

typedef struct node {
    int priority;
    job_t *job;
    struct node *next;
} node_t;

node_t *rtr_queue;
job_t **jobs;
job_t *active = NULL;

int num_jobs = 0;
int finished_jobs = 0;

int time = 1;
int cpu_busy_time = 0;
int cpu_idle_time = 0;

const char *alg_names[] = {"fcfs", "ps", "sjf", "rr"};
int alg_id = -1;

int iscomment(const char *line);
void load_jobs(FILE *f);
job_t *set_next_job();
void run();
void print_status_line();
void print_report();

void push(node_t **head, job_t *j);
job_t *pop(node_t **);
int getpri(job_t *j);

/*-------------------------------------------------------------*/

int main(int argc, char *argv[]) {

    if (argc != 3) {
        puts("usage: cpu_sim <process filename> <algorithm>");
        return 0;
    }

    for (int i = 0; i < NUM_JOBTYPES; i++) {
        if (!strcmp(argv[2], alg_names[i])) {
            alg_id = i;
        }
    }

    FILE *f = fopen(argv[1], "r");
    load_jobs(f);

    fclose(f);

    if (alg_id != -1) {

        run();
    } else {
        printf("\"%s\" is not a valid algorithm.\n", alg_names[alg_id]);
        return 0;
    }
}

/*-------------------------------------------------------------*/

void run() {

    puts("┌───────────────────────────────┐");
    puts("│   Time   :   CPU   :    IO    │");
    puts("├───────────────────────────────┤");

    for (;;) {

        if (active) {

            --active->burst_countdown;
            --active->quant_countdown;

            // if CPU burst is done, switch to IO
            // and start running a new job.
            if (active->burst_countdown == 0) {
                active->state = IO;
                active->burst_countdown = active->io_burst_length;
                active = set_next_job();
            }

            // else if the current job's quantum is expired, put it
            // at the end of the RTR queue and start the next one.
            else if (active->quant_countdown == 0) {
                active->state = RTR;
                push(&rtr_queue, active);
                active = set_next_job();
            }

            ++cpu_busy_time;

        }

        // if no job is using the CPU, try to pop a new one from the queue.
        // increment the idle time if there is nothing ready to run.
        else {
            if (!(active = set_next_job())) {
                ++cpu_idle_time;
            }
        }

        // now look at the jobs that are not using the CPU.
        for (int i = 0; i < num_jobs; i++) {

            job_t *j = jobs[i];

            if (j->state == IO) {
                // if IO burst is done, put back into RTR queue.
                if (j->burst_countdown-- == 0) {
                    if (j->reps == 0) {
                        j->state = DONE;
                        j->end_time = time;
                        finished_jobs++;
                    } else {
                        j->state = RTR;
                        push(&rtr_queue, j);
                    }
                }
            }

            if (j->state == RTR) {
                ++j->wait_time;
            }
        }

        if(finished_jobs<num_jobs)
            print_status_line();
        else
            break;

        ++time;
    }

    print_report();

    for (int i = 0; i < num_jobs; i++) {
        free(jobs[i]);
    }

    if (rtr_queue) {
        free(rtr_queue);
    }

}

/*-------------------------------------------------------------*/

job_t *set_next_job() {

    job_t *j = NULL;
    if ((j = pop(&rtr_queue))) {

        j->state = CPU;

        if (!j->start_time) {
            j->start_time = time;
        }

        if (j->burst_countdown <= 0) {
            j->burst_countdown = j->cpu_burst_length;
            j->reps--;
        }

        j->quant_countdown = (alg_id == RR ? RR_QUANTUM_LENGTH : -1);
    }
    return j;
}

/*-------------------------------------------------------------*/

void push(node_t **head, job_t *j) {

    node_t *new = malloc(sizeof(node_t));
    new->job = j;
    new->next = NULL;
    new->priority = getpri(j);

    if (*head == NULL) {
        *head = new;
        return;
    }

    if (new->priority < (*head)->priority) {
        new->next = *head;
        *head = new;
        return;
    }

    node_t *cur = *head;

    while (cur->next && new->priority > cur->next->priority) {
        cur = cur->next;
    }

    new->next = cur->next;
    cur->next = new;
}

/*-------------------------------------------------------------*/

job_t *pop(node_t **head) {

    node_t *cur = *head;

    if (!cur) {
        return NULL;
    }

    job_t *j = cur->job;
    *head = (*head)->next;
    free(cur);

    return j;
}

/*-------------------------------------------------------------*/

int getpri(job_t *j) {

    int p = -1;

    if (alg_id == PS) {
        p = j->priority;
    }

    if (alg_id == SJF) {
        p = j->cpu_burst_length * j->reps;
    }

    if (alg_id == RR) {
        p = time;
    }

    return p;
}

/*-------------------------------------------------------------*/

void print_status_line() {

    char *iostring = malloc(16 * sizeof(char));
    int c = 0;

    for (int i = 0; i < num_jobs; i++) {
        if (jobs[i]->state == IO) {
            c += sprintf(&iostring[c], "%d ", jobs[i]->id);
        }
    }

    if (!c) {
        strcpy(iostring, "xx");
    }

    if (active) printf("│  %4d %9d %9s     │\n", time, active->id, iostring);
    else printf("│  %4d %9s %9s     │\n", time, "xx", iostring);

    free(iostring);
}

/*-------------------------------------------------------------*/

void print_report() {

    puts("└───────────────────────────────┘\n");

    int turn_time = 0;

    for (int i = 0; i < num_jobs; i++) {

        printf("   Process ID: %5d\n", jobs[i]->id);
        printf("   Start Time: %5d\n", jobs[i]->start_time);
        printf("   End Time:   %5d\n", jobs[i]->end_time);
        printf("   Wait Time:  %5d\n", jobs[i]->wait_time);

        turn_time += jobs[i]->end_time;
        puts("─────────────────────────────────");
    }

    printf("   Average Turnaround Time: %d\n", turn_time / num_jobs);
    printf("   CPU Busy Time: %d\n", cpu_busy_time);
    printf("   CPU Idle Time: %d\n\n", cpu_idle_time);

}

/*-------------------------------------------------------------*/

void load_jobs(FILE *f) {

    int bufsize = 128;
    char line[bufsize];

    while (fgets(line, bufsize, f)) {

        if (!iscomment(line)) {

            job_t *j = calloc(1, sizeof(job_t));

            sscanf(line, "%d %d %d %d %d",
                   &j->id,
                   &j->cpu_burst_length,
                   &j->io_burst_length,
                   &j->reps,
                   &j->priority);

            push(&rtr_queue, j);
            ++num_jobs;
        }
    }

    jobs = malloc(num_jobs * sizeof(job_t));

    node_t *cur = *&rtr_queue;

    int i = 0;
    while (cur) {
        jobs[i++] = cur->job;
        cur = cur->next;
    }
}

/*-------------------------------------------------------------*/

int iscomment(const char *line) {
    return (line[0] == '/' && line[1] == '/');
}
```

Answer 1

Keep names and enum values in sync

enum algs and alg_names[] are declared quite a bit apart from each other. That makes it hard to spot if they are in sync. It is best to declare the enum and the array with the names right next to each other, and use designated initializers to ensure the compiler will enforce the correct order, like so:

enum algs {
    FCFS, PS, SJF, RR
};

static const char *const alg_names[] = {
    [FCFS] = "fcfs",
    [PS] = "ps",
    [SJF] = "sjf",
    [RR] = "rr",
};

If you have very long lists then you might also consider using macros so you can avoid repetion, see this question for some examples.

Use static where appropriate

Use the static keyword for global variables and functions that are only accessed from within the same source file.

Use more const

Make everything that should not change const. This helps the compiler find accidental errors where you do overwrite a const variable, and allows it to generate more optimal code.

For example, the array alg_names[] as shown above can be made const as well (in your code, only the strings pointed to were marked const, the pointers themselves could still be changed). Another example is getpri(): since it doesn't change the job, you should write:

int getpri(const job_t *j);

Avoid forward declarations

You have a number of forward declarations right before the definition of main(). These are unnecessary; if you change the order in which the functions are defined, you don't need the forward declarations anymore. That removes some repetition from the code, and reduces the potential for mistakes.

Consider moving all global variables into a single struct

There are a lot of variables, and some of them even have names that conflict with standard library functions, such as time. Consider creating a struct state that holds all the variables related to the state of the simulation:

struct state {
    node_t *rtr_queue;
    job_t **jobs;
    job_t *active;
    ...
};

Then you can declare and initialize the state as follows:

struct state state = {
    .active = NULL;
    .num_jobs = 0;
    ...
};

The variable state could be the single global variable left, but you can also consider declaring this variable inside main() instead, and pass a pointer to it to the functions that need to access the state. This is even better, as it will allow you to simulate multiple systems at the same time in a single program.

Missing error checking

Always check the return value of functions that can fail. For example, fopen() can return NULL if the input file does not exist or doesn't have read permissions. If you don't check it, then the program will likely crash due to a segmentation fault. This will be very annoying for the user, who will correctly conclude there is a bug in your program. Instead, check it and print a helpful error message instead:

FILE *f = fopen(argv[1], "r");
if (!f) {
    fprintf(stderr, "Could not open %s: %s\n", arv[1], strerror(errno));
    return 1;
}

There are some helper functions that make this easier, for example the standard function perror() can be used to print an error message, or if you target Linux or *BSD only you could use the even more convenient err().

Also check in load_jobs() that you have read the whole file. To distinguish fgets() from returning NULL because of the end-of-file has been reached or a real error occured, use feof().

Memory allocations can also fail, so check the return value of malloc() and calloc() as well.

Add conditions to the outer for-loop in run()

I would move the condition that you check at the end of the for-loop into the for-statement itself, so it is clear right at the top what is being looped over. So:

for (time = 0; finished_jobs < num_jobs; ++time) {

Now just by looking at that line I can deduce that each iteration will be a time step, and we continue doing steps until all jobs are finished.

Don't free jobs and rtr_queue in run()

These resources were not allocated by run(), so it shouldn't be run()'s job to clean them up. They were allocated by load_jobs(), I would put the resource cleanup in a new function called free_jobs(), and call that function from main().

Avoid repeating type names when allocating memory

Instead of:

node_t *new = malloc(sizeof(node_t));

I recommend you write this instead:

node_t *new = malloc(sizeof(*new));

If you ever change the type of new, you only have to change it in one place. Of course now you have that problem when you change the name of the variable, but then it is more likely to generate a compiler error if you forget to change the right hand side.

Avoid unnecessary allocations

You don't need to use malloc() to allocate memory for iostring in print_status_line(), you can just write:

char iostring[16];

Guard against buffer overflows

Is iostring actually large enough? What if num_jobs is very large, so that the string will be longer than 15 characters? Use snprintf() to guard against buffer overflows:

c += snprintf(&iostring[c], sizeof(iostring) - c, "%d ", jobs[i]->id);

However, be aware that snprintf() can return a value greater than the number of bytes written if it reached the end of the buffer early. It can potentially also return -1. It would be easier to change the format of the report so that you don't need to write to a temporary string. For example:

void print_status_line() {
    if (active)
        printf("│  %4d %9d", time, active->id);
    else
        printf("│  %4d %9s", time, "xx");

    int c = 0;

    for (int i = 0; i < num_jobs; i++) {
        if (jobs[i]->state == IO) {
            c += printf(" %d", jobs[i]->id);
        }
    }    

    if (!c)
        c += printf(" xx");

    printf("%*s|\n", c < 14 ? 14 - c : 0, "");
}

Answer 2

Array length

Explicitly declaring NUM_JOBTYPES 4 and also having alg_names be automatically sized is risky. There are two options, either of which would bring you more consistency:

• Simply declare alg_names[NUM_JOBTYPES]
• Define NUM_JOBTYPES to be equal to the size of alg_names via sizeof

Otherwise, a sleep-deprived future you (for example) could adjust one without adjusting the other, and the compiler would have a more difficult time catching the inconsistency.

Pre-decrement

        --active->burst_countdown;

creeps me out. Based on the C order of operations this does do what you want, but it's a misleading way to write decrement in this case. active->burst_countdown-- accomplishes the same thing but it's more clear that it's the countdown that's being decremented, not the active pointer.

Assignment expressions

You're not doing yourself any favours here:

        if (!(active = set_next_job())) {

Just split this up into two statements.

Early-return

I find p to be unneeded here:

int p = -1;

if (alg_id == PS) {
    p = j->priority;
}

if (alg_id == SJF) {
    p = j->cpu_burst_length * j->reps;
}

if (alg_id == RR) {
    p = time;
}

return p;

This could be rephrased as a switch where every case returns.

Answer 3

Overall Impression

At first glance everything looks great, the indentation is good, the use of enums over Magic numbers is good, the only obvious thing is the comments between functions that look like /*-------------------------------------------------------------*/, they are not useful.

First looks can be deceiving.

Avoid Global Variables

It is very difficult to read, write, debug and maintain programs that use global variables. Global variables can be modified by any function within the program and therefore require each function to be examined before making changes in the code. In C and C++ global variables impact the namespace and they can cause linking errors if they are defined in multiple files. The answers in this stackoverflow question provide a fuller explanation.

Functions such as load_jobs() can return values values such as the pointer to the head of the rtr_queue;

Use Descriptive Variable Names

Variable names using only one letter, such as f or .j don't really help anyone who has to maintain the code to understand the code. In 6 months time, even you might have problems understanding f means file pointer and j mean job or even what cur means.

void load_jobs(FILE* f) {

    int bufsize = 128
    char line[bufsize];

    while (fgets(line, bufsize, f)) {

        if (!iscomment(line)) {

            job_t* j = calloc(1, sizeof(job_t));

            sscanf(line, "%d %d %d %d %d",
                &j->id,
                &j->cpu_burst_length,
                &j->io_burst_length,
                &j->reps,
                &j->priority);

            push(&rtr_queue, j);
            ++num_jobs;
        }
    }

    jobs = malloc(num_jobs * sizeof(job_t));

    node_t* cur = *&rtr_queue;

    int i = 0;
    while (cur) {
        jobs[i++] = cur->job;
        cur = cur->next;
    }
}

It is also very inconsistent with other variable names you are using. It is important to be consistent throughout the program for variable names

Test for Possible Memory Allocation Errors

In modern high level languages such as C++, memory allocation errors throw an exception that the programmer can catch. This is not the case in the C programming language. While it rare in modern computers because there is so much memory, memory allocation can fail, especially if the code is working in a limited memory application such as embedded control systems. In the C programming language when memory allocation fails, the functions malloc(), calloc() and realloc() return NULL. Referencing any memory address through a NULL pointer results in undefined behavior (UB).

Possible undefined behavior in this case can be a memory page error (in Unix this would be call Segmentation Violation), corrupted data in the program and in very old computers it could even cause the computer to reboot (corruption of the stack pointer).

To prevent this unknown behavior a best practice is to always follow the memory allocation statement with a test that the pointer that was returned is not NULL.

Examples of the problem can be found in the load_job() function above.

Example of Current Code with Test:

            job_t* j = calloc(1, sizeof(job_t));
            if (!j)
            {
                fprintf(stderr, "The call to calloc(1, %u) in load_jobs() failed\n", sizeof(*j));
                exit(EXIT_FAILURE);
            }

    jobs = malloc(num_jobs * sizeof(*jobs));
    if (!jobs)
    {
        fprintf(stderr, "The call to malloc(%d, %u) in load_jobs() failed\n", num_jobs, sizeof(*jobs));
        exit(EXIT_FAILURE);
    }

The second example (malloc()) could also be re-written using calloc().

Convention When Using Memory Allocation in C

When using malloc(), calloc() or realloc() in C a common convetion is to sizeof(*PTR) rather sizeof(PTR_TYPE), this make the code easier to maintain and less error prone, since less editing is required if the type of the pointer changes.

            job_t* j = calloc(1, sizeof(job_t));  

Would be better as

            job_t* j = calloc(1, sizeof(*j));  

Avoid Using C++ Keywords as Variable Names

Someone may build this program using a C++ compiler because C++ is backward compatible with C (mostly) or it may be more convient to convert this program to C++ to use the STL and / or Object Oriented classes. The use of C++ keywords such as new can cause problems in these cases. The variable name new also isn't quite as descriptive as newNode or new_node.

void push(node_t** head, job_t* j) {

    node_t* new = malloc(sizeof(node_t));
    new->job = j;
    new->next = NULL;
    new->priority = getpri(j);

    ...
}

This is another location where testing of the result of malloc() should be added.

Lack of Sufficient Error Checking in Main

Malloc is not the only library function used that can fail, the function fopen() will also return a NULL pointer if it fails, and fopen() can fail for a variety of reasons, the file may not be there, the file may not have the proper permissions for the program to open are just 2 possible causes for fopen() to fail. There needs to be a test to see that f has a value here as well.

There is another distinct problem in main(), the array alg_names is being index by -1 in the error case, this causes undefined behavior and will probably not print what is requested. The test for alg_id being negative is too late, it should be performed before the code even attempts to open the input file.

int main(int argc, char* argv[]) {

    if (argc != 3) {
        puts("usage: cpu_sim <process filename> <algorithm>");
        return EXIT_FAILURE;
    }

    for (int i = 0; i < NUM_JOBTYPES; i++) {
        if (!strcmp(argv[2], alg_names[i])) {
            alg_id = i;
        }
    }

    if (alg_id < 0)
    {
        fprintf(stderr, "Invalid argument %s please try one of the following:", argv[2]);
        for (int i = 0; i < NUM_JOBTYPES; i++)
        {
            fprintf(stderr, "%s\n", alg_names[i]);
        }
        return EXIT_FAILURE;

    }

    FILE* f = fopen(argv[1], "r");
    if (!f)
    {
        fprintf(stderr, "Can't open file %s for input.\n", argv[1]);
        return EXIT_FAILURE;
    }
    load_jobs(f);
    fclose(f);

    run();

    return EXIT_SUCCESS;
}