Brainscape's Knowledge GenomeTM

Browse over 1 million classes created by top students, professors, publishers, and experts.


See full index

CS6200 - Final Review > P3L1 - Scheduling > Flashcards

P3L1 - Scheduling Flashcards

1
Q

What is the role of the CPU Scheduler?

A

To decide how and when the processes (and their threads) access the shared CPUs

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
2
Q

T/F: Scheduler concerns itself with both user level tasks and kernel level tasks

A

True!

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
3
Q

When do you need to run the scheduler?

A

Whenever the CPU becomes idle

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
4
Q

What is a common amount of time given to a task?

A

Timeslice

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
5
Q

What are the steps that occur when the scheduler selects a task to be scheduled?

A
  1. Switch to new task
  2. Enter user mode
  3. Set program counter
  4. Execution begins!
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
6
Q

What is the structure of the ready queue known as?

A

runqueue

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
7
Q

_____ scheduling assumes that once a task is assigned to a CPU, it will run on that CPU until its finished

A

Run to Completion

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
8
Q

What are some common metrics for comparing schedulers?

A
  1. Throughput
  2. Average job completion time
  3. Average job wait time
  4. CPU utilization
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
9
Q

_____ algorithm has tasks scheduled in the order in which they arrive?

A

First come First serve (FCFS)

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
10
Q

What is an alternative to using execution time when choosing tasks to schedule?

A

Priority levels

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
11
Q

When scheduling based on priority levels, which task should run first?

A

The task with the highest priority level

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
12
Q

What is an effective way to be able to quickly tell a task’s priority

A

Maintain a separate runqueue for each priority level

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
13
Q

What is one dangerous situation that can occur with priority scheduling?

A

Starvation

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
14
Q

What is starvation in the context of scheduling?

A

When low priority tasks are essentially never scheduled because higher priority tasks continually enter the system and take precedence

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
15
Q

What is one mechanism to protect against starvation?

A

Priority aging - The priority of a task is not just the numerical property but a function of the actual priority and the amount of time the task has spent in the runqueue

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
16
Q

What is priority inversion?

A

When the highest priority task that SHOULD run cannot run because the lowest priority task is holding a mutex it needs

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
17
Q

What is one way to combat priority inversion?

A

Temporarily boost the priority of the mutex owner long enough to allow it to complete

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
18
Q

Define a timeslice?

A

The maximum amount of uninterrupted time that can be given to a task

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
19
Q

T/F: A task may run for a smaller amount of time than what the timeslice specifies?

A

True!

20
Q

What is one use of timeslices?

A

To allow tasks to be interleaved

21
Q

What are the downsides of timeslicing?

A

The overhead - We have to interrupt the running task, execute the scheduler ,and have to context switch to the new task

22
Q

How long should a timeslice be?

A

CPU intensive tasks –> Prefer longer timeslice values

I/O intensive tasks –> Prefer shorter timeslice values

23
Q

T/F: A runqueue data structure is only LOGICALLY a queue?

A

True! It can be implemented as multiple queues or even a tree

24
Q

____ is a structure that maintains multiple distinct queues, each differentiated by their timeslice values

A

Multi queue

25
Q

T/F: The topmost level of a multi queue has the larger timeslice value!

A

False! It holds the lowest

26
Q

How did the Linux O(1) Scheduler get its name?

A

It can add/select tasks in constant time regardless of the number of tasks in the system

27
Q

How many priority levels does the Linux O(1) scheduler have?

A

140 priority levels

28
Q

What are levels 0-99 used for in the Linux O(1) scheduler?

A

real time tasks

29
Q

What are levels 100-139 used for in the Linux O(1) scheduler?

A

timesharing tasks

30
Q

What is the feedback for the Linux O(1) scheduler?

A

How long a task spent sleeping during its timeslice

31
Q

How is the runqueue implemented for the Linux O(1) scheduler?

A

As two arrays - active and expired

32
Q

Which of the two arrays of the Linux O( 1) schedulers runqueue is used for selecting the next task to run?

A

Active

33
Q

What are some downsides of the Linux O(1) scheduler?

A
  1. A task cannot run again until everything in the active array is complete
  2. It makes no fairness guarantees
34
Q

What scheduler replaced the Linux O(1) scheduler?

A

The CFS (Completely Fair Scheduler)

35
Q

What type of data structure is used for the runquee for the CFS?

A

A red-black (self balancing) tree

36
Q

How are tasks ordered in the runqueue for CFS?

A

Based on amount of time that they spent running on the CPU - vruntime

37
Q

How long does selection take for CFS?

A

Constant time

38
Q

How long does addition take for CFS?

A

Log(# of tasks)

39
Q

Describe a shared memory multiprocessor

A

Multiple CPUs each with their own private L1/L2 cache, as well as a LLC which may or may not be shared. Lastly there is a DRAM shared across CPU’s

40
Q

Describe a multicore system

A

Each CPU can have multiple internal cores each with its own private L1/L2 cache, a shared LLC and DRAM

41
Q

T/F: It makes sense to schedule tasks on CPUs close to memory holding their state?

A

True! Keeps the cache hot

42
Q

What is the scheduling type known as in which we keep tasks on the CPU closest to the memory node where their state is?

A

NUMA-aware scheduling

43
Q

What is hyperthreading?

A

CPU support for multiple execution contexts (2)

44
Q

How do we know if a thread is CPU bound or memory bound?

A

Use historic information like hardware counters that are updated as the processor executes and keep information about various aspects of execution

45
Q

Is CPI a good metric for informing scheduling decisions?

A

No, its more or less the same across applications

CS6200 - Final Review (10 decks)

Brainscape helps you reach your goals faster, through stronger study habits.
© 2024 Bold Learning Solutions. Terms and Conditions