Solved Mid Term Paper CS703 (Advance Operating Systems ) Part-2

Question 20:

What are the requirements and implications for the discussed two implementations of

condition variables for transactional memory?

Answer:

The requirements and implications for deferred signal approach are Commit Actions

The requirements and implications for Speculative signal approach are Escape Actions, and

Robust Conflicts Detections

Question 21:

Explain, in your own words, how the proposed approach manages to avoid deadlocks

when unstructured locking is used.

Answer:

The proposed approach says that the deadlock cannot occur when we have the requested lock

and its future lock set. The future lockset is the set of locks when the lock is requested and all

locks in between till a matching unlock is found. The proposed approach starts by tracking the

simple effects. Simple effects may be the empty sequences of locks and unlocks events.

Proposed approach uses a continuation effects i.e. the effect of code to its following expression.

The proposed approach has the feature to add notes to the lock operation according to their

continuation effects.

The continuation effects are calculated statically, but the future lock sets are computed at run

time. When a function is called the continuation effects is pushed on to the stack up to the time

the call is not fully executed. During the continuation effect, the locks are identified and added to

the lock set. At runtime the lock operation unblocks whenever we find a lockset. This assists to

avoid deadlocks. The proposed approach gives only a single lock to every lock operation, this

increase the degree of parallelism.

Now let us see constitutes of the proposed approach and its implementation in various

programming language constructs.

Effects: Simple effects may be the empty sequences of locks and unlocks events. Continuation

effect i.e. the effect of code to its following expression. Notes are added to the lock operation

according to their continuation effects. The continuation effects are calculated statically, but the

future lock sets are computed at run time. When a function is called the continuation effects is

pushed on to the stack up to the time the call is not fully executed. During the continuation

effect, the locks are identified and added to the lock set. At runtime the lock operation unblocks

whenever we find a lockset. This assists to avoid deadlocks. The proposed approach gives only

a single lock to every lock operation, this increase the degree of parallelism. The runtime

system utilizes the dynamically computed future locksets so that each lock operation can only

proceed when its future lockset is available to the requesting thread.

Function Calls: As we know that the continuation approach is intra-procedural so the unlock

operation for a lock operation may not reside in the same function. This problem is resolved by

adding the notes to function call according to the continuation effect. As static analysis says

ensures that there is always an unlock operation for a lock, so the algorithm traverse the lockset

and find the matching unlock terminates.

Conditionals: A demerit defining effects as ordered events is that, in case of conditional

expressions/statements, it becomes less likely that the branches will have the same effect.

13 CS-703 Advance Operating Systems

Virtual University of Pakistan

Proposed approach can deal with it. Proposed approach traversed each branch and keep tracks

of each branch, and algorithms calculates the lockset for each branch individually.

Loops and recursions: loops and recursions introduce additional problems. In the case of

recursion and loops, function and its body name must express the same name. But this is no

possible, due to the reason that the two effects cannot be structure-wise equivalent: the effect of

a function name is contained in the effect of its body, due to the recursive call. To handle this

problem, a summary is tagged to the function names showing the effect of their bodies.

Question 22:

How static analysis is performed and what are its limitations?

Answer:

Static analysis is performed in the following four phases:

Pointer Analysis: First, the heap and stack state is formulated at each point of the program by

doing a pointer analysis that is based on symbolic expressions. The analysis has been modified

to treat the heap allocation in a context-sensitive manner. The out of first stage is a mapping for

each expression to a set of abstract locations. Each abstract location may have any forms e.g. a

formal parameter, a global variable or a heap-allocated location.

Effect Interference: we have a functional control flow graph in the analysis. Here a forward

dataflow algorithm is run on the graph to compute the effect for each function. Nodes of the

graph show input, current and output effects. The input effects are formulated from its front

edges. The output effect is computed by appending the current effect to the input effect and is

propagated to a node’s successors until a fixed point is reached. Output effects that have no

successors are joined to computer a function’s effect.

Loops: at this phase, lock counts effects flowing from back edges must be equivalent to the

input effect of the same node. Due to this bound, we can efficiently encode loop effects: from

the entrance to exit the counts of each lock should match. We take effect of the entire loop. The

empty effect on all branches compensates for the case where a loop is not executed.

Effect Optimization: function effect repetitions should be avoids. For this optimization

techniques are applied. One technique is to find the common prefixes and suffixes so that the

number of branches may be reduced. Another technique for removing the nested loop is to take

the nested loops out. We also trigger the data flow algorithm, which is CPU-intensive, only for

functions that are known to contain lock operations, to avoid additional overheads.

Limitations are as follows:

