Description
CMPS111 Homework 1
(5 marks) Question 1. Briefly outline the evolution of Operating Systems from those used by the
earliest stored program computers of the 1940s to their modern counterparts.
(5 marks) Question 2. In the following piece of C code, how many processes are created when it is
executed? Explain your answer.
int main() {
fork();
fork();
fork();
exit(1);
}
(5 marks) Question 3. If an Operating System assigns an unsigned 32bit integer to store current
time as the number of seconds elapsed since 00:00 on January 1 1970, is this likely to be a
problem? Explain your answer.
(5 marks) Question 4. Describe how a web server might leverage multi-threading to improve
performance. Include diagrams if you feel this will make your answer clearer.
(5 marks) Question 5. (a) In a multiprogrammed environment with 16MB of memory where all
processes require 1MB of unshared memory and spend 60% of their time in I/O wait, calculate how
much memory will remain unused when approximately 99% CPU utilization is achieved. (b) In the
same multiprogrammed environment, if each process now requires 3MB of unshared memory,
calculate the maximum achievable CPU utilization. Show all your work.
§
CMPS111 Homework 2
(6 Marks) Question 1. Briefly outline the role of the Process Control Block (PCB), listing and
describing three pieces of information an Operating System might choose to store in the PCB.
(4 marks) Question 2. If we assume that when processes are interrupted they are placed in a
queue containing all non-running processes not waiting for an I/O operation to complete, briefly
describe two strategies the Operating System might adopt to service that queue. One-word answers
will not suffice.
(5 marks) Question 3. Outline a mechanism by which counting semaphores could be implemented
using the minimal number of binary semaphores and ordinary machine instructions. Include C or
pseudo code snippets if you feel this will make your answer clearer and/or more concise.
(4 marks) Question 4. Define the terms “race condition”, “deadlock”, and “starvation” as they relate
to Operating System design and outline the relationship between deadlock and starvation.
(6 marks) Question 5. Can the “priority inversion” problem outlined in section (3) of the background
information to Lab 2 occur if user-level threads are used instead of kernel-level threads? Explain
your answer.
§
CMPS111 Homework 3
(5 Marks) Question 1. Multi-level feedback queues (MLFQs) are implemented in many modern
time-sharing operating systems, including those derived from 4.4 BSD Unix. Briefly describe the
operation of MLFQs in 4.4 BSD Unix and the motivation behind using them.
(4 Marks) Question 2. A system has two processes and three identical resources. Each process
needs a maximum of two resources. Is deadlock possible? Explain your answer.
(3 marks) Question 3. Explain how quantum value and the time taken to perform a context switch
affect each other in a round robin process-scheduling algorithm.
(8 marks) Question 4. Five threads, A through E, arrive in alphabetic order at a scheduling queue
one second apart from each other. Estimated running times are 10, 6, 2, 4, and 8 seconds,
respectively. Their externally determined priorities are 3, 5, 2, 1, and 4, respectively, 5 being the
highest priority. For each of the following scheduling algorithms, determine the mean turnaround
time and mean waiting time. Assume thread switching is effectively instantaneous.
(a) First Come First Served
(b) Round Robin
(c) Preemptive Priority Scheduling
(d) Preemptive Shortest Job First
For (b), assume the system is multi-programmed with a quantum of 4 seconds. In all cases, show
your work and include diagrams/charts/tables as appropriate.
(5 Marks) Question 5. If a hard real-time system has four tasks with periods of 50, 100, 200, and
250 ms (milliseconds) respectively, and the four tasks require 35, 20, 10, and X ms of CPU time
respectively, calculate the largest value of X for which the system is schedulable during the period
of the fourth task, and state the scheduling algorithm used. Show all your work and include charts
as appropriate.
CMPS111 Homework 4
(6 Marks) Question 1. For the following Unix directory listing, express the file permissions shown as
(a) a protection matrix, (b) access control lists, and (c) capability lists. In this case, the user alice
is in two groups, users and devs.
-rw-r–r– 2 bob users 4096 Apr 11 08:08 notes.txt
-rwxr-xr-x 1 alice devs 3264 Apr 11 08:08 prog
-rw-rw—- 1 alice users 128 Apr 11 08:08 prog.c
-rw-r—– 1 alice devs 8122 Apr 11 08:08 image.gif
(4 Marks) Question 2. Processor A has separate memory caches for data and executable code;
processor B has a single cache where it stores both data and executable code. (a) Which processor
will leave an operating system running on it more susceptible to a buffer overflow attack? Explain
your answer. (b) List and describe two ways an operating system might try to protect itself from
buffer overflow attacks regardless of the processor on which it runs.
(4 Marks) Question 3. Consider a simple, non-paged memory management system in which
memory consists of the following hole sizes in memory order: 10 MB, 4 MB, 20 MB, 18 MB, 7 MB, 9
MB, 12 MB, and 15 MB. Which hole is taken for successive segment requests of 12 MB, 10 MB,
and 9 MB for (a) first fit (b) best fit (c) worst fit (d) next fit? Show all your work.
(3 Marks) Question 4. A computer with a 32-bit processor uses a two-level page lookup mechanism
consisting of page tables and a page table directory. Virtual Addresses consist of a 9-bit page table
directory field, an 11-bit page table field, and an offset. How large are the pages and how many are
there in the address space? Show your work.
(8 Marks) Question 5. (a) Explain the difference between the terms internal fragmentation and
external fragmentation as they relate to memory allocation. (b) Briefly outline the concept of paging.
(c) Explain why paging is considered a better memory management technique than compaction. In
all cases, draw diagrams if you feel this will make your answers clearer.
CMPS111 Homework 5
(4 Marks) Question 1. Consider a computer with a 32-bit processor and 8 KB pages. Calculate the
number of linear page table entries required if virtual addresses are 48-bit.
(6 Marks) Question2. A system has four processes and five allocatable resources. The current
allocation and maximum needs are as follows:
Allocated Maximum Available
Process A 1 0 2 1 1 1 1 2 1 4 0 0 X 1 1
Process B 2 0 1 1 1 2 2 2 1 0
Process C 1 1 0 1 0 2 1 3 1 0
Process D 1 1 1 1 1 1 1 2 2 1
Calculate the smallest value of X for which this is a state from which most processes can run to
completion without deadlock. Show your work and explain your answer.
(5 Marks) Question 3. Can two kernel-level threads in the same user-level process synchronize
using a kernel-level semaphore? What if the threads are implemented entirely at user-level?
Assume that no threads in any other processes have access to the semaphore. Discuss your
answers.
(6 Marks) Question 4. Early computers did not have Direct Memory Access (DMA); the CPU
handled every byte of data read or written. (a) Briefly describe the mechanism by which these early
computers handled non-DMA read operations. (b) What impact did the lack of DMA have on
multiprogramming? Use diagrams if you feel they make your answers clearer.
(4 Marks) Question 5. Consider the FIFO page replacement algorithm and the reference string:
1 2 3 4 1 2 5 1 2 3 4 5
If the number of page frames increases from three to four, does the number of page faults go down,
stay the same, or increase? Explain you answer using diagrams as appropriate.