143:
in that it causes a process to freeze. Two or more processes become deadlocked when each of them is doing nothing while waiting for a resource occupied by another program in the same set. On the other hand, a process is in starvation when it is waiting for a resource that is continuously given to
120:
Many operating system schedulers employ the concept of process priority. A high priority process A will run before a low priority process B. If the high priority process (process A) blocks and never yields, the low priority process (B) will (in some systems) never be scheduled—it will experience
125:. Modern scheduling algorithms normally contain code to guarantee that all processes will receive a minimum amount of each important resource (most often CPU time) in order to prevent any process from being subjected to starvation.
121:
starvation. If there is an even higher priority process X, which is dependent on a result from process B, then process X might never finish, even though it is the most important process in the system. This condition is called a
144:
other processes. Starvation-freedom is a stronger guarantee than the absence of deadlock: a mutual exclusion algorithm that must choose to allow one of two processes into a
89:. The name "finite bypass" means that any process (concurrent part) of the algorithm is bypassed at most a finite number times before being allowed access to the
117:, is supposed to allocate resources equitably; that is, the algorithm should allocate resources so that no process perpetually lacks necessary resources.
361:
328:
549:
544:
436:
554:
371:
294:
155:
technique. Aging is a technique of gradually increasing the priority of processes that wait in the system for a long time.
356:
321:
269:
386:
236:
204:
109:
always switches between the first two tasks while a third never gets to run, then the third task is being starved of
451:
86:
82:
411:
351:
314:
133:
151:
A possible solution to starvation is to use a scheduling algorithm with priority queue that also uses the
391:
164:
140:
20:
477:
416:
401:
114:
406:
55:
431:
421:
337:
196:
376:
366:
106:
472:
446:
129:
102:
66:
35:
8:
85:, and is one of the two requirements for any mutual exclusion algorithm; the other being
39:
518:
396:
152:
122:
441:
426:
290:
265:
232:
200:
189:
184:
145:
47:
27:
381:
220:
90:
43:
492:
487:
482:
538:
456:
257:
51:
502:
46:
to process its work. Starvation may be caused by errors in a scheduling or
497:
306:
224:
148:
and picks one arbitrarily is deadlock-free, but not starvation-free.
59:
110:
262:
Concurrent
Programming: Algorithms, Principles, and Foundations
264:. Springer Science & Business Media. pp. 10–11.
132:
may suffer from scheduling starvation. An example is
101:
Starvation is usually caused by an overly simplistic
128:
In computer networks, especially wireless networks,
188:
113:. The scheduling algorithm, which is part of the
536:
322:
219:
329:
315:
183:
362:Earliest eligible virtual deadline first
336:
252:
250:
248:
54:, and can be intentionally caused via a
537:
437:Statistical time-division multiplexing
284:
256:
105:. For example, if a (poorly designed)
310:
245:
229:The Art of Multiprocessor Programming
50:algorithm, but can also be caused by
289:. Wiley India Edition. p. 193.
65:When starvation is impossible in a
13:
81:. This property is an instance of
14:
566:
387:Generalized foreground-background
139:Starvation is normally caused by
42:is perpetually denied necessary
550:Processor scheduling algorithms
545:Concurrency (computer science)
278:
213:
177:
16:Resource shortage in computers
1:
170:
134:maximum throughput scheduling
96:
555:Problems in computer science
34:is a problem encountered in
7:
392:Highest response ratio next
165:Dining philosophers problem
158:
21:Starvation (disambiguation)
10:
571:
372:Fixed-priority pre-emptive
195:. Prentice Hall. pp.
69:, the algorithm is called
18:
511:
465:
402:Multilevel feedback queue
344:
287:Operating System Concepts
407:Process Contention Scope
231:. Elsevier. p. 24.
191:Modern Operating Systems
56:denial-of-service attack
432:Shortest remaining time
285:Galvin, Peter (2010).
377:Foreground-background
130:scheduling algorithms
338:Processor scheduling
107:multi-tasking system
103:scheduling algorithm
67:concurrent algorithm
36:concurrent computing
19:For other uses, see
32:resource starvation
519:Processor affinity
412:Proportional share
352:Deadline-monotonic
123:priority inversion
532:
531:
427:Shortest job next
357:Earliest deadline
296:978-81-265-2051-0
185:Tanenbaum, Andrew
562:
331:
324:
317:
308:
307:
301:
300:
282:
276:
275:
254:
243:
242:
221:Herlihy, Maurice
217:
211:
210:
194:
181:
146:critical section
77:or said to have
48:mutual exclusion
28:computer science
570:
569:
565:
564:
563:
561:
560:
559:
535:
534:
533:
528:
507:
478:Completely Fair
461:
340:
335:
305:
304:
297:
283:
279:
272:
255:
246:
239:
218:
214:
207:
182:
178:
173:
161:
99:
91:shared resource
71:starvation-free
24:
17:
12:
11:
5:
568:
558:
557:
552:
547:
530:
529:
527:
526:
521:
515:
513:
509:
508:
506:
505:
500:
495:
493:SCHED DEADLINE
490:
485:
480:
475:
469:
467:
463:
462:
460:
459:
454:
449:
444:
439:
434:
429:
424:
419:
417:Rate-monotonic
414:
409:
404:
399:
394:
389:
384:
379:
374:
369:
364:
359:
354:
348:
346:
342:
341:
334:
333:
326:
319:
311:
303:
302:
295:
277:
271:978-3642320279
270:
258:Raynal, Michel
244:
237:
212:
205:
175:
174:
172:
169:
168:
167:
160:
157:
98:
95:
52:resource leaks
15:
9:
6:
4:
3:
2:
567:
556:
553:
551:
548:
546:
543:
542:
540:
525:
522:
520:
517:
516:
514:
510:
504:
501:
499:
496:
494:
491:
489:
486:
484:
481:
479:
476:
474:
471:
470:
468:
464:
458:
457:YDS algorithm
455:
453:
450:
448:
445:
443:
440:
438:
435:
433:
430:
428:
425:
423:
420:
418:
415:
413:
410:
408:
405:
403:
400:
398:
395:
393:
390:
388:
385:
383:
380:
378:
375:
373:
370:
368:
365:
363:
360:
358:
355:
353:
350:
349:
347:
343:
339:
332:
327:
325:
320:
318:
313:
312:
309:
298:
292:
288:
281:
273:
267:
263:
259:
253:
251:
249:
240:
238:9780123977953
234:
230:
226:
222:
216:
208:
206:0-13-092641-8
202:
198:
193:
192:
186:
180:
176:
166:
163:
162:
156:
154:
149:
147:
142:
137:
135:
131:
126:
124:
118:
116:
112:
108:
104:
94:
92:
88:
84:
80:
79:finite bypass
76:
75:lockout-freed
72:
68:
63:
61:
57:
53:
49:
45:
41:
37:
33:
29:
22:
523:
503:SCHED NORMAL
286:
280:
261:
228:
215:
190:
179:
150:
138:
127:
119:
100:
78:
74:
70:
64:
31:
25:
422:Round-robin
225:Shavit, Nir
87:correctness
539:Categories
524:Starvation
498:SCHED FIFO
473:Brain Fuck
452:Windows NT
367:Fair-share
345:Algorithms
171:References
97:Scheduling
58:such as a
447:Two-level
60:fork bomb
44:resources
260:(2012).
227:(2012).
187:(2001).
159:See also
141:deadlock
111:CPU time
83:liveness
38:where a
397:Lottery
197:184–185
40:process
442:Stride
293:
268:
235:
203:
115:kernel
512:Other
466:Linux
153:aging
488:O(n)
483:O(1)
382:Gang
291:ISBN
266:ISBN
233:ISBN
201:ISBN
26:In
541::
247:^
223:;
199:.
136:.
93:.
73:,
62:.
30:,
330:e
323:t
316:v
299:.
274:.
241:.
209:.
23:.
Text is available under the Creative Commons Attribution-ShareAlike License. Additional terms may apply.