进程与线程

进程

进程是资源分配的基本单位 在某一个瞬间,CPU只能运行一个进程。

进程模型

计算机上所有可运行的软件,通常包括操作系统,被组织成若干 顺序进程 ,称为 进程

202031162023

程序与进程的关系

进程的创建

  • 导致进程创建的4种主要事件:

    • 系统初始化
    • 系统调用
    • 用户请求创建
    • 批处理作业初始化

守护进程 :停留在后台的线程

写时复制

进程的终止

  • 终止的条件:

    • 正常退出(自愿)
    • 出错退出(自愿)
    • 严重错误(非自愿)
    • 被其他进程杀死(非自愿)

进程的层次结构

UNIX中,进程创建一个新进程后,该进程称为其的父进程,它与它的所有后代组成一个 进程组 。 但在Windows中,进程之间没有层次关系,除了父进程在创建子进程时,会获得其的句柄,除此之外,没有任何联系。

进程的状态

  • 运行态(正在占用CPU)
  • 就绪态(可运行,但还没有运行)
  • 阻塞态(正在等待外部事件,如IO读取)

202031162835

像不像线程

调度程序 :负责切换进程的执行

进程的实现

为实现进程模型,操作系统维护一张表: 进程表

enter image description here

enter image description here

中断向量 :中断服务程序的入口地

多道程序设计模型

CPU利用率 = 1-P^n

n称为 多道程序设计的道数 P为CPU空转的概率

线程

线程是独立调度的基本单位

202031162222

线程的使用

使用线程的理由:

  • 更好描述程序的行为
  • 线程比进程更轻量
  • 提高性能

有限状态机

每个计算机都有一个被保存的状态,存在一个会发生且使得相关状态发生改变的事件集合

经典的线程模型

每个线程都有自己的堆栈

enter image description here

POSIX线程

一种线程标准,定义的线程包叫做 pthread

在用户空间中实现线程

  • 用户级线程的优点:

    • 可以定制自己的调度算法
  • 局限性:

    • 如何实现阻塞系统调用

enter image description here

在内核中实现线程

代价很大

混合实现

enter image description here

调度程序激活机制

上行调用

弹出线程

一个消息的到达导致系统创建一个处理该消息的线程

使单线程代码多线程化

全局变量的问题

进程与线程的区别

  • 线程不拥有资源,线程只能访问隶属进程的资源
  • 在同一进程中,线程的切换不会引起进程切换,从一个进程中的线程切换到另一个进程中的线程时,会引起进程切换
  • 创建进程的开销比创建线程大
    • 如创建撤销进程需要分配或回收资源,如内存空间、I/O 设备
    • 进行进程切换时,涉及当前执行进程 CPU 环境的保存及新调度进程 CPU 环境的设置,而线程切换时只需保存和设置少量寄存器内容

进程间通信

有关问题:

  • 进程之间传递信息
  • 进程之间的活动不会出现交叉
  • 进程之间运行的顺序

竞争条件

两个或多个进程读写某些共享数据,得到的结果取决于进程运行的精确时序

临界区

通过 互斥 来组织多个进程同时读写共享数据 把对共享内存进行访问的程序片段称为临界区

  • 任何两个进程不能同时处于临界区
  • 不对CPU的速度和数量做假设
  • 临界区外运行的进程不能阻塞其他进程
  • 不能使进程无限等待进入临界区

202031165214

同步与互斥

  • 同步:多个进程因为合作产生的直接制约关系,使得进程有一定的先后执行关系。
  • 互斥:多个进程在同一时刻只有一个进程能进入临界区

忙等待的互斥

  • 屏蔽中断:进程进入临界区后屏蔽所有中断,这样系统就无法切换到其他进程了
  • 锁变量
  • 严格轮换法: 连续测试一个变量直到某个值出现为止,称为 忙等待

    • 自旋锁:用于忙等待的锁
  • Peterson解法

  • TSL 指令 调用enter() -> 忙等待,直到获得锁 -> 调用leave()

睡眠与唤醒

优先级反转问题 生产者-消费者问题

信号量

信号量(Semaphore)是一个整型变量,可以对其进行原子操作的

  • down:如果信号量大于 0 ,执行 -1 操作;如果信号量等于 0,进程睡眠,等待信号量大于 0
  • up :对信号量执行 +1 操作,唤醒睡眠的进程让其完成 down 操作

