Lecture Notes: Operating Systems

COMP3033 Operating Systems

Dr. Sunny Seon Phil JEONG

---

Chapter 2: Operating-System Structures

1. Operating System Services

Operating systems provide services to users and programs, categorized as:

• User Services:

  • User Interface (UI): CLI (Command-Line Interface), GUI (Graphical User Interface), Touchscreen, batch processing (批处理)
  • Program Execution
    • Load a program into memory
    • Run a program, and then end execution.
  • I/O Operations: Read/write files, input/output handling
  • File-System Manipulation: Create, delete, read/write files
  • Communications: Process communication & networking
  • Error Detection: Handling software/hardware errors

• System Efficiency Services:

  • Resource Allocation: CPU, memory, I/O management
  • Logging: Tracking user resource usage
  • Protection & Security:
    • Protection: Ensure that all access to system resources is controlled
    • Security: Avoid attack from outside the system

---

2. Operating System Interface

• CLI
  • CLI (Command Line Interface) or command interpreter allows direct command entry
  • Commands are
    • sometimes implemented in kernel
      • commands built-in
    • sometimes by systems program
      • names of programs
      • +Advantage: adding new features doesn’t require modification of interpreter
  • Shell (vs. Kernel)
    • Multiple flavors of interpreters implemented
• GUI
  • User-friendly

---

3. System Calls， API，C Libraries

• System Calls: Interface for processes to request OS services.
  • Examples: read(), write(), fork(), exec() on Unix/Linux
• API (Application Programming Interface):
  • specifies a set of functions that are available to an application programmer.
  • Three most common APIs (libraries):
    • Win32 API (Windows)
    • POSIX API (Linux, UNIX, macOS)
      • Portable Operating System Interface
    • Java API (JVM-based applications)

API and System Call

• 调用者只需遵循 API
  • 无需了解系统调用的实现方式
  • 大多数操作系统接口细节都通过 API 隐藏在程序员面前
• The system call interface invokes the intended system call in OS kernel and returns status of the system call and any return values
• Each system call has a number (as index)
• System-call interface maintains a table: indexed according to these numbers

System Call Parameter Passing Methods:

• Registers: Fastest, but limited number.
  • 将参数直接存放在 CPU 寄存器中，传递给系统调用。
  • 优点：
    • 传输速度快，因为寄存器在 CPU 中。
  • 缺点：
    • 寄存器数量有限，无法传递大量数据。
    • 不适用于传递结构体或数组等复杂数据。
• Memory Table: Stores parameters in memory and passes address.
  • 将参数保存在内存中的某个位置，并传递该内存地址给系统调用。
  • 优点：
    • 适合传递大量数据，如结构体、数组等。
  • 缺点：
    • 需要额外的内存管理。
    • 可能涉及内存拷贝，增加开销。
• Stack: Push/pop parameters from the stack.
  • 方式：参数通过 stack 进行传递，调用函数时将参数压入栈中。
  • 优点：
    • 易于实现，符合函数调用约定。
    • 支持变长参数。
  • 缺点：
    • 栈传递的效率不如寄存器传递。
    • 如果参数数量过多，可能导致栈溢出。

Standard C Library vs System Call

• Advantages of using Standard C Library
  • It is simpler to call a function in a standard C library rather than to make a system call
  • Portability
• Advantages of using system calls
  • more powerful
  • a little bit faster

Standard C Library vs C POSIX Library: subset ⊏ superset

---

• Programs
  • kernel
  • system program
  • application program
• How can apps be used in multi-operating systems？
  • interpreted language, like Python, Ruby, and interpreter available on multiple operating systems
  • Written in a language that includes a VM containing the running app (like Java)
  • Written in a standard language (like C), compiled separately on each operating system to run on each OS
  • Application Binary Interface (ABI)
    • about how different components of binary code can interface for a given operating system on a given architecture in low-level details
      二进制代码的不同组件如何在低级细节中与给定体系结构上的给定操作系统进行交互

---

4. Operating System Structure

4.1 OS Architectures

1. Monolithic（庞大而单一）- Traditional UNIX
   • The traditional UNIX OS follows a monolithic kernel structure.
   • Single large kernel handling everything. 一个单一的大型进程 ，管理大多数操作系统服务，包括文件系统、CPU 调度和内存管理。
   • Fast but complex.
   • The UNIX OS consists of two separable parts
     • Systems programs
     • The kernel
