SRM Institute of Science and Technology

Mode of Exam
College of Engineering and Technology
School of Computing OFFLINE
DEPARTMENT OF COMPUTING TECHNOLOGIES
SRM Nagar, Kattankulathur – 603203, Chengalpattu District,
Academic Year: 2023 (ODD SET - C

Test: CLA-T2 Date: 07-10-2023

Course Code & Title: 18CSE356T & Distributed Operating Systems Duration: 1 Hour
40 Minutes
Year & Sem: III/IV Year / V/VII Sem Max. Marks: 50

Part - A
(1*10 = 10 Marks)
Instructions: Answer all
Q. Question Marks BL CO PO PI
No Code
1 The difference in time values of two clocks is called------ 1 L1 3 3 1.6.1
a) Clock drift
b) Clock skew
c) Clock Synchronization
d) Application Software

Answer: b) Clock skew

2 Which provides dialog control and synchronization 1 L1 2 2 1.6.1

facilities.
a) Presentation Layer
b) Session Layer
c) Data Link Layer
d) Network Layer

Answer: b) Session Layer

3 A “glue” between client and server parts of application is 1 L1 2 2 1.6.1

a) Middleware
b) Firmware
c) Package
d) System Software

Answer: a) Middleware
4 The _______ calls certain procedures on remote systems 1 L1 2 2 1.6.1
and is used to perform synchronous or asynchronous
interactions between systems.
a) Procedure
b) RPC
c) Message Oriented
d) DB
Answer: b) RPC
5 The local operating system on the server machine passes 1 L1 2 2 1.6.1
the incoming packets to the
a) Server Stub
b) Client Stub
 c) Client Operating system
d) Binding Agent

Answer: a) Server Stub

6 Absolute time synchronization can be achieved by 1 L2 3 3 1.6.1

a) Vector time stamping Method
b) Christian’s Method
c) Lamport’s Method
d) Richart – Agarwala Algorithm
Answer: b) Christian’s Method

7 Which algorithm requires “ 1 to ∞” messages to enter and 1 L2 3 3 1.6.1

leave a critical region?
a) Token Ring Algorithm
b) Centralized Algorithm
c)Decentralized Algorithm
d)Distributed Algorithm
Answer: a) Token Ring Algorithm

8 If timestamps of two events are same, then the events are 1 L1 3 3 1.6.1
_____
a) concurrent
b) non-concurrent
c) monotonic
d) non-monotonic
Answer: a) concurrent

9 Which is the following property of transaction ensuring 1 L2 3 3 1.6.1

that once transaction commits, the changes are
permanent?
a) Atomic
b) Consistent
c) Isolated
d) Durable
Answer: d) Durable

10 An aid to determine the deadlock occurrence is 1 L2 3 3 1.6.1

a) Resource Allocation Graph
b) Starvation Graph
c) Inversion Graph
d) None of the above
Answer: a) Resource Allocation Graph

Part – B (5*2=10 Marks)

Answer all 5 questions
11 Write any four-synchronization mechanism that are suitable for 2 L 2 2 1.6.1
distributed system? 3
Clock synchronization
• Event ordering
• Mutual exclusion
• Deadlock
• Election algorithms

12 What is mean by drifting of clocks? 2 L 2 2 1.6.1

As mentioned, no two clocks would have the same clock rate of 2
 oscillations i.e; clock rate would be different. The difference of clock
rate is called clock drift. Ordinary quartz clocks drifts by ~ 1 second in
11–12 days. The drift rate varies from clock to clock.
13 Discuss the principle of RPC between the client and server stub with an 2 L 3 3 1.6.1
example? 2
The client stub passes the message to the transport layer, which sends it
to the remote server machine. On the server, the transport layer passes
the message to a server stub, which demarshalls(unpack) the parameters
and calls the desired server routine using the regular procedure call
mechanism.
14 What are the two approaches of addressing and give some details about 2 L 2 2 1.6.1
it? 2
• Only one process can run on each machine, which is a serious
restriction

15 Write the two-phase locking concept in Concurrency control - locking? 2 L 3 3 1.6.1

A transaction is said to follow the Two-Phase Locking protocol if 3
Locking and Unlocking can be done in two phases.
1. Growing Phase
2. Shrinking Phase
Part – C (4*5=20 Marks)
Answer any 4 out of 6 questions
16 Write short notes on SONET with an appropriate example? 5 L 2 2 1.6.1
2
• SONET uses a basic transmission rate of 51.84 Mbps.
• It is a basic unit of consisting of 9 x 90 array of bytes called a
Frame.

SONET Network Elements:

17 How does ATM work? Explain with neat diagram 5 L 2 2 1.6.1
2

18 Explain Reliable and unreliable communication in transport protocol with 5 L 2 2 1.6.1

