Execution

Program

  • 就是一个指令序列
  • 程序在内存中：存放程序段、数据段
  • Input、Compute、Print
  • 执行方式:
    • 顺序执行
      • 内存、CPU、系统资源都属于单个程序
    • 并发执行
      • PCB 进程控制块，放在内存中。用来描述进程的各种信息
      • 内存中存放程序段，数据段

进程

进程是资源分配的最小单位
程序段、数据段、PCB三部分组成了进程实体。
程序段存放程序代码，数据段存放运行时使用、产生的运算数据，如全局变量、局部变量、宏定义常量，都在数据段。
进程是一个动态过程

进程的组成

  • PCB
    • 进程描述信息
      • PID 进程标识符：进程被创建时分配的唯一的、不重复的ID，用于区分不同进程
      • UID 用户标识符
    • 进程管理控制信息

进程的组织（多个进程要以什么方式组织起来）

  1. 链接方式

    • 按照进程状态将PCB分为多个队列

    • 操作系统持有指向各个队列的指针

    • 执行指针：指向当前处于运行态的进程。（单CPU中，同一时刻只会有一个进程处于运行状态）

    • 就绪队列指针：指向当前处于就绪状态的进程。（优先级高的放在前面）
    • 阻塞队列指针：指向当前处于阻塞状态的进程，很多操作系统还会根在·据阻塞原因不同，再分为多个阻塞队列。

  2. 索引方式

    • 按照进程状态建立几张索引表
    • 操作系统持有指向各个索引表的指针

进程的特征

进程相比程序，有特征：

  • 动态性（基本特征）：进程是程序的一次执行过程，是动态地产生、变化和消亡的
  • 并发性：内存中有多个进程实体，各进程可并发执行
  • 独立性：进程是能独立运行、独立获得资源、独立接受调度的基本单位。（是资源分配、接受调度（有了线程以后就不是了）的基本单位）
  • 异步性：各进程按各自独立、不可预知的速度向前推进，操作系统要提供“进程同步机制”来解决异步问题。（并发程序执行结果的不确定。）
  • 结构性：每个进程配置一个PCB。从结构上看，进程由程序段、数据段、PCB组成

进程的状态与转换

进程的状态

  • 运行态（Running）：占有CPU，在CPU上运行。（单核就只能有一个，双核可以同时有两个）
  • 就绪态（Ready）：已经具备运行条件，但没有空闲CPU，就暂时不能运行。（除了CPU，什么资源都已经有了）
  • 阻塞态（Waiting/Blocking）：因等待某事件而暂时不能运行。
  • 创建态（New）：进程正被创建，操作系统分配资源、初始化PCB
  • 终止态（Terminated）：进程从系统中撤销，操作系统回收资源、撤销PCB

进程的转换


进程控制

进程控制：实现进程状态的转换
进程控制通过原语实现，原语用关/开中断来实现。原语是一种特殊的程序，原语的执行必须一气呵成，不能中断（使用开中断、关中断指令实现）。

进程通信

  1. 进程通信：进程之间的信息交换

  2. 共享存储

    • 内存分配一个共享空间，两个进程通过共享空间交流。
    • 对于共享空间的访问必须是互斥的，不能同时写
    • 基于数据结构的共享：低级通信方式，速度慢，限制多
    • 基于存储区的共享：划分存储区，进程交流的方式由进程决定

  3. 消息传递

    • 以格式化消息来传递
    • 消息头、消息体组成（如计算机网络的报文）
      • 直接通信方式：消息直接挂到消息缓冲队列的队尾
      • 间接通信方式：消息先发送到中间实体（信箱），如电子邮件系统（邮件服务器）
  4. 管道通信
  • 管道：内存中固定大小的缓冲区
  • 管道只能实现半双工通信，某个时间只能单向传输。如果同时双向通信，需要设置两个管道
  • 各个进程要互斥地访问管道
  • 数据以字符流写入管道，管道写满，write()就阻塞，管道读空，read()就阻塞
  • 如果没写满，就不允许读。如果没读空，就不允许写
  • 数据一旦读出，就会被从管道中抛弃，则读管道的进程只能有一个

