Answer :

In this assignment task, we will demonstrate and identify the deadlocks and synchronisation process. The assessment has three parts where we determine and analyse an operating system and some concerns related to logical issues with system. We also work on resolving the issues and identify the possible implications. 

TASK – 1 

Memory management – memory management is a feature of operating system that handle primary memory and return the process back, works between disk and main memory while execution of a process. It keeps track of each and every memory location either it is allocated to any process or not (free memory). Memory management decide which process and to what time a memory block is to be assign. When the memory blocks are free, it collects those and update their status. Every memory block has a process address space. It is a logical reference address code. The operating system manages the mapping of these logical address space with physical address space while allocating a memory block to a process (Operating System - Memory Management - Tutorialspoint, 2020). There are total of three types of address spaces work here, that are – 

1. Physical address – this address generates at the time, program is loaded in to the main memory.
2. Symbolic address – these are used s source code. It includes constants, variable names, labels and some basic elements. 
3. Relative address – while compiling process, the symbolic addresses are converted into relative addresses.

Logical addresses are the addresses that are generated by a program and the addresses referred to these logical addresses are called physical address. the main memory has two parts, as: high memory, which handles user processes and Low memory, where an operating system is resides. For memory allocation, an operating system uses these two memory allocation mechanisms – 

1. Multiple partition allocation – in this type of memory allocation, main memory is divided into some fixed size partitions. Each partition here, contains one process. Whenever a memory partition is free, a queued process is loaded into that freed partition. When a process complete or terminated, the freed partition available to other processes.
2. Single partition allocation – this memory allocation process uses relocation register scheme which protects user processes from each other, changing operating system data and codes. The relocation register contains values of a smallest physical address. There are a range of logical addresses contained by a logical register. Every logical register is lesser than the limit register.

Virtual memory – an operating system is capable to assign more memory than the installed one on the system. This additional memory is called as virtual memory. It is a part of the hard disk that is configured to use as RAM of the system. The process of translating a virtual address into physical address is called mapping. While copying virtual contents from hard disk to main memory is called swapping or paging. As the ultimate advantage of this virtual memory, a running program can use more then the physical installed memory. The virtual memory has two main advantages, as: it allows us to extend the physical memory and it protect the memory by using virtual addresses that are mapped to some physical addresses. There are so many conditions, when a program will not fully be loaded into main memory and an operating system needs virtual memory. For example, while error handling situation, program features are not in use fully, not enough number of I/O free while a process is executing, etc. (Operating System - Virtual Memory - Tutorialspoint, 2020)

The memory management unit or MMU is built into the hardware. This memory management unit works in translating virtual addresses into physical addresses. Several schemes or algorithms are used to allocate virtual memory, as demand paging, segmentation or demand segmentation. Here is the brief description of these – 

• Demand paging – it is somehow similar to paging system combined with swapping. In this process, processes are residing in to secondary memory and loaded only when demanded. When, there is need to execute a program and its contents are not found in the main memory due to its swapped out from the memory, the processor than treat this process as invalid memory references, called as page fault. Then it transfers its control to the operating system and demand to load that page or contents into main memory. 

TASK – 2

Given details – 

Here are the waiting time and turnaround time of each processes, responding to each scheduling algorithm – 

The Formula to Calculate the Turnaround Time = Completion Time – Arrival Time.

The Formula to Calculate the Waiting Time = Turnaround Time – Service Time.

(ProQuest Ebook Central, 2020)

i) Feedback (FB) q=3

This algorithm is somehow similar to MLQ scheduling algorithm but it can move between the process queues. It analyses the behaviour of the processes and according to change their priority. 

Chart for Feedback q = 3 – 

0                                                                        3                                                                       11                                                                     14                                                                     28                                                              30

Calculation steps –

• Since the Process A arrived First, it started to execute and after 3 units gets completed. Thus the Completion Time for a is 3. Hence its Turnaround Time is 3 and Waiting Time is 3.
•  Now Process B has arrived at 3 units and takes 8 units of Service time and gets completed at 11 units. Hence its Turnaround Time is 8 and Waiting time is 0.
• Process C also arrived at 3 units and is waiting in the Ready que since Process B was running, it takes 3 units and gets completed at 14 units. Hence its Turnaround time is  11 and Waiting Time is 8.
• Now Process D and E has arrived at 7 units but firstly Process D will be Executed.
• Process D takes service time of 14 units and gets completed at 28 units. Hence its Turnaround Time is 21 and Waiting Time is 7.
• Now Process E is executed and it takes 2 units of service time and gets completed at 30 units. Hence its Turnaround Time is 23 and Waiting Time is 21. 

 ii) Highest Respond Ratio Next (HRRN)

It is one of the most optimal scheduling algorithms which works on non-primitive algorithm for scheduling purposes. It determines scheduling based on response ratio. So, we need to have a response time for every process and a priority order of the jobs. To calculate response ration, we use the below formula – 

