Friday, 7 February 2014
Thursday, 6 February 2014
 |
OPERATING SYSTEMS: DEADLOCKS & CHARACTERIZATION |
Deadlock
A deadlock is
a situation in which two or more competing actions are each waiting for the
other to finish, and thus neither ever does.
In an operating system, a deadlock is a situation which occurs when a process or thread enters a waiting state because a resource requested is being held by another waiting process, which in
turn is waiting for another resource. If a process is unable to change its
state indefinitely because the resources requested by it are being used by
another waiting process, then the system is said to be in a deadlock.
Both processes need resources to continue
executing. P1 requires additional resource R1 and is in possession of resource
R2, P2 requires additional resource R2 and is in possession of R1; neither
process can continue.
Necessary condition
A deadlockers situation can arise
if all of the following conditions hold simultaneously in a system:
1. Mutual
Exclusion: At
least one resource must be held in a non-sharable mode. Only
one process can use the resource at any given instant of time.
2. Hold and Wait or Resource
Holding: A process is currently holding at least one resource and
requesting additional resources which are being held by other processes.
3. No Preemption: The operating system must
not de-allocate resources once they have been allocated; they must be released
by the holding process voluntarily.
4. Circular Wait: A process must be waiting
for a resource which is being held by another process, which in turn is waiting
for the first process to release the resource. In general, there is a set of
waiting processes, P = {P1, P2, ..., PN}, such
that P1 is waiting for a resource held by P2, P2 is
waiting for a resource held by P3 and so on until PN is
waiting for a resource held by P1.
These four conditions are known
as the Coffman conditions from their first description in a
1971 article by Edward G. Coffman, Jr. Unfulfillment
of any of these conditions is enough to preclude a deadlock from occurring.
Deadlock
can only occur in systems where all 4 conditions hold true.
Circular
wait prevention
Circular
wait prevention consists of allowing processes to wait for resources, but
ensure that the waiting can't be circular. One approach might be to assign a
precedence to each resource and force processes to request resources in order
of increasing precedence. That is to say that if a process holds some
resources, and the highest precedence of these resources is m, then this process cannot request any resource
with precedence smaller than m. This forces
resource allocation to follow a particular and non-circular ordering, so
circular wait cannot occur. Another approach is to allow holding only one
resource per process; if a process requests another resource, it must first
free the one it's currently holding (or hold-and-wait).
Avoidance
Deadlock can be
avoided if certain information about processes is available in advance of
resource allocation. For every resource request, the system sees if granting
the request will mean that the system will enter an unsafe state,
meaning a state that could result in deadlock. The system then only grants
requests that will lead to safe states. In order for the
system to be able to figure out whether the next state will be safe or unsafe,
it must know in advance at any time the number and type of all resources in
existence, available, and requested. One known algorithm that is used for
deadlock avoidance is the Banker's algorithm, which requires resource usage
limit to be known in advance. However, for many systems it is impossible to
know in advance what every process will request. This means that deadlock
avoidance is often impossible.
Two other algorithms
are Wait/Die and Wound/Wait, each of which uses a symmetry-breaking technique.
In both these algorithms there exists an older process (O) and a younger process
(Y). Process age can be determined by a time stamp at process creation time.
Smaller time stamps are older processes, while larger timestamps represent
younger processes.
Wait/Die
|
Wound/Wait
|
|
O needs a resource held by Y
|
O waits
|
Y dies
|
Y needs a resource held by O
|
Y dies
|
Y waits
|
It is important to note that a process may be in unsafe state but would not
result in a deadlock. The notion of safe/unsafe state only refers to the
ability of the system to enter a deadlock state or not. For example, if a
process requests A which would result in an unsafe state, but releases B which
would prevent circular wait, then the state is unsafe but the system is not in
deadlock
Prevention
Deadlocks can be
prevented by ensuring that at least one of the following four conditions occur:
·
Removing the mutual exclusion condition means that no process may
have exclusive access to a resource. This proves impossible for resources that
cannot be spooled, and even with spooled resources deadlock could still occur.
Algorithms that avoid mutual exclusion are called non-blocking synchronization
algorithms.
·
The "hold and wait" conditions may be removed by
requiring processes to request all the resources they will need before starting
up (or before embarking upon a particular set of operations); this advance
knowledge is frequently difficult to satisfy and, in any case, is an
inefficient use of resources. Another way is to require processes to release
all their resources before requesting all the resources they will need. This
too is often impractical. (Such algorithms, such as serializing tokens, are
known as the all-or-none algorithms.)
·
A "no preemption" (lockout) condition may also be
difficult or impossible to avoid as a process has to be able to have a resource
for a certain amount of time, or the processing outcome may be inconsistent or
thrashing may occur. However, inability to enforce preemption may interfere
with a priority algorithm. (Note: Preemption of a "locked
out" resource generally implies a rollback, and is to be avoided, since it
is very costly in overhead.) Algorithms that allow preemption include lock-free
and wait-free algorithms and optimistic concurrency control.
·
The circular wait condition: Algorithms that avoid circular waits
include "disable interrupts during critical sections" , and "use
a hierarchy to determine a partial ordering of resources" (where no
obvious hierarchy exists, even the memory address of resources has been used to
determine ordering) and Dijkstra's solution.
Detection
Often neither
deadlock avoidance nor deadlock prevention may be used. Instead deadlock
detection and process restart are used by employing an algorithm that tracks
resource allocation and process states, and rolls back and restarts one or more
of the processes in order to remove the deadlock. Detecting a deadlock that has
already occurred is easily possible since the resources that each process has
locked and/or currently requested are known to the resource scheduler or OS.
Detecting the possibility of a deadlock before it occurs is much more difficult and
is, in fact, generally undecidable, because the halting
problem can be rephrased as a deadlock scenario. However, in specific environments, using specific means of locking resources, deadlock
detection may be decidable.
In the general case, it is not possible to
distinguish between algorithms that are merely waiting for a very unlikely set
of circumstances to occur and algorithms that will never finish because of
deadlock.
Distributed
deadlock
Distributed
deadlocks can occur in distributed systems when distributed transactions or concurrency
control is being used. Distributed deadlocks can be detected either by
constructing a global wait-for graph, from local wait-for graphs at a deadlock
detector or by a distributed algorithm like edge chasing.
Phantom deadlocks are deadlocks that are detected in a
distributed system.
|
|
Operating System Questions and Answers |
_____is used in operating system to
separate to mechanism from policy
A.
Single level implementation
B.
Two level implementation
C.
Multi level implementation
D.
None
The operating
systems creates _____ fom the physical computer
A.
Virtual computers
B.
Virtual space
C.
Virtual device
D.
None
_____shares
characteristics with both hardware and software
A.
Operating system
B.
Software
C.
Data
D.
None
Multiprogramming systems:
A.
Are easier to develop than single programming
systems
B.
Execute each job faster
C.
Execute more jobs in the same time period
D.
Are used only one large mainframe computers.
Which is
built directly on the hardware?
A.
Computer Environment
B.
Application Software
C.
Operating System
D.
Database System
A.
Windows 98
B.
Windows NT
C.
Windows XP
D.
MS DOS
|
|
Virtual Memory Questions and Answers |
Fixed partitions
A.
are very common in current operating systems.
B.
are very efficient in memory utilization.
C.
are very inefficient in memory utilization.
D.
are most used on large mainframe operating
systems.
If a virtual memory system has 4 pages in real memory and
rest must be swapped to disk. Which of following is the hit ratio for the
following page address stream? Assume that memory starts emply. Use the First Out
(FIFO) algorithm.
A.
A.10%
B.
15%
C.
C.21%
D.
D.31%
A computer system has 4 k word cahe organized ina block _set
_associative manner, with 4 blocks per set ,64 words per block. The number of
bits in the set and WORD fields of the main memory address format is
A.
15,4
B.
6,4
C.
7,2
D.
4,6
In a paged segment scheme of memory management , the segment
table itself must have a page table because
A.
the segment is spread over a number to hit in one
page .
B.
each segment is spread over a number of pages.
C.
segment tables point to page tables and not to
the physical location of the segment .
D.
the processor’s description base register points
to a page table.
Which of the following statements is false?
A.
Segmentation suffers from external
fragmentation.
B.
Paging suffers from internal fragmentation.
C.
Segmented memory can be paged.
D.
Virtual memory is used only in multi-user
systems.
|
|
HTET Answer Key Level – 2 |
HTET Answer Key Level – 2 (TGT) SET – B (held on 02 Feb. 2014)
PART – II (Language – I English)
Q. No.
|
Answer
|
31
|
3) peirce
|
32
|
2) Tickets are being sold…
|
33
|
2) has
|
34
|
2) Listening, speaking, reading, writing
|
35
|
3) Abstract thinking
|
36
|
3) obligation
|
37
|
2) The grammar translation method
|
38
|
2) or 4) The policeman
|
39
|
3) sacrilegious
|
40
|
2) kaleidoscope
|
41
|
2) something so small…
|
42
|
20 used to
|
43
|
2) tell
|
44
|
1) the
|
45
|
4) A lot of
|
46
|
4) run out of
|
47
|
2) have been collected
|
48
|
3) would have passed
|
49
|
4) did you be
|
50
|
1) is
|
51
|
1) everybody regards fitness…
|
52
|
1) Statement (i) is true
|
53
|
4) We cannot be sedentary
|
54
|
1) To value someone…lightly
|
55
|
2) vitality
|
56
|
2) A quantum leap in the…
|
57
|
4) We want to get…
|
58
|
1) up
|
59
|
4) be
|
60
|
2) developed a strong bond
|
This is not Final and Official Key. It’s an individual effort only. (90% Correct)
|
|
MS-Access : Objective Questions |
1. What Are The Different Views To Display A Table
A) Datasheet View
B) Design View
C) Pivote Table & Pivot Chart View
D) All Of Above
2. Which Of The Following Creates A Drop Down List Of Values To Choose From?
A) Ole Object
B) Hyperlink
C) Memo
D) Lookup Wizard
3. The Command Center Of Access File That Appears When You Create Or Open The Ms Access Database File.
A) Database Window
B) Query Window
C) Design View Window
D) Switchboard
4. The Third Stage In Designing A Database Is When We Analyze Our Tables More Closely And Create A ___________ Between Tables
A) Relationship
B) Join
C) Query
D) None Of These
5. In A Database Table, The Category Of Information Is Called __________
A) Tuple
B) Field
C) Record
D) All Of Above
6. This Key Uniquely Identifies Each Record
A) Primary Key
B) Key Record
C) Unique Key
D) Field Name
7. It Is An Association Established Between Common
A) Line
B) Relationship
C) Primary Key
D) Records
8. This Is The Stage In Database Design Where One Gathers And List All The Necessary Fields For The Database Project.
A) Data Definition
B) Data Refinement
C) Establishing Relationship
D) None Of The Above
9. A Database Language Concerned With The Definition Of The Whole Database Structure And Schema Is ________
A) DCL
B) DML
C) DDL
D) All Of Above
10. Which Of The Field Has Width 8 Bytes?
A) Memo
B) Number
C) Date/time
D) Hyperlink
11. Which Of The Following Statement Is True?
A) Foreign Key Fields Don\'t Allow Duplicate Values
B) In Primary Key Field You Can Enter Duplicate Value
C) In An Indexed Field You May Or May Not Enter Duplicate Value Depending Upon Setting
D) All Statements Are True
12. Following Is Not A Database Model
A) Network Database Model
B) Relational Database Model
C) Object Oriented Database Model
D) None
13. Microsoft Access Is A
A) RDBMS
B) OODBMS
C) ORDBMS
D) Network Database Model
14. DCL Provides Commands To Perform Actions Like
A) Change The Structure Of Tables
B) Insert, Update Or Delete Records And Data Values
C) Authorizing Access And Other Control Over Database
D) None Of Above
15. The Database Language That Allows You To Access Or Maintain Data In A Database
A) DCL
B) DML
C) DDL
D) None Of Above
16. What Is The Maximum Length A Text Field Can Be?
A) 120
B) 255
C) 265
D) 75
17. Which Of The Following Is Not A Database Object?
A) Tables
B) Queries
C) Relationships
D) Reports
18. A __________ Enables You To View Data From A Table Based On A Specific Criterion
A) Form
B) Query
C) Macro
D) Report
19. What Are The Columns In A Microsoft Access Table Called?
A) Rows
B) Records
C) Fields
D) Columns
20. Which Of The Following Is Not A Type Of Microsoft Access Database Object?
A) Table
B) Form
C) Worksheets
D) Modules
Answers
1-D, 2-D, 3-A, 4-A, 5-B, 6-A, 7-B, 8-A, 9-C, 10-C, 11-C, 12-D, 13-A, 14-C, 15-A, 16-B, 17-C, 18-B, 19-C, 20-C
1. Which Of The Following Database Object Hold Data?
A) Forms
B) Reports
C) Queries
D) Tables
2. Which Of The Following Store Command To Retrieve Data From Database?
A) Forms
B) Reports
C) Queries
D) Tables
3. Which Of The Following Database Object Produces The Final Result To Present?
A) Forms
B) Reports
C) Queries
D) Tables
4. What Is The Difference Between ‘open’ And ‘open Exclusively’
A) Open Statement Opens Access Database Files And Open Exclusively Opens Database Files Of Other Program Like Oracle
B) Open Exclusive Locks Whole Database So That No One Can Access It Whereas Open Locks Only The Record That Is Being Accessed
C) Both Open And Open Exclusively Are Same
D) Open Exclusive Command Does Not Exist In Ms Access
5. Which Of The Following Is A Method To Create A New Table In Ms Access?
A) Create Table In Design View
B) Create Table Using Wizard
C) Create Table By Entering Data
D) All Of Above
6. To Create A New Table, In Which Method You Don’t Need To Specify The Field Type And Size?
A) Create Table In Design View
B) Create Table Using Wizard
C) Create Table By Entering Data
D) All Of Above
7. When Creating A New Table Which Method Can Be Used To Choose Fields From Standard Databases And Tables
A) Create Table In Design View
B) Create Table Using Wizard
C) Create Table By Entering Data
D) None Of Above
8. In Table Design View, Which Key Can Be Used To Switch Between The Field Names And Properties Panels?
A) F3
B) F4
C) F5
D) F6
9. In Table Design View What Are The First Column Of Buttons Used For
A) Indicate Primary Key
B) Indicate Current Row
C) Both Of Above
D) None Of Above
10. The Default And Maximum Size Of Text Field In Access
A) 50 And 255 Characters
B) 8 And 1 Gb
C) 266 Characters & 64000 Characters
D) None Of Above
11. The Size Of Yes No Field Is Always
A) 1 Bit
B) 1 Byte
C) 1 Character
D) 1 Gb
12. Which Of The Following Is Not A Field Type In Access
A) Memo
B) Hyperlink
C) Ole Object
D) Lookup Wizard
13. The Size Of A Field With Number Data Type Can Not Be
A) 2
B) 4
C) 8
D) 16
14. Which Field Type Will You Select When Creating A New Table If You Require To Enter Long Text In That Field?
A) Text
B) Memo
C) Currency
D) Hyperlink
15. Which Field Type Can Store Photos?
A) Hyperlink
B) Ole
C) Both Of These Can Be Used
D) Access Tables Can’t Store Photos
16. When Entering Field Name, How Many Characters You Can Type In Maximum?
A) 60
B) 64
C) 68
D) Any Number Of Character
17. After Entering All Fields Required For A Table, If You Realize That The Third Field Is Not Needed, How Will You Remove?
A) You Need To Delete The Whole Table. There Is No Method To Remove A Particular Field Only.
B) Delete All The Fields From Third Downwards And Reenter The Required Fields Again.
C) Select The Third Column In Datasheet View Then Delete
D) Select The Third Row In Table Design View Then Delete
18. How Can You Define A Field So That When Entering Data For That Field It Will Display ****** Instead Of Actual Typed Text
A) Input Mask
B) Validation Rule
C) Indexed
D) Ime Mode
19. A Small Button With Three Dots Usually Displayed At The Right Of Field Properties Box
A) Make Button
B) Expression Button
C) Build Button
D) None Of Above
20. To Sort Records In A Table
A) Open Table, Click On The Field On Which The Sorting Is To Be Done,Then Click Sort Button On Database Toolbar
B) Open Table, Click Sort Button On Database Toolbar, Choose Field Based On Which To Sort, Click Ok
C) Click The Field Heading To Sort It Ascending Or Descending
D) All Of Above
Answers:
1-D, 2-C, 3-B, 4-B, 5-D, 6-C, 7-B, 8-D, 9-C, 10-A, 11-A, 12-D, 13-D, 14-B, 15-B, 16-B, 17-D, 18-A, 19-C, 20-A,
Subscribe to:
Posts (Atom)