操作系统-进程(二)
2020 年 11 月 25 日 287 1987 字 暂无评论

01.进程同步与互斥

1.1概述

  • 进程同步

    • 并发性带来了异步性,有时需要通过进程同步解决这种异步问题。
    • 有的进程之间需要相互配合地完成工作,各进程的工作推进需要遵循一定的先后顺序。
  • 进程互斥

    • 对临界资源的访问,需要互斥的进行。
    • 即同一个时间段内只能允许一个进程访问该资源。
  • 进程互斥的四个部分

    • 进入区

      • 检查是否可进入临界区,若可进入,需要“上锁”。
    • 临界区

      • 访问临界资源的那段代码。
    • 退出区

      • 负责“解锁”。
    • 剩余区

      • 其余代码部分。
  • 进程互斥需要遵循的原则

    • 空闲让进

      • 临界区空闲时,应允许一个进程访问。
    • 忙则等待

      • 临界区正在被访问时,其他试图访问的进程需要等待。
    • 有限等待

      • 要在有限时间内进入临界区,保证不会饥饿。
    • 让权等待

      • 进不了临界区的进程,要释放处理机,防止忙等。

1.2进程互斥的软件实现方法

  • 单标志法

    • 两个进程在访问完临界区后会把使用临界区的权限转交给另一个进程。
    • 每个进程进入临界区的权限只能被另一个进程赋予
  • 存在问题

    • 违背“空闲让进”原则

  • 双标志先检查法

    • 设置一个布尔型数组flag[],数组中各个元素用来标记进程想进入临界区的意愿。
  • 存在问题

    • 违背了“忙则等待”原则

  • 双标志后检查法

    • 双标志前检查法改版,先上锁后检查。
  • 存在问题

    • 解决了“忙则等待”原则
    • 违背了“空闲让进”和“有限等待”原则

  • Peterson算法

    • 如果双方都争着想进入临界区,主动让对方先使用临界区。
  • 存在问题

    • 遵循了“空闲让进”、“忙则等待”和“有限等待”三个原则。
    • 违背了“让权等待”原则

1.3进程互斥的硬件实现方法

  • 中断屏蔽方法

    • 利用“开/关中断指令”实现。
  • 优点

    • 简单、高效。
  • 缺点

    • 不适用于处理机。
    • 只适用于操作系统内核进程,不适用于用户进程。

  • TestAndSet指令

    • 简称TS指令,或TestAndSetLock指令,或TSL指令
    • TSL指令是用硬件实现的,执行的过程不允许被中断。
  • 优点

    • 实现简单,无需像软件实现方法那样严格检查是否会有逻辑漏洞。
    • 适用于多处理机环境。
  • 缺点

    • 不满足“让权等待”原则。
    • 暂时无法进入临界区的进程会占用CPU并循环执行TSL指令,从而导致“忙等”。

  • Swap指令

    • 也称Exchange指令,或简称XCHG指令。
    • Swap指令是用硬件实现的,执行的过程不允许被中断,只能一气呵成。
  • 优点

    • 实现简单,无需像软件实现方法那样严格检查是否会有逻辑漏洞。
    • 适用于多处理机环境。
  • 缺点

    • 不满足“让权等待”原则。
    • 暂时无法进入临界区的进程会占用CPU并循环执行Swap指令,从而导致“忙等”。

02.信号量机制

  • 用户进程可以通过使用操作系统提供的一对原语来对信号量进行操作,从而很方便的实现了进程互斥、进程同步。
  • 信号量其实就是一个变量(可以是一个整数,也可以是更复杂的记录型变量),可以用一个信号量来表示系统中某种资源的数量,比如:系统中只有一台打印机,就可以设置一个初值为1的信号量。
  • 原语是一种特殊的程序段,其执行只能一气呵成,不能被中断。原语是由关中断/开中断指令实现。
  • 一对原语wait(S)原语和signal(S)原语,可以把原语理解为我们自己写的函数,函数名分别为wait和signal,括号里的信号量S其实就是函数调用时传入的一个参数。
  • wait、signal原语常简称为P、V操作(来自荷兰语proberen和verhogen)。因此常把wait(S)、signal(S)两个操作分别写为P(S)、V(S)

2.1整形信号量

  • 用一个整数型的变量作为信号量,用来表示系统中某种资源的数量
  • 整形信号量与普通整形变量的区别:对信号量只能执行初始化、P、V三种操作。
  • 整形信号量存在的问题:不满足让权等待原则

2.2记录型信号量

  • 整形信号量的缺陷是存在“忙等”问题,因此提出“记录型信号量”,记录型数据结构表示的信号量。
  • S.value表示某种资源数,S.L指向等待该资源的队列。
  • P操作中,一定是先S.value--,之后可能需要执行block原语
  • V操作中,一定是先S.value++,之后可能需要执行wakeup原语
  • 注意:要能够自己推断在什么条件下需要执行block或wakeup
  • 可以用记录型信号量实现系统资源的“申请”和“释放”。
  • 可以用记录型信号量实现进程互斥、进程同步。

2.3实现进程互斥

  • 分析问题,确定临界区。
  • 设置互斥信号量,初值为1.
  • 临界区之前对信号量执行P操作。
  • 临界区之后对信号量执行V操作。

注意:对不同的临界资源需要设置不同的互斥信号量P、V操作必须成对出现。缺少P(mutex)就不能保证临界资源的互斥访问。缺少V(mutex)会导致资源永不被释放,等待进程永不被唤醒。

2.4实现进程同步

  • 分析问题,找出哪里需要实现“一前一后”的同步关系。
  • 设置同步信号量,初始值为0。
  • 在“前操作”之后执行V操作
  • 在“后操作”之前执行P操作

2.5实现前驱关系

  • 分析问题,画出前驱图,把每一对前驱关系都看成一个同步问题。
  • 为每一对前驱关系设置同步信号量,初值为0。
  • 在每个“前操作”之后执行V操作。
  • 在每个“后操作”之前执行P操作。

03.生产者消费者问题

  • 生产者、消费者共享一个初始为空、大小为n的缓冲区
  • 只有缓冲区没满时,生产者才能把产品放入缓冲区,否则必须等待
  • 只有缓冲区不空时,消费者才能从中取出产品,否则必须等待
  • 缓冲区是临界资源,各进程必须互斥地访问

  • 实现互斥的P操作一定要在实现同步的P操作之后
  • V操作不会导致进程阻塞,因此两个V操作顺序可以交换

04.多生产者-多消费者

  • 互斥关系(mutex=1)

    • 对缓冲区(盘子)的访问要互斥地进行。
  • 同步关系(一前一后)

    • 父亲将苹果放入盘子后,女儿才能取苹果。
    • 母亲将橘子放入盘子后,儿子才能取橘子。
    • 只有盘子为空时,父亲或母亲才能放入水果。

总结:在生产者-消费者问题中,如果缓冲区大小为1,那么有可能不需要设置互斥信号量就可以实现互斥访问缓冲区的功能。

05.吸烟者问题

06.读者-写者问题

  • 允许多个读者可以同时对文件执行读操作。
  • 只允许一个写者往文件中写信息。
  • 任一写者在完成写操作之前不允许其他读者或写者工作。
  • 写者执行写操作前,应让已有的读者和写者全部退出。

07.哲学家进餐问题

  • 哲学家进餐问题的关键在于解决进餐死锁
  • 这些进餐之间只存在互斥关系,但是与之前接触到的互斥关系不同的是,每个进程都需要同时持有两个临界资源,因此就有“死锁”问题的隐患。

版权属于:zfh

本文链接:http://zfhblog.com/index.php/archives/184/



评论已关闭