C191-Terms-Chapter-4

Question 1

Long-term scheduling

Answer 1

Decides when a process should enter the ready state and start competing for the CPU.

A process entering the RL from the suspended list is subject to long-term scheduling. The OS may want to decide whether it should be re-admitted to the current mix of processes to compete for the CPU.

Question 2

Short-term scheduling

Answer 2

Decides which of the ready processes should run next on the CPU.

When a running process becomes blocked and later reenters the RL, short-term scheduling is again applied to let the process compete for the CPU.

Whenever a running p isn’t allowed to continue running, it’s moved back to the RL by the OS. The decision to stop and remove the p is subject to short-term scheduling. Likewise, moving p back to the RL is also a short-term decision.

Question 3

non-preemptive scheduling algorithm

Answer 3

Allows a running process to continue until the process terminates or blocks on a resource.

When a process blocks and leaves the RL, a new p must be chosen to run.

Question 4

A preemptive scheduling algorithm

Answer 4

May stop the currently running process and choose another process to run. The decision is made whenever:

A new process enters the ready list.

A previously blocked or suspended process re-enters the RL.

The OS periodically interrupts the currently running process to give other processes a chance to run.

Question 5

priority of a process (or thread)

Answer 5

Is a numerical value that indicates the importance of the process relative to other processes. The scheduler uses this value to decide which process to run next.

The priority can be a constant value assigned when the process is created or can change dynamically based on some combination of the following parameters.

Question 6

arbitration rule

Answer 6

Decides which process should proceed if two or more processes have the same priority.

Question 7

Arrival time

Answer 7

A common parameter used to compute short-term priority.

The point in time when the process enters the RL.

Question 8

Departure time

Answer 8

A common parameter used to compute short-term priority.

The point in time when the process leaves the RL by entering the blocked or suspended state, or by terminating all work.

Question 9

Attained CPU time

Answer 9

A common parameter used to compute short-term priority.

The amount of CPU time used by the process since arrival.

Question 10

Real time in system

Answer 10

A common parameter used to compute short-term priority.

The amount of actual time the process has spent in the system since arrival.

The real time keeps increasing regardless of the state the process is in.

Question 11

Total CPU time

Answer 11

A common parameter used to compute short-term priority.

The amount of CPU time the process will consume between arrival and departure. For short-term scheduling, total CPU time is sometimes called the CPU burst.

Question 12

External priority

Answer 12

A common parameter used to compute short-term priority.

A numeric priority value assigned to the process explicitly at the time of creation.

Question 13

Deadline

Answer 13

A common parameter used to compute short-term priority.

A point in time by which the work of the process must be completed.

Question 14

Period

Answer 14

A common parameter used to compute short-term priority.

A time interval during which a periodically repeating computation must be completed. The end of each period is the implicit deadline for the current computation.

Question 15

Other considerations

Answer 15

A common parameter used to compute short-term priority.

The resource requirements of a process, such as the amount of memory used, or the current load on the system.

Question 16

batch process

Answer 16

Performs a long-running and generally repetitive task that does not require any intervention from the user. Ex: Payroll, insurance claims processing, weather prediction, scientific calculations.

The main objective in scheduling batch processes is to maximize the number of processes completed per unit of time.

The order in which processes are executed cannot reduce the total CPU times of the individual processes but can reduce the waiting times.

In modern computing, any long-running computation that does not require interaction with a user is called a batch job or batch process.

Question 17

FIFO (First-In-First-Out) algorithm

Answer 17

Also known as FCFS (First-Come-First-Served), schedules processes strictly according to the process arrival time.

The earlier the arrival, the higher the priority.

Theoretically, multiple processes could have the same arrival time, in which case the arbitration rule can pick a process at random. In practice, all requests are processed sequentially and thus all processes have different arrival times.

FIFO is non-preemptive.

Question 18

SJF (Shortest Job First) algorithm

Answer 18

Also known as SJN (Shortest Job Next), schedules processes according to the total CPU time requirements.

The shorter the required CPU time, the higher the priority. If multiple processes have the same CPU time requirement, then the arbitration rule can select a process based on the arrival times.

SJF is non-preemptive. A more appropriate name for SJF would be “Shortest Total CPU Time First”. Good for a batch OS.

Question 19

SRT (Shortest Remaining Time) algorithm

Answer 19

Schedules processes according to the remaining CPU time needed to complete the work.

