1
\$\begingroup\$

I wrote a program that implements the Shortest Job First (SJF) scheduling algorithm. The total number of processes is read directly from the standard input, following that for each process to specify the execution time. The average waiting time is also calculated and the order of execution of the processes is displayed.

I had a few implementation issues, including many memory leaks. I solved the problems with the free function to free the memory. Then if I entered a negative character or number, the program would stop working. I solved the problem with do {..} while (n <0);.

My question is what other issues does this implementation hide? Any other bugs. What can I add or remove?

code:

#include <sys/types.h>
#include <sys/wait.h>
#include "lab.h"
void assignValue(int*, int**, int**);
void averages(int*, int**, int**);
void completionTime(int*, int**, int**);
void swap(int*, int*, int*);
void sort(int*, int**, int**);
void shjb(int*, int**, int**, int**);
int main(void)
{
    int numProcesses;
    do
    {
        printf("Total number of processes: ");
        if(scanf("%d", &numProcesses) != 1)
        {
            err_msg("Failed to read integer!");
            exit(1);
        }
    } while (numProcesses < 0);
    
    int* processesNum = (int*)malloc(numProcesses * sizeof(int));
    int* burst = (int*)malloc(numProcesses * sizeof(int));
    int* completion = (int*)malloc(numProcesses * sizeof(int));
    assignValue(&numProcesses, &burst, &processesNum);
    shjb(&numProcesses, &burst, &processesNum, &completion);
    
    free(processesNum);
    free(burst);
    free(completion);
    return 0;
}
void shjb(int *numProcesses, int **burst, int **processesNum, int **completion)
{
    sort(numProcesses, &(*burst), &(*processesNum));
    completionTime(numProcesses, &(*burst), &(*completion));
    averages(numProcesses, &(*burst), &(*completion));    
}
void averages(int *numProcesses, int **burst, int **completion)
{
    double averageTurn = 0;
    double averageWait = 0;
    for(int i=0; i < *numProcesses; i++)
    {
        averageTurn += *(*completion + i);
        averageWait += *(*completion + i) - *(*burst + i);
    }
    printf("\nAverage TurnAroundTime: %.2f", averageTurn / *numProcesses);
    printf("\nAverage WaitingTime: %.2f", averageWait / *numProcesses);
}
void completionTime(int *numProcesses, int **burst, int **completion)
{   
    int temp = *(*burst + 0);
    for(int i=1; i <= *numProcesses; i++)
    {
        *(*completion + (i-1)) = temp;
        temp = temp + *(*burst + i);
    }
    printf("\nCompletion Time: \n");
    for(int i=0; i < *numProcesses; i++)
        printf("%d ", *(*completion + i));
}
void swap(int *v1, int *v2, int *temp)
{
    *temp = *v1;
    *v1 = *v2;
    *v2 = *temp;
}
void sort(int *numProcesses, int **burst, int **processesNum)
{
    int temp;
    for(int i=0;i < *numProcesses; i++)
    {
        for(int j=0;j <= i; j++)
        {
            if(*(*burst + i) < *(*burst + j))
            {
                swap((*burst + i), (*burst + j), &temp);
                swap((*processesNum + i), (*processesNum + j), &temp);
 }
        }
    }
    for(int i=0; i <= *numProcesses; i++)
    {
        for(int j=i+1; j <= *numProcesses - 1; j++)
{
            if(*(*burst + i) == *(*burst + j))
            {
                if(*(*processesNum + i) > *(*processesNum + j))
                {
                    swap((*burst + i), (*burst + j), &temp);
                    swap((*processesNum + i), (*processesNum + j), &temp);
                }
            }                
        }
    }
    printf("\n\nAfter sorting in ascending order");
    
    printf("\nBursts:\n");
    for(int i=0; i < *numProcesses; i++)
        printf("%d ", *(*burst + i));
    
    printf("\nProcesses:\n");
    for(int i=0; i < *numProcesses; i++)
        printf("%d ", *(*processesNum + i));
}
void assignValue(int *numProcesses, int **burst, int **processesNum)
{
    for(int i=0; i < *numProcesses; i++)
    {
        *(*processesNum + i) = i+1;
        do
        {
            printf("Burst time for P[%d]: ", i+1);
            if(scanf("%d", &(*(*burst + i))) != 1)
            {
                err_msg("Failed to read integer!\n");
                exit(1);
            }
        } while (*(*burst + i) < 0);
    }
    printf("\nProcesses ID are: \n");
    for(int i=0; i < *numProcesses; i++)
        printf("%d ", *(*processesNum + i));
    printf("\nBurst times for processes:\n");
    for(int i=0; i< *numProcesses; i++)
        printf("%d ", *(*burst + i));
    printf("\n");
}

