Q11- What is parsing? Explain any three parsing techniques.?
Ans-Parsing is the process of analyzing a text, made of a sequence of tokens, to
determine its grammatical structure with respect to a given formal grammer. Parsing
is also known as syntactic analysis and parser is used for analyzing a text. The task
of the parser is essentially to determine if and how the input can be derived from the
start symbol of the grammar.
Following are three parsing techniques:
Top-down parsing - Top-down parsing can be viewed as an attempt to find left-most
derivations of an input-stream by searching for parse trees using a top-down
expansion of the given formal grammar rules. Tokens are consumed from left to right.
Inclusive choice is used to accommodate ambiguity by expanding all alternative righthand-
sides of grammar rules.
Bottom-up parsing - A parser can start with the input and attempt to rewrite it to the
start symbol. Intuitively, the parser attempts to locate the most basic elements, then
the elements containing these, and so on. LR parsers are examples of bottom-up
parsers. Another term used for this type of parser is Shift-Reduce parsing.
Recursive descent parsing- It is a top down parsing without backtracking. This parsing
technique uses a set of recursive procedures to perform parsing. Salient advantages of
recursive descent parsing are its simplicity and generality. It can be implemented in
any language supporting recursive procedures.
Q12-
Ans-a)-For A Allocation- (4+1+1+0+0) = 6 & Available(3)=> 6+3=9
Q13-
Q14- Explain any three policies for process scheduling that uses resource consumption
information. What is response ratio?
Ans-
Three policies for process scheduling are described below in brief:
1. First-come First-served (FCFS) (FIFO)
– Jobs are scheduled in order of arrival
– Non-preemptive
• Problem:
– Average waiting time can be large if small jobs wait behind long ones
– May lead to poor overlap of I/O and CPU and convoy effects
2. Shortest Job First (SJF)
– Choose the job with the shortest next CPU burst
– Provably optimal for minimizing average waiting time
• Problem:
– Impossible to know the length of the next CPU burst
3. Round Robin(RR)
– Often used for timesharing
– Ready queue is treated as a circular queue (FIFO)
– Each process is given a time slice called a quantum
– It is run for the quantum or until it blocks
– RR allocates the CPU uniformly (fairly) across all participants. If average
queue length is n, each participant gets 1/n
– As the time quantum grows, RR becomes FCFS
– Smaller quanta are generally desirable, because they improve response time
• Problem:
– Context switch overhead of frequent context switch
Q15-Macros Vs Subroutines
(i) Macros are pre processor directives i.e. it is processed before the source
program is passed to the compiler.
Subroutines are blocks of codes with a specific task, to be performed and are
directly passed to the compiler.
(ii) In a macro call the pre processor replaces the macro template with its macro
expansion, in a literal way.
(iii) Macro increases the program size.
Q16-
Q.17. Write short notes on:
i. YACC.
ii. Debug monitors
Ans-(i)YACC stands for “Yet another Compiler-Compiler” : Computer program input
generally has some structure; in fact, every computer program that does input can be
thought of as defining an “input language” which it accepts. An input language may be
as complex as a programming language, or as simple as a sequence of numbers.
Unfortunately, usual input facilities are limited, difficult to use, and often are lax about
checking their inputs for validity.
YACC provides a general tool for describing the input to a computer program. The
YACC user specifies the structures of his input, together with code to be invoked as
each such structure is recognized. YACC turns such a specification into a subroutine
that handles the input process; frequently, it is convenient and appropriate to have most
of the flow of control in the user's application handled by this subroutine. The output
from YACC is LALR parser for the input programming laughing
(ii)Debug monitors provide debugging support for a program. A debug monitor
executes the program being debugged under its own control thereby providing
execution efficiency during debugging. There are debug monitors that are language
independent and can handle programs written in many languages. For example-DEC-
10. Debug monitor provide the following facilities for dynamic debugging:
1. Setting breakpoints in the program
2. Initiating a debug conversation when control reaches a breakpoint.
3. Displaying values of variables
4. Assigning new values to variables.
5. Testing user defined assertions and predicates involving program variables.
Q18-
Q19-Define deadlock? Explain the necessary conditions for deadlock to occur. (5)
Ans:Deadlock is a situation, in which processes never finish executing and system
resources are tied up, preventing other jobs from starting. A process requests
resources; if the resources are not available at that time, the process enters a wait
state. Waiting processes may never again change state, because the resources they
have requested are held by other waiting processes, thereby causing
deadlock.Necessary conditions for deadlock to occur are:
i. Mutual exclusion: At least one resource must be held in a nonsharable mode;
that is, only one process at a time can use the resource. If another process requests
that resource, the requesting process must be delayed until the resource has been
released.
ii. Hold and wait: A process must be holding at least one resource and waiting
to acquire additional resources that are currently being held by other processes.
iii. No pre-emption: Resources cannot be pre-empted; that is, a resource can be
released only voluntarily by the process holding it, after the process holding it has
completed its task.
iv. Circular wait: A set{P0, P1,……, Pn) of waiting processes must exist such
that P0 is waiting for a resource that is held by P1, P1 is waiting for a resource that is
held by P2, ……., Pn-1 is waiting for a resource that is held by Pn and Pn is waiting
for a resource that is held by P0.
All four conditions must hold simultaneously for a deadlock to occur and conditions
are not completely independent. For example, the circular-wait implies the hold-andwait
condition.
Q20-An operating system contains 3 resource classes. The number of resource units in
these classes is 7, 7 and 10. The current resource allocation state is shown below:
The sequence satisfies the safety criteria. So current allocation
state is safe.
(ii) Request made by process P1, Request(P1)= [1 1 0]
Here, Request(P1)< Need(P1) < Available
i.e. [1 1 0]< [1 4 5] < [2 3 0]
Pretending that request can be fulfilled, we get new state:
Q.21. Given memory partitions of 100k, 500k, 200k, 300k, and 600k (in order), apply first
fit and best fit algorithms to place processes with the space requirement of 212k,
417k, 112k and 426k (in order)? Which algorithm makes the most effective use of
memory?
Ans:
Given memory partitions of 100k, 500k, 200k, 300k, and 600k (in order), applying
first fit algorithms to place processes with the space requirement of 212k, 417k, 112k
and 426k (in order), we have the following status:
0 comments:
Post a Comment