• Shuffle
    Toggle On
    Toggle Off
  • Alphabetize
    Toggle On
    Toggle Off
  • Front First
    Toggle On
    Toggle Off
  • Both Sides
    Toggle On
    Toggle Off
  • Read
    Toggle On
    Toggle Off
Reading...
Front

Card Range To Study

through

image

Play button

image

Play button

image

Progress

1/67

Click to flip

Use LEFT and RIGHT arrow keys to navigate between flashcards;

Use UP and DOWN arrow keys to flip the card;

H to show hint;

A reads text to speech;

67 Cards in this Set

  • Front
  • Back

What 4 things should a good scheduler do?

1) minimize user response times of all interactive processes (major objective today!)


2) maximize system throughput


3) be fair


4) avoid starvation

What is starvation?

Some ready processes never get core time, which is a problem typical to schedulers using priority i.e its when the lowest priority processes keep getting set aside.

How is starvation remedied?

Increase priorities of processes that have waited too long.

Which is more difficult, ensuring fairness or avoiding starvation?

Ensuring fairness.

What does a non-preemptive CPU scheduler never do?

It will never remove a core from a running process; it will wait because the process has yet to release the core, issue a system call, and terminate. When it does so, it is obsolete.

What is FCFS? Describe it.

First come first served (FCFS)


simple and easy to use scheduler that uses FIFO queue

Why is FCFS not as great as it sounds?

Processes that require less core time have to wait behind processes that make bigger demands.

What is SJF? What does it do?

Shortest job first (SJF)


Gives a core to the process requesting the least amount of core time.

List +/-s of SJF.

+ gives a core to the process requesting the least amount of time


+reduces average wait




- must know ahead of time how much of core time each process needs, which is impossible


- still lets processes monopolize a core

What does a preemptive scheduler do?

Temporarily returns a running process to the ready queue whenever another process requires that core in a more urgent fashion.

When does a process demand a core more urgently than normal?

1) when it has been waiting for too long.


2) when it has higher priority.

List the traits of preemptive schedulers without priorities.

1) all processes have the same priority


2) ready queue is FIFO

List the traits of preemptive schedulers with priorities.

1) use multiple queues


2) differ in the way they adjust process priorities

What basic assumption does round robin make?

It assumes that all processes have the same priority.

What differentiates round robin from FCFS?

processes only get a core for up to T time units

What happens to processes that exceed their slice time?

They return to the end of the ready queue.

What is the benefit of using a large time slice?

Less context switches

What is the benefit of using a small time slice?


Is this a true CPU schedule? 

Is this a true CPU schedule?

No, it is ideal. The graphic here is a true CPU schedule.

No, it is ideal. The graphic here is a true CPU schedule.

What problem do you need to solve to find the right time slice?

Adjust the time slice to guarantee a maximum waiting time in the ready queue.

Adjust the time slice to guarantee a maximum waiting time in the ready queue.

How much system load leads to very small time slices being produced? Is there a problem with this? Justify your answer.

heavy load,


Yes, results in overabundance of context switch overhead

When does this equation work well?

When does this equation work well?

When a system is lightly loaded.

What happens to a system using a round robin scheduler when the workload exceeds some threshold?

The throughput of the system decreases.

How is the decreased throughput of an overloaded RR solve?

By adding priorities.

What do the new priorities that solve decreased throughput of an RR distinguish among?

1) CPU bound processes (large amounts of core time)


2) interactive processes


3) IO bound processes (small amounts of core time)

Organize by priority: IO bound processes, interactive processes, CPU bound processes

interactive


IO


CPU

How does the size of time slices assigned to a process correspond to its priority?

Highest priority = smallest time slices


Lowest pritority = biggest time slices




higher priority processes can take cores from lower priority processes

How is the response time of an interactive process affected by its priority?

interactive processes will get good response times

How does prioritizing the CPU aid overloaded RR?

CPU bound processes will get the CPU...


less frequently than with RR and for longer periods of time thus there will be less context switch overhead

