CS2850: Operating Systems

CS2850R: Operating Systems – PAPER FOR FIRST SITS/RESIT

CANDIDATES

Time allowed: THREE hours (including upload time)

• Please answer ALL questions.

• Handwrite your answers on paper, and write the module number and your candi-
date number at the top of each page. Photograph/scan the pages and keep the
original paper versions, as they may be required by the examiners.

• For each question you attempt, please clearly state the question number.

• Please do not include your name or Student ID Number anywhere on your work.

• Academic Misconduct: We will check all assignments for academic miscon-

duct. Suspected offences will be dealt with under the College’s formal Academic
Misconduct procedures. Please remember:

– The work submitted is expected to be your own work and only your work.
You may not ask for help with the assessments from any source, or copy
anyone else’s work.
– You must not give help to anyone else, including sending them any parts of
the questions or copies of your solutions, even after the 23-hour time period
has finished.

2019/20 Page 1 of 10 NEXT PAGE

 CS2850/CS2850R

• Submitting your work:

– Your document must be submitted through Moodle using the submission link
in the module Moodle page. If possible please convert your document into
a PDF document before submitting to make the upload process quicker and
easier.
– If you run into technical difficulties with uploading, email
EPMS-AAquery@rhul.ac.uk

If you have any questions in relation to completing the assessment or if you have any
difficulty completing this assessment on time please e-mail us at
EPMS-AAquery@rhul.ac.uk

Page 2 of 10 NEXT PAGE

 CS2850/CS2850R

1. (a) What is the difference between the kernel and user CPU execution modes?
[3 marks]
(b) In a mainframe system without multiprogramming (i.e., programs cannot be
run concurrently), consider three tasks A, B and C. Suppose that their esti-
mated running times are:

running time (minutes)

A 12
B 3
C 6

Give the turnaround times for each of these tasks and the average turnaround
time in the context of the following batch system scheduling strategies, mak-
ing sure to show all your working.
i. First-Come, First-Served (FCFS), assuming the order A, B, C. [5 marks]
ii. Shortest Job First (SJF). [5 marks]
(c) The Best Fit memory management algorithm tends to leave small unused
regions of memory that are often not usable for memory allocation requests.
How could you adapt this algorithm to improve this, without changing its main
approach? [4 marks]
(d) Consider the concurrent program that consists of the following two pro-
cesses that share the variable x:
P1: x = 9; P2: x = 11;
if(x > 10) if(x < 10)
x = x - 3; x = x * 2;
How many different values may the variable x have when the program termi-
nates? Give a possible execution sequence for each case. [8 marks]

Page 3 of 10 NEXT PAGE

 CS2850/CS2850R

2. (a) There are four properties that are required for any correct algorithm to solve
the mutual exclusion problem. Explain the importance of the property “No
process running outside its critical region may block any process.” in this
context. [4 marks]
(b) Consider the following proposed solution to the mutual exclusion problem for
a number of threads that share the same code, where variable x is initially
set to 0:
while(1) {
if(x == 0) {
x = 1;
critical_region();
non_critical_region();
x = 0;
}
}
This proposed solution fails the most basic rule of mutual exclusion as it
allows multiple threads to execute their critical regions simultaneously.

i. Explain how this code also does not meet one other condition required
to solve the mutual exclusion problem. [5 marks]
ii. Give one example of execution order that shows the above algorithm
does not fully comply with the property you mentioned in i. [4 marks]
iii. What could be gained with a revised version of this program using a
semaphore? [4 marks]
iv. Could the barrier synchronisation mechanism be used to achieve mutual
exclusion in the above program, instead of introducing a semaphore?
Justify your answer. [4 marks]
(c) Describe how the Test and Set Lock (TSL) instruction works, and how it can
be used to correctly implement mutual exclusion. [4 marks]

Page 4 of 10 NEXT PAGE

 CS2850/CS2850R

3. (a) What is an i-node in the context of file systems? Explain what is gained by
using i-nodes instead of a file allocation table (FAT). [6 marks]
(b) In the context of deadlock avoidance algorithms:
i. Give one example of a safe state and one example of an unsafe state
under the following context:
• four processes are active and each of these needs to use at least
one resource from the system (for each state, you decide how many
resources each process is holding and the maximum each will need);
• only one type of resource exists, with seven resources available in
the system in total.
Represent the examples in tables. Each row should show the informa-
tion for a process. The columns should show the number of resources
held, and the maximum number of resources simultaneously required
by each process.
In addition, for each example, demonstrate why it is a safe/unsafe state.
[8 marks]
ii. Give an example of why it is difficult to use the Banker’s algorithm for
multiple resources in a real system, based on the structures it requires.
[5 marks]
(c) In the context of virtualisation, hypervisors should score well in three dimen-
sions: safety, fidelity and efficiency. Discuss why all three are important.
[6 marks]

