System Software And Operating System Important Descriptive Questions 2
If frames are increased say to 4, then number of page faults also increases, to 10 in this case.
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 
)
R1 R2
R3
R5
Entry section
Exit section
Q.11. Define the following:
(i) FIFO Page replacement algorithm.
(ii) LRU Page replacement algorithm. (6)
Ans:
(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
16
DC14 System Software and Operating System
|
(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 search performance. What approaches are adopted to handle collision? (8)
Ans:
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.
17
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.
(8)
Ans:
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
18
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 ‘a lue>’
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
START <constant> directive indicates that the first word of the target program generated by the assembler should be placed in the memory word with address
<constant>.
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)
Ans:
Algebraic expressions such as
a/b+(c-d)e
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 expression tree is evaluated using a post-order traversal of the expression tree as
follows:
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:
19
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)
Ans:
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 R2R3R4
R5R6
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)
20
DC14 System Software and Operating System
Ans:
(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”
In the expression "(a+b)-(a+b)/4", "common subexpression" refers 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 incurs substantial analysis 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 saved PSW information unit corresponding to this interrupt contains useful information for this purpose.
3. Return from interrupt processing.
(vii) Real time operating System
21
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 a r>;
where a bel> 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)
Ans:
(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:
22
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
(iii)
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)
Ans:
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
23
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)
Ans:
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.
repeat
Entry sectioncritical section
Exit sectionremainder 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
{
24
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