程序设计语言-北京大学数学科学学院.pdfVIP

程序设计语言 Programming Languages 裘宗燕 数学学院信息科学系 2012年2-6月 第9章并发性 为什么需要并发性？ 简单历史 并发程序的基本问题 并发程序设计基础 进程与线程 共享存储器模型 消息传递模型 进程间通讯 2012年5月 2 为什么（需要）并发 顺序程序：在运行中只有一个活动的执行上下文 顺序执行是命令式程序的基本特性，也出现在说明性程序的执行中 并发程序运行中可能存在多个同时活动的执行上下文，多个“控制线程” 三方面重要原因： • 为更好反映问题的逻辑结构。许多程序里，特别是各种服务器和图形应 用，需要维护一批基本上相互独立的“作业”的轨迹。构造这种程序时， 最简单最合逻辑的方式是用一个独立的控制线程表示一个作业 • 需要应对多台独立设备。OS 可能在任何时候被中断，为此需要用一个 上下文表示中断前的工作，用另一上下文表示中断本身。实时控制系统 常需要处理多台独立的外部设备（它们各有独立的控制线程），还需要 与其他处理器上运行的线程交互，以实现系统的整体行为 • 通过并发可能提高系统性能。有些程序本质上可能不需要并行，但使用 多个处理器同时工作可能提高系统性能，得到很大速度提升 2012年5月 3 并发性 并发性不是新想法 • 有关并发程序设计的大部分最基础的理论工作从20 世纪60 年代开始提 出和研究，70 年代其基础理论框架已经基本完成 • Algol 68 已包含了有关并发性的程序设计特征 对并发性的广泛兴趣是近年的新现象，原因：低价的多处理器系统，图形、 多媒体和互联网应用的发展（用并发线程描述特别自然）等 并发性问题出现在许多不同层次上 • 数字逻辑层几乎所有事情都是并行的，信号在大量连线上同时传播 • 在现代处理器里，流水线和超标量特征就是为了利用指令级并行 • 专用向量处理器实现一种中层的数据并行；各种多处理器系统中存在 很多并行运行的进程；在互联网上一切事情都并发地进行 • 本章集中关注中尺度和大尺度的并发性，这些并发性由程序员可见的 结构的语义表示，多处理器的机器可以利用这种并发性 2012年5月 4 并发性：简单历史 早期计算机是单用户机器，一个用户工作时占用整个计算机硬件 单用户模式成本太高。计算机系统转到另一模式：用户在线下创建作业 （输入源代码）；操作员维护一批作业，启动作业执行。每个程序最后把 控制转回驻留的监控程序，它立即读入下一程序后令其执行 商务应用需要读入大量数据，计算相对简单。程序执行到I/O 时处理器 给设备发命令后进入忙等待，可能导致大量时间闲置 为利用忙等待的闲置周期，开发了中断驱动的I/O 和多道程序设计技术 （多个应用可同时驻留内存）。两项发明都需要硬件支持。前者要求实 现中断，后者要求内存保护，保证一个程序的错误不破坏其他程序 OS 维持多个程序的轨迹，知道哪些正在等I/O 完成，哪些可运行 程序在运行中需要I/O 时把控制传给OS，OS 给设备发命令后立即把控 制传给另一可运行程序。设备完成时发中断使控制回到OS 。OS 知道等 待这个IO 的程序又可运行了，并从可运行程序里选一个执行。这样，只 有内存里的所有程序都在等I/O 时处理器才会闲置 2012年5月 5 中断和竞态 中断驱动的I/O 把并发性引进OS：中断可能随时发生，包括控制已经位 于OS 里的情况，