CORE Metadata, citation and similar papers at core.ac.

uk
Provided by Almae Matris Studiorum Campus

Sample Exam Questions

69714 - REAL TIME OPERATING SYSTEM M
MEng in Automation Engineering, University of Bologna
Academic Year 2012-2013

Paolo Torroni

This is a collection of past exam questions. Some of the questions are taken
from the course text books.1 For the time being, solutions are not provided.
Be aware that “Midterm” and “Final” exams only cover part of the syllabus.
A “Standard” exam instead covers all the syllabus. Exam rules and organization
of the course are summarized in the first set of slides.2

Licence
The original material in this collection is licensed under a Creative Commons
Attribution-ShareAlike 3.0 Unported License.3 This is a Free Culture licence.
You are free:
• to Share: to copy, distribute and transmit the work
• to Remix: to adapt the work

• to make commercial use of the work

Under the following conditions:
• Attribution: You must attribute the work in the manner specified by
the author or licensor (but not in any way that suggests that they endorse
you or your use of the work).

• Share Alike: If you alter, transform, or build upon this work, you may
distribute the resulting work only under the same or similar license to this
one.

1 Abraham Silberschatz, Peter B. Galvin, Greg Gagne. Operating System Concepts,

8th or 9th Edition. International Student Version. Wiley 2010 (2013), and Giorgio C. But-
tazzo. Hard Real-Time Computing Systems: Predictable Scheduling Algorithms
and Applications, 3rd Edition. Springer 2011
2 https://campus.unibo.it/105196
3 http://creativecommons.org/licenses/by-sa/3.0/
 Real-Time Operating Systems M
First Midterm. April 5, 2013

Part II
Please, fill in your data in the fields below. E-mail will be
used for communication of the exam results. Open questions (4 points)
O1) Illustrate the microkernel approach to OS design.
Name . . . . . . . . . . . . . . Comment on advantages and disadvantages.
O2) Describe the di↵erences among short-term, medium-
Registration No. . . . term, and long term scheduling.
O3) There are many possible CPU-scheduling algorithms.
E-mail . . . . . . . . . . . . .
How could we select one particular algorithm for a par-
ticular system? Discuss various evaluation methods.
Part I
Quizzes (2 points) Part III

Mark each of the following statements True or False.

Exercise (3 points)
Explain your answer in one sentence (if you wish).
Suppose that processes P1 , P2 , . . . , P5 arrive for execution
at the times indicated in Table 1. Each process will run for
T After a fork(), the child process and the
Q1) the amount of time listed, and will be assigned a priority
F parent process have no shared address space.
ranging from 0 (highest) to 10 (lowest). No more
processes will arrive until the last process completes.
Explanation (optional): In answering the questions, base all decisions on the
information you have at the time the decision must be made.

T RPCs use a message-based communication

Q2) scheme to provide a remote service. Table 1: Process arrival/CPU-burst times and priorities.
F
Explanation (optional): Process Arrival Time Burst Time Priority
P1 0.0 8 10
P2 0.4 4 2
P3 0.5 1 10
T A disadvantage of the M:M threading model is P4 0.8 2 1
Q3) F that developers cannot create as many threads P5 1.0 2 5
as necessary, since kernel threads cannot run in
parallel on a multiprocessor.
Explanation (optional):
E1) Draw four Gantt charts that illustrate the execution
of these processes using the following scheduling
algorithms:
T Ordinary pipes continue to exist even after
Q4) F the processes have finished communicating and E1.1) FCFS;
have terminated. E1.2) preemptive SJF;
Explanation (optional): E1.3) preemptive priority (SJF if priority is equal);
E1.4) RR (quantum=2).
E2) What is the turnaround time of each process for
each of these four scheduling algorithms?
E3) What is the waiting time of each process for each of
these four scheduling algorithms?
E4) Which of the algorithms results in the maximum
overall turnaround time (over all processes)?
Part IV
Code analysis (2 points)
The program below uses the Phreads API.

C1) What would be the output from the program at LINE

A, LINE B, and LINE C?
C2) How many processes/threads would be active by the
time LINE B is executed?

Justify your answers. If there are di↵erent possible

answers, explain what the possibilities are.
#include <sys/types.h>
#include <sys/wait.h>
#include <pthread.h>
#include <stdio.h>
#include <unistd.h>

int value = 5;
void *runner1(void *param);
void *runner2(void *param);

int main()
{
pthread_t tid1, tid2;
pthread_attr_t attr1, attr2;

pthread_attr_init(&attr1);
pthread_create(&tid1,&attr1,runner1,NULL);

pthread_attr_init(&attr2);
pthread_create(&tid2,&attr2,runner2,NULL);

printf("A: value = %d\n", value); /* LINE A */

pthread_join(tid1,NULL);
pthread_join(tid2,NULL);

return 0;
}

void *runner1(void *param) {

value += 10;
printf("B: value = %d\n", value); /* LINE B */

pthread_exit(0);
}

void *runner2(void *param) {

value += 10;
printf("C: value = %d\n", value); /* LINE C */

pthread_exit(0);
}
 Real-Time Operating Systems M
First Midterm. April 5, 2013

Part II
Please, fill in your data in the fields below. E-mail will be
used for communication of the exam results. Open questions (4 points)
O1) What is the purpose of interrupts? Explain how
Name . . . . . . . . . . . . . . interrupt-driven system operation can be obtained
using dual mode operation and system calls.
Registration No. . . . O2) Explain scheduling queues.
O3) Describe the di↵erences between direct communica-
E-mail . . . . . . . . . . . . .
tion and indirect communication in message-based
systems.
Part I
Quizzes (2 points) Part III

