Tema 1 · Introducción a la Programación de Sistemas y a la Programación Concurrente
系统编程与并发编程导论 · 逐页逐句双语讲义

Tema 1: Introducción a la Programación de Sistemas y a la Programación Concurrente · SCTR
49 页原版 PDF 一页不落 · 西语原句逐字照抄 + 中文一句一译
怎么用这份讲义

一、封面与目录

p.1–p.2
p.1

Portada · 封面

▸ 原页截图 p.1 原讲义第 1 页

Sistemas Concurrentes y de Tiempo Real

并发与实时系统

Grado en Ingeniería Telemática

远程通信工程(Telemática)本科专业

Tema 1: Introducción a la Programación de Sistemas y a la Programación Concurrente

主题 1:系统编程与并发编程导论

这是整份讲义的第一页,只有封面信息,没有教学内容。全篇页号以页号胶囊(p.1…p.49)为准——它等于 PDF 的物理页序;本页封面上没有印页码,从 p.2 起幻灯片右下角才出现 2、3、4… 的编号,两者一致。
p.2

Índice de contenidos · 目录

▸ 原页截图 p.2 原讲义第 2 页

Índice de contenidos

目录

• Programación de sistemas

• 系统编程

• Lenguajes para programación de sistemas

• 系统编程所用的语言

• Gestión de actividades concurrentes: procesos y eventos

• 并发活动的管理:进程与事件

• De la programación secuencial a la programación concurrente

• 从顺序编程到并发编程

• Beneficios y usos de la programación concurrente

• 并发编程的收益与用途

• Problemas de la programación concurrente:

• 并发编程的问题:

– Instrucciones atómicas

– 原子指令

– Sección crítica

– 临界区

– Exclusión mutua

– 互斥

目录第 5 条写的是「Beneficios y usos…」,但正文对应那一页(p.33)标题已经改成「Motivación」——内容一致、措辞不同。答题时按实质答(提升处理器性能、利用多处理器、对天然并发系统建模、获得时间收益),别因为标题对不上而慌。
这一页就是全章骨架:4 大块——系统编程 → 语言 → 并发活动(进程/事件)→ 并发编程(含三大问题)。简答题常要求你「按目录复述本章结构」,背下这 6 条即可。
p.3

Programación de Sistemas · 系统编程:与应用编程的分界

▸ 原页截图 p.3 原讲义第 3 页

El concepto de programación de sistemas tiene sentido frente al de programación de aplicaciones

系统编程这个概念是相对于应用编程而言才有意义的

En la programación de aplicaciones, el objetivo es producir software para proporcionar servicios al usuario (por ej. un procesador de textos)

在应用编程中,目标是生产软件,为用户提供服务(例如一个文字处理软件)

En la programación de sistemas el software proporciona servicios al hardware, al sistema operativo o a otros componentes del sistema

在系统编程中,软件服务于硬件、操作系统或系统的其他组件

必考对比:应用编程「给用户提供服务」,系统编程「给硬件 / 操作系统 / 其他系统组件提供服务」。一句话判据——你的程序是被人直接用,还是被机器、OS 或别的软件调用。
口诀:应用面向人,系统面向机。用户拿服务,系统喂硬件。
p.4

Programación de Sistemas · 系统编程:抽象层次更低

▸ 原页截图 p.4 原讲义第 4 页

En la programación de sistemas el grado de abstracción con respecto al hardware y la forma en la que se ejecutan las aplicaciones es menor

在系统编程中,相对于硬件的抽象程度,以及应用程序的执行方式,都更低层

Un ejemplo de programación de sistemas es la programación de sistemas empotrados/embebidos con características de tiempo real

系统编程的一个例子是编写具有实时特性的嵌入式系统

En estos sistemas los computadores forman parte de otros sistemas más complejos, a los que controlan

在这类系统中,计算机是更复杂系统的一部分,并对那些系统进行控制

「grado de abstracción … es menor」是高频填空:系统编程的抽象层次更低(不是更高)。举的例子固定答「嵌入式 / 实时系统」。
注意原文把两个同义词并排写成「empotrados/embebidos」,西语里两者都指 embedded,考试写哪个都对;但别写成「empotrado」以外的拼法。
p.5

Programación de Sistemas · 让系统编程变「特殊」的因素

▸ 原页截图 p.5 原讲义第 5 页

Algunas características que hacen a la programación de sistemas “especial”:

让系统编程显得「特殊」的一些特征:

– Se interacciona con el mundo físico a través del hardware

– 通过硬件与物理世界交互

– En esta interacción hay que tener en cuenta factores como:

– 在这种交互中必须考虑如下因素:

• La fiabilidad y la criticidad de los sistemas. Los sistemas deben ser predecibles

• 系统的可靠性与关键性。系统必须是可预测的

• Los recursos (memoria, almacenamientos, comunicaciones,..) son limitados y hay que tenerlos en cuenta al programar

• 资源(内存、存储、通信……)是有限的,编程时必须把它们考虑进去

• El tiempo físico

• 物理时间

– Los ordenadores son inherentemente secuenciales y en el tiempo discreto

– 计算机本质上是顺序的,工作在离散时间中

– En el mundo real, el tiempo es continuo y existe la simultaneidad de eventos

– 在真实世界里时间是连续的,并且存在事件的同时性

– La interacción con el entorno esta sujeta a restricciones de tiempo real

– 与环境的交互受实时约束的限制

原文笔误:「esta sujeta」应为「está sujeta」(缺重音,这里作动词「处于」)。讲义逐字保留原文,但考试写作文时请写 está。
三件套记忆:可靠 + 资源 + 时间——系统要可预测(fiabilidad/criticidad),资源有限(memoria/almacenamiento/comunicaciones),时间特殊(离散机器 vs 连续世界 + 实时约束)。
常考「为什么系统编程特殊」:能从三方面各举一例即可拿满分——必须可预测、资源受限、时间约束(还有与物理世界交互)。
p.6

Programación de Sistemas · 如何获得与环境的交互:OS 与实时 OS

▸ 原页截图 p.6 原讲义第 6 页

¿Cómo conseguimos esa interacción con el entorno?

我们怎样获得这种与环境的交互?

• Los Sistemas Operativos controlan el hardware y nos proporcionan abstracciones de más alto nivel

• 操作系统控制硬件,并为我们提供更高层的抽象

– Gestionan aspectos como el tiempo, la concurrencia, etc., para que sea más fácil

– 它们管理时间、并发等方面,使编程更容易

– En sistemas donde el tiempo es un factor crítico, no nos vale cualquier sistema operativo y tendremos que utilizar Sistemas Operativos de Tiempo Real

– 在时间成为关键因素的系统里,随便一个操作系统都不行,必须使用实时操作系统

• En ocasiones tendremos que interactuar con el hardware directamente.

• 有时我们不得不直接与硬件交互。

– En algunos sistemas empotrados con recursos muy limitados (el sistema operativo no cabe) o en el caso de que trabajemos en las primeras capas de un sistema operativo.

– 在一些资源极其有限的嵌入式系统中(操作系统根本装不进去),或者当我们工作在操作系统的最底层时。

两个「必须绕过 OS」的理由是标准考点:①嵌入式系统资源太少、OS 塞不进去;②工作在操作系统的头几层(驱动 / 内核)。
时间关键 → RTOS(Sistemas Operativos de Tiempo Real);资源太小 → 裸机。两句口诀:时间要紧上实时,装不下就裸奔。
p.7

Lenguajes para Programación de Sistemas · 系统编程语言及特征

▸ 原页截图 p.7 原讲义第 7 页

La mayor parte de los lenguajes para programación de sistemas son de bajo nivel.

用于系统编程的语言大多是低层语言。

Algunos de los más utilizados

最常用的一些是

– C, C++, Rust, Ada

– C、C++、Rust、Ada

Algunas características:

一些特征:

– Acceso a memoria física, sin recolección de basura direcciones absolutas, bits sin signo, tipos de memoria (ROM, RAM, flash,…)

– 可访问物理内存,没有垃圾回收,可用绝对地址、无符号位、各类存储器(ROM、RAM、flash……)

– Posibilidad de acceso al hardware directamente, o bien a través de interfaces de acceso al sistema operativo (APIs)

– 既可以直接访问硬件,也可以通过访问操作系统的接口(应用程序接口)访问

– Soporte de eventos y/o concurrencia

– 支持事件和/或并发

– Eficientes y con capacidad de análisis de consumo de recursos (predecibles)

– 高效,并且能够分析资源消耗(即可预测)

原文在「sin recolección de basura」与「direcciones absolutas」之间漏了逗号,读作「没有垃圾回收、可用绝对地址」,不是「没有绝对地址的垃圾回收」。抄写题目时补上逗号更清楚;「bits sin signo」指无符号位域,不是「没有符号的位」。
高频多选:C、C++、Rust、Ada 四个名字,问「哪个不是系统编程常用语言」时别选错;再问特征,答「可访问物理内存 + 无 GC + 可直接访问硬件 + 支持事件/并发 + 可预测」。
p.8

Lenguajes para Programación de Sistemas · 交叉编译:host 与 target

▸ 原页截图 p.8 原讲义第 8 页

Con frecuencia los sistemas de desarrollo son distintos de los sistemas en los que se va a ejecutar la aplicación final

通常开发系统与最终运行应用程序的系统并不是同一个

Los compiladores que se utilizan se denominan compiladores cruzados y generan código para plataformas distintas en las que se ejecutan.

所使用的编译器称为交叉编译器,它们生成的是给与自身不同的平台运行的代码。

– La máquina en la que se desarrolla se denomina host y en la que se ejecuta target

– 开发所用的机器称为宿主机,运行所用的机器称为目标机

– La depuración se realiza parcialmente en el host utilizando emuladores y simuladores del hardware

– 调试部分地在宿主机上用硬件的模拟器和仿真器完成

– La depuración final es compleja, porque en ocasiones el target no tiene interfaces de entrada/salida

