COMPS267F (PRACTICE ASSIGNMENT)
COMPS267F (2200) PRACTICE ASSIGNMENT Page 1 of 26











COMPS267F
Operating Systems




PRACTICE ASSIGNMENT


Spring 2022 Presentation
PRACTICE ASSIGNMENT

QUESTION BOOK (SAMPLE)


COMPS267F (PRACTICE ASSIGNMENT)
COMPS267F (2200) PRACTICE ASSIGNMENT Page 2 of 26

The following is just to show the content that is similar to what you will see in the Take-Home
Assignment. It is not relevant to this Practice Assignment.
Important Notes about the Take Home Assignment
• This assignment is open book. Some questions are challenging, normally no perfect answer
will be expected. You should consider the time is never enough. Proficiency and efficiency
are part of the assessment.
• The plagiarism rules of the university are applied. The submitted work must be original, that
is, your own. The students will be disqualified if plagiarised materials are submitted. For
examples, students should not aid or attempt to aid another student or receive or attempt to
receive aid from another person, or interact on sharing platforms, or copy a part or the whole
answers from a source. Students committed plagiarism will be penalized.
• You should constantly check your email account (sxxxxxxx@hkmu.edu.hk) for announcements
and updates.
• The final assignment is available for download at 09:00 on the scheduled date. The submission
time is 17:00. No late submission is allowed.
Important Notes about Working on the Assignment
• You should answer in English. Show steps in your answers that involves calculation.
• Write down your assumptions to supplement the information of a question if needed.
• Over-verbose answers and answers with contradictory content will be penalised.
• You should download the Answer Book Word template file. Type in or copy all your answers
into the designated space in the Answer Book.
Submission Method
• You should only submit the Answer Book (in PDF format) with your answers entered in the
answer boxes.
o Optionally you may submit also the original Word document of the Answer Book
• You are normally allowed to submit only once before the end of the prescribed deadline for
submission at the OLE.
Good Luck Students!

NOTES ABOUT THIS PRACTICE ASSIGNMENT
The aim of these exercises and practices is to show you the format of the short and long questions in the
take-home assignment so that you can be better prepared.
The sample questions shown here have no relation to the questions in the real assignment paper, both in
content and in difficulty level. The real paper is open-book and may contain more open-ended and
challenging questions which are not shown here. The open-ended questions may take you more time
(of course some may think otherwise).
The most challenging open-ended problem-solving questions are not included.
You should answer in the Answer Book in the actual take-home assignment
COMPS267F (PRACTICE ASSIGNMENT)
COMPS267F (2200) PRACTICE ASSIGNMENT Page 3 of 26

Part 1
(a) Write down any suitable performance requirement on desktop systems.

(b) Write down any service provided by typical operating systems in the aspect of process
management.

(c) Define CPU bound processes in the context of program execution.

(d) In a single-processor, single-programming system, three IO bound processes are created at the
same time and ready for execution. The turnaround time of each process is expected to be 20
ms in a single programming environment and each would spend 10% using the CPU. Assume
that there is no context-switching overhead.
(i) Apart from the New state and the Terminate state, which other three states would the
three processes spend time in?
(ii) Which of the three states would all three processes definitely spend the same amount of
time?
(iii) Which component of the operating system is responsible for selecting the process to
use the processor?
(iv) Estimate the best CPU utilization rate during the execution of the three processes.
(v) If the same three processes were executed in a single-processor, multi-programming
system, would the best CPU utilization rate change? Justify your answer.

(e) State a major difference between preemptive and non-preemptive scheduling (in fewer than 30
words). Give one example CPU scheduling algorithm that is based on preemptive scheduling.

(f) Compare the following two CPU scheduling algorithms. Describe which performance
aspect(s) would differ significantly. Justify your answer.
Algorithm A: Round-Robin (RR) with time quantum of 10 ms.
Algorithm B: Round-Robin (RR) with time quantum of 1 ms.
COMPS267F (PRACTICE ASSIGNMENT)
COMPS267F (2200) PRACTICE ASSIGNMENT Page 4 of 26

Part 2

(a) A barbershop consists of a waiting room with n chairs; and the barber room containing the
barber chair.
• If there are no customers to be served the barber goes to sleep.
• If a customer enters the barbershop and all chairs are occupied, then the customer leaves
the shop.
• If the barber is busy, then the customer sits in one of the available free chairs.
• If the barber is asleep, the customer wakes the barber up.

Fill in the blanks in the following program with the appropriate semaphores that coordinate the
barber and the customers.

