ITSA2003 Network Operating System & Configuration: Algorithm Analysis

This document provides a detailed solution to a Network Operating System and Configuration assignment. It includes a step-by-step application of Banker's Algorithm, explaining the process of determining safe states for processes. Furthermore, it elaborates on program execution steps, highlighting the use of MAR and MBR registers. The document also discusses page replacement algorithms such as FIFO, Optimal, and LRU, including their advantages and disadvantages. Additionally, it defines basic terms like live lock, race condition, and deadlock with real-world examples. Finally, it explains the concept and characteristics of an algorithm and provides a solution for Round Robin scheduling algorithm with average waiting time calculation. Desklib offers this and many other solved assignments and past papers to aid students in their studies.

Network Operating Systems and
configuration

1 | P a g e
Table of Contents
Answer 1: Bankers Algorithm...............................................................................................................1
Answer 3: Page replacement............................................................................................................5
Answer 1: Basic Terms..........................................................................................................................5
Answer 2: Concept of an algorithm....................................................................................................7
Characteristics of an Algorithm.........................................................................................................7
Answer 3 : Round robin scheduling algorithm......................................................................................7

2 | P a g e
Task 1
Answer 1: Bankers Algorithm
Given:
Allocation
Process R0 R1 R2 R3
P0 2 0 1 2
P1 0 1 2 1
P2 4 0 0 3
P3 1 2 1 0
P4 1 0 3 0
Maximum
Process R0 R1 R2 R3
P0 3 2 1 4
P1 0 2 5 3
P2 5 1 0 5
P3 1 4 3 0
P4 3 0 3 3
Available =
0 2 2 2
Firstly calculated the need that is Maximum- Allocation
Need
Process R0 R1 R2 R3
P0 1 2 0 2
P1 0 1 3 2
P2 1 1 0 2
P3 0 2 2 0

3 | P a g e
P4 2 0 0 3
Now calculating that Po will execute or not; the need of P0 is compared with the available slot.
Need <= Available
1202<= 0222 (This is not true)
Thus, Po should wait
Now calculating that P1 will execute or not; the need of P1 is compared with the available slot.
Need <= Available
0132<= 0222 (This is true)
Thus, P1 is kept in safe state
Future calculating the work,
Work= Work + Allocation
Work (P1)= 0222+0121
= 0343
P1 is executed
Now calculating that P2 will execute or not; the need of P2 is compared with the available slot.
Need <= Available
1102<= 0343 (This is not true)
Thus, P2 should wait
Now calculating that P3 will execute or not; the need of P3 is compared with the available slot.
Need <= Available
0220<= 0222 (This is true)
Thus, P3 is kept in safe state
Future calculating the work,
Work= Work + Allocation
Work (P3)= 0343+1210
= 1553
P3 is executed
Now calculating that P4 will execute or not; the need of P4 is compared with the available slot.
Need <= Available
2005<= 1553 (This is not true)
Thus, P4 should wait

4 | P a g e
Now, again calculating that P0 will execute or not; the need of P0 is compared with the available
slot.
Need <= Available
1202<= 1553 (This is true)
Thus, P0 is kept in safe state
Future calculating the work,
Work= Work + Allocation
Work (P0)= 1553+2012
= 3565
P0 is executed
Now calculating that P2 will execute or not; the need of P2 is compared with the available slot.
Need <= Available
1102<= 3565 (This is true)
Thus, P2 is kept in safe state
Future calculating the work,
Work= Work + Allocation
Work (P2)= 3565+4003
= 7568
P2 is executed
Now calculating that P4 will execute or not; the need of P4 is compared with the available slot.
Need <= Available
2003<= 7568(This is true)
Thus, P4 is kept in safe state
Future calculating the work,
Work= Work + Allocation
Work (P4)= 7568 + 1030
= 8598
P4 is executed
Thus, the Sequence is P1 P3 P0 P2 P4

5 | P a g e
Answer 2: Program execution
The six steps are described as follows:
A. The value of Program counter is PC=
300(Given) Thus, the address of the first
instruction is 300.This value is loaded in
MAR.
B. B. The value in location 300 is loaded in
MBR. The value of Pc is incremented
from 300 to 301. These two steps can be
done parallel.
C. The value of MBR is loaded in IR
A. The ADDRESS PORTION OF IR(940)
is loaded into MAR
B. The value in location 940 is loaded in
MBR
C. The value of MBR is loaded into AC
A. The value of PC (301) loaded in MAR
B. The value in location 301 is loaded in
MBR, PC is incremented.
C. The value of MBR is loaded in IR
A. Address portion of IR (941) is loaded in
MAR.
B. Value in location 941 is loaded in MBR
C. The old value of AC and the value of
location MBR are added and the result is
stored in AC
A. Value in the PC (302) is loaded in MAR.
B. The value in location 302 is loaded into
A. Address portion of IR (941) is loaded in