The shorter the remaining CPU time, the higher the priority. If multiple processes have the same remaining time requirement, then the arbitration rule can select a process based on the arrival times.

SRT is the preemptive version of SJF.

Question 20

turnaround time

Answer 20

The turnaround time of a process is the time between arrival and departure, and is the sum of the total CPU time and the waiting time.

Question 21

average turnaround time (ATT)

Answer 21

For a set of n processes is the mean of the n individual turnaround times.

Question 22

Starvation

Answer 22

Another important objective in batch scheduling is to guarantee fairness.

Starvation is the indefinite postponement of a process while other processes are allowed to proceed. Both SJF and SRT can lead to starvation.

Question 23

interactive process

Answer 23

Communicates with the user in the form of a dialog by receiving commands or data from the keyboard or a pointing device and responding by generating output on the user’s terminal or another output device.

The primary goal in scheduling interactive processes is to respond promptly to each input.

Consequently, interactive processes must time-share the CPU using preemptive scheduling to give each process a chance to make progress in a timely manner.

Question 24

time quantum

Answer 24

Q, is a small amount of time (typically 10 to 100 milliseconds) during which a process is allowed to use the CPU.

Question 25

round-robin (RR) algorithm

Answer 25

Uses a single queue of processes. The priority is determined solely by a process’s position within the queue.

RR scheduling treats all processes as equals. External priorities can be used to divide processes into groups based on importance.

The process at the head of the queue has the highest priority and is allowed to run for Q time units. When Q ends, the process is moved to the tail of the queue and the next process now at the head of the queue is allowed to run for Q time units.

Question 26

ML scheduling algorithm

Answer 26

Multilevel (ML) scheduling maintains a separate queue of processes at each priority level. Within each level, processes are scheduled using RR.

ML is prone to starvation because it relies on the fact that queues are empty at certain times.

If a stream of processes continues arriving at some priority level k, then no process at any level below k will be able to run, leading to starvation of all processes at levels below k.

Question 27

multilevel feedback (MLF) algorithm

Answer 27

Multilevel feedback scheduling is similar to ML but addresses the problems of starvation and fairness by:

Using a different time quantum at each priority level.

Changing the priority of every process dynamically.

Under the multilevel feedback (MLF) algorithm a newly arriving process enters the highest-priority queue, N, and is allowed to run for Q time units.

When Q is exceeded, the process is moved to the next lower priority queue, N-1, and is allowed to run for 2Q time units. The quantum size is doubled with each decreasing priority level. Thus at priority level L, the maximum time allowed is 2(N-L)Q time units.

MLF automatically favors short-running processes while processes with long running times gradually migrate to lower priority levels.

Question 28

response time

Answer 28

Of a process is the elapsed time from the submission of a request (pressing the Enter key or clicking a mouse button) until the response begins to arrive. Guaranteeing adequate response time is the primary goal in the scheduling of interactive processes.

For a process running alone, the response time depends on the type of request.

When multiple processes time-share the CPU, the response time increases with the number of processes, the length of the time quantum, and the time it takes to perform a context switch.

Question 29

real-time process

Answer 29

Is characterized by continual input, which must be processed fast enough to generate nearly instantaneous output. Each arriving input item is subject to a deadline. Ex: Streaming of audio or video, processing and displaying radar data, control of robots or of fly-by-wire aircraft.

Question 30

period

Answer 30

Is a time interval (typically in milliseconds or even microseconds) within which each input item must be processed. The end of each period is the implicit deadline for processing the current item.

Question 31

rate monotonic (RM) algorithm

Answer 31

Schedules processes according to the period. The shorter the period, the higher the priority.

RM is preemptive.

RM is not guaranteed to produce a feasible schedule, but empirical evidence shows that RM is likely to produce a feasible schedule if CPU is less than approximately 0.7.

The actual value depends on the particular set of processes.

Question 32

earliest deadline first (EDF) algorithm

Answer 32

Schedules processes according to the shortest remaining time until the deadline. The shorter the remaining time, the higher the priority.

EDF is preemptive.

EDF is an optimal algorithm in that a feasible schedule is always guaranteed as long as U ≤ 1.

Question 33

feasible

Answer 33

A schedule is feasible if the deadlines of all processes can be met.

Question 34

CPU utilization (U)

Answer 34

Is the sum of the individual fractions of CPU times used by each process.

Question 35

