Monday, March 26, 2012

System Software And Operating System Important Descriptive Questions 2

System Software And Operating System Important Descriptive Questions 2

Q.11. Define the following:
(i)  FIFO Page replacement algorithm.
(ii)  LRU Page replacement algorithm.                                                         (6)

(i) FIFO policy: This policy simply removes pages in the order they arrived in the main memory. Using this policy we simply remove a page based on the time of its arrival in the memory. For example if we have the reference string: 1, 2, 3, 4, 1, 2, 5,
1, 2, 3, 4, 5 and 3 frames (3 pages can be in memory at a time per process) then we
have 9 page faults as shown


DC14                                                                      System Software and Operating System

If frames are increased say to 4, then number of page faults also increases, to 10 in this case.

(ii) LRU policy: LRU expands to least recently used. This policy suggests that we re- move a page whose last usage is farthest from current time. For reference string:  1, 2,
3, 4, 1, 2, 5, 1, 2, 3, 4, 5, we have the following page faults

Q.12.    List the properties which a hashing function should possess to ensure a good searc performance. What approaches are adopted to handle collision?                                    (8)

A hashing function h should possess the following properties to ensure good search performance:
1.The hashing function should not be sensitive to the symbols used in some source
program. That is it should perform equally well for different source programs.
2.The hashing function h should execute reasonably fast.
The following approaches are adopted to handle collision are:
Chaining:  One  simple  scheme  is  to  chain  all  collisions  in  lists  attached  to  the appropriate slot. This allows an unlimited number of collisions to be handled and doesn't  require  a  priori  knowledge  of  how  many  elements  are  contained  in  the collection. The tradeoff is the same as with linked lists versus array implementations of collections: linked list overhead in space and, to a lesser extent, in time.
Rehashing: Re-hashing schemes use a second hashing operation  when  there is a collision. If there is a further collision, we re-hash until an empty "slot" in the table is found. The re-hashing function can either be a new function or a re-application of the original one. As long as the functions are applied to a key in the same order, then a sought key can always be located.


DC14                                                                      System Software and Operating System

Overflow  chaining: Another scheme  will  divide  the  pre-allocated  table  into  two sections:  the primary  area to  which keys are mapped and an area  for collisions, normally termed the overflow area. When a collision occurs, a slot in the overflow area is used for the new element and a link from the primary slot established as in a chained system. This is essentially the same as chaining, except that the overflow area is pre-allocated and thus possibly faster to access. As with re-hashing, the maximum number of elements must be known in advance, but in this case, two parameters must be estimated: the optimum size of the primary and overflow areas.

Q.13.  What is assembly language? What kinds of statements are present in an assembly language program? Discuss. Also highlight the advantages of assembly language.
Assembly language is a family of low-level language for programming computers, microprocessors, microcontrollers etc. They implement a symbolic representation of the numeric machine codes and other constants needed to program a particular CPU architecture. This representation is usually defined by the hardware manufacturer, and is based on abbreviations (called mnemonic) that help the programmer remember


DC14                                                                      System Software and Operating System

individual  instruction,  register  etc.  Assembly  language  programming  is  writing machine   instructions  in  mnemonic  form,  using  an  assembler  to  convert  these mnemonics into actual processor instructions and associated data.
An assembly program contains following three kinds of statements:
1. Imperative statements: These indicate an action to be performed during execution of the assembled program. Each imperative statement typically translates into one machine instruction.
2. Declaration statements: The syntax of declaration statements is as follows: [Label]                 DS<constant>
[Label]      DC alue>’
The DS statement reserves areas of memory and associates names with them. The DC statement constructs memory words containing constants.
3. Assembler directives: These instruct the assembler to perform certain actions during the assembly of a program. For example
STAR <constant> directive indicates that the first word of the target program generated by the assembler should be placed in the memory word with address
The advantages of assembly language program would be
           reduced errors
           faster translation times
           changes could be made easier and faster

Q.14.   What is an expression tree? How an expression is evaluated using an expression tree? Discuss its advantages over the other evaluation techniques.                                              (8)

Algebraic expressions such as
have an inherent tree-like structure. For example, following figure is a representation of the expression in above equation. This kind of tree is called an expression tree.

The terminal nodes (leaves) of an expression tree are the variables or constants in the expression (a, b, c, d, and e). The non-terminal nodes of an expression tree are the operators (+, - , and  )
The expression tree is evaluated using a post-order traversal of the expression tree as
1.           If this node has no children, it should return the value of the node
2.           Evaluate the left hand child
3.           Evaluate the right hand child
4.           Then evaluate the operation indicated by the node and return this value
An expression tree is advantageous for:


DC14                                                                      System Software and Operating System

