- 一页一块:页号胶囊是 PDF 物理页序(1–49);幻灯片上印的页码可能另有编号,以胶囊为准。
- 逐句对照:蓝色左框内是西语原句(逐字照抄,含原文笔误),下面带「中」字标的是中文翻译;项目符号统一用 • 表示。
- 提示框:绿色「考点」= 这页怎么考;红色「陷阱」= 易错点与原文勘误;紫色「记忆钩子」= 口诀;橙色「补充」= 前后页串联。
- 术语悬停:西语句里带浅蓝底的词,鼠标停上去出中文;中文句里带虚下划线的词,停上去出西语原词。
- 公式:一律用本地 MathJax 渲染(断网也能显示),每个公式下附「符号 / 西语读法 / 中文含义」三列小表——口语考试念的就是这一列。
一、封面与目录
p.1–p.2Portada · 封面
▸ 原页截图 p.1
Grado en Ingeniería Telemática
远程通信工程(Telemática)本科专业
Tema 1: Introducción a la
主题 1:
Índice de contenidos · 目录
▸ 原页截图 p.2
Índice de contenidos
目录
•
•
• Lenguajes para
•
• Gestión de actividades concurrentes:
• 并发活动的管理:
• De la programación secuencial a la
• 从顺序编程到
• Beneficios y usos de la
•
• Problemas de la
•
–
–
–
–
–
–
Programación de Sistemas · 系统编程:与应用编程的分界
▸ 原页截图 p.3
El concepto de
En la
在
En la
在
Programación de Sistemas · 系统编程:抽象层次更低
▸ 原页截图 p.4
En la
在
Un ejemplo de
En estos sistemas los computadores forman parte de otros sistemas más complejos, a los que controlan
在这类系统中,计算机是更复杂系统的一部分,并对那些系统进行控制
Programación de Sistemas · 让系统编程变「特殊」的因素
▸ 原页截图 p.5
Algunas características que hacen a la
让
– Se interacciona con el mundo físico a través del
– 通过
– En esta interacción hay que tener en cuenta factores como:
– 在这种交互中必须考虑如下因素:
• La
• 系统的
• Los
•
• 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
– 在真实世界里时间是连续的,并且存在
– La interacción con el entorno esta sujeta a restricciones de
– 与环境的交互受
Programación de Sistemas · 如何获得与环境的交互:OS 与实时 OS
▸ 原页截图 p.6
¿Cómo conseguimos esa interacción con el entorno?
我们怎样获得这种与环境的交互?
• Los
•
– Gestionan aspectos como el tiempo, la
– 它们管理时间、
– En sistemas donde el tiempo es un factor crítico, no nos vale cualquier
– 在时间成为关键因素的系统里,随便一个
• En ocasiones tendremos que interactuar con el
• 有时我们不得不直接与
– En algunos
– 在一些
Lenguajes para Programación de Sistemas · 系统编程语言及特征
▸ 原页截图 p.7
La mayor parte de los lenguajes para
用于
Algunos de los más utilizados
最常用的一些是
– C, C++, Rust, Ada
– C、C++、Rust、Ada
Algunas características:
一些特征:
– Acceso a
– 可访问
– Posibilidad de acceso al
– 既可以直接访问
– Soporte de
– 支持
– Eficientes y con capacidad de análisis de consumo de
– 高效,并且能够分析
Lenguajes para Programación de Sistemas · 交叉编译:host 与 target
▸ 原页截图 p.8
Con frecuencia los
通常
Los compiladores que se utilizan se denominan
所使用的编译器称为
– La máquina en la que se desarrolla se denomina
– 开发所用的机器称为
– La
–
– La
– 最终的
Lenguajes para Programación de Sistemas · 时间的处理:Java 两种时钟
▸ 原页截图 p.9
Tratamiento del tiempo:
对时间的处理:
– Suelen existir
– 通常会有
– En Java:
– 在 Java 中:
• System.currentTimeMillis(),
• 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?
– 例子:怎样测量一段代码执行所花的时间?
Lenguajes para Programación de Sistemas · 测量耗时的代码与三个问题
▸ 原页截图 p.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,
其他程序、
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
但我们真正需要知道的是最坏时间:这就是实时系统语言要解决的问题
Lenguajes para Programación de Sistemas · 内存管理:为什么要自己控地址
▸ 原页截图 p.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
• 在
• Por ej. el
• 例如,
• Ese
• 必须把这个
Un ejemplo en C · C 语言实例:位域 + 绝对地址映射
▸ 原页截图 p.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(错误)五段组成。
Gestión de memoria · 更多问题:不可预测与碎片
▸ 原页截图 p.13
Más problemas:
还有更多问题:
– Gestión de memoria no
– 内存管理
• El esfuerzo para encontrar un
• 找一个
–
–
• Si se tiene un
• 如果有一个大小为 N 的
• Después de un tiempo de ejecución, la mayor parte de la memoria son huecos (
• 运行一段时间后,内存的大部分都变成了空洞(
– Las
– 与
Espacio libre · Nuevo objeto · Objeto antiguo
图注:空闲空间、新对象、旧对象——新对象被放进空洞后,剩下的那块就是碎片。
Lenguajes para Programación de Sistemas · 为什么是 C/C++,Ada 与 Rust 的定位
▸ 原页截图 p.14
Las anteriores limitaciones hacen que no todos los lenguajes puedan ser utilizados en la
上述限制使得并非所有语言都能用于
Los más utilizados con diferencia son C y C++, que permiten acceder a la
遥遥领先的最常用语言是 C 和 C++:它们允许访问
– Son lenguajes extremadamente propensos a errores
– 它们极其容易出错
– Están impuestos por la industria
– 它们是产业界强制的事实标准
Lenguajes como
像
Gestión de actividades concurrentes: Eventos y Procesos · 并发活动管理开场
▸ 原页截图 p.15
Como consecuencia de la interacción con el mundo físico, la
由于要与物理世界交互,
Un ejemplo sencillo: gestión de la interacción con un
一个简单的例子:管理与一块
Gestión de actividades concurrentes: Eventos y Procesos · 智能手表接口
▸ 原页截图 p.16
Supongamos un paquete en java, que nos proporciona la siguiente
假设有一个 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?
那我们怎么做呢?
Gestión de actividades concurrentes: Eventos y Procesos · 轮询方案及其四个疑问
▸ 原页截图 p.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
• 这只是一个简单的例子,而
Eventos y Procesos · 两种抽象:并发与事件
▸ 原页截图 p.18
Los
Las más comunes son:
最常见的两种是:
–
–
–
–
• Las
• 这些
En resumen… · 小结:系统编程与用户应用编程的差别
▸ 原页截图 p.19
La
– Interacción con el
– 与
– El
–
– No todas las
– 传统编程的
– Se necesitan nuevas
– 需要新的
De la programación secuencial a la programación concurrente · 冯·诺依曼机的顺序执行
▸ 原页截图 p.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
对它译码,并向系统各部件发出信号使其执行
{
x = …
y = …
if (x < y) z = x;
else z = y;
…
}
{
x = 0;
y = 0;
…
}
Ejemplo · 顺序程序的形式化:precede a 与 ∀e
▸ 原页截图 p.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)(取决于输入数据)
Ejemplo · 循环与全序:程序是确定性的
▸ 原页截图 p.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
程序是
Programación Concurrente · 并非所有指令都必须顺序执行
▸ 原页截图 p.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.23–p.32Programación Concurrente · 六种正确顺序
▸ 原页截图 p.24
No todas las instrucciones de un programa tienen que ejecutarse de forma
一个程序里的指令并非都必须以顺序方式执行
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……
…..
……(省略号表示其余几种排列,页上不再列出)
Programación Concurrente · 新运算符 ||
▸ 原页截图 p.25
Supongamos que definimos un nuevo
假设我们定义一个新运算符 || 来表示这种行为
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 种
Programación Concurrente · 三个处理器与时间重叠
▸ 原页截图 p.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
我们把 P || Q 的含义扩展为:存在 P 与 Q 的一条合法执行,其中两段代码在时间上重叠。
∃e. ¬(P → Q) ∧ ¬(Q → P)
存在某个事件 e,使「P 先于 Q」不成立、且「Q 先于 P」也不成立——也就是谁都不在谁之前,二者真正并行重叠。
Programación Concurrente · 逻辑处理器
▸ 原页截图 p.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
但这不是好主意,因为那样一来我们的程序代码就会依赖底层架构
En su lugar, suponemos que existen un par de
取而代之,我们假设存在一对逻辑处理器,各自执行其中一段代码。
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 · 执行树与 10 条可能执行
▸ 原页截图 p.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
P || Q 会生成一棵执行树
Cada camino en el árbol representa una posible
树中的每一条路径都代表 P || Q 的一种合法的执行
En este caso hay 10 posibles ejecuciones (sobre un procesador)
在这个例子里,共有 10 种可能的执行(单处理器上)
Interleaving · 顺序执行只是其中一条路径
▸ 原页截图 p.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
顺序执行 P; Q(先做完 P 再做 Q)只是所有可能执行中的一条
Orden Parcial · 偏序:内部有序、彼此无序
▸ 原页截图 p.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 的指令之间没有既定顺序
Orden Parcial · 偏序即不确定性
▸ 原页截图 p.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)。
Las instrucciones de P||Q están parcialmente ordenadas
P||Q 的指令是偏序的(只规定了部分先后)。
Programación Concurrente · 小结:进程、交错、traza
▸ 原页截图 p.32
Resumiendo,
小结如下:
P || Q representa la ejecución
P || Q 表示 P 与 Q 的并发执行。
P y Q se llaman
P 与 Q 称为进程/线程,它们与其他进程并发执行。
Si no tenemos suficientes procesadores, se intercalan las instrucciones de P y Q (
如果处理器不够,就把 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),也就是树上的一条路径。
Para que un programa P||Q sea correcto deben serlo todas sus trazas de ejecución
要让 P||Q 正确,它的所有执行轨迹都必须正确。
三、动机与并发加速实例
p.33–p.39Motivación · 为什么要并发
▸ 原页截图 p.33
Mejorar el
提升处理器的性能
Explotar las
充分利用多处理器架构
Simplificar el modelado de sistemas que son concurrentes de forma natural
简化对「本身就天然并发」的系统的建模
Obtener ganancias en tiempo
在时间上获得收益(缩短总耗时)
Ejemplo · Búsqueda lineal(顺序版)
▸ 原页截图 p.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
标签:线性查找
Ejemplo · Búsqueda lineal aplicando concurrencia(pthread 版)
▸ 原页截图 p.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 是一个全局变量(所以线程函数不必通过参数拿到数组)。
Ejemplo · main:创建两个线程
▸ 原页截图 p.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。
Ejemplo · 数组一分为二,两线程各查一半
▸ 原页截图 p.37
La búsqueda la realiza una
查找由一个线程在这段数组上完成(图中左侧 0–4 号格,蓝色对应 th1)。
La búsqueda la realiza otra hebra sobre esta parte del array
查找由另一个线程在这段数组上完成(图中右侧 5–9 号格,橙色对应 th2)。
Ejemplo
标题:示例
Comunicación y Sincronización · 共享内存 vs 消息传递
▸ 原页截图 p.38
Los procesos en un programa concurrente habitualmente tienen que
并发程序中的进程通常必须通信并同步它们的动作。
La comunicación puede realizarse a través de la
通信可以通过共享内存完成。
O a través de algún mecanismo de
也可以通过某种消息传递机制完成。
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。
Comunicación y Sincronización · 同步条件
▸ 原页截图 p.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
这就是一个同步条件的例子:读之前必须等写完成。
四、并发编程的经典问题:售票机与临界区
p.40–p.48Problemas de la programación concurrente · 本章问题清单
▸ 原页截图 p.40
原子指令
临界区
互斥
Ejemplo:
例子:售票机(剧院售票窗口)
Pueden comprarse entradas desde distintas taquillas
观众可以从不同的售票窗口买票。
Problemas · 售票机模型:T1 || T2 || … || Tn
▸ 原页截图 p.41
Cada
每个售票窗口是一个进程 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?
这个解法正确吗?
Ejemplo · 错误轨迹:22 号座位卖了两次
▸ 原页截图 p.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
这是一条执行轨迹——树上的一条可能路径——它展示了错误。它足以证明程序不正确。
Ejemplo · 精化代码:先检查座位是否空闲
▸ 原页截图 p.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?
现在就对了吗?
Ejemplo · 精化后仍有错误轨迹
▸ 原页截图 p.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
我们处于和之前相同的情形,只不过现在把问题定位出来了:两次检查都通过,之后才各自置位。
Ejemplo · 原子指令与编译后的机器指令
▸ 原页截图 p.45
原子指令:处理器执行过程中不会被打断的指令。
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?
那么,如果被标记出的那段代码是原子的,会怎样?
Ejemplo · 若蓝框代码原子,错误轨迹不再可能
▸ 原页截图 p.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
如果蓝色框里的代码是原子的,那么这条错误轨迹就不可能发生。
Ejemplo · 原子之后唯一可能的交错
▸ 原页截图 p.47
El único
唯一可能的交错发生在 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 随后走错误提示分支,不会双卖)
Ejemplo · 临界区与互斥的形式定义
▸ 原页截图 p.48
Instrucciones atómicas: las que el procesador realiza sin interrupción.
原子指令:处理器执行时不会被打断的指令。
Sólo las instrucciones máquina son atómicas
只有机器指令才是原子的。
临界区:进程代码中应当以原子方式执行的那一部分。
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
当两个进程的临界区在时间上不能重叠(代码不能交错)时,就说它们必须以互斥方式执行。
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
图中标注:临界区(左右两个蓝框里圈出的同一段代码,各自属于一个进程)。
五、课程后续
p.49En el resto de la asignatura… · 后续课程路线
▸ 原页截图 p.49
Nos centraremos en:
我们将聚焦于:
Estudiar la
用不同机制研究并发,既用于系统编程,也关注它对下列领域的影响:
Sistemas Distribuidos y Paralelos
分布式系统与并行系统
Comunicaciones
通信
Estudiar otros mecanismos basados en
研究其他基于消息传递的机制
Estudiaremos la influencia del tiempo en los
我们将研究时间对实时系统的影响
专有名词速记表(A–Z)
共 82 条,覆盖全 49 页的高频术语。第三列点页码直接跳回原页;最后一列只写「一句话 + 最容易被扣分的点」。
| 西语术语 | 中文 | 页码 | 一句话记住 · 易错点 |
|---|---|---|---|
| A | |||
| abstracciones | 抽象 | p.6 | OS 把硬件细节包起来;越靠系统层抽象越薄——别把「层数多」当成抽象好。 |
| Ada | Ada | p.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.16 | SmartWatch 的 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.38 | send/receive 显式通信;同步内建在通信原语里。 |
| predecible | 可预测的 | p.13 | 执行时间可界定;易错:cache/中断让最坏时间很难估。 |
| predecibles | 可预测的 | p.5 | 实时系统必须可预测;与 fiabilidad、criticidad 一起背。 |
| primitivas | 原语 | p.9 | OS 提供的底层调用(时钟、延时);精度受时钟粒度限制。 |
| procesadores lógicos | 逻辑处理器 | p.27 | 建模用的虚拟处理器;几个逻辑处理器就是几条执行流。 |
| procesos | 进程 | p.2 | 并发抽象之一,与 eventos 并列;别与线程混为一谈。 |
| procesos/hebras | 进程/线程 | p.32 | P、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.14 | Java/C# 有 GC;Ada 走静态检查、Rust 走所有权。 |
| recursos | 资源 | p.5 | CPU、内存、I/O 都有限;并发就是共享与调度这些资源。 |
| registro | 寄存器 | p.11 | 外设寄存器被映射到内存地址,用指针+volatile 访问。 |
| registros | 寄存器 | p.11 | 内存映射 I/O 的核心;易错:漏 volatile 会被编译器优化掉读写。 |
| reloj del sistema | 系统时钟 | p.9 | currentTimeMillis 精度低且会跳变;测耗时用 nanoTime。 |
| reloj inteligente | 智能手表 | p.15 | SmartWatch 例子:接口+轮询,引出「并发 vs 事件」。 |
| rendimiento | 性能/吞吐 | p.33 | 并发的第一动机;易错:加速受串行部分上限约束。 |
| retrasos | 延迟 | p.9 | sleep 类延时精度有限,不能用于硬实时。 |
| Rust | Rust | p.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.8 | host 侧工具链(编译器、调试器);与 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 | 交错总数 | 规模感受 |
|---|---|---|
| 1 | 2 | 各 1 条指令,只有 AB / BA 两种顺序。 |
| 2 | 6 | 各 2 条指令,已经需要枚举 6 条 traza。 |
| 3 | 20 | 各 3 条指令,手工列举开始吃力。 |
| 4 | 70 | 各 4 条指令,超过人工可穷举的范围。 |
| 5 | 252 | 各 5 条指令,测试覆盖面迅速失控。 |
| 6 | 924 | 各 6 条指令,接近千条合法执行路径。 |
| 7 | 3432 | 各 7 条指令,靠穷举验证正确性已不现实。 |
处理器数量不改变交错总数,只决定这些交错是「真并行」还是「分时交错」——判定要点见下表。
| 处理器数 | P || Q 的执行形态 |
|---|---|
| 1 | 只能交错执行:仍是并发(concurrencia),但不是并行(paralelismo)。 |
| 2 | 两进程可同时推进:出现真正并行,但合法交错集合仍是 (m+n)!/m!·n! 条。 |
| 3 | 处理器多于进程时并行度饱和,多余处理器对本例无用。 |
易混概念对照 · 一张表分清
以下 8 组概念在课件里反复出现,考试最爱在这里设陷阱。左边是常被混用的两方,右边给出一句话分界。