– 最终的调试很复杂,因为有时目标机根本没有输入/输出接口

方向别搞反:host 上开发,target 上运行;交叉编译器「在 host 跑、产出 target 的代码」。口诀:宿主养、目标跑。
emulador(模拟器,用软件模拟整台机器/指令集)与 simulador(仿真器,模拟硬件行为/时序)在西语里常被混用,但原文并列出现,答「两者都在 host 上用来替代真实硬件」即可,不要只说一个。
p.9

Lenguajes para Programación de Sistemas · 时间的处理:Java 两种时钟

▸ 原页截图 p.9 原讲义第 9 页

Tratamiento del tiempo:

对时间的处理:

– Suelen existir primitivas para acceso al reloj del sistema y para expresar retrasos en la ejecución del programa

– 通常会有原语用于访问系统时钟,以及表达程序执行中的延迟

– En Java:

– 在 Java 中:

• System.currentTimeMillis(), reloj del sistema, se ve afectado por los cambios de otros comandos (por ejemplo, al cambiar la fecha)

• System.currentTimeMillis(),即系统时钟,会受其他命令改动的影响(例如修改日期时)

• System.nanoTime(), reloj absoluto desde el comienzo de la ejecución de la máquina virtual

• System.nanoTime(),从虚拟机开始执行算起的绝对时钟

– Ejemplo: ¿Cómo medir el tiempo que tarda en ejecutarse un trozo de código?

– 例子:怎样测量一段代码执行所花的时间?

几乎必考的一道选择题:测「一段代码耗时」应该用 nanoTime(),不能用 currentTimeMillis()——后者会因系统时钟被改(改日期、NTP 校时)而跳变。
注意 nanoTime() 不是「当前时间的纳秒表示」,它只有相对意义(JVM 启动以来的计时),不能拿它算日期。
p.10

Lenguajes para Programación de Sistemas · 测量耗时的代码与三个问题

▸ 原页截图 p.10 原讲义第 10 页
long start = System.nanoTime();
// Código a monitorizar
double elapsedTimeInSec = (System.nanoTime() - start) * 1.0e-9

long start = System.nanoTime();

long start = System.nanoTime();(记录起始时刻)

// Código a monitorizar

// 要监测的那段代码

double elapsedTimeInSec = (System.nanoTime() - start) * 1.0e-9

double elapsedTimeInSec = (System.nanoTime() - start) * 1.0e-9(纳秒差乘 10-9 得秒)

Problemas:

问题:

Interferencia de otros programas, procesos

其他程序、进程的干扰

Gestión de la memoria. Las variables pueden cambiar de sitio (memoria principal, cache,….) sin nuestro control

内存管理。变量可能在主存、cache 等之间换位置(memoria principal, cache,…),完全不受我们控制

Pero necesitamos conocer el peor tiempo: Lenguajes para Sistemas de Tiempo Real

但我们真正需要知道的是最坏时间:这就是实时系统语言要解决的问题

考点是「为什么实测耗时说明不了问题」:①别的进程干扰;②变量在内存/缓存间迁移不可控。所以实时系统要看 peor tiempo(最坏执行时间 WCET),而不是平均值。
公式记法:耗时 = 结束 nanoTime − 起始 nanoTime,再乘 1.0e-9 换成秒。口诀:差一差,乘负九次方。
p.11

Lenguajes para Programación de Sistemas · 内存管理:为什么要自己控地址

▸ 原页截图 p.11 原讲义第 11 页

La gestión de memoria:

内存管理:

– En los lenguajes actuales la gestión de la memoria se ha automatizado mucho

– 在当今的语言中,内存管理已经高度自动化

– No sabemos físicamente dónde están nuestras variables u objetos

– 我们并不知道自己的变量或对象在物理上位于哪里

– Pueden cambiar de sitio de forma transparente y son eliminados cuando no van a ser utilizados de nuevo

– 它们会不可见地换位置,并在不再被使用时被回收

• En la programación de sistemas necesitamos tener un mayor control

• 在系统编程中,我们需要更强的控制力

• Por ej. el hardware se accede a través de registros que se encuentran en direcciones físicas de memoria fijas

• 例如,硬件是通过位于固定物理内存地址上的寄存器来访问的

• Ese registro habrá que mapearlo a una variable de un programa para poderlo manipular

• 必须把这个寄存器映射成程序里的一个变量,才能操作它

这页是 p.12 那段 C 代码的铺垫:考点是「访问硬件 = 把固定物理地址上的寄存器映射成变量」,而且这个映射必须绕过语言的自动内存管理(GC 会把你的映射当成垃圾收掉)。
连接前后页:p.11 说「需要更强控制」,p.12 立刻给出 C 的位域 struct + #define 绝对地址,p.13 再讲这种手动管理的代价(不可预测、碎片)。
p.12

Un ejemplo en C · C 语言实例:位域 + 绝对地址映射

▸ 原页截图 p.12 原讲义第 12 页
typedef struct {
    uint8_t Denable : 1;  // bit 0
    uint8_t Dfun    : 2;  // bits 1-2
    uint8_t Unit    : 3;  // bits 3-5
    uint8_t Busy    : 1;  // bit 6
    uint8_t Error   : 1;  // bit 7
} Reg_Cont;
// Mapeo del registro a una dirección absoluta
#define REG_CONTROL_ADDRESS ((volatile Reg_Cont*) 0x177566)
Reg_Cont tmp = {
    .Denable = 1,
    .Dfun    = 0,  // Por ejemplo, Read = 0
    .Unit    = 4,
    .Busy    = 0,
    .Error   = 0   // None = 0
};
*REG_CONTROL_ADDRESS = tmp;

typedef struct { uint8_t Denable : 1; uint8_t Dfun : 2; uint8_t Unit : 3; uint8_t Busy : 1; uint8_t Error : 1; } Reg_Cont;

用位域(bit-field)把 8 位的控制寄存器拆成 5 个字段:使能 1 位、功能 2 位、单元 3 位、忙 1 位、错误 1 位,整体叫 Reg_Cont。

// Mapeo del registro a una dirección absoluta

// 把该寄存器映射到一个绝对地址

#define REG_CONTROL_ADDRESS ((volatile Reg_Cont*) 0x177566)

#define REG_CONTROL_ADDRESS ((volatile Reg_Cont*) 0x177566)——把常量 0x177566 强制转成指向 Reg_Cont 的 volatile 指针。

Reg_Cont tmp = { .Denable = 1, .Dfun = 0, .Unit = 4, .Busy = 0, .Error = 0 };

先在一个临时结构体里按字段填好要写的值(使能=1、功能=0、单元=4、忙=0、错误=0)。

// Por ejemplo, Read = 0

// 例如 Read = 0(功能字段取 0 表示读)

// None = 0

// None = 0(错误字段取 0 表示无错误)

*REG_CONTROL_ADDRESS = tmp;

*REG_CONTROL_ADDRESS = tmp;——把整个结构体一次写入那个绝对地址,于是真正写进了硬件寄存器。

R. Control · Denable · Funcion · Unidad · Busy · Error

图注:一个 8 位控制寄存器由 Denable(使能)、Funcion(功能)、Unidad(单元)、Busy(忙)、Error(错误)五段组成。

必算:位域宽度之和 1+2+3+1+1 = 8 位 = 1 字节;各字段起始位分别是 bit 0 / 1–2 / 3–5 / 6 / 7。答题时要能画出这条「8 格横条」。
关键字 volatile 不能省:它告诉编译器「这块内存可能被硬件随时改」,禁止把读写优化掉或缓存到寄存器里。少了它,*REG_CONTROL_ADDRESS = tmp 可能被优化成空操作——这是本页最容易丢分的点。
口诀:位域切片,指针落地,volatile 保命。struct 画格子,宏给绝对地址,volatile 防优化。
p.13

Gestión de memoria · 更多问题:不可预测与碎片

▸ 原页截图 p.13 原讲义第 13 页

Más problemas:

还有更多问题:

– Gestión de memoria no predecible

– 内存管理不可预测

• El esfuerzo para encontrar un hueco depende del estado previo de la memoria

• 找一个空洞要花多大功夫,取决于内存之前的状态

– Fragmentación

– 碎片

• Si se tiene un hueco de tamaño N y se crea un objeto de tamaño M, con m<N se tendrá un fragmento de tamaño M-N

• 如果有一个大小为 N 的空洞,要创建一个大小为 M 的对象,且 m<N,就会剩下一个大小为 M-N 的碎片

• Después de un tiempo de ejecución, la mayor parte de la memoria son huecos (recolección de basura)

• 运行一段时间后,内存的大部分都变成了空洞(垃圾回收来收拾)

– Las direcciones correspondientes al hardware no se pueden recolectar

– 与硬件对应的地址是不能被回收的

Espacio libre · Nuevo objeto · Objeto antiguo

图注:空闲空间、新对象、旧对象——新对象被放进空洞后,剩下的那块就是碎片。

原文勘误:这里写的是「un fragmento de tamaño M-N」,但既然 m<N(更准确地说 M<N),剩下的碎片应该是 N-M。老师口述时也是「N 减 M」。抄答案时用 N−M 并注明原文如此。
考点三连:①内存管理不可预测(依赖先前状态);②碎片 = 空洞被小对象占用后的余量;③硬件映射的地址不能被 GC 回收——这是「有 GC 的语言做不了系统编程」的根本原因。
口诀:找洞看历史,放小留碎片,硬件不许收。
p.14

Lenguajes para Programación de Sistemas · 为什么是 C/C++,Ada 与 Rust 的定位

▸ 原页截图 p.14 原讲义第 14 页

Las anteriores limitaciones hacen que no todos los lenguajes puedan ser utilizados en la programación de sistemas

上述限制使得并非所有语言都能用于系统编程

Los más utilizados con diferencia son C y C++, que permiten acceder a la memoria física y no tienen recolector de basura

遥遥领先的最常用语言是 C 和 C++:它们允许访问物理内存,而且没有垃圾回收器