A 2-tier approach for a general-purpose OS

Answer 35

The simplest approach is to divide processes into two groups. Real-time processes run at the highest priority level but due to their short running times can use FIFO. Interactive and batch processes can be scheduled together using MLF.

Question 36

A 2-tier approach with floating priorities

Answer 36

Real time processes use either FIFO or RR in an ML scheme. Interactive and batch processes use a variation of MLF.

Every process is assigned a base priority at creation but an increment is added based on the past action the process has taken.

Ex: Returning from a request for keyboard input would add 6 to the base priority while returning from a request for disk input would add only 1. Thus the current priority depends on the type of process and the process’s behavior.

Question 37

CPU utilization

Answer 37

We want to keep the CPU as busy as possible. Conceptually, CPU utilization can range from 0 to 100 percent. In a real system, it should range from 40 percent (for a lightly loaded system) to 90 percent (for a heavily loaded system).

Question 38

Throughput

Answer 38

If the CPU is busy executing processes, then work is being done. One measure of work is the number of processes that are completed per time unit, called throughput. For long processes, this rate may be one process over several seconds; for short transactions, it may be tens of processes per second.

Question 39

Turnaround time

Answer 39

From the point of view of a particular process, the important criterion is how long it takes to execute that process.

The interval from the time of submission of a process to the time of completion is the turnaround time. Turnaround time is the sum of the periods spent waiting in the ready queue, executing on the CPU, and doing I/O.

Question 40

Waiting time

Answer 40

The CPU-scheduling algorithm does not affect the amount of time during which a process executes or does I/O. It affects only the amount of time that a process spends waiting in the ready queue. Waiting time is the sum of the periods spent waiting in the ready queue.

Question 41

Response time

Answer 41

In an interactive system, turnaround time may not be the best criterion. Often, a process can produce some output fairly early and can continue computing new results while previous results are being output to the user.

Thus, another measure is the time from the submission of a request until the first response is produced. This measure, called response time, is the time it takes to start responding, not the time it takes to output the response.

Question 42

load sharing

Answer 42

If multiple CPUs are available, load sharing, where multiple threads may run in parallel, becomes possible, however scheduling issues become correspondingly more complex.

Question 43

multiprocessor

Answer 43

Traditionally, the term multiprocessor referred to systems that provided multiple physical processors, where each processor contained one single-core CPU.

However, the definition of multiprocessor has evolved significantly, and on modern computing systems, multiprocessor now applies to the following system architectures:

Multicore CPUs
Multithreaded cores
NUMA systems
Heterogeneous multiprocessing

Question 44

asymmetric multiprocessing

Answer 44

One approach to CPU scheduling in a multiprocessor system has all scheduling decisions, I/O processing, and other system activities handled by a single processor — the master server. The other processors execute only user code.

This asymmetric multiprocessing is simple because only one core accesses the system data structures, reducing the need for data sharing.

The downfall of this approach is the master server becomes a potential bottleneck where overall system performance may be reduced.

Question 45

symmetric multiprocessing (SMP)

Answer 45

The standard approach for supporting multiprocessors is symmetric multiprocessing (SMP), where each processor is self-scheduling. Scheduling proceeds by having the scheduler for each processor examine the ready queue and select a thread to run.

Note that this provides two possible strategies for organizing the threads eligible to be scheduled:

All threads may be in a common ready queue.
Each processor may have its own private queue of threads.

Question 46

multicore processor

Answer 46

Most contemporary computer hardware now places multiple computing cores on the same physical chip, resulting in a multicore processor.

Each core maintains its architectural state and thus appears to the operating system to be a separate logical CPU.

SMP systems that use multicore processors are faster and consume less power than systems in which each CPU has its own physical chip.

Question 47

memory stall

Answer 47

When a thread is on CPU and accesses memory contents that is not in the CPU’s cache, the thread execution stalls while the contents of that memory is fetched.

However, a memory stall can also occur because of a cache miss (accessing data that are not in cache memory).

Question 48

hardware threads

Answer 48

A given CPU core can run a single thread (one hardware thread per core) or more than one per core (multiple hardware threads per core) to optimize core use, for example to avoid memory stalls by switching hardware threads if the current thread causes a stall.

To remedy the situation of a memory stall, many recent hardware designs have implemented multithreaded processing cores in which two (or more) hardware threads are assigned to each core.

That way, if one hardware thread stalls while waiting for memory, the core can switch to another thread.

