Question

Answer the following questions about Starvation.

1. Explain what it means for a job to experience Starvation.
2. How is starvation similar to or different from Deadlock or Livelock?
3. What can an operating system do to prevent a starving job from "remaining in the system forever"?

Answer 1

1. ) Starvation or indefinite blocking is phenomenon associated with the Priority scheduling algorithms, in which a process ready to run for CPU can wait indefinitely because of low priority. In heavily loaded computer system, a steady stream of higher-priority processes can prevent a low-priority process from ever getting the CPU. Here we can use both the terms process or job ,both are same.

Starvation also occurs if a process is indefinitely postponed. This may happen if the process requires a resource for execution that it is never allotted or if the process is never provided the processor for some reason.

Some of the common causes of starvation are as follows:

1. If a process is never provided the resources it requires for execution because of faulty resource allocation decisions, then starvation can occur.
2. A lower priority process may wait forever if higher priority processes constantly monopolize the processor.
3. Starvation may occur if there are not enough resources to provide to every process as required.
4. If random selection of processes is used then a process may wait for a long time because of non-selection.

Deadlock and Starvation both are the conditions where the processes requesting for a resource has been delayed for a long. Although deadlock and starvation both are different from each other in many aspects. Deadlock is a condition where no process proceeds for execution, and each waits for resources that have been acquired by the other processes. On the other hands, in Starvation, process with high priorities continuously uses the resources preventing low priority process to acquire the resources.

B)

Difference between Deadlock and Starvation in OS

1. Definition of Deadlock and Starvation

Both deadlock and starvation are related concepts that prevent a fair system scheduling where the processes are blocked from gaining access to the resources. Deadlock, as the name suggests, refers to a condition where a set of threads or processes are blocked because each process is waiting to acquire a resource that is being held by another process thereby resulting in a deadlock situation where the programs cease to function. Starvation, on the other hand, is triggered by a deadlock which causes a process to freeze because a low priority process is denied access to a resource that is allocated to a high priority process.

2. Condition

A deadlock refers to a specific condition that occurs when a thread or a process goes into a waiting period because the system resource it requested is being held by another process, which in turn is waiting for another process to release its resource thereby creating a deadlock. This is caused by poor resource utilization. Starvation is an indefinite postponement condition where a low priority process is denied access to the resources it requires because the resources are being allocated to another high priority process. It is a resource management problem which forces the system to allocate resources to only high priority processes.

3. Characterization of Deadlock and Starvation

Deadlock is the ultimate form of starvation that is caused when the following four conditions occur concurrently: Mutual Exclusion, No Preemption, Hold & Wait, and Circular Wait. A deadlock condition occurs only in systems in which all the four conditions hold true. Starvation occurs based on different conditions such as when there aren’t enough resources to go around and priority of processes starts getting lower or when processes start handing resources to other processes without control. If a low priority process requests a resource reserved for highest priority processes, the process starves forever. Starvation also occurs when resources are allocated arbitrarily causing processes to wait for a longer period of time.

4. Prevention

Starvation can be prevented by using a proper scheduling algorithm with priority queue that in fact also uses the aging technique , a scheduling technique which adds the aging factor to the priority of each request meaning it increases the priority level of low priority processes that have been waiting for a long time. Also providing more resources to programs should avoid continued congestion of resources. To prevent the system from going into a deadlock, processes must be denied access to one or more resources while simultaneously waiting for others and only one process should be allowed to access a resource at a time.

BASIS FOR COMPARSION	DEADLOCK	STARVATION
Basic	Deadlock is where no process proceeds, and get blocked.	Starvation is where low priority processes get blocked, and high priority process proceeds.
Arising condition	The occurrence of Mutual exclusion, Hold and wait, No preemption and Circular wait simultaneously.	Enforcement of priorities, uncontrolled resource management.
Other name	Circular wait.	Lifelock.
Resources	In deadlocked, requested resources are blocked by the other processes.	In starvation, the requested resources are continuously used by high priority processes.
Prevention	Avoiding mutual exclusion, hold and wait, and circular wait and allowing preemption.	Aging

Livelock occurs when two or more processes continually repeat the same interaction in response to changes in the other processes without doing any useful work. These processes are not in the waiting state, and they are running concurrently. This is different from a deadlock because in a deadlock all processes are in the waiting state.

A livelock is similar to a deadlock, except that the states of the processes involved in the livelock constantly change with regard to one another, none progressing. Livelock is a special case of resource starvation; the general definition only states that a specific process is not progressing.

A deadlock is a state in which each member of a group of actions, is waiting for some other member to release a lock. A livelock on the other hand is almost similar to a deadlock, except that the states of the processes involved in a livelock constantly keep on changing with regard to one another, none progressing. Thus Livelock is a special case of resource starvation, as stated from the general definition, the process is not progressing. Starvation is a problem which is closely related to both, Livelock and Deadlock. In a dynamic system, requests for resources keep on happening. Thereby, some policy is needed to make a decision about who gets the resource when. This process, being reasonable, may lead to a some processes never getting serviced even though they are not deadlocked.

C)

Solution to to prevent a starving job from "remaining in the system forever"

Aging

Aging is a technique of gradually increasing the priority of processes that wait in the system for a long time so that it will get opportunity to get executed.

For example, if priority of a process ranges from 127(low) to 0(high), we could increase the priority of a waiting process by 1 Every 15 minutes. Eventually even a process with an initial priority of 127 would take no more than 32 hours for priority 127 process to age to a priority 0 process.