– Son lenguajes extremadamente propensos a errores

– 它们极其容易出错

– Están impuestos por la industria

– 它们是产业界强制的事实标准

Lenguajes como Ada, de más alto nivel y específicamente diseñados para programación de sistemas han tenido un impacto limitado y sólo se usan en algunos sectores, como el aeroespacial

像 Ada 这样层次更高、专门为系统编程设计的语言,影响却很有限,只用于航空航天等少数领域

Rust es la alternativa más reciente y está teniendo muy buena acogida

Rust 是最近出现的替代方案,并且很受欢迎

三句话结论,考试逐条背:C/C++ 用得最多(能访问物理内存、无 GC,但易错、被产业绑定);Ada 更高层、为系统编程而设计,但影响有限(航空航天);Rust 是新兴替代方案、接受度很好。
「propensos a errores」是缺点,但原文把它和「impuestos por la industria」并列成 C/C++ 的两个事实——不要误答成「C 是安全语言」。
口诀:C 老、Ada 贵、Rust 新——老而不倒靠产业,贵而少用限航天,新而受宠看未来。
p.15

Gestión de actividades concurrentes: Eventos y Procesos · 并发活动管理开场

▸ 原页截图 p.15 原讲义第 15 页

Como consecuencia de la interacción con el mundo físico, la programación de sistemas tiene que hacer frente a interacciones con el entorno que pueden ser concurrentes, simultáneas o de las que simplemente desconocemos el orden.

由于要与物理世界交互,系统编程必须应对与环境的交互——这些交互可能是并发的、同时的,或者我们根本不知道它们的先后顺序。

Un ejemplo sencillo: gestión de la interacción con un reloj inteligente

一个简单的例子:管理与一块智能手表的交互

这一页是新一章的标题页,只有两句引入。原文右下角页码 15,标题占两行(Gestión de actividades concurrentes: / Eventos y Procesos),接下来 p.16–p.18 用智能手表的例子把「并发」和「事件」两种抽象讲清楚。
名词辨析常考:concurrente(并发,概念上同时)、simultáneo(同时,物理上真的同一时刻)、orden desconocido(顺序未知)。三者是本章反复出现的判据。
p.16

Gestión de actividades concurrentes: Eventos y Procesos · 智能手表接口

▸ 原页截图 p.16 原讲义第 16 页

Supongamos un paquete en java, que nos proporciona la siguiente interfaz:

假设有一个 Java 包,向我们提供下面这个接口:

public interface SmartWatch {
    boolean isTapDetected();
    boolean isSwipeUpDetected();
    boolean isSwipeDownDetected();
    void showTime();
    void showNotifications();
    void showWeather();
}

public interface SmartWatch { boolean isTapDetected(); boolean isSwipeUpDetected(); boolean isSwipeDownDetected(); void showTime(); void showNotifications(); void showWeather(); }

接口 SmartWatch 一共 6 个方法:3 个「检测」类(点按、上滑、下滑,返回 boolean)和 3 个「显示」类(时间、通知、天气,返回 void)。

¿Cómo lo hacemos?

那我们怎么做呢?

这 6 个方法就是后续所有讨论的素材:3 个输入(tap / swipe up / swipe down)是事件,3 个输出是动作。考题常问「哪些方法代表事件源,哪些代表动作」。
注意接口只提供「检测」和「显示」,没有任何「等待」或「订阅」方法——这正是 p.17 那个 while(true)+sleep 轮询方案别扭的根源。
p.17

Gestión de actividades concurrentes: Eventos y Procesos · 轮询方案及其四个疑问

▸ 原页截图 p.17 原讲义第 17 页
public class WatchExample {
  public void start() {
    SmartWatch watch = SmartWatchManager.getWatch();
    while (true) {
      watch.showTime();
      try {
        Thread.sleep(1000);
      } catch (InterruptedException e) {
        break;
      }
      if (watch.isTapDetected()) {
        watch.showWeather();
      } else if (watch.isSwipeUpDetected()) {
        watch.showNotifications();
      }
    }
  }
}

• Las acciones se pueden pulsar en cualquier momento y en cualquier orden

• 这些动作可能在任何时刻、以任何顺序被按下

• ¿Cómo controlamos la gestión de las acciones mientras se espera al siguiente segundo,…?

• 在等待下一秒到来的这段时间里,我们怎么管理这些动作的处理……?

• ¿Cuándo/Cómo empiezan y acaba el sistema?

• 系统什么时候、以什么方式开始和结束?

• Se trata de un ejemplo sencillo, situaciones mucho más complejas ocurren continuamente en Programación de Sistemas

• 这只是一个简单的例子,而系统编程中不断出现复杂得多的情况

这段代码是「顺序轮询」的典型反例,考法固定:说出它的三个毛病——①每秒 sleep 期间无法响应,事件可能被漏掉或延迟;②只处理了 tap 和 swipe up,swipe down 被忽略;③系统用 while(true) 永不结束,没有明确的开始/结束语义。
原文只写了 isTapDetected 与 isSwipeUpDetected 两个分支,没有 isSwipeDownDetected——不是漏印,是这段示例本身的缺陷(可与 p.16 的接口对比)。答题时指出这一点会很加分。
口诀:轮询三宗罪——慢、漏、停不下。
p.18

Eventos y Procesos · 两种抽象:并发与事件

▸ 原页截图 p.18 原讲义第 18 页

Los sistemas operativos y (algunos) lenguajes proporcionan abstracciones para tratar con la interacción con el entorno y con otros sistemas software

操作系统以及(部分)语言提供了抽象,用来应对与环境、以及其他软件系统之间的交互

Las más comunes son:

最常见的两种是:

– Concurrencia: Distintas entidades (procesos/hebras) se ejecutan (conceptualmente) al mismo tiempo. En el ejemplo anterior cada proceso se encargaría de una de las funciones. El orden de ejecución viene impuesto por el entorno

– 并发:不同实体(进程/线程)在概念上同时执行。在上面的例子里,每个进程负责其中一个功能,执行顺序由环境决定

– Eventos: En este caso, la ejecución del programa no es secuencial, sino que viene determinado por los eventos externos. Las aplicaciones están estructuradas en dos bloques separados (detección y selección de eventos y el manejo de estos eventos).

– 事件:这时程序的执行不是顺序的,而是由外部事件决定。应用被分成两个独立的块(事件的检测与选择,以及事件的处理)。

• Las abstracciones no son excluyentes. Se pueden y se pueden combinar en algunos casos

• 这些抽象并不互斥,在有些情况下可以、也的确会组合使用

必背两条定义:并发 = 多个实体(进程/线程)概念上同时执行,顺序由环境决定;事件 = 执行不顺序,由外部事件决定,程序分成「检测/选择」和「处理」两块。
原文「Se pueden y se pueden combinar」重复了半句,语义是「可以组合(se pueden combinar)」。另外强调:两种抽象不互斥,这是常见的判断题陷阱。
p.19

En resumen… · 小结:系统编程与用户应用编程的差别

▸ 原页截图 p.19 原讲义第 19 页

La programación de sistemas tiene muchos aspectos que la diferencian de la programación de aplicaciones de usuario

系统编程有很多方面区别于用户的应用编程

– Interacción con el sistema operativo y el hardware

– 与操作系统和硬件交互

– El tiempo real es importante y hay que saber gestionarlo

– 实时很重要,必须懂得管理它

– No todas las abstracciones de la programación más convencional se pueden utilizar. Gestión de memoria diferente

– 传统编程的抽象并非都能用,内存管理方式也不同

– Se necesitan nuevas abstracciones para tratar con la concurrencia

– 需要新的抽象来处理并发

这是第一部分的小结页,简答题「系统编程与用户应用编程有何区别」的标准四点答案:①与 OS/硬件交互;②实时性重要;③传统抽象不全适用、内存管理不同;④需要新的并发抽象。
四点串成一句:下探硬件、盯住时间、扔掉旧抽象、新造并发件。
p.20

De la programación secuencial a la programación concurrente · 冯·诺依曼机的顺序执行

▸ 原页截图 p.20 原讲义第 20 页

Los lenguajes de programación secuenciales explotan explícitamente las características de la máquina que los ejecuta

顺序编程语言会明确地利用执行它的那台机器的特性

En cada ciclo del reloj

在每一个时钟周期里

Se trae una instrucción de la memoria

从内存中取来一条指令

Se decodifica y se envían señales a las componentes del sistema para que se ejecute

对它译码,并向系统各部件发出信号使其执行

Máquina Von-Neumann

冯·诺依曼机

{
  x = …
  y = …
  if (x < y) z = x;
  else z = y;
  …
}
{
  x = 0;
  y = 0;
  …
}
图上是经典冯·诺依曼结构:CPU 通过总线与 RAM 相连,两侧是 input / output;程序和数据都存在同一内存里(存储程序思想),所以取指—译码—执行严格按周期推进,这是「固有顺序性」的物理来源。右侧两个代码框是同一进程的指令流与变量区。
核心结论要能推导:冯·诺依曼机每周期取一条指令 → 指令之间天然全序 → 语言的语义就是这种全序 → 这就是「顺序编程」,也是后面要用 || 打破的东西。
p.21

Ejemplo · 顺序程序的形式化:precede a 与 ∀e

▸ 原页截图 p.21 原讲义第 21 页

Si P = p1;p2;…;pn es un programa secuencial

若 P = p1;p2;…;pn 是一个顺序程序

p1 siempre precederá a p2 (cualquiera que sea la ejecución),

p1 总是先于 p2(无论哪一次执行),

P2 siempre precederá a p3

P2 总是先于 p3

….

……

pn-1 siempre precederá a pn

pn−1 总是先于 pn

Si el símbolo “→” significa “precede a” y ∀e significa “para toda ejecución”, el comportamiento puede formalizarse como ∀e.(p1 →p2) ∧(p2 →p3) ∧… ∧(pn-1 →pn)