Mark each of the following statements True or False.

Exercise (3 points)
Explain your answer in one sentence (if you wish).
Suppose that processes P1 , P2 , . . . , P5 arrive for execution
at the times indicated in Table 1. Each process will run for
T After a fork(), the child process and the
Q1) the amount of time listed, and will be assigned a priority
F parent process have no open files in common.
ranging from 0 (highest) to 10 (lowest). No more
processes will arrive until the last process completes.
Explanation (optional): In answering the questions, base all decisions on the
information you have at the time the decision must be made.

T A rendezvous can be obtained using a

Q2) blocking send() and a blocking receive(). Table 1: Process arrival/CPU-burst times and priorities.
F
Explanation (optional): Process Arrival Time Burst Time Priority
P1 0.0 8 10
P2 0.4 4 2
P3 0.5 1 10
T A disadvantage of the many-to-one threading P4 0.8 2 1
Q3) F model is that the entire process will block if a P5 1.0 2 5
thread makes a blocking system call.
Explanation (optional):
E1) Draw four Gantt charts that illustrate the execution
of these processes using the following scheduling
T A wait() system call is used to make a process algorithms:
Q4) F wait for an input/output device to become
ready. E1.1) nonpreemptive SJF;
Explanation (optional): E1.2) preemptive SJF;
E1.3) preemptive priority (FCFS if priority is equal);
E1.4) RR (quantum=4).
E2) What is the turnaround time of each process for
each of these four scheduling algorithms?
E3) What is the waiting time of each process for each of
these four scheduling algorithms?
E4) Which of the algorithms results in the minimum
average waiting time (over all processes)?
Part IV
Code analysis (2 points)
The program below uses the Phreads API.

C1) What would be the output from the program at LINE

A, LINE B, and LINE C?
C2) How many processes/threads would be active by the
time LINE B is executed?

Justify your answers. If there are di↵erent possible

answers, explain what the possibilities are.
#include <sys/types.h>
#include <sys/wait.h>
#include <pthread.h>
#include <stdio.h>
#include <unistd.h>

int value = 5;
void *runner(void *param);

int main()
{
pid_t pid;
pthread_t tid;
pthread_attr_t attr;

printf("A: value = %d\n", value); /* LINE A */

pid = fork();

if (pid == 0) {
pthread_attr_init(&attr);
pthread_create(&tid,&attr,runner,NULL);
pthread_join(tid,NULL);
printf("B: value = %d\n", value); /* LINE B */
return 0;
}
else if (pid > 0) {
wait(NULL);
printf("C: value = %d\n", value); /* LINE C */
return 0;
}
return 0;
}

void *runner(void *param) {

value += 10;
pthread_exit(0);
}
 Real-Time Operating Systems M
Second Midterm. May 13, 2013

O2) What is the cause of thrashing? How does the system

Please, fill in your data in the fields below. E-mail will be detect thrashing? Once it detects thrashing, what can
used for communication of the exam results. the system do to eliminate the problem?
O3) Explain how data can be transferred from a device
to the main memory using a direct memory access
Name . . . . . . . . . . . . . . (DMA) controller.

Registration No. . . .
Part III
E-mail . . . . . . . . . . . . . Exercises (3 points)
Part I E1) Consider the following snapshot of a system:

Quizzes (2 points) Allocation Max Request

ABCD ABCD ABCD
Mark each of the following statements True or False. P1 0012 0023 0001
Explain your answer in one sentence (if you wish). P2 1000 1220 0110
P3 1354 2356 1000
T A process cannot be executed if its logical P4 0001 2201 2200
Q1) F address space is bigger than the size of the
physical memory. Available
1220
Explanation (optional):
E1.1) Is the system in deadlock?
E1.2) Is the system in a safe state?
T An inverted page table contains, in each
Q2) entry, a page number and a frame number. E1.3) Can P3 ’s request be safely granted immediately?
F
E1.4) If P3 ’s request is granted immediately, does the
Explanation (optional): system enter a deadlock?

Be sure to motivate your answers.

T Paging eliminates internal fragmentation. E2) Given five memory partitions of 100 KB, 500 KB,
Q3)
F 200 KB, 300 KB, and 600 KB (in order), how would
the first-fit, best-fit, and worst-fit algorithms place
Explanation (optional): processes of 210 KB, 420 KB, 110 KB, and 430 KB (in
order)? Which algorithm makes the most efficient use
of memory?
T Deadlock cannot occur among processes that E3) Consider the following reference string:
Q4) need at most one (non-shareable) resource each.
F
1, 2, 3, 4, 5, 3, 4, 1, 6, 7, 8, 7, 8, 9, 7, 8, 9, 5, 6, 5, 7.
Explanation (optional):
Suppose you have four page frames. How may page
faults occur for the LRU page replacement algorithm?
Is that the minimum possible number of page faults?

Part II
Part IV
Open questions (3 points)
Code analysis (3 points)
O1) Why do some operating systems use spinlocks as
a synchronisation mechanism only on multiprocessor The Cigarette-Smokers Problem is a well-known process
systems and not on single-processor systems? synchronisation problem that can defined as follows:
 Consider a system with three smoker pro-