2. Monolithic Plus Modular - Linux System Structure
   • Advantages for monolithic design
     • High speed
     • High efficiency
   • Advantages for modular design
     • changes in one component affect only that component, and no others
     • Modules can be modified easily.
3. Layered Approach
   • Divides OS into hierarchical layers.
   • Easy to manage but slower.
   • Advantage
     • Simplicity of construction and debugging.
   • Disadvantages
     • Hard to define each layer.
     • Poor performance.
4. Microkernel (e.g., Mach)
   • e.g., Mach – Mac OS X kernel (Darwin) partly based on Mach
   • Moves as much components from the kernel into user space
   • More secure but has communication overhead.
5. Modules
   • loadable kernel modules (best practice)
   • Uses object-oriented approach
6. Hybrid Systems
   • Combines different architectures (e.g., Windows, macOS).

---

Chapter 3: Process

1. Process Concept

Process

• a program in execution in memory
• execution must progress in sequential fashion

Process 组成

• the program code (also called text section)
• stack (函数调用参数、返回地址、局部变量)
• data section (全局变量、静态变量)
• heap (动态分配的内存 malloc / new)
• program counter, processor registers (include all current data of the program inside the CPU)

Process State

• New: The process is being created
• Running: Instructions are being executed by CPU
• Waiting: The process is waiting for some event to occur
• Ready: The process is waiting to be assigned to a processor
• Terminated: The process has finished execution
  

---

2. Process Scheduling

Process Control Block (PCB) (also called task control block)

• 操作系统管理进程的关键数据结构
• A PCB is a kernel data structure
  • invisble to Process itself, changed only by the kernel
• Each process has a corresponding unique PCB in the kernel.
• 包含
  • Process state – running, waiting, etc.
  • Program counter (PC) – location of instruction to next execute
  • CPU registers – contents of all process-centric registers
  • CPU scheduling information - 调度信息（优先级、队列信息）
  • Memory-management information – 内存管理信息（地址空间）
  • Accounting information – CPU used, clock time elapsed since start, time limits
  • I/O status information – I/O devices allocated to process, list of open files

Process Scheduling

• Process scheduler (kernal 里的 algorithm)
  • Maintains scheduling queues of processes
  • Ready queue: 等待 CPU 执行的进程。
  • Wait queues: 等待 I/O 事件的进程。
  • 上下文切换 Context Switch:
    • 当 CPU 切换进程时，需要保存和恢复 PCB。
    • 上下文切换是额外开销，依赖硬件支持。

---

3. Operations on Processes

Process Creation

• 父进程（Parent Process） 通过 fork() 创建子进程（Child Process）
• 父子进程资源共享方式：
  • 完全共享（共享所有资源）
  • 部分共享（共享部分资源）
  • 完全独立（无资源共享）
• 进程执行方式：
  • 并行执行（父子进程同时运行）
  • 顺序执行（父进程等待子进程完成）

Process Termination

• 进程调用 exit() 终止自身。
• 父进程调用 wait() 终止子进程。
• 父进程可以使用 abort() 终止子进程（如子进程占用过多资源）。
• 孤儿进程（Orphan Process）：父进程终止，但子进程仍在运行。
• 僵尸进程（Zombie Process）：
  • 子进程已终止，但 PCB 仍保留，等待父进程读取状态。
  • Reaping (回收)

---

4. Inter-process Communication (IPC)

• Advantages/Reasons of process cooperation
  • Information sharing
  • Computation speed-up
  • Modularity
  • Convenience
• Disadvantages
  • Added complexity
  • Deadlocks (死锁) possible
  • Starvation (饥饿) possible

IPC 方式	说明
共享内存（Shared Memory）	进程直接共享内存，需要同步控制
消息传递（Message Passing）	通过 send() 和 receive() 传递消息

---

Shared Memory

Major issues: Synchronization (同步) (Discussed in Chapters 6 & 7)

• Producer-Consumer Problem: Paradigm (范例) for cooperating processes
  • 无界缓冲区（Unbounded Buffer）：无限存储，不会阻塞生产者。
  • 有界缓冲区（Bounded Buffer）：存储大小固定，生产者可能阻塞。