Understanding the order of operation. Operations that must be done sooner are further to the right in the tree.
Counting the number of terms or factors in an expression. Each term or factor is a child node. For example the expression (a+b)/c+2*d contains two terms.

Q.15.    Draw an expression tree for the string. f + (x+y) *((a+b)/(c-d))
Indicate the register requirement for each node and list out the evaluation order for the expression tree.                                                                                                                         (8)

An expression tree for the string f + (x+y) *((a+b)/(c-d)) is given below: Maximun register requirement is 2.

The expression will be evaluated in the following order: resister R1 first, then register R2, and so on.

f +    (x+y)         *   (   (a+b)         /        (c-d))

R1                              R2



Q.16.          Explain the following:-
(i) Elimination of common sub expressions during code optimisation. (ii) Pure and impure interpreters.
(iii) Lexical substitution during macro expansion. (iv)Overlay structured program.
(v) Facilities of a debug monitor.
(vi) Actions of an interrupt processing routine. (vii) Real time operating system.
(viii) Fork-join.                                                                                          (16)


DC14                                                                      System Software and Operating System

(i)       Elimination of common sub expression during code optimization
An optimizing transformation is a rule for rewriting a segment of a program to
improve  its  execution  efficiency  without  affecting  its  meaning.        One  of  the techniques is “Common sub expression elimination”
I the   expression   "(a+b)-(a+b)/4" "common   subexpression refer to   the duplicated "(a+b)". Compilers implementing this technique realize that "(a+b)" won't change, and as such, only calculate its value once.
(ii) Pure and impure interpreters
In a pure interpreter, the source program is retained in the source form all through its interpretation.   This   arrangement   incur substantia analysi overheads   while interpreting a statement.An impure interpreter performs some preliminary processing of the  source program to reduce the analysis overheads during interpretation. The preprocessor converts the program to an intermediate representation (IR), which is used during interpretation. This speeds up interpretation as the code component of the IR i.e the  IC,  can  be analyzed more efficiently than the source form of the program.
(iii)Lexical substitution during macro expansion: Lexical substitution is used to generate an assembly statement from a model statement. A model statement consists of 3 types of strings:
1. An ordinary string, which stands for itself.
2. The name of a formal parameter which is preceded by the character &.
3. The name of a preprocessor variable, which is also preceded by the character
During lexical expansion, strings of type 1 are retained without substitution. Strings of  types  2  and  3  are  replaced  by  the  values of  the  formal  parameters  or preprocessor variables. The value of a formal parameter is the corresponding actual parameter string.
(iv) Overlay structured program: A program containing overlays is referred as
overlay structured program where an overlay is a part of program which has the same load origin as some other part(s) of the program. Such a program consists of
1. A permanently resident portion, called the root
2. A set of overlays
The overlay structure of a program is designed by identifying mutually exclusive modules-that is, modules that do not call each other. The basic idea is that such modules do not need to reside simultaneously in memory. Hence they are located in different overlays with the same load origin.
(v) Facilities of a debug monitor are as follows:
a. Setting breakpoints in the program
b. Initiating a debug conversation when control reaches a breakpoint
c. Displaying values of variables
d. Assigning new values to variables
e. Testing user defined assertions and predicates involving program variables.
(vi) Action of an interrupt processing routine are as follows:
1. Save contents of CPU registers. This action is not necessary if the CPU registers are saved by the interrupt action itself.
2. Process the interrupt and take appropriate actions. The interrupt code field of save PSW  information  unit  corresponding  to  this  interrupt  contains  useful information for this purpose.
3. Return from interrupt processing.
(vii) Real time operating System


DC14                                                                      System Software and Operating System

A real-time operating system has well-defined, fixed time constraints. Processing must be  done within the defined constraints, or the system will fail. A real time system is considered to function correctly only if it returns the correct result within any time constraints. So the following features are desirable in a real-time operating system:
1. Multi-tasking within an application
2. Ability to define the priorities of tasks
3. Priority driven or deadline oriented scheduling
4. Programmer defined interrupts.
(viii)  fork-join  are  primitives  in  a  higher  level  programming  language  for implementing interacting processes. The syntax is as follows:
fork <label>;
join ar>;
where abel> is a label associated with some program statement, and ar> is a variable.  A  statement  fork  label1  causes  creation  of  a  new  process  that  starts executing at the statement with the label label1. This process is concurrent with the process which executed the statement fork label1.A join statement synchronizes the birth of a process with the termination of one or more processes.
Fork-Join provide a functionally complete facility for control synchronization.

Q.17 List  and  explain  the  three  events  concerning  resource  allocation.  Define  the following:
(i) Deadlock.
(ii) Resource request and allocation graph (RRAG)
(iii)Wait for graph (WFG)                                                               (6)