lab.h content:

/* Our own header, to be included *after* all standard system headers */

#ifndef __ourhdr_h
#define __ourhdr_h

#include    <sys/types.h>   /* required for some of our prototypes */
#include    <stdio.h>       /* for convenience */
#include    <stdlib.h>      /* for convenience */
#include    <string.h>      /* for convenience */
#include    <unistd.h>      /* for convenience */

#define MAXLINE 4096            /* max line length */

#define FILE_MODE   (S_IRUSR | S_IWUSR | S_IRGRP | S_IROTH)
                    /* default file access permissions for new files */
#define DIR_MODE    (FILE_MODE | S_IXUSR | S_IXGRP | S_IXOTH)
                    /* default permissions for new directories */

typedef void    Sigfunc(int);   /* for signal handlers */

                    /* 4.3BSD Reno <signal.h> doesn't define SIG_ERR */
#if defined(SIG_IGN) && !defined(SIG_ERR)
#define SIG_ERR ((Sigfunc *)-1)
#endif

#define min(a,b)    ((a) < (b) ? (a) : (b))
#define max(a,b)    ((a) > (b) ? (a) : (b))

                    /* prototypes for our own functions */
char    *path_alloc(int *);         /* {Prog pathalloc} */
int      open_max(void);            /* {Prog openmax} */
void     clr_fl(int, int);          /* {Prog setfl} */
void     set_fl(int, int);          /* {Prog setfl} */
void     pr_exit(int);              /* {Prog prexit} */
void     pr_mask(const char *);     /* {Prog prmask} */
Sigfunc *signal_intr(int, Sigfunc *);/* {Prog signal_intr_function} */

int      tty_cbreak(int);           /* {Prog raw} */
int      tty_raw(int);              /* {Prog raw} */
int      tty_reset(int);            /* {Prog raw} */
void     tty_atexit(void);          /* {Prog raw} */
#ifdef  ECHO    /* only if <termios.h> has been included */
struct termios  *tty_termios(void); /* {Prog raw} */
#endif

void     sleep_us(unsigned int);    /* {Ex sleepus} */
ssize_t  readn(int, void *, size_t);/* {Prog readn} */
ssize_t  writen(int, const void *, size_t);/* {Prog writen} */
int      daemon_init(void);         /* {Prog daemoninit} */

int      s_pipe(int *);             /* {Progs svr4_spipe bsd_spipe} */
int      recv_fd(int, ssize_t (*func)(int, const void *, size_t));
                                    /* {Progs recvfd_svr4 recvfd_43bsd} */
int      send_fd(int, int);         /* {Progs sendfd_svr4 sendfd_43bsd} */
int      send_err(int, int, const char *);/* {Prog senderr} */
int      serv_listen(const char *); /* {Progs servlisten_svr4 servlisten_44bsd} */
int      serv_accept(int, uid_t *); /* {Progs servaccept_svr4 servaccept_44bsd} */
int      cli_conn(const char *);    /* {Progs cliconn_svr4 cliconn_44bsd} */
int      buf_args(char *, int (*func)(int, char **));
                                    /* {Prog bufargs} */

int      ptym_open(char *);         /* {Progs ptyopen_svr4 ptyopen_44bsd} */
int      ptys_open(int, char *);    /* {Progs ptyopen_svr4 ptyopen_44bsd} */
#ifdef  TIOCGWINSZ
pid_t    pty_fork(int *, char *, const struct termios *,
                  const struct winsize *);  /* {Prog ptyfork} */
#endif

int     lock_reg(int, int, int, off_t, int, off_t);
                                    /* {Prog lockreg} */
#define read_lock(fd, offset, whence, len) \
            lock_reg(fd, F_SETLK, F_RDLCK, offset, whence, len)
#define readw_lock(fd, offset, whence, len) \
            lock_reg(fd, F_SETLKW, F_RDLCK, offset, whence, len)
#define write_lock(fd, offset, whence, len) \
            lock_reg(fd, F_SETLK, F_WRLCK, offset, whence, len)
#define writew_lock(fd, offset, whence, len) \
            lock_reg(fd, F_SETLKW, F_WRLCK, offset, whence, len)
#define un_lock(fd, offset, whence, len) \
            lock_reg(fd, F_SETLK, F_UNLCK, offset, whence, len)

pid_t   lock_test(int, int, off_t, int, off_t);
                                    /* {Prog locktest} */

#define is_readlock(fd, offset, whence, len) \
            lock_test(fd, F_RDLCK, offset, whence, len)
#define is_writelock(fd, offset, whence, len) \
            lock_test(fd, F_WRLCK, offset, whence, len)