---

Message Passing

1. 直接通信（Direct Communication）
进程必须显式指定对方：

send(P, message);
receive(Q, message);

2. 间接通信（Indirect Communication）
通过 邮箱（Mailbox） 进行消息交换：

send(mailbox, message);
receive(mailbox, message);

Message passing may be either blocking (synchronous) or non-blocking (asynchronous)

方式	发送者	接收者
同步（阻塞）	等待接收方处理	等待消息
异步（非阻塞）	立即返回	立即返回

If both send and receive are blocking, this case is called rendezvous （会合）

---

Pipe

• 匿名管道（Ordinary Pipes）：unidirectional 单向，Require parent-child relationship 父子进程通信。
• 命名管道（Named Pipes）：bidirectional 双向，无需父子关系。

匿名管道示例:

int fd[2];
pipe(fd);
pid_t pid = fork();

if (pid == 0) {  // 子进程
    close(fd[1]);
    read(fd[0], buffer, sizeof(buffer));
} else {  // 父进程
    close(fd[0]);
    write(fd[1], "Hello", 5);
}

---

5. Communication in Client-Server Systems

本节介绍 Sockets 和 RPC，他们都属于 IPC 中的 Message Passing

Sockets

• 用于网络通信（Client-Server）。
• 套接字 = IP 地址 + 端口号。

服务器端

ServerSocket server = new ServerSocket(6013);
Socket client = server.accept();
PrintWriter out = new PrintWriter(client.getOutputStream(), true);
out.println("Hello Client!");

客户端

Socket socket = new Socket("127.0.0.1", 6013);
BufferedReader in = new BufferedReader(new InputStreamReader(socket.getInputStream()));
System.out.println(in.readLine());

---

Remote Procedure Calls

• 封装进程间通信，使其看起来像本地函数调用。
• 基于底层消息传递（通常使用 Socket 进行通信）：
  • 客户端调用 RPC，将请求参数封装成消息，发送给远程服务器。
  • 服务器解包消息，执行相应函数，将结果打包返回。
• 数据传输
  • 序列化/反序列化（Marshalling & Unmarshalling）：将数据转换为可传输的格式（如 JSON、XML）。
  • 使用 TCP 或 UDP 进行底层传输。
• Example

  • // 客户端调用 RPC 函数
    result = rpc_call("add", 5, 10);  // 实际上底层是 send()/recv()
    

---

Chapter 4: Threads & Concurrency

1. Process vs. Thread

• What is thread?
  • A thread is a single sequence stream within a process.

对比项	进程（Process）	线程（Thread）
创建开销	高（需要分配独立资源）	低（共享进程资源）
内存空间	每个进程有独立的地址空间	同一进程内多个线程共享地址空间
调度与管理	由操作系统负责	由操作系统或用户负责
资源共享	不共享资源	共享进程内的资源
上下文切换	较慢	快

---

2. Concurrency vs. Parallelism

• Concurrency is a property of a program where two or more tasks can be in progress simultaneously.
  • 并发是指多个任务的进展，这些任务并不一定同时执行，通常在单核系统中，通过时间片轮转来模拟同时执行。
• Parallelism is a run-time property where two or more tasks are being executed simultaneously.
  • 并行是指多个任务同时执行，通常需要多核处理器支持，每个核心执行一个任务。
  • 并行是并发的一种实现方式，并行意味着并发，但并发不一定意味着并行。

多核编程（Multicore Programming）

• 多核编程挑战：任务划分、负载均衡、数据拆分、数据依赖、调试困难等。
• 并行性（Parallelism）：多个任务同时执行，需要多个处理器或核心支持。
• 并发性（Concurrency）：多个任务的进度同时进行，单处理器通过上下文切换提供并发。

数据并行（Data Parallelism）：

• 数据的子集分布在多个核心上，执行相同的操作。
  • 示例：图像处理时，每个核心处理图像的一部分。

任务并行（Task Parallelism）：

• 将不同任务分配给不同的核心，执行不同的操作。
  • 示例：声音处理时，任务分配到不同的核心处理不同的音频处理（滤波、回声等）。

---

3. Thread Libraries