cesses. Each smoker continuously rolls a /* tobacco agent */
cigarette (make_cigarette()) and then smokes while(TRUE) {
wait(agentSem);
it (smoke()). But to roll a cigarette, the smoker signal(paper);
needs three resources: tobacco, paper, and signal(matches);
matches. One of the smokers has an infinite }
amount of paper, another has infinite tobacco,
and the third has infinite matches. /* paper agent */
In order to provide a given smoker with the while(TRUE) {
missing two resources, so he can roll a cigarette, wait(agentSem);
a number of other processes synchronise with one signal(tobacco);
another and with the smokers. signal(matches);
At one time, only one smoker can acquire the }
missing two resources. Smokers cannot accumu-
/* matches agent */
late resources for future use. Several smokers can while(TRUE) {
smoke at the same time, but each can smoke at wait(agentSem);
most one cigarette at a time. signal(tobacco);
signal(paper);
The following pseudo-code shows a possible solution with }
nine processes: three smokers, three pushers, and three
agents. All nine processes execute concurrently. /* tobacco pusher */
while(TRUE) {
A1) Show a possible execution that reaches LINE A. Be wait(tobacco);
sure to indicate which instructions are executed by wait(mutex);
which process before LINE A is executed. if(isPaper) {
isPaper = FALSE;
A2) Is the mutex semaphore needed? What happens signal(tobacco_and_paper);
if we remove all occurrences of wait(mutex) and }
signal(mutex) from this solution? else if(isMatches) {
isMatches = FALSE;
A3) Show how other possible synchronisation issues–in signal(tobacco_and_matches);
particular, deadlock and starvation–are solved (or }
show what synchronisation issues are unsolved, if any). else isTobacco = TRUE;
signal(mutex);
}
/* semaphores and shared global variables */
semaphore agentSem = 1, mutex = 1; /* paper pusher */
semaphore tobacco = 0, paper = 0, match = 0; while(TRUE) {
semaphore paper_and_matches = 0, wait(paper);
tobacco_and_matches = 0, wait(mutex);
tobacco_and_paper = 0; if(isTobacco) {
Boolean isPaper = FALSE, isTobacco = FALSE, isTobacco = FALSE;
isMatches = FALSE; signal(tobacco_and_paper);
}
/* smoker with tobacco */ else if(isMatches) {
while(TRUE) { isMatches = FALSE;
wait(paper_and_matches); signal(paper_and_matches);
make_cigarette(); }
signal(agentSem); else isPaper = TRUE;
smoke(); /* LINE A */ signal(mutex);
} }

/* smoker with paper */ /* matches pusher */

while(TRUE) { while(TRUE) {
wait(tobacco_and_matches); wait(matches);
make_cigarette(); wait(mutex);
signal(agentSem); if(isPaper) {
smoke(); isPaper = FALSE;
} signal(paper_and_matches);
}
/* smoker with matches */ else if(isTobacco) {
while(TRUE) { isTobacco = FALSE;
wait(tobacco_and_paper); signal(tobacco_and_matches);
make_cigarette(); }
signal(agentSem); else isMatches = TRUE;
smoke(); signal(mutex);
} }
 Real-Time Operating Systems M
Second Midterm. May 13, 2013

O2) Under what circumstances do page faults occur?

Please, fill in your data in the fields below. E-mail will be Describe the actions taken from the operating system
used for communication of the exam results. when a page fault occurs.
O3) Consider a system consisting of four resources of the
same type that are shared by three processes, each
Name . . . . . . . . . . . . . . of which needs at most two resources. Show that the
system is deadlock free.
Registration No. . . .

E-mail . . . . . . . . . . . . .
Part III
Exercises (3 points)
Part I
E1) Consider the following snapshot of a system:
Quizzes (2 points)
Allocation Max Request
Mark each of the following statements True or False. ABCD ABCD ABCD
Explain your answer in one sentence (if you wish). P1 0012 0023 0001
P2 1354 2356 1000
T A hashed page table contains, in each entry, P3 1000 1220 0110
Q1) a pointer to a list. P4 0001 2201 2200
F
Explanation (optional): Available
1220

T Deadlock cannot occur among processes that E1.1) Is the system in deadlock?
Q2) F request (non-shareable) resources only when E1.2) Is the system in a safe state?
they have none.
E1.3) Can P2 ’s request be safely granted immediately?
Explanation (optional): E1.4) If P2 ’s request is granted immediately, does the
system enter a deadlock?

T Paging permits pages to be of arbitrary size. Be sure to motivate your answers.

Q3)
F E2) Consider a logical address space of 32 pages with
1,024 words per page, mapped onto a physical
Explanation (optional): memory of 16 frames. How many bits are required in
the logical address? How many bits are required in the
physical address?
T The working-set model is used to prevent
Q4) thrashing while at the same time optimising E3) Consider the following reference string:
F
CPU utilisation.
4, 2, 3, 4, 5, 3, 4, 1, 6, 7, 8, 9, 7, 8, 9, 5, 6, 5, 7, 5, 6.
Explanation (optional):
Suppose you have four page frames. How may page
faults occur for the LRU page replacement algorithm?
Is that the minimum possible number of page faults?

Part II
Part IV
Open questions (3 points)
Code analysis (3 points)
O1) How does the signal() operation on condition
variables associated with monitors di↵er from the The Cigarette-Smokers Problem is a well-known process
signal() operation defined for semaphores? synchronisation problem that can defined as follows:
 Consider a system with three smoker pro-