若符号「→」表示「先于」,∀e 表示「对所有执行」,则该行为可形式化为 ∀e.(p1 →p2) ∧(p2 →p3) ∧… ∧(pn−1 →pn)

Este comportamiento se mantiene incluso si el código P tiene instrucciones de selección y bucles.

即使代码 P 中含有选择指令和循环,这一行为依然成立。

if (b) {A;} else {B;}

if (b) {A;} else {B;}(选择语句)

∀e.(b →A) ∨(b →B) (depende de los datos de entrada)

∀e.(b →A) ∨(b →B)(取决于输入数据)

三个符号必须会写会读:→(precede a,先于)、∀e(para toda ejecución,对所有执行)、∧ / ∨(y / o,与/或)。顺序程序 = 指令全序,用 ∧ 串起相邻;选择语句用 ∨ 因为只走一支。
原文第二行写成大写「P2」,与前面的「p1 / p3」大小写不一致,是笔误(同一变量 p2)。抄公式时统一用小写 p。
读法口诀:箭头是「先」,倒 A 是「所有执行」,尖朝上是「且」,尖朝下是「或」。
p.22

Ejemplo · 循环与全序:程序是确定性的

▸ 原页截图 p.22 原讲义第 22 页

while (b) {B}

while (b) {B}(当 b 成立时反复执行 B)

∀e.b ∨(b →B →b) ∨(b →B →b →B →b) ∨…

∀e.b ∨(b →B →b) ∨(b →B →b →B →b) ∨…——要么一次都不进循环,要么进 1 次、2 次……

(el número de iteraciones depende de los datos de entrada)

(迭代次数取决于输入数据)

Dado P = p1;p2;…;pn

给定 P = p1;p2;…;pn

Si 0<i<j≤n entonces ∀e.pi →pj

若 0<i<j≤n,则 ∀e.pi →pj(下标小的指令永远先执行)

Las instrucciones están totalmente ordenadas

这些指令是全序的(totally ordered)

El programa es determinista. Dada una instrucción, y unos datos de entrada, siempre se sabe cuál es la siguiente instrucción a ejecutar

程序是确定性的。给定一条指令和一组输入数据,永远知道下一条要执行的是哪条指令

循环的形式化写法是「0 次 ∨ 1 次 ∨ 2 次 ∨ …」,考试要求你说明「迭代次数由输入决定」,但序列本身仍然全序——所以程序依然确定。
口诀:循环只改次数,不改顺序。全序不变 ⇒ 确定性不变。
这一页的「determinista」正好是下一板块的反面:P||Q 是indeterminista(见 p.31),因为同时有多条指令可执行。
p.23

Programación Concurrente · 并非所有指令都必须顺序执行

▸ 原页截图 p.23 原讲义第 23 页

No todas las instrucciones de un programa tienen que ejecutarse de forma secuencial

一个程序里的指令并非都必须顺序执行

El lenguaje nos obliga a establecer un orden de ejecución

是语言在强迫我们规定一个执行顺序

{
  x = 0;
  y = 0;
  z = 0;
  …
}

{ x = 0; y = 0; z = 0; … }

这段代码给三个互不相关的变量赋初值:x = 0; y = 0; z = 0; ……

本页是全章的转折点,一句话考点:这三条赋值彼此没有数据依赖,却被迫写成某个顺序——顺序是语言强加的,不是问题本身要求的。
下一页(p.24)会告诉你这种代码有 6 种顺序都正确:3 个元素的全排列 3! = 6。

二、从顺序到并发:||、交错与偏序

p.23–p.32
p.24

Programación Concurrente · 六种正确顺序

▸ 原页截图 p.24 原讲义第 24 页

No todas las instrucciones de un programa tienen que ejecutarse de forma secuencial

一个程序里的指令并非都必须以顺序方式执行

Este código podría ejecutarse de 6 formas distintas y todas ellas correctas

这段代码可以按 6 种不同的方式执行,而且这 6 种全都正确

{ x = 0; y = 0; z = 0; … }

第 1 种:先 x = 0,再 y = 0,再 z = 0……

{ x = 0; z = 0; y = 0; … }

第 2 种:先 x = 0,再 z = 0,最后 y = 0……

{ y = 0; x = 0; z = 0; … }

第 3 种:先 y = 0,再 x = 0,再 z = 0……

…..

……(省略号表示其余几种排列,页上不再列出)

考点:3 条互不依赖的赋值 → 排列数 3! = 6;幻灯片只展示了前 3 种,剩下 3 种(z→x→y、z→y→x、y→z→x)自己补全。
记忆钩子:全排列数 = n!;三条赋值 3! = 6,两条 2! = 2,四条 4! = 24。
p.25

Programación Concurrente · 新运算符 ||

▸ 原页截图 p.25 原讲义第 25 页

Supongamos que definimos un nuevo operador || para representar este comportamiento

假设我们定义一个新运算符 || 来表示这种行为

x = 0 || y = 0 || z = 0 = {x = 0 → y = 0 → z = 0, x = 0 → z = 0 → y = 0, y = 0 → x = 0 → z = 0, …}

三条赋值用 || 连起来,等于「所有合法顺序」组成的集合:x→y→z、x→z→y、y→x→z……

x = 0 → y = 0 → z = 0

集合元素之一:先 x 再 y 再 z

x = 0 → z = 0 → y = 0

集合元素之二:先 x 再 z 再 y

y = 0 → x = 0 → z = 0

集合元素之三:先 y 再 x 再 z

…

省略号:集合里还有另外三种排列,共 6 种

考点:|| 的结果不是「一条执行路径」,而是一个集合(所有交错顺序);→ 是把两条指令「钉死」先后,|| 是「松开」先后。
易错:|| 不是逻辑或。在这里它是并发组合运算符,优先级与结合方式都要按讲义定义来读。
p.26

Programación Concurrente · 三个处理器与时间重叠

▸ 原页截图 p.26 原讲义第 26 页

Supongamos que definimos un nuevo operador || para representar este comportamiento

假设我们定义一个新运算符 || 来表示这种行为

¿Y si tuviéramos 3 procesadores?

那如果我们有 3 个处理器呢?

Podríamos asignar cada código a un procesador, obteniendo un comportamiento correcto y una ejecución posiblemente más rápida.

我们可以把每段代码分配给一个处理器,从而既得到正确行为,又可能得到更快的执行。

Extendemos el significado de P || Q para indicar que existe una ejecución válida de P y Q, en la que ambos códigos se solapan en el tiempo

我们把 P || Q 的含义扩展为:存在 P 与 Q 的一条合法执行,其中两段代码在时间上重叠。

∃e. ¬(P → Q) ∧ ¬(Q → P)

存在某个事件 e,使「P 先于 Q」不成立、且「Q 先于 P」也不成立——也就是谁都不在谁之前,二者真正并行重叠。

考点:并行(solapamiento)的判据是 ∃e. ¬(P→Q) ∧ ¬(Q→P);写成 ∀ 就变成「任何时刻都有先后」,意思正好相反。
易错:量词是 ∃(存在一条执行)而不是 ∀;两个否定用 ∧ 连接,表示两个方向都不成立。
p.27

Programación Concurrente · 逻辑处理器

▸ 原页截图 p.27 原讲义第 27 页

¿Cómo razonamos sobre la ejecución de P || Q?

我们怎样对 P || Q 的执行进行推理?

Podríamos exigir la existencia de dos procesadores para que exista un solapamiento de instrucciones real

我们可以要求必须有两个处理器,才能出现真正意义上的指令重叠

No es buena idea porque entonces el código de nuestro programa dependería de la arquitectura subyacente

但这不是好主意,因为那样一来我们的程序代码就会依赖底层架构

En su lugar, suponemos que existen un par de procesadores lógicos cada uno ejecutando uno de los códigos.

取而代之,我们假设存在一对逻辑处理器,各自执行其中一段代码。

Un procesador lógico puede coincidir con uno real, pero ¿qué hacemos si no hay suficientes procesadores?

逻辑处理器可以与真实处理器重合,但如果没有足够的处理器,我们怎么办?

Supongamos que P = p1 →p2 →… →pn y que Q = q1 →q2 →… →qm

设 P = p1 → p2 → … → pn,Q = q1 → q2 → … → qm

¿Cómo puede ser la ejecución P || Q si sólo hay un procesador?

如果只有一个处理器,P || Q 的执行会是什么样?

这一页是「建模选择」:与其把并发绑定到硬件核数,不如假设逻辑处理器,让语义与机器无关。下一页用交错(interleaving)回答最后那个问题。
记忆钩子:逻辑处理器 ≠ 真实核;够就真并行,不够就交错,语义不变。
p.28

Interleaving · 执行树与 10 条可能执行

▸ 原页截图 p.28 原讲义第 28 页

Supongamos n = 2 y m = 3: P = p1 →p2 y Q = q1 →q2 →q3

设 n = 2、m = 3:P = p1 → p2,Q = q1 → q2 → q3

P || Q genera un árbol de ejecución

P || Q 会生成一棵执行树

Cada camino en el árbol representa una posible ejecución correcta de P ||Q

树中的每一条路径都代表 P || Q 的一种合法的执行

En este caso hay 10 posibles ejecuciones (sobre un procesador)

在这个例子里,共有 10 种可能的执行(单处理器上)

考点:10 = 5! / (2!·3!),即从 5 个位置里挑 2 个放 p1、p2(其余给 q1、q2、q3);树根到叶的每条路径都保持 p1 在 p2 前、q1 在 q2 在 q3 前。
图上每个节点标着下一步可以执行哪条指令:只要某进程还有未执行指令,它的下一条就可以被选中,形成分叉。
p.29

Interleaving · 顺序执行只是其中一条路径

▸ 原页截图 p.29 原讲义第 29 页

Supongamos n = 2 y m = 3: P = p1 →p2 y Q = q1 →q2 →q3

设 n = 2、m = 3:P = p1 → p2,Q = q1 → q2 → q3

P || Q genera un árbol de ejecución

P || Q 生成一棵执行树