Page 5 of 10 NEXT PAGE

 CS2850/CS2850R

4. (a) Consider the following C code:

#include <stdio.h>
#include <unistd.h>
#include <sys/wait.h>

int main(int argc, char *argv[]) {

FILE *f = fopen("foo.txt", "w");

int i = 0;

int i1 = 2;
int i2 = 1;

if (fork() == 0) {
sleep(i1);
i = i * 2;
fprintf(f, "i = %d\n", i);
fclose(f);
return 0;
}
else{
i = i + 2;
sleep(i2);
fprintf(f, "i = %d\n", i);
fclose(f);
}
wait(NULL);
printf("i = %d\n", i);
return 0;
}
i. The program writes
i = 2
on stdout and
i = 2
i = 0
on file foo.txt. Explain why, if you replace
if (fork() == 0){
...

Page 6 of 10 NEXT PAGE

 CS2850/CS2850R

i = i * 2;
...
}
with
if (fork() == 0){
...
i = (i + 1) * 2;
...
}
the output of the program on stdout remains the same while the output
on file foo.txt becomes
i = 2
i = 2
[3 marks]
ii. Go back to the original version of the code. Explain why, if you replace
int i1 = 2;
int i2 = 1;
with
int i1 = 1;
int i2 = 2;
the program writes
i = 2
on stdout and
i = 0
i = 2
on file foo.txt. [3 marks]
iii. Go back once again to the original version of the code. Explain why, if
you remove return 0; in if (fork() == 0){ ... }, the program writes
i = 0
i = 2
on stdout and
i = 0
i = 2
on file foo.txt. [2 marks]

Page 7 of 10 NEXT PAGE

 CS2850/CS2850R

(b) Consider the following C code:

#include <stdlib.h>
#include <stdio.h>
#include <string.h>
struct node{
int val;
struct node *next;
};
void insertNode(struct node **t, int v){
if (*t == NULL){
*t = malloc(sizeof **t);
(**t).val = v;
(**t).next = NULL;
}
else{
insertNode(&((**t).next), v);
}
}
void freeNode(struct node *t, int *sumOdd, int *sumEven) {
...
}
int main() {
struct node *root = NULL;
int sumOdd = 0;
int sumEven = 0;
for (int i = 0; i < 10; i++ ){
insertNode(&root, i);
}
printf("(*root).val = %d\n", (*root).val);
freeNode(root, &sumOdd, &sumEven);
printf("sumOdd = %d\n", sumOdd);
printf("sumEven = %d\n", sumEven);
return 0;
}
Write the code for function void freeNode indicated above.
For each node in the struct list created by the program, the function should:
i. check if (*t).val is even or odd,

Page 8 of 10 NEXT PAGE

 CS2850/CS2850R

ii. add its value to sumOdd if (*t).val is odd and to sumEven otherwise,
iii. call itself to process the next node and
iv. free the current node.

Hint The output of the program should be

(*root).val = 0
sumOdd = 25
sumEven = 20
and you can use the modulus operator to check if an integer, n, is even or
odd. For example, n%2 is zero if n = 6 and one if n = 7.
[9 marks]
(c) Consider the following C code:

#include <stdio.h>
#include <stdlib.h>

void sumIntegers(int n, int* a){

int s = 0;
for (int i = 0; i < n; i++){
s = s + i;
a[i] = s;
}
}

int main(int argc, char *argv[]){

int a[10];
int *pA = &a[0];
sumIntegers(10, a);

int k = strtol(argv[1], NULL, 10);

int x = k - 1;
int y = k + 1;
int z = k;

printf("%lu ", sizeof(a) - 10 * (x + y + z + k)/k);

printf("%i ", a[x]);
printf("%li ", k * (&a[y] - (a + k)));

Page 9 of 10 NEXT PAGE

 CS2850/CS2850R

printf("%i\n", *(pA + k) - a[z]);

}

Let k < 10 be an arbitrary positive integer. On running the program with

input k the output is
u1 u2 u3 u4
where ui (i= 1, 2, 3, 4) are four positive integers. Explain why
i. u1= 0 [2 marks]
.
ii. u2= k(k−1)
2
[2 marks]
.
iii. u3= k [2 marks]
.
iv. u4= 0 [2 marks]
.

Example Royal Holloway College was established in 1879. Let k1 = 1, k2 =

8, k3 = 7, k4 = 9. On running the program with input ki (i = 1, 2, 3, 4) the ob-
served outputs are
0 0 1 0
for k = k1 = 1,
0 28 8 0
for k = k2 = 8
0 21 7 0
for k = k3 = 7 and
0 36 9 0
for k = k4 = 9

END

Page 10 of 10 CM/NC