6 | P a g e
MBR, PC is incremented.
C. The value of MBR is loaded in IR
MAR.
B. Value in AC is loaded in MBR
C. The value in MBR is stored in location 941.
Use of MAR- It is used to hold the memory location of data so that it can be accessed whenever it is
needed. It is a CPU register that stores the memory address from the data so that it can be fetched
from the CPU.
Use of MBR- It contains the copy of memory location and copies the data item to MBR. It act as a
buffer that allows the processor and memory units to act as independent units.
Answer 3: Page replacement
These algorithms are used to decide which page is needed to be replaced when new pages enters the
system. Whenever new page enter the system and there is no memory available then page fault
occurs (Lee, Bahn & Noh, 2014). Operating system then uses the existing page by replacing it
with the new page. There are various page replacement algorithms that are available so that number
of page faults gets reduced. The different page replacement algorithms that are available are: First in First Out- It is a simplest form of page replacement algorithm in which it
keeps track of all the pages and keeps the oldest page at first position in the queue.
When the queue is full and ne page enters the first page is replaced (Zhan, Zhang,
Jiang, Yang, Li and Li, 2018).
Advantage and disadvantage- It is easy to understand but it is not very effective. It
has a very slow process execution rate and also increases the chances of page fault
(Tsai and Lei, 2017).
 Optimal Page replacement- It is an algorithm in which the page that has less
probability of being used in future is replaced. It is used to set a benchmark so that
other replacement algorithm can be compared and analysed (Zhan, Zhang, Jiang,
Yang, Li and Li, 2018).
Advantage and disadvantage- It is useful as it has lowest page fault rate and it never
suffers from the issue of Belady’s anomaly. It is difficult to implement and need
future knowledge to take any actions.
 Least Recently Used- The page that is used very least is replaced with the new page.
It uses the principal of locality like replacing the page which is less likely to be
referenced in the near future (Tsai and Lei, 2017).
Advantage and disadvantage- It also never suffer from Belady’s anomaly and
assembles full statically analysis (Wu, Jin, Yang and Yue, 2014).
Task 2
Answer 1: Basic Terms
Some of the terms are explained by considering one general human example is:
o Live lock- The concept of live lock is similar to deadlock; the only difference
in live lock is that state of processes keeps on changing with respect to other

7 | P a g e
processes (Hu, Neamtiu & Alavi, 2016). It is a case off resource starvation
but it generally occurs when specific process is not progressing (Yu, Srisa-an,
& Rothermel, 2017).
Example- The real life example of live lock is when two humans collide in a
narrow corridor. There is a very little space for both the individuals to pass
together from the corridor. But if both the individuals adjust a little by
moving side the issue could be resolved (Gao & Xu, 2015). But while
moving aside they end up swaying with each other without making any
progress.
o Race Condition- It is an unwanted condition that occurs when two or more
operations are performed by the system at the same time. It causes can issues
as a proper sequence needs to be followed for completing the operations
correctly. Apart from that in computer system this issue arise at the time of
entering commands. The wrong sequence can overwrite the commands and
may cause error (Qin & Jin, 2015).
Example- A human related example that can explain this situation is
condition of light switch. In offices or homes, many light switches are
connected from a same celling light. Thus, irrelevant position of the switches
may cause wrong output. The problem will arise when two individuals are
using the switch at the same time. Thus, their actions will cancel out and no
result would be obtained.
o Deadlock- It is a situation when other the system requires the same resource
at the same time. Deadlock is a condition that prevents both the user to access
the resources. In terms of computer science, deadlock is a condition when
two or more processes are waiting for the resource to be released by other
process.
Example- The traffic of vehicles sometimes led to condition of deadlock.