Cada camino en el árbol representa una posible ejecución correcta de P ||Q

树中每条路径都代表 P || Q 的一种合法执行

La ejecución secuencial P; Q es una de entre todas las posibles

顺序执行 P; Q(先做完 P 再做 Q)只是所有可能执行中的一条

考点:P;Q 与 P||Q 的关系——P;Q 是 P||Q 的一种特例(一条 traza),反过来不成立。
记忆钩子:分号是 || 集合里的一个元素:P;Q ∈ P||Q。
p.30

Orden Parcial · 偏序:内部有序、彼此无序

▸ 原页截图 p.30 原讲义第 30 页

Una ejecución correcta de P || Q (P = p1 →p2 →… →pn ,Q = q1 →q2 →… →qm ) se obtiene intercalando las instrucciones de P y Q, pero no de cualquier forma

P || Q 的一条合法执行,是把 P 与 Q 的指令交错起来得到的——但不是随便怎么交错都行。

El orden relativo de las instrucciones en P y Q debe mantenerse,

P 与 Q 内部指令的相对顺序必须保持不变,

Dados dos índices i, j,

给定两个下标 i、j,

si i < j entonces ∀e. (pi →pj) ∧ (qi →qj)

若 i < j,则在任何执行里都有 pi 先于 pj,且 qi 先于 qj(各自内部保序)。

si i < j entonces ∀e. (pi → qj) ∨ (qj → pi)

若 i < j,则 pi 与 qj 之间必有某一个先后(二者之一在前),但谁先谁后不作规定。

El orden en P y Q se conserva

P 与 Q 内部的顺序被保留

Pero no hay orden establecido entre las instrucciones de P y las de Q

但 P 的指令与 Q 的指令之间没有既定顺序

考点:这两条公式就是「偏序」:内部用 ∧(两者都成立),跨进程用 ∨(任一方向都可,但不能都不成立)。
易错:第二条写成 ∧ 就变成「pi 在前且 qj 在前」,自相矛盾;必须是 ∨。
p.31

Orden Parcial · 偏序即不确定性

▸ 原页截图 p.31 原讲义第 31 页

Una ejecución correcta de P || Q (P = p1 →p2 →… →pn ,Q = q1 →q2 →… →qm ) se obtiene intercalando las instrucciones de P y Q, pero no de cualquier forma

P || Q 的合法执行来自把 P、Q 的指令交错排列,但并非任意交错都合法。

El orden relativo de las instrucciones en P y Q debe mantenerse,

P、Q 各自内部的相对指令顺序必须保持,

Dados dos índices i, j,

对任意两个下标 i、j,

si i < j entonces ∀e. (pi →pj) ∧ (qi →qj)

i < j 时,任何执行都满足 pi 先于 pj 且 qi 先于 qj。

si i < j entonces ∀e. (pi → qj) ∨ (qj → pi)

i < j 时,pi 与 qj 之间总有一个先后,而方向不受约束。

En cada momento, puede haber varias instrucciones posibles a ser ejecutadas, por lo que la ejecución paralela es, por definición, INDETERMINISTA

在每一时刻,都可能有多条指令可供执行,因此并行执行按定义就是不确定的(INDETERMINISTA)。

Las instrucciones de P||Q están parcialmente ordenadas

P||Q 的指令是偏序的(只规定了部分先后)。

考点:偏序 → 每一时刻可能有多条可执行指令 → 不确定性(indeterminismo),这是并发程序与顺序程序的本质差别。
易错:不确定 ≠ 随机。它是「规范允许多种执行」,不是运行时掷骰子。
p.32

Programación Concurrente · 小结:进程、交错、traza

▸ 原页截图 p.32 原讲义第 32 页

Resumiendo,

小结如下:

P || Q representa la ejecución concurrente de P y Q.

P || Q 表示 P 与 Q 的并发执行。

P y Q se llaman procesos/hebras y se ejecutan concurrentemente con otros procesos

P 与 Q 称为进程/线程,它们与其他进程并发执行。

Si no tenemos suficientes procesadores, se intercalan las instrucciones de P y Q (interleaving)

如果处理器不够,就把 P 与 Q 的指令交错执行(interleaving)。

Sin embargo, los código de P y Q se ejecutan secuencialmente

然而,P 与 Q 各自的代码仍然是顺序执行的。

Si P = p1 →p2 →… →pn y Q = q1 →q2 →… →qm, el número total de posibles ejecuciones de P||Q sin tener en cuenta posibles solapamientos de instrucciones es (m+n)!/m!*n!

若 P = p1→…→pn、Q = q1→…→qm,则不考虑指令重叠时,P||Q 可能执行的总数为 (m+n)! / (m!·n!)。

Cada posible ejecución se denomina traza (es un camino en el árbol)

每一种可能的执行称为一条轨迹(traza),也就是树上的一条路径。

Para que un programa P||Q sea correcto deben serlo todas sus trazas de ejecución

要让 P||Q 正确,它的所有执行轨迹都必须正确。

考点:正确性判据是「所有 traza 都正确」;只要存在一条错误 traza(如 p.42 售票机),程序就是错的。
原文勘误:第 8 行「los código de P y Q」应为「los códigos de P y Q」(数不一致),此处按原文照录。

三、动机与并发加速实例

p.33–p.39
p.33

Motivación · 为什么要并发

▸ 原页截图 p.33 原讲义第 33 页

Mejorar el rendimiento de los procesadores

提升处理器的性能

Explotar las arquitecturas multiprocesadores

充分利用多处理器架构

Simplificar el modelado de sistemas que son concurrentes de forma natural

简化对「本身就天然并发」的系统的建模

Obtener ganancias en tiempo

在时间上获得收益(缩短总耗时)

考点:四条动机要能默写——性能、多核、天然并发建模、时间收益;后两条也解释了为什么并发不只是「为了快」。
记忆钩子:快、多核、像现实、省时间。
p.34

Ejemplo · Búsqueda lineal(顺序版)

▸ 原页截图 p.34 原讲义第 34 页
int busquedaLineal(int x, Array v, int li, int ls){
  int i=li, pos=-1, enc=0;
  while (i<=ls && !enc)  {
    if (v[i]==x) enc=1;
    else i++;
  }
  if (enc) pos=i;
  return(pos);
}