Non C code: C language can be tightly dealt with our static analysis. However, library code

cannot be handled by our analysis. In our assumptions, we take the library functions’ effect as

empty effects. However, we can add user-defined notes for library functions. There is another

limitation with our analysis that it cannot handle non-local jumps (including signals) and inline

assembly.

Pointer analysis: our analysis is not capable of handling pointers arithmetic that involves locks

in it. Our analysis also fails to track heap allocation at recursive functions and loops. Another

limitation is that we need that lock pointers are changed only before they are shared between

threads, and that locks pointed by with at least two levels of indirection are not aliased at

function calls.

14 CS-703 Advance Operating Systems

Virtual University of Pakistan

Conditional Execution: if the locks and their matching unlock operation happens to be

executed in separate conditional statements, and they have similar guards, in this case, our

analysis will not accept the program.

Question 23:

What is are message-oriented models?

Mechanism of this model is passing messages/events among processes with an easy an

efficient way. Such model also provides the facility of putting the messages into the queues

unless they are served. Messages have the states of wait and ready etc. pre-emption for high

priority messages is facilitated. Message-oriented models bear these features:

· Special types of processes communicate among each other with special paths like

sockets, ports, or channels etc.

· Process communication paths are static. Creating, deleting or changing connection

among processes is difficult.

· Processes work in their separate spaces and rarely access the shared data

· Message-oriented models bear the following characteristics:

· Process synchronization is made possible through queues that are attached with

processes

· When more than one processes operate on data, the data structure are passed by

reference

· Peripheral devices are also work like messages. Signal is sent to devices and an

interrupt is generated by devices in response

· Priorities for process are set statically at the time of system design

· Mostly one process is served at a time and served completely before looking into the

queue for next process

Messages-oriented models provide the following facilities:

· It carries a handle for identifying a message, and message data portion

· Messages communication is established through channels and ports.

· Messages are sent and received through operations like SendMessage, AwaitReply,

WaitForMessage, and SendReply etc.

Question 24:

What is Procedure-Oriented Model?

Mechanism of this model is quickly switching the context of processes by giving the protection

and addressing mechanism. Processes use sharing of data extensively. Inter process

communication is secured by semaphores, locks, monitors etc. Pre-emption of resources is only

given to high priority processes after the resources are released by the using process.

Procedure-oriented models bear these features:

· Processes access global data in a synchronized and controlled way.

· As a process and no communication channel associated with it so process creation is

easy. Process deletion is also easy when a process holds no lock.

· Process is assigned a single task to complete and the process wanders at many location

and states while changing its context.

Procedure-oriented models bear the following characteristics:

· Process synchronization in case of many resources is made possible through locks

· Process are made to share the data, and data access is given for shortest possible time and

smallest possible part of resource

· Control of devices and interrupts from devices are also dealt with the help of locks

15 CS-703 Advance Operating Systems

Virtual University of Pakistan

· Process are given priority dynamically, this priority is on the basis of short time of completion

· To save the context switching from conflicts, global naming is important

Procedure-oriented models provide the following facilities:

· They provide procedures. Procedures have algorithms, local data, parameters and results

· They provide synchronous and asynchronous procedure calls

· FORK, JOIN, WAIT, SIGNAL calls are provided for processes and protection of processes

Question 25:

What factor must be considered while choosing message-oriented or procedure-oriented

system model?

We have seen that in the paper that both message-oriented and procedure-oriented models are

counter parts of each other. System designed under any one model and be transformed into the

other more with confidence. Same functionality can be achieved through the implementation of

any of these two models. So why to choose and prefer over the other? For the answer of this

question we will have to think two steps down. Process and synchronization facilities are things

which make one or the other style more attractive or more tedious.

For example there is a system which is more tending towards utilizing the virtual memory

mechanism to perform its tasks; here it is easier to distribute the memory into messages blocks

and queue messages; but it is very difficult to protect the shared memory; so in such system it is

a better decision to choose a message-oriented model.

There is another system which is more tending towards the usage of stack and block structured

allocation. In such case we can choose the procedure-oriented model.

Following factors may also be considered while choosing one these models:

· Organization of real and virtual memory

· Space and size of the word that is used to save the state of each process context switch

· The ease with which process scheduling and dispatching can be accomplished

· The control and arrangement of peripheral devices and interrupts generated by these

devices

· Architecture of the register that can be programmed

· Architecture of the instructions

Although the above factors can be considered while choosing one of the models, but it is to be

noted that it is very rare that a programmer has a clear influence by one of them over the other.

And the other thing even rarer is the fact that a programmer has a full knowledge of the two

models and factors influencing them.

Question 26:

How are address translations and physical memory managed in the Exokernel?

For address translation, the virtual address space is divided into two portions. First portion

keeps the application data and code. Virtual addresses in this portion are mapped and typically

hold exception handling code and page-tables.

Following actions will take place On a TLB miss:

· Exokernel checks where the virtual address is located. In case of the standard user

segment, the exception is dispatched directly to the application. In case of the second

segment and guaranteed mapping, exokernal installs the TLB entry and continues; and in

case of second segment and not guaranteed mapping exokernal forwards it to the

application.

· The application searches the virtual address in its page-table structure and, if the access is

not valid, an appropriate exception is generated. If the virtual address mapping is allowed,

16 CS-703 Advance Operating Systems

Virtual University of Pakistan

the application constructs the appropriate TLB entry and its associated capability and

invokes the appropriate exokernal routine.

· Exokernel then checks whether the access is allowed are not. If access is allowed then

mapping is installed in the TLB and control is returned to the application. And if the access is

not allowed an error is returned.

· At the last application does some cleanup work and then resumes its execution.

For efficient virtual memory management, TLB must be refilled fast. To do this , Exokernal use

the caching for TLB entries in the kernel. Exokernal uses overlaying the hardware TLB with big

software TLB (STLB) to absorb capacity misses. On a TLB miss, Exokernal first checks that the

required mapping is in the STLB. If it is located there, Exokernal installs it and resumes

execution; in the opposite case, the miss is forwarded to the application.

The STLB have 8 bytes entry and it has total 4096 entries. It has direct mapping and located in

unmapped physical memory. When an STLB has a “hit”, it takes 18 instructions. In the opposite

case, performing an up call to application level on a TLB miss, a system call to install a new

mapping is at least 3 to 6 microseconds more expensive. As we know that exokernel has a

principle of exposing kernel bookkeeping structures, the STLB can be mapped to a capability

that can search the entries efficiently.

Question 26:

How does Exokernel use hardware support to improve the performance?

Exokernel improve its performance by securely exposing the hardware. The main principal of

the exokernel architecture is that the kernel should provide secure low-level primitives so that

these primitives permit all hardware resources to be accessed as directly as possible. So the

the major struggle of an exokernel designer is therefore to safely export all privileged

instructions, hardware DMA capabilities, and machine resources. The exported resources are

hardware i.e. physical memory, the CPU, disk memory, translation look-aside buffer (TLB), and

addressing context identifiers. Due to this securely exposing hardware principle, an

improvement occurs in the less tangible machine resources such as interrupts, exceptions, and

cross-domain calls. Exokernel should not apply higher-level abstractions on these events. Most

of the physical resources should be partitioned and sub-divided in a fine manner. The number,

format, and current set of TLB mappings should be visible to library systems, and these should

be replaceable by library operating systems. These should also be visible to and replaceable

any “privileged” co-processor state. An exokernel must export privileged instructions to library

operating systems so that they may be able to implement traditional operating system

abstractions such as processes and address spaces. A system call can have an exported

operation that checks the ownership of any resources involved. In negative wording, we can say

that this principle states that an exokernel should avoid resource management. The resources

should be managed to up to the required by protection (i.e., management of allocation,

revocation, and ownership). We believe that using the hardware under this principle brings

improvement in the performance because distributed, application-specific, and resource

management is the best way to build efficient flexible systems.

Question 27:

Can we say that Exokernel is a micro-kernel? What abstractions does it support?

No, we cannot say that exokernel is a micro-kernel. In practice, exokernel system provides

applications with greater flexibility and better performance than microkernel systems. The low

level interface of Exokernel permits application-level software to manipulate resources very

efficiently. Protected control transfer in exokernal is recoded 7 times faster than that of the

current implementations of microkernel. Similarly, the exception dispatch is 5 time better than

17 CS-703 Advance Operating Systems

Virtual University of Pakistan

that of the microkernel. Exokernel gives flexibility to the application level software, while

microkernel does not provide this flexibility. For example, virtual memory is implemented at

application level, where it can be tightly integrated with distributed shared memory systems and

garbage collectors. Efficient protected control transfer in exokernel permits applications to build

a large array of efficient IPC primitives by trading performance for additional functionality. As

opposite to exokernel, microkernel systems do not give permission to un-trusted application

software to build specialized IPC primitives because virtual memory and message passing

services are implemented by the kernel and trusted servers. In the same way, microkernel does

not provide the capability of modifying many other abstractions, such as page-table structures

and process abstractions. Moreover, many of the hardware resources in microkernel systems,

such as the network, screen, and disk, are encapsulated in heavyweight servers that cannot be