cesses. Each smoker continuously rolls a /* tobacco agent */
cigarette (make_cigarette()) and then smokes while(TRUE) {
wait(agentSem);
it (smoke()). But to roll a cigarette, the smoker signal(paper);
needs three resources: tobacco, paper, and signal(matches);
matches. One of the smokers has an infinite }
amount of paper, another has infinite tobacco,
and the third has infinite matches. /* paper agent */
In order to provide a given smoker with the while(TRUE) {
missing two resources, so he can roll a cigarette, wait(agentSem);
a number of other processes synchronise with one signal(tobacco);
another and with the smokers. signal(matches);
At one time, only one smoker can acquire the }
missing two resources. Smokers cannot accumu-
/* matches agent */
late resources for future use. Several smokers can while(TRUE) {
smoke at the same time, but each can smoke at wait(agentSem);
most one cigarette at a time. signal(tobacco);
signal(paper);
The following pseudo-code shows a possible solution with }
nine processes: three smokers, three pushers, and three
agents. All nine processes execute concurrently. /* tobacco pusher */
while(TRUE) {
A1) Show a possible execution that reaches LINE A. Be wait(tobacco);
sure to indicate which instructions are executed by wait(mutex);
which process before LINE A is executed. if(isPaper) {
isPaper = FALSE;
A2) Is the mutex semaphore needed? What happens signal(tobacco_and_paper);
if we remove all occurrences of wait(mutex) and }
signal(mutex) from this solution? else if(isMatches) {
isMatches = FALSE;
A3) Show how other possible synchronisation issues–in signal(tobacco_and_matches);
particular, deadlock and starvation–are solved (or }
show what synchronisation issues are unsolved, if any). else isTobacco = TRUE;
signal(mutex);
}
/* semaphores and shared global variables */
semaphore agentSem = 1, mutex = 1; /* paper pusher */
semaphore tobacco = 0, paper = 0, match = 0; while(TRUE) {
semaphore paper_and_matches = 0, wait(paper);
tobacco_and_matches = 0, wait(mutex);
tobacco_and_paper = 0; if(isTobacco) {
Boolean isPaper = FALSE, isTobacco = FALSE, isTobacco = FALSE;
isMatches = FALSE; signal(tobacco_and_paper);
}
/* smoker with tobacco */ else if(isMatches) {
while(TRUE) { isMatches = FALSE;
wait(paper_and_matches); signal(paper_and_matches);
make_cigarette(); }
signal(agentSem); else isPaper = TRUE;
smoke(); signal(mutex);
} }

/* smoker with paper */ /* matches pusher */

while(TRUE) { while(TRUE) {
wait(tobacco_and_matches); wait(matches);
make_cigarette(); wait(mutex);
signal(agentSem); if(isPaper) {
smoke(); /* LINE A */ isPaper = FALSE;
} signal(paper_and_matches);
}
/* smoker with matches */ else if(isTobacco) {
while(TRUE) { isTobacco = FALSE;
wait(tobacco_and_paper); signal(tobacco_and_matches);
make_cigarette(); }
signal(agentSem); else isMatches = TRUE;
smoke(); signal(mutex);
} }
 Real-Time Operating Systems M
First+Second Midterm. May 13, 2013

T Deadlock cannot occur among processes that

Q6) need at most one (non-shareable) resource each.
Please, fill in your data in the fields below. E-mail will be F
used for communication of the exam results.
Explanation (optional):

Name . . . . . . . . . . . . . .
T The working-set model is used to prevent
Registration No. . . . Q7) F thrashing while at the same time optimising
CPU utilisation.
E-mail . . . . . . . . . . . . . Explanation (optional):

Part I T A hashed page table contains, in each entry,

Q8)
Quizzes (4 points) F a pointer to a list.

Explanation (optional):
Mark each of the following statements True or False.
Explain your answer in one sentence (if you wish).

T A rendezvous can be obtained using a

Q1) blocking send() and a blocking receive(). Part II
F

Explanation (optional): Open questions (7 points)

O1) Illustrate the modular kernel approach to OS design.
T A disadvantage of the M:M threading model Comment on advantages and disadvantages.
Q2) F is that developers cannot create as many O2) There are many possible CPU-scheduling algorithms.
threads as necessary, since kernel threads How could we select one particular algorithm for a par-
cannot run in parallel on a multiprocessor. ticular system? Discuss various evaluation methods.
Explanation (optional): O3) Under what circumstances do page faults occur?
Describe the actions taken from the operating system
when a page fault occurs.
T Immediately after a fork() is executed, the O4) Explain how data can be transferred from a device
Q3) F child process and the parent process have no to the main memory using a direct memory access
shared variables. (DMA) controller.
Explanation (optional): O5) Consider a system consisting of four resources of the
same type that are shared by three processes, each
of which needs at most two resources. Show that the
T Named pipes continue to exist even after the system is deadlock free.
Q4) F processes have finished communicating and have
terminated.

Explanation (optional):

T Paging eliminates internal fragmentation.

Q5)
F

Explanation (optional):
Part III Part IV
Exercises (6 points) Code analysis (5 points)
E1) Suppose that processes P1 , P2 , . . . , P5 arrive for execu- C1) The program below uses the Phreads API.
tion at the times indicated in Table 1. Each process
will run for the amount of time listed, and will be C1.1) What would be the output from the program at
assigned a priority ranging from 0 (highest) to 10 LINE A, LINE B, and LINE C?
(lowest). No more processes will arrive until the last C1.2) How many processes/threads would be active
process completes. by the time LINE B is executed?

Be sure to justify your answers.

Table 1: Process arrival/CPU-burst times and priorities.

Process Arrival Time Burst Time Priority #include <sys/types.h>

P1 0.0 8 7 #include <sys/wait.h>
#include <pthread.h>
P2 0.4 4 2 #include <stdio.h>
P3 0.5 1 7 #include <unistd.h>
P4 0.8 2 1
P5 1.0 2 5 int val = 10;
void *runner(void *param);