8 | P a g e
As shown above, all the vehicle need to cross the way but waits for the other vehicle to clear
the way. Thus, traffic gridlock is an everyday example of a deadlock situation.
Answer 2: Concept of an algorithm
An algorithm is a step by step procedure that is used to solve a particular problem. A computer
program can also be viewed as an algorithm as it is a procedure that is used to resolve the problem.
The concept of algorithms is widely used in all the sectors of information technology (Gatys, Ecker
& Bethge, 2015). It can be said as a well-defined process that is adopted to solve a problem. It is an
effective method that is used to express all the finite amount of space and time. An algorithm is
mostly used in data processing, calculations and other computer related operations. An algorithm
mainly manipulates the data so that repeated task can be performed by simply entering the input data.
It is a detail series of instructions that are used to solve the problem. In computers, algorithms are
used to accomplish the task so that the task can be solved. It is a sequence of computational steps that
are used to perform complex tasks (Gulshan, et. al, 2016). It can be said as a set of instructions that
are designed to perform specific task. The methods of algorithm design form one of the core
practical technologies of computer science and an algorithm can be specified by the algorithm. It is a
synonym for finite computational method so that it fitness best in the property. They are created
independently in more than one programming language (Wen, Shao, Xue & Fang, 2015).
Characteristics of an Algorithm
The algorithms are unambiguous in nature as all the inputs are clear so that it may lead to clear
meaning. It has well defined inputs so that desired output could be obtained. One of the important

9 | P a g e
characteristics is that algorithm should terminate after finite steps (Wen, Shao, Xue & Fang,
2015).
Answer 3 : Round robin scheduling algorithm
Calculating Average waiting time
Given,
Quantum=25 time units.
Process Burst Time
P1 62
P2 14
P3 28
P4 81
P5 39
Gantt Chart
P1 P2 P3 P4 P5 P1 P3 P4 P5 P1 P4 P4
0 25 39 64 89 114 139 142 167 181 193 218
224
Process Arrival time Burst time Completion time Waiting time
P1 0 62 193 131
P2 25 14 39 0
P3 39 28 142 75
P4 64 81 224 79
P5 89 39 181 53
Average waiting time= Waiting time of all processes/ Number of processes
=131+75+75+ 53+0/5
=67.6

10 | P a g e
References
Gao, Q., & Xu, M. (2015). U.S. Patent No. 9,052,967. Washington, DC: U.S. Patent and
Trademark Office.
Gatys, L. A., Ecker, A. S., & Bethge, M. (2015). A neural algorithm of artistic style. arXiv
preprint arXiv:1508.06576.
Gulshan, V., Peng, L., Coram, M., Stumpe, M. C., Wu, D., Narayanaswamy, A., ... & Kim,
R. (2016). Development and validation of a deep learning algorithm for detection of
diabetic retinopathy in retinal fundus photographs. Jama, 316(22), 2402-2410.
Hu, Y., Neamtiu, I., & Alavi, A. (2016, July). Automatically verifying and reproducing
event-based races in android apps. In Proceedings of the 25th International
Symposium on Software Testing and Analysis (pp. 377-388). ACM.
Lee, S., Bahn, H., & Noh, S. H. (2014). CLOCK-DWF: A write-history-aware page
replacement algorithm for hybrid PCM and DRAM memory architectures. IEEE
Transactions on Computers, 63(9), 2187-2200.
Qin, L. I. U., & Jin, C. H. E. N. (2015). Job-Shop Scheduling with Parallel Equipments
Based on Five Dimensions Scheduling Algorithm. Journal of Jiangnan University
(Natural Science Edition), 1, 010.
Tsai, H.B. and Lei, C.L., 2017, April. A page replacement algorithm based on frequency
derived from reference history. In Proceedings of the Symposium on Applied
Computing (pp. 1522-1527). ACM.
Wen, X., Shao, L., Xue, Y., & Fang, W. (2015). A rapid learning algorithm for vehicle
classification. Information Sciences, 295, 395-406.
Wu, Z., Jin, P., Yang, C. and Yue, L., 2014, September. APP-LRU: a new page replacement
method for PCM/DRAM-based hybrid memory systems. In IFIP International
Conference on Network and Parallel Computing (pp. 84-95). Springer, Berlin,
Heidelberg.
Yu, T., Srisa-an, W., & Rothermel, G. (2017). An automated framework to support testing
for process‐level race conditions. Software Testing, Verification and
Reliability, 27(4-5), e1634.
Zhan, J., Zhang, Y., Jiang, W., Yang, J., Li, L. and Li, Y., 2018. Energy-aware page
replacement and consistency guarantee for hybrid NVM–DRAM memory
systems. Journal of Systems Architecture, 89, pp.60-72.