Shared data structures:
var barber, wait: semaphore; {initially = 0}
entry: semaphore; {initially = 1}
count: integer; {initially = 0}

Code for the barber is:
repeat
wait(barber);
“shave”
until false;

Code for a customer process:
wait( __________ );
if count = n
then exit;
count := count + 1;
if count > 1
then
begin
signal( __________ )
wait( __________ );
end
else
signal( __________ );
signal( __________ );
“shave”
COMPS267F (PRACTICE ASSIGNMENT)
COMPS267F (2200) PRACTICE ASSIGNMENT Page 5 of 26

wait( __________ );
count := count – 1;
if count > 0
then
signal( __________ );
signal( __________ );


(b) The following table shows the current state information of different processes with the units of
resource allocated and demanded to complete the process.
Assume there is only 1 unit of resource available at the moment, state whether this is a safe state.
Justify your answer.

Process Allocation Max
P1 1 4
P3 4 6
P5 5 8
P7 0 2

(c) Access-List and Access-Group are two file access protection schemes. State their differences.

(d) Explain the meaning of a device independent I/O system. Discuss how it is related to the
concepts of logical and physical devices.
(e) Consider the following segment table.

Segment Base Length
0 219 600
1 2321 14
2 90 100
3 1230 580
4 1990 96
What are the physical addresses for the following logical addresses?
(i) (2, 90)
(ii) (3, 200)
(iii) (4, 100)

COMPS267F (PRACTICE ASSIGNMENT)
COMPS267F (2200) PRACTICE ASSIGNMENT Page 6 of 26

(f) Write down True or False for each of the following statements about threads.
[2]
(i) A thread can have many processes.
(ii) A thread has its own program counter.
(iii) Context switching between threads is more efficient than that of processes.
(iv) Kernel-level threads are managed directly by the operating system kernel.

COMPS267F (PRACTICE ASSIGNMENT)
COMPS267F (2200) PRACTICE ASSIGNMENT Page 7 of 26

Part 3

(a) First-come-first-serve (FCFS) is a relatively simple CPU scheduling algorithm. Consider that
there are two multi-programming systems A and B. System A executes mostly CPU bound
processes, and system B executes mostly IO bound processes. Which system would be best to
demonstrate the benefits of using FCFS? Explain your answer.
(b) Assume that the memory access time is 200 ns (i.e. 0.2 μs), and the page-fault handling time is
20 ms. Assume that the page fault rate is 0.00001, evaluate the effective memory access time.

(c) Chris has found that his computer has a problem. Anders suggests that the problem is called
thrashing, and he recommends to Chris to execute fewer programs at the same time. Chris asks
you to explain further to him about thrashing, and to tell him if Anders' solution is correct.

(d) Suppose the effective memory access time is 20 ns on a cache hit and 100 ns on a cache miss.
Calculate the hit rate to achieve an average effective memory access time of 60 ns?

(e) What special hardware support is needed for the implementation of a segmentation-based
memory management system? Explain how this hardware is used in translating a logical address
with segment number S and offset D.

(f) Explain the reason why users can more likely use the most up-to-date software with software-
as-a-service (SAAS) cloud computing service.

(g) Describe any two benefits of Computer Clusters for mission critical systems such as the patient
management system of a hospital. Justify your answers.

(h) Define what is locality of references in memory access. Give an example of programming
structure or construct that leads to locality of references.



COMPS267F (PRACTICE ASSIGNMENT)
COMPS267F (2200) PRACTICE ASSIGNMENT Page 8 of 26

Part 4
(a) An operating system processes the following virtual pages:
2, 4, 1, 3, 4, 5, 6, 5, 5, 2, 6, 3
Determine the number of page faults using the last-in-first-out (LIFO) replacement. LIFO is a
new algorithm that replaces the latest current page with the new page. You must show
graphically each frame when each page is accessed. Assume this system has a physical memory
of four (4) frames and all of them are initially empty.

(b) One way to minimize page fault handling time in a virtual memory system is to reduce the copy
out, which refers to the operation to copy a page to the backing store. This could be achieved by
copying out only the modified pages. Can we do more? Consider the possibility of reducing
the possibility of a page being modified. Discuss the feasibility.

(c) These processes are found in the ready list with their arrival time and CPU burst time given in
the following table.
Process Arrival Time (ms) Burst Time (ms)
P1 0 350
P2 0 125
P3 0 475
P4 0 250
P5 0 75
For each of the following process scheduling algorithms, derive a Gantt chart. In addition,
calculate the turn-around time of each process.
Note: In case of a tie, process with a smaller ID has a higher priority (i.e. P1 has higher priority
than P4).
(i) First Come First Serve (FCFS)
(ii) Non-preemptive Shortest Job First (SJF)
(iii) Round Robin (RR) with a time quantum of 50 ms.
(d) Describe the items that comprise a semaphore.

