OS Walkthrough 01— Multi-threading & CPU Scheduling

PKU’s OS on Coursera: Week 01 ~ Week 04

5 min readFeb 1, 2023

Operating Systems courses on Coursera are fewer than computer programming, data structure, and algorithm. Though taught in Chinese, Peking University’s Operating Systems renders OS basics from a bird’s eye view. After I completed this course, the following passages are the key points I noted encapsulating this OS course.

This article is about spooling, system call, interrupt & exception, process, PCB (process control block), process state diagram, process VS. thread, multithreading, CPU scheduling algorithms (FCFS, SJF, SRTN; RR, HRRN, MLFQ), batch processing / interactive processing / real-time processing, & priority inversion.

Peking University’s Operating Systems on Coursera: https://www.coursera.org/learn/os-pku

PKU’s OS on Coursera: Week 05 ~ Week 06

yc-kuo.medium.com

(1) Week 01: Introduction to OS

(2) Week 02: OS Environment

(3) Week 03: Process and Thread Models

(4) Week 04: CPU Scheduling

(5) References

(1) Week 01: Introduction to OS

Concurrency VS. Parallelism
Time-sharing OS (time slice) / real-time OS / general OS / embedded OS
Real-time OS: hard real-time VS. soft real-time
User level / kernel level / hardware level
Spooling (Simultaneous Peripheral Operation On-Line): Improving batch processing, mediating between a computer application and a slow peripheral, such as a printer. [1]

(2) Week 02: OS Environment

CPU = Arithmetic Logic Unit (ALU) + Control Unit (CU) + Register + Cache. Register and cache are often composed of SRAM.
A few significant registers: PC (Program Counter), IR (Instruction Register), and PSW (Program Status Words).
2 kinds of CPU modes: user mode & kernel mode.
Instruction: privileged instruction & non-privileged instruction.
x86 CPUs support 4 CPU privilege instructions : R0, R1, R2, R3. R0: kernel mode. R1 & R2: in between. R3: user mode. Currently, most of the OSs based on x86 CPU only use R0 & R3.

6. Interrupt & exception:

According to Computer Organization and Design (4th ed.) [8], under the MIPS convetion, we use the term “exception” to refer to “internal” unexpected change in control flow, and use “interrupt” to refer to the “external” ones.

Interrupt (external) : this happens as a result of outside interference, whether that’s from the user, from peripherals, from other hardware devices, or through a network. [2]
Exception (internal): this happens when executing a process or thread.

7. Probing into interrupt (external) & exception (internal):

Interrupt: from I/O devices and other hardware components. Async (asynchronous). Return to the next instruction.
Exception 01 — Trap: Conscious arrangement. Sync (synchronous). Return to the next instruction.
Exception 02 — Fault: Can be restored. Sync. Return to the current instruction.
Exception 03 — Abort: Can’t be restored. Sync. Do not return.

8. User mode -> kernel mode: interrupt, exception, trap (system call).

9. System call (trap): CPU switches to kernel mode from user mode.

10. OSs are interrupt-driven. (This is the Intel x86 convention [8], using interrupt to include the external and internal ones mentioned earlier on)

(3) Week 03: Process and Thread Models

1. Process: the abstraction of an execution of a program.

2. Process: resource allocation unit & CPU scheduling unit. (After the thread is introduced, the thread becomes the new CPU scheduling unit)

3. PCB (process control block): the only way an OS perceives processes. A process and its PCB are one-to-one correspondence.

4. Every process has its own independent address space.

5. Process list / PCB / FCB / MMU

6. Linux: fork() & exec()

7. Process state diagram: New/Created, Running, Ready, Blocked/Waiting, Terminated.

8. Atomic action: An indivisible sequence of primitive operations that must complete without interruption. [6]

9. Process VS. Thread:

A process may be split into several threads.
The threads in a process share the same address space and use all the resources in that process.
After introducing the thread, the resource allocation unit is still a process.
The CPU scheduling unit becomes a thread

10. Pros of multithreading:

Raise CPU utilization
When some threads have to stop and wait for the connection or take a large amount of CPU time, they can be handled in the background, so the rest of the threads can still work correctly in the foreground.

11. Cons of multithreading:

Race condition
The overhead cost of context switching
Need more memory space to store threads

12. Multi-programming / Multi-processing / Multi-threading

13. User-level thread & kernel-level thread:

User level thread: UNIX
Kernel level thread: Windows

(4) Week 04: CPU Scheduling

Scheduling algorithms / scheduler / process scheduler
I/O-bound process VS. CPU-bound process (compute-bound process)
Preemptive VS. Non-preemptive
Batch processing / interactive processing / real-time processing
Evaluating a batch processing scheduling algorithm:

CPU utilization
Throughput
Turnaround time (TAT)

6. Evaluating an interactive processing scheduling algorithm:

Response time
Proportionality

7. Evaluating a real-time processing scheduling algorithm:

Within the time limit (hard real-time VS. soft real-time)
Reliability

8. Scheduling algorithms in batch processing:

First-come, first-served (FCFS) [cf. FIFO in page replacement algorithms]
Shortest job first (SJF)
Shortest remaining time next (SRTN)

9. Scheduling algorithms in interactive processing:

Round-robin (RR): Quantum (time slice) (20 ms ~ 50 ms, or 10 ms ~ 100 ms). Cost of process switching & context switching.
Priority scheduling
Highest response ratio next (HRRN)
Multi-level feedback queue (MLFQ) [may cause hungry]
Aging

10. Scheduling algorithms in real-time processing:

Separating scheduling mechanism & scheduling policy.