RR = (W+S)/S

Chart for HRRN –

0                                                                        3                                                                       6                                                                        14                                                                     16                                                              30

Calculation steps – 

• The Processing gets started from A and gets completed after 3 units. Its Turnaround time is 3 and Waiting time is 0.
• Then we have Process B and Process Present in the que so we took Response Ratio of both where C gets higher ratio so c is executed first.
• After 2 units it gets completed at 6 and Process B is executed which gets completed at 14 units. Turnaround and Waiting time for C is 3 & 0 and for B is 11 & 3 respectively. 
• Now Process D and E are present in the que so we again took Response ratio of both where E has higher Response Ratio so it will be executed first and completed at 16 and now D is executed which gets completed 30.
• Turnaround and Waiting time for D is 23 & 9 and for E is 9 & 7 respectively.

iii) Round Robin (RR) q=4

This algorithm also works as primitive algorithm. Every process in the round robin scheduling, is assigned a fix execution time. Once the execution of process starts, it pre-empted and another process will start within a given time. To save process state, context switching method is used. 

Chart for RR –

0                                    3                                                       6                                                      10                                                   14                                                    16                                                   20                                      30

Calculation steps – 

• Here we have Time Quantum of 4 units. We started by execution of Process A which gets completed at 3 units and Process B and C has arrived.
• Since C has high Priority than B so C is executed first and gets completed at 6 units, now B is executed and works for 4 units and remaining 4 units are added in the que but when B is working Process D and E were present in the que so we need  to put D and E before B in the ready que.
• Now D is executed and works for 4 units thus remaining of its 10 units are sent in que (after B). Then E is executed which works for 2 units and gets completed at 16 units.
• The remaining B and are Executed then and gets completed at 20 and 30 respectively.

iv) Shortest Remaining Time (SRT)

SRT is a primitive version of SJF scheduling algorithm. In SRT algorithm, process execution is stopped after a certain time period. When a new process has arrived, SRT schedule the process with least burst time, from the process queue.  

Chart for SRT –

0                                                            3                                                           6                                                          7                                                            9                                                          16                                                    30

Calculation steps – 

• The Process gets Started from A and gets completed at 3 units since no other process is scheduled in between 0 to 3. So it has Turnaround time of 3 and Waiting time of 0.
• Now Process B and C arrived at 3, where C is executed and B will be placed in the que since C have lower Service time. C works for 3 units and gets completed at 6, thus its Turnaround time is 3 and Waiting time is 0.
• After that B is executed and works for 1 unit and remaining 7 units will be added to the que. Now at 7 Process D and E have arrived, here E will be executed because of lower Service time. E works for 2 units and gets completed at 9 so its Turnaround time is 2 and Waiting time is 0.
• Process B have lower service time than D so it will be executed first. B works for 7 units and gets completed at 16 so its Turnaround time is 13 and Waiting time is 5.
• D works for 14 units and gets completed at 30. Thus Turnaround time is 23 and Waiting time is 9.

v. Shortest Process Next (SPN)

This algorithm works by sorting all the processes by their arrival time. Then select a process which has min arrival time and min burst time. Here are the details of the whole process. 

Chart for SPN –

0                                                                       3                                                                       6                                                                        14                                                                     16                                                              30

Calculation steps – 

• A arrives First and works for 3 units to get completed. Hence its Turnaround Time is 3 and Waiting time is 0.
• After that B and C are present in the que and since Service time of C is less so it will be executed and gets completed at 6. So its Turnaround Time is 3 and Waiting time is o.
• Than B is executed and works for 8 units and gets completed at 14. So Turnaround Time is 11 and Waiting time is 3.
• Now D and E are present in the que and since E has low service time so it will be executed. E works for 2 units and completed at 16. Turnaround time is 9 and Waiting time is 7.
• At last D is executed and gets completed at 30. Turnaround Time is 23 and waiting time is 9.

TASK – 3

Answer to the question based on the provided resource graph:

a. Is the system deadlocked?

Ans.  – Yes, the system is deadlocked.

b. Which, if any, processes are blocked?

Ans. – the P3 process is blocked here.

c. What is the resulting graph after reduction?

Ans. – here is the resulting graph after reduction – 

Figure: resulted graph after reduction

Details of calculation – in the provided resource graph, a resources R1 and R2 are assigned to process P2 while the resource R2 is used by process P1 and depends on resources R1. The process P3 uses resource R2 but depends on resources R3, R4 and R5. When the process P1 starts, it uses R1 but also depends on R2. When process P2 starts, it uses R3 but depends on R1 and R2 to free up. Till time it starts its work, R1 and R2 will be freed and no deadlock is created. When process P3 starts, it uses R2 that is already in use by P2. P3 is also depend on R3, R4 and R5. Here process P3 creates a deadlock when it didn’t get the required resources to complete the process.