bypassed or made suitable to application-specific needs.

Another aspect to be note is that, like microkernel systems, an exokernel can provide backward

compatibility in three ways:

· Binary emulation of the operating system and its programs

· By implementing its hardware abstraction layer on top of an exokernel

· Re-implementing the operating system’s abstractions on top of an exokernel

Just similar to microkernels, exokernels are designed to increase extensibility. And just opposite

to traditional microkernels, an exokernel pushes the kernel interface much closer to the

hardware, which allows for greater flexibility.

Question 28:

Abstractions are slow and are not tuned to all applications, how does Exokernel

addresses this problem?

Most of the fixed high-level abstractions are slow. They put a resistance in the performance of

application. This slow performance is due to the reason that there is no single way to abstract

physical resources or to implement an abstraction that is best for all applications. When an

operating system needs an abstraction to be implemented, the operating system has some

restrictions to make trade-offs between read-intensive or write-intensive workloads, support for

sparse or dense address spaces, etc. These tradeoffs put some penalties on performance on

classes of applications. For example, relational databases and garbage collectors sometimes

have very predictable data access patterns, and their performance suffers when a general

purpose page replacement strategy such as LRU is imposed by the operating system. But we

know that the performance improvement is very important factor in application-specific policies.

To address this problem of efficiency, Exokernal uses the techniques of application-controlled

file caching. And it has been measured that this technique can reduce application running time

by as much as 45%.

Question 29:

Differentiate between Locks and Semaphores?

Answer:

Locks: locks are synchronization primitives used to protect shared data structures among

threads. Locks can be implemented both ways i.e. busy-waiting and blocking (sleep).

Semaphores: semaphores are synchronization primitives used to protect shared data

structures among threads as well as can provide coordination among different threads.

Semaphores are enhancement to locks and can be used as locks (i.e. mutexes).

18 CS-703 Advance Operating Systems

Virtual University of Pakistan

Question 30:

Differentiate between Semaphores and Condition Variables?

Answer:

Semaphores: semaphores are synchronization primitives used to protect shared data

structures among threads as well as can provide coordination among different threads.

Semaphores are enhancement to locks and can be used as locks (i.e. mutexes).

Condition Variables: condition variables are used to provide inter-thread coordination i.e.

to coordinate events occurring in different threads. If one or more threads are waiting

(blocked) for an event/signal to occur in another thread, we use condition variables to

provide coordination among these threads.

Question 31:

How can we use Semaphores for thread reaping?

Answer:

Semaphores can be used for thread reaping. Here semaphore is used as mutex i.e.

initialized with zero (count = 0). When the we want to wait for the new thread to

complete (i.e. pthead_join()) we call P() operation, which causes the calling thread to

block as count = -1. The thread who is being joined, would call V() operation when going

to exit. Which would signal to the blocked thread and it would resume its execution.

Question 32:

Briefly discuss “Resource Ordering” technique for preventing deadlocks?

Answer:

Resource ordering is a practical and commonly used technique to prevent deadlocks. We

assign a number to each resource (i.e. resource itself or the lock/semaphore associated

with it) or we assign levels (i.e. these particular resources are categorized at level 1, these

resources are at level 2 and so on). At each level there can be resources of multiple types.

Rule: All threads will acquire the resources in same order (i.e. first level 1 resources, then

level 2 resources and so on), that is, holding the resources taken from previous level, we

take resources from next level.

If every thread follows that rule then there would be no chance of a deadlock, because

there would be no circular wait situation.

Question 33:

Briefly discuss the problem of “Priority Inversion”?

Answer:

Priority Inversion problem occurs when:

· A high priority job waits for a low priority job while a medium priority job runs

on the CPU.

· Or A high priority job keeps spinning in a loop waiting for a lower priority job to

release a lock, but the lower priority job never gets a chance to run on the CPU.

19 CS-703 Advance Operating Systems

Virtual University of Pakistan

Question 34:

Briefly discuss the disadvantages of “Threads” paradigm?

Answer:

Disadvantages of Threads paradigm are as follows:

1. It makes the overall code of the program, non-deterministic. It introduces

Heisenbugs in the program. A Heisenbug is a type of bug that disappears or alters

its behavior when you attempt to debug it.

2. In large, complex real life programs/problems, the programmer usually does not

visualize properly that which synchronization mechanism should be deployed

here in a particular situation. Hence, introducing wrong synchronization primitives in

different scenarios, resulting in lots of undetectable bugs in the code.

3. As threads grow in numbers, for each thread kernel has to allocate memory

internally for its stack. Hence the kernel’s memory space is used for the purpose,