int busquedaLineal(int x, Array v, int li, int ls){

函数签名:在数组 v 的 [li, ls] 区间里查找 x,返回其位置。

int i=li, pos=-1, enc=0;

i 从下界 li 开始;pos 初值 −1 表示未找到;enc 是「已找到」标志,初值 0。

while (i<=ls && !enc) {

当 i 还没越过上界、且尚未找到时,继续循环。

if (v[i]==x) enc=1;

若当前位置的元素等于 x,置找到标志 enc = 1。

else i++;

否则下标后移一位,继续检查。

if (enc) pos=i;

若找到,把位置记到 pos。

return(pos);

返回 pos(找不到就是 −1)。

Búsqueda lineal

标签:线性查找

考点:这是顺序基线——下一页把它改成 pthread 版本,用来比较「并发能否缩短时间」。
注意循环条件是 && !enc:找到即停,不是把整段扫完。
p.35

Ejemplo · Búsqueda lineal aplicando concurrencia(pthread 版)

▸ 原页截图 p.35 原讲义第 35 页
void *busquedaLineal(void *argg ){
  int i=0, pos=-1, enc=0;
  struct argm *arg;
  arg=(struct argm *) argg;
  i=arg->li;

  while (i<=arg->lf && !enc)  {
    if ((v[i])==(arg->x)) enc=1;
    else i++;
  }
  if (enc)
    printf("Encontrado en pos =%d\n", i);
}

void *busquedaLineal(void *argg ){

线程入口函数:参数是 void*,返回 void*,符合 pthread 要求。

int i=0, pos=-1, enc=0;

局部变量:下标 i、结果 pos、找到标志 enc。

struct argm *arg;

声明一个指向参数结构体的指针 arg。

arg=(struct argm *) argg;

把 void* 参数强制转换回 struct argm*。

i=arg->li;

从结构体里取出本次查找区间的下界 li,作为起点。

while (i<=arg->lf && !enc) {

只要未越过上界 lf 且未找到,就继续。

if ((v[i])==(arg->x)) enc=1;

若全局数组 v 的第 i 个元素等于目标 x,置找到标志。

else i++;

否则下标后移。

if (enc) printf("Encontrado en pos =%d\n", i);

若找到,打印「在位置 %d 找到」。

Búsqueda lineal aplicando concurrencia

标签:应用并发(多线程)的线性查找

"v" es una variable global

注:v 是一个全局变量(所以线程函数不必通过参数拿到数组)。

易错:函数没有显式 return,pthread 会拿到未定义的返回值;另外 v 是全局共享数据,多线程只读它才安全。
考点:pthread 线程函数的固定签名 void* f(void*),参数/返回值都靠指针传递。
p.36

Ejemplo · main:创建两个线程

▸ 原页截图 p.36 原讲义第 36 页
int main () {
  struct argm arg, arg2;
  pthread_t th1,th2;
  pthread_attr_t attr;
  int val=1;
  rellenar(v);
  arg.li=0;  arg.lf=4;  arg.x=1;
  arg2.li=5; arg2.lf=9; arg2.x=1;
  for (val=0;val<10;val++) { printf("arg=%d ", v[val]); }
  pthread_attr_init(&attr);
  printf("Creamos\n");
  pthread_create(&th1,&attr,busquedaLineal,&a
  printf("Creamos\n");
  pthread_create(&th2,&attr,busquedaLineal,&a
  pthread_join (th1,NULL);
  pthread_join(th2,NULL);
  printf("Fin\n");
  return 0;
}

int main () {

主函数开始。

struct argm arg, arg2;

两个参数结构体,分别给两个线程用。

pthread_t th1,th2;

两个线程标识符。

pthread_attr_t attr;

线程属性对象。

int val=1;

循环变量 val。

rellenar(v);

给全局数组 v 填充数据。

arg.li=0; arg.lf=4; arg.x=1;

线程 1 负责区间 [0,4],目标值 1。

arg2.li=5; arg2.lf=9; arg2.x=1;

线程 2 负责区间 [5,9],目标值 1。

for (val=0;val<10;val++) { printf("arg=%d ", v[val]); }

启动前先把整个数组打印一遍,便于核对内容。

pthread_attr_init(&attr);

初始化线程属性对象。

printf("Creamos\n");

打印「Creamos」(我们创建线程),提示即将建线程。

pthread_create(&th1,&attr,busquedaLineal,&a

创建线程 1:入口 busquedaLineal,参数是 arg 的地址(原文该行被排版截断为「&a」)。

pthread_create(&th2,&attr,busquedaLineal,&a

创建线程 2:同一入口函数,参数换成 arg2 的地址(同样被截断)。

pthread_join (th1,NULL);

等待线程 1 结束。

pthread_join(th2,NULL);

等待线程 2 结束。

printf("Fin\n");

打印「Fin」(结束)。

return 0;

主函数返回 0。

原文勘误:两行 pthread_create 的末尾参数在 PDF 里被截断成「&a」,按上下文应为 &arg 和 &arg2;此处照录原文,不改写。
考点:pthread_attr_init → pthread_create → pthread_join 三步走;两线程各查一半,是「分治式并发」的最小例子。
p.37

Ejemplo · 数组一分为二,两线程各查一半

▸ 原页截图 p.37 原讲义第 37 页

La búsqueda la realiza una hebra sobre esta parte del array

查找由一个线程在这段数组上完成(图中左侧 0–4 号格,蓝色对应 th1)。

La búsqueda la realiza otra hebra sobre esta parte del array

查找由另一个线程在这段数组上完成(图中右侧 5–9 号格,橙色对应 th2)。

Ejemplo

标题:示例

这张图只是示意:10 个格子的数组被切成左右两半,两个箭头分别指向「一个 hebra 查这一段」和「另一个 hebra 查那一段」,正好对应 p.36 里 arg.li=0/lf=4 与 arg2.li=5/lf=9。
记忆钩子:切数组、开线程、各查一半——并发的「分而治之」最小模板。
p.38

Comunicación y Sincronización · 共享内存 vs 消息传递

▸ 原页截图 p.38 原讲义第 38 页

Los procesos en un programa concurrente habitualmente tienen que comunicar y sincronizar sus acciones.

并发程序中的进程通常必须通信并同步它们的动作。

La comunicación puede realizarse a través de la memoria compartida

通信可以通过共享内存完成。

O a través de algún mecanismo de paso de mensajes

也可以通过某种消息传递机制完成。

emisor{
  ….
  x = m
}
receptor{
  local y
  ….
  y = x
}
Global x

emisor{ …. x = m }

发送方:把要传的值 m 写进共享变量 x。

receptor{ local y …. y = x }

接收方:声明局部变量 y,再执行 y = x,从共享变量读出。

Global x

x 是全局变量(共享内存通信的媒介)。

emisor{
  ….
  send m to receptor
  ….
}
receptor{
  local y
  ….
  receive y from emisor
  ….
}

emisor{ …. send m to receptor …. }

消息传递版发送方:显式执行 send,把 m 发给 receptor。

receptor{ local y …. receive y from emisor …. }

消息传递版接收方:显式执行 receive,把来自 emisor 的值接收进 y。

考点:两种通信范式的对比——共享内存靠全局变量(需要额外同步),消息传递靠 send/receive(同步内建在通信原语里)。
记忆钩子:共享内存 = 一块黑板;消息传递 = 递纸条。
p.39

Comunicación y Sincronización · 同步条件

▸ 原页截图 p.39 原讲义第 39 页

¿Qué ocurre si el receptor lee el valor antes de que esté disponible?

如果接收方在值还没准备好之前就去读,会发生什么?

El receptor no puede leer su mensaje hasta que el emisor lo haya "enviado"

接收方必须等到发送方「已经发送」之后,才能读取它的消息。

emisor{ …. x = m } / receptor{ local y …. y = x } / Global x

共享内存版代码不变:写 x 与读 x 之间存在先后要求。

emisor{ …. send m to receptor …. } / receptor{ local y …. receive y from emisor …. }

消息传递版代码不变:send 必须先于对应的 receive。

Esto es un ejemplo de una condición de sincronización

这就是一个同步条件的例子:读之前必须等写完成。

考点:同步条件 = 对执行顺序的约束(这里写作 写 → 读,即 send → receive);违反它就会出现「读到旧值/空值」。
易错:通信与同步不是两件事——共享内存方案里,「先写后读」这条同步必须由程序员另外保证。

四、并发编程的经典问题:售票机与临界区

p.40–p.48
p.40

Problemas de la programación concurrente · 本章问题清单

▸ 原页截图 p.40 原讲义第 40 页

Instrucciones atómicas

原子指令

Sección crítica

临界区

Exclusión mutua

互斥

Ejemplo: Máquinas vendedoras de entradas

例子:售票机(剧院售票窗口)

Pueden comprarse entradas desde distintas taquillas

观众可以从不同的售票窗口买票。

这一页只是路线图:接下来 p.41–p.48 用同一个售票机例子,依次引出错误轨迹 → 加检查 → 原子性 → 临界区 → 互斥。
考点:这四个名词的定义与关系(原子 → 临界区 → 互斥)是本页之后所有内容的主线。
p.41

Problemas · 售票机模型:T1 || T2 || … || Tn

▸ 原页截图 p.41 原讲义第 41 页

Cada Taquilla es un proceso Ti

每个售票窗口是一个进程 Ti。

Todas las taquillas se ejecutan concurrentemente

所有窗口并发执行。

Todas las taquillas ejecutan el mismo código

所有窗口执行同一段代码。

Suponemos que hay un array de booleanos que representa los asientos del teatro

假设有一个布尔数组表示剧院的座位(true = 已售)。

T1 || T2 || …|| Tn

整个系统写作 T1 || T2 || … || Tn(n 个窗口并发)。

Código de Tn
while (1){
  mostrar butacas libres al usuario
  a = … //asiento seleccionado
  asientos[a] = true
  emitir la entrada
}
….
int asientos[]

Código de Tn

Tn 的代码(每个窗口都一样;页面上还并列了一份 Código de T1)。

while (1){

无限循环:窗口一直营业。

mostrar butacas libres al usuario

向用户显示空闲座位。

a = … //asiento seleccionado

a = ……(用户选中的座位号)。

asientos[a] = true

把该座位标记为已售。

emitir la entrada

出票。

int asientos[]

共享的座位数组(全局)。

¿Esta solución es correcta?

这个解法正确吗?

易错:代码里没有检查座位是否已经被别人买走——直接写 true。这就是下一页错误轨迹的根源。
考点:会写出 T1 || T2 || … || Tn 这种并发组合,并说明「所有窗口跑同一段代码、共享 asientos[]」。
p.42

Ejemplo · 错误轨迹:22 号座位卖了两次

▸ 原页截图 p.42 原讲义第 42 页

Esta solución es incorrecta. Es posible que dos personas distintas compren el mismo asiento

这个解法是错误的:有可能两个不同的人买到同一个座位。

Pseudocódigo de cada taquilla
while (1){
  mostrar butacas libres al usuario
  a = … //asiento seleccionado
  asientos[a] = 1
  emitir la entrada
}

Pseudocódigo de cada taquilla

每个窗口的伪代码

Ti: mostrar butacas libres al usuario

Ti:向用户显示空闲座位。

Tj: mostrar butacas libres al usuario

Tj:也向用户显示空闲座位。

Ti: a = …; //asiento seleccionado en la taquilla i, por ejemplo a = 22

Ti:a = ……(i 号窗口选中的座位,例如 a = 22)。

Tj: a = …; //asiento seleccionado en la taquilla j, por ejemplo a = 22

Tj:a = ……(j 号窗口选中的座位,例如同样是 a = 22)。

Ti: asientos[22] = 1

Ti:把 22 号标记为已售。

Tj: asientos[22] = 1

Tj:又把 22 号标记为已售(覆盖,没有报错)。

Ti: emitir la entrada

Ti:出票。

Tj: emitir la entrada

Tj:也出票。

El asiento 22 se ha vendido a dos clientes distintos

结果:22 号座位被卖给了两个不同的顾客。

Esto es una traza de ejecución, un posible camino en el árbol, que muestra un error. Sirve para demostrar que un programa es incorrecto

这是一条执行轨迹——树上的一条可能路径——它展示了错误。它足以证明程序不正确。

考点:证明并发程序错误只需一条错误 traza(反例);而证明正确必须覆盖所有 traza。
记忆钩子:「查—选—写—票」四步被另一窗口插进来,就会双卖。
p.43

Ejemplo · 精化代码:先检查座位是否空闲

▸ 原页截图 p.43 原讲义第 43 页

Añadimos este código para asegurarnos de que cuando se selecciona una butaca está realmente libre

我们加上这段代码,以确保选座时该座位确实空闲。

Refinamos el código

我们精化代码。

Pseudocódigo de Ti

Ti 的伪代码

while (1){
  exito = 0;
  while (!exito){
    mostrar butacas libres al usuario
    a=…; //asiento seleccionado
    if (! asientos[a]) {
      asientos[a] = 1;
      emitir la entrada
      exito = 1;
    } else {
      dar un mensaje de error
    }
  }
}

while (1){

外层无限循环:窗口持续营业。

exito = 0;

每次卖票前把「成功」标志清 0。

while (!exito){

只要还没成功,就重试。

mostrar butacas libres al usuario

显示空闲座位。

a=…; //asiento seleccionado

a = ……(选中的座位)。

if (! asientos[a]) {

若该座位尚未售出(值为 false):

asientos[a] = 1;

标记为已售;

emitir la entrada

出票;

exito = 1;

置成功标志,退出内层循环。

} else {

否则(座位已被占):

dar un mensaje de error

给出错误提示,然后重新选座。

¿Ahora está bien?

现在就对了吗?

考点:这一版看似加上了「检查」,但检查与置位是两条独立指令,中间仍可被另一个窗口插入——p.44 立刻给出新的错误轨迹。
易错:「先检查后使用」不等于原子(check-then-act 竞态),这是并发最经典的坑。
p.44

Ejemplo · 精化后仍有错误轨迹

▸ 原页截图 p.44 原讲义第 44 页

TRAZA de ejecución que muestra el error

展示该错误的执行轨迹(TRAZA)

Ti: chequea asiento[22] y lo encuentra libre

Ti:检查 22 号座位,发现它是空的。

Tj: chequea asiento[22] y lo encuentra libre

Tj:也检查 22 号座位,也发现它是空的。

Ti: asientos[22] = 1

Ti:把 22 号置为已售。

Tj: asientos[22] = 1

Tj:又把 22 号置为已售。

Ti: emitir la entrada

Ti:出票。

Tj: emitir la entrada

Tj:出票。

Estamos en la misma situación de antes, salvo que ahora tenemos localizado el problema

我们处于和之前相同的情形,只不过现在把问题定位出来了:两次检查都通过,之后才各自置位。

考点:错误轨迹的写法——必须是「Ti 检查 → Tj 检查 → Ti 置位 → Tj 置位」这种交错;说明 if 判断本身不提供互斥。
p.45

Ejemplo · 原子指令与编译后的机器指令

▸ 原页截图 p.45 原讲义第 45 页

Instrucciones atómicas: las que el procesador realiza sin interrupción.

原子指令:处理器执行过程中不会被打断的指令。

Sólo las instrucciones máquina son atómicas

只有机器指令才是原子的。

>
load asientos[a] to CPU register
test the value of CPU register
jump to L1 if true
set asientos[a] to true
>
code for “emitir la entrada”
set éxito a true
L1: code for “mensaje error”
L2: code following if statement

load asientos[a] to CPU register

把 asientos[a] 装入 CPU 寄存器。

test the value of CPU register

测试寄存器的值(是否为 true)。

jump to L1 if true

若为 true 则跳到 L1(即走「报错」分支)。

set asientos[a] to true

把 asientos[a] 置为 true(标记已售)。

code for “emitir la entrada”

「出票」对应的代码。

set éxito a true

把 éxito(成功标志)置为 true。

L1: code for “mensaje error”

标签 L1:「错误提示」对应的代码。

L2: code following if statement

标签 L2:if 语句之后的代码。

¿y si el código marcado fuera atómico?

那么,如果被标记出的那段代码是原子的,会怎样?

考点:一行 C 的 if (!asientos[a]) { asientos[a]=1; … } 会展开成四条机器指令;只有单条机器指令天然原子,整段 if 不是。
图中用蓝框圈出的正是这四条:load / test / jump / set——它们合起来才等价于「检查并置位」。
p.46

Ejemplo · 若蓝框代码原子,错误轨迹不再可能

▸ 原页截图 p.46 原讲义第 46 页

Instrucciones atómicas: las que el procesador realiza sin interrupción.

原子指令:处理器执行时不会被打断的指令。

Sólo las instrucciones máquina son atómicas

只有机器指令才是原子的。

>
load asiento[a] to CPU register
test the value of CPU register
jump to L1 if true
set asiento[a] to true
>
code for “emitir la entrada”
set éxito a true
L1: code for “mensaje error”
L2: code following if statement

TRAZA de ejecución que muestra el error

展示错误的执行轨迹

Ti: chequea asientos[22] y lo encuentra libre

Ti:检查 asientos[22],发现是空的。

Tj: chequea asientos[22] y lo encuentra libre

Tj:检查 asientos[22],也发现是空的。

Ti: asientos[22] = 1

Ti:置 asientos[22] = 1。

Tj: asientos[22] = 1

Tj:又置 asientos[22] = 1。

Ti: emitir la entrada

Ti:出票。

Tj: emitir la entrada

Tj:出票。

Si el código azul fuera atómico la traza errónea ya no puede ocurrir

如果蓝色框里的代码是原子的,那么这条错误轨迹就不可能发生。

考点:原子性把「检查 + 置位」变成不可分割的一步,等价于说这条错误 traza 被从执行树里整枝剪掉。
易错:真实硬件并不提供这种复合原子指令——所以需要下一页的「临界区 + 互斥」。
p.47

Ejemplo · 原子之后唯一可能的交错

▸ 原页截图 p.47 原讲义第 47 页

El único entrelazado posible ocurre ANTES O DESPUÉS de que Ti hay ejecutado el código azul

唯一可能的交错发生在 Ti 执行完蓝框代码的之前或之后。

TRAZA de ejecución no errónea

一条不错误的执行轨迹

Ti: chequea asiento[22] y lo encuentra libre

Ti:检查 22 号座位,发现空闲。

Ti: asientos[22] = 1

Ti:置为已售(上两步已在原子块内合成一步)。

Tj: chequea asiento[22] y lo encuentra ocupado

Tj:再检查 22 号,发现已被占用。

…

……(Tj 随后走错误提示分支,不会双卖)

记忆钩子:原子块 = 不可插入的黑盒;别的线程只能排在它前面或后面。
考点:对比 p.44 与 p.47 两条轨迹,说清「加原子性」到底排除了哪一条路径。
p.48

Ejemplo · 临界区与互斥的形式定义

▸ 原页截图 p.48 原讲义第 48 页

Instrucciones atómicas: las que el procesador realiza sin interrupción.

原子指令:处理器执行时不会被打断的指令。

Sólo las instrucciones máquina son atómicas

只有机器指令才是原子的。

Sección crítica: parte del código de un proceso que debería ejecutarse de forma atómica

临界区:进程代码中应当以原子方式执行的那一部分。

Cuando dos secciones críticas de dos procesos no pueden solaparse en el tiempo (su código no puede entrelazarse) se dice que deben ejecutarse en exclusión mutua

当两个进程的临界区在时间上不能重叠(代码不能交错)时,就说它们必须以互斥方式执行。

Si SCi y SCj son dos secciones críticas de los procesos Ti y Tj, la exclusión mutua significa que ∀e. (SCi →SCj )∨(SCj →SCi )

若 SCi、SCj 分别是进程 Ti、Tj 的临界区,则互斥意味着:任何执行里都必有 SCi 先于 SCj 或 SCj 先于 SCi(一个整体先后,不许交错)。

Sección crítica

图中标注:临界区(左右两个蓝框里圈出的同一段代码,各自属于一个进程)。

考点:互斥公式 ∀e.(SCi → SCj) ∨ (SCj → SCi)——对每个执行 e,两个临界区必须是「全序」的;绝不能出现指令级交错。
易错:公式里是 ∨(谁先都行,但不能同时),不是 ∧(同时发生反而违背互斥)。

五、课程后续

p.49
p.49

En el resto de la asignatura… · 后续课程路线

▸ 原页截图 p.49 原讲义第 49 页

Nos centraremos en:

我们将聚焦于:

Estudiar la concurrencia con diferentes mecanismos para su utilización en la programación de sistemas y también su influencia en:

用不同机制研究并发,既用于系统编程,也关注它对下列领域的影响:

Sistemas Distribuidos y Paralelos

分布式系统与并行系统

Comunicaciones

通信

Estudiar otros mecanismos basados en paso de mensajes

研究其他基于消息传递的机制

Estudiaremos la influencia del tiempo en los Sistemas de Tiempo Real

我们将研究时间对实时系统的影响

这是全章的收尾:并发机制 → 分布式/并行 → 通信 → 消息传递 → 实时系统中的时间约束;正好对应课程名「并发与实时系统」的两半。
考点:这一页常出「本课程后续学什么」的简答——三条主线:并发机制、消息传递、实时时间。

专有名词速记表(A–Z)

共 82 条,覆盖全 49 页的高频术语。第三列点页码直接跳回原页;最后一列只写「一句话 + 最容易被扣分的点」。

西语术语中文页码一句话记住 · 易错点
A
abstracciones抽象p.6OS 把硬件细节包起来;越靠系统层抽象越薄——别把「层数多」当成抽象好。
AdaAdap.14为高可靠/实时而生,内建任务与保护对象;产业影响有限,航天军工仍在用。
APIs应用程序接口p.7系统程序靠 OS 的 API(如 POSIX)干活;易错:API 不等于跨平台一致。
árbol de ejecución执行树p.28每个分叉=下一步可选哪条指令;根到叶的一条路径=一条 traza。
arquitectura subyacente底层架构p.27语义不能绑死核数;建模在逻辑处理器上,程序才可移植。
arquitecturas multiprocesadores多处理器架构p.33并发动机之一:不榨干多核就是浪费硬件;易错:核多 ≠ 自动变快。
B
bajo nivel底层p.7贴着寄存器/地址写;换来的是控制力,代价是可移植性与安全性。
C
compiladores cruzados交叉编译器p.8在 host 上编译出 target 能跑的代码;易错:它是编译器,不是模拟器。
comunicar通信p.38进程间交换数据;只有两条路——共享内存或消息传递。
concurrencia并发p.6多个活动在时间上重叠;单核靠交错,多核才真并行。
concurrente并发的p.32并发的=执行可能重叠;不等于 simultáneo(同时)。
concurrentes并发的p.15多个进程并存、相对顺序未知;是「允许重叠」而非「必须重叠」。
condición de sincronización同步条件p.39对顺序的硬约束(写→读、send→receive);违反就读到空值/旧值。
criticidad关键性p.5出错代价极高(人身/重大损失);与 fiabilidad、可预测性并列为实时三大特征。
D
depuración调试p.8嵌入式靠仿真器/在线调试;易错:target 上常常没有 printf 可看。
determinista确定性p.22给定输入只有一条执行;并发默认是 indeterminista。
direcciones地址p.13内存/硬件地址不可随意回收或搬移;GC 的「搬移」在系统层是灾难。
direcciones físicas物理内存p.11要直接控制就必须拿到物理地址与寄存器映射。
E
ejecución执行(一次运行)p.28一次具体运行=树上一条路径;同一程序可以有多条执行。
emuladores模拟器p.8软件模拟 target 指令集,能跑原程序;与 simulador(模拟环境/外设)区分。
entrada/salida输入/输出p.8嵌入式常直接读写 I/O 寄存器;易错:别假设有统一驱动层。
entrelazado交错p.47指令级交错;原子块内部不允许 entrelazado。
eventos事件p.2事件驱动(回调/事件循环)是与进程并列的并发抽象,两者不互斥。
Exclusión mutua互斥p.2两个临界区不能重叠:∀e.(SCi→SCj)∨(SCj→SCi)。
F
fiabilidad可靠性p.5长时间正确运行的能力;实时系统三特征之一。
Fragmentación碎片p.13反复分配/释放留下空洞;嵌入式常干脆禁用动态分配。
G
grado de abstracción抽象程度p.4系统编程的抽象层次低于应用编程——这是两者最本质的差别。
H
hardware硬件p.3系统程序直接与硬件/OS 打交道;应用编程站在更高层。
hebra线程p.37进程内的执行流,共享地址空间;切换比进程便宜。
hebras线程p.18并发两大抽象之一;西语里 proceso/hebra 常混用,按上下文读。
host宿主机p.8编译发生的开发机;产物跑在 target 上。
hueco空洞p.13碎片留下的空洞;易错:有空洞也不一定能装下大块请求。
I
INDETERMINISTA不确定的p.31同一程序有多种合法执行;它不是随机,而是规范允许。
Instrucciones atómicas原子指令p.2执行中不被打断;只有机器指令天然原子,整段 if 不是。
interfaz接口p.16SmartWatch 的 6 个方法即接口;接口只声明行为,不保证线程安全。
interleaving交错p.32处理器不够时把两段指令交错;每种交错都是一条 traza。
M
Máquina Von-Neumann冯·诺依曼机p.20取指-译码-执行串行推进;这是顺序语义的硬件根源。
Máquinas vendedoras de entradas售票机p.40双卖同一座位的经典反例;证明错误只需一条 traza。
mecanismos机制p.49信号量、管程、消息传递等;后续课程的主线。
memoria compartida共享内存p.38靠全局变量通信;易错:同步要程序员自己做(先写后读)。
memoria física物理内存p.7系统编程要能控制物理内存布局;带 GC 的语言做不到。
O
operador运算符p.25|| 是并发组合,结果是所有合法顺序的集合——不是逻辑或。
P
paso de mensajes消息传递p.38send/receive 显式通信;同步内建在通信原语里。
predecible可预测的p.13执行时间可界定;易错:cache/中断让最坏时间很难估。
predecibles可预测的p.5实时系统必须可预测;与 fiabilidad、criticidad 一起背。
primitivas原语p.9OS 提供的底层调用(时钟、延时);精度受时钟粒度限制。
procesadores lógicos逻辑处理器p.27建模用的虚拟处理器;几个逻辑处理器就是几条执行流。
procesos进程p.2并发抽象之一,与 eventos 并列;别与线程混为一谈。
procesos/hebras进程/线程p.32P、Q 的统一叫法;答题写「进程/线程」都算对。
Programación Concurrente并发编程p.1研究多活动重叠执行的编程;本章后半的主题。
programación de aplicaciones应用编程p.3站在 OS/库之上写业务逻辑;与系统编程对照记。
Programación de Sistemas系统编程p.1直接与硬件/OS 打交道的编程;抽象层次低。
R
recolección de basura垃圾回收p.7自动回收内存;系统编程要确定性,故通常禁用 GC。
recolector de basura垃圾回收器p.14Java/C# 有 GC;Ada 走静态检查、Rust 走所有权。
recursos资源p.5CPU、内存、I/O 都有限;并发就是共享与调度这些资源。
registro寄存器p.11外设寄存器被映射到内存地址,用指针+volatile 访问。
registros寄存器p.11内存映射 I/O 的核心;易错:漏 volatile 会被编译器优化掉读写。
reloj del sistema系统时钟p.9currentTimeMillis 精度低且会跳变;测耗时用 nanoTime。
reloj inteligente智能手表p.15SmartWatch 例子:接口+轮询,引出「并发 vs 事件」。
rendimiento性能/吞吐p.33并发的第一动机;易错:加速受串行部分上限约束。
retrasos延迟p.9sleep 类延时精度有限,不能用于硬实时。
RustRustp.14所有权+类型系统在编译期挡住数据竞争;系统编程新宠。
S
Sección crítica临界区p.2应当原子执行的代码段;必须用互斥保护。
secuencial顺序地p.24顺序执行;3 条无关赋值 3!=6 种顺序都正确。
secuencial P; Q顺序执行(先 P 后 Q)p.29它只是 P||Q 的一条 traza;反过来不成立。
simuladores仿真器p.8模拟整个目标环境(外设、时序);比 emulador 更偏系统级。
simultáneas同时的p.15真正同时执行,需要多个物理处理器。
simultaneidad同时性p.5并发系统必须处理「同时发生」;实时系统的核心难点之一。
sincronizar同步p.38协调动作的先后;通信往往隐含同步。
sistema operativo操作系统p.3系统编程的主要抽象提供者与服务对象。
Sistemas Concurrentes y de Tiempo Real并发与实时系统p.1课程名:并发 + 实时,两条主线贯穿全课。
sistemas de desarrollo开发系统p.8host 侧工具链(编译器、调试器);与 target 运行环境相对。
Sistemas de Tiempo Real实时系统p.49正确性依赖时间;后续课程重点。
sistemas empotrados嵌入式系统p.6专用计算机藏在设备里;常常没有 OS 或只有 RTOS。
sistemas empotrados/embebidos嵌入式系统p.4同一概念的两种西语说法;看到任一都认。
Sistemas Operativos操作系统p.6通用 OS 不适合硬实时;需要 RTOS 或裸机。
Sistemas Operativos de Tiempo Real实时操作系统p.6调度可预测、响应有界的 OS(RTOS)。
solapan重叠p.26时间重叠=并行判据 ∃e.¬(P→Q)∧¬(Q→P)。
T
Taquilla售票窗口p.41售票窗口=进程 Ti;所有窗口同代码、共享 asientos[]。
target目标机p.8程序最终运行的机器,通常资源受限。
tiempo real实时p.4正确性包含时间约束;实时 ≠ 快。
traza执行轨迹p.32执行树的一条路径;程序正确要求所有 traza 都正确。

交错数量速查 · 数值阈值

p.32 给出两个进程 P(m 条指令)与 Q(n 条指令)的合法交错总数:(m+n)! / (m!·n!)。下表按 m = n 逐级列出,用来直观感受「并发组合数爆炸」——这也是并发程序难以测试、难以复现 bug 的根源。

m = n交错总数规模感受
12各 1 条指令,只有 AB / BA 两种顺序。
26各 2 条指令,已经需要枚举 6 条 traza。
320各 3 条指令,手工列举开始吃力。
470各 4 条指令,超过人工可穷举的范围。
5252各 5 条指令,测试覆盖面迅速失控。
6924各 6 条指令,接近千条合法执行路径。
73432各 7 条指令,靠穷举验证正确性已不现实。

处理器数量不改变交错总数,只决定这些交错是「真并行」还是「分时交错」——判定要点见下表。

处理器数P || Q 的执行形态
1只能交错执行:仍是并发(concurrencia),但不是并行(paralelismo)。
2两进程可同时推进:出现真正并行,但合法交错集合仍是 (m+n)!/m!·n! 条。
3处理器多于进程时并行度饱和,多余处理器对本例无用。
速记:并发 = 逻辑上同时推进(单核也能做到);并行 = 物理上同时执行(需要多核)。数量级只需记住 2 → 6 → 20 → 70,再往上就是「组合爆炸」。

易混概念对照 · 一张表分清

以下 8 组概念在课件里反复出现,考试最爱在这里设陷阱。左边是常被混用的两方,右边给出一句话分界。

Concurrencia · 并发逻辑上同时推进:单核靠时间片交错也能做到(p.32)。
Paralelismo · 并行物理上同时执行:必须有多核/多处理器,是并发的特例(p.31–p.32)。
Programación de sistemas · 系统编程贴近硬件与操作系统,关注时间、并发、资源管理(p.3–p.4)。
Programación de aplicaciones · 应用编程建立在系统提供的抽象之上,不直接管硬件(p.3–p.4)。
host · 开发机编写与交叉编译所在的机器(p.8)。
target · 目标机程序真正运行的嵌入式设备,最终调试只能在其上进行(p.8)。
currentTimeMillis() · 墙钟受系统时钟调整影响,精度毫秒级,适合记「日期时间」(p.9)。
nanoTime() · 单调计时从 JVM 启动起单调递增、纳秒级,专门用来测耗时(p.9–p.10)。
Proceso · 进程并发活动的执行单位,有独立控制流与状态(p.15–p.17)。
Evento · 事件对外部刺激的响应,通常与主控制流共享同一执行线索(p.15–p.17)。
Instrucción atómica · 原子指令硬件保证不可分割的一条指令,是构造互斥的底层砖块(p.40)。
Sección crítica · 临界区访问共享资源的一段代码,需要协议保证互斥,本身不是原子指令(p.47–p.48)。
Traza · 执行轨迹执行树中的一条实际路径,即一种具体交错(p.32)。
Árbol de ejecución · 执行树所有合法交错的集合,分支来自调度选择(p.32)。
Determinismo · 确定性同一输入只有唯一结果;顺序程序通常如此(p.31)。
Indeterminismo · 不确定性同一输入可能有多个合法 traza,P || Q 按定义就是不确定的(p.31)。
最常见的混淆:把「并发」直接等同于「并行」。单核上两个进程交错执行是并发但绝非并行;反过来多核并行一定蕴含并发。