Systems Programming Examination
Hello, dear friend, you can consult us at any time if you have any questions, add WeChat: daixieit
Systems Programming Examination
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); |
Marking
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
Assume
• 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
#include
#include
#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] );
#include
#include
#include
#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;
};
|
2022-05-21