• Thread Libraries 线程库为程序员提供了创建与管理线程的 API。
  • POSIX Pthreads：最常用的线程库，支持用户级和内核级线程。
  • Windows threads：Windows 操作系统的线程库。
  • Java threads：Java 提供的线程模型。

---

4. Implicit Threading

---

5. Threading Issues

---

Chapter 5: CPU Scheduling

1. Basic Concepts

• Purpose of multiprogramming: maximum CPU utilization
• CPU–I/O Burst Cycle
  • 进程的执行周期通常包括 CPU 执行和 I/O 等待，每个进程在 CPU 执行和 I/O 等待之间交替进行。

CPU Scheduler

• CPU Scheduler 负责从 ready queue 中选择一个进程，并将 CPU 分配给该进程。
• 调度决策发生的时机：
  • 进程从 running 转换到 waiting（non-preemptive 自愿离开CPU 非抢占性调度）。
  • 进程从 running 转换到 ready（preemptive 抢占性调度）。
  • 进程从 waiting 转换到 ready (preemptive)。
  • 进程 terminates（non-preemptive 非抢占性调度）。

抢占式与非抢占式调度

• 抢占式调度（Preemptive）：
  • CPU 可以被其他进程抢占。
  • 提高响应时间，适用于交互式环境。
  • 可能引发 race conditions 数据竞争问题（需要线程同步）。
• 非抢占式调度（Non-preemptive）：
  • 进程执行完成或者主动放弃 CPU。
  • 没有数据竞争问题，但可能导致低优先级进程长时间得不到 CPU。

---

2. Scheduling Criteria

• CPU utilization：尽量让 CPU 始终处于忙碌状态。
• Throughput 吞吐量：每单位时间完成的进程数。
• Response time 响应时间：从提交请求到第一次响应的时间（适用于时间共享系统）。
• Waiting time 等待时间：进程在就绪队列中等待的总时间。
• Turnaround time 周转时间：从进程开始到结束所经历的总时间（包括等待时间和执行时间）。
  • Turnaround time = Waiting time + time for all CPU bursts

---

3. Scheduling Algorithms

1. First-Come, First-Served (FCFS)

• 原理：按进程到达的顺序分配 CPU。
• 缺点：可能导致 长进程 阻塞 短进程，产生 Convey effect 护送效应。

2. Shortest-Job-First (SJF)

• 原理：选择 预计 CPU 时间最短 的进程执行。
• 优点：最小化平均等待时间。
• 缺点：难以预测下一次 CPU 时间，且可能导致 饥饿现象。
• Determining Length of Next CPU Burst
  • 通过 过去的 CPU 运行时间 来预测 下一个运行时间，即：
  • $\tau_{n+1} = \alpha t_n + (1 - \alpha) \tau_n$
  • $\tau_n$ 是第 n 次的预测 CPU 运行时间
  • $t_n$ 是实际的第 n 次 CPU 运行时间
  • $\alpha$ 是平滑因子，通常设置为 0.5

3. Priority Scheduling (PS)

• 原理：根据进程的优先级分配 CPU，优先级高的进程优先执行。
  • A priority number (integer) may be associated with each process
  • The CPU is allocated to the process with the highest priority (smallest integer = highest priority)
• 缺点：低优先级进程可能永远得不到执行（Starvation）。
• 解决方法：Aging 老化，逐步提高低优先级进程的优先级。
• SJF is priority scheduling where priority is the inverse of predicted next CPU burst time

4. Round-Robin (RR)

• 原理：
  • Each process gets a small unit of CPU time (time quantum 定额 q), usually 10-100 milliseconds.
  • After q has elapsed, the process is preempted by a clock interrupt and added to the end of the ready queue.
• 优点：适用于 时间共享系统，响应较快。
• 缺点：时间片过小导致频繁 context switch，过大则退化为 FCFS。

5. Multilevel Queue Scheduling (MQS)

• 原理：将进程分为多个队列，每个队列采用不同的调度算法。
  • foreground 前台队列（交互式进程）：使用 RR 算法。
  • background 后台队列（批处理进程）：使用 FCFS 算法。
• 缺点：可能导致 低优先级队列的进程饥饿。

6. Multilevel Feedback Queue Scheduling (MFQS)