int main()
Draw four Gantt charts that illustrate the execution {
of these processes using the following scheduling pid_t pid;
algorithms: pthread_t tid;
pthread_attr_t attr;
E1.1) nonpreemptive SJF;
E1.2) preemptive SJF; printf("A: value = %d\n", val); /* LINE A */
E1.3) preemptive priority (FCFS if priority is equal); pid = fork();
E1.4) RR (quantum=4).
if (pid == 0) {
In answering the questions, base all decisions on the pthread_attr_init(&attr);
information you have at the time the decision must be pthread_create(&tid,&attr,runner,NULL);
made. pthread_join(tid,NULL);
printf("B: value = %d\n", val); /* LINE B */
E2) Consider the following snapshot of a system: return 0;
}
else if (pid > 0) {
Allocation Max Request wait(NULL);
ABCD ABCD ABCD printf("C: value = %d\n", val); /* LINE C */
P1 0001 2201 2200 return 0;
P2 0012 0023 0001 }
P3 1354 2356 1000 return 0;
P4 1000 1220 0110 }

Available void *runner(void *param) {

1220 val += 20;
pthread_exit(0);
}
E1.1) Is the system in deadlock?
E1.2) Is the system in a safe state? C2) The Cigarette-Smokers Problem is a well-known
E1.3) Can P3 ’s request be safely granted immediately? process synchronisation problem, defined as follows:
E1.4) If P3 ’s request is granted immediately, does the Consider a system with three smoker pro-
system enter a deadlock? cesses. Each smoker continuously rolls a
Be sure to motivate your answers. cigarette (make_cigarette()) and then
smokes it (smoke()). But to roll a cigarette,
E3) Consider the following reference string: the smoker needs three resources: tobacco,
paper, and matches. One of the smokers
1, 2, 3, 4, 5, 3, 4, 1, 6, 7, 8, 7, 8, 9, 7, 8, 9, 5, 4, 5, 4, 2. has an infinite amount of paper, another has
infinite tobacco, and the third has infinite
Suppose you have four page frames. How may page matches.
faults occur for the LRU page replacement algorithm? In order to provide a given smoker with
Is that the minimum possible number of page faults? the missing two resources, so he can roll
 a cigarette, a number of other processes
synchronise with one another and with the /* tobacco agent */
smokers. while(TRUE) {
At one time, only one smoker can acquire wait(agentSem);
the missing two resources. Smokers cannot signal(paper);
accumulate resources for future use. Several signal(matches);
}
smokers can smoke at the same time, but
each can smoke at most one cigarette at a /* paper agent */
time. while(TRUE) {
wait(agentSem);
The following pseudo-code shows a possible solution signal(tobacco);
with nine processes: three smokers, three pushers, and signal(matches);
three agents. All nine processes execute concurrently. }

C2.1) Show a possible execution that reaches LINE A. /* matches agent */

Be sure to indicate which instructions are while(TRUE) {
executed by which process before LINE A is wait(agentSem);
executed. signal(tobacco);
signal(paper);
C2.2) Is the mutex semaphore needed? What happens }
if we remove all occurrences of wait(mutex)
and signal(mutex) from this solution? /* tobacco pusher */
C2.3) Show how other possible synchronisation issues– while(TRUE) {
in particular, deadlock and starvation–are wait(tobacco);
wait(mutex);
solved (or show what synchronisation issues are
if(isPaper) {
unsolved, if any). isPaper = FALSE;
signal(tobacco_and_paper);
}
/* semaphores and shared global variables */ else if(isMatches) {
semaphore agentSem = 1, mutex = 1; isMatches = FALSE;
semaphore tobacco = 0, paper = 0, match = 0; signal(tobacco_and_matches);
semaphore paper_and_matches = 0, }
tobacco_and_matches = 0, else isTobacco = TRUE;
tobacco_and_paper = 0; signal(mutex);
Boolean isPaper = FALSE, isTobacco = FALSE, }
isMatches = FALSE;
/* paper pusher */
/* smoker with tobacco */ while(TRUE) {
while(TRUE) { wait(paper);
wait(paper_and_matches); wait(mutex);
make_cigarette(); if(isTobacco) {
signal(agentSem); isTobacco = FALSE;
smoke(); signal(tobacco_and_paper);
} }
else if(isMatches) {
/* smoker with paper */ isMatches = FALSE;
while(TRUE) { signal(paper_and_matches);
wait(tobacco_and_matches); }
make_cigarette(); else isPaper = TRUE;
signal(agentSem); signal(mutex);
smoke(); }
}
/* matches pusher */
/* smoker with matches */ while(TRUE) {
while(TRUE) { wait(matches);
wait(tobacco_and_paper); wait(mutex);
make_cigarette(); if(isPaper) {
signal(agentSem); isPaper = FALSE;
smoke(); /* LINE A */ signal(paper_and_matches);
} }
else if(isTobacco) {
isTobacco = FALSE;
signal(tobacco_and_matches);
}
else isMatches = TRUE;
signal(mutex);
}
 Real-Time Operating Systems M
Final Exam. June 12, 2013

Part I
Please, fill in your data in the fields below. E-mail will be
used for communication of the exam results. Quizzes (2 points)
Mark each of the following statements True or False.
Name . . . . . . . . . . . . . . Explain your answer in one sentence (if you wish).

Registration No. . . . T The Stack Resource Policy may stop a task

Q1) allowed by the Non-Preemptive Protocol.
F
E-mail . . . . . . . . . . . . . Explanation (optional):
Frequently used formulas and tables
Some of the following formulas and tables may be useful in T Given a set of independent aperiodic tasks,
solving some of the exercises. with arbitrary arrival times, any algorithm that
F
Schedulability Analysis (Extended) Q2) executes the tasks in order of nondecreasing
P Ch Ci + Bi relative deadlines is optimal with respect to
8i = 1, . . . , n +
1
 i(2 /i 1) minimising the maximum lateness.