it grows and soon reaches a limit beyond which it cannot expand. Secondly, when

there are too many threads created, the benefit of parallelism achieved by

overlapping I/O and CPU activities is destroyed / nullified.

4. As the number of threads grow, the overall thread management, done by a main

controller thread, becomes a cumbersome job.

5. Context Switching overhead increases to a great extent, with the increase of no. of

threads. Similarly thread scheduling and synchronization overhead increases with

the increase in number of threads.

Question 35:

In lectures, we studied that there are three methods possible to achieve

concurrency. What is the difference between second (Single Process, multiple

events) and third (threads) method?

Answer:

Single process, multiple events approach:

In this approach, we have a single process, when we have to block, we do not block in

fact we schedule an event for future firing, and in the call back of that event a registered

function is used. The process in fact tries to save itself from getting blocked.

Drawbacks of this approach:

· The process has to maintain the state of each request/session.

· All requests/sessions can be in different states. So a FSM have to be maintained

for each session/client.

· All these FSMs are maintained in a global table of a single process.

Threads approach:

Multiple execution states within a single address space. Instead of managing a global

table for the states of every session, we offload all the session processing task to one

execution stream (execution state) and another session processing to another execution

stream and so on. Each execution stream maintains its data by itself.

20 CS-703 Advance Operating Systems

Virtual University of Pakistan

Question 36:

What are the things included in a thread’s context?

Answer:

Thread’s context usually consists of:

· CPU registers

· Program Counter

· Stack Pointer

Question 37:

Who generates/creates the user-level thread? And do we require a system call to

generate a user-level thread?

Answer:

User-level threads are created by a library (run time system). Whenever the program

wants to create a thread, it calls the library, no system call is triggered, the library creates

the thread itself.

Question 38:

What is the concept of “Scheduler Activation” as discussed in the lectures?

Answer:

Scheduler Activation:

Suppose kernel-level thread is going to block, if kernel somehow, notify it to the

application / process [that this particular kernel thread is going to block]. The run time

system (user-level thread library) checks that the user-level threads which are mapped to

this blocking kernel thread, do not have some lock which other kernel level threads may

need. If there are such lock(s), it temporarily gets these lock(s) back. This is known as

scheduler activation. This scheduler activation is used on top of hybrid threads model.

Question 39:

What is the relationship between different threads in a single process? How one

thread can wait for the termination of another thread?

Answer:

Different threads in a single process are peers of each other (i.e. there is no parent child

relationship).

A thread can wait for the termination of another thread by calling the pthread_join()

function, passing the joining thread’s thread ID as argument in the function call.

Question 40:

In multithreaded programs, what are the two cases in which we need synchronization

mechanisms?

Answer:

The two cases are:

1. to protect shared resources/data structures

2. to provide coordination among different threads of a process

21 CS-703 Advance Operating Systems

Virtual University of Pakistan

Question 41:

In threads execution, what we mean by the term “arbitrary interleaving of executions”?

Answer:

Arbitrary interleaving of executions means we cannot predict the order of execution of

threads, and execution can switch from one thread to another at arbitrary point of time.

Secondly, we also cannot predict the rate of execution of instructions in different threads.

So the goal is to write the multi-threaded program in such a way that any arbitrary

interleaving of executions of threads does not make our program unpredictable.

Question 42:

In the “Too Much Milk” problem discussed in the lecture, what is the flaw in

solution#2?

Answer:

Consider the situation, thread A runs, leaves note A then thread B runs, leaves note B,

then thread A runs, checks condition (no Note from B), since note from B is present,

hence fails then thread B runs, checks condition (no Note from A), since note from A is

present hence fails, then thread A runs, removes note A, then thread B runs, removes note

B. Hence, no one buys milk.

Question 43:

Consider the following ways of handling deadlock:

(1) Banker’s algorithm

(2) Detect deadlock and kill thread, releasing all resources

(3) Reserve all resources in advance

(4) Restart thread and release all resources if thread needs to wait

(5) Resource ordering

(6) Detect deadlock and roll back thread’s actions.

(a) One criterion to use in evaluating different approaches to deadlock is which approach permits

the greatest concurrency. In other words, which approach allows the most threads to make

progress without waiting when there is no deadlock? Give a rank order from 1 to 6 for each of

the ways of handling deadlock just listed, where 1 allows the greatest degree of concurrency.

Comment on your ordering.

(b) Another criterion is efficiency; in other words, which requires the least processor overhead.

Rank order the approaches from 1 to 6, with 1 being the most efficient, assuming that deadlock

is a very rare event. Comment on your ordering. Does your ordering change if deadlocks occur

frequently?