void    err_dump(const char *, ...);    /* {App misc_source} */
void    err_msg(const char *, ...);
void    err_quit(const char *, ...);
void    err_ret(const char *, ...);
void    err_sys(const char *, ...);
void    err_init(const char *);

void    log_msg(const char *, ...);     /* {App misc_source} */
void    log_open(const char *, int, int);
void    log_quit(const char *, ...);
void    log_ret(const char *, ...);
void    log_sys(const char *, ...);

void    TELL_WAIT(void);        /* parent/child from {Sec race_conditions} */
void    TELL_PARENT(pid_t);
void    TELL_CHILD(pid_t);
void    WAIT_PARENT(void);
void    WAIT_CHILD(void);

#endif  /* __ourhdr_h */
```
\$\endgroup\$
0

1 Answer 1

1
\$\begingroup\$

Improvements in your code from my last review of the Round Robin Question:

  1. You are using many functions, this is a major improvement.
  2. The variables are declared as necessary.

The code is not as readble as it was in the first question I answered for 2 reasons, one is the function name shjb(), a better name would shortestJob() or shortestJobFirst(). The other reason is all the pointer arithmetic the code is performing. While you are using allocated memory rather than arrays in this program, within your functions you can treat the allocated memory as arrays and that would make the code more readable. As an example the function assignValue(int* numProcesses, int** burst, int** processesNum) could be re-written as


void assignValue(int numProcesses, int burst[], int processesNum[])
{
    for (int i = 0; i < numProcesses; i++)
    {
        processesNum[i] = i + 1;
        do
        {
            printf("Burst time for P[%d]: ", i + 1);
            if (scanf("%d", &burst[i]) != 1)
            {
                err_msg("Failed to read integer!\n");
                exit(1);
            }
        } while (burst[i] < 0);
    }

    printf("\nProcesses ID are: \n");
    for (int i = 0; i < numProcesses; i++)
        printf("%d ", processesNum[i]);

    printf("\nBurst times for processes:\n");
    for (int i = 0; i < numProcesses; i++)
        printf("%d ", burst[i]);
    printf("\n");
}

Unless you are planning on changing the value of numProcesses it is better to pass it by value rather than by reference, this prevents the number of processes being accidently changed.

The call in main() would then change to


    assignValue(numProcesses, burst, processesNum);

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 unknown behavior (UB).

Possible unknown 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.

Current Code:


    int* processesNum = (int*)malloc(numProcesses * sizeof(int));
    int* burst = (int*)malloc(numProcesses * sizeof(int));
    int* completion = (int*)malloc(numProcesses * sizeof(int));

Code With Error Handling:


    int* processesNum = malloc(numProcesses * sizeof(*processesNum));
    if (processesNum == NULL)
    {
        fprintf(stderr, "Memory allocation for processesNum failed\n");
        return EXIT_FAILURE;
    }

    int* burst = malloc(numProcesses * sizeof(*burst));
    if (burst == NULL)
    {
        fprintf(stderr, "Memory allocation for burst failed\n");
        return EXIT_FAILURE;
    }

    int* completion = malloc(numProcesses * sizeof(*completion));
    if (completion == NULL)
    {
        fprintf(stderr, "Memory allocation for completion failed\n");
        return EXIT_FAILURE;
    }


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.

There is no reason to cast the return value of memory allocation to the proper type, the compiler handles this.

DRY Code

I will repeat the suggestion about DRY code I made:

There is a programming principle called the Don't Repeat Yourself Principle sometimes referred to as DRY code. If you find yourself repeating the same code mutiple times it is better to encapsulate it in a function. If it is possible to loop through the code that can reduce repetition as well.

This code is repeated at twice, so it should be a function:


        if(scanf("%d", &limit) != 1)
        {
            err_msg("Failed to read integer");
            exit(1);
        }

Memory Leaks

Since this program is not expected to keep running for a great length of time memory leaks are not a major issue. If the program was expected to run for hours, days, weeks or months then memory leaks could be an issue, but not in the current implementation. The best way to avoid memory leaks is to do the memory allocation and deletion in the same function as you are currently doing in main().

\$\endgroup\$
2
  • \$\begingroup\$ (There's a copy&paste error in your 3rd allocation failure handling. While a procedure doesn't really suggest itself, a macro should do.) \$\endgroup\$
    – greybeard
    Commented Feb 7, 2022 at 6:22
  • \$\begingroup\$ @greybeard the copy&paste error was burst versus completion, then thanks. It is fixed. My code is definitely violating DRY so I agree with either a function or a macro. \$\endgroup\$
    – pacmaninbw
    Commented Feb 7, 2022 at 14:44

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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