Question 49

chip multithreading (CMT)

Answer 49

A CPU with multiple cores, where each core supports multiple hardware threads supports chip multithreading.

From an operating system perspective, each hardware thread maintains its architectural state, such as instruction pointer and register set, and thus appears as a logical CPU that is available to run a software thread. This technique—known as chip multithreading (CMT)

Question 50

hyper-threading (also known as simultaneous multithreading or SMT)

Answer 50

Intel processors use the term hyper-threading to describe assigning multiple hardware threads to a single processing core.

Question 51

coarse-grained multithreading

Answer 51

A thread executes on a core until a long-latency event such as a memory stall occurs. Because of the delay caused by the long-latency event, the core must switch to another thread to begin execution.

However, the cost of switching between threads is high, since the instruction pipeline must be flushed before the other thread can begin execution on the processor core. Once this new thread begins execution, it begins filling the pipeline with its instructions.

Question 52

Fine-grained (or interleaved) multithreading

Answer 52

Switches between threads at a much finer level of granularity—typically at the boundary of an instruction cycle. However, the architectural design of fine-grained systems includes logic for thread switching. As a result, the cost of switching between threads is small.

It is important to note that the resources of the physical core (such as caches and pipelines) must be shared among its hardware threads, and therefore a processing core can only execute one hardware thread at a time.

Consequently, a multithreaded, multicore processor actually requires two different levels of scheduling

Question 53

Two levels of scheduling

Answer 53

On one level are the scheduling decisions that must be made by the operating system as it chooses which software thread to run on each hardware thread (logical CPU).

A second level of scheduling specifies how each core decides which hardware thread to run. There are several strategies to adopt in this situation. One approach is to use a simple round-robin algorithm to schedule a hardware thread to the processing core.

Note that the two different levels of scheduling are not necessarily mutually exclusive. In fact, if the operating system scheduler (the first level) is made aware of the sharing of processor resources, it can make more effective scheduling decisions.

Question 54

Load balancing

Answer 54

On SMP systems, it is important to keep the workload balanced among all processors to fully utilize the benefits of having more than one processor.

Load balancing attempts to keep the workload evenly distributed across all processors in an SMP system. It is important to note that load balancing is typically necessary only on systems where each processor has its own private ready queue of eligible threads to execute.

On systems with a common run queue, load balancing is unnecessary, because once a processor becomes idle, it immediately extracts a runnable thread from the common ready queue.

Question 55

push migration

Answer 55

An approach to load balancing.

A specific task periodically checks the load on each processor and—if it finds an imbalance—evenly distributes the load by moving (or pushing) threads from overloaded to idle or less-busy processors.

Question 56

Pull migration

Answer 56

Occurs when an idle processor pulls a waiting task from a busy processor. Push and pull migration need not be mutually exclusive and are, in fact, often implemented in parallel on load-balancing systems.

Question 57

processor affinity

Answer 57

Consider what happens to cache memory when a thread has been running on a specific processor. The data most recently accessed by the thread populate the cache for the processor. As a result, successive memory accesses by the thread are often satisfied in cache memory (known as a “warm cache”).

Because of the high cost of invalidating and repopulating caches, most operating systems with SMP support try to avoid migrating a thread from one processor to another and instead attempt to keep a thread running on the same processor and take advantage of a warm cache.

This is known as processor affinity—that is, a process has an affinity for the processor on which it is currently running.

Question 58

soft affinity

Answer 58

When an operating system has a policy of attempting to keep a process running on the same processor—but not guaranteeing that it will do so.

Here, the operating system will attempt to keep a process on a single processor, but it is possible for a process to migrate between processors during load balancing.

Question 59

hard affinity

Answer 59

Some systems provide system calls that support hard affinity, thereby allowing a process to specify a subset of processors on which it can run. Many systems provide both soft and hard affinity.

Question 60

NUMA

Answer 60

Non-uniform memory access. If the operating system’s CPU scheduler and memory-placement algorithms are NUMA-aware and work together, then a thread that has been scheduled onto a particular CPU can be allocated memory closest to where the CPU resides, thus providing the thread the fastest possible memory access.

Question 61

heterogeneous multiprocessing

Answer 61

Although mobile systems now include multicore architectures, some systems are now designed using cores that run the same instruction set, yet vary in terms of their clock speed and power management, including the ability to adjust the power consumption of a core to the point of idling the core.

