操作系统-进程与线程

• 进程（Process）
• 线程（Thread）
• 进程间通信（Inter Process Communication, IPC）
• 调度（scheduler）
• IPC问题

进程（Process）

• 伪并行：在单核CPU上每个进程拥有自己的虚拟CPU，自己的程序计数器
• 进程的创建：
  • 系统初始化：
    • 前台进程：与用户交互的进程
    • 守护进程：后台进程，在请求到达时唤醒该进程以服务请求
    • ps程序：UNIX系统中用于列出正在运行的进程
  • 正在运行的程序执行了创建进程的系统调用
  • 用户请求创建一个新进程
  • 一个批处理作业的初始化
  • UNIX中子进程与父进程可以共享不可写的内存区，或者共享所有内存区但必须通过 写时复制 来确保修改发生在私有内存区域

    可写的内存是不可以共享的

• 进程的终止：
  • 正常退出（自主）：exit()
  • 出错退出（自主）
  • 严重错误（非自主）
  • 被其他进程杀死（非自主）：kill()
• 进程的层次结构：UNIX中父进程与子进程的关联，系统启动时init进程出现在启动映像中，开始运行的时候读入一个说明终端数量的文件，为每个终端创建一个进程等待用户登录，登录成功后这个登录进程就执行一个shell用于接收命令，这些命令又会创建新的进程，以此类推
• 进程的状态：
  • 运行态（实际占用CPU）
  • 就绪态（可运行，但因为其他进程正在运行而暂停）
  • 阻塞态（等待输入）
• 进程的实现：
  • 进程表：每个进程占用一个进程表项，包含了程序计数器、堆栈指针、内存分配情况、优先级、PID等信息
  • 中断发生后操作系统的底层工作步骤：
    1. 硬件push进堆栈程序控制器
    2. 硬件从中断向量（在内存底部的固定区域，包含中断服务程序的入口地址）装入新的程序计数器
    3. 汇编语言过程保存寄存器值
    4. 汇编语言过程设置新的堆栈
    5. C中断服务例程运行
    6. 调度程序决定下一个将运行的进程
    7. C过程返回至汇编代码
    8. 汇编语言过程开始运行新的当前进程
• 多道程序设计模型：
  • 描述多道程序设计的道数 n 与CPU利用率的关系
  • 假设一个进程等待I/O操作的时间与停留在内存中的时间的比为 p, 则当内存中同时有n个进程时CPU空转的概率是 p^n，所以: CPU利用率 = 1 - p^n

线程（Thread）

• 可以共享公共内存
• 有限状态机：由多个状态和使得相关状态发生改变的事件结合构成
• 构造服务器的三种方法：

• 进程和线程的内容关系：
  • 进程中所有线程共享的部分：地址空间、全局变量、打开文件、子进程、即将发生的定时器、信号与信号处理程序、用户信息
  • 每个线程独有部分：程序计数器、寄存器、堆栈、状态
• POSIX线程：IEEE标准定义的线程包为 pthread
• 实现
  • 用户级线程包：线程表在用户空间（每个进程中）
  • 内核管理的线程包：线程表在内核空间（不在每个进程中）
  • 混合实现：使用内核级线程，再将用户级线程与内核级线程多路复用起来
  • 调度程序激活（scheduler activation）
  • 弹出式线程

进程间通信（Inter Process Communication, IPC）

• 竞争条件（race condition）：多个进程几乎同时读写共享数据时，最后的结果取决于进程运行的精确时序。
• 临界区（critical section）：
  • 为了避免竞争条件，需要实现进程之间的互斥（mutual exclusion）：
  • 临界区的定义：对共享内存进行访问的程序片段
• 睡眠与唤醒：
  • sleep、wakeup、count
  • 生产者-消费者问题：一个缓冲区，前者存数据，后者取数据，缓冲区内的数据项数目为count，由于count未加限制，会出现竞争条件
  • 解决方案：唤醒等待位（有限个进程）
• 信号量（semaphore）：可以取0（没有唤醒操作）或者正值（有一个或多个唤醒操作）
  • down：检查信号量，大于0，则信号量减1，等于0，则进程睡眠，此时down操作还没有结束，down操作中的检查数值、修改变量值，睡眠操作，都是原子操作
  • up：使信号量增1，如果此时有进程在该信号量上睡眠，由系统选择其中一个完成其未完成down操作，使得信号量仍为0
• 互斥量（mutex）：
  • 可以处于两种状态：加锁lock，解锁unlock，一般用以个整型量表示，0表示解锁，其他值表示加锁。
  • 用户级线程包：mutex_lock,mutex_unlock实现如下：

mutex_lock:
    TSL REGISTER,MUTEX  将互斥信号量复制到寄存器，置1
    CMP REGISTER,#0     互斥信号量是0吗？
    JZE ok              如果为0，返回
    CALL thread_yield   互斥信号量非0；调度另一个线程
    JMP mutex_lock      稍后再试
ok: RET                 返回调用者；进入临界区

mutex_unlock:
    MOVE MUTEX,#0       将mutex置0
    RET                 返回调用者

• 管程（monitor）：比信号量更容易保证并行编程的正确性，但管程是一个编程语言概念。
• 消息传递（message passing）
• 屏障（barrier）
• 避免锁（read-copy-update，RCU）

调度（scheduler）

IPC问题

• 哲学家就餐问题
• 读者-写者问题