Chapter 5

Question 1

Lack of process synchronization can result in two extreme conditions:

Answer 1

deadlock or starvation

Question 2

In early OS, deadlock was known as __________

Answer 2

deadly embrace

Question 3

an extreme case of indefinite postponement

Answer 3

starvation

Question 4

Seven cases of deadlock

Answer 4

Case 1: Deadlocks on File Requests
Case 2: Deadlocks in Databases
Case 3: Deadlocks in Dedicated Device Allocation
Case 4: Deadlocks in Multiple Device Allocation
Case 5: Deadlocks in Spooling
Case 6: Deadlocks in a Network
Case 7: Deadlocks in Disk Sharing

Question 5

What is locking?

Answer 5

a technique used to guarantee the integrity of the data through which the user locks out all other users while working with the database

Question 6

Locking can be done at three different levels:

Answer 6

• the entire database can be locked for the duration of the request;
• a subsection of the database can be locked;
• or only the individual record can be locked until the process is completed.

Question 7

conditions for deadlock

Answer 7

Mutual exclusion
Resource holding
No preemption
Circular wait

Question 8

In general, operating systems use one of three strategies to deal with deadlocks:

Answer 8

• Prevent one of the four conditions from occurring (prevention).
• Avoid the deadlock if it becomes probable (avoidance).
• Detect the deadlock when it occurs and recover from it gracefully (detection)

Question 9

The Banker’s Algorithm is based on a bank with a fixed amount of capital that operates on the following principles:

Answer 9

• No customer will be granted a loan exceeding the bank’s total capital.
• All customers will be given a maximum credit limit when opening an account.
• No customer will be allowed to borrow over the limit.
• The sum of all loans won’t exceed the bank’s total capital.

Question 10

One algorithm was proposed by Dijkstra in 1965 to regulate resource allocation to avoid deadlocks.

Answer 10

The Banker’s Algorithm

Question 11

deadlock became more prevalent after the introduction of these systems

Answer 11

interactive systems

Question 12

There are several recovery algorithms, but they all have one feature in common:

Answer 12

They all require at least one victim, an expendable job, which, when removed from the deadlock, will free the system.

Question 13

Several factors must be considered to select the victim that will have the least-negative effect on the system. The most common are:

Answer 13

• The priority of the job under consideration—high-priority jobs are usually untouched
• CPU time used by the job—jobs close to completion are usually left alone
• The number of other jobs that would be affected if this job were selected as the victim

Question 14

recovery methods:

Answer 14

1. terminate every job that’s active in the system and restart them from the beginning.
2. terminate only the jobs involved in the deadlock and ask their users to resubmit them.
3. identify which jobs are involved in the deadlock and terminate them one at a time
4. use a snapshot of the job so it can continue without a restart
5. selects a nondeadlocked job, preempts the resources it’s holding, and allocates them to a deadlocked process so it can resume execution, thus breaking the deadlock
6. stops new jobs from entering the system, which allows the nondeadlocked jobs to run to completion so they’ll release their resources.

Question 15

How can we eliminate mutual exclusion

Answer 15

May be bypassed by spooling, which allows the output from many jobs to be stored in separate temporary spool files at the same time

Question 16

Directed graphs use these symbols:

Answer 16

Processes represented by circles and resources represented by squares

Question 18

How can we eliminate resource holding

Answer 18

By forcing each job to request, at creation time, every resource it will need to run to completion

Question 19

How to eliminate no preemption

Answer 19

By allowing the OS to deallocate resources from jobs

Question 20

How to eliminate circular wait

Answer 20

One solution was proposed by Havender, based on a numbering system.

Forces each job to request its resources in ascending order

Question 21

This scheme removes the possible of a circular wait and therefore guarantees the removal of deadlocks

Answer 21

Hierarchical ordering

Question 22

Difficulties of hierarchical ordering

Answer 22

1. Discovering the best order for the resources so that the needs of the majority of the users are satisfied
2. Assigning a ranking to nonphysical resources such as files where there is no basis for assigning a higher number to one over another

Question 23

What algorithm was used in avoidance

Answer 23

Banker’s Algorithm

Question 24

Steps to reduce a graph:

Answer 24

1. Find a process that is currently using a resource and not waiting for one. This process can be removed from the graph, and the resource can be returned to the available list
2. Find a process that’s waiting only for resource classes that aren’t fully allocated. This process isn’t contributing to deadlock since it would eventually get the resource it’s waiting for, finish its work, and return the resource to the “available list”
3. Go back to step 1 and continue with steps 1 and 2 until all lines connecting resources to process have been removed.

Question 25

Solution to address starvation problem

Answer 25

Algorithm same as aging, once starvation has been detected, the system can block new jobs until the starving jobs have been satisfied.

Question 26

result of liberal allocation of resources

Answer 26

deadlock

Question 27

result of conservative allocation of resources

Answer 27

starvation