Such systems are known as heterogeneous multiprocessing (HMP). A feature of some mobile computing CPUs in which cores vary in their clock speed and power management.

Question 62

big.LITTLE

Answer 62

ARM processor implementation of HMP in which high performance big cores are combined with energy efficient LITTLE cores.

By combining a number of slower cores with faster ones, a CPU scheduler can assign tasks that do not require high performance, but may need to run for longer periods, (such as background tasks) to little cores, thereby helping to preserve a battery charge.

Similarly, interactive applications which require more processing power, but may run for shorter durations, can be assigned to big cores.

Additionally, if the mobile device is in a power-saving mode, energy-intensive big cores can be disabled and the system can rely solely on energy-efficient little cores.

Question 63

Soft real-time systems

Answer 63

provide no guarantee as to when a critical real-time process will be scheduled. They guarantee only that the process will be given preference over noncritical processes.

Question 64

Hard real-time systems

Answer 64

have stricter requirements. A task must be serviced by its deadline; service after the deadline has expired is the same as no service at all.

Question 65

event latency

Answer 65

the amount of time that elapses from when an event occurs to when it is serviced.

Question 66

Interrupt latency

Answer 66

refers to the period of time from the arrival of an interrupt at the CPU to the start of the routine that services the interrupt.

When an interrupt occurs, the operating system must first complete the instruction it is executing and determine the type of interrupt that occurred.

It must then save the state of the current process before servicing the interrupt using the specific interrupt service routine (ISR). The total time required to perform these tasks is the interrupt latency

Question 67

dispatch latency

Answer 67

The amount of time required for the scheduling dispatcher to stop one process and start another is known as dispatch latency. Providing real-time tasks with immediate access to the CPU mandates that real-time operating systems minimize this latency as well.

The most effective technique for keeping dispatch latency low is to provide preemptive kernels. For hard real-time systems, dispatch latency is typically measured in several microseconds.

Question 68

conflict phase

Answer 68

The conflict phase of dispatch latency has two components:

Preemption of any process running in the kernel.

Release by low-priority processes of resources needed by a high-priority process.

Question 69

periodic

Answer 69

A type of real-time process that repeatedly moves between two modes at fixed intervals- needing CPU time and not needing CPU time.

the processes are considered periodic. That is, they require the CPU at constant intervals (periods).

Once a periodic process has acquired the CPU, it has a fixed processing time
T, a deadline D by which it must be serviced by the CPU, and a period P.

The relationship of the processing time, the deadline, and the period can be expressed as 0 <= T <= D <= P. The rate of a periodic task is 1/p.

Question 70

rate

Answer 70

The rate of a periodic task is 1/p.

A periodic real-time process has a scheduling rate of 1 / p (where p is the length of its running period).

Question 71

admission-control algorithm

Answer 71

In real-time scheduling, the scheduler may not allow a process to start if its scheduling request as impossible - if it cannot guarantee that the task will be serviced by its deadline.

The scheduler does one of two things. It either admits the process, guaranteeing that the process will complete on time, or rejects the request as impossible if it cannot guarantee that the task will be serviced by its deadline. Used with priority based scheduling.

Question 72

rate-monotonic scheduling algorithm

Answer 72

schedules periodic tasks using a static priority policy with preemption. If a lower-priority process is running and a higher-priority process becomes available to run, it will preempt the lower-priority process.

Upon entering the system, each periodic task is assigned a priority inversely based on its period. The shorter the period, the higher the priority; the longer the period, the lower the priority. The rationale behind this policy is to assign a higher priority to tasks that require the CPU more often.

Furthermore, rate-monotonic scheduling assumes that the processing time of a periodic process is the same for each CPU burst. That is, every time a process acquires the CPU, the duration of its CPU burst is the same.

Question 73

Earliest-deadline-first (EDF)

Answer 73

scheduling assigns priorities dynamically according to deadline. The earlier the deadline, the higher the priority; the later the deadline, the lower the priority.

Under the EDF policy, when a process becomes runnable, it must announce its deadline requirements to the system. Priorities may have to be adjusted to reflect the deadline of the newly runnable process. Note how this differs from rate-monotonic scheduling, where priorities are fixed.

Question 74

Proportional share

Answer 74

Proportional share schedulers operate by allocating shares among all applications assuring each gets a specific portion of CPU time.

