1. Overview

This assignment focuses on the concepts of Synchronisation, Deadlocks, CPU Scheduling, Memory Management / Virtual Memory and File Systems.

2. Learning outcomes

This assessment is relevant to the Course Learning Outcomes CLOs 2, 4, 5 and 6.

3. Assessment details

This assessment will determine your ability to

1)  Understand the concepts taught during weeks 4 through 11 of the course.

2)  Work independently in self-directed study or collaboratively with your teammate to answer all the questions in your own words.

4.  Academic integrity and plagiarism

It is understood by us that many of the algorithms used in this course have common implementations. You are welcome to look at online code examples to understand possible solutions to the set problems. However, what you submit must be your own work and your submission will be checked and compared with other solutions.

Submitting material generated by an AI tool as your own work constitutes plagiarism and academic dishonesty. DO NOT simply copy other people's work, it is not difficult for us to detect copied work, and we will pursue such cases.

5. Individual work

This assignment is individual assignment. That means you MUST complete this assignment individually.

6. Submission

Prepare the answers to this assignment in an electronic format and convert to a single Acrobat PDF (.pdf) file for submission, with the filename being your student number (e.g., S1234567.pdf) containing all the answers to all the questions in this assignment. Paper submissions are not accepted.

Your assignment should submit via Canvas → Assignments → Written Assignment 2.

It is your responsibility to correctly submit your files. Please verify that your submission is correctly submitted by downloading what you have submitted to see if your submitted file includes the correct content. Never leave submission to the last minute – you may have difficulty uploading files. You can submit multiple times – a new submission will override any earlier submissions.

However, if your final submission is after the due time, late penalties will apply.

7. Late submission and extension policy

A penalty of 10% per day of the total available marks will apply for each day being late. After 10 days, you will receive zero marks for the assignment.

If you want to seek an extension of time for assignment submission, you must have a substantial reason for that, such as unexpected circumstances. Reasons such as, unable to cope with study load, is not substantial. Also, you must apply for an extension as soon as possible. Last minute  extensions cannot be granted unless it attracts special consideration.

Please find out how to apply for special consideration via this link.

Any student wishing an extension must go through the official procedure for applying for extensions and must apply at least a week before the due date. Do not wait till the submission due date to apply for an extension.

8. Assignment questions

This assignment has 18 questions from four topics and students are required to answer all questions. Those topics are:

1)  Synchronisation and Deadlocks (week 4, 5 and 6)

2)  CPU Scheduling (week 7)

3)   Memory Management / Virtual Memory (week 8, 9 and 10)

4)   File Systems (week 11)

Tips:

1)   Do not copy from lecture notes or any other sources.

2)   Use your own words and clearly demonstrate your understanding.

3)  The marking guide is designed in alignment with the course content. Your answers should focus on the material covered in this course.

Word Limit: 30 x N, where N being the number of the marks for the question.

For short answer questions, it is generally recommended to keep your answer concise. This helps maintain clarity and ensures that the response is both informative and to the point.

Provide one or two sentences PER MARK, typically ranging from 10 to 20 words per sentence, with no more than three sentences in total.

In average, ONE MARK is 30 words. For a question of N marks, the word limit is 30 x N. For example, if the question is worth 3 marks, the word limit for the question is 90 words. Slightly exceed the word limit will NOT lead to penalty.

Topic 1: Synchronisation and Deadlocks (30 marks)

1)  (4 marks) Explain what a race condition and a critical section are and how the two are related to each other.

2)  (5 marks) Explain whether there are atomic operations on a semaphore, how the atomic operations are implemented in a single processor system without hardware support, and whether the implementation is suitable for a multiprocessor system.

3)  (2 marks) Explain what “busy waiting” means and how it can be addressed in a semaphore.

4)  (4 marks) Write the pseudo code for a semaphore, which can show the number of threads waiting. Explain your code including how the semaphore works and how the waiting threads are recorded.

5)  (3 marks) Explain what problem(s) Condition Variables aim to address. Write pseudo code to demonstrate. Explain the code.

6)  (2 marks) Explain how a Monitor is implemented and works.

7)  (3 marks) Explain how the signal() operation associated with monitors differ from the corresponding operation defined for semaphores?

8)  Consider a system consisting of ten instances of the same resource that are shared by three processes, each of which needs at most four instances.

(a) (2 marks) Discuss whether the system is deadlock free.

(b) (5 marks) Compare the system performance between deadlock prevention and deadlock avoidance, assuming that it takes one time unit to consume an instance, and a process does not have to wait for other instances before consuming.

Topic 2: CPU Scheduling (17 marks)

1)   (2 marks) Five jobs are waiting to be run. Their expected run times are 10, 9, 5, 3, and 7. Assuming no pre-emption, what scheduling algorithm would you use, that is, in what order should they be run to minimise average waiting time? Calculate the average waiting time.

2)  (10 marks) Five batch jobs, A through E, arrive at a computer centre at the same time.

They have estimated running times of 10, 6, 2, 4, and 8 minutes. Their (externally determined) priorities are 3, 5, 2, 1, and 4, respectively, with 5 being the highest priority. For each of the following scheduling algorithms, determine the mean process turnaround time. Ignore process switching overhead.

a.  Round robin.

b.  Priority scheduling.

c.  First-come, first-served (run in the order of A through E).

d.  Shortest job first.

3)  (5 marks) You are tasked to design a scheduling system that needs to be able to handle computation intensive, interactive as well as real-time programs with soft guarantee.

Illustrate your design.

Topic 3: Memory Management / Virtual Memory (26 marks)

1)  (3 marks) Discuss the methods that reduce memory consumption.

2)  (4 marks) Discuss the address rendered directly from the CPU in relation to the actual memory address to be used.

3)  (3 marks) In a 32-bit system, assuming the frame size is 16KB, what is the maximum number of frames that the system may have? Identify the physical address for the first byte in frame 95 (note that frame number starts from 0).

4)  (3 marks) Discuss why paging is needed over segmentation.

5)  (10 marks) Assuming in a 32-bit system where large segments need to be supported, design a memory allocation solution for the system. Also assume the system supports segments up to 256KB and the page size is 4KB. Justify your design. Work out the address layout and explain how your solution works using the address layout.

6)  (3 marks) Assume in a system where TLB lookup takes t time units, memory access time is m time units and page-fault service time is s time units. Also assume that TLB hit ratio is h and page fault rate is p. Work out the effective access time (EAT).

Topic 4: File Systems (17 marks)