Lab description:

In this lab youll be writing the implementation for round robin scheduling for a given workload and quantum length. Youll be given a basic skeleton that parses an input file and command line arguments. Youre expected to understand how you would implement round robin if you were to implement it yourself in a kernel (which means doing it in C).

Additional APIs

You may need a doubly linked list for your implement. For this lab you should use TAILQ from sys/queue.h. Use man 3 tailq to see all of the macros you can use. Theres already a list created for you called process_list with a TAILQ entry name of pointers. You should not have to include any more headers or use any additional APIs, besides adding your code.

Starting the lab

The skeleton for Lab 2 is provided with this document on BruinLearn. You should be able to run make in the lab-02 directory to create a rr executable, and then make clean to remove all binary files. There is also an example processes.txt file in your lab directory. The rr executable takes a file path as the first argument, and a quantum length as the second. For example, you can run: ./rr processes.txt 3.

Files to modify

You should only be modifying rr.c and README.md in the lab-02 directory.

Your task

You should only add additional fields to struct process and add your code to main between the comments in the skeleton. You may add functions to call from main if you wish, but calls should only be between the comments. We assume a single time unit is the smallest atomic unit (we cannot split it even smaller). You should ensure your scheduler calculates the total waiting time and total response time to the variables total_waiting_time and total_response_time. The program then outputs the average waiting time and response time for you. Finally, fill in your README.md so that you could use your program without having to use this document.

Errors

All the allocations and input are handled for you, so there should be no need to handle any errors. You may assume integer overflows will not happen with a valid schedule.

Example output

The process.txt file is based on these examples. You should be able run:

> ./rr processes.txt 3

Average waiting time: 7.00

Average response time: 2.75

------------------------------------------------------------------------------------------------------------

rr.c skeleton code looks like below

*** Please make sure only edit the commented parts, I bolded the parts to make sure!!!!

#include #include #include #include #include #include #include #include #include #include

typedef uint32_t u32; typedef int32_t i32;

struct process { u32 pid; u32 arrival_time; u32 burst_time;

TAILQ_ENTRY(process) pointers;

/* Additional fields here */ /* End of "Additional fields here" */ };

TAILQ_HEAD(process_list, process);

u32 next_int(const char **data, const char *data_end) { u32 current = 0; bool started = false; while (*data != data_end) { char c = **data;

if (c < 0x30 || c > 0x39) { if (started) { return current; } } else { if (!started) { current = (c - 0x30); started = true; } else { current *= 10; current += (c - 0x30); } }

++(*data); }

printf("Reached end of file while looking for another integer "); exit(EINVAL); }

u32 next_int_from_c_str(const char *data) { char c; u32 i = 0; u32 current = 0; bool started = false; while ((c = data[i++])) { if (c < 0x30 || c > 0x39) { exit(EINVAL); } if (!started) { current = (c - 0x30); started = true; } else { current *= 10; current += (c - 0x30); } } return current; }

void init_processes(const char *path, struct process **process_data, u32 *process_size) { int fd = open(path, O_RDONLY); if (fd == -1) { int err = errno; perror("open"); exit(err); }

struct stat st; if (fstat(fd, &st) == -1) { int err = errno; perror("stat"); exit(err); }

u32 size = st.st_size; const char *data_start = mmap(NULL, size, PROT_READ, MAP_PRIVATE, fd, 0); if (data_start == MAP_FAILED) { int err = errno; perror("mmap"); exit(err); }

const char *data_end = data_start + size; const char *data = data_start;

*process_size = next_int(&data, data_end);

*process_data = calloc(sizeof(struct process), *process_size); if (*process_data == NULL) { int err = errno; perror("calloc"); exit(err); }

for (u32 i = 0; i < *process_size; ++i) { (*process_data)[i].pid = next_int(&data, data_end); (*process_data)[i].arrival_time = next_int(&data, data_end); (*process_data)[i].burst_time = next_int(&data, data_end); }

munmap((void *)data, size); close(fd); }

int main(int argc, char *argv[]) { if (argc != 3) { return EINVAL; } struct process *data; u32 size; init_processes(argv[1], &data, &size);

u32 quantum_length = next_int_from_c_str(argv[2]);

struct process_list list; TAILQ_INIT(&list);

u32 total_waiting_time = 0; u32 total_response_time = 0;

/* Your code here */ /* End of "Your code here" */

printf("Average waiting time: %.2f ", (float)total_waiting_time / (float)size); printf("Average response time: %.2f ", (float)total_response_time / (float)size);

free(data); return 0; }