(i)  Deadlock: Each process in a set of processes is waiting for an event that only a process in the set can cause.
(ii) Deadlocks can be described by a directed bipartite graph called a Resource- Request-Allocation graph (RRAG).A graph G = (V,E) is called bipartite if V can be decomposed into two disjoint sets V1 and V2 such that every edge in E joins a vertex in V1 to a vertex in V2.Let V1 be a set of processes and V2 be a set of resources. Since the graph is directed we will consider:


DC14                                                                      System Software and Operating System

    an  edge  (Rj,Pi)  (an  assignment  edge)  to  mean  that  resource  Rj  has  been allocated to process Pi
    an edge (Pi,Rj) (called a request edge) to mean that process Pi has requested resource Rj
1. Use a resource allocation graph to derive a wait-for graph.
2. Wait-for graph obtained by making an edge from p1 to p2 iff p1 is waiting for a resource that is allocated to p2.
3. Deadlock exists iff a cycle exists in resulting wait-for graph.


Q.18.          A system contains 10 units of resource class Ru. The resource requirements of three  user processes P1, P2 and P3 are as follows
P1                  P2                P3
Maximum requirements              8                     7                   5
Current allocation                       3                     1                  3
Balance requirements                 5                    6                   2
New request made                      1                    0                   0
Using Banker’s algorithm, determine if the projected allocation state is safe and whether the request of P1 will be granted or not.                                                           (6)

From the given data: Total_alloc=[7] Total_exist=[10]
The projected allocation state is feasible since the total allocation in it does not exceed  the  number  of resource units  of Ru. Since P3 is two units short of its maximum requirements and two unallocated units exits in the system, hence P3 can complete. This will release the resources allocated to it, that is, 5 resources. Now P1 can complete since the  number of unallocated units of Ru exceeds the units needed to satisfy its maximum  requirement then P2 can be completed. Thus the


DC14                                                                      System Software and Operating System

processes can finish in the sequence P3, P1, and P2. Hence projected allocation state is safe so algorithm will grant the request made by P1.

Q.19.  What is a race condition? Explain how does a critical section avoid this condition.
What are the properties which a data item should possess to implement a critical section?         (6)

Race  condition:  The  situation  where  several  processes  access   and  manipulate shared  data concurrently. The final value of the shared data depends upon which process  finishes  last.  To  prevent  race  conditions,  concurrent  processes  must  be synchronized.
Data consistency requires that only one processes should update the value of a data item at  any time. This is ensured through the notion of a critical section. A critical section for data  item d is a section of code, which cannot be executed concurrently with itself or with other critical sections for d. Consider a system of n processes (P0, P1,…,       P n-1), each process has a segment of code called a critical section, in which the proceses may be changing common variables, updating a table, writing a file, and so on. The important feature of the system is that, when one process is executing in its critical section, no other process is to be allowed to  execute in its critical section. Thus the execution of critical sections by the processes is mutually exclusive in time.


Entry section

critical section

Exit section

remainder section
until FALSE

Solution to the Critical Section Problem must satisfy the following three conditions:
1.         Mutual Exclusion.  If process Pi is executing in its critical section, then no
other processes can be executing in their critical sections.
2.         Progress.  If no process is executing in its critical section and there exist some processes that wish to enter their critical section, then the selection of the processes that will enter the critical section next cannot be postponed indefinitely.
3.         Bounded Waiting A bound must exist on the number of times that other processes are allowed to enter their critical sections after a process has made a request to enter its critical section and before that request is granted.
Assume that each process executes at a nonzero speed
No assumption concerning relative speed of the n processes.
Q.20. Describe a solution to the Dining philosopher problem so that no races arise.    (4) Ans:
A solution to the dining philosopher problem:
monitor DP


DC14                                                                      System Software and Operating System

enum { THINKING; HUNGRY, EATING) state [5] ;
condition self [5];
void pickup (int i) { state[i] = HUNGRY; test(i);
if (state[i] != EATING) self [i].wait;
void putdown (int i) {
state[i] = THINKING;
// test left and right neighbors test((i + 4) % 5);
test((i + 1) % 5);
void test (int i) {
if ( (state[(i + 4) % 5] != EATING) && (state[i] == HUNGRY) &&
(state[(i + 1) % 5] != EATING) ) {
state[i] = EATING ;
self[i].signal () ;
initialization_code() {
for (int i = 0; i < 5; i++)
state[i] = THINKING;

Each philosopher I invokes the operations pickup() and putdown() in the following sequence:
dp.pickup (i) EAT
dp.putdown (i)

No comments:

Post a Comment