📚 Operating System Process Scheduling and Concurrent Programming | 操作系统进程调度与并发编程
This article, drawing on Pearson ActiveLearn resources (OPS combined 007), examines the core concepts of process scheduling and concurrent programming required for the Edexcel A-Level Computer Science specification. It covers process states, scheduling algorithms, concurrency issues and synchronisation mechanisms, equipping you with the knowledge to tackle both theory and practical programming tasks.
本文基于Pearson ActiveLearn资源(OPS combined 007),深入探讨Edexcel A-Level计算机科学大纲中要求的进程调度与并发编程核心概念。内容涵盖进程状态、调度算法、并发问题及同步机制,帮助读者掌握应对理论考试与实践编程任务所需的知识。
1. Introduction to Processes and Threads | 进程与线程简介
A process is a program in execution, consisting of the program code, current activity, and allocated resources such as memory and file handles. Each process has its own address space.
进程是正在执行的程序,由程序代码、当前活动以及分配的内存和文件句柄等资源组成。每个进程拥有自己独立的地址空间。
A thread is the smallest unit of execution within a process. Multiple threads within the same process share the same address space and resources, enabling efficient communication but also requiring careful synchronisation.
线程是进程内部的最小执行单元。同一进程内的多个线程共享相同的地址空间和资源,这使得通信高效,但也需要谨慎的同步处理。
In modern operating systems, processes are managed by the kernel, allowing multi-tasking and improved CPU utilisation through concurrent execution of threads.
在现代操作系统中,进程由内核管理,通过线程的并发执行实现多任务并提高CPU利用率。
2. Process States and Transitions | 进程状态与转换
A process can be in one of several states: New, Ready, Running, Blocked (Waiting), and Terminated. The state diagram illustrates how a process moves between these states under the control of the OS scheduler.
进程可能处于以下几种状态之一:新建、就绪、运行、阻塞(等待)和终止。状态图显示了进程在操作系统调度器的控制下如何在各状态之间转换。
When a process is created, it enters the New state. Once admitted by the long-term scheduler, it moves to the Ready queue. The short-term scheduler dispatches a Ready process to the Running state when a CPU becomes available.
进程创建后进入新建状态。一旦被长程调度器接纳,便移入就绪队列。短程调度器在CPU可用时将某个就绪进程分派到运行状态。
If a running process needs to wait for an I/O operation or a resource, it moves to the Blocked state. After the event occurs, it returns to the Ready state. A process terminates when it finishes execution or is killed.
若运行中的进程需要等待I/O操作或资源,则转为阻塞状态。事件发生后,返回就绪状态。进程执行完成或被终止时进入终止状态。
| State | Meaning |
|---|---|
| New | Process created but not yet admitted |
| Ready | Ready to run, waiting for CPU |
| Running | Currently executing on a CPU |
| Blocked | Waiting for I/O or an event to complete |
| Terminated | Execution finished or process killed |
3. Scheduling Algorithms: FCFS and SJF | 调度算法:先来先服务和最短作业优先
First-Come, First-Served (FCFS) executes processes in the order they arrive. It is simple to implement but can cause the convoy effect, where short processes wait behind long ones, increasing average waiting time.
先来先服务按进程到达的顺序执行。实现简单,但可能导致护送效应,即短作业排在长作业之后,致使平均等待时间增加。
Shortest Job First (SJF) selects the process with the shortest expected burst time next. It minimises average waiting time but requires knowledge of future burst times, which is rarely available. Preemptive SJF is known as Shortest Remaining Time First (SRTF).
最短作业优先选择预期CPU脉冲时间最短的进程。它最小化平均等待时间,但需要预知未来的脉冲时间,这在实际中难以获得。抢占式SJF称为最短剩余时间优先。
Non-preemptive SJF cannot interrupt a running process, while SRTF can preempt if a new process arrives with a shorter burst remaining.
非抢占式SJF不能中断正在运行的进程,而SRTF可在新到达进程的剩余时间更短时进行抢占。
Average turnaround time = Σ (completion time – arrival time) ÷ number of processes
平均周转时间 = Σ(完成时间 – 到达时间) ÷ 进程数目
4. Round Robin and Priority Scheduling | 时间片轮转与优先级调度
Round Robin (RR) is a preemptive algorithm designed for time-sharing systems. Each process gets a small unit of CPU time (time quantum). If a process does not finish within its quantum, it returns to the tail of the ready queue.
时间片轮转是一种为分时系统设计的抢占式算法。每个进程获得一小段CPU时间(时间片)。若进程未在该时间片内完成,则返回到就绪队列尾部。
The choice of quantum is critical: too large and RR behaves like FCFS; too small and context switch overhead degrades performance.
时间片的选择至关重要:过大则轮转退化为先来先服务;过小则上下文切换开销降低性能。
Priority scheduling assigns a priority to each process. The CPU is allocated to the process with the highest priority (smallest number usually). Both preemptive and non-preemptive variants exist. A major problem is starvation, which can be solved by aging (gradually increasing the priority of waiting processes).
优先级调度为每个进程分配一个优先级。CPU分配给优先级最高(通常数值最小)的进程。存在抢占式和非抢占式两种变体。其主要问题是饥饿,可通过老化(逐渐提高等待进程的优先级)来解决。
5. Multilevel Queue and Multilevel Feedback Queue | 多级队列与多级反馈队列
Multilevel Queue scheduling partitions the ready queue into several separate queues, e.g., foreground (interactive) and background (batch). Each queue has its own scheduling algorithm. A fixed-priority preemptive order between queues prevents processes in lower-priority queues from running unless higher queues are empty.
多级队列调度将就绪队列划分为多个独立队列,例如前台(交互)和后台(批处理)。每个队列拥有自己的调度算法。队列间采用固定优先级抢占顺序,只有高优先级队列为空时,低优先级队列中的进程才能运行。
Multilevel Feedback Queue (MLFQ) allows processes to move between queues based on their CPU usage. Typically, a new process starts at the highest priority. If it consumes its quantum, it moves to a lower queue. This favours short interactive processes and gradually demotes CPU-bound ones, balancing responsiveness and throughput.
多级反馈队列允许进程根据CPU使用情况在队列间迁移。通常新进程从最高优先级开始。若用完时间片,则降到较低队列。这有利于短交互式进程,并逐渐将CPU密集型进程降级,平衡响应速度与吞吐量。
6. Concurrent Programming Basics | 并发编程基础
Concurrent programming involves executing multiple instruction sequences (threads or processes) that overlap in time. It leads to better resource utilisation and responsiveness but introduces challenges such as race conditions, deadlocks and data inconsistency.
并发编程涉及在时间上重叠执行多个指令序列(线程或进程)。它能提高资源利用率和响应速度,但也带来了竞争条件、死锁和数据不一致等挑战。
Threads within a single process share global variables and heap memory. Synchronisation mechanisms are needed to coordinate access to shared data. Without proper control, two threads may simultaneously read and write shared data, causing errors that are hard to reproduce.
同一进程内的线程共享全局变量和堆内存。需要同步机制来协调对共享数据的访问。若缺乏适当控制,两个线程可能同时读写共享数据,导致难以复现的错误。
Testing and debugging concurrent programs is more difficult because execution order is non-deterministic and depends on timing.
测试和调试并发程序更为困难,因为执行顺序是非确定性的,并且依赖于时序。
7. Race Conditions and Critical Sections | 竞争条件与临界区
A race condition occurs when the outcome of a program depends on the relative timing or interleaving of threads. For example, two threads incrementing a shared counter without synchronisation may produce an incorrect final value because the read-modify-write sequence is not atomic.
当程序的结果取决于线程的相对时序或交错时,就会发生竞争条件。例如,两个线程在没有同步的情况下递增共享计数器,可能产生错误的最终值,因为读-改-写序列并不是原子操作。
A critical section is a segment of code that accesses a shared resource and must not be executed by more than one thread at a time. Proper synchronisation ensures mutual exclusion, so that only one thread enters its critical section at any moment.
临界区是访问共享资源的一段代码,不能同时由多个线程执行。正确的同步可确保互斥,即任何时刻仅一个线程进入其临界区。
Solutions must satisfy three requirements: mutual exclusion, progress (a process outside the critical section should not block others), and bounded waiting (no starvation).
解决方案必须满足三项要求:互斥、进展(未处于临界区的进程不应阻塞其他进程)以及有限等待(无饥饿)。
8. Mutexes and Semaphores | 互斥锁与信号量
A mutex (mutual exclusion lock) is a binary lock used to protect critical sections. Before entering the critical section, a thread acquires the mutex; after exiting, it releases the lock. Only the thread that locked the mutex can unlock it.
互斥锁是用于保护临界区的二进制锁。进入临界区之前,线程获取互斥锁;退出之后,释放锁。只有加锁的线程才能解锁。
A semaphore is a generalised synchronisation primitive that can count beyond binary states. It supports two atomic operations: wait (P) decrements the semaphore value, blocking if the value becomes negative; signal (V) increments it, potentially unblocking a waiting thread. Counting semaphores can manage a pool of identical resources.
信号量是一种更通用的同步原语,可以计数超过二进制状态。它支持两个原子操作:wait(P)减少信号量值,若值为负则阻塞;signal(V)增加值,可能唤醒一个等待的线程。计数信号量可用于管理多个相同资源的池。
In Edexcel pseudocode, typical P(decrement) and V(increment) functions are used to illustrate semaphore-based solutions. Care must be taken to avoid deadlock when multiple semaphores are involved.
在Edexcel伪代码中,常用P(递减)和V(递增)函数来演示基于信号量的解决方案。涉及多个信号量时,须小心避免死锁。
9. Deadlock: Conditions and Prevention | 死锁:条件与预防
Deadlock is a situation where two or more processes are unable to proceed because each holds a resource and waits for a resource held by another. The four necessary conditions for deadlock are: mutual exclusion, hold and wait, no preemption, and circular wait.
死锁是指两个或更多进程因各自持有资源并等待对方持有的资源而无法继续执行的情况。死锁的四个必要条件为:互斥、持有并等待、不可抢占以及循环等待。
To prevent deadlock, at least one condition must be broken. For instance, requiring processes to request all resources at once breaks hold and wait; allowing resource preemption breaks the no-preemption condition; imposing a total ordering on resource acquisition prevents circular wait.
为预防死锁,必须打破至少一个条件。例如,要求进程一次性请求所有资源可打破持有并等待;允许资源抢占可打破不可抢占条件;对资源获取施加全序可防止循环等待。
Deadlock avoidance uses additional information about future resource needs; the Banker’s algorithm is a classic example. Deadlock detection allows the OS to recover by terminating processes or preempting resources.
死锁避免利用关于未来资源需求的额外信息;银行家算法是典型例子。死锁检测使操作系统可通过终止进程或抢占资源进行恢复。
10. The Producer-Consumer Problem | 生产者-消费者问题
The producer-consumer problem is a classic synchronisation challenge where one or more producer threads generate data and place it into a fixed-size buffer, while consumer threads remove and process that data. The producer must wait when the buffer is full; the consumer must wait when the buffer is empty.
生产者-消费者问题是一个经典的同步挑战,其中一个或多个生产者线程生成数据并放入固定大小的缓冲区,而消费者线程取出并处理这些数据。当缓冲区满时,生产者必须等待;当缓冲区为空时,消费者必须等待。
Using semaphores, one common solution employs three semaphores: mutex (binary, for buffer access), empty (counting, initialised to buffer size) and full (counting, initialised to 0). The producer waits on empty, acquires mutex, inserts the item, releases mutex, and signals full. The consumer waits on full, acquires mutex, removes an item, releases mutex, and signals empty.
使用信号量的一种常见解决方案采用了三个信号量:mutex(二进制,用于缓冲区访问)、empty(计数,初始化为缓冲区大小)和full(计数,初始化为0)。生产者等待empty,获取mutex,插入数据项,释放mutex,然后signal full。消费者等待full,获取mutex,移除数据项,释放mutex,然后signal empty。
This pattern prevents race conditions and ensures that producers do not overwrite full slots and consumers do not read empty slots. Variants of this problem appear in many real-world concurrent systems, such as print spoolers or message queues.
这种模式防止了竞争条件,并确保生产者不会覆盖已满的槽位,消费者不会读取空槽位。该问题的变体出现在许多实际并发系统中,如打印后台处理程序或消息队列。
11. Key Terminology and Exam Tips | 关键术语与考试技巧
Be precise when defining terms such as ‘process’, ‘thread’, ‘mutual exclusion’ and ‘starvation’. Use the official Edexcel definitions where available, and support explanations with clear diagrams or pseudocode examples in exam responses.
定义术语时务必准确,如’进程’、’线程’、’互斥’和’饥饿’。尽量使用Edexcel官方定义,并在考试答案中用清晰的图表或伪代码示例辅助说明。
When comparing scheduling algorithms, reference turnaround time, waiting time, and response time. State the strengths and weaknesses of each algorithm concisely; for example, ‘SJF gives minimum average waiting time but requires knowledge of burst times’.
在比较调度算法时,要提及周转时间、等待时间和响应时间。简明地陈述每种算法的优缺点;例如,’SJF可提供最短平均等待时间,但需要预知CPU脉冲时间’。
For concurrency questions, always identify the critical section and show how mutual exclusion is achieved. Describe potential outcomes if synchronisation is omitted, and be prepared to trace semaphore values step by step.
对于并发问题,务必识别临界区并说明如何实现互斥。描述省略同步机制可能导致的后果,并准备好逐步追踪信号量的值。
Practise writing algorithms using pseudocode that includes P() and V() operations on semaphores, and mutex lock/unlock pairs to reinforce understanding of synchronisation patterns.
通过编写包含信号量P()和V()操作以及互斥锁加解锁对的伪代码算法进行练习,以加深对同步模式的理解。
Finally, remember that scheduling and concurrency topics often appear in longer written questions and practical programming scenarios. Strengthen your skills by simulating scheduling on sample process sets and implementing small multi-threaded programs in a language like Python or Java.
最后,请记住调度和并发主题经常出现在较长的书面题和实际编程场景中。通过对示例进程集合进行调度模拟,并使用Python或Java等语言编写小型多线程程序来强化技能。
Published by TutorHao | Computer Science Revision Series | aleveler.com
更多咨询请联系16621398022（同微信）
屏轩国际教育cambridge primary/secondary checkpoint, cat4, ukiset,ukcat,igcse,alevel,PAT,STEP,MAT, ibdp,ap,ssat,sat,sat2课程辅导，国外大学本科硕士研究生博士课程论文辅导Cancel reply