(e) You are developing a video editing software called OpenVideoEditor. The software size is
found to be very large because it is offering over 500 user functions to make it the best editor on
the market. It takes a long time to start the software.
Your partner is suggesting the technique of dynamic loading to solve the problem. In the
following space, discuss whether you agree with the suggestion by referring to the editor.
• Explain dynamic loading.
• State whether you agree or disagree.
• Justify your answer. If you disagree, explain why it cannot solve the problem. If you
agree, explain how the technique can solve the problem.


COMPS267F (PRACTICE ASSIGNMENT)
COMPS267F (2200) PRACTICE ASSIGNMENT Page 9 of 26

Part 5

(a) A paging system supporting virtual memory uses a 32 bit logical address with a 20 bit page
table field and 12 bit offset field. The physical memory size is 1G (i.e. 230) bytes.
(i) Determine the number of entries in the page table (i.e. the number of rows) and also
determine the size of each frame and the number of frames in this system.
(ii) Explain how the logical address 0010200716 is translated into physical address.
(iii) Determine the number of entries in the frame table
(iv) A certain process is known to occupy 8 pages of logical memory. The process is allocated 2
physical frames. Explain why this arrangement is feasible in a virtual memory system.
(v) The process in the above part is known to cause thrashing. Describe a solution to solve the
problem.
(b) Explain the cause of internal fragmentation.

(c) The following table specifies the current resource allocation status of several processes in a
multi-programming system. There are three resource types. State whether the system is in a
safe state. Justify your answer.

Process Allocation Max
P1 0 1 0 1 3 1
P2 0 0 1 0 2 1
P3 0 0 0 2 0 0
P4 1 0 0 1 1 2
P5 1 0 1 1 3 3
Available = 0 2 1

(d) Suppose that the head of a moving-head disk with 200 tracks, numbered 0 to 199, is currently
serving a request at track 80 and has just finished a request at track 130. The queue of requests
is kept in a FIFO queue as the following.
68, 74, 17, 95, 100, 128
Calculate the total number of head movements (in terms of tracks traversed) needed to satisfy
these requests for the following disk-scheduling algorithms.
Illustrate the head movement either graphically or other means.

(i) SCAN scheduling
(ii) C-SCAN scheduling (service during downward movement only)
(iii) SSTF

COMPS267F (PRACTICE ASSIGNMENT)
COMPS267F (2200) PRACTICE ASSIGNMENT Page 10 of 26

(e) What is the most important advantage of the Shortest Job First (SJF) algorithm? Describe any
three weaknesses in this algorithm when used in practical systems and discuss whether the
algorithm suitable for time-sharing systems.







[END OF PRACTICE ASSIGNMENT]



COMPS267F (PRACTICE ASSIGNMENT)
COMPS267F (2200) PRACTICE ASSIGNMENT Page 11 of 26

Appendix: Useful Conversion Tables

Units and Magnitudes

1 byte = 8 bits
1 Kbytes = 1024 bytes = 210 bytes
1 Mbytes = 1048576 bytes = 220 bytes

1 hour = 60 mins
1 min = 60 seconds (s)
1 ms = 10-3 s
1 µs = 10-6 s
1 ns = 10-9 s

10-3 milli (m)
10-6 micro (µ)
10-9 nano (n)

Base 16-2-10 Conversions

Hex Binary Decimal
0 0000 0
1 0001 1
2 0010 2
3 0011 3
4 0100 4
5 0101 5
6 0110 6
7 0111 7
8 1000 8
9 1001 9
A 1010 10
B 1011 11
C 1100 12
D 1101 13
E 1110 14
F 1111 15

Powers of 2

2-5 = 0.03125 20 = 1 25 = 32 210 = 1024
2-4 = 0.0625 21 = 2 26 = 64 211 = 2048
2-3 = 0.125 22 = 4 27 = 128 212 = 4096
2-2 = 0.25 23 = 8 28 = 256 213 = 8192
2-1 = 0.5 24 = 16 29 = 512 220 = 1048576
221 ~ 2M 222 ~ 4M 223 ~ 8M 224 ~ 16M
225 ~ 32M 226 ~ 64M 227 ~ 128M 228 ~ 256M
229 ~ 512M 230 ~ 1G 231 ~ 2G 232 ~ 4G

[END OF APPENDIX]