互斥量

信号量的一个简化版本,值只能取0或者1

自旋锁是忙等待的体现

  • 快速用户区互斥量futex
  • pthread中的互斥量 条件变量

死锁

两个进程互相等待对方,一直阻塞下去

管程

一个管程由过程、变量、数据结构等组合成的一个集合

monitor ProducerConsumer
    integer i;
    condition c;

    procedure insert();
    begin
        // ...
    end;

    procedure remove();
    begin
        // ...
    end;
end monitor;

在一个时刻只能有一个进程使用管程

像不像一个类(有属性,有行为)

进程可以在任何时候通过管程间接获取数据,但是不能直接获取数据

消息传递

send(目的,&msg);
receive(,&msg);

用消息传递解决生产者-消费者问题 消息传递接口

屏障

当一个进程到达屏障时,就会被阻拦,直到所有进程都到达屏障为止

enter image description here

避免锁:读-复制-更新(RCU)

要么读取旧版本,要么读取新版本

调度

调度程序与调度算法

简介

  • 进程行为

    IO活动与CPU计算

    • 计算密集型
    • IO密集型

enter image description here

  • 何时调度

    • 运行一个新进程后
    • 一个进程退出后
    • 一个进程阻塞后
    • IO中断

非抢占式 :直到一个进程阻塞或者主动释放CPU

抢占式 :运行一段时间,后调度程序进行调度挑选下一个运行的进程

调度算法

  • 调度算法的目标

enter image description here

批处理系统

在该系统中,调度算法目标是保证吞吐量和周转时间

  • 先来先服务 first-come first-serverd(FCFS)
  • 短作业优先 shortest job first(SJF)
  • 最短剩余时间优先 shortest remaining time next(SRTN)

交互式系统

在该系统中调度算法的目标是快速地进行响应

  • 时间片轮转

每次调度时,把 CPU 时间分配给队首进程,该进程可以执行一个时间片。当时间片用完时,由计时器发出时钟中断,调度程序便停止该进程的执行,并将它送往就绪队列的末尾,同时继续把 CPU 时间分配给队首的进程 该算法效率与时间片大小有关,时间片过于小,会造成进程切换频繁,过大实时性无法得到保证

  • 优先级调度

为每个进程分配一个优先级,按优先级进行调度 为了防止低优先级的进程永远等不到调度,可以随着时间的推移增加等待进程的优先级

  • 多级反馈队列

它设置了多个队列,每个队列时间片大小都不同,例如 1,2,4,8,..。进程在第一个队列没执行完,就会被移到下一个队列,在这种情况下,就能有效避免一个进程需要执行连续多个时间片而造成的切换频繁问题

202031164556

  • 保证调度
  • 彩票调度
  • 公平分享调度

实时系统

硬实时 :必须满足一定的截止时间

软实时 :可以容忍一定的超时

策略和机制

调度机制与调度策略分离

线程调度

  • 用户级调度
  • 内核级调度

enter image description here

经典进程同步问题

哲学家就餐问题

五个哲学家围着一张圆桌,每个哲学家面前放着食物。哲学家的生活有两种交替活动:吃饭以及思考。当一个哲学家吃饭时,需要先拿起自己左右两边的两根筷子,并且一次只能拿起一根筷子

20203117217

读者-写者问题

允许多个进程同时对数据进行读操作,但是不允许读和写以及写和写操作同时发生

进程通信

  • 进程同步:控制多个进程按一定顺序执行;
  • 进程通信:进程间传输信息

为了能够达到进程同步的目的,需要让进程进行通信

管道

  • 只支持半双工
  • 只支持父子进程或者兄弟进程

202031171046

FIFO(命名管道)

202031183319

有名管道以磁盘文件的方式存在,可以实现本机任意两个进程通信

消息队列

  • 消息队列可以独立于读写进程存在,从而避免了 FIFO 中同步管道的打开和关闭时可能产生的困难
  • 避免了 FIFO 的同步阻塞问题,不需要进程自己提供同步方法
  • 读进程可以根据消息类型有选择地接收消息,而不像 FIFO 那样只能默认地接收

信号量

用于为多个进程提供共享对象的访问

共享存储

多个进程可以使用一个给定的存储区进行通信

可以使用文件或者内存

套接字

用于不同机器之间的进程通信

results matching " "

No results matching " "

results matching " "

No results matching " "