Schedulers operate by allocating T shares among all applications. An application can receive N shares of time, thus ensuring that the application will have N/T of the total processor time. Used in proportional share scheduling.

Question 75

analytic evaluation

Answer 75

One major class of evaluation methods is analytic evaluation. Analytic evaluation uses the given algorithm and the system workload to produce a formula or number to evaluate the performance of the algorithm for that workload.

Question 76

Deterministic modeling

Answer 76

one type of analytic evaluation. This method takes a particular predetermined workload and defines the performance of each algorithm for that workload.

Deterministic modeling is simple and fast. It gives us exact numbers, allowing us to compare the algorithms.

However, it requires exact numbers for input, and its answers apply only to those cases. The main uses of deterministic modeling are in describing scheduling algorithms and providing examples.

In cases where we are running the same program over and over again and can measure the program’s processing requirements exactly, we may be able to use deterministic modeling to select a scheduling algorithm.

Furthermore, over a set of examples, deterministic modeling may indicate trends that can then be analyzed and proved separately.

Question 77

Queueing models

Answer 77

On many systems, the processes that are run vary from day to day, so there is no static set of processes (or times) to use for deterministic modeling.

What can be determined, however, is the distribution of CPU and I/O bursts. These distributions can be measured and then approximated or simply estimated. The result is a mathematical formula describing the probability of a particular CPU burst.

We can describe the distribution of times when processes arrive in the system (the arrival-time distribution). From these two distributions, it is possible to compute the average throughput, utilization, waiting time, and so on for most algorithms.

Question 78

queueing-network analysis.

Answer 78

The computer system is described as a network of servers. Each server has a queue of waiting processes. The CPU is a server with its ready queue, as is the I/O system with its device queues. Knowing arrival rates and service rates, we can compute utilization, average queue length, average wait time, and so on.

At the moment, the classes of algorithms and distributions that can be handled are fairly limited.

The mathematics of complicated algorithms and distributions can be difficult to work with. Thus, arrival and service distributions are often defined in mathematically tractable—but unrealistic—ways.

It is also generally necessary to make a number of independent assumptions, which may not be accurate.

Question 79

Simulations

Answer 79

To get a more accurate evaluation of scheduling algorithms, we can use simulations. Running simulations involves programming a model of the computer system.

Software data structures represent the major components of the system. The simulator has a variable representing a clock. As this variable’s value is increased, the simulator modifies the system state to reflect the activities of the devices, the processes, and the scheduler.

As the simulation executes, statistics that indicate algorithm performance are gathered and printed.

Question 80

The data to drive the simulation can be generated in several ways

Answer 80

The most common method uses a random-number generator that is programmed to generate processes, CPU burst times, arrivals, departures, and so on, according to probability distributions. The distributions can be defined mathematically (uniform, exponential, Poisson) or empirically.

If a distribution is to be defined empirically, measurements of the actual system under study are taken. The results define the distribution of events in the real system; this distribution can then be used to drive the simulation.

Question 81

A distribution-driven simulation may be inaccurate

Answer 81

Because of relationships between successive events in the real system. The frequency distribution indicates only how many instances of each event occur; it does not indicate anything about the order of their occurrence.

To correct this problem, we can use trace files. We create a trace by monitoring the real system and recording the sequence of actual events.

We then use this sequence to drive the simulation. Trace files provide an excellent way to compare two algorithms on exactly the same set of real inputs. This method can produce accurate results for its inputs.

Question 82

Regression testing

Answer 82

confirms that the changes haven’t made anything worse, and haven’t caused new bugs or caused old bugs to be recreated (for example because the algorithm being replaced solved some bug and changing it caused that bug to reoccur).

Question 83

analytic evaluation

Answer 83

A means of comparing scheduling algorithm effectiveness by analyzing an algorithm against a workload and assigning it a score.

Question 84

deterministic modeling

Answer 84

One type of analytic evaluation, which takes a particular predetermined workload and defines the performance of each algorithm for that workload.

Question 85

queueing-network analysis

Answer 85

An area of computing study in which algorithms are analyzed for various aspects and effectiveness.

Question 86

Little’s formula

Answer 86

A scheduling equation (n = λ × W) that is particularly useful because it is valid for any scheduling algorithm and arrival distribution.

Question 87

trace files

Answer 87

A scheduling algorithm evaluation method in which thread details are captured on real systems and various scheduling algorithms analyzed to determine effectiveness.