real time scenario. 3
• TCP guarantees reliable transmission even if packets are lost or
delayed.
• Packets must be acknowledged by the receiver– if ACK not
received in a certain time period, resend.
• Reliable communication is considered connection-oriented because
it “looks like” communication in circuit switched networks. One
way to implement virtual circuits
• Other virtual circuit implementations at layers 2 & 3: ATM, X.25,
Frame Relay, ..
• For applications that value speed over absolute correctness, TCP/IP
provides a connectionless protocol: UDP
• UDP = Universal Datagram Protocol
• Client-server applications may use TCP for reliability, but the
overhead is greater
• Alternative: let applications provide reliability (end-to-end
argument).

19 Infer the concept of Message Passing and its related issues? 5 L 3 3 1.6.1
Message Passing provides a mechanism to allow processes to communicate and 2
to synchronize their actions without sharing the same address space. For
example − chat programs on World Wide Web. Now let us discuss the message
passing step by step. Messages sent by a process can be either fixed or variable
 size.
Issues with IPC by message passing in distributed systems include
synchronization issues in blocking send, failure handling challenges, buffering
problems, network latency, delays and dropped messages, deadlocks, race
conditions and security concerns.

20 Discuss in detail about Nested Transaction with any real time scenario. 5 L 3 3 1.6.1
3
• The top-level transaction may fork off children that run in
parallel with one another, on different machines, to gain performance
or simplify programming.
• Each of these children may also execute one or more
sub transactions, or fork off its own children.
• Provide a natural way of distributing a transaction across multiple
machines.
• Follow a logical division of the work of the original transaction.
For example, a transaction for planning a trip by which three different
flights need to be reserved can be logically split up into three sub
transactions. Each of these sub transactions can be managed separately and
independent of the other two.

21 Describe about ACID properties. 5 L 3 3 1.6.1

• The characteristic feature of a transaction is either all of these 2
operations are executed or none are executed.
• This all-or-nothing property of transactions is one of the four
characteristic properties that transactions have.
– 1. Atomic: To the outside world, the transaction happens
indivisibly.
– 2. Consistent: The transaction does not violate system
invariants.
– 3. Isolated: Concurrent transactions do not interfere with
each other.
– 4. Durable: Once a transaction commits, the changes are
permanent.
 Part – D (1*10=10 Marks)
Answer any 1 question
22 What is meant by Deadlock and explain in detail about Deadlock Detection 1 L 3 3 1.6.1
and Prevention with real time example. 0 3
• A set of blocked processes each holding a resource and waiting to
acquire a resource held by another process in the set.
Example:
• System has 2 tape drives.
• P1 requests for one tape drive and the system allocates tape drive 1.
• P2 request for one tape drive and the system allocates tape drive 2.
• P1 request for one more tape drive and enter in waiting state.
• P2 request for one more tape drive and it also enter in waiting state.

Deadlock Prevention:
 Designing the system in a way that deadlock become impossible.
 Prevention is different from avoidance because no runtime testing
(dynamically) of potential allocations need be performed.
 Prevent the one of the four necessary conditions:
 Mutual exclusion condition
 Hold and wait condition
 No-Preemption condition
 Circular-wait condition
Mutual Exclusion
• Unfortunately it is not possible to prevent deadlocks by denying
mutual-exclusion.
• Cannot be prevented for all resources. Some resources are
intrinsically non-sharable for example printer, and some are
sharable like CPU.

Hold and wait ( Collective Requests )

• This method denies the hold-and-wait condition.
• We must guarantee that whenever a process requests a resource, it
does not hold any other resources.
Following policies maybe used to ensure this:
• 1. A process must request all of its resources before it begins
execution. If all the needed resources are available , they are
allocated to it. If one or more resources are not available , none will
be allocated and process would just wait.
No-Preemption condition ( resources will be preempted)
 A preemptable resource is one whose state can be easily saved and
restored later.
 A resource temporarily taken away from the process without harm
to the computation performed by this process.
 CPU, Main Memory are preemptable resources.
 If the resources are preemptable, deadlocks can be prevented.
 Two policies:
1. when a process requests for a resource, and resource is not
available. Its already held resources taken away from it. And the
process is blocked. The process is unblocked when the resources
(requested by it, and preempted from it) available and allocated to it.
2.When a process requests a resource that is not currently available,
the system checks, if the requested resource is currently held by
another process that is already blocked and waiting for other
resources. If so , the requested resource is taken away from the waiting
process and give to the requesting process, otherwise condition-1
applied.
Circular wait condition (ordered requests)
 Each resource (type) is assigned a global number to impose total
ordering.
 Impose a total ordering of all resource types , and require that each
process can only requests resources in an increasing order of
enumeration.
 Process should not request a resource with a number lower than is
already held resource.
 If process request = j and process already held resource = i then, j >
i
 Single request will be enough for the same resource type.
 It has proven that with this, graph can never have circular-wait.
 If tape drive =1 , disk drive = 5, printer = 12, after getting tape drive
