Topic: task scheduling

topics > computer science > Group: parallel processing

program control
action chunks
data flow machines
defining a process
dynamic code modification
hard real time systems
high priority processes
interrupt handler
multi-user systems
non-deterministic processing
non-preemptive task scheduling
operating system kernel
plan-based task scheduling
process threads
real time systems
Subtopic: processor scheduling up

Quote: never seek optimal scheduling; merely avoid persistently pessibal decisions [»hoarCA10_1974]
Quote: few parameters work in processor scheduling; interactive vs. batch, foreground vs. background, fixed share of cycles per job, unused cycles wasted [»lampBW10_1983]
Quote: the computer time given to a user is proportional to the shares provided; whether high or low priority, sequential or multiple jobs [»larmJ9_1978]
Quote: use preemptive scheduling where possible; use grain of time to secure independence [»hoarCA10_1974]
Quote: when scheduling, keep a low variance and mean on waiting times [»hoarCA10_1974]

Subtopic: livelock up

Quote: when scheduling, ensure that every program makes progress; avoid fixed priorities and infinite overtaking [»hoarCA10_1974]
Quote: avoid receive livelock by round-robin polling on interrupts and interrupt only when not polling; guarantees CPU for user tasks [»moguJC8_1997]

Subtopic: load management up

Quote: shed load to control demand rather than allowing the system to become overloaded [»lampBW10_1983]
Quote: use bi-modal scheduler for weakly-hard real-time; panic mode guarantees tasks will meet scheduability constraints [»bernG12_2001]

Subtopic: scheduler up