h:Ph >Pi Th Ti
✓ ◆✓ ◆ Explanation (optional):
Q Ch Ci + Bi
8i = 1, . . . , n +1 +1 2
h:Ph >Pi Th Ti
T Push-through blocking cannot a↵ect a highest-
P Ch Ci + Bi Q3) priority task.
8i = 1, . . . , n + 1 F
h:Ph >Pi Th Ti
Explanation (optional):
Response Time Analysis (Extended)
8
iP1
>
> (0) T For independent preemptive periodic tasks
>
< R i = C i + Bi + Ck
k=1 & ' Q4) F under fixed priorities, the critical instant of a
>
> (s) (s 1)
iP1 (s 1)
Ri given task occurs when all higher priority tasks
>
: Ri = Ci + Bi + Ii = Ci + Bi + Ck have all di↵erent activation times.
k=1 Tk
Explanation (optional):
Processor Demand Test
⌫
P
n L Di + Ti
g(0, L) = Ci T The processor utilization’s least upper bound
i=1 Ti Q5) Ulub distinguishes between feasible and infeasi-
F
ble task sets.
1 P
n
L⇤ = (Ti Di )Ui
1 U i=1 Explanation (optional):
Tables
1
n n(2 /n 1)
T EDF is a simpler but more rigid scheduling
1 1.000 Q6)
F algorithm than Timeline scheduling.
2 0.828
3 0.780
4 0.757 Explanation (optional):
5 0.743
6 0.735
7 0.279
8 0.724
9 0.721
10 0.718
 0
Part II 2 Ti Ci Di
⌧1 3 1 3
Open questions (3 points) ⌧2
⌧3
4
6
1
1
2
5
⌧4 12 2 10
O1) Discuss the main properties of the Stack Resource
Policy protocol.
Figure 3: Characteristics of the 02 task set.
O2) Compare advantages and disadvantages of complete
tree-search algorithms (such as Bratley’s) with respect
to heuristic algorithms (such as the one used in the
E3) Consider a task set 3 , composed of 5 periodic tasks
Spring kernel) for real-time task scheduling.
⌧1 , . . . , ⌧5 that share 4 resources a, b, c, d and execute on
a single-processor machine. 3 ’s tasks are represented
in Figure 4. Each resource is accessed in mutual
Part III exclusion using the Priority Ceiling Protocol (PCP).
Exercises (6 points) T1 a

E1) Let 1 = ⌧1 , . . . , ⌧6 be a set of preemptable, aperiodic T2 a d

tasks with precedence constraints, to be executed on a T3 d b c
single-processor machine. Figure 1 shows release time
ai , worst-case computation time Ci , absolute deadline T4 c

di , relative to ai , and precedence relations of each task T5 b c

⌧i in 1 .

1 ⌧1 ⌧2 ⌧3 ⌧4 ⌧5 ⌧6
ai 0 6 4 13 0 10 Figure 4: Graphical representation of critical sections in 3.
Ci 5 4 3 4 1 1
di 20 20 19 18 20 18 Figure 5 shows phase i , period Ti = Di , worst-case
prec ⌧ 2 ! ⌧4 ⌧1 ! ⌧5 ⌧4 ! ⌧6 computation time Ci , and a description of the access
⌧ 3 ! ⌧4 ⌧5 ! ⌧6 windows to the shared resources of each task ⌧i , in
terms of start time t(Rk ) and duration i,Rk of the
critical section for each task ⌧i and each resource Rk .
Figure 1: Characteristics of the 1 task set.
3 i Ti Ci t(a) i,a t(b) i,b t(c) i,c t(d) i,d
Show the minimum lateness schedule for 1 , using a ⌧1 8 20 5 1 3
Gantt chart. Be sure to motivate your answer. ⌧2 6 30 6 1 4 3 1
⌧3 4 40 6 3 1 5 1 1 4
E2) Consider a set of periodic tasks 2 = ⌧1 , . . . , ⌧4 , to be ⌧4 2 50 3 1 1
scheduled on a single-processor machine. Figure 2 ⌧5 0 60 6 1 4 3 1
shows period Ti and worst-case computation time Ci
of each task ⌧i .
Figure 5: Characteristics of the 3 task set.
2 Ti Ci
⌧1 3 1
⌧2 4 1 E3.1) Using a Gantt chart, show the schedule under
⌧3 6 1 RM+PCP, from time 0 until completion of the
⌧4 12 2 first instance of ⌧5 . Below the Gantt chart, show
how ⌧5 ’s active priority p5 evolves.
Figure 2: Characteristics of the 2 task set.

E2.1) Is 2 feasible under fixed priorities?

E2.2) Is 2 feasible under dynamic priorities?

Let us now assume the following relative deadlines for

⌧2 , ⌧3 , ⌧4 : D2 = 2, D3 = 5, D4 = 10, whereas T1 = D1 =
3. Let us call 02 this new task set (see Figure 3).

E2.3) Is 0
2 feasible under fixed priorities?
E2.4) Is 0
2 feasible under dynamic priorities?

Be sure to motivate your answer.

 Real-Time Operating Systems M
Final Exam. June 12, 2013

Part I
Please, fill in your data in the fields below. E-mail will be
used for communication of the exam results. Quizzes (2 points)
Mark each of the following statements True or False.
Name . . . . . . . . . . . . . . Explain your answer in one sentence (if you wish).

Registration No. . . . T Under the Priority Ceiling Protocol, a task