What two problems arise when dealing with RR overload?

1) how is priority assigned to processes? (since process behaviors can change during their execution)


2) how is starvation avoided?

How is priority assigned to processes? (since process behaviors can change during their execution)

Dynamic priorities are used.

Summarize the reward/penalize scheme of dynamic prioritizing.

Reward:


1) processes that use system calls


2) processes that interact with user


3) processes that have been in the ready queue for an extended period of time




Penalize:


processes that have exceeded their time slice

What is the numeric priority convention for UNIX System V?

0 is lowest



What is the numeric priority convention for most UNIX systems?

0 is highest

What is the numeric priority convention for Linux?

0 is highest

What is the numeric priority convention for Windows NT and beyond?

0 is lowest

Name the three process classes of a system V.4 scheduler

1) real-time


2) time-sharing


3) system (for kernel processes)

Of the three process classes, which has the lowest priority?

time-sharing

Of the three process classes, which has the highest priority?

real time

Are real time priorities fixed?

yes

Are time-sharing priorities fixed?

No, they use variable priorities

In a time-sharing process, what can the system administrator specify at each priority level?

1) maximum flexibility


2) maximum risk of making a bad choice

In a real-time process, what can the system administrator specify at each priority level?

a different quantum size (rt_quantum)

What can happen to a time-sharing processs if there are too many tuning options left to the system admin?

the likelihood of the system being "out of tune" increases

Recall the five examples of time-sharing parameters given in the slides.

1) quantum size (ts_quantum)


2) new priority for processes that use their whole CPU quantum (ts_tqexp)


3) new priority for proc returning from waiting state (ts_slpret)


4) Max. amount of time a process can remain in the ready queue without having priority recomputed (ts_maxwait)


5) new priority for processes that have been in the ready queue for ts_maxwait (ts_lwait)

The priority of a process is decreased when...

it has exhausted its time quantum

The priority of a process is increased when...

1) it has completed a system call


2) it has waited a in the ready queue for a long time

Which of the five examples of time-sharing parameters given in the slide are used to reward "good" behaviors?

ts_slpret


ts_lwait

Which of the five examples of time-sharing parameters given in the slide are used to reward "bad" behaviors?

ts_tqexp

a

a

What does IVP stand for? Name three types of equations that this encompasses.
initial value problem 1) first order equations 2) higher order equations 3) systems of differential equations"
What does BVP stand for? Name two types of problems that this encompasses
"boundary value problems 1) two point boundary value problems 2) Strum–Liouville eigenvalue problems"
What does PDE stand for?Name three types of equations that this encompasses.
"partial differential equation 1) diffusion equations 2) advection equations 3) wave equations"
What form must a second order differential equation have to be linear?
"a*y'' + b*p(x)*y' + q(x)*y = g(x), where a, b, and c are constants p(t), q(t) and g(t) are functions of x"
How many priority bands does Mac OS X use in its multi–level feedback queue?
four
Name the priority bands that Mac OS X uses in its multi–level feedback queue.
"Normal, System high priority, Kernel mode only, Real–time"
Does Mac OS X manage processes with its multi–level feedback queue?
No, it manages threads.
How do Mac OS thread priorities vary?
"1) they must remain within their bands, 2) realtime threads tell the scheduler the number (A) of clock cycles they will need out of the next (B) clock cycles."
How many priority levels does a Windows scheduler have? How are they divided up?
"32, 0:15 for other threads, 16:31 for real–time threads"
Does a Windows scheduler manage threads or processes?
threads
Real time threads run at __________ between 16 and 31
fixed priorities
In what situation can real–time threads be preempted? Are there many situations?
"a higher priority process arrives. nope"
Does the base priorty of a thread change?
No
Between what values can a base priority be incremented/decremented by?
–2:2
When do thread priorities go below their base priority?
They don't.
When is a thread priority incremented?
when they return from the waiting state
When is a thread priority decremented?
When it exhausts its time.