Brainscape's Knowledge GenomeTM

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


See full index

CS340 > CPU Scheduling > Flashcards

CPU Scheduling Flashcards

1
Q

What is a burst cycle?

A

CPU does not work continuously. It computes in bursts, before waiting for a I/O burst. The distribution of these bursts, is the main concern of the OS.

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

Do most processes use short CPU bursts or longer bursts?

A

Most OS processes are interactive, therefore spend the majority of their time waiting for I/O, interleaved with short bursts of computation.

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

Which two state transition scenarios doesn’t require any decisions from the scheduler?

A

From running to wait state, and process termination.

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

What is the difference between pre-emptive and co- operating scheduling?

A

Pre-emptive is when OS interrupts process while it is running. This leads to race conditions. Co-operative scheduling means the process releases CPU when it doesn’t need it anymore.

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

Why is pre-emptive scheduling preferred?

A

CPU is most valuable resource. OS should keep control over how it used.

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

What does the dispatcher do?

A

It does a context switch. Save current process info to its PCB, and move in PCB of new process. It may have to switch hardware from user to kernel mode or vice versa. may also have to jump to the correct location in the current program instructions.

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

What is the dispatch latency?

A

The time it takes for the dispatcher to do a context switch.

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

What is the CPU utilization criteria?

A

Keep the CPU as busy as possible

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

What is throughput?

A

How many process finish execution in a given time unit

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

What is turnaround time?

A

The amount of time it takes to execute a process from creation to termination.

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

What is waiting time?

A

How long a process spends in ready queue.

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

What is response time?

A

How long it takes from request submission till first response.

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

Explain FCFS.

A

First Come First Serve. Non-preempitive. CPU is allocated to whichever process comes first, and the process is allowed to run till it terminates.

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

Advantages of FCFS?

A

Minimal context-switches (only when process is finished). scheduler doesn’t have to make any decisions so time saved.

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

Disadvantages of FCFS?

A

Convoy Effect. If computationally intensive process comes first, then all other processes has to wait till it finishes. Severely decreases response time. Affects interactivity.

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

Explain Round Robin

A

Preemptive version of FCFS. Processes are switched after time slice in the order they came in.

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

Explain Round Robin

A

Pre-emptive version of FCFS. Processes are switched after time slice in the order they came in.

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

How does time slice length affect RR.

A

Context switches are expensive. Short time slice results in more switches decreasing CPU utilisation. Longer slice increases throughput, but will get closer and closer to FCFS.

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

Disadvantages of RR

A

processes are not prioritised. Higher priority processes will have to wait for lower priority.

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

Explain SJF.

A

Shortest Job First. Most optimal algorithm, however it is impossible to calculate process CPU burst. Can be estimated based on how long it took last time, but not very accurate.

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

Is there a pre-emptive version of SJF?

A

Yes. We also need to know arrival time of processes. While a process is running, if a shorter process arrives, the running process is pre-empted, and has to wait until the shorter one finishes. It’s leftover burst time is updated.

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

Explain Priority Scheduling

A

Higher priority processes are scheduled first. Can be pre-emptive with arrival times, similar to SJF.

23
Q

What are the two types of priority allocation in the ready queue?

A

Explicit (can’t change once in ready queue) or Variable.(can be changed while running)

24
Q

What is starvation in priority scheduling?

A

If priorities cannot change, there is a possibility that lower priority processes may never execute as they are constantly pre-empted by the arrival of higher-priority processes.

25
Q

What is the solution to starvation?

A

Variable priority. Priority of processes in ready queue are increased based on how long it has been waiting.

26
Q

What is multi-level scheduling?

A

Ready queue has levels based on process types. For example, different algorithms for foreground processes (interactive) vs background processes (CPU bound).

27
Q

Parameters for establishing a multilevel scheduler.

A

Criteria for deciding which queue a process should go into

Scheduling algorithm to use for each queue

Scheduling between queues, how are the queues switched?

Number of queues?

Can a process move between queues?

28
Q

What is SMP?

A

Symmetric multiprocessing. Each CPU core has its own scheduler. Ready queue can be shared, or separate.

29
Q

Issues with shared ready queue with multicore CPU?

A

Race conditions. Queue needs to be locked while a scheduler is accessing it.

30
Q

Issues with separate ready queues in multicore CPU?

A

Load balancing. One core might have a big ready queues, while others sit idly.

31
Q

What is real-time scheduling?

A

Sometimes processes must be executed by a set time. For example in time sensitive situations like autonomous vehicles where system must react to events happening.

32
Q

What is soft real-time scheduling?

A

Critical tasks are assigned higher priority. No gurantee whether they will finish by deadline.

33
Q

What is hard real-time scheduling?

A

Tasks will finish by deadline. No exceptions.

34
Q

What is event latency?

A

Time elapsed from event occurs till it is served.

35
Q

How can event latency be split?

A

Interrupt latency - Time from event arrival till start of service routine. OS needs to figure out interrupt type.

Dispatch latency - Time for service routine to pre-empt current process.

36
Q

What is the extra component needed for make a soft real-time system into a hard real-time system?

A

Deadlines. Each CPU burst must finish before deadline.

37
Q

What is a periodic process?

A

A process that requires CPU time at constant intervals. E.g., polling, monitoring, sampling, etc.

38
Q

What is a sporadic process?

A

Event driven. E.g. fault detecting, change in environment, etc.

39
Q

What does c, p, and d stand for in real-time CPU Scheduling?

A

c = computation time for process
p = period of process
d = deadline

40
Q

Does it matter if p and d are the same?

A

No. They can be the same. p can be less than d or the same. p can change depending on system load

c <= d <= p

41
Q

How is the computation time for periodic processes known?

A

Through simulation and analysis.

42
Q

What happens if computation is finished before the next period?

A

The process is blocked till the next period.

43
Q

How does p changes for sporadic processes?

A

p is now the minimum between events

44
Q

Can p be 0?

A

Yes, these are for sporadic process that occurred at the same time.

45
Q

How does the scheduler deal with simultaneous sporadic events?

A

No right way to do it. It’s up to the OS, and it doesn’t generally matter which order they are serviced.

46
Q

What are Cyclic Executives (CE)?

A

Pre-scheduled tasks that are already programmed. E.g. wash cycle. They are highly predictable, but inflexible and difficult to maintain.

47
Q

How is major cycle time calculated for CEs?

A

LCM of process periods.

48
Q

How is frame time calculated for CEs?

A

GCD of process periods.

49
Q

What is Rate Monotonic algorithmn?

A

Fixed priority. The shortest period is given highest priority.

50
Q

What is Least Compute Time?

A

Fixed priority. The shortest computation time is given highest priority. Similar to SJF.

51
Q

What is Shortest Completion Time (SCT)?

A

Same as pre-emptive SJF. In real-time systems the computation time is known therefore this is feasible.

52
Q

What is slack time?

A

Time till deadline - computation time left.

53
Q

What is EDF?

A

Earliest deadline first. Process with closest deadline is prioritised first.

54
Q

What type of scheduling is required for real-time OS?

A

pre-emptive, priority based.

CS340 (5 decks)

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