Q1) F can be blocked only before it starts executing,
never once it has started.
E-mail . . . . . . . . . . . . .
Explanation (optional):
Frequently used formulas and tables
Some of the following formulas and tables may be useful in
solving some of the exercises. T For each task set, there exists always one and
Q2) F only one optimal scheduling algorithm (in the
Schedulability Analysis (Extended)
sense of feasibility).
P Ch Ci + Bi 1
8i = 1, . . . , n +  i(2 /i 1) Explanation (optional):
h:Ph >Pi Th Ti
✓ ◆✓ ◆
Q Ch Ci + Bi
8i = 1, . . . , n +1 +1 2
Th Ti T Preemption generally does not increase the
h:Ph >Pi Q3) complexity of a scheduling problem.
F
P Ch Ci + Bi
8i = 1, . . . , n + 1 Explanation (optional):
h:Ph >Pi Th Ti

Response Time Analysis (Extended)

8 T For independent preemptive periodic tasks
>
> (0)
iP1
Q4) F under fixed priorities, the critical instant of a
>
< R i = C i + Bi + Ck given task occurs when all higher priority tasks
k=1 & '
iP1 (s 1) have the same activation time as its own.
>
> (s) (s 1) Ri
>
: Ri = Ci + Bi + Ii = Ci + Bi + Ck
k=1 Tk Explanation (optional):

Processor Demand Test

⌫ T A task set consisting of three tasks, ⌧1 , ⌧2 , and
P
n L Di + Ti ⌧3 , with identical period, is RM-feasible if and
g(0, L) = Ci Q5) F
i=1 Ti only if the total processor utilisation is at most
1.
1 P
n
L⇤ = (Ti Di )Ui Explanation (optional):
1 U i=1
Tables
1
n n(2 /n 1) T Priority Inversion is a phenomenon that cannot
1 1.000 Q6) occur if tasks are independent.
F
2 0.828
3 0.780 Explanation (optional):
4 0.757
5 0.743
6 0.735
7 0.279
8 0.724
9 0.721
10 0.718
 0
Part II 2 Ti Ci Di
⌧1 3 1 3
Open questions (3 points) ⌧2
⌧3
4
6
1
1
2
5
⌧4 12 2 10
O1) What are the main unsolved problems of the Priority
Inheritance Protocol? Use examples to illustrate the
point. Figure 3: Characteristics of the 0
2 task set.
O2) Compare advantages and disadvantages of RM with
respect to EDF.
E3) Consider a task set 3 , composed of 5 periodic tasks
⌧1 , . . . , ⌧5 that share 4 resources a, b, c, d and execute on
a single-processor machine. 3 ’s tasks are represented
Part III in Figure 4. Each resource is accessed in mutual
exclusion using the Stack Resource Policy (SRP).
Exercises (6 points)
T1 a
E1) Let 1 = ⌧1 , . . . , ⌧6 be a set of preemptable, aperiodic
tasks with precedence constraints, to be executed on a T2 a d
single-processor machine. Figure 1 shows release time T3 d b c
ai , worst-case computation time Ci , absolute deadline
di , relative to ai , and precedence relations of each task T4 c

⌧i in 1 . T5 b c

1 ⌧1 ⌧2 ⌧3 ⌧4 ⌧5 ⌧6
ai 0 6 4 13 0 10
Ci 5 4 3 4 1 1 Figure 4: Graphical representation of critical sections in 3.
di 20 20 19 18 20 18
prec ⌧ 2 ! ⌧4 ⌧1 ! ⌧5 ⌧4 ! ⌧6 Figure 5 shows phase i , period Ti = Di , worst-case
⌧ 3 ! ⌧4 ⌧5 ! ⌧6 computation time Ci , and a description of the access
windows to the shared resources of each task ⌧i , in
terms of start time t(Rk ) and duration i,Rk of the
Figure 1: Characteristics of the 1 task set. critical section for each task ⌧i and each resource Rk .
Show the minimum lateness schedule for 1 , using a 3 i Ti Ci t(a) i,a t(b) i,b t(c) i,c t(d) i,d
Gantt chart. Be sure to motivate your answer. ⌧1 8 20 5 1 3
⌧2 6 30 6 1 4 3 1
E2) Consider a set of periodic tasks 2 = ⌧1 , . . . , ⌧4 , to be ⌧3 4 40 6 3 1 5 1 1 4
scheduled on a single-processor machine. Figure 2 ⌧4 2 50 3 1 1
shows period Ti and worst-case computation time Ci ⌧5 0 60 6 1 4 3 1
of each task ⌧i .

2 Ti Ci Figure 5: Characteristics of the task set.

3
⌧1 3 1
⌧2 4 1
⌧3 6 1 E3.1) Using a Gantt chart, show the schedule under
⌧4 12 2 EDF+SRP, from time 0 until completion of the
first instance of ⌧5 . Below the Gantt chart, show
how the system ceiling ⇧s evolves.
Figure 2: Characteristics of the 2 task set.

E2.1) Is 2 feasible under fixed priorities?

E2.2) Is 2 feasible under dynamic priorities?

Let us now assume the following relative deadlines for

⌧2 , ⌧3 , ⌧4 : D2 = 2, D3 = 5, D4 = 10, whereas T1 = D1 =
3. Let us call 02 this new task set (see Figure 3).

E2.3) Is 0
2 feasible under fixed priorities?
E2.4) Is 0
2 feasible under dynamic priorities?

Be sure to motivate your answer.

 Real-Time Operating Systems M
Standard Exam. June 12, 2013

Part I
Please, fill in your data in the fields below. E-mail will be
used for communication of the exam results. Quizzes (8 pts)
Mark each of the following statements True or False.
Name . . . . . . . . . . . . . . Explain your answer in one sentence (if you wish).