process can request for the disk drive, after disk drive process can
request for the printer. But it a process have the number =5, it
cannot request for the number=1 for tape drive.
Deadlock Detection:
• Uses algorithm that keeps examining state of system to determine
whether a deadlock has occurred.
• When deadlock has occurred system takes action to recover.
• Algorithms are same for centralized as well as distributed.
• Uses resource allocation graph and searching for cycle or not
depending upon single or multiple units of resources.
Following steps are needed to construct Weight For Graph(WFG).
1. Construct separate Resource allocation graph for each site.
Resource node exists for all local resources and process node exists
for all processes that are either holding or waiting for resource.
2. Construct WFG by removing resources and collapsing edges.
Take union of all WFG of all sites and construct single global WFG.
Two sites, site 1 with 2 resources and site 2 with 1 resource.
• P1 is holding R1 and requesting for R3.
• P2 is holding R2 and requesting for R1.
• P3 is holding R3 and requesting for R2
Union of WFG of two sites will show either deadlock exists or not. Local
WFG does not contain cycle while Global has.
Difficulties: Maintaining WFG of each site is difficult.
Most important feature of deadlock detection algorithm is correctness
which depends on these properties.
1) Progress Property:
Deadlocks must be detected in finite amount of time.
2) Safety Property:
Detected deadlock must exist. Message delays and out of date WFG cause
false cycles to be detected. It results in detection of deadlocks that do not
exist called phantom deadlocks.
Three commonly used techniques for organizing WFG in a distributes
system are..
• Centralized Algorithms
• Distributed Algorithms
• Hierarchical Algorithms
 • Local coordinator at each site that maintains WFG of its local
resources.
• Central coordinator that is responsible for constructing union of all
WFG.
• Central coordinator constructs global WFG from information
received form local coordinator of all sites.
Deadlock detection is performed as follows.
1. If cycle exists in local WFG of any site, it represents local deadlock.
Such deadlocks are detected and resolved by local coordinator.
2. Deadlocks involving resources at two or more sites get reflected as
cycles in global WFG. Such deadlocks are detected and handled by
central coordinator.
3. In centralized approach messages are sent form local to central
coordinator to transfer information as follows.
Continuous Transfer: local coordinator send message whenever an new
edge is added or deleted
Periodic Transfer: local coordinator sends message after fix time when no
of changes have occurred.(in order to reduce messages)
Transfer on Request: on request of central coordinator. Central
coordinator invokes cycle detection algorithm periodically and requests
information from each site just before invoking algorithm.
Drawbacks:
• Failure of central coordinator. Back up can resolve issue.
• Central coordinator will become performance bottle neck in large
system having to many sites.
• It may detect false deadlocks or phantom.
Hierarchical Approach:
• Uses logical hierarchy(tree) of deadlock detectors.
• Deadlock detectors are called controllers.
• Each controller is responsible for deadlocks that involves sites
falling within its range.
• Unlike centralized approach instead of maintaining WFG at a single
site, it is distributed over no of controllers.
WFG is maintained on following rules.
• Each controller that forms a tree of hierarchy tree maintains local
WFG of single site.
• Each non-leaf controller maintains WFG that is union of WFGs of
its immediate children in hierarchy tree.
Fully Distributed Approaches for deadlock detection:
• Each site of system shares equal responsibility for deadlock
detection.
Types:
• WFG based Distributed algorithm for deadlock detection.
• Probe based Distributed algorithm for deadlock detection.

Or
23 Explain in detail about the Remote Procedure Call with neat diagram. 1 L 2 2 1.6.1
1984: Birrell & Nelson 0 2
– Mechanism to call procedures on other machines
Goal: Make distributed computing look like centralized computing
– Aims at hiding most of the intricacies of message passing,
and ideal for client-server applications
– Allow remote services to be called as procedures
– Transparency with regard to location, implementation,
language
 • A remote procedure call makes a call to a remote service look
like a local call
– RPC makes transparent whether server is local or remote
– RPC allows applications to become distributed
transparently
– RPC makes architecture of remote machine transparent
Possible issues:
• Calling and called procedures run on different machines
• They execute in different address spaces
• Parameters and results have to be passed, it can be complicated
when the machines are not identical.
– How do you represent integers – big-endian little-endian
• Either or both machines can crash and each of the possible
failures causes different problems.
Client and Server Stub

Solution — a pair of Stubs:

• Client stub
– packs the arguments with the procedure name or ID into
a message
– sends the msg to the server and then awaits a reply msg
– unpacks the results and returns them to the client
• Server stub
– receives a request msg
– unpacks the arguments and calls the appropriate server
procedure
– when it returns, packs the result and sends a reply msg back to
the client
RPC System Components and Call Flows
 Steps:
1. Client procedure calls client stub in normal way
2. Client stub builds message, calls local OS
3. Client's OS sends message to remote OS
4. Remote OS gives message to server stub
5. Server stub unpacks parameters, calls server
6. Server does work, returns result to the stub
7. Server stub packs it in message, calls local OS
8. Server's OS sends message to client's OS
9. Client's OS gives message to client stub
10. Stub unpacks result, returns to client

Question Paper Setter Approved by Audit Professor/ Course Coordinator

* Performance Indicators are available separately for Computer Science and Engineering in AICTE
examination reforms policy.