线程、多线程模型

线程

线程是一个基本的CPU执行单元，也是程序执行流的最小单位。线程提升了系统的并发度，使得进程内也能并发处理各种任务。
引入线程后，进程是资源分配的基本单位，线程是调度的基本单位。
引入线程后，各线程间也能并发，提升并发度。
引入线程后，并发带来的系统开销减少。主要是进程并发需要陷入内核态，线程就不需要

线程的属性

线程是CPU调度的单位
多CPU计算机中，各个线程可占用不同的CPU
每个线程都有一个线程ID、线程控制块（TCB）
线程也有 就绪、阻塞、运行 三种基本状态
线程几乎不拥有系统资源
同一进程的不同线程之间共享进程的资源
由于共享内存地址空间，线程间通信不需要系统干预

线程的实现方式

用户级线程

线程在用户态，操作系统内核看不到

内核级线程

线程运行在内核态，操作系统内核可以看得见

组合方式

n个用户级线程映射到m个内核级线程上

多线程模型

多对一模型

多个用户级线程映射到一个内核级线程，每个用户进程对应一个内核级线程

  • 优点：用户级线程的切换在用户空间完成，线程管理开销小，效率高
  • 缺点：用户级线程被阻塞，整个进程都会被阻塞，并发度不高，多个线程不能再多核机器并行运行

    一对一模型

    一个用户级线程映射到一个内核级线程，每个用户进程有与用户线程同等数量的内核级线程
  • 优点：一个线程被阻塞，别的线程还能执行，并发能力强。
  • 缺点：一个进程占用多个内核级线程，线程管理成本高，开销大

    多对多模型

    n用户级线程映射到m个内核级线程（n>=m），每个用户进程对应m个内核级线程
    同时克服了一对一模型的缺点和多对一模型的缺点。

Modeling Multiprogramming 多道程序设计模型

采用多道程序提高CPU利用率
$CPU utilization = 1 - p^{n}$ （p是进程等待IO的时间与其在内存中的时间比）


例子：对于一个512M内存的计算机，操作系统占128M，80%时间I/O，则CPU 利用率为=1-0.83=49%

线程信号控制

Signal 被用来在UNIX系统中唤醒进程，当有事件发生时
Signal

  • Signal is generated by particular event
  • Signal is delivered to a process
  • Signal is handled

方式：

  • 将信号传送给信号量应用的线程
  • 将信号传递给进程的每个线程
  • 将信号传递给进程中特定线程
  • 指定一个特定线程来接受进程的所有信号

进程模型到线程模型的迁移

许多已有的程序是为单线程编写的，把这些程序改写为多线程会产生许多问题

原因

  1. 对线程来说的全局变量对整个程序来说并不是全局的
  2. 许多库过程是不可重入的
  3. 有些信号逻辑上是线程专用的，而有些不是
  4. 堆栈的管理

例子

  1. UNIX维护的errno全局变量，对线程来说是全局的变量，若两个线程先后访问，第二次会修改第一次的结果
  2. UNIX的malloc()函数，在进行内存分配时，内存指针可能会指向不确定的位置，如果发生线程切换，会导致指针异常从而引起崩溃
  3. 例如某个线程调用信号alarm，如果线程完全由用户实现，内核根本不知道有线程的存在，很难将信号发送给正确的线程
  4. 如果一个堆栈溢出时，内核只需要为该进程提供更多的堆栈。当一个进程有多个线程时，就必须有多个堆栈。

解决方案

  1. 禁用全局变量或者是为每个线程建立一份单独的全局变量拷贝区
  2. 为每个过程提供一个包装器，该包装器设置一个二进制位来标志某个库正在使用中，在先前的调用为返回前，任何调用该库的线程都会被阻塞。（该方法会降低程序的并行性）