Registration No. . . . T In the indirect communication IPC scheme, a

Q1) F communication link may be associated with at
most two processes.
E-mail . . . . . . . . . . . . .
Explanation (optional):
Frequently used formulas and tables
Some of the following formulas and tables may be useful in
solving some of the exercises. T An advantage of multithreading is an increased
Q2) responsiveness in interactive applications.
Schedulability Analysis (Extended) F
P Ch Ci + Bi 1
8i = 1, . . . , n +  i(2 /i 1) Explanation (optional):
h:Ph >Pi Th Ti
✓ ◆✓ ◆
Q Ch Ci + Bi
8i = 1, . . . , n +1 +1 2 T All named pipes created by a process P are
Th Ti
h:Ph >Pi Q3) F automatically removed from the file system
P Ch Ci + Bi after P terminates.
8i = 1, . . . , n + 1
h:Ph >Pi Th Ti Explanation (optional):

Response Time Analysis (Extended)

8 T Paging eliminates external fragmentation.
iP1
>
> (0) Q4)
>
< R i = C i + Bi + Ck F
k=1 & '
iP1 (s 1)
>
> (s) (s 1) Ri Explanation (optional):
>
: Ri = Ci + Bi + Ii = Ci + Bi + Ck
k=1 Tk

Processor Demand Test T Deadlock cannot occur among processes that

⌫ Q5) F need at most two (non-shareable) resources
P
n L Di + Ti each.
g(0, L) = Ci
i=1 Ti
Explanation (optional):
1 P
n
L ⇤
= (Ti Di )Ui
1 U i=1
Tables T The working-set model is used to prevent
1
Q6) F thrashing while at the same time optimising
n n(2 /n 1) CPU utilisation.
1 1.000
2 0.828 Explanation (optional):
3 0.780
4 0.757
5 0.743
6 0.735 T For independent preemptive periodic tasks with
7 0.279 Q7) F fixed priorities, the critical instant of a given
8 0.724 task occurs when all higher priority tasks have
9 0.721 the same activation time as its own.
10 0.718
Explanation (optional):
 E2) Let 2 = ⌧1 , . . . , ⌧6 be a set of nonpreemptable,
aperiodic and synchronous tasks with precedence
T Preemption generally does not increase the constraints, to be executed on a single-processor
Q8) complexity of a scheduling problem.
F machine. Figure 1 shows worst-case computation
time Ci , absolute deadline di , and precedence relations
Explanation (optional): of each task ⌧i in 2 .

2 ⌧1 ⌧2 ⌧3 ⌧4 ⌧5 ⌧6
T The processor utilization’s least upper bound Ci 5 4 3 4 1 1
Q9) Ulub distinguishes between feasible and infeasi- di 20 20 19 18 20 18
F prec ⌧2 ! ⌧4 ⌧1 ! ⌧5 ⌧4 ! ⌧6
ble task sets.
⌧3 ! ⌧4 ⌧5 ! ⌧6
Explanation (optional):
Figure 1: Characteristics of the 2 task set.
T Priority Inversion is a phenomenon that can Show the minimum lateness schedule for 2, using a
Q10) F occur only when there are tasks sharing Gantt chart.
non-preemptible resources.
Be sure to motivate your answer.
Explanation (optional):
E3) Consider a task set 3 , composed of 5 periodic tasks
⌧1 , . . . , ⌧5 that share 4 resources a, b, c, d and execute on
a single-processor machine. 3 ’s tasks are represented
T Ceiling blocking cannot a↵ect top-priority tasks. in Figure 2. Each resource is accessed in mutual
Q11) exclusion using the Priority Ceiling Protocol (PCP).
F
Explanation (optional): T1 a

T2 a d

T Under the Priority Ceiling Protocol, a task T3 d b c

Q12) F can be blocked only before it starts executing, T4 c
never once it has started.
T5 b c
Explanation (optional):

Figure 2: Graphical representation of critical sections in 3.

Part II Figure 3 shows phase i , period Ti = Di , worst-case

computation time Ci , and a description of the access
Open questions (10 pts) windows to the shared resources of each task ⌧i , in
terms of start time t(Rk ) and duration i,Rk of the
critical section for each task ⌧i and each resource Rk .
O1) Describe the content of a Process Control Block.
O2) Illustrate the Dining Philosophers Problem. Show 3 i Ti Ci t(a) i,a t(b) i,b t(c) i,c t(d) i,d
a possible solution using semaphores. Discuss three ⌧1 8 20 5 1 3
di↵erent ways to prevent deadlock. ⌧2 6 30 6 1 4 3 1
⌧3 4 40 6 3 1 5 1 1 4
O3) What are the Priority Inheritance Protocol’s main un- ⌧4 2 50 3 1 1
solved problems? Use examples to illustrate the point. ⌧5 0 60 6 1 4 3 1

Part III Figure 3: Characteristics of the 3 task set.

Exercises (13 pts) E3.1) What is the worst-case blocking time Bi for
each task ⌧i 2 3 ?
E1) Consider the following reference string: E3.2) Is 3 feasible with RM+PCP?
1, 2, 3, 4, 5, 3, 4, 1, 6, 7, 8, 7, 8, 9, 7, 8, 9, 5, 6, 5, 7. E3.3) Using a Gantt chart, show the schedule under
RM+PCP, from time 0 until completion of the
Suppose you have four page frames. How may page first instance of ⌧5 . Below the Gantt chart, show
faults occur for the LRU page replacement algorithm? how ⌧5 ’s active priority p5 evolves.
Is that the minimum possible number of page faults?
Be sure to motivate your answer.
Be sure to motivate your answer.