Quote: need an overall control program to direct individual transactions and to transfer program output to other programs or to system output [»jackMA_1975]
Quote: the Comit dispatcher takes a branch that was specified earlier or takes a random branch from a set [»comit_1961, OK]
QuoteRef: sammJE_1969 ;;427 Comit uses routing for non-replacement operations; e.g., shelving, I/O, free storage
QuoteRef: sammJE_1969 ;;430 dispatcher by logical subscripts changed by routing (by merging or from workspace by *Dj where jth constituent subscripts merged
Quote: the DDM1 data flow machine can distribute concurrent subnets to subelements of a process-store element [»daviAL_1979]

Subtopic: fine grain up

Quote: survey of fine-grain thread packages; good for medium-grain; none supported fine-grain with a general thread model [»pricGW11_2003]

Subtopic: dual-mode scheduling up

Quote: low overhead scheduler combines unsorted queues for Earliest Deadline First (short tasks) with a priority queue for Rate Monotonic (all others) [»zubeKM10_2001]
Quote: Cilk generates a fast and slow clone of every procedure; use slow clone for parallel semantics; use fast clone for work-first [»frigM6_1998]
Quote: when a processor runs out of work, it attempts to steal a slow clone; otherwise processors work on quick clones at tail of deque; a fast clone and its children were never stolen [»frigM6_1998]

Subtopic: overload up

Quote: on overload, drop packets early; once accept packet, process to completion

Subtopic: rate monotonic scheduling up

Quote: generalized rate monotonic scheduling gives predictable response time, schedulability, and stable overload; models aperiodic as periodic [»shaL9_1993]
Quote: rate-monotonic scheduling assigns higher priority to short tasks; achieves 69% utilization for high-priority periodic tasks and more for lower priority tasks [»rajkR_1991]
Quote: use rate-monotonic priority assignment for optimal, static priorities; highest priority given to task with highest request rate [»liuCL1_1973]
Quote: use constant-ratio grid with rate-monotonic scheduling and ratio <2; e.g., 256 priority levels from 1 msec to 100 seconds has a schedulability loss of 0.0014 [»shaL6_1991]

Subtopic: deadline-based scheduling up

Quote: only independent, periodic, regular tasks can have hard deadlines; no hard deadlines for nonperiodic tasks such as initialization and failure recovery [»liuCL1_1973]
Quote: deadline monotonic scheduling allows tasks to have a deadline earlier than the end of its period [»shaL9_1993]
Quote: assign higher priorities to tasks with narrower windows for execution
Quote: define task priority as its deadline in microseconds; better than priority levels since easily understood [»clarDD12_1995]
Quote: deadline promotion -- a task with a short deadline can promote a task with a long deadline if it holds a locked monitor [»clarDD12_1995]
Quote: a critical instance occurs when a task has the longest response time; i.e., when requested with higher priority tasks [»liuCL1_1973]

Subtopic: time vs work-based scheduling up

Quote: time-based scheduling is better than work-based scheduling for real-time garbage collector; yields consistent utilization without frequent pauses [»bacoDF1_2003]

Subtopic: scheduling by topological sort up

Quote: Lustre scheduling by topological sort; disallows syntactically cyclic definitions [»benvA1_2003]

Subtopic: fair priority up

Quote: a priority scheme is fair if no node always receives high priority for updates [»rahiSK_1982]
Quote: for fair priority, periodically reset local clocks and the node sequence number [»rahiSK_1982, OK]

Subtopic: priority inversion/inheritance up

Quote: synchronization primitives can lead to priority inversion; solve with priority inheritance and priority ceiling protocols [»shaL9_1990]
Quote: under priority inheritance, a job executes its critical section at the highest priority level of all blocked processes [»shaL9_1990]
Quote: under priority ceilings, if a job can not preempt other jobs, those jobs execute at at least its priority level; no deadlocks or chained blocks [»shaL9_1990]
Quote: a priority inheritance protocol executes critical sections at the highest priority level of all blocked jobs; prevents priority inversion [»rajkR_1991]
Quote: the priority ceiling protocol is a priority inheritance protocol that avoids both multiple blocking and deadlocks; good performance [»rajkR_1991]

Subtopic: random search up

Quote: random search of scheduling solutions more effective than complete search; master or collar variables determine the behavior [»menzT1_2007]

Subtopic: message scheduling up

Quote: when Medusa blocks on a communication channel, it waits a 'pause' time in case the block is temporary [»oustJK2_1980]
Quote: a V server can process messages in any order; for scheduling flexibility

Subtopic: non-active processes up

Quote: Thoth has resident and transient teams of processes; transient teams swapped to secondary storage as needed [»cherDR2_1979]
Quote: a stunned process has not started, or under debugging or migration; gives system requirements, address space, thread state, client ports [»taneAS12_1990]

Subtopic: process queues up

Quote: each process is on exactly one process queue; used for monitor locks, condition variables, and fault handlers [»johnRK3_1982]

Subtopic: event queue up

Quote: the sleep command suspends a process until an event occurs; reactivated when no process with a higher, given priority [»ritcDM_1979]
Quote: a process's evaluation stack is always empty when it blocks for a condition or a monitor [»johnRK3_1982]

Subtopic: interrupts up

Quote: prioritized interrupts leads to short critical sections, while the traditional interrupt scheme has a high overhead; up to 12% of CPU time [»smalC1_1997]

Subtopic: timer up

Quote: redesigned BSD timer facilities; constant time operations; scalable; bounded interrupt time [»costAM7_1998]
Quote: use efficient, trigger states and timing wheels for soft timers; end of system call, end of exception handler, end of interrupt handler, idle loop [»aronM8_2000]

Related Topics up

Group: program control   (27 topics, 547 quotes)
Topic: action chunks (6 items)
Topic: data flow machines (14 items)
Topic: deadlocks (21 items)
Topic: defining a process (23 items)
Topic: dynamic code modification (15 items)
Topic: hard real time systems (64 items)
Topic: high priority processes (13 items)
Topic: interrupt handler (20 items)
Topic: interrupts (25 items)
Topic: multi-tasking (22 items)
Topic: multi-user systems (4 items)
Topic: non-deterministic processing (19 items)
Topic: non-preemptive task scheduling (16 items)
Topic: operating system kernel (67 items)
Topic: plan-based task scheduling (13 items)
Topic: process threads (25 items)
Topic: real time systems
(14 items)

Updated barberCB 3/06
Copyright © 2002-2008 by C. Bradford Barber. All rights reserved.
Thesa is a trademark of C. Bradford Barber.