• 原理：进程可以在不同队列间移动，避免饥饿现象。
  • 新进程先进入最高优先级队列。
  • 时间片未完成的进程被移至较低优先级队列。(aging, prevent starvation)
• 优点：灵活，适应性强。
• the most general CPU scheduling algorithm

---

4. Thread Scheduling

线程调度模型

• 用户级线程（User-Level Threads）：

  • 线程管理由 thread library 完成，不依赖 kernal。
  • 适用于不支持线程管理的操作系统。
  • process-contention scope (PCS)
  • 优点：不需要系统调用，线程创建和切换速度快。
  • 缺点：无法利用多核系统，线程竞争和调度需要用户自己处理。

• 内核级线程（Kernel-Level Threads）：

  • 由 kernal 管理。
  • system-contention scope (SCS)
  • 每个线程由操作系统调度，支持多核并行。
  • 优点：能够利用多核架构，操作系统能自动调度线程。
  • 缺点：每个线程管理都需要进行系统调用，开销较大。

• 多对一、多对多模型（Many-to-One, Many-to-Many）：

  • 多对一（Many-to-One）：多个用户级线程映射到一个内核线程上。
  • 多对多（Many-to-Many）：多个用户级线程映射到多个内核线程上。
  • 一对一（One-to-One）：每个用户级线程都有一个对应的内核线程，常见于 Windows 和 Linux。

---

5. Multi-Processor Scheduling

• 多处理器调度更加复杂，尤其在 Symmetric multiprocessing (SMP) 对称多处理 系统中，每个处理器都有自己的 就绪队列 和 线程调度。

SMP（对称多处理） 调度策略：

1. 共同就绪队列（Common Ready Queue）：

   • 所有线程都在一个共享的就绪队列中，操作系统负责选择哪个线程分配到哪个 CPU 上。
   • 优点：所有线程共享一个队列，避免了资源的浪费。

2. 私有就绪队列（Private Ready Queue）：

   • 每个处理器有自己的私有队列，操作系统通过调度算法在不同的队列之间分配任务。
   • 优点：避免了调度时的冲突，提高了效率。

负载均衡（Load Balancing）：

• 推迁移（Push Migration）：检查各处理器的负载，将任务从负载过重的处理器迁移到空闲的处理器。
• 拉迁移（Pull Migration）：空闲的处理器主动拉取等待队列中的任务。

---

6. Real-Time CPU Scheduling

实时系统调度：

• 软实时系统（Soft Real-Time Systems）：高优先级的实时任务优先执行，但不能保证任务会被准时执行。(best try only)
• 硬实时系统（Hard Real-Time Systems）：任务必须在规定的时间内完成，否则会导致系统错误。

实时调度标准：

1. Event Latency 响应时间：从事件发生到处理完成所经历的时间。
2. 调度延迟：
   • Interrupt latency 中断延迟：从中断到 interrupt service routine (ISR) 开始执行的时间。
   • Dispatch Latency 调度延迟：从当前进程被挂起到新的进程开始执行的时间。

实时调度算法：

• 速率单调调度（Rate-Monotonic Scheduling, RMS）：任务的优先级与其周期的倒数成正比，周期越短优先级越高。
• 最早截止时间调度（Earliest Deadline First, EDF）：优先级与任务的截止时间成正比，截止时间越早优先级越高。

---

7. Operating Systems Examples

---

Midterm Hints

Section A

1. ch1, p13 Interrupt-Driven
2. ch1, p26 Caching
3. ch1, p31 Dual-mode (user & kernal)
4. ch2, p34 Monolithic - Traditional UNIX
5. ch3, p14 Context Switch
6. ch3, p59 Named pipes
7. ch5, p12, p14 SJF, Determining Length of Next CPU Burst
8. ch5, p26, p28 MQS, MFQS
9. ch3, p9 Process Control Block
10. ch3, p21, p22 Process Creation

Section B

1. ch2
2. ch3, p34-37 Zombie and Orphan Process
3. ch3, p39 IPC Models(Shared memory & Message Passing)
4. ch4, p11-12 Data and Task Parallelism
5. ch2, p20 Syscall 传参

Section C

1. ch5, p10-20 Scheduling Algorithms(FCFS, SJF, RR)
2. ch3, p22-30 fork()
3. ch4, p26-30 pthreads.h

---