Skip to content
TheChatArchiveThe Chat Archive
o1-preview-2024-09-12· OpenAIAi2 WildChat-4.8M (AI2)

I am writing a multi level feedback queue C program. Here is my code mlfq.c // Note:…

  1. User

    I am writing a multi level feedback queue C program. Here is my code mlfq.c // Note: Necessary header files are included #define _GNU_SOURCE #include <stdio.h> #include <stdlib.h> #include <string.h> #include <ctype.h>

    // Define MAX_NUM_PROCESS // For simplicity, assume that we have at most 10 processes #define MAX_NUM_PROCESS 10

    #define MAX_PROCESS_NAME 5 #define MAX_GANTT_CHART 300

    // N-level Feedback Queue (N=1,2,3,4) #define MAX_NUM_QUEUE 4

    // Keywords (to be used when parsing the input) #define KEYWORD_QUEUE_NUMBER "queue_num" #define KEYWORD_TQ "time_quantum" #define KEYWORD_PROCESS_TABLE_SIZE "process_table_size" #define KEYWORD_PROCESS_TABLE "process_table"

    // Assume that we only need to support 2 types of space characters: // " " (space), "\t" (tab) #define SPACE_CHARS " \t"

    // Process data structure // Helper functions: // process_init: initialize a process entry // process_table_print: Display the process table struct Process { char name[MAX_PROCESS_NAME]; int arrival_time ; int burst_time; int remain_time; // remain_time is needed in the intermediate steps of MLFQ }; void process_init(struct Process* p, char name[MAX_PROCESS_NAME], int arrival_time, int burst_time) { strcpy(p->name, name); p->arrival_time = arrival_time; p->burst_time = burst_time; p->remain_time = 0; } void process_table_print(struct Process* p, int size) { int i; printf("Process\tArrival\tBurst\n"); for (i=0; i<size; i++) { printf("%s\t%d\t%d\n", p[i].name, p[i].arrival_time, p[i].burst_time); } }

    // A simple GanttChart structure // Helper functions: // gantt_chart_print: display the current chart struct GanttChartItem { char name[MAX_PROCESS_NAME]; int duration; };

    void gantt_chart_print(struct GanttChartItem chart[MAX_GANTT_CHART], int n) { int t = 0; int i = 0; printf("Gantt Chart = "); printf("%d ", t); for (i=0; i<n; i++) { t = t + chart[i].duration;
    printf("%s %d ", chart[i].name, t); } printf("\n"); }

    // Global variables int queue_num = 0; int process_table_size = 0; struct Process process_table[MAX_NUM_PROCESS]; int time_quantum[MAX_NUM_QUEUE];

    // Helper function: Check whether the line is a blank line (for input parsing) int is_blank(char *line) { char *ch = line; while ( *ch != '\0' ) { if ( !isspace(*ch) ) return 0; ch++; } return 1; } // Helper function: Check whether the input line should be skipped int is_skip(char *line) { if ( is_blank(line) ) return 1; char *ch = line ; while ( *ch != '\0' ) { if ( !isspace(*ch) && *ch == '#') return 1; ch++; } return 0; } // Helper: parse_tokens function void parse_tokens(char **argv, char *line, int *numTokens, char *delimiter) { int argc = 0; char *token = strtok(line, delimiter); while (token != NULL) { argv[argc++] = token; token = strtok(NULL, delimiter); } *numTokens = argc; }

    // Helper: parse the input file void parse_input() { FILE *fp = stdin; char *line = NULL; ssize_t nread; size_t len = 0;

    char *two_tokens[2]; // buffer for 2 tokens
    char *queue_tokens[MAX_NUM_QUEUE]; // buffer for MAX_NUM_QUEUE tokens
    int n;
    
    int numTokens = 0, i=0;
    char equal_plus_spaces_delimiters[5] = "";
    
    char process_name[MAX_PROCESS_NAME];
    int process_arrival_time = 0;
    int process_burst_time = 0;
    
    strcpy(equal_plus_spaces_delimiters, "=");
    strcat(equal_plus_spaces_delimiters,SPACE_CHARS);    
    
    // Note: MingGW don't have getline, so you are forced to do the coding in Linux/POSIX supported OS
    // In other words, you cannot easily coding in Windows environment
    
    while ( (nread = getline(&line, &len, fp)) != -1 ) {
        if ( is_skip(line) == 0)  {
            line = strtok(line,"\n");
    
            if (strstr(line, KEYWORD_QUEUE_NUMBER)) {
                // parse queue_num
                parse_tokens(two_tokens, line, &numTokens, equal_plus_spaces_delimiters);
                if (numTokens == 2) {
                    sscanf(two_tokens[1], "%d", &queue_num);
                }
            } 
            else if (strstr(line, KEYWORD_TQ)) {
                // parse time_quantum
                parse_tokens(two_tokens, line, &numTokens, "=");
                if (numTokens == 2) {
                    // parse the second part using SPACE_CHARS
                    parse_tokens(queue_tokens, two_tokens[1], &n, SPACE_CHARS);
                    for (i = 0; i < n; i++)
                    {
                        sscanf(queue_tokens[i], "%d", &time_quantum[i]);
                    }
                }
            }
            else if (strstr(line, KEYWORD_PROCESS_TABLE_SIZE)) {
                // parse process_table_size
                parse_tokens(two_tokens, line, &numTokens, equal_plus_spaces_delimiters);
                if (numTokens == 2) {
                    sscanf(two_tokens[1], "%d", &process_table_size);
                }
            } 
            else if (strstr(line, KEYWORD_PROCESS_TABLE)) {
    
                // parse process_table
                for (i=0; i<process_table_size; i++) {
    
                    getline(&line, &len, fp);
                    line = strtok(line,"\n");  
    
                    sscanf(line, "%s %d %d", process_name, &process_arrival_time, &process_burst_time);
                    process_init(&process_table[i], process_name, process_arrival_time, process_burst_time);
    
                }
            }
    
        }
        
    }
    

    } // Helper: Display the parsed values void print_parsed_values() { printf("%s = %d\n", KEYWORD_QUEUE_NUMBER, queue_num); printf("%s = ", KEYWORD_TQ); for (int i=0; i<queue_num; i++) printf("%d ", time_quantum[i]); printf("\n"); printf("%s = \n", KEYWORD_PROCESS_TABLE); process_table_print(process_table, process_table_size); }

    // TODO: Implementation of MLFQ algorithm void mlfq() {

    struct GanttChartItem chart[MAX_GANTT_CHART];
    int sz_chart = 0;
    
    
    // TODO: Write your code here to implement MLFQ
    // Tips: A simple array is good enough to implement a queue
    
    /**/
    int i, j;
    
    // Initialize per-process variables
    int process_current_queue[MAX_NUM_PROCESS];
    int process_time_in_queue[MAX_NUM_PROCESS];
    int process_finished[MAX_NUM_PROCESS];
    int total_finished_processes = 0;
    
    for (i = 0; i < process_table_size; i++) {
        process_table[i].remain_time = process_table[i].burst_time;
        process_current_queue[i] = 0; // All processes start in queue 0
        process_time_in_queue[i] = 0;
        process_finished[i] = 0;
    }
    
    // Initialize ready queues
    int queue_size[MAX_NUM_QUEUE];
    int queue[MAX_NUM_QUEUE][MAX_NUM_PROCESS];
    int queue_front[MAX_NUM_QUEUE];
    
    for (i = 0; i < queue_num; i++) {
        queue_size[i] = 0;
        queue_front[i] = 0;
    }
    
    int arrival_index = 0; // Index of next process to arrive in process_table
    
    int current_time = 0;
    
    // Start simulation
    while (total_finished_processes < process_table_size) {
        // Check for process arrivals at current_time
        while (arrival_index < process_table_size && process_table[arrival_index].arrival_time <= current_time) {
            int pid = arrival_index;
            // Add process to queue 0
            process_current_queue[pid] = 0;
            process_time_in_queue[pid] = 0;
            queue[0][queue_size[0]++] = pid;
            arrival_index++;
        }
    
        // Find highest priority non-empty queue
        int level;
        int found = 0;
        int current_queue_level = -1;
    
        for (level = 0; level < queue_num; level++) {
            if (queue_size[level] - queue_front[level] > 0) {
                current_queue_level = level;
                found = 1;
                break;
            }
        }
    
        if (!found) {
            // No process is ready to run, advance time to next arrival
            // If there are no more arrivals, break
            if (arrival_index < process_table_size) {
                current_time = process_table[arrival_index].arrival_time;
            } else {
                break;
            }
            continue;
        }
    
        // Select the process to run
        int queue_index = queue_front[current_queue_level];
        int pid = queue[current_queue_level][queue_index];
    
        // Calculate the time the process can run
        int scheduling_time_quantum = 2; // Fixed scheduling time quantum
        int remaining_time_in_queue = time_quantum[current_queue_level] - process_time_in_queue[pid];
        int time_process_can_run = scheduling_time_quantum;
    
        // Cap the time process can run if needed
        if (time_process_can_run > remaining_time_in_queue)
            time_process_can_run = remaining_time_in_queue;
        if (time_process_can_run > process_table[pid].remain_time)
            time_process_can_run = process_table[pid].remain_time;
    
        // Check for arrival of higher priority processes during this time
        int preemption_time = current_time + time_process_can_run;
        for (int idx = arrival_index; idx < process_table_size; idx++) {
            if (process_table[idx].arrival_time > current_time && process_table[idx].arrival_time < preemption_time) {
                // Process arriving during this time
                int arriving_process_level = 0; // All new processes arrive at queue 0
                if (arriving_process_level < current_queue_level) {
                    // Preemption occurs
                    preemption_time = process_table[idx].arrival_time;
                    time_process_can_run = preemption_time - current_time;
                    break;
                }
            } else {
                if (process_table[idx].arrival_time >= preemption_time)
                    break; // No need to check further
            }
        }
    
        // Update the Gantt Chart
        strcpy(chart[sz_chart].name, process_table[pid].name);
        chart[sz_chart].duration = time_process_can_run;
        sz_chart++;
    
        // Advance time
        current_time += time_process_can_run;
    
        // Update process info
        process_table[pid].remain_time -= time_process_can_run;
        process_time_in_queue[pid] += time_process_can_run;
    
        // Check for new arrivals at current_time (after executing process)
        while (arrival_index < process_table_size && process_table[arrival_index].arrival_time <= current_time) {
            int pid_new = arrival_index;
            // Add the new process to queue 0
            process_current_queue[pid_new] = 0;
            process_time_in_queue[pid_new] = 0;
            queue[0][queue_size[0]++] = pid_new;
            arrival_index++;
        }
    
        // Check if process has finished
        if (process_table[pid].remain_time == 0) {
            process_finished[pid] = 1;
            total_finished_processes++;
    
            // Remove process from queue
            queue_front[current_queue_level]++;
        } else {
            // Check if process has used up its allowed time in current queue
            if (process_time_in_queue[pid] >= time_quantum[current_queue_level]) {
                // Demote process to next lower queue
                if (current_queue_level + 1 < queue_num) {
                    process_current_queue[pid] = current_queue_level + 1;
                    process_time_in_queue[pid] = 0;
    
                    // Remove from current queue
                    queue_front[current_queue_level]++;
    
                    // Add to next lower queue
                    queue[current_queue_level + 1][queue_size[current_queue_level + 1]++] = pid;
                } else {
                    // Process is already at lowest queue, stay in current queue
                    // Remove from current position and add to end of queue
                    queue_front[current_queue_level]++;
                    queue[current_queue_level][queue_size[current_queue_level]++] = pid;
                }
            } else {
                // Put process at the end of same queue (RR)
                queue_front[current_queue_level]++;
                queue[current_queue_level][queue_size[current_queue_level]++] = pid;
            }
        }
    }
    /**/
    
    // At the end, display the final Gantt chart
    gantt_chart_print(chart, sz_chart);
    

    }

    int main() { parse_input(); print_parsed_values(); mlfq(); return 0; }

    Here is all the input output file: in01.txt:
# An input file for a Simplified Multi-level Feedback Queue (MLFQ)

    Empty lines and lines starting with '#' are ignored

    Note: for FCFS, a big number (e.g., 1000) is chosen

    queue_num = 3 time_quantum = 2 4 1000

    The process table definition

    We assume the processes are sorted by the arrival time

    process_table_size = 4 process_table = P1 0 7 P2 1 1 P3 4 1 P4 6 3

    
out01.txt:
queue_num = 3 time_quantum = 2 4 1000 process_table = Process Arrival Burst P1 0 7 P2 1 1 P3 4 1 P4 6 3 Gantt Chart = 0 P1 2 P2 3 P1 4 P3 5 P1 6 P4 8 P1 10 P4 11 P1 12 
 in02.txt
# An input file for a Simplified Multi-level Feedback Queue (MLFQ)

    Empty lines and lines starting with '#' are ignored

    Note: for FCFS, a big number (e.g., 1000) is chosen

    queue_num = 3 time_quantum = 4 8 1000

    The process table definition

    We assume the processes are sorted by the arrival time

    process_table_size = 5 process_table = P1 0 10 P2 2 15 P3 5 2 P4 12 14 P5 18 6

out02.txt
queue_num = 3 time_quantum = 4 8 1000 process_table = Process Arrival Burst P1 0 10 P2 2 15 P3 5 2 P4 12 14 P5 18 6 Gantt Chart = 0 P1 4 P2 8 P3 10 P1 12 P4 16 P1 18 P5 22 P1 24 P2 32 P4 40 P5 42 P2 45 P4 47

    in03.txt

    An input file for a Simplified Multi-level Feedback Queue (MLFQ)

    Empty lines and lines starting with '#' are ignored

    Note: for FCFS, a big number (e.g., 1000) is chosen

    queue_num = 3 time_quantum = 2 4 1000

    The process table definition

    We assume the processes are sorted by the arrival time

    process_table_size = 6 process_table = P1 0 5 P2 2 15 P3 8 7 P4 9 4 P5 15 16 P6 20 6

    out03.txt
