CPU Virtualizing: Processes & Scheduling

Question 1

What happens when you run a program?

Answer 1

Loads from disk to memory
The CPU, using its instruction Set Architecture (ISA), sequentially:
Fetches an instruction from memory.
Decodes to identify the specific command.
Executes the identified operation(e.g, adding numbers, memory access, function jumps.)
Move to next instruction
The cycle repeats billions of times every second until the program finishes
Despite this simple model, many other complex processes occur during a program’s execution.

Question 2

Explain short: What is the goal of process abstraction?

Answer 2

The goal of process abstraction is to run multiple processes concurrently, by time sharing the cpu. We then need mechanisms (context switch) and policy(scheduler). This makes the illuision that each program has it’s own isolated machine.

Question 3

What is virtualization of the CPU?

Answer 3

It involves a single cpu acting as if it were multiple seperate CPUs- Enables users to run many concurrent programs

Question 4

Which states can a process be? Explain them.

Answer 4

Running: The process is actively executing instruction on a processor.

Ready: The process is prepared to run but isn’t currently chosen by the OS to execute.

Blocked: The process is waiting for an event before it can proceed. For instance, a process become blocked when initiating an I/O request to a disk or network, allowing another process to use the processor in the meantime

Running to Ready: The OS interrupts the running process and puts it back in the queue to wait its turn.
Running to Blocked: The process initiates I/O, like reading from a disk, and can't run until the I/O is done.
Ready to Running: The OS decides it's this process's turn to run.
Blocked to Ready: The I/O operation that was blocking the process is now finished.

Question 5

What does fork() do? What does exec() do What does wait() do?

Answer 5

The fork() function creates a new process, which is an exact copy of the calling process. It’s like having two identical versions of the original process, both seemingly continuing from where fork() was called

The wait() system call allows the parent process to pause and wait until its child process finishes. Once the child completes, the parents resume, and wait() provides the child’s PID as its return value. This will always make the child go first.

Exec()
Loads the code and static data from the file.
Overwrites current code segment and static data of the process.
Re-initializes the heap and stack to match the new program’s requirements.

Question 6

What different modes can an OS run an executable from?

Answer 6

User and kernel mode

Question 7

What is kernel mode?

Answer 7

In Kernel mode:

The OS can run system calls.
The OS doesn't trust the user's stack or provided addresses.
The OS has full access to the hardware, like using any CPU instruction and accessing any memory.
Kernel mode is for the most trusted and low-level OS functions.
Crashes in kernel mode can stop the whole computer.

Question 8

What are the two types of scheduler?

Answer 8

Preemptive and non preemptive

Question 9

What is a context switch?

Answer 9

For example when a process switches from user to kernel mode. It then saves context (PC, registers, kernel stack, pointer) of process on kernel stack

Question 10

What is SJF (shortest-job-first)?

Answer 10

It runs the shortest job available, not preemptive

Question 11

What is FIFO (first-in first-out)?

Answer 11

It runs the process with the shortest arrival time

Question 12

What is RR (round-robin), and how does it work?

Answer 12

A scheduling algorithm.| It runs each process on a given time quatum. This could be 2ms.

Question 13

Why do we want to have a scheduler?

Answer 13

Maximize CPU usage.
Minimize turnaround time (arrival to completion).
Minimize response time (arrival to first scheduling).
Ensure fairness for all processes.
Minimize overhead by running processes long enough to cover context switch costs (e.g., 1 microsecond).

Question 14

What is stride scheduling?

Answer 14

Each process is assigned a ticket value.
We calculate a “stride” for each process using a fixed number (e.g., 1000 or 10000).
A “pass” value is increased by the stride value for each process.
The operating system selects the process with the lowest pass value to run.
If multiple processes have the same pass value, the one with the lowest stride value runs first.
If both pass and stride values are identical, the process that entered the scheduling queue first gets to run first.

Question 15

What is the formula for turnaround time? What is turnaround time?

Answer 15

Tturnaround = Tcompletion - Tarrival

Scheduler performance is measured using turnaround time, which is the duration from a process entering the queue to its completion. Interestingly, better turnaround times can sometimes mean less fairness in scheduling.

Question 16

What is the formula for response time?

Answer 16

Tresponse = Tfirstrun - Tarrival

Question 17

Why is it difficult to create a good scheduler?

Answer 17

Turnaround time and response time:| Both are bad where the other is good

Question 18

What is multi-level feedback queue(MLFQ)?

Answer 18

The scheduler has different priority levels for processes, and it uses a round-robin approach within each priority level. It starts with the highest-priority process and moves down if not done. If two processes have the same priority, they take turns in a round-robin fashion.

Question 19

What are some of the problems with multi-level feedback queue(MLFQ)?

Answer 19

Starvation: If there are to many interactive jobs they will combine to consume a lot cpu time, preventing long running jobs from getting any cpu time, so they starve.

Question 20

What can we done in MLFQ to prevent starvation?

Answer 20

Periodically boost the priority level of all jobs. For a given time slice we can move all jobs to the highest priority queue.

Question 21

What is lottery scheduling?

Answer 21

Each process gets different amount of tickets and an OS chooses a ticket. The process that has that ticket can run for a given time.

Question 22

How do we calculate fairness in a scheduler?

Answer 22

U = tCompletionA / tCompletionB (1 = perfect)

Question 23

What is the difference between lottery scheduler and stride scheduler?

Answer 23

Stride scheduler is deterministic

Question 24

What are the advantages and disadvantages of using randomness in a scheduler?

Answer 24

Negative:

Unpredictable: Lottery scheduling can't guarantee exact proportions, leading to uncertain outcomes.

Positive:

Fairness: It promotes fairness.
Lightweight for the OS.
Avoids corner cases.

Question 25

How does the OS schedule threads?

Answer 25

OS schedules threads that are ready to run independently, much like processes

Question 26

When and what , trap function

Answer 26

A trap function, also known as a system call:

Used by a program when it requires privileged access or services provided by the operating system.
Necessary when the program intends to perform tasks like file operations, I/O, process control, and more.
Specifies the specific action or service the program is requesting from the operating system.
    For instance, opening a file, allocating memory, creating a new process, or executing network operations.
Essentially allows a program to seek the operating system's assistance for tasks beyond its direct capabilities.
Encompasses both the timing of the request (when) and the nature of the requested operation (what).