## Chapter 1: Introduction to Operating System ### Basic Knowledge 1. **（背）Computer System Architecture** - **I/O Devices**: I/O devices can work concurrently (同时) with the CPU. **The device controller is responsible for a specific device type and has a local buffer.** Data is transferred between the device and the **local buffer of the controller.** - I/O 的定义：**Betwen device and buffer of controller** 一定要区分不是 Devices and Memory - 为什么要用 Buffer: Balance the speed difference between device and CPU (Usually CPU is much faster than device) - **CPU and Memory**: Concepts of single - processor, dual - core processor, and the term Non - Uniform Memory Access system (NUMA). - Single/Multiple Processor: **Each Processor has its own cache. All processors share main memory.** - Dual-core Processor: **Each core has its own cache (L1). All cores share L2 cache.** - NUMA: 每个 CPU 有自己的 Memory 块，CPU 之间也可以通过 interconnect 访问别的 CPU 的内存（但是慢） [](https://imgse.com/i/pE0thtO) 2. **（背）Definition of Operating System** - The operating system is an intermediate **program** between users and computer hardware. - Components: **Kernel (resident in memory)**, system programs, application programs, middleware. 3. （看即可）Goals of Operating System - Personal Computers: Emphasize convenience, ease of use, and good performance. - Shared Computers (such as mainframes or minicomputers): Satisfy all users, efficiently utilize hardware, and manage user programs. - Mobile Devices (such as smartphones and tablets): Optimize usability and battery life, and provide user interfaces such as touchscreens and voice recognition. - Embedded Computers: Run programs. 4. **（背）Operations of Operating System** - **Management Work Content**: Caching, process management, memory management, file management, secondary storage management, I/O, protection, and security. 5. **（背）Interrupt Mechanism** - **Interrupt Definition**: A signal sent by **hardware or software** that requires immediate processing. Software interrupts (traps or exceptions) are triggered by errors or user requests (system calls), and hardware interrupts are generated by devices. - **Interrupt Handling Steps**: 1. Save the CPU state (store registers and the program counter PC) 2. Determine the interrupt type through the interrupt vector to obtain the corresponding ISR address 3. Run the ISR to handle the interrupt. - **DMA (Direct Memory Access)**: **The device controller can directly transfer data blocks from the buffer to the main memory without CPU intervention.** Only one interrupt is generated for each data block, and the transfer speed is fast. [](https://imgse.com/i/pE0t4hD) 6. （看即可）Process - related - **Difference between Program and Process**: **A program is a passive entity in storage, and a process is an active entity in memory.** The creation and execution of a process require resources such as CPU, memory, I/O, files, and initialization data. When a process ends, reusable resources need to be reclaimed. A process can be single - threaded or multi - threaded, and the program counter specifies the position of the next instruction. - **Multiprogramming and Multitasking**: Multiprogramming means that some jobs are stored in memory simultaneously, and job scheduling selects and loads jobs. Multitasking means that the CPU switches jobs frequently, and CPU scheduling determines the next running job. - **Process Execution Modes**: User mode and kernel mode. The dual - mode can protect the operating system and other system components. System calls are used to request operating system services. - **Process Management Activities**: Create and delete user and system processes, suspend and resume processes, process synchronization, process communication, deadlock handling. 7. Memory Management - To execute a program, part or all of the program instructions and data need to be placed in memory. - Memory Management Activities: Track memory usage, decide the loading and unloading of processes and data, and allocate and release memory space as needed. 8. File System Management - The operating system provides a unified logical view, abstracting physical attributes into files. Files are usually organized into directories. - File System Activities: Create and delete files and directories, and map files to secondary storage. 9. Secondary Storage Management - Disks are used to store data that is not suitable for the main memory or needs to be stored for a long time. - Management Activities: Mounting and unmounting, free space management, storage allocation, disk scheduling, partitioning, protection. 10. I/O Sub - system - Hide the characteristics of hardware devices. - Responsible for the memory management of I/O (buffering, caching, spooling), and provide a general device driver interface and specific hardware device drivers. 11. Protection and Security - Protection: A mechanism to control the access of processes or users to resources defined by the operating system. - Security: Defend the system against internal and external attacks, and distinguish users and determine permissions through user IDs and group IDs. 12. Virtualization - Virtualization abstracts the hardware of a single computer into multiple execution environments, which is achieved through virtual machines (such as VirtualBox, VMware). - Virtual Machine Managers (VMMs) run directly and provide services and resource management for virtual machine processes. 13. Free and Open - source Operating Systems - Provided in the form of source code, such as GNU/Linux, BSD UNIX, etc. - Free software (a social movement) and open - source (a development technique) overlap in most cases but have differences. 14. **Data Structures**: Kernel data structures include singly linked lists, doubly linked lists, circular linked lists, binary search trees, hash tables, bitmaps, etc. ### Knowledge Graph ``` |--Computer System Architecture | |--I/O Devices | | |--Concurrent work with CPU | | |--Device Controller | | | |--Responsible for specific device type | | | |--Has local buffer | |--CPU and Memory | | |--Single - processor | | |--Multi - processor (such as dual - core) | | |--Non - Uniform Memory Access system (NUMA) |--Operating System | |--Definition | | |--Intermediate program between users and hardware | | |--Composition: Kernel, system programs, application programs, middleware | |--Goals | | |--Personal Computers: Convenience, ease of use, good performance | | |--Shared Computers: User satisfaction, efficient hardware utilization, program management | | |--Mobile Devices: Optimize usability and battery life | | |--Embedded Computers: Run programs | |--Operations | | |--Caching | | |--Process Management | | | |--Difference between program and process | | | |--Multiprogramming and multitasking | | | |--Process execution modes (user/kernel mode) | | | |--Process management activities | | |--Memory Management | | | |--Relationship between program execution and memory | | | |--Memory management activities | | |--File System Management | | | |--Unified logical view and file directories | | | |--File system activities | | |--Secondary Storage Management | | | |--Disk usage | | | |--Management activities | | |--I/O Sub - system | | | |--Hide hardware characteristics | | | |--I/O memory management and drivers | | |--Protection and Security | | | |--Protection: Control resource access | | | |--Security: Defend against internal and external attacks and user differentiation |--Virtualization | |--Concept: Abstract hardware into multiple execution environments | |--Implementation: Virtual machines (such as VirtualBox, VMware) | |--Virtual Machine Managers (VMMs) |--Free and Open - source Operating Systems | |--Provided in the form of source code | |--Difference between free software and open - source |--Kernel Data Structures | |--Singly linked lists, doubly linked lists, circular linked lists | |--Binary search trees | |--Hash tables, bitmaps ``` ## Chapter 2: Operating-System Structures ### Basic Knowledge #### (I) Operating System Services 1. Service Categories - User - Oriented - **User Interface**: Command - Line Interface (CLI), Graphical User Interface (GUI), Touchscreen, Batch Processing. - **Program Execution**: Load programs into memory, run and terminate programs. - **I/O Operations**: Perform input and output operations on devices. - **File System Operations**: Read, write, create, delete files, etc. - **Communication**: Exchange information between processes. - **Error Detection**: Handle potential hardware or software errors. - Efficient - Operation - Oriented - **Resource Allocation**: Allocate resources such as CPU, main memory, file storage, I/O devices to multiple users or jobs. - **Logging**: Track the usage of computer resources by users. - **Protection and Security**: Protection ensures controlled access to system resources; security prevents the system from external attacks. 2. **Abstract View**: The operating system provides basic computing resources and controls and coordinates the use of hardware among various applications and users. #### (II) Operating System Interfaces 1. User - Operating System Interface - **CLI**: Command - Line Interface. Commands are sometimes implemented in the kernel (built - in commands) and sometimes by system programs. Different types of shells such as Bourne Shell (sh), GNU Bourne - Again Shell (bash), C Shell (csh), Korn Shell (ksh), Z Shell (zsh). - **GUI**: Graphical User Interface. It is user - friendly, based on the desktop metaphor, and uses icons to represent files, programs, etc. The combination of CLI and GUI in different operating systems (e.g., Windows is mainly GUI - based with the CLI "cmd" shell; Mac OS X has the "Aqua" GUI interface and a UNIX kernel and shell; Unix and Linux are mainly CLI - based with an optional GUI). The new interface features of touchscreen devices (gesture - based operations, virtual keyboard input, voice commands). 2. **System Calls**: Provide a programming interface for programs to use operating system services. Parameter passing methods (register passing, memory block table passing, stack passing). Types of system calls (process control, file management, device management, information maintenance, communication, protection). 3. **API (Application Programming Interface)**: Application developers design programs based on the API. Common APIs include Win32 API (for Windows), POSIX API (for POSIX - based systems, including most UNIX, Linux, Mac OS X versions), Java API (for Java Virtual Machine). **The API hides the details of the operating system interface.** 4. **Standard C Library and System Calls**: Standard C library functions may call system calls. Using the standard C library is **simpler and more portable** , but system calls are more powerful and faster. #### (III) Operating System Structures 1. **History of Operating System Implementation**: In the early days, assembly language was used. Later, system programming languages (such as Algol, PL/1) were used. Now, C and C++ are mostly used, usually a combination of multiple languages, with assembly for the底层 and C for the main body. 2. Types of Operating System Structures | OS Structure Type | Key Features | | --------------------------------------- | ------------------------------------------------------------ | | Simple Structure | - Unorganized implementation <br> - Direct hardware interaction <br> - Basic system services | | Monolithic Structure (Traditional UNIX) | - Composed of system programs and a large, non - layered kernel <br> - All kernel functions at the same level <br> - High efficiency due to direct interactions | | Layered Structure | - Divided into multiple layers <br> - Each layer uses services of the lower layer <br> - Clear structure for building and debugging | | Microkernel | - Minimal core functions in the kernel (e.g., process & memory management, communication) <br> - Other functions as user - space servers <br> - Communication via message passing | | Module Structure | - Core components are independent modules <br> - Modules can be loaded and unloaded as needed <br> - Object - oriented approach for interaction | | Hybrid Structure | - Combines features of multiple structures <br> - Balances performance, scalability, reliability, and security | 1. Examples - **macOS and iOS**: Based on the Mac OS X structure, with Cocoa and Cocoa Touch frameworks, providing graphics and media support. It contains the Mach microkernel and the BSD UNIX kernel. Darwin provides two system call interfaces (Mach system calls and BSD system calls). - **Android**: Based on the Linux kernel but with modifications. It is open - source and developed for smartphones and tablets. The runtime environment includes core libraries and the Dalvik Virtual Machine (gradually replaced by the ART VM). Applications are developed using Java and the Android API. #### (IV) Operating System Booting 1. **Boot Process**: After the system is powered on, **the code at a fixed memory location is executed**. Through the bootstrap loader, the kernel can be loaded into memory and started in one step (the bootstrap loader in ROM or EEPROM locates and loads the kernel) or two steps (the ROM code (BIOS) first loads the boot block on the hard disk, and then the bootstrap loader in the boot block loads the kernel). After that, system daemons are started. ### Knowledge Graph ``` Operating System Structure |--Operating System Services | |--User - Oriented | | |--User Interface (CLI, GUI, Touchscreen, Batch Processing) | | |--Program Execution (Load, Run, Terminate Programs) | | |--I/O Operations | | |--File System Operations | | |--Communication | | |--Error Detection | |--Efficient - Operation - Oriented | |--Resource Allocation (CPU, Memory, etc.) | |--Logging | |--Protection and Security (Protection, Security) |--Operating System Interfaces | |--User - Operating System Interface | | |--CLI (Command Implementation Methods, Different Shell Types) | | |--GUI (Features, Combinations in Different Systems, Touchscreen Interface Features) | |--System Calls | | |--Definition and Function | | |--Parameter Passing Methods (Register, Memory Block Table, Stack) | | |--System Call Types (Process Control, File Management, etc.) | |--API | | |--Definition and Function | | |--Common APIs (Win32, POSIX, Java) | |--Standard C Library and System Calls | |--Features of Standard C Library (Simple, Portable) | |--Features of System Calls (Powerful, Fast) |--Operating System Structures | |--History of Operating System Implementation (Early Assembly, Later System Programming Languages, Current C/C++ and Hybrid Situations) | |--Types of Operating System Structures | | |--Simple Structure (e.g., MS - DOS) | | |--Monolithic Structure (Composition and Features of Traditional UNIX) | | |--Layered Structure (Layered Approach, Advantages and Disadvantages) | | |--Microkernel (Principle, Advantages, Disadvantages) | | |--Modules (Implementation Method, Features) | | |--Hybrid Systems (Hybrid Situations of Common Operating Systems) | |--Examples | |--macOS and iOS (Based on Structure, Frameworks, Kernels, System Call Interfaces) | |--Android (Based on Kernel, Runtime Environment, Application Development Methods) |--Operating System Booting | |--Boot Process (One - step or Two - step Kernel Loading, Starting Daemons) ``` ## Chapter 3: Processes ### Basic Knowledge #### Process Definition - A process is an instance of a program in execution. It includes the program code, its data, the CPU state (registers), and the process control block (PCB). For example, when you run a text - editing program, each instance of that program running is a process. #### Process Control Block (PCB) - The PCB contains all the information about a process. It includes process - specific identification (PID), CPU - related information (such as the program counter, register values), memory - related information (e.g., memory allocation details), and I/O - related information (e.g., open file descriptors). It serves as a handle for the operating system to manage and control the process. #### Process States ##### Basic States - **New**: The process is being created. For instance, when you double - click an application icon, the system starts the process creation, and it enters the new state. - **Ready**: The process is waiting to be assigned to a CPU. It has all the necessary resources except the CPU. Multiple ready processes form the ready queue. - **Running**: The process is currently executing on the CPU. Only one process can be running on a single - core CPU at a time. - **Blocked (Waiting)**: The process is waiting for an event to occur, such as an I/O operation to complete, a resource to become available, or a signal. For example, if a process is waiting for data to be read from a disk, it enters the blocked state. - **Terminated**: The process has finished execution and its resources are being reclaimed by the operating system. [](https://imgse.com/i/pE0BN28) #### Process Scheduling ##### Scheduling Queues - **Ready Queue**: Holds all the processes that are ready to execute and waiting for the CPU. - **Device Queues**: Each I/O device has a device queue. Processes that are waiting for a particular I/O device to become available are placed in the corresponding device queue. ##### Context Switch - **Save the state** of the old process (the one is running on CPU) and - **Load the saved state** (CPU registers, program counter in PCB) for the new process (the one will run on CPU) via a context switch (i.e., switch PCB) Context switch time is: - **Overhead (额外开销)**, , the system does no useful work while switching - **dependent on the complexity of OS**. The more complex the OS and the PCB，the longer time the context switch - **also dependent on hardware support** #### Process Operations ##### Process Creation - A parent process can create a child process. In Unix - like systems, the `fork()` system call is used to create a new process. The child process is a copy of the parent process in terms of the address space (initially), but they can diverge in their execution paths. ##### Process Termination - A process can terminate voluntarily, for example, when it has completed its task or encountered an error condition that it cannot handle. In Unix, the `exit()` system call is used for this purpose. A process can also be terminated involuntarily by the operating system. #### Inter - Process Communication (IPC) ##### Shared Memory - Processes communicate through a shared memory - User processes control - Requires careful synchronization to avoid data races. - Producer-Consumer Problem (用来描述 sychronous problem) - Producer process wait while buffer is full (If it is unbounded buffer, no need to wait) - Consumer process wailt while buffer is null - Two types of buffer zone: unbounded no practical limit on the size of the buffer / bounded buffer: 循环队列 ##### Message Passing - Kernel Control - Processes communicate by sending and receiving messages. - Implementation of communication link - Physical Link Level: Shared memory/Hardware bus/network - Logical level: **Direct(process to process) or indirect(mail box)/Synchronous(blocking) or asynchronous(non-blocking)/Automatic or explicit buffering** - Direct Communication - Processes must name each other explicitly. - Send()andreceive() primitives (原语) are defined as - `send(P, message)` –send a message to process P - `receive(Q, message)` –receive a message from process Q - Properties of communication link - Links are established **automatically** - A link is associated with exactly one pair of communicating processes - Between each pair there exists exactly one link - The link may be unidirectional, but is usually **bi-directional** - Inderict Communication - Messages are directed and received from mailboxes (also referred to as ports(端口)) - Each mailbox has a unique id - Processes can communicate only if they share a mailbox - The send() and receive() primitives are defined as - send(*A, message*) –send a message to mailbox A - receive(*A, message*) –receive a message from mailbox A - Operations - Create a new mailbox - Message passing by mailbox - Destroy Mailbox - Properties - Link established only if processes share one mailbox - Link may be associated with multiple processes - **Each pair of processes may share many links** - Link can be undirectional or bi-directional - Message Passing: Synchronization - **Two statuses: Blocking / Non-Blocking** - Blocking (Sychronous) - **Blocking send: Sender is blocked until the message is received by the receiving process or mailbox** - **Blocking receive: Receiver is blocked until there is a message available ** - Non-Blocking (Asychronous) - Non-blocking send--the sender sends the message and continues without waiting for the message to be received - Non-blocking receive--the receiver receives: A valid message / NULL - Different combinationspossible - If both send and receive are blocking, this case is called rendezvous（会合） - Message Buffering: Queue of message attached to the link, in the **kernel memory** - Zero capacity –no messages are queued on a link.Sender must wait for receiver (rendezvous) - Bounded capacity –finite length of *n*messagesSender must wait if link full - Unbounded capacity –infinite length Sender never waits - 不是很重要的东西：IPC System Example - **以消息传递为中心**：Windows系统通过高级本地过程调用（ALPC）工具实现以消息传递为中心的进程间通信，且仅在同一系统的进程间生效。 - 通信步骤 - 客户端打开子系统连接端口对象的句柄。 - 客户端发送连接请求。 - 服务器创建两个私有通信端口，并将其中一个的句柄返回给客户端。 - 客户端和服务器使用相应的端口句柄发送消息、回调以及监听回复。 - 消息传递方式 - **小消息（不超过256字节）**：使用端口的消息队列作为中间存储，消息从一个进程复制到另一个进程。 - **大消息**：需通过一个与通道相关联的共享内存区域（段对象）传递。 - **超大消息**：当数据量太大无法放入段对象时，服务器进程可使用API直接读写客户端的地址空间。 - **ALPC的可见性**：ALPC工具并非Windows API的一部分，因此应用程序员无法直接看到。 #### Pipes - Two types - Ordinary pipe (anonymous pipe): 除了创建这个 pipe 的进程以外都不可见。Typically, a parentprocess creates a pipe and uses it to communicate with a childprocess that it created. (Not all) - Named pipes –can be accessed without a parent-child relationship. - Ordinary pipes [](https://imgse.com/i/pE0RwsP) - Named pipes - Named Pipes are more powerful than ordinary pipes - Communication is bidirectional - No parent-child relationship is necessary between the communicating processes - Several (>=2) processes can use the named pipe for communication - Provided on both UNIX and Windows systems ### Socket - endpoint for communication - a data structure inside the kernel that represents the local end of a network connection - IP + Port ## Chapter 4: Threads ### Definition [](https://imgse.com/i/pE0jA6f) #### Threads - A thread is a basic unit of *CPU* utilization; it comprises a thread ID, a program counter (**PC**), a register set, and a stack - Most modern applications are multi-threaded - Kernel is multi-threaded #### Pros and Cons of threads ##### Pros - Economy - Creating process: heavy-weight - Creating threads: light-weight - Resource sharing - Threads share the memory and resources of process to which they belong by default - Responsiveness - may allow continued execution if part of process is blocked, especially important for user interfaces - Efficiency - Scalability ##### Cons - More difficult to program with threads (a single process can now do multiple things at the same time). - New categories of bug are possible (synchronizationis then required between threads: Chapter 6). #### Compare with processes | Similiarities | Differences | | ------------------------------------------------------------ | ------------------------------------------------------------ | | Threads share CPU and only one thread active (running) at a time. | A thread is a component of a process | | Threads within a processes execute sequentially. | Multiple threads can exist within one process. | | Thread can create children. | Multiple threads execute concurrentlyand share resources such as memory, while different processes do not share these resources. | | If one thread is blocked, another thread can run. | | ### Multicore Programming #### Programming Challenge - Identifying Tasks: Find areas of an application that can be divided into separate and concurrent tasks. - Balance: Ensure tasks perform equal work of equal value. - Data splitting: Similar to dividing tasks. - Data dependency - Test and debug **Parallelism: A system can perform more than one task simultaneously （并行）** **Concurrency: Single processor / core, CPU scheduler providing concurrency by doing context switches; More than one task are progressing** Notice the difference between concurrency and parallelism: **Parallelismimplies concurrency, but concurrencydoes not imply parallelism.** [](https://imgse.com/i/pE0jDc6) #### Types of Parallelism - **Data parallelism** focuses on distributing subsets of the same dataacross multiple computing cores and performing the same operation on eachcore. - **Task parallelism** involves distributing not data but tasks (threads) acrossmultiple computing cores. Each thread is performing a unique operation. #### Amdahl’s Law [](https://imgse.com/i/pE0j5gP) 1. **公式**： $$ Speedup \leq \frac{1}{S + \frac{1 - S}{N}} $$ 其中： - $ Speedup $ 表示加速比，即优化或并行化后系统性能与优化或并行化前系统性能的比值。例如，如果优化前运行一个程序需要100秒，优化后需要20秒，那么加速比就是 $ \frac{100}{20} = 5 $ 倍。 - $ S $ 是程序中串行部分所占的比例，取值范围是 $ 0 \leq S \leq 1 $ 。例如，如果一个程序有20%的部分必须串行执行，那么 $ S = 0.2 $ 。 - $ N $ 是处理器核心的数量。比如，从单核心升级到4核心处理器，这里 $ N = 4 $ 。 2. **推导过程**： 假设在单核心处理器上运行程序的总时间为 $ R_1 $ ，程序由串行部分和并行部分组成，串行部分时间占比为 $ S $ ，并行部分时间占比为 $ P $ ，且 $ S + P = 1 $ ，那么 $ R_1 = S + P = 1 $ （这里将单核心运行时间归一化设为1）。 当使用 $ N $ 个核心运行程序时，串行部分时间不变仍为 $ S $ ，而并行部分由于可以并行执行，其时间变为 $ \frac{P}{N} $ ，所以在 $ N $ 个核心上运行的总时间 $ R_N \geq S + \frac{P}{N} = S + \frac{1 - S}{N} $ （这里用 “ $ \geq $ ” 而不是 “ $ = $ ” ，是因为线程之间额外的通信开销）。 因此，加速比 $ Speedup = \frac{R_1}{R_N} \leq \frac{1}{S + \frac{1 - S}{N}} $ 。 3. **实际应用案例**： 课件中给出了一个例子，如果应用程序75%是并行的（即 $ P = 0.75 $ ），25%是串行的（即 $ S = 0.25 $ ），从1个核心增加到2个核心时： 首先计算在2核心上运行的时间 $ R_2 = 0.25 + \frac{0.75}{2} = 0.25 + 0.375 = 0.625 $ 。 然后得出最大加速比 $ Speedup = \frac{1}{0.625} = 1.6 $ 倍。这意味着增加一个核心后，理论上程序最多能快1.6倍。 4. **局限性与意义**： - **局限性**：随着 $ N $ 趋近于无穷，最大加速比趋近于 $ \frac{1}{S} $ 。这表明程序的串行部分对增加核心所获得的性能提升有着不成比例的影响。也就是说，如果串行部分占比很大，即使不断增加核心数量，性能提升也会非常有限。例如，若 $ S = 0.5 $ ，那么无论增加多少核心，加速比最大也只能达到2倍。此外，阿姆达尔定律没有充分考虑当代多核系统中的一些复杂因素，如线程间通信开销、缓存一致性等问题在实际情况中对性能的影响可能更为复杂。 - **意义**：它提醒开发者，在进行并行化优化时，要特别关注程序中的串行部分，因为这往往是性能提升的瓶颈。如果串行部分占比过高，单纯增加核心数量并不能显著提高性能，可能需要重新设计算法或架构，减少串行部分的比例，才能更有效地利用多核处理器的优势。 #### Gustafson’s Law 1. $$ \text{speed}_{\text{up}} = S + P \times N = N + (1 - N) \times S $$ 2. It is based on the assumption of a fixed problem size = an execution workload that does not change with respect to the improvement of the resources #### User Threads and Kernel Threads - User threads: management (thread creation, thread scheduling, etc.) done by user-level threads library. - Kernel threads: management (thread creation, thread scheduling, etc.) supported by the kernel | Type | Advantages | Disadvantages | | -------------- | ------------------------------------------------------------ | ------------------------------------------------------------ | | User Threads | **1.** No need for operating system support, can run on old or simple operating systems **2.** No need for system calls, only library function calls are required, which is fast | **1.** The number of threads in a process does not affect the CPU time it gets, that is, a single - threaded process and a multi - threaded process get the same amount of time 2. Thread scheduling within a process needs to be completed at the user level, which is complex for programming, and threads need to cooperate with each other | | Kernel Threads | 1. The kernel knows the number of threads in a process and can allocate more CPU time to multi - threaded processes **2.** Thread scheduling is automatically completed by the kernel, no need for cooperation between threads, and user programs are easy to write | **1.** Every thread management operation requires a system call, which is slow **2. T**he kernel's process control block (PCB) data structure is more complex, and it needs to track both the process and the threads within the process | Ultimately, a relationship must exist between user threads and kernel ##### Many-to-One Model  - Many user-level threads mapped to single kernel thread. - One thread blocking (waiting for something) causes all threads to block (because their common kernel thread is blocked). - Multiple threads may not run in parallel on multicore system because only one may be in kernel at a time. - Few systems currently use this model - Examples: GNU Portable Threads / Solaris Green Threads ##### One-to-One Model [](https://imgse.com/i/pE0vXZD) - One user-level threads mapped to one kernel thread - One thread blocking **does not** cause all threads to block (Only its corresponding kernel thread blocked) - Allow multiple threads to run parallel on multiprocessors. - **Drawback: Number of threads per process sometimes restricted due to overhead.** ##### Many-to-Many Model  - Allows many user level threads to be mapped to many kernel threads. - Allows the operating system to create a sufficient number of kernel threads. - **Drawbacks: Hard to be implemented -> Few systems apply Many-to-Many model** #### `pthreads` Programming POSIX Pthreads是一个用于线程创建和同步的POSIX标准（IEEE 1003.1c）API，在UNIX操作系统（如Linux和Mac OS X）中较为常见，可在用户空间或内核级实现。以下重点介绍 `pthread_attr_init`、`pthread_create` 和 `pthread_join` 的用法： 1. **`pthread_attr_init` 函数** - **功能**：初始化一个线程属性对象 `pthread_attr_t`。通过该函数，可以获取线程属性的默认值，之后可以根据需求对这些属性进行修改，如设置线程的栈大小、调度策略等。 - **用法示例**： ```c pthread_attr_t attr; pthread_attr_init(&attr); ``` **说明**：在使用线程属性之前，必须先调用 `pthread_attr_init` 进行初始化。该函数的参数是一个指向 `pthread_attr_t` 类型变量的指针。 2. **`pthread_create` 函数** - **功能**：创建一个新的线程。新线程从指定的函数开始执行。 - **函数原型**： ```c int pthread_create(pthread_t *thread, const pthread_attr_t *attr, void *(*start_routine) (void *), void *arg); ``` - **参数说明**： - `thread`：指向 `pthread_t` 类型变量的指针，用于存储新创建线程的标识符。 - `attr`：指向线程属性对象 `pthread_attr_t` 的指针。如果为 `NULL`，则使用默认的线程属性。 - `start_routine`：新线程开始执行的函数指针。该函数接受一个 `void *` 类型的参数，并返回一个 `void *` 类型的值。 - `arg`：传递给 `start_routine` 函数的参数。 - **用法示例**： ```c pthread_t tid; pthread_attr_t attr; pthread_attr_init(&attr); pthread_create(&tid, &attr, runner, argv[1]); ``` - **说明**：在上述示例中，`runner` 是新线程要执行的函数，`argv[1]` 是传递给 `runner` 函数的参数。 3. **`pthread_join` 函数** - **功能**：等待指定的线程结束。调用该函数的线程会被阻塞，直到指定的线程执行完毕。通过这种方式，可以确保主线程在子线程完成任务后再继续执行，避免出现数据竞争或逻辑错误。 - **函数原型**： ```c int pthread_join(pthread_t thread, void **retval); ``` - **参数说明**： - `thread`：要等待的线程的标识符。 - `retval`：指向 `void *` 类型指针的指针。如果不为 `NULL`，则 `pthread_join` 会将被等待线程的返回值（即 `start_routine` 函数的返回值）存储在 `*retval` 中。 - **用法示例**： ```c pthread_t tid; // 创建线程 pthread_create(&tid, NULL, runner, argv[1]); // 等待线程结束 pthread_join(tid, NULL); ``` - **说明**：在上述示例中，主线程调用 `pthread_join` 等待 `tid` 标识的线程结束。`NULL` 参数表示不获取被等待线程的返回值。 综合示例： ```c #include <pthread.h> #include <stdio.h> #include <stdlib.h> int sum; void *runner(void *param); int main(int argc, char *argv[]) { pthread_t tid; pthread_attr_t attr; if (argc != 2) { fprintf(stderr, "usage: thrd-posix <integer value>\n"); return -1; } if (atoi(argv[1]) < 0) { fprintf(stderr, "Argument %d must be non - negative\n", atoi(argv[1])); return -1; } pthread_attr_init(&attr); pthread_create(&tid, &attr, runner, argv[1]); pthread_join(tid, NULL); printf("sum = %d\n", sum); } void *runner(void *param) { int i, upper = atoi(param); sum = 0; if (upper > 0) { for (i = 1; i <= upper; i++) sum += i; } pthread_exit(0); } ``` 在这个示例中，主线程创建了一个新线程，新线程执行 `runner` 函数进行求和计算，主线程通过 `pthread_join` 等待新线程完成计算后，输出求和结果。 比较： | `pthread_exit()` | `return (void*)(intptr_t)0` | | ------------------------------------------------------------ | ------------------------------------------------------------ | | `pthread_exit` 是Pthreads库提供的函数，用于显式地终止调用它的线程 。 | `return` 是C语言的关键字，用于从函数中返回。在线程执行函数中使用 `return`，意味着函数执行结束，线程也随之结束，因为线程的执行逻辑就在这个函数中。 | | `pthread_exit` 的参数是一个 `void*` 类型的值，这个值可以被 `pthread_join` 函数获取，用于传递线程的执行结果等信息。在实际使用中，传递的可能是一个指向结构体的指针，结构体中包含各种线程执行相关的数据；或者像示例中传递一个简单的整数值（通过 `(void*)(intptr_t)` 进行类型转换）。 | 在线程执行函数中使用 `return` 返回值时，该返回值同样会被 `pthread_join` 获取。返回值的类型也需要转换为 `void*` 类型。 | ### Implicit Threading Motivation: - Growing in popularity as numbers of threads increase, program correctness more difficult with explicit threads - Creation and management of threads done by compilers and run-time libraries rather than programmers Methods: - Thread Pools - Fork-join - OpenMP #### Thread Pools - Create a number of threads in advance in a pool where they await work (预先创建一组线程置于池中等待任务) Advantages: - Usually slightly faster to service a request with an existing thread than create a new thread - Allows the number of threads in the application(s) to be bound to the size of the pool - Separating task to be performed from mechanics of creating task allows different strategies for running task - 如定期调度任务 #### Fork-Join - 多个线程（任务）先被创建（fork），执行完毕后再合并（join）。类似于分治 [](https://imgse.com/i/pEBC6z9) ```java Task(problem) if problem is small enough solve the problem directly else subtask1 = fork(new Task(subset of problem) subtask2 = fork(new Task(subset of problem) result1 = join(subtask1) result2 = join(subtask2) return combined results ``` #### Openmp - Set of compiler directives and an API for C, C++, FORTRAN - | Comparison Item | Define local variables in each `thread` function | Use thread - local storage (`thread_local`) | | --------------------------------- | ------------------------------------------------------------ | ------------------------------------------------------------ | | Data Independence | Variables are independent each time the function is called, but with a short lifespan when the function is called multiple times, making it difficult to maintain the state throughout the thread's lifecycle | Each thread has an independent copy, which persists throughout the thread's lifecycle and is initialized only once | | Sharing within a Thread | The scope of function - local variables is only within the function, making it difficult to share among different functions within the thread | It can be easily shared among different functions within the thread while maintaining data isolation between threads | | Memory Management and Performance | When the function is called frequently, variables are created and destroyed frequently, increasing overhead | Memory is allocated when the thread starts and released when it ends, suitable for resources that are used for a long time within the thread's lifecycle | #### Thread Cancellation - Definition: Terminating a thread before it has finished - Two general approaches: - **Asynchronous cancellation** terminates the target thread immediately - **Deferred cancellation** allows the target thread to periodically check if it should be cancelled ## Chapter 5: CPU Scheduling ### Basic Concepts - Purpose of multiprogramming: maximum CPU utilization - CPU–I/O Burst Cycle (一个 CPU Burst 接一个 I/O Burst) - Process execution consists of a cycleof CPU execution and I/O wait - CPU burst followed by I/O burst - **Process State Transitions**: A process transitions between different states during execution （五个状态 new-ready-running-waiting-terminated) ### CPU Scheduler - The CPU scheduler (CPU 调度程序) selects a process from the processes in ready queue, and allocates the CPU to it. - CPU scheduling decisions may take place when a process - **From Running to Waiting (Non - preemptive)**: When a process makes an I/O system call, it voluntarily relinquishes the CPU and enters the waiting state. For example, when reading a file, the process waits for the disk I/O operation to complete. - **From Running to Ready (Preemptive)**: When a clock interrupt occurs, the currently running process is suspended and returns to the ready queue, waiting to be scheduled again. This ensures that multiple processes can share the CPU time fairly. - **From Waiting to Ready (Preemptive)**: When the I/O operation is completed, such as the hard - disk controller sending an interrupt signal indicating that the data has been read, the waiting process enters the ready queue, waiting for CPU allocation. - **Termination (Non - preemptive)**: The process finishes execution, automatically ends, and releases CPU resources. - Preemptive and Non - preemptive Scheduling - **Non - preemptive Scheduling**: It is determined by the process itself. The scheduling process is relatively simple, but it may cause important processes to be blocked by unimportant processes for a long time. - **Preemptive Scheduling**: Scheduling occurs in addition to the non - preemptive situations mentioned above. It is determined by the hardware and the kernel. It can improve the response time and create an interactive environment, but it may lead to race conditions, especially when multiple processes share data. In addition, issues such as shared - data access, CPU preemption in kernel mode, and how to handle interrupts during key operating - system activities need to be considered. ### Scheduling Criteria 废话一堆感觉没什么看的 - **CPU Utilization**: Keep the CPU as busy as possible, that is, maximize CPU utilization to fully utilize the hardware resources. - **Throughput**: The number of processes that complete execution per unit time. The goal is to increase throughput as much as possible so that the system can handle more tasks. - **Response Time**: The time from the submission of a request to the generation of the first response. It is mainly for time - sharing environments and measures the system's response speed to user requests. - **Waiting Time**: The total time a process waits in the ready queue. The waiting time should be minimized to improve the process execution efficiency. - **Turnaround Time**: The total time required to execute a specific process, including waiting time and all CPU burst times, that is, **turnaround time = waiting time + all CPU burst times**. Similarly, it is desired to minimize the turnaround time. ### Scheduling Algorithms #### Metrics to evaluate - Average waiting time: 进程在就绪队列中等待的总时间 $$ \text{waiting time} = \text{turnaround time} - \text{burst time} $$ - Average turnaround time：执行特定进程的总时间（从开始到结束，包括等待时间），计算方式为等待时间加上所有CPU突发时间，追求最小化 $$ \text{turnaround time} = \text{complete time} - \text{arrival time} $$ #### 做题流程 - 画 Gantt 图 - 维护 ready queue #### First-Come, First-Served (FCFS) Scheduling - FCFS调度算法按照进程到达就绪队列的先后顺序来调度进程，先到达的进程先获得CPU资源并执行，直到该进程完成任务或者主动让出CPU。 - **工作原理**：当一个进程进入就绪队列，它会按照到达顺序排在队列末尾。CPU调度程序总是从就绪队列的头部选择进程，将CPU分配给排在最前面的进程，该进程开始执行，直到运行结束、进行I/O操作（此时进入等待状态）或者因为其他原因主动放弃CPU，调度程序才会选择队列中的下一个进程。 例子：假设进程P1、P2、P3在时间t = 0时按顺序到达就绪队列，它们的突发时间（burst time，即进程需要占用CPU的时间）分别为：P1（24）、P2（3）、P3（3）。其甘特图（Gantt Chart）如下： | P1 | P2 | P3 | | ---- | ----- | ----- | | 0-24 | 24-27 | 27-30 | - Average waiting time: $\frac{0 + 24 + 27}{3} = 17$ - Average turnaround tume: $\frac{24 + 27 + 30}{3} = 27$ 潜在的问题： - **平均等待时间和周转时间可能较长**：当有长进程先到达时，后面的短进程需要等待很长时间，导致整体平均等待时间和周转时间变长，如第一个示例中的情况。 - **Convoy effect(护送效应)** -short process behind long proce - 如果有一个CPU密集型（CPU突发时间长、I/O突发时间短）的长进程先到达，后续跟着多个I/O密集型（I/O突发时间长、CPU突发时间短）的短进程，这些短进程会因为长进程占用CPU而长时间等待，就像护航队一样，降低了CPU和设备的利用率 。 #### Shortest-Job-First (SJF) Scheduling - SJF调度算法根据进程下一个CPU突发（CPU burst）的长度来安排调度，优先选择下一个CPU突发时间最短的进程执行，直到该进程完成或因其他原因（如I/O操作）暂停，然后再从就绪队列中选择下一个CPU突发时间最短的进程。 - 工作原理 - 系统为每个进程记录其下一个CPU突发的预计长度。 - 当CPU空闲时，调度程序遍历就绪队列，挑选出下一个CPU突发时间最短的进程，将CPU分配给它。 - 被选中的进程开始执行，直至完成任务、主动让出CPU（如进行I/O操作）或被抢占（在抢占式SJF中）。 - **应对**：通常通过预测来估计下一个CPU突发长度。一种常用方法是利用进程过去的CPU突发历史数据，采用指数平均法进行预测。 - 公式为 $\tau_{n+1} = \alpha t_{n} + (1 - \alpha)\tau_{n}$，其中 $\tau_{n+1}$ 是下一个CPU突发的预测值，$t_{n}$ 是上一个CPU突发的实际长度，$\tau_{n}$ 是上一次的预测值，$\alpha$ 是一个介于0和1之间的参数（通常设为0.5）。 - 当 $\alpha = 0$ 时，预测值始终等于初始值，不考虑历史实际数据； - 当 $\alpha = 1$ 时，预测值仅取决于上一个实际的CPU突发长度。一般情况下，公式展开后，越近期的实际数据权重越大。 - 实际上做题的时候 Burst time 会给定。系统情况是对每一个在 ready queue 里的 process 做一次预测，算出一个新的 burst time. 假设一组进程的到达时间和突发时间如下：（非抢占版） | 进程 | 到达时间 | 突发时间 | | ---- | -------- | -------- | | P1 | 0.0 | 6 | | P2 | 2.0 | 8 | | P3 | 4.0 | 7 | | P4 | 5.0 | 3 | 其调度甘特图如下： | P1 | P4 | P3 | P2 | | ----- | ----- | ------ | ------- | | 0 - 6 | 6 - 9 | 9 - 16 | 16 - 24 | 平均等待时间计算： - P1等待时间为 $0$。 - P2等待时间为P1、P4、P3的执行时间减去其到达时间，即 $(6 + 3 + 7) - 2 = 14$。 - P3等待时间为P1和P4的执行时间减去其到达时间，即 $(6 + 3) - 4 = 5$。 - P4等待时间为P1的执行时间减去其到达时间，即 $6 - 5 = 1$。 - 平均等待时间 = $(0 + 14 + 5 + 1) / 4 = 5$。 平均周转时间计算： - P1周转时间为 $6$。 - P2周转时间为 $24 - 2 = 22$。 - P3周转时间为$16 - 4 = 12$。 - P4周转时间为 $9 - 5 = 4$ 。 - 平均周转时间 = $(6 + 22 + 12 + 4) / 4 = 11$。 如果是抢占版（The preemptive version of SJFis also called shortest-remaining-time-first），就要每一个时刻检查 ready queue，把里面每一个process的burst time减去已经执行的部分的time，排序。取最小的执行。 **如果是 pre-emptive version**，注意公式： $$ \text{waiting time} = \text{turnaround time} - \text{burst time} $$ > 解释：在抢占式调度中，一个进程可能会多次被抢占，其执行过程被分割成多个片段。但无论进程执行过程如何被打断，周转时间始终是从进程到达系统到完成的总时长，突发时间是进程实际占用CPU运行的累计时长。因此，从周转时间中减去进程实际占用CPU运行的突发时间，剩下的就是进程在就绪队列中等待CPU的时间，即等待时间。 #### Round Robin - Each process gets a small unit of CPU time (timequantum 定额*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. - Timer interrupts every quantum *q* to schedule next process - 每个进程被分配一个小的CPU时间单元，即时间片（time quantum，通常用q表示 ），一般为10 - 100毫秒。当时间片q过去后，进程会被时钟中断抢占，并被添加到就绪队列的末尾。接着，调度器从就绪队列头部选取下一个进程执行，同样分配一个时间片，如此循环。例如，假设有进程P1、P2、P3在就绪队列中，时间片q = 4毫秒，P1先执行4毫秒后被抢占移到队列末尾，接着P2执行4毫秒，然后P3执行4毫秒，之后又轮到P1执行4毫秒，以此类推。 - Performance - $q$ too large $\rightarrow$ FCFS - $q$ too small $\rightarrow$ too much time is spent on context switch - $q$ should be large compared to context switch time - $q$ usually 10ms to 100ms, context switch < 10 usec(微秒) **做题：把 arrival time = 0 计算即可** - 优势 - **公平性**：RR算法确保了每个进程都能在一定时间间隔内获得CPU时间，避免了某些进程长时间得不到执行的情况，体现了公平调度的原则。 - **响应性**：由于进程能够频繁地获得CPU时间片并执行，所以对于交互式系统来说，它能快速响应用户的请求，提升用户体验。 - **不足**：与SJF等一些优化平均等待时间或周转时间的算法相比，RR算法因为频繁的 Context switch 以及可能导致进程不能一次性完成其CPU突发任务，所以平均周转时间通常会较高。例如在处理一些长CPU突发时间的进程时，进程会被多次中断，导致整体完成时间变长，从而增加了周转时间 #### Priority Scheduling - 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) - Two policies - Preemptive: the current process is pre-empted immediately by high priority process - Non-preemptive: the current process finishes its burst first, then scheduler chooses the process with highest priority - 最短作业优先（SJF）算法实际上是优先级调度的一种特殊情况，其中优先级是根据预测的下一个CPU突发时间的倒数来确定的。即预测的CPU突发时间越短，优先级越高。这样可以使得短作业优先得到处理，从而减少平均等待时间。 - 存在的问题：Starvation:low priority processes may never execute - 低优先级的进程可能会因为不断有高优先级进程进入系统而长时间得不到执行机会 - 解决方案：Aging: as time progresses increase the priority of the process - 随着时间的推移，逐渐提高低优先级进程的优先级，使得即使最初优先级较低的进程，在等待足够长的时间后，也能获得较高的优先级，从而有机会执行。例如，每经过一定时间间隔，就将低优先级进程的优先级数值减小（在规定的优先级表示方式下，数值减小意味着优先级提高）。 **做题的时候注意：Run the process with the highest priority. Processes with the same priority run round-robin** （但也要看题目要求）。 #### Multilevel Queue - Ready queue is partitioned into separate queues, e.g.: （不一定是只有两个 queue ，可以有多个） - foreground (interactive 交互processes) - background (batch 批处理 processes) - Process permanently in a given queue (stay in that queue = 进程永久处于某个给定队列中，不会在队列间移动。) - Each queue has its own scheduling algorithm - foreground – RR - background – FCFS - Scheduling must be done between the queues - Fixed priority scheduling - Each queue has a given priority - High priority queue is served before low priority queue - Possibility of starvation - Time slice - Each queue gets a certain amount of CPU time [](https://imgse.com/i/pEBVPlF) - Multilevel feedback queue - 一个进程可以在不同队列之间移动； - 可以通过这种方式考虑老化机制（防止饥饿现象） - 优点：防止饥饿 - 多级反馈队列调度器 - 这是最通用的 CPU 调度算法 - 由以下参数定义： 1. 队列数量 2. 每个队列的调度算法 3. 进程在队列之间移动的策略 4. 何时提升一个进程的队列级别 5. 何时降低一个进程的队列级别 6. 当一个进程需要服务时，它将进入哪个队列 - Example - **三个队列**： 1. **队列 Q0**：采用时间片为 8 毫秒的轮转调度算法（RR）。 2. **队列 Q1**：采用时间片为 16 毫秒的轮转调度算法（RR）。 3. **队列 Q2**：采用先来先服务调度算法（FCFS）。这里是 FCFS 和 RR 相结合的多级反馈队列情况。 - **调度规则**： - 一个新作业进入队列 Q0，在 Q0 中按照先来先服务（FCFS）原则进行调度。 - 当该作业获得 CPU 时，它会被分配 8 毫秒的 CPU 时间。 - 如果该作业在 8 毫秒内没有完成，它将被移动到队列 Q1。 - 在队列 Q1 中： - 作业同样按照先来先服务原则调度，并且会额外获得 16 毫秒的 CPU 时间。 - 如果作业仍然没有完成，它将被抢占 CPU 并移动到队列 Q2，在队列 Q2 中它会一直运行直到完成，但具有较低的优先级。 ### Thread Scheduling - Distinguish between **user-level** and **kernel-level** threads #### For user-level thread In Many-to-one and Many-to-Many model, - **多对一模型（Many - to - one Model）**：多个用户级线程映射到一个内核级线程（轻量级进程 Light-Weigh-Process，LWP）。在这种模型下，**用户级线程的调度由线程库 (thread libraries) 在用户空间完成**，效率较高，但一旦某个线程执行了阻塞操作（如I/O请求），整个进程都会被阻塞，因为所有用户级线程共享同一个内核级线程。 - process-contention scope (PCS) **进程内竞争范围** - **多对多模型（Many - to - many Model）**：多个用户级线程映射到多个内核级线程。线程库负责将用户级线程调度到内核级线程上运行。 #### For kernel-level thread **Kernel threads are scheduled by Kernel onto available CPU** - system-contention scope(SCS) **系统内竞争范围** - competition is among all kernel-level threads from all processes in the system ### Multi-Processor Scheduling The term Multiprocessor now applies to the following system architectures: - Multicore CPUs - Multithreaded cores - NUMA systems #### Symmetric multiprocessing (SMP) 对称多处理 - Definition: Each processor is self scheduling - Two strategies - All threads may be in a common ready queue (a) - Each processor may have its own private queue of threads (b) [](https://imgse.com/i/pEBV7A1) #### Multicore Processors 省流：**多核处理器（Multicore Processors）**：当前趋势是将多个处理器核心集成在同一物理芯片上，这样不仅速度更快，功耗也更低。同时，每个核心上的多线程技术也在发展。当线程访问不在CPU缓存中的内存内容时，会发生内存延迟（memory stall），解决办法是为每个核心配备多个硬件线程，当一个线程出现内存延迟时，切换到其他线程执行。 [](https://imgse.com/i/pEBVbh6) #### Multithreaded Multicore System 以芯片多线程（CMT，如英特尔的超线程技术）为例，在一个四核系统中，若每个核心有2个硬件线程，操作系统会将其视为8个逻辑处理器。调度分为两个层次： - 操作系统决定哪个软件线程在逻辑CPU上运行。 - 每个核心决定哪个硬件线程在物理核心上运行。 #### Multiple-Processor Scheduling –Load Balancing **负载均衡（Load Balancing）**在SMP系统中，为提高效率需使所有CPU保持负载均衡。负载均衡旨在均匀分配工作负载，有两种方式： - 推迁移（Push migration）：周期性检查每个处理器的负载，将任务从过载的CPU推送到负载较轻的CPU。 - 拉迁移（Pull migration）：空闲的CPU从繁忙的CPU中拉取等待的任务。 - **这两种方式通常 Parallel实现。** #### Multiple-Processor Scheduling –Processor Affinity - 当一个线程在某个处理器上运行时，该**处理器的缓存会存储该线程的内存访问信息，即线程对该处理器具有亲和性。** - 负载均衡可能影响处理器亲和性，因为线程可能为平衡负载在处理器间迁移，从而丢失原处理器缓存中的内容。 - **软亲和性（Soft affinity）**：操作系统尝试让线程在同一处理器上运行，但不保证。 - 硬亲和性（Hard affinity）：允许进程指定可运行的处理器集合，内核不会将该进程迁移到其他CPU，即使当前CPU负载很高。 #### NUMA and CPU Scheduling **NUMA与CPU调度**：非统一内存访问（NUMA）系统中，处理器访问本地内存比访问非本地内存更快。若操作系统支持NUMA，会将离CPU最近的内存分配给正在运行的线程，以提高内存访问效率。 ### Real-Time CPU Scheduling Types of challenges: - Soft real-time systems: Critical real-time tasks have the highest priority, but no guarantee as to when tasks will be scheduled (best try only) 关键实时任务具有最高优先级，但不保证任务何时被调度，只是尽力而为。 - Hard real-time systems: a task must be serviced by its deadline (guarantee) #### Event latency - Definition: the amount of time that elapses from when an event occurs to when it is serviced.从事件发生到其得到服务所经过的时间。 - Two types of latencies affect performance - Interrupt latency –time from arrival of interrupt to start of **kernel interrupt service routine(ISR)** that services interrupt - Dispatch latency(调度延迟) –time for scheduler to take current process off CPU and switch to another [](https://imgse.com/i/pEBVL9K) #### Priority-based Scheduling **基于优先级的调度（Priority - based Scheduling）**：对于实时调度，调度器必须支持抢占式、基于优先级的调度。但仅这样只能保证软实时，对于硬实时，还必须具备满足截止期限的能力。实时进程具有周期性需要CPU的特点，有处理时间t、截止期限d和周期p，且$0 ≤ t≤ d≤ p$，周期任务的速率为$1/p$。 [](https://imgse.com/i/pEBVO1O) #### Rate Monotonic Scheduling 根据任务周期的倒数分配优先级，周期越短，优先级越高；周期越长，优先级越低。例如，$P1$每50ms需要运行20ms（$t = 20$，$d = p = 50$），$P2$每100ms需要运行35ms（$t = 35$，$d = p = 100$），则$P1$的优先级高于$P2$。但该算法可能出现错过截止期限的情况，如$P1$每50ms需运行25ms，$P2$每80ms需运行35ms时，$P2$会在80ms时错过截止期限。 #### Missed Deadlines with Rate Monotonic Scheduling 根据截止期限分配优先级，截止期限越早，优先级越高；截止期限越晚，优先级越低。例如，学生在面对多个不同作业截止期限时，可能会采用这种调度方式安排任务。 #### Proportional Share Scheduling 比例共享调度（Proportional Share Scheduling）是一种CPU调度算法，旨在按照一定比例为系统中的各个进程分配CPU时间，以确保每个进程都能获得相对公平的资源份额。下面结合你提供的课件内容来详细介绍： 1. **份额分配机制**：在该调度算法中，系统将CPU时间划分为一定数量的份额（shares）。例如，课件中提到假设\(T = 20\)，则表示总共有20个份额，每一个份额代表5%的CPU时间。每个应用程序会被分配到\(N\)个份额（\(N < T\)），这就保证了该应用程序能获得\(N/T\)比例的总处理器时间。比如，若一个应用程序获得\(N = 5\)个份额，那么它将拥有\(5/20 = 25\%\)的CPU时间。 2. **时间分配特点**：无论应用程序是否使用分配给它的CPU时间，该比例的CPU时间都为其保留。这意味着，即使某个应用程序在某一时刻处于空闲状态，没有使用完分配的CPU时间份额，其他应用程序也不能占用这部分空闲的时间，以保证分配的公平性和稳定性。 Loading... ## Chapter 1: Introduction to Operating System ### Basic Knowledge 1. **（背）Computer System Architecture** - **I/O Devices**: I/O devices can work concurrently (同时) with the CPU. **The device controller is responsible for a specific device type and has a local buffer.** Data is transferred between the device and the **local buffer of the controller.** - I/O 的定义：**Betwen device and buffer of controller** 一定要区分不是 Devices and Memory - 为什么要用 Buffer: Balance the speed difference between device and CPU (Usually CPU is much faster than device) - **CPU and Memory**: Concepts of single - processor, dual - core processor, and the term Non - Uniform Memory Access system (NUMA). - Single/Multiple Processor: **Each Processor has its own cache. All processors share main memory.** - Dual-core Processor: **Each core has its own cache (L1). All cores share L2 cache.** - NUMA: 每个 CPU 有自己的 Memory 块，CPU 之间也可以通过 interconnect 访问别的 CPU 的内存（但是慢） [](https://imgse.com/i/pE0thtO) 2. **（背）Definition of Operating System** - The operating system is an intermediate **program** between users and computer hardware. - Components: **Kernel (resident in memory)**, system programs, application programs, middleware. 3. （看即可）Goals of Operating System - Personal Computers: Emphasize convenience, ease of use, and good performance. - Shared Computers (such as mainframes or minicomputers): Satisfy all users, efficiently utilize hardware, and manage user programs. - Mobile Devices (such as smartphones and tablets): Optimize usability and battery life, and provide user interfaces such as touchscreens and voice recognition. - Embedded Computers: Run programs. 4. **（背）Operations of Operating System** - **Management Work Content**: Caching, process management, memory management, file management, secondary storage management, I/O, protection, and security. 5. **（背）Interrupt Mechanism** - **Interrupt Definition**: A signal sent by **hardware or software** that requires immediate processing. Software interrupts (traps or exceptions) are triggered by errors or user requests (system calls), and hardware interrupts are generated by devices. - **Interrupt Handling Steps**: 1. Save the CPU state (store registers and the program counter PC) 2. Determine the interrupt type through the interrupt vector to obtain the corresponding ISR address 3. Run the ISR to handle the interrupt. - **DMA (Direct Memory Access)**: **The device controller can directly transfer data blocks from the buffer to the main memory without CPU intervention.** Only one interrupt is generated for each data block, and the transfer speed is fast. [](https://imgse.com/i/pE0t4hD) 6. （看即可）Process - related - **Difference between Program and Process**: **A program is a passive entity in storage, and a process is an active entity in memory.** The creation and execution of a process require resources such as CPU, memory, I/O, files, and initialization data. When a process ends, reusable resources need to be reclaimed. A process can be single - threaded or multi - threaded, and the program counter specifies the position of the next instruction. - **Multiprogramming and Multitasking**: Multiprogramming means that some jobs are stored in memory simultaneously, and job scheduling selects and loads jobs. Multitasking means that the CPU switches jobs frequently, and CPU scheduling determines the next running job. - **Process Execution Modes**: User mode and kernel mode. The dual - mode can protect the operating system and other system components. System calls are used to request operating system services. - **Process Management Activities**: Create and delete user and system processes, suspend and resume processes, process synchronization, process communication, deadlock handling. 7. Memory Management - To execute a program, part or all of the program instructions and data need to be placed in memory. - Memory Management Activities: Track memory usage, decide the loading and unloading of processes and data, and allocate and release memory space as needed. 8. File System Management - The operating system provides a unified logical view, abstracting physical attributes into files. Files are usually organized into directories. - File System Activities: Create and delete files and directories, and map files to secondary storage. 9. Secondary Storage Management - Disks are used to store data that is not suitable for the main memory or needs to be stored for a long time. - Management Activities: Mounting and unmounting, free space management, storage allocation, disk scheduling, partitioning, protection. 10. I/O Sub - system - Hide the characteristics of hardware devices. - Responsible for the memory management of I/O (buffering, caching, spooling), and provide a general device driver interface and specific hardware device drivers. 11. Protection and Security - Protection: A mechanism to control the access of processes or users to resources defined by the operating system. - Security: Defend the system against internal and external attacks, and distinguish users and determine permissions through user IDs and group IDs. 12. Virtualization - Virtualization abstracts the hardware of a single computer into multiple execution environments, which is achieved through virtual machines (such as VirtualBox, VMware). - Virtual Machine Managers (VMMs) run directly and provide services and resource management for virtual machine processes. 13. Free and Open - source Operating Systems - Provided in the form of source code, such as GNU/Linux, BSD UNIX, etc. - Free software (a social movement) and open - source (a development technique) overlap in most cases but have differences. 14. **Data Structures**: Kernel data structures include singly linked lists, doubly linked lists, circular linked lists, binary search trees, hash tables, bitmaps, etc. ### Knowledge Graph ``` |--Computer System Architecture | |--I/O Devices | | |--Concurrent work with CPU | | |--Device Controller | | | |--Responsible for specific device type | | | |--Has local buffer | |--CPU and Memory | | |--Single - processor | | |--Multi - processor (such as dual - core) | | |--Non - Uniform Memory Access system (NUMA) |--Operating System | |--Definition | | |--Intermediate program between users and hardware | | |--Composition: Kernel, system programs, application programs, middleware | |--Goals | | |--Personal Computers: Convenience, ease of use, good performance | | |--Shared Computers: User satisfaction, efficient hardware utilization, program management | | |--Mobile Devices: Optimize usability and battery life | | |--Embedded Computers: Run programs | |--Operations | | |--Caching | | |--Process Management | | | |--Difference between program and process | | | |--Multiprogramming and multitasking | | | |--Process execution modes (user/kernel mode) | | | |--Process management activities | | |--Memory Management | | | |--Relationship between program execution and memory | | | |--Memory management activities | | |--File System Management | | | |--Unified logical view and file directories | | | |--File system activities | | |--Secondary Storage Management | | | |--Disk usage | | | |--Management activities | | |--I/O Sub - system | | | |--Hide hardware characteristics | | | |--I/O memory management and drivers | | |--Protection and Security | | | |--Protection: Control resource access | | | |--Security: Defend against internal and external attacks and user differentiation |--Virtualization | |--Concept: Abstract hardware into multiple execution environments | |--Implementation: Virtual machines (such as VirtualBox, VMware) | |--Virtual Machine Managers (VMMs) |--Free and Open - source Operating Systems | |--Provided in the form of source code | |--Difference between free software and open - source |--Kernel Data Structures | |--Singly linked lists, doubly linked lists, circular linked lists | |--Binary search trees | |--Hash tables, bitmaps ``` ## Chapter 2: Operating-System Structures ### Basic Knowledge #### (I) Operating System Services 1. Service Categories - User - Oriented - **User Interface**: Command - Line Interface (CLI), Graphical User Interface (GUI), Touchscreen, Batch Processing. - **Program Execution**: Load programs into memory, run and terminate programs. - **I/O Operations**: Perform input and output operations on devices. - **File System Operations**: Read, write, create, delete files, etc. - **Communication**: Exchange information between processes. - **Error Detection**: Handle potential hardware or software errors. - Efficient - Operation - Oriented - **Resource Allocation**: Allocate resources such as CPU, main memory, file storage, I/O devices to multiple users or jobs. - **Logging**: Track the usage of computer resources by users. - **Protection and Security**: Protection ensures controlled access to system resources; security prevents the system from external attacks. 2. **Abstract View**: The operating system provides basic computing resources and controls and coordinates the use of hardware among various applications and users. #### (II) Operating System Interfaces 1. User - Operating System Interface - **CLI**: Command - Line Interface. Commands are sometimes implemented in the kernel (built - in commands) and sometimes by system programs. Different types of shells such as Bourne Shell (sh), GNU Bourne - Again Shell (bash), C Shell (csh), Korn Shell (ksh), Z Shell (zsh). - **GUI**: Graphical User Interface. It is user - friendly, based on the desktop metaphor, and uses icons to represent files, programs, etc. The combination of CLI and GUI in different operating systems (e.g., Windows is mainly GUI - based with the CLI "cmd" shell; Mac OS X has the "Aqua" GUI interface and a UNIX kernel and shell; Unix and Linux are mainly CLI - based with an optional GUI). The new interface features of touchscreen devices (gesture - based operations, virtual keyboard input, voice commands). 2. **System Calls**: Provide a programming interface for programs to use operating system services. Parameter passing methods (register passing, memory block table passing, stack passing). Types of system calls (process control, file management, device management, information maintenance, communication, protection). 3. **API (Application Programming Interface)**: Application developers design programs based on the API. Common APIs include Win32 API (for Windows), POSIX API (for POSIX - based systems, including most UNIX, Linux, Mac OS X versions), Java API (for Java Virtual Machine). **The API hides the details of the operating system interface.** 4. **Standard C Library and System Calls**: Standard C library functions may call system calls. Using the standard C library is **simpler and more portable** , but system calls are more powerful and faster. #### (III) Operating System Structures 1. **History of Operating System Implementation**: In the early days, assembly language was used. Later, system programming languages (such as Algol, PL/1) were used. Now, C and C++ are mostly used, usually a combination of multiple languages, with assembly for the底层 and C for the main body. 2. Types of Operating System Structures | OS Structure Type | Key Features | | --------------------------------------- | ------------------------------------------------------------ | | Simple Structure | - Unorganized implementation <br> - Direct hardware interaction <br> - Basic system services | | Monolithic Structure (Traditional UNIX) | - Composed of system programs and a large, non - layered kernel <br> - All kernel functions at the same level <br> - High efficiency due to direct interactions | | Layered Structure | - Divided into multiple layers <br> - Each layer uses services of the lower layer <br> - Clear structure for building and debugging | | Microkernel | - Minimal core functions in the kernel (e.g., process & memory management, communication) <br> - Other functions as user - space servers <br> - Communication via message passing | | Module Structure | - Core components are independent modules <br> - Modules can be loaded and unloaded as needed <br> - Object - oriented approach for interaction | | Hybrid Structure | - Combines features of multiple structures <br> - Balances performance, scalability, reliability, and security | 1. Examples - **macOS and iOS**: Based on the Mac OS X structure, with Cocoa and Cocoa Touch frameworks, providing graphics and media support. It contains the Mach microkernel and the BSD UNIX kernel. Darwin provides two system call interfaces (Mach system calls and BSD system calls). - **Android**: Based on the Linux kernel but with modifications. It is open - source and developed for smartphones and tablets. The runtime environment includes core libraries and the Dalvik Virtual Machine (gradually replaced by the ART VM). Applications are developed using Java and the Android API. #### (IV) Operating System Booting 1. **Boot Process**: After the system is powered on, **the code at a fixed memory location is executed**. Through the bootstrap loader, the kernel can be loaded into memory and started in one step (the bootstrap loader in ROM or EEPROM locates and loads the kernel) or two steps (the ROM code (BIOS) first loads the boot block on the hard disk, and then the bootstrap loader in the boot block loads the kernel). After that, system daemons are started. ### Knowledge Graph ``` Operating System Structure |--Operating System Services | |--User - Oriented | | |--User Interface (CLI, GUI, Touchscreen, Batch Processing) | | |--Program Execution (Load, Run, Terminate Programs) | | |--I/O Operations | | |--File System Operations | | |--Communication | | |--Error Detection | |--Efficient - Operation - Oriented | |--Resource Allocation (CPU, Memory, etc.) | |--Logging | |--Protection and Security (Protection, Security) |--Operating System Interfaces | |--User - Operating System Interface | | |--CLI (Command Implementation Methods, Different Shell Types) | | |--GUI (Features, Combinations in Different Systems, Touchscreen Interface Features) | |--System Calls | | |--Definition and Function | | |--Parameter Passing Methods (Register, Memory Block Table, Stack) | | |--System Call Types (Process Control, File Management, etc.) | |--API | | |--Definition and Function | | |--Common APIs (Win32, POSIX, Java) | |--Standard C Library and System Calls | |--Features of Standard C Library (Simple, Portable) | |--Features of System Calls (Powerful, Fast) |--Operating System Structures | |--History of Operating System Implementation (Early Assembly, Later System Programming Languages, Current C/C++ and Hybrid Situations) | |--Types of Operating System Structures | | |--Simple Structure (e.g., MS - DOS) | | |--Monolithic Structure (Composition and Features of Traditional UNIX) | | |--Layered Structure (Layered Approach, Advantages and Disadvantages) | | |--Microkernel (Principle, Advantages, Disadvantages) | | |--Modules (Implementation Method, Features) | | |--Hybrid Systems (Hybrid Situations of Common Operating Systems) | |--Examples | |--macOS and iOS (Based on Structure, Frameworks, Kernels, System Call Interfaces) | |--Android (Based on Kernel, Runtime Environment, Application Development Methods) |--Operating System Booting | |--Boot Process (One - step or Two - step Kernel Loading, Starting Daemons) ``` ## Chapter 3: Processes ### Basic Knowledge #### Process Definition - A process is an instance of a program in execution. It includes the program code, its data, the CPU state (registers), and the process control block (PCB). For example, when you run a text - editing program, each instance of that program running is a process. #### Process Control Block (PCB) - The PCB contains all the information about a process. It includes process - specific identification (PID), CPU - related information (such as the program counter, register values), memory - related information (e.g., memory allocation details), and I/O - related information (e.g., open file descriptors). It serves as a handle for the operating system to manage and control the process. #### Process States ##### Basic States - **New**: The process is being created. For instance, when you double - click an application icon, the system starts the process creation, and it enters the new state. - **Ready**: The process is waiting to be assigned to a CPU. It has all the necessary resources except the CPU. Multiple ready processes form the ready queue. - **Running**: The process is currently executing on the CPU. Only one process can be running on a single - core CPU at a time. - **Blocked (Waiting)**: The process is waiting for an event to occur, such as an I/O operation to complete, a resource to become available, or a signal. For example, if a process is waiting for data to be read from a disk, it enters the blocked state. - **Terminated**: The process has finished execution and its resources are being reclaimed by the operating system. [](https://imgse.com/i/pE0BN28) #### Process Scheduling ##### Scheduling Queues - **Ready Queue**: Holds all the processes that are ready to execute and waiting for the CPU. - **Device Queues**: Each I/O device has a device queue. Processes that are waiting for a particular I/O device to become available are placed in the corresponding device queue. ##### Context Switch - **Save the state** of the old process (the one is running on CPU) and - **Load the saved state** (CPU registers, program counter in PCB) for the new process (the one will run on CPU) via a context switch (i.e., switch PCB) Context switch time is: - **Overhead (额外开销)**, , the system does no useful work while switching - **dependent on the complexity of OS**. The more complex the OS and the PCB，the longer time the context switch - **also dependent on hardware support** #### Process Operations ##### Process Creation - A parent process can create a child process. In Unix - like systems, the `fork()` system call is used to create a new process. The child process is a copy of the parent process in terms of the address space (initially), but they can diverge in their execution paths. ##### Process Termination - A process can terminate voluntarily, for example, when it has completed its task or encountered an error condition that it cannot handle. In Unix, the `exit()` system call is used for this purpose. A process can also be terminated involuntarily by the operating system. #### Inter - Process Communication (IPC) ##### Shared Memory - Processes communicate through a shared memory - User processes control - Requires careful synchronization to avoid data races. - Producer-Consumer Problem (用来描述 sychronous problem) - Producer process wait while buffer is full (If it is unbounded buffer, no need to wait) - Consumer process wailt while buffer is null - Two types of buffer zone: unbounded no practical limit on the size of the buffer / bounded buffer: 循环队列 ##### Message Passing - Kernel Control - Processes communicate by sending and receiving messages. - Implementation of communication link - Physical Link Level: Shared memory/Hardware bus/network - Logical level: **Direct(process to process) or indirect(mail box)/Synchronous(blocking) or asynchronous(non-blocking)/Automatic or explicit buffering** - Direct Communication - Processes must name each other explicitly. - Send()andreceive() primitives (原语) are defined as - `send(P, message)` –send a message to process P - `receive(Q, message)` –receive a message from process Q - Properties of communication link - Links are established **automatically** - A link is associated with exactly one pair of communicating processes - Between each pair there exists exactly one link - The link may be unidirectional, but is usually **bi-directional** - Inderict Communication - Messages are directed and received from mailboxes (also referred to as ports(端口)) - Each mailbox has a unique id - Processes can communicate only if they share a mailbox - The send() and receive() primitives are defined as - send(*A, message*) –send a message to mailbox A - receive(*A, message*) –receive a message from mailbox A - Operations - Create a new mailbox - Message passing by mailbox - Destroy Mailbox - Properties - Link established only if processes share one mailbox - Link may be associated with multiple processes - **Each pair of processes may share many links** - Link can be undirectional or bi-directional - Message Passing: Synchronization - **Two statuses: Blocking / Non-Blocking** - Blocking (Sychronous) - **Blocking send: Sender is blocked until the message is received by the receiving process or mailbox** - **Blocking receive: Receiver is blocked until there is a message available ** - Non-Blocking (Asychronous) - Non-blocking send--the sender sends the message and continues without waiting for the message to be received - Non-blocking receive--the receiver receives: A valid message / NULL - Different combinationspossible - If both send and receive are blocking, this case is called rendezvous（会合） - Message Buffering: Queue of message attached to the link, in the **kernel memory** - Zero capacity –no messages are queued on a link.Sender must wait for receiver (rendezvous) - Bounded capacity –finite length of *n*messagesSender must wait if link full - Unbounded capacity –infinite length Sender never waits - 不是很重要的东西：IPC System Example - **以消息传递为中心**：Windows系统通过高级本地过程调用（ALPC）工具实现以消息传递为中心的进程间通信，且仅在同一系统的进程间生效。 - 通信步骤 - 客户端打开子系统连接端口对象的句柄。 - 客户端发送连接请求。 - 服务器创建两个私有通信端口，并将其中一个的句柄返回给客户端。 - 客户端和服务器使用相应的端口句柄发送消息、回调以及监听回复。 - 消息传递方式 - **小消息（不超过256字节）**：使用端口的消息队列作为中间存储，消息从一个进程复制到另一个进程。 - **大消息**：需通过一个与通道相关联的共享内存区域（段对象）传递。 - **超大消息**：当数据量太大无法放入段对象时，服务器进程可使用API直接读写客户端的地址空间。 - **ALPC的可见性**：ALPC工具并非Windows API的一部分，因此应用程序员无法直接看到。 #### Pipes - Two types - Ordinary pipe (anonymous pipe): 除了创建这个 pipe 的进程以外都不可见。Typically, a parentprocess creates a pipe and uses it to communicate with a childprocess that it created. (Not all) - Named pipes –can be accessed without a parent-child relationship. - Ordinary pipes [](https://imgse.com/i/pE0RwsP) - Named pipes - Named Pipes are more powerful than ordinary pipes - Communication is bidirectional - No parent-child relationship is necessary between the communicating processes - Several (>=2) processes can use the named pipe for communication - Provided on both UNIX and Windows systems ### Socket - endpoint for communication - a data structure inside the kernel that represents the local end of a network connection - IP + Port ## Chapter 4: Threads ### Definition [](https://imgse.com/i/pE0jA6f) #### Threads - A thread is a basic unit of *CPU* utilization; it comprises a thread ID, a program counter (**PC**), a register set, and a stack - Most modern applications are multi-threaded - Kernel is multi-threaded #### Pros and Cons of threads ##### Pros - Economy - Creating process: heavy-weight - Creating threads: light-weight - Resource sharing - Threads share the memory and resources of process to which they belong by default - Responsiveness - may allow continued execution if part of process is blocked, especially important for user interfaces - Efficiency - Scalability ##### Cons - More difficult to program with threads (a single process can now do multiple things at the same time). - New categories of bug are possible (synchronizationis then required between threads: Chapter 6). #### Compare with processes | Similiarities | Differences | | ------------------------------------------------------------ | ------------------------------------------------------------ | | Threads share CPU and only one thread active (running) at a time. | A thread is a component of a process | | Threads within a processes execute sequentially. | Multiple threads can exist within one process. | | Thread can create children. | Multiple threads execute concurrentlyand share resources such as memory, while different processes do not share these resources. | | If one thread is blocked, another thread can run. | | ### Multicore Programming #### Programming Challenge - Identifying Tasks: Find areas of an application that can be divided into separate and concurrent tasks. - Balance: Ensure tasks perform equal work of equal value. - Data splitting: Similar to dividing tasks. - Data dependency - Test and debug **Parallelism: A system can perform more than one task simultaneously （并行）** **Concurrency: Single processor / core, CPU scheduler providing concurrency by doing context switches; More than one task are progressing** Notice the difference between concurrency and parallelism: **Parallelismimplies concurrency, but concurrencydoes not imply parallelism.** [](https://imgse.com/i/pE0jDc6) #### Types of Parallelism - **Data parallelism** focuses on distributing subsets of the same dataacross multiple computing cores and performing the same operation on eachcore. - **Task parallelism** involves distributing not data but tasks (threads) acrossmultiple computing cores. Each thread is performing a unique operation. #### Amdahl’s Law [](https://imgse.com/i/pE0j5gP) 1. **公式**： $$ Speedup \leq \frac{1}{S + \frac{1 - S}{N}} $$ 其中： - $ Speedup $ 表示加速比，即优化或并行化后系统性能与优化或并行化前系统性能的比值。例如，如果优化前运行一个程序需要100秒，优化后需要20秒，那么加速比就是 $ \frac{100}{20} = 5 $ 倍。 - $ S $ 是程序中串行部分所占的比例，取值范围是 $ 0 \leq S \leq 1 $ 。例如，如果一个程序有20%的部分必须串行执行，那么 $ S = 0.2 $ 。 - $ N $ 是处理器核心的数量。比如，从单核心升级到4核心处理器，这里 $ N = 4 $ 。 2. **推导过程**： 假设在单核心处理器上运行程序的总时间为 $ R_1 $ ，程序由串行部分和并行部分组成，串行部分时间占比为 $ S $ ，并行部分时间占比为 $ P $ ，且 $ S + P = 1 $ ，那么 $ R_1 = S + P = 1 $ （这里将单核心运行时间归一化设为1）。 当使用 $ N $ 个核心运行程序时，串行部分时间不变仍为 $ S $ ，而并行部分由于可以并行执行，其时间变为 $ \frac{P}{N} $ ，所以在 $ N $ 个核心上运行的总时间 $ R_N \geq S + \frac{P}{N} = S + \frac{1 - S}{N} $ （这里用 “ $ \geq $ ” 而不是 “ $ = $ ” ，是因为线程之间额外的通信开销）。 因此，加速比 $ Speedup = \frac{R_1}{R_N} \leq \frac{1}{S + \frac{1 - S}{N}} $ 。 3. **实际应用案例**： 课件中给出了一个例子，如果应用程序75%是并行的（即 $ P = 0.75 $ ），25%是串行的（即 $ S = 0.25 $ ），从1个核心增加到2个核心时： 首先计算在2核心上运行的时间 $ R_2 = 0.25 + \frac{0.75}{2} = 0.25 + 0.375 = 0.625 $ 。 然后得出最大加速比 $ Speedup = \frac{1}{0.625} = 1.6 $ 倍。这意味着增加一个核心后，理论上程序最多能快1.6倍。 4. **局限性与意义**： - **局限性**：随着 $ N $ 趋近于无穷，最大加速比趋近于 $ \frac{1}{S} $ 。这表明程序的串行部分对增加核心所获得的性能提升有着不成比例的影响。也就是说，如果串行部分占比很大，即使不断增加核心数量，性能提升也会非常有限。例如，若 $ S = 0.5 $ ，那么无论增加多少核心，加速比最大也只能达到2倍。此外，阿姆达尔定律没有充分考虑当代多核系统中的一些复杂因素，如线程间通信开销、缓存一致性等问题在实际情况中对性能的影响可能更为复杂。 - **意义**：它提醒开发者，在进行并行化优化时，要特别关注程序中的串行部分，因为这往往是性能提升的瓶颈。如果串行部分占比过高，单纯增加核心数量并不能显著提高性能，可能需要重新设计算法或架构，减少串行部分的比例，才能更有效地利用多核处理器的优势。 #### Gustafson’s Law 1. $$ \text{speed}_{\text{up}} = S + P \times N = N + (1 - N) \times S $$ 2. It is based on the assumption of a fixed problem size = an execution workload that does not change with respect to the improvement of the resources #### User Threads and Kernel Threads - User threads: management (thread creation, thread scheduling, etc.) done by user-level threads library. - Kernel threads: management (thread creation, thread scheduling, etc.) supported by the kernel | Type | Advantages | Disadvantages | | -------------- | ------------------------------------------------------------ | ------------------------------------------------------------ | | User Threads | **1.** No need for operating system support, can run on old or simple operating systems **2.** No need for system calls, only library function calls are required, which is fast | **1.** The number of threads in a process does not affect the CPU time it gets, that is, a single - threaded process and a multi - threaded process get the same amount of time 2. Thread scheduling within a process needs to be completed at the user level, which is complex for programming, and threads need to cooperate with each other | | Kernel Threads | 1. The kernel knows the number of threads in a process and can allocate more CPU time to multi - threaded processes **2.** Thread scheduling is automatically completed by the kernel, no need for cooperation between threads, and user programs are easy to write | **1.** Every thread management operation requires a system call, which is slow **2. T**he kernel's process control block (PCB) data structure is more complex, and it needs to track both the process and the threads within the process | Ultimately, a relationship must exist between user threads and kernel ##### Many-to-One Model  - Many user-level threads mapped to single kernel thread. - One thread blocking (waiting for something) causes all threads to block (because their common kernel thread is blocked). - Multiple threads may not run in parallel on multicore system because only one may be in kernel at a time. - Few systems currently use this model - Examples: GNU Portable Threads / Solaris Green Threads ##### One-to-One Model [](https://imgse.com/i/pE0vXZD) - One user-level threads mapped to one kernel thread - One thread blocking **does not** cause all threads to block (Only its corresponding kernel thread blocked) - Allow multiple threads to run parallel on multiprocessors. - **Drawback: Number of threads per process sometimes restricted due to overhead.** ##### Many-to-Many Model  - Allows many user level threads to be mapped to many kernel threads. - Allows the operating system to create a sufficient number of kernel threads. - **Drawbacks: Hard to be implemented -> Few systems apply Many-to-Many model** #### `pthreads` Programming POSIX Pthreads是一个用于线程创建和同步的POSIX标准（IEEE 1003.1c）API，在UNIX操作系统（如Linux和Mac OS X）中较为常见，可在用户空间或内核级实现。以下重点介绍 `pthread_attr_init`、`pthread_create` 和 `pthread_join` 的用法： 1. **`pthread_attr_init` 函数** - **功能**：初始化一个线程属性对象 `pthread_attr_t`。通过该函数，可以获取线程属性的默认值，之后可以根据需求对这些属性进行修改，如设置线程的栈大小、调度策略等。 - **用法示例**： ```c pthread_attr_t attr; pthread_attr_init(&attr); ``` **说明**：在使用线程属性之前，必须先调用 `pthread_attr_init` 进行初始化。该函数的参数是一个指向 `pthread_attr_t` 类型变量的指针。 2. **`pthread_create` 函数** - **功能**：创建一个新的线程。新线程从指定的函数开始执行。 - **函数原型**： ```c int pthread_create(pthread_t *thread, const pthread_attr_t *attr, void *(*start_routine) (void *), void *arg); ``` - **参数说明**： - `thread`：指向 `pthread_t` 类型变量的指针，用于存储新创建线程的标识符。 - `attr`：指向线程属性对象 `pthread_attr_t` 的指针。如果为 `NULL`，则使用默认的线程属性。 - `start_routine`：新线程开始执行的函数指针。该函数接受一个 `void *` 类型的参数，并返回一个 `void *` 类型的值。 - `arg`：传递给 `start_routine` 函数的参数。 - **用法示例**： ```c pthread_t tid; pthread_attr_t attr; pthread_attr_init(&attr); pthread_create(&tid, &attr, runner, argv[1]); ``` - **说明**：在上述示例中，`runner` 是新线程要执行的函数，`argv[1]` 是传递给 `runner` 函数的参数。 3. **`pthread_join` 函数** - **功能**：等待指定的线程结束。调用该函数的线程会被阻塞，直到指定的线程执行完毕。通过这种方式，可以确保主线程在子线程完成任务后再继续执行，避免出现数据竞争或逻辑错误。 - **函数原型**： ```c int pthread_join(pthread_t thread, void **retval); ``` - **参数说明**： - `thread`：要等待的线程的标识符。 - `retval`：指向 `void *` 类型指针的指针。如果不为 `NULL`，则 `pthread_join` 会将被等待线程的返回值（即 `start_routine` 函数的返回值）存储在 `*retval` 中。 - **用法示例**： ```c pthread_t tid; // 创建线程 pthread_create(&tid, NULL, runner, argv[1]); // 等待线程结束 pthread_join(tid, NULL); ``` - **说明**：在上述示例中，主线程调用 `pthread_join` 等待 `tid` 标识的线程结束。`NULL` 参数表示不获取被等待线程的返回值。 综合示例： ```c #include <pthread.h> #include <stdio.h> #include <stdlib.h> int sum; void *runner(void *param); int main(int argc, char *argv[]) { pthread_t tid; pthread_attr_t attr; if (argc != 2) { fprintf(stderr, "usage: thrd-posix <integer value>\n"); return -1; } if (atoi(argv[1]) < 0) { fprintf(stderr, "Argument %d must be non - negative\n", atoi(argv[1])); return -1; } pthread_attr_init(&attr); pthread_create(&tid, &attr, runner, argv[1]); pthread_join(tid, NULL); printf("sum = %d\n", sum); } void *runner(void *param) { int i, upper = atoi(param); sum = 0; if (upper > 0) { for (i = 1; i <= upper; i++) sum += i; } pthread_exit(0); } ``` 在这个示例中，主线程创建了一个新线程，新线程执行 `runner` 函数进行求和计算，主线程通过 `pthread_join` 等待新线程完成计算后，输出求和结果。 比较： | `pthread_exit()` | `return (void*)(intptr_t)0` | | ------------------------------------------------------------ | ------------------------------------------------------------ | | `pthread_exit` 是Pthreads库提供的函数，用于显式地终止调用它的线程 。 | `return` 是C语言的关键字，用于从函数中返回。在线程执行函数中使用 `return`，意味着函数执行结束，线程也随之结束，因为线程的执行逻辑就在这个函数中。 | | `pthread_exit` 的参数是一个 `void*` 类型的值，这个值可以被 `pthread_join` 函数获取，用于传递线程的执行结果等信息。在实际使用中，传递的可能是一个指向结构体的指针，结构体中包含各种线程执行相关的数据；或者像示例中传递一个简单的整数值（通过 `(void*)(intptr_t)` 进行类型转换）。 | 在线程执行函数中使用 `return` 返回值时，该返回值同样会被 `pthread_join` 获取。返回值的类型也需要转换为 `void*` 类型。 | ### Implicit Threading Motivation: - Growing in popularity as numbers of threads increase, program correctness more difficult with explicit threads - Creation and management of threads done by compilers and run-time libraries rather than programmers Methods: - Thread Pools - Fork-join - OpenMP #### Thread Pools - Create a number of threads in advance in a pool where they await work (预先创建一组线程置于池中等待任务) Advantages: - Usually slightly faster to service a request with an existing thread than create a new thread - Allows the number of threads in the application(s) to be bound to the size of the pool - Separating task to be performed from mechanics of creating task allows different strategies for running task - 如定期调度任务 #### Fork-Join - 多个线程（任务）先被创建（fork），执行完毕后再合并（join）。类似于分治 [](https://imgse.com/i/pEBC6z9) ```java Task(problem) if problem is small enough solve the problem directly else subtask1 = fork(new Task(subset of problem) subtask2 = fork(new Task(subset of problem) result1 = join(subtask1) result2 = join(subtask2) return combined results ``` #### Openmp - Set of compiler directives and an API for C, C++, FORTRAN - | Comparison Item | Define local variables in each `thread` function | Use thread - local storage (`thread_local`) | | --------------------------------- | ------------------------------------------------------------ | ------------------------------------------------------------ | | Data Independence | Variables are independent each time the function is called, but with a short lifespan when the function is called multiple times, making it difficult to maintain the state throughout the thread's lifecycle | Each thread has an independent copy, which persists throughout the thread's lifecycle and is initialized only once | | Sharing within a Thread | The scope of function - local variables is only within the function, making it difficult to share among different functions within the thread | It can be easily shared among different functions within the thread while maintaining data isolation between threads | | Memory Management and Performance | When the function is called frequently, variables are created and destroyed frequently, increasing overhead | Memory is allocated when the thread starts and released when it ends, suitable for resources that are used for a long time within the thread's lifecycle | #### Thread Cancellation - Definition: Terminating a thread before it has finished - Two general approaches: - **Asynchronous cancellation** terminates the target thread immediately - **Deferred cancellation** allows the target thread to periodically check if it should be cancelled ## Chapter 5: CPU Scheduling ### Basic Concepts - Purpose of multiprogramming: maximum CPU utilization - CPU–I/O Burst Cycle (一个 CPU Burst 接一个 I/O Burst) - Process execution consists of a cycleof CPU execution and I/O wait - CPU burst followed by I/O burst - **Process State Transitions**: A process transitions between different states during execution （五个状态 new-ready-running-waiting-terminated) ### CPU Scheduler - The CPU scheduler (CPU 调度程序) selects a process from the processes in ready queue, and allocates the CPU to it. - CPU scheduling decisions may take place when a process - **From Running to Waiting (Non - preemptive)**: When a process makes an I/O system call, it voluntarily relinquishes the CPU and enters the waiting state. For example, when reading a file, the process waits for the disk I/O operation to complete. - **From Running to Ready (Preemptive)**: When a clock interrupt occurs, the currently running process is suspended and returns to the ready queue, waiting to be scheduled again. This ensures that multiple processes can share the CPU time fairly. - **From Waiting to Ready (Preemptive)**: When the I/O operation is completed, such as the hard - disk controller sending an interrupt signal indicating that the data has been read, the waiting process enters the ready queue, waiting for CPU allocation. - **Termination (Non - preemptive)**: The process finishes execution, automatically ends, and releases CPU resources. - Preemptive and Non - preemptive Scheduling - **Non - preemptive Scheduling**: It is determined by the process itself. The scheduling process is relatively simple, but it may cause important processes to be blocked by unimportant processes for a long time. - **Preemptive Scheduling**: Scheduling occurs in addition to the non - preemptive situations mentioned above. It is determined by the hardware and the kernel. It can improve the response time and create an interactive environment, but it may lead to race conditions, especially when multiple processes share data. In addition, issues such as shared - data access, CPU preemption in kernel mode, and how to handle interrupts during key operating - system activities need to be considered. ### Scheduling Criteria 废话一堆感觉没什么看的 - **CPU Utilization**: Keep the CPU as busy as possible, that is, maximize CPU utilization to fully utilize the hardware resources. - **Throughput**: The number of processes that complete execution per unit time. The goal is to increase throughput as much as possible so that the system can handle more tasks. - **Response Time**: The time from the submission of a request to the generation of the first response. It is mainly for time - sharing environments and measures the system's response speed to user requests. - **Waiting Time**: The total time a process waits in the ready queue. The waiting time should be minimized to improve the process execution efficiency. - **Turnaround Time**: The total time required to execute a specific process, including waiting time and all CPU burst times, that is, **turnaround time = waiting time + all CPU burst times**. Similarly, it is desired to minimize the turnaround time. ### Scheduling Algorithms #### Metrics to evaluate - Average waiting time: 进程在就绪队列中等待的总时间 $$ \text{waiting time} = \text{turnaround time} - \text{burst time} $$ - Average turnaround time：执行特定进程的总时间（从开始到结束，包括等待时间），计算方式为等待时间加上所有CPU突发时间，追求最小化 $$ \text{turnaround time} = \text{complete time} - \text{arrival time} $$ #### 做题流程 - 画 Gantt 图 - 维护 ready queue #### First-Come, First-Served (FCFS) Scheduling - FCFS调度算法按照进程到达就绪队列的先后顺序来调度进程，先到达的进程先获得CPU资源并执行，直到该进程完成任务或者主动让出CPU。 - **工作原理**：当一个进程进入就绪队列，它会按照到达顺序排在队列末尾。CPU调度程序总是从就绪队列的头部选择进程，将CPU分配给排在最前面的进程，该进程开始执行，直到运行结束、进行I/O操作（此时进入等待状态）或者因为其他原因主动放弃CPU，调度程序才会选择队列中的下一个进程。 例子：假设进程P1、P2、P3在时间t = 0时按顺序到达就绪队列，它们的突发时间（burst time，即进程需要占用CPU的时间）分别为：P1（24）、P2（3）、P3（3）。其甘特图（Gantt Chart）如下： | P1 | P2 | P3 | | ---- | ----- | ----- | | 0-24 | 24-27 | 27-30 | - Average waiting time: $\frac{0 + 24 + 27}{3} = 17$ - Average turnaround tume: $\frac{24 + 27 + 30}{3} = 27$ 潜在的问题： - **平均等待时间和周转时间可能较长**：当有长进程先到达时，后面的短进程需要等待很长时间，导致整体平均等待时间和周转时间变长，如第一个示例中的情况。 - **Convoy effect(护送效应)** -short process behind long proce - 如果有一个CPU密集型（CPU突发时间长、I/O突发时间短）的长进程先到达，后续跟着多个I/O密集型（I/O突发时间长、CPU突发时间短）的短进程，这些短进程会因为长进程占用CPU而长时间等待，就像护航队一样，降低了CPU和设备的利用率 。 #### Shortest-Job-First (SJF) Scheduling - SJF调度算法根据进程下一个CPU突发（CPU burst）的长度来安排调度，优先选择下一个CPU突发时间最短的进程执行，直到该进程完成或因其他原因（如I/O操作）暂停，然后再从就绪队列中选择下一个CPU突发时间最短的进程。 - 工作原理 - 系统为每个进程记录其下一个CPU突发的预计长度。 - 当CPU空闲时，调度程序遍历就绪队列，挑选出下一个CPU突发时间最短的进程，将CPU分配给它。 - 被选中的进程开始执行，直至完成任务、主动让出CPU（如进行I/O操作）或被抢占（在抢占式SJF中）。 - **应对**：通常通过预测来估计下一个CPU突发长度。一种常用方法是利用进程过去的CPU突发历史数据，采用指数平均法进行预测。 - 公式为 $\tau_{n+1} = \alpha t_{n} + (1 - \alpha)\tau_{n}$，其中 $\tau_{n+1}$ 是下一个CPU突发的预测值，$t_{n}$ 是上一个CPU突发的实际长度，$\tau_{n}$ 是上一次的预测值，$\alpha$ 是一个介于0和1之间的参数（通常设为0.5）。 - 当 $\alpha = 0$ 时，预测值始终等于初始值，不考虑历史实际数据； - 当 $\alpha = 1$ 时，预测值仅取决于上一个实际的CPU突发长度。一般情况下，公式展开后，越近期的实际数据权重越大。 - 实际上做题的时候 Burst time 会给定。系统情况是对每一个在 ready queue 里的 process 做一次预测，算出一个新的 burst time. 假设一组进程的到达时间和突发时间如下：（非抢占版） | 进程 | 到达时间 | 突发时间 | | ---- | -------- | -------- | | P1 | 0.0 | 6 | | P2 | 2.0 | 8 | | P3 | 4.0 | 7 | | P4 | 5.0 | 3 | 其调度甘特图如下： | P1 | P4 | P3 | P2 | | ----- | ----- | ------ | ------- | | 0 - 6 | 6 - 9 | 9 - 16 | 16 - 24 | 平均等待时间计算： - P1等待时间为 $0$。 - P2等待时间为P1、P4、P3的执行时间减去其到达时间，即 $(6 + 3 + 7) - 2 = 14$。 - P3等待时间为P1和P4的执行时间减去其到达时间，即 $(6 + 3) - 4 = 5$。 - P4等待时间为P1的执行时间减去其到达时间，即 $6 - 5 = 1$。 - 平均等待时间 = $(0 + 14 + 5 + 1) / 4 = 5$。 平均周转时间计算： - P1周转时间为 $6$。 - P2周转时间为 $24 - 2 = 22$。 - P3周转时间为$16 - 4 = 12$。 - P4周转时间为 $9 - 5 = 4$ 。 - 平均周转时间 = $(6 + 22 + 12 + 4) / 4 = 11$。 如果是抢占版（The preemptive version of SJFis also called shortest-remaining-time-first），就要每一个时刻检查 ready queue，把里面每一个process的burst time减去已经执行的部分的time，排序。取最小的执行。 **如果是 pre-emptive version**，注意公式： $$ \text{waiting time} = \text{turnaround time} - \text{burst time} $$ > 解释：在抢占式调度中，一个进程可能会多次被抢占，其执行过程被分割成多个片段。但无论进程执行过程如何被打断，周转时间始终是从进程到达系统到完成的总时长，突发时间是进程实际占用CPU运行的累计时长。因此，从周转时间中减去进程实际占用CPU运行的突发时间，剩下的就是进程在就绪队列中等待CPU的时间，即等待时间。 #### Round Robin - Each process gets a small unit of CPU time (timequantum 定额*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. - Timer interrupts every quantum *q* to schedule next process - 每个进程被分配一个小的CPU时间单元，即时间片（time quantum，通常用q表示 ），一般为10 - 100毫秒。当时间片q过去后，进程会被时钟中断抢占，并被添加到就绪队列的末尾。接着，调度器从就绪队列头部选取下一个进程执行，同样分配一个时间片，如此循环。例如，假设有进程P1、P2、P3在就绪队列中，时间片q = 4毫秒，P1先执行4毫秒后被抢占移到队列末尾，接着P2执行4毫秒，然后P3执行4毫秒，之后又轮到P1执行4毫秒，以此类推。 - Performance - $q$ too large $\rightarrow$ FCFS - $q$ too small $\rightarrow$ too much time is spent on context switch - $q$ should be large compared to context switch time - $q$ usually 10ms to 100ms, context switch < 10 usec(微秒) **做题：把 arrival time = 0 计算即可** - 优势 - **公平性**：RR算法确保了每个进程都能在一定时间间隔内获得CPU时间，避免了某些进程长时间得不到执行的情况，体现了公平调度的原则。 - **响应性**：由于进程能够频繁地获得CPU时间片并执行，所以对于交互式系统来说，它能快速响应用户的请求，提升用户体验。 - **不足**：与SJF等一些优化平均等待时间或周转时间的算法相比，RR算法因为频繁的 Context switch 以及可能导致进程不能一次性完成其CPU突发任务，所以平均周转时间通常会较高。例如在处理一些长CPU突发时间的进程时，进程会被多次中断，导致整体完成时间变长，从而增加了周转时间 #### Priority Scheduling - 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) - Two policies - Preemptive: the current process is pre-empted immediately by high priority process - Non-preemptive: the current process finishes its burst first, then scheduler chooses the process with highest priority - 最短作业优先（SJF）算法实际上是优先级调度的一种特殊情况，其中优先级是根据预测的下一个CPU突发时间的倒数来确定的。即预测的CPU突发时间越短，优先级越高。这样可以使得短作业优先得到处理，从而减少平均等待时间。 - 存在的问题：Starvation:low priority processes may never execute - 低优先级的进程可能会因为不断有高优先级进程进入系统而长时间得不到执行机会 - 解决方案：Aging: as time progresses increase the priority of the process - 随着时间的推移，逐渐提高低优先级进程的优先级，使得即使最初优先级较低的进程，在等待足够长的时间后，也能获得较高的优先级，从而有机会执行。例如，每经过一定时间间隔，就将低优先级进程的优先级数值减小（在规定的优先级表示方式下，数值减小意味着优先级提高）。 **做题的时候注意：Run the process with the highest priority. Processes with the same priority run round-robin** （但也要看题目要求）。 #### Multilevel Queue - Ready queue is partitioned into separate queues, e.g.: （不一定是只有两个 queue ，可以有多个） - foreground (interactive 交互processes) - background (batch 批处理 processes) - Process permanently in a given queue (stay in that queue = 进程永久处于某个给定队列中，不会在队列间移动。) - Each queue has its own scheduling algorithm - foreground – RR - background – FCFS - Scheduling must be done between the queues - Fixed priority scheduling - Each queue has a given priority - High priority queue is served before low priority queue - Possibility of starvation - Time slice - Each queue gets a certain amount of CPU time [](https://imgse.com/i/pEBVPlF) - Multilevel feedback queue - 一个进程可以在不同队列之间移动； - 可以通过这种方式考虑老化机制（防止饥饿现象） - 优点：防止饥饿 - 多级反馈队列调度器 - 这是最通用的 CPU 调度算法 - 由以下参数定义： 1. 队列数量 2. 每个队列的调度算法 3. 进程在队列之间移动的策略 4. 何时提升一个进程的队列级别 5. 何时降低一个进程的队列级别 6. 当一个进程需要服务时，它将进入哪个队列 - Example - **三个队列**： 1. **队列 Q0**：采用时间片为 8 毫秒的轮转调度算法（RR）。 2. **队列 Q1**：采用时间片为 16 毫秒的轮转调度算法（RR）。 3. **队列 Q2**：采用先来先服务调度算法（FCFS）。这里是 FCFS 和 RR 相结合的多级反馈队列情况。 - **调度规则**： - 一个新作业进入队列 Q0，在 Q0 中按照先来先服务（FCFS）原则进行调度。 - 当该作业获得 CPU 时，它会被分配 8 毫秒的 CPU 时间。 - 如果该作业在 8 毫秒内没有完成，它将被移动到队列 Q1。 - 在队列 Q1 中： - 作业同样按照先来先服务原则调度，并且会额外获得 16 毫秒的 CPU 时间。 - 如果作业仍然没有完成，它将被抢占 CPU 并移动到队列 Q2，在队列 Q2 中它会一直运行直到完成，但具有较低的优先级。 ### Thread Scheduling - Distinguish between **user-level** and **kernel-level** threads #### For user-level thread In Many-to-one and Many-to-Many model, - **多对一模型（Many - to - one Model）**：多个用户级线程映射到一个内核级线程（轻量级进程 Light-Weigh-Process，LWP）。在这种模型下，**用户级线程的调度由线程库 (thread libraries) 在用户空间完成**，效率较高，但一旦某个线程执行了阻塞操作（如I/O请求），整个进程都会被阻塞，因为所有用户级线程共享同一个内核级线程。 - process-contention scope (PCS) **进程内竞争范围** - **多对多模型（Many - to - many Model）**：多个用户级线程映射到多个内核级线程。线程库负责将用户级线程调度到内核级线程上运行。 #### For kernel-level thread **Kernel threads are scheduled by Kernel onto available CPU** - system-contention scope(SCS) **系统内竞争范围** - competition is among all kernel-level threads from all processes in the system ### Multi-Processor Scheduling The term Multiprocessor now applies to the following system architectures: - Multicore CPUs - Multithreaded cores - NUMA systems #### Symmetric multiprocessing (SMP) 对称多处理 - Definition: Each processor is self scheduling - Two strategies - All threads may be in a common ready queue (a) - Each processor may have its own private queue of threads (b) [](https://imgse.com/i/pEBV7A1) #### Multicore Processors 省流：**多核处理器（Multicore Processors）**：当前趋势是将多个处理器核心集成在同一物理芯片上，这样不仅速度更快，功耗也更低。同时，每个核心上的多线程技术也在发展。当线程访问不在CPU缓存中的内存内容时，会发生内存延迟（memory stall），解决办法是为每个核心配备多个硬件线程，当一个线程出现内存延迟时，切换到其他线程执行。 [](https://imgse.com/i/pEBVbh6) #### Multithreaded Multicore System 以芯片多线程（CMT，如英特尔的超线程技术）为例，在一个四核系统中，若每个核心有2个硬件线程，操作系统会将其视为8个逻辑处理器。调度分为两个层次： - 操作系统决定哪个软件线程在逻辑CPU上运行。 - 每个核心决定哪个硬件线程在物理核心上运行。 #### Multiple-Processor Scheduling –Load Balancing **负载均衡（Load Balancing）**在SMP系统中，为提高效率需使所有CPU保持负载均衡。负载均衡旨在均匀分配工作负载，有两种方式： - 推迁移（Push migration）：周期性检查每个处理器的负载，将任务从过载的CPU推送到负载较轻的CPU。 - 拉迁移（Pull migration）：空闲的CPU从繁忙的CPU中拉取等待的任务。 - **这两种方式通常 Parallel实现。** #### Multiple-Processor Scheduling –Processor Affinity - 当一个线程在某个处理器上运行时，该**处理器的缓存会存储该线程的内存访问信息，即线程对该处理器具有亲和性。** - 负载均衡可能影响处理器亲和性，因为线程可能为平衡负载在处理器间迁移，从而丢失原处理器缓存中的内容。 - **软亲和性（Soft affinity）**：操作系统尝试让线程在同一处理器上运行，但不保证。 - 硬亲和性（Hard affinity）：允许进程指定可运行的处理器集合，内核不会将该进程迁移到其他CPU，即使当前CPU负载很高。 #### NUMA and CPU Scheduling **NUMA与CPU调度**：非统一内存访问（NUMA）系统中，处理器访问本地内存比访问非本地内存更快。若操作系统支持NUMA，会将离CPU最近的内存分配给正在运行的线程，以提高内存访问效率。 ### Real-Time CPU Scheduling Types of challenges: - Soft real-time systems: Critical real-time tasks have the highest priority, but no guarantee as to when tasks will be scheduled (best try only) 关键实时任务具有最高优先级，但不保证任务何时被调度，只是尽力而为。 - Hard real-time systems: a task must be serviced by its deadline (guarantee) #### Event latency - Definition: the amount of time that elapses from when an event occurs to when it is serviced.从事件发生到其得到服务所经过的时间。 - Two types of latencies affect performance - Interrupt latency –time from arrival of interrupt to start of **kernel interrupt service routine(ISR)** that services interrupt - Dispatch latency(调度延迟) –time for scheduler to take current process off CPU and switch to another [](https://imgse.com/i/pEBVL9K) #### Priority-based Scheduling **基于优先级的调度（Priority - based Scheduling）**：对于实时调度，调度器必须支持抢占式、基于优先级的调度。但仅这样只能保证软实时，对于硬实时，还必须具备满足截止期限的能力。实时进程具有周期性需要CPU的特点，有处理时间t、截止期限d和周期p，且$0 ≤ t≤ d≤ p$，周期任务的速率为$1/p$。 [](https://imgse.com/i/pEBVO1O) #### Rate Monotonic Scheduling 根据任务周期的倒数分配优先级，周期越短，优先级越高；周期越长，优先级越低。例如，$P1$每50ms需要运行20ms（$t = 20$，$d = p = 50$），$P2$每100ms需要运行35ms（$t = 35$，$d = p = 100$），则$P1$的优先级高于$P2$。但该算法可能出现错过截止期限的情况，如$P1$每50ms需运行25ms，$P2$每80ms需运行35ms时，$P2$会在80ms时错过截止期限。 #### Missed Deadlines with Rate Monotonic Scheduling 根据截止期限分配优先级，截止期限越早，优先级越高；截止期限越晚，优先级越低。例如，学生在面对多个不同作业截止期限时，可能会采用这种调度方式安排任务。 #### Proportional Share Scheduling 比例共享调度（Proportional Share Scheduling）是一种CPU调度算法，旨在按照一定比例为系统中的各个进程分配CPU时间，以确保每个进程都能获得相对公平的资源份额。下面结合你提供的课件内容来详细介绍： 1. **份额分配机制**：在该调度算法中，系统将CPU时间划分为一定数量的份额（shares）。例如，课件中提到假设\(T = 20\)，则表示总共有20个份额，每一个份额代表5%的CPU时间。每个应用程序会被分配到\(N\)个份额（\(N < T\)），这就保证了该应用程序能获得\(N/T\)比例的总处理器时间。比如，若一个应用程序获得\(N = 5\)个份额，那么它将拥有\(5/20 = 25\%\)的CPU时间。 2. **时间分配特点**：无论应用程序是否使用分配给它的CPU时间，该比例的CPU时间都为其保留。这意味着，即使某个应用程序在某一时刻处于空闲状态，没有使用完分配的CPU时间份额，其他应用程序也不能占用这部分空闲的时间，以保证分配的公平性和稳定性。 最后修改：2025 年 03 月 24 日 © 允许规范转载 打赏 赞赏作者 支付宝微信 赞 1 如果觉得我的文章对你有用，请随意赞赏
