Systems Programming Examination CONFIDENTIAL, INDIVIDUAL, CLOSED BOOK
• You must submit your answer in Canvas. (You can download your home directory from Ed and upload the zip file to Canvas.)
• Please upload all files as individual files to this assignment dropbox
Failure to submit a compilable program for question 1 will limit the maximum mark of that question to 50%
Copyright By PowCoder代写 加微信 powcoder
• You should write your assumption when you are asking for clarification of a question
• Any code which is not C is not considered as compiling code. Makefiles or
scripts are not necessary for this examination.
• All final exam materials are strictly confidential. Do not record or share any
materials from this exam. Penalties apply.
• Permitted references: systems-programming-reference-pages.pdf
Good luck!
• No other material is allowed. Do not seek external assistance of any kind during the examination.
EXAMINATION TIME: 2 hours and 10 minutes (including 10 minutes reading times) SUBMISSION:
Q1. Doubly Linked List
This question is worth 40 marks
A doubly linked list structure is defined as:
struct node {
void *data;
struct node *prev; struct node *next;
Your task is to write C code for the function insert():
struct node *
insert(struct node *head, int index, void *data, struct node **created)
On success, returns the new head of the doubly linked list. After the insertion of the new node, its index in the list should be equal to index. The new node stores the value data in the data field and sets the next and prev pointers as
appropriate. created is a pointer to store the address of the new node.
The following error cases are considered in order:
– When the head of the linked list is NULL, data is non NULL, and index is zero, a
new node is allocated, initialised and returned as the head of the linked list. – If the previous condition was not true, then:
– when the index is greater than the linked list length, or – when head is NULL, or
– when data is NULL, then NULL is returned.
You may write helper functions.
Hint: be careful with forward and back pointers and edge cases
You should not assume anything about the data type, memory size, or memory
location of data.
Restrictions and Hints
– You cannot use any C library functions or any external code, except for malloc()
– There are no sentinel nodes in this linked list. NULL indicates an empty list.
– If you need access to a test case you can find one
here: https://edstem.org/courses/5467/lessons/11459/slides/83012 (Links to an external site.)
This is the only test case offered:
struct node *head = NULL;
void *data = (void*)”some data”; struct node *created = NULL;
head = insert(head, 0, data, &created); assert(head != NULL);
assert(created != NULL); assert(created->data == data);
40 Marks – Full correctness and considering the memory management required
• 20 marks – tested for compilation, and limited automatic marking. Code that does not compile cannot be awarded these marks.
• 20 marks – manual marking will also be done. Comments and other explanations may be awarded partial marks if you are unable to complete the task.
gcc -o dlist -Wall -Werror -Wvla -lm dlist.c
SUBMIT your file dlist.c containing your insert function contained within (NO. Do not include main() function please)
Q2. Plates
This question is worth 60 marks
The dining philosophers problem is about n philosophers sharing two resources left and right chopstick.
We extend this problem where a philosopher will only eat from a clean plate.
A philosopher can only change to the `eating` state if they can acquire all three resources:
– left chopstick, and – right chopstick, and – a clean plate.
There are p plates, where p > 0. A plate has two states: clean and dirty. All p plates are initially clean. When a philosopher is finished eating, the plate becomes dirty.
A washer is another actor in this problem. There are k washers, where 0 < k < 2n. Each washer will be idle or washing. All washers are initially idle.
The washer waits for a `dirty` plate that is not being used. Once they acquire it, they will wash it clean and during this time and it cannot be used by
other philosophers or washers.
Write the code, or the pseudocode, for the modified dining philosophers problem such that there are the maximal number of philosophers eating. Your program
should be deadlock free.
The parameters to this problem are:
- n philosophers, all initially not eating
- p plates, all initially clean
- k washers, all initially idle (not washing)
Write the comments in your code to explain each step how washers and philosophers are synchronising their activities
• no error checking is required for n, p, k. Please focus on the concurrency part of the problem.
• any philosopher finishes eating in a finite, unknown amount of time
• any washer finishes washing in a finite, unknown amount of time
• to design program so that any philosopher may eat at some point, any
washer may wash at some point, no deadlocks, etc
You may use any combination of these locking mechanisms to solve this problem: - barrier,
- semaphore, - mutex
This code is free to use in any way, or you can create your own, or modify this as you please.
#include
#include
// add or modify code to solve the problem… struct philosopher {
bool eating; };
struct washer { bool washing;
struct chopstick {
bool used; };
struct plate {
// clean=1, dirty=0 bool clean;
// add or modify code to solve the problem… pthread_t *philosopher;
pthread_mutex_t *chopstick;
pthread_t *washer; pthread_mutex_t *plate;
struct thread_args { int id, n, p, k;
// original philosophers naive solution
// this code has at least one deadlock
// add or modify code to solve the problem…
void * philosopher_tfunc(void * _args) {
struct thread_args *args = (struct thread_args*)_args;
int id = args->id; // id of philosopher int n = args->n;
int p = args->p;
int k = args->k;
for (;;) {
pthread_mutex_lock( &chopstick[i] ); pthread_mutex_lock( &chopstick[(i + 1) % n] );
printf(“Philosopher %d is eating…\n”, id); pthread_mutex_unlock(&chopstick[i]); pthread_mutex_unlock(&chopstick[(i + 1) % n]);
return 0; }
// add or modify code to solve the problem… void * washer_tfunc(void * _args) {
struct thread_args *args = (struct thread_args*)_args;
int id = args->id; // id of washer int n = args->n;
int p = args->p;
int k = args->k;
return 0; }
// add or modify code to solve the problem… int main(int argc, char **argv) {
if (argc < 4) {
fprintf(stderr, "Usage: ./plates
int n = strtol(argv[1], NULL, 10);
if (EINVAL == errno || ERANGE == errno)
return 2; errno=0;
int p = strtol(argv[2], NULL, 10);
if (EINVAL == errno || ERANGE == errno)
return 2; errno=0;
int k = strtol(argv[3], NULL, 10);
if (EINVAL == errno || ERANGE == errno)
philosopher_count = n; washer_count = n;
struct thread_args *philosopher_args = (struct thread_args *)malloc(sizeof(struct thread_args) * n); struct thread_args *washer_args = (struct thread_args *)malloc(sizeof(struct thread_args) * k);
philosopher = (pthread_t*)malloc(sizeof(pthread_t) * n);
chopstick = (pthread_mutex_t*)malloc(sizeof(pthread_mutex_t) * n);
washer = (pthread_t*)malloc(sizeof(pthread_t) * k);
plate = (pthread_mutex_t*)malloc(sizeof(pthread_mutex_t) * p);
plate_state = (struct plate *)malloc(sizeof(struct plate) * p);
for (i = 0; i < p; ++i)
plate_state[i].clean = 1;
for (i = 0; i < n; ++i) pthread_mutex_init(chopstick + i, NULL);
for (i = 0; i < p; ++i) pthread_mutex_init(plate + i, NULL);
for (i = 0; i < p; ++i) {
washer_args[i].id = i;
washer_args[i].n = n;
washer_args[i].p = p;
washer_args[i].k = k;
pthread_create(washer + i, NULL, washer_tfunc, washer_args+i);
for (i = 0; i < n; ++i) {
philosopher_args[i].id = i;
philosopher_args[i].n = n;
philosopher_args[i].p = p;
philosopher_args[i].k = k;
pthread_create(philosopher + i, NULL, philosopher_tfunc, philosopher_args+i);
return 0; }
Restrictions and Hints
- You may only use pthreads and standard C library functions. You may not use libraries, or other C modules, or code from outside the course contents.
- If you need access to a test case you can find one
here: https://edstem.org/courses/5467/lessons/11459/slides/83012 (Links to an external site.)
This question be manual marked. Despite this if your program compiles you will be able to test for race conditions and deadlock.
Writing pseudocode will limit your maximum grade to 80% for this question. Pseudocode will require similar level of descriptive precision to that of code for full marks.
Any code that does not compile will be assumed to be pseudocode and will be
marked as such.
There are marks for explaining your solution in the code comments
Submission
Your submitted code will be compiled using:
gcc -o plates -Wall -Werror -Wvla -lm -lpthread plates.c
You can make all your own code, or you can start with the following to build upon. Either way, submit your plates.c file.
SUBMIT your file plates.c with all the functions contained within. You should also
include your main() function.
程序代写 CS代考 加微信: powcoder QQ: 1823890830 Email: powcoder@163.com