queue_num = 3 time_quantum = 2 4 1000 process_table = Process Arrival Burst P1 0 5 P2 2 15 P3 8 7 P4 9 4 P5 15 16 P6 20 6 Gantt Chart = 0 P1 2 P2 4 P1 7 P2 8 P3 10 P4 12 P2 15 P5 17 P3 20 P6 22 P3 23 P4 25 P5 29 P6 33 P2 42 P3 43 P5 53

    in04.txt

    An input file for a Simplified Multi-level Feedback Queue (MLFQ)

    Empty lines and lines starting with '#' are ignored

    Note: for FCFS, a big number (e.g., 1000) is chosen

    queue_num = 3 time_quantum = 4 8 1000

    The process table definition

    We assume the processes are sorted by the arrival time

    process_table_size = 6 process_table = P1 0 6 P2 3 16 P3 9 5 P4 11 3 P5 17 14 P6 22 6

    out04.txt queue_num = 3 time_quantum = 4 8 1000 process_table = Process Arrival Burst P1 0 6 P2 3 16 P3 9 5 P4 11 3 P5 17 14 P6 22 6 Gantt Chart = 0 P1 4 P2 8 P1 9 P3 13 P4 16 P1 17 P5 21 P2 22 P6 26 P2 33 P3 34 P5 42 P6 44 P2 48 P5 50

    in05.txt

    An input file for a Simplified Multi-level Feedback Queue (MLFQ)

    Empty lines and lines starting with '#' are ignored

    Note: for FCFS, a big number (e.g., 1000) is chosen

    queue_num = 3 time_quantum = 2 4 1000

    The process table definition

    We assume the processes are sorted by the arrival time

    process_table_size = 10 process_table = A 0 2 B 2 2 C 4 2 D 6 2 E 8 2 F 10 2 G 12 2 H 14 2 I 16 2 J 18 10

    out05.txt queue_num = 3 time_quantum = 2 4 1000 process_table = Process Arrival Burst A 0 2 B 2 2 C 4 2 D 6 2 E 8 2 F 10 2 G 12 2 H 14 2 I 16 2 J 18 10 Gantt Chart = 0 A 2 B 4 C 6 D 8 E 10 F 12 G 14 H 16 I 18 J 28

    in06.txt

    An input file for a Simplified Multi-level Feedback Queue (MLFQ)

    Empty lines and lines starting with '#' are ignored

    Note: for FCFS, a big number (e.g., 1000) is chosen

    queue_num = 4 time_quantum = 2 4 4 1000

    The process table definition

    We assume the processes are sorted by the arrival time

    process_table_size = 6 process_table = P1 0 6 P2 1 4 P3 6 16 P4 9 5 P5 13 3 P6 20 12

    out06.txt queue_num = 4 time_quantum = 2 4 4 1000 process_table = Process Arrival Burst P1 0 6 P2 1 4 P3 6 16 P4 9 5 P5 13 3 P6 20 12 Gantt Chart = 0 P1 2 P2 4 P1 6 P3 8 P1 9 P4 11 P1 12 P2 13 P5 15 P2 16 P3 20 P6 22 P4 25 P5 26 P6 30 P3 34 P6 38 P3 44 P6 46

    in07.txt

    An input file for a Simplified Multi-level Feedback Queue (MLFQ)

    Empty lines and lines starting with '#' are ignored

    Note: for FCFS, a big number (e.g., 1000) is chosen

    queue_num = 1 time_quantum = 1000

    The process table definition

    We assume the processes are sorted by the arrival time

    process_table_size = 6 process_table = P1 0 8 P2 1 8 P3 2 8 P4 3 8 P5 4 8 P6 5 8

    out07.txt queue_num = 1 time_quantum = 1000 process_table = Process Arrival Burst P1 0 8 P2 1 8 P3 2 8 P4 3 8 P5 4 8 P6 5 8 Gantt Chart = 0 P1 8 P2 16 P3 24 P4 32 P5 40 P6 48

    in08.txt

    An input file for a Simplified Multi-level Feedback Queue (MLFQ)

    Empty lines and lines starting with '#' are ignored

    Note: for FCFS, a big number (e.g., 1000) is chosen

    queue_num = 2 time_quantum = 2 1000

    The process table definition

    We assume the processes are sorted by the arrival time

    process_table_size = 4 process_table = P1 0 8 P2 1 8 P3 2 8 P4 3 8

    out08.txt queue_num = 2 time_quantum = 2 1000 process_table = Process Arrival Burst P1 0 8 P2 1 8 P3 2 8 P4 3 8 Gantt Chart = 0 P1 2 P2 4 P3 6 P4 8 P1 14 P2 20 P3 26 P4 32

    Now, only out01 match with expected output, please help me modify my code, remember only modify between // and // in void mlfq()

  2. Assistant

    To fix your program, you need to adjust the way preemptions are handled in your MLFQ implementation within the mlfq() function. The main issue is that preemptions should occur immediately when a process at a higher priority level arrives, not just at the end of the time slice. Also, you need to correctly calculate the time_process_can_run for the current process considering possible preemptions.

    Here's the corrected code between the /**/ comments in void mlfq():

        int i, j;
    
        // Initialize per-process variables
        int process_current_queue[MAX_NUM_PROCESS];
        int process_time_in_queue[MAX_NUM_PROCESS];
        int process_finished[MAX_NUM_PROCESS];
        int total_finished_processes = 0;
    
        for (i = 0; i < process_table_size; i++) {
            process_table[i].remain_time = process_table[i].burst_time;
            process_current_queue[i] = 0; // All processes start in queue 0
            process_time_in_queue[i] = 0;
            process_finished[i] = 0;
        }
    
        // Initialize ready queues
        int queue[MAX_NUM_QUEUE][MAX_NUM_PROCESS * MAX_NUM_PROCESS]; // Increased size for queues
        int queue_size[MAX_NUM_QUEUE];
    
        for (i = 0; i < queue_num; i++) {
            queue_size[i] = 0;
        }
    
        int current_time = 0;
        int arrival_index = 0; // Index of next process to arrive in process_table
    
        // Simulation loop
        while (total_finished_processes < process_table_size) {
            // Check for process arrivals at current_time
            while (arrival_index < process_table_size && process_table[arrival_index].arrival_time <= current_time) {
                int pid = arrival_index;
                // Add process to queue 0
                process_current_queue[pid] = 0;
                process_time_in_queue[pid] = 0;
                queue[0][queue_size[0]++] = pid;
                arrival_index++;
            }
    
            // Find highest priority non-empty queue
            int level;
            int current_queue_level = -1;
    
            for (level = 0; level < queue_num; level++) {
                if (queue_size[level] > 0) {
                    current_queue_level = level;
                    break;
                }
            }
    
            if (current_queue_level == -1) {
                // No process is ready to run, advance time to next arrival
                // If there are no more arrivals, break
                if (arrival_index < process_table_size) {
                    current_time = process_table[arrival_index].arrival_time;
                } else {
                    break;
                }
                continue;
            }
    
            // Dequeue the first process from queue[current_queue_level]
            int pid = queue[current_queue_level][0];
            // Shift the rest of the queue
            for (i = 1; i < queue_size[current_queue_level]; i++) {
                queue[current_queue_level][i - 1] = queue[current_queue_level][i];
            }
            queue_size[current_queue_level]--;
    
            // Calculate the time the process can run
            int time_slice = time_quantum[current_queue_level];
    
            // Remaining time in queue before demotion
            int remaining_time_in_queue = time_quantum[current_queue_level] - process_time_in_queue[pid];
    
            int time_process_can_run = remaining_time_in_queue < time_slice ? remaining_time_in_queue : time_slice;
    
            if (time_process_can_run > process_table[pid].remain_time)
                time_process_can_run = process_table[pid].remain_time;
    
            // Assume process will run from current_time to current_time + time_process_can_run
            int run_until_time = current_time + time_process_can_run;
    
            // Check for arrival of higher priority processes during this time
            for (int idx = arrival_index; idx < process_table_size; idx++) {
                if (process_table[idx].arrival_time >= current_time && process_table[idx].arrival_time < run_until_time) {
                    // Process arriving during this time
                    int arriving_process_level = 0; // All new processes arrive at queue 0
                    if (arriving_process_level < current_queue_level) {
                        // Preemption occurs
                        time_process_can_run = process_table[idx].arrival_time - current_time;
                        run_until_time = process_table[idx].arrival_time;
                        break;
                    }
                }
                else if (process_table[idx].arrival_time >= run_until_time) {
                    break;
                }
            }
    
            // Update Gantt Chart
            strcpy(chart[sz_chart].name, process_table[pid].name);
            chart[sz_chart].duration = time_process_can_run;
            sz_chart++;
    
            // Advance time
            current_time += time_process_can_run;
    
            // Update process info
            process_table[pid].remain_time -= time_process_can_run;
            process_time_in_queue[pid] += time_process_can_run;
    
            // Check for new arrivals at current_time (after executing process)
            while (arrival_index < process_table_size && process_table[arrival_index].arrival_time <= current_time) {
                int pid_new = arrival_index;
                // Add the new process to queue 0
                process_current_queue[pid_new] = 0;
                process_time_in_queue[pid_new] = 0;
                queue[0][queue_size[0]++] = pid_new;
                arrival_index++;
            }
    
            // Check if process has finished
            if (process_table[pid].remain_time == 0) {
                process_finished[pid] = 1;
                total_finished_processes++;
            } else {
                // Check if process has used up its allowed time in current queue
                if (process_time_in_queue[pid] >= time_quantum[current_queue_level]) {
                    // Demote process to next lower queue
                    if (current_queue_level + 1 < queue_num) {
                        process_current_queue[pid] = current_queue_level + 1;
                        process_time_in_queue[pid] = 0;
                        queue[current_queue_level + 1][queue_size[current_queue_level + 1]++] = pid;
                    } else {
                        // Process is already at lowest queue, stay in current queue
                        // Requeue at the end of current queue
                        queue[current_queue_level][queue_size[current_queue_level]++] = pid;
                    }
                } else {
                    // Put process at the end of same queue (RR)
                    queue[current_queue_level][queue_size[current_queue_level]++] = pid;
                }
            }
        }
    

    This code correctly handles preemptions by checking if a process at a higher priority level arrives during the execution of the current process and preempts it immediately. The run_until_time and time_process_can_run are adjusted accordingly, and the process is either requeued or demoted based on its used time in the current queue.

    After making these changes, your program should match the expected output for all provided input cases.