操作系统个人复习笔记（十四）

文章目录

• 操作系统个人复习笔记（十四）
• 进程同步和进程互斥
• • 进程同步
  • 进程互斥
  • 进程互斥的软件实现方法
  • • 单标志法
    • 双标志先检查法
    • 双标志后检查法
    • Peterson算法
  • 进场互斥的硬件实现方法
  • • 中断屏蔽方法
    • TestAndSel指令
    • Swap指令

进程同步和进程互斥

进程同步

同步亦称直接制约关系，它是指为完成某种任务而建立的两个或多个进程，这些进程因为需要在某些位置上协调它们的工作次序而产生的制约关系。进程间的直接制约关系就是源于它们之间的相互合作。

进程互斥

为了实现对临界资源的互斥访问，同时保证系统整体性能，需要遵循以下原则:

1. 空闲让进。临界区空闲时，可以允许一个请求进入临界区的进程立即进入临界区;
2. 忙则等待。当已有进程进入临界区时，其他试图进入临界区的进程必须等待;
3. 有限等待。对请求访问的进程，应保证能在有限时间内进入临界区(保证不会饥饿);.
4. 让权等待。当进程不能进入临界区时，应立即释放处理机，防止进程忙等待。

• entry section（进入区）

  负责检查是否可进入临界区，若可进入，则应设置正在访问临界资源的标志（可理解为“上锁”），以阻止其他进程同时进入临界区

• critical section（临界区/临界段）

  访问临界资源的那段代码

• exit section（退出区）

  负责接触正在访问临街资源的标志（可理解为“解锁”）

• remainder section（剩余区）

  做其他处理

进程互斥的软件实现方法

单标志法

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

存在的问题：

假设有P0和P1两个进程，如果此时允许进入临界区的进程是P0，而P0一直不访问临界区，那么虽然此时临界区空闲，但是并不允许P1访问，因此违背了“空闲让进”原则。

双标志先检查法

设置一个布尔型数组flag[]，数组中各个元素用来标记各进程想进入临界区的意愿，比如“flag[0] = ture”意味着0 进程PO现在想要进入临界区。每个进程在进入临界区之前先检查当前有没有别的进程想进入临界区，如果没有，则把自身对应的标志flag[i]设为true,之后开始访问临界区。

存在的问题：

违反“忙则等待”原则，因为进入区的“检查”和“上锁”两个处理不是一气呵成的。“检查”后，“上锁”前可能发生进程切换。

双标志后检查法

双标志先检查法的改版。前一个算法的问题是先“检查”后“上锁”，但是这两个操作又无法一气呵成，因此导致了两个进程同时进入临界区的问题。因此，人们又想到先“上锁”后“检查”的方法，来避免上述问题。

存在的问题

双标志后检查法虽然解决了“忙则等待”的问题，但是又违背了“空闲让进”和“有限等待”原则，会因各进程都长期无法访问临界资源而产生“饥饿”现象。

Peterson算法

算法思想:双标志后检查法中，两个进程都争着想进入临界区，但是谁也不让谁，最后谁都无法进入临界区。GaryL. Peterson想到了一种方法，如果双方都争着想进入临界区，那可以让进程尝试“孔融让梨”，主动让对方先使用临界区。谁最后主动“谦让”，谁就等待

存在的问题

Peterson算法用软件方法解决了进程互斥问题，遵循了空闲让进、忙则等待、有限等待三个原则，但是依然未遵循让权等待的原则。

进场互斥的硬件实现方法

中断屏蔽方法

利用“开/关中断指令”实现（与原语的实现思想相同）

优点

简单、高效

缺点

不适用于多处理机，只适用于操作系统内核进程，不适用于用户进程，只能运行在内核态，这组指令如果能让用户随意使用会很危险

TestAndSel指令

简称TS指令，也有的地方成为TestAndSetLock，或TSL指令

TSL指令是用硬件实现的，执行过程不允许终端，只能一气呵成

优点

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

缺点

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

Swap指令

有的地方也称Exchange指令，或简称XCHG指令

Swap指令是用硬件实现的，执行过程不允许被众多，只能一气呵成

优点

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

缺点

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

文章知识点与官方知识档案匹配，可进一步学习相关知识算法技能树首页概览34282 人正在系统学习中