操作系统 | Rainnn の Blog

操作系统的基本特征

①并发：两个或多个事件在同一时间间隔内发生（宏观上同时发生，微观上交替发生）

②共享：共享指资源共享，指系统中的资源可供内存中多个并发执行的进程共同使用。

③虚拟：通过时分复用/空分复用将一个物理实体变为若干逻辑上的对应物（用户错觉以为自己有一个多余的）。

时分复用：利用设备为一用户服务的空闲时间，服务其它用户。分为虚拟处理机器（为进程）、虚拟设备技术（为I/O）。

空分复用：利用存储器的空闲空间分区域存放和运行多道程序。引入虚拟存储可逻辑上扩大存储器容量（本质上是时分），使一道程序在远小于它的内存空间中运行（用户程序各个部分分时进入内存运行）。

④异步：进程的执行不是一贯到底的，而是走走停停，以不可预知的速度向前推进，这就是进程的异步（请求某种资源，如打印机，需要等待）

操作系统的作用

操作系统处于用户和计算机硬件之间；

管理多种硬件资源和软件资源，如处理机、存储器、I/O设备、文件等；

隐藏硬件操作细节（实现对硬件资源的抽象）

操作系统定义：操作系统是一组控制和管理计算机硬件和软件资源、合理地对各类作业进行调度，以及方便用户的程序集合。

双重模式操作：用户态（模式）内核态（模式）（user mode、kernel mode）

用户态：执行用户程序的状态

内核态：执行内核程序的状态

当计算机系统表示用户应用程序正在执行，系统处于用户模式。

然而，当用户应用程序需要操作系统的服务(通过系统调用)，它必须从用户模式转换过来执行请求。

系统引导时，硬件开始处于内核模式。用户进程在用户态下运行，一旦出现陷阱或中断，硬件就从用户态切换到核心态。

双重模式操作提供了保护操作系统和用户程序不受错误用户程序影响的手段。实现方法为：将能引起损害的机器指令作为特权指令（privileged instructuion）。如果在用户模式下试图执行特权指令，那么硬件并不执行该指令，认为该指令非法，并将其以陷阱的形式通知操作系统，切换为kernel mode，由操作系统代为完成。

系统调用（system call）

操作系统内核提供一系列预定功能，通过一组称为系统调用的接口呈现给编程人员，系统调用把应用程序的请求传给内核，系统调用相应的内核函数完成所需的处理，将处理结果返回给应用程序。C 或 C++编写。系统调用是内核的一部分。

系统调用过程：传参——陷入指令/trap/访管指令——操作系统切换至kernel mode处理系统调用——返回应用程序

系统调用大致分为五大类：进程控制，文件管理，设备管理，信息维护和通信

向操作系统传递参数的几种方式

通过寄存器(registers)来传递参数

将参数存在内存的块(blocks)和(table)表中，并将块的地址通过寄存器来传递

参数通过程序放在(placed)或压入(pushed)堆栈(stack)中，并通过操作系统弹出(popped off)

采用块或堆栈方法，不限制所传递参数的数量或长度。

程序、进程、线程的基本概念以及区别？

程序本身不是进程；程序只是被动实体，如存储在磁盘上包含一系列指令的文件内容(常被称为可执行文件)，而进程是活动实体

进程：程序的一次执行，是系统进行资源分配调度的一个独立单位。

线程：进程的一个实体，是CPU调度分配的基本单位，线程之间基本上不拥有系统资源。

一个程序至少有一个进程，一个进程至少有一个线程，资源分配给进程，同一个进程下所有线程共享该进程的资源。

进程的五个基本特征

动态性：是进程的最基本的特征，表现在进程由创建而产生，由调度而执行，因得不到资源而暂停执行，由撤销而消亡。

并发性：多个进程实体同存于内存中，能在一段时间内同时执行。

独立性：进程实体是一个能独立运行的基本单位，同时也是系统中独立获得资源和独立调度的基本单位。

异步性：指进程按各自独立的、不可预知的速度向前推进；或者说，进程按异步方式运行。

结构特征：从结构上看，进程实体由程序段、数据段以及进程控制块（PCB）组成，这三部分也称为进程映像。

进程有哪几种状态，状态之间的转换

进程在执行时会改变状态(state)。进程状态在某种程度上是由当前活动所定义的。每个进程可能处于下列状态之一：

新的：进程正在被创建

运行：指令正在被执行。

等待：进程等待某个事件的发生(如I/O完成或收到信号)

就绪：进程等待分配处理器

终止：进程完成执行

new: The process is being created

running: Instructions are being executed

waiting: The process is waiting for some event to occur

ready: The process is waiting to be assigned to a processor

terminated: The process has finished execution

running→ready中断是被动的

running→waiting 是主动的

为什么在转换图中没有就绪到阻塞和阻塞到执行的转换方向？

没有就绪->阻塞：就绪状态没有占用处理机。不经过执行，其状态便不会改变

没有阻塞->执行：阻塞进程完成I/O后，会先进入就绪队列，才会被调度进程选中，变为执行态

PCB及其作用

进程控制块（process control block，PCB）：每个进程在操作系统内用进程控制块来表示，它包含许多与一个特定进程相关的信息。

进程状态（包括new ready running waiting terminated）

程序计数器（表示进程要执行的下个指令的地址）

CPU寄存器（包括累加器、索引寄存器、堆栈指针、通用寄存器）

CPU调度信息（包含进程优先级、调度队列的指针）

内存管理信息（根据所使用的内存系统，包含基址和界限寄存器的值、页表或段表）

记账信息（CPU时间、实际使用时间、时间界限）

I/O状态信息（包含给进程的I/O设备列表、打开的文件列表）

PCB的作用：反映进程的动态特征，描述进程的执行情况，使操作系统能控制进程的运行。

区别并发（concurrency）和并行（parallel）

并发：一个处理器处理多个任务，实际上先后执行，看起来同时发生

并发的基本单位是线程但“程序由独占处理器执行”在现代多处理器系统上不成立，对于单处理器多线程来说，线程在运行时可能被中断，切换到另一个线程；对于多处理器线程来说，线程就是并行执行的解决方法：线程池

并行：多个处理器（或单处理器的多核）同时处理多个不同任务，物理上真正同时

调度队列（作业队列、就绪队列、设备队列）

作业队列（job queue）：该队列包括系统中的所有进程。（在外存中）

就绪队列（ready queue）：驻留在内存中就绪的、等待运行的进程保存在就绪队列中。

设备队列（device queues）：等待特定I/O设备的进程列表称为设备队列。

进程选择：调度程序（短期、中期、长期）

进程选择是由相应的调度程序（scheduler）来执行的。

通常对于批处理系统，进程更多地是被提交，而不是马上执行。这些进程被放到大容量存储设备(通常为磁盘)的缓冲池中,保存在那里以便以后执行。

长期调度程序（long-term scheduler）或作业调度程序（job scheduler）从该池中选择进程，并装入内存以准备执行。

短期调度程序（short-term scheduler）或CPU调度程序从准备执行的进程中选择进程，并为之分配CPU。

长期调度程序执行频率低，短期调度程序执行频率高。长期调度程序控制多道程序设计的程度（内存中的进程数量）

中期调度程序 (medium-term scheduler)的核心思想是能将进程从内存(或从 CPU 竞争)中移出，从而降低多道程序设计的程度。

介绍一下上下文切换

将CPU 切换到另一个进程需要保存当前进程的状态并恢复另一个进程的状态，这一任务称为上下文切换 (context switch)。当发生上下文切换时，内核会将旧进程的状态保存在其PCB 中，然后装入经调度要执行的并已保存的新进程的上下文。上下文切换时间是额外开销（pure overhead）

一次系统调用中发生了几次CPU上下文切换？

两次。

从用户态到内核态的转变，需要通过系统调用来完成。

一次系统调用中的过程：

保存 CPU 寄存器里原来用户态的指令位

为了执行内核态代码，CPU 寄存器需要更新为内核态指令的新位置

跳转到内核态运行内核任务

当系统调用结束后，CPU 寄存器需要恢复原来保存的用户态，然后再切换到用户空间，继续运行进程

所以一次系统调用中发生了两次CPU上下文切换（用户态-内核态-用户态）

同步、异步、阻塞、非阻塞的概念

同步调用一旦开始,调用者必须等到方法调用返回后,才能继续后续的行为

异步调用更像一个消息传递,一旦开始,方法调用就会立即返回,调用者就可以继续后续的操作

阻塞：当试图对该文件描述符进行读写时，如果当时没有数据可读，或者暂时不可写，程序就进入等待状态，直到有东西可读或者可写为止

非阻塞：如果没有数据可读，或者不可写，读写函数马上返回，而不会等待

线程与进程的区别

① 线程作为调度和分派的基本单位，进程作为资源拥有的基本单位

② 进程有自己独立的地址空间，每启动一个进程，系统都会为其分配地址空间，建立数据表来维护代码段、堆栈段和数据段，线程没有独立的地址空间，它使用相同的地址空间共享数据

③ CPU切换一个线程比切换进程花费小

④ 创建一个线程比进程开销小

⑤ 线程之间通信更方便，同一个进程下，线程共享全局变量，静态变量等数据，进程之间的通信需要以通信的方式（IPC）进行；（但多线程程序处理好同步与互斥是个难点）

⑥ 多进程程序更安全，生命力更强，一个进程死掉不会对另一个进程造成影响（源于有独立的地址空间），多线程程序更不易维护，一个线程死掉，整个进程就死掉了（因为共享地址空间）

引入线程的目的（为什么有了进程还要有进程）

OS 中进程的引入是为了使多个程序并发执行，改善资源利用率，提高系统的吞吐量；但进程时空开销大、通信代价大、不能很好的利用多处理器系统、不适合并行计算和分布计算的要求

引入线程是为了减少程序并发执行时所付出的时空开销，使 OS 具有更好的并发性。

进程间的通信方式？

① 管道（Pipes）

管道是一种单向通信机制，通常用于在父进程和子进程之间传递数据。有两种类型：无名管道和命名管道。无名管道是父子进程之间的通信方式，而命名管道（FIFO）可用于任意两个进程之间的通信。

② 消息队列（Message Queues）

消息队列是一种进程间通信机制，允许多个进程通过发送和接收消息来进行数据交换。消息队列通常用于进程之间的异步通信。

③ 共享内存（Shared Memory）

共享内存是一种高效的进程间通信方式，允许多个进程访问共享的内存区域。这使得数据可以直接在进程之间共享，而无需复制，但需要注意处理同步和互斥问题，以防止数据冲突。

④ 消息传递（Message Passing）

消息传递是一种更通用的通信机制，其中进程通过发送和接收消息来交换数据。这可以包括直接进程间通信（如进程间消息传递）或通过中间件实现的分布式通信。

⑤ 套接字（Sockets）

套接字通常用于网络通信，但也可以在同一台计算机上的进程之间进行通信。套接字提供了一种通用的、全双工的通信机制。

⑥ 文件（File）

进程可以通过读写共享的文件进行通信。这是一种简单的通信方式，但通常不适合高性能或大规模数据传输。

⑦ 信号量（Semaphores）

信号量是用于进程同步的计数器，可以用来控制多个进程对共享资源的访问。

⑧ 信号（Signals）

信号是一种轻量级的通信方式，用于在进程之间传递异步通知。例如，进程可以向其他进程发送信号来请求它们执行某些操作。

用户级线程和内核级线程是什么？相对的各自有什么优点？

用户级线程：仅由用户程序执行的线程，内核并不知道线程的存在。线程的维护由应用进程通过线程库完成优点：执行速度快，线程切换不需要核心态，调度是应用程序决定的，可以选择最好的算法，可以运行在任何操作系统上 内核级线程：有关线程的所有工作都在内核中完成，应用程序中没有相应的线程管理代码，只有一个到内核的API 优点：一个进程发生阻塞不会影响到其他进程，操作系统可以将多个线程对应到多个内核上并行执行缺点：由于有内核的参与，线程切换需要切换到内核态，开销大

用户线程与核心线程的映射模型

多对一模型：多个用户线程映射到一个内核线程。任一时刻只有一个线程能访问内核，多个线程不能并行运行在多处理器上。

如果一个线程执行了阻塞系统调用，那么整个进程会阻塞。

一对一模型：每个用户线程映射到一个内核线程，当一个线程阻塞时其他线程可以继续执行。允许多个线程并行地运行在多处理器上。

唯一的缺点是每创建一个用户线程就需要创建一个相应的内核线程，创建内核线程的开销会影响应用程序的性能，所以这种模型的绝大多数实现限制了系统所支持的线程数量。

多对多模型：多对多模型多路复用了许多用户线程到同样数量或更小数量的内核线程上。可以创建任意多的必要用户线程，且相应内核线程能在多处理器系统中并发执行；一个线程阻塞时，另一个线程可以继续执行。

二级模型：一个流行的多对多模型的变种，仍然多路复用了许多用户线程到同样数量或更小数量的内核线程上，但也允许将一个用户线程绑定到某个内核线程上。这个变种被称为二级模型（two-level model）。

线程哪些资源共享？哪些资源不共享？

共享：堆、全局变量、静态变量、文件等共用资源

独享：栈、寄存器

中断、硬件中断（外中断）、软件中断（内中断）、陷入/陷阱trap、系统调用

中断：CPU对中断信号的一种响应。CPU暂停正在执行的程序，保存现场，执行中断处理程序，而后回到断点，继续原来的程序

根据中断源，分为硬件中断、软件中断

硬件中断（硬中断/外中断）：由I/O设备（外部设备）发出

软件中断（软中断/内中断）：由CPU内部事件引起的中断，例如进程在运算中发生了上/下溢，程序出错（非法指令、地址越界），电源故障等

硬中断是由外部事件引起的，因此具有随机性和突发性；而软中断的发生不是随机的，而是由程序安排好的

系统调用是陷入、陷阱trap的一种

系统调用大致分为五大类：进程控制，文件管理，设备管理，信息维护和通信

中断向量表：
每种设备有响应中断处理程序，该程序的入口地址放在中断向量表中，由中断号对应。
根据中断号，查中断向量表，得程序入口地址，转入中断处理程序执行

介绍下几种常见的进程调度算法及其流程（FCFS，SJF，剩余短作业优先，优先级调度，轮转法，多级反馈队列等等）

①FCFS 先到先服务调度算法

每次调度从就绪队列中选一个最先进入该队列的进程，为之分配处理机，并投入运行

②SJF最短作业优先调度算法

每次调度从就绪队列中选出一个估计运行时间最短的进程，为之分配处理机，并投入运行

③优先级调度算法（Priority scheduling）

将处理机分配给就绪队列中优先级最高的进程

非抢占式（non-preemptive）优先级：一旦把处理及分配给优先级最高的进程，便一直执行到完成，或者其因发生某事件放弃处理机时，系统重新将其分配给另一优先级最高进程。

抢占式（preemptive）优先级：执行期间，如果出现优先级更高的进程，进程调度立刻停止当前（原最高优先级进程）的执行，重新分配处理机给优先级更高的进程

优先级调度算法的一个主要问题是无穷阻塞(indefinite blocking)或饥饿(starvation)。可以运行但缺乏 CPU 的进程可认为是阻塞的，它在等待 CPU。优先级调度算法会使某个低优先级进程无穷等待CPU。

低优先级进程无穷等待问题的解决之一是老化 (aging)。老化是一种技术，以逐渐增加在系统中等待很长时间的进程的优先。

④轮转法调度（Round-robin, RR）

就绪进程按先来先服务排成队列，每次为队首进程分配一个CPU时间片执行。当时间片用完后，该进程被送往就绪队列末尾，再为队首进程分配时间片，周而复始

⑤多级队列调度 Multilevel queue scheduling algorithm

将就绪队列分成多个独立队列，根据进程的属性，如内存大小、进程优先级、进程类型，一个进程被永久地分配到一个队列。每个队列有自己的调度算法。例如，前台进程和后台进程可处于不同队列。前台队列可能采用 RR 算法调度，而后台队列可能采用 FCFS 算法调度。

⑥多级反馈队列调度 Multilevel feedback queue scheduling algorithm

设置多个就绪队列，并为各个队列赋予不同的优先权。第一个队列的优先权最高，第二队列次之，其余队列的优先权逐个降低。

赋予各个队列中进程执行时间片的大小也各不相同，优先权越高，时间片越小。

当一个新进程进入内存后，首先将它放入第一队列的末尾按FCFS原则排队等待调度。当轮到该进程执行时，如能在该时间片内完成，便可准备撤离系统；如果它在一个时间片结束时尚未完成，调度程序便将该进程转入第二队列的末尾，再同样地按FCFS原则等待调度执行；如果它在第二队列中运行一个时间片后仍未完成，再依法将它转入第三队列。如此下去，当一个长进程从第一队列降到第n队列后，在第n队列中便采取按时间片轮转的方式运行。

仅当第一队列空闲时，调度程序才调度第二队列中的进程运行；仅当第1~ (i-1) 队列均空时，才会调度第i队列中的进程运行。

如果处理机正在第i队列中为某进程服务时，又有新进程进入优先权较高的队列，则此时新进程将抢占正在运行进程的处理机，由调度程序把正在运行进程放回第i队列末尾，重新把处理机分配给新进程。

哲学家进餐有哪些实现方式？

哲学家进餐问题的核心是保证至少有一位哲学家能拿到两只筷子就餐后释放筷子。

（1）最多只允许n-1个哲学家拿起筷子就餐。

（2）资源分级算法,奇数号哲学家先拿左手边的筷子，偶数号的哲学家先拿右手边的筷子。

（3）设立规则，当一位哲学家拿起一只筷子时，另一个筷子无法得到，则放下刚刚拿起的筷子.

(4 ) 服务生算法，一次只允许一名哲学家进餐，等到这名哲学家进餐完毕后才允许其他哲学家进餐。

什么是死锁？什么是饥饿？

死锁（deadlocked）：一组处于等待（阻塞）状态的进程，每一个进程持有其他进程所需要的资源，而又等待使用其他进程所拥有的资源，致使这组进程互相等待，均无法向前推进。

另一种定义：当一组进程中每个进程都在等待一个事件，而这一事件只能由这一组进程的另一个进程引起时，这组进程处于死锁状态。

饥饿（starvation）：就绪进程长时间得不到调度是处于等待状态，而不是死锁中的互相等待。

死锁产生的四个必要条件？

如果在一个系统中下面4个条件同时满足，那么会引起死锁。

互斥 Mutual exclusion：至少有一个资源必须处于非共享模式，即一次只有一个进程使用。如果另一进程申请该资源，那么申请进程必须等到该资源被释放为止。

占有并等待 Hold and wait：一个进程必须占有至少一个资源，并等待另一资源，而该资源为其他进程所占有。

非抢占 No preemption：资源不能被抢占，即资源只能在进程完成任务后自动释放。

循环等待 Circular wait：有一组等待进程{P0,P1,…,Pn}，P0等待的资源为P1所占有，P1等待的资源为P2所占有，……，Pn-1等待的资源为Pn所占有，Pn等待的资源为P0所占有。

在此，强调所有4个条件必须同时满足才会出现死锁。

如何处理死锁？

死锁的处理策略有三种：

死锁预防/死锁避免：可使用协议以预防或避免死锁，确保系统不会进入死锁状态

死锁恢复：可允许系统进入死锁状态，然后检测它，并加以恢复。

可忽视这个问题，认为死锁不可能在系统内发生。（鸵鸟策略）

这里第三种方法为绝大多数操作系统所采用，包括UNIX和Windows

预防死锁？

死锁预防(deadlock prevention)是一组方法，以确保至少一个必要条件不成立，这些方法通过限制如何申请资源的方法来预防死锁。

互斥

对于非共享资源，必须要有互斥条件，通常不能通过互斥条件来预防死锁。

占有并等待

可以使用的协议（两种方法）：

资源一次性分配：每个进程在执行前申请并获得所有资源。可以实现通过要求申请资源的系统调用在所有其他系统调用之前进行。

另外一种协议允许进程在没有资源时才可申请资源。一个进程可申请一些资源并使用它们。然而，在它申请更多其他资源之前，它必须释放其现已分配的所有资源。

这两种协议有两个主要缺点：

资源利用率(resourceutilization)可能比较低，因为许多资源可能已分配，但是很长时间没有被使用。

第二，可能发生饥饿。一个进程如需要多个常用资源，可能会永久等待，因为其所需要的资源中至少有一个已分配给其他进程。

非抢占

使用协议：如果一个进程占有资源并申请另一个不能立即分配的资源，那么其现已分配的资源都可被抢占。

循环等待

对所有资源类型进行完全排序，且要求每个进程按递增顺序来申请资源，释放则相反（证明如下）

简述下银行家算法

死锁避免(deadlock avoidance)要求操作系统事先得到有关进程申请资源和使用资源的额外信息。有了这些额外信息，系统可确定：对于一个申请，进程是否应等待。为了确定当前申请是允许还是延迟，系统必须考虑现有可用资源、已分配给每个进程的资源、每个进程将来申请和释放的资源。

银行家算法是一种最有代表性的避免死锁的算法。在避免死锁方法中允许进程动态地申请资源，但系统在进行资源分配之前，应先计算此次分配资源的安全性，若分配不会导致系统进入不安全状态，则分配，否则等待。为实现银行家算法，系统必须设置若干数据结构。

逻辑地址和物理地址

逻辑地址空间：CPU 生成的地址称为逻辑地址（也称虚拟地址），由程序所生成的所有逻辑地址的集合叫逻辑地址空间。

物理地址空间：内存单元的地址叫做物理地址，与程序的逻辑地址空间所对应的为物理地址空间。

地址绑定的方法

编译时 compile time

如果在编译时就知道进程将在内存中的驻留地址，那么就可以生成绝对代码。如果将来开始地址发生变化，需要重新编译代码。

不利于程序在内存中的浮动，不支持虚拟内存机制。

加载时 load time

如果在编译时不知道进程将驻留在内存的什么地方，那么编译器就必须生成可重定位代码。对于这种情况，最后绑定会延迟到加载时才进行，如果开始地址发生变化，只需重新加载用户代码以引入改变值。

不利于程序的浮动，不支持虚拟内存机制。

执行时 execution time

如果进程在执行时可以从一个内存段移到另一个内存段，那么绑定必须延迟到执行时才进行。

要有硬件支持，支持虚拟内存机制。

链接的方式（静态链接、动态链接）

静态链接：

定义：运行前将所有程序模块链接在一起，形成可执行文件，运行时直接装入内存。

优点：运行速度快。

缺点：链接及装入过程费时，可能装入用不到的模块，不利于模块的升级。

动态链接：

定义：运行时链接，且仅链接需要的模块。

优点：便于模块的升级，减少了链接的时间，节省内存空间。缺点：运行速度慢。

碎片（外部碎片、内部碎片）

外部碎片（external fragmentation）：可用内存之和可以满足请求，但并不连续。

外碎片不属于任何进程，在所有进程外。

内部碎片（internal fragmentation）：进程所分配的内存比所要的要大，这两个数字之差称为内部碎片，这部分内存在分区内，但又不能使用。

内碎片存在于进程所在内存区域内部，是属于该进程的。

解决外部碎片问题的方法：

紧缩（compaction）：移动内存内容，以便所有空闲空间合并成一整块。仅在重定位是动态并在运行时可采用。

允许物理空间为非连续

连续内存分配 Contiguous Memory Allocation

每个进程位于一个连续的内存区域。利用重定位寄存器和界限地址寄存器实现。

基地址寄存器（base register）含有最小的合法物理内存地址，而界限地址寄存器（limit register）决定了范围的大小。

多分区方法 Multiple-partition method：

内存分为固定大小的分区，固定分区不拆分分区，可变分区拆分分区：

固定分区 Fixed-sized partitions

将内存空间划分成若干个固定大小的区域，在每个区域可装入一个进程。

可变分区 variable-partition

操作系统中有一个表，用于记录哪些内存可用，哪些内存已被占用。一开始，所有内存都可用于用户进程，因此可做为一大块可用内存，称为孔（hole）

动态存储分配 Dynamic Storage Allocation：

从一组可用孔中选择一个空闲孔的最为常用方法有首次适应(first-fit)、最佳适应(best-fit)、最差适应(worst-fit)：

首次适应：分配第一个足够大的孔。查找可以从头开始，也可以从上次首次适应结束时开始。一旦找到足够大的空闲孔，就可以停止。

最佳适应：分配最小的足够大的孔。必须查找整个列表，除非列表按大小排序。这种方法可以产生最小剩余孔。

最差适应：分配最大的孔。同样，必须查找整个列表，除非列表按大小排序。这种方法可以产生最大剩余孔，该孔可能比最佳适应方法产生的较小剩余孔更为有用。

（补充）next-fit：从上次找到合适孔的位置继续往后找此次合适的孔

固定分区会产生内部碎片，动态分区会产生外部碎片，这两种技术对内存的利用率都比较低。

分页 Pageing

一个作业在内存的各个页面可分配到不同帧中，但每个页面是连续的。用户视角的内存和实际的物理内存的分离。内存分帧，作业分页，帧的大小和页的大小相同。内存分配以页为单位。会产生内碎片。

基本定义：

采用分页技术不会产生外部碎片，但会有内部碎片

a、页（page）：将逻辑内存分成的固定大小的块

b、帧（frame）：将物理内存分成的固定大小的块。

c、页表：将页和帧完成映射（逻辑地址到物理地址的映射）。由于页号是从 0 开始按顺序排列的，所以页表中忽略页号，只留帧号。

d、逻辑地址格式：页号+页内偏移量

e、物理地址 = 帧号*页大小+页内偏移量

f、帧表（frame table）：内存分配的细节，如哪些帧已用，哪些帧可用，总帧数等。每个条目对应着一个帧，以表示该帧是空闲还是已占用，如果占用，是被哪个(或哪些)进程的哪个页所占用。

硬件支持：

a、作为一组专用寄存器来实现：寄存器的访问速度快，所以地址变换的速度快。但是页表较大时成本太大。

b、将页表放入内存，使用页表基寄存器（Page-table base register， PTBR）指向页表，页表长度寄存器（Page-table length register，PTLR）记录页表长度。

进程未执行时页表的初始地址和长度保存在 PCB 中，执行时装入到相应寄存器中。此方法访问一个字节需要先从内存中访问页表得到物理地址，然后再次访问内存取得目的数据，一次需要两次访问内存，过于耗时。

c、采用小但专用且快速的硬件缓冲，这种缓冲称为转换表缓冲区（TLB）。TLB是关键的快速内存。由两部分组成：键和值。

TLB与页表一起按如下方法使用：TLB只包括页表中的一小部分条目。当CPU产生逻辑地址后，其页号提交给TLB。如果找到页号，那么也就得到了帧号，并可用来访问内存。整个任务与不采用内存映射相比，其时间增加不会超过10%。如果页码不在 TLB 中(称为 TLB 失效)，那么就需要访问页表。当得到帧号后，就可以用它来访问内存(如图8.11所示)。同时，将页号和帧号增加到TLB中，这样下次再用时就可很快查找到。如果 TLB中的条目已满，那么操作系统会选择一个来替换。替换策略有很多，从最近最少使用替换(LRU)到随机替换等。另外，有的TLB允许有些条目固定下来，也就是说它们不会从 TLB 中被替换。通常内核代码的条目是固定下来的。

有的 TLB 在每个 TLB 条目中还保存地址空间标识符(address-space identifer,ASID)。ASID 可用来唯一地标识进程，并为进程提供地址空间保护。当TLB试图解析虚拟页号时它确保当前运行进程的 ASID 与虚拟页相关的 ASID 相匹配。如果不匹配,那么就作为 TLB失效。除了提供地址空间保护外，ASID也允许TLB同时包括多个不同进程的条目。如果TLB 不支持独立的 ASID，每次选择一个页表时(例如，上下文切换时)，TLB就必须被冲刷（flushed）或删除，以确保下一个进程不会使用错误的地址转换。

分段 Segmentation

支持用户视角的内存管理方案。作业分段，内存按动态分区管理。内存分配以段为单位，每段都有段名和长度。作业在内存中不连续，但是在段内连续。产生外碎片

分段和分页的区别

页是信息的物理单位，分页是为实现离散分配方式，以消减内存的外碎片，提高内存的利用率；或者说，分页仅仅是由于系统管理的需要，而不是用户的需要；段是信息的逻辑单位，它包含有一组其意义完整的信息。分段的目的是为了能更好地满足用户的需要；

页的大小固定且由系统决定，把逻辑地址划分为页号和页内地址两部分，是由机器硬件实现的，因为一个系统只有一种大小的页面；段的长度不固定，决定于用户所编写的程序，通常由编译程序对源程序进行编译时，根据信息的性质来划分；

分页的作业地址空间是一维的，即单一的线性地址空间，程序员只须一个地址记忆符，即可表示一个地址；分段的作业地址空间是二维的，程序员在标识一个地址时，既需给出段名，又需给出段内地址：<seqment-number,offset>（<段号, 段内偏移>）

虚拟存储器

虚拟存储器从逻辑上扩充内存容量（其容量=内存+外存）（成本近于外存，速度近于内存）。它使应用程序认为它有连续可用的内存，而实际上，它只有少部分进入内存，部分存储在外存中，需要时进行数据交换。

虚拟内存 virtual memeory

定义：仅把作业的一部分装入内存即可执行，具有请求调入功能和置换功能，能在逻辑上对内存空间加以扩充的一种存储器系统。

思想：根据局部性原理，我们只需要将当前要执行的那部分页或段先放入内存执行，其他先放在磁盘中。若程序想要访问的页（或段）未在内存中（称为缺页或缺段），操作系统调用请求调页（段）功能将所要访问的放入内存。若此时内存已满，则需要利用置换功能将内存中暂时不用的页（段）调出内存，将新的页（段）调入内存。

优点：

① 使一个大程序可以在小内存中运行；

② 用户在一个虚拟内存中编程，使得编程不再受内存容量限制；

③ 内存可以装入更多程序并发执行；

④ 提高系统的并发度和吞吐量，减少了 I/O 时间。

有哪些页面置换算法？

① 最佳置换算法(OPT)：每次选择淘汰的页面将是以后永不使用，或者在最长时间内不再被访问的页面，这样可以保证最低的缺页率。

② 先进先出置换算法(FIFO)：每次选择淘汰的页面是最早进入内存的页面。

③ 最近最久未使用置换算法(LRU)：每次淘汰的页面是最近最久未使用的页面

④ 时钟置换算法(CLOCK算法)：

为每个页面设置一个访问位，再将内存中的页面都通过链接指针链接成一个循环队列。当某个页被访问时，其访问位置当需要淘汰一个页面时，只需检查页的访问位。如果是0，就选择该页换出；如果是1，暂不换出，将访问位改为0，继续检查下一个页面，若第一轮扫描中所有的页面都是1，则将这些页面的访问位一次置为0后，再进行第二轮扫描（第二轮扫描中一定会有访问位为0的页面，因此简单的CLOCK算法选择一个淘汰页面最多会经过两轮扫描）。

⑤ 改进型时钟置换算法：除了页面访问情况，又添加一个置换代价。淘汰页优先选择未访问、未修改的；再未访问、已修改的顺次

第一轮：从当前位置开始扫描第一个的页用于替换，本轮扫描不修改任何标志位。

第二轮：若第一轮扫描失败，则重新扫描，查找第一个的页用于替换。本轮将所有扫描的过的页访问位设为0。

第三轮：若第二轮扫描失败，则重新扫描，查找第一个的页用于替换。本轮扫描不修改任何标志位。

第四轮：若第三轮扫描失败，则重新扫描，查找第一个的页用于替换。

文件系统中文件是如何组织的？

逻辑组织：

①有结构文件（记录文件）

文件由若干记录构成。每个记录是一组相关的数据集合，用于描述一个对象某方面的属性。

分为定长记录文件（记录长度相同）、不定长记录文件

②无结构文件（字符流文件）

文件内部不划分记录，由一组相关信息组成有序字符流，即流式文件，其长度直接按字节计算。如大量源程序、可执行程序、库函数等都是无结构。

物理结构：连续文件（放在连续物理块）、串联文件（分散至离散物理块，指针指向下一物理块；只能顺序访问，不能随机存取）、索引文件（为每个文件建立索引表，放物理块块好）

文件物理空间的分配方法

连续分配：每个文件在磁盘上占有一组连续的块，可以用第一块磁盘地址和连续块的数量来定义。

1）优点：实现简单，随机存取速度快，效率高，适合文件内容不进行变动的情况（swap space）

2）问题：难以进行文件扩展，需要提前声明文件大小产生外碎片

链接分配：每个文件是磁盘块的链表，磁盘块分布在磁盘的任何地方，目录块包含文件第一块和最后一块的指针。

1）优点：实现简单，只需要首地址；没有外碎片问题；文件可以扩展，不需要提前声明文件大小

2）问题：每个文件块都有指针，占用空间；无法实现随机读取；可靠性差，一个中间数据块中指针的丢失都会导致链的断裂

索引分配：把所有指针放到统一的索引块上，上面存放着磁盘块地址的数组，索引块的第 i个条目指向了文件的第 i 个块

1）优点：随机访问；可扩展；文件不需要提前声明大小；没有外碎片

2）问题：浪费空间

磁盘调度算法

FCFS：先来先服务，根据进程请求访问磁盘的的先后次序进行调度。算法比较公平，但是因为磁臂摆动幅度大导致平均寻道距离大，效率低

SSTF：最短寻道时间优先算法（贪心算法）每次都选择处理距离当前磁头位置最近的待处理请求。提高了性能但不是最优。基本与 SJF 最短作业优先调度一样，因为新请求随时会抵达，所以可能导致磁头一直在一个小范围摆动，产生饥饿

SCAN：又称电梯调度算法。磁臂从磁盘的一端向另一端移动，磁头经过每个柱面时处理位于该柱面上的请求。到达另一端时改变移动方向继续处理。避免了饥饿现象。但当磁头到达一端折返往回移动时，在该端等待服务的请求可能很少，等待的时间也比较短，因为该区域的请求刚刚被访问过；而另一端等待服务的请求可能很多，等待的时间也可能很长

C- SCAN：circular SCAN，SCAN 调度变种，要求磁头单项移动，即磁头从磁盘一边移动到另一端并处理请求，当磁头移动到另一端时会马上返回磁盘开始，返回时不处理请求。提供更为均匀的等待时间，与 SCAN 相比比较公平，但需要移动更多个柱面

LOOK，C-LOOK：SCAN 和 C-SCAN是使磁头在整个磁盘宽度内进行移动，但这并不容易实现。通常，磁头只会移动到一个方向上最远的请求为止。与 SCAN 和 C-SCAN相比提高了效率。

抖动/颠簸（thrashing）

现象：如果进程没有它所需要的活跃使用的帧，那么它会很快产生页错误。这时，必须置换某个页。然而，其所有页都在使用，它置换一个页，但又立刻再次需要这个页。因此，它会一而再地产生页错误，置换一个页，而该页又立即出错且需要立即调进来。

定义：这种频繁的页面调度行为称为颠簸（thrashing）

本质：如果一个进程在换页上用的时间要多于执行时间，那么这个进程就在颠簸。

抖动/颠簸（thrashing）的解决方法：

① 采用局部置换或优先级置换算法

能限制系统颠簸。采用局部置换，如果一个进程开始颠簸，那么它不能从其他进程拿到帧，且不能使后者也颠簸。然而这个问题还没有完全得到解决。如果进程颠簸，那么绝大多数时间内也会排队来等待调页设备。由于调页设备的更长的平均队列页错误的平均等待时间也会增加。因此，即使对没有颠簸的进程，其有效访问时间也会增加。

② 工作集合模型(working-set model)是基于局部性假设的。该模型使用参数Δ定义工作集合窗口(working-set window)。其思想是检查最近Δ个页的引用。这最近Δ个引用的页集合称为工作集合(working set)。如果一个页正在使用中，那么它就在工作集合内。如果它不在使用，那么它会在其上次引用的Δ时间单位后从工作集合中删除。因此，工作集合是程序局部的近似。

工作集合的精确度与Δ的选择有关。如果Δ太小，那么它不能包含整个局部；如果Δ太大，那么它可能包含多个局部。在最为极端的情况下，如果Δ为无穷大，那么工作集合为进程执行所接触到的所有页的集合。

这种工作集合策略防止了颠簸，并尽可能地提高了多道程序的程度，优化了CPU的利用率。

工作集合模式的困难是跟踪工作集合。工作集合窗口是移动窗口。在每次引用时，会增加新引用，而最老的引用会失去。如果一个页在工作集合窗口内被引用过，那么它就处于工作集合内。

处理中断的过程

保护断点：即保存下一将要执行的指令的地址，就是把这个地址送入堆栈。

寻找中断入口：根据不同的中断源所产生的中断向量，查找不同的入口地址，入口地址处存放着中断处理程序。

执行中断处理程序。

中断返回：执行完中断指令后，就从中断处返回到主程序，继续执行。

什么是虚拟内存？什么是共享内存？（来自网络）

虚拟内存是计算机系统内存管理的一种技术。它使得应用程序认为它拥有连续可用的内存（一个连续完整的地址空间），而实际上，它通常是被分隔成多个物理内存碎片，还有部分暂时存储在外部磁盘存储器上，在需要时进行数据交换。与没有使用虚拟内存技术的系统相比，使用这种技术的系统使得大型程序的编写变得更容易，对真正的物理内存（例如RAM）的使用也更有效率。

共享内存是最快速的进程间通信机制。操作系统在几个进程的地址空间上映射一段内存，然后这几个进程可以在不需要调用操作系统函数的情况下在那段内存上进行读/写操作

原文链接：https://blog.csdn.net/zhanyd/article/details/102987669

http://blog.sina.com.cn/s/blog_a9cdad020102wxzw.html

说一说操作系统中缓冲区溢出怎么处理

缓冲区溢出

当计算机程序向缓冲区内填充的数据位数超过了缓冲区本身的容量。溢出的数据覆盖在合法数据上

理想情况是，程序检查数据长度并且不允许输入超过缓冲区长度的字符串。但是绝大多数程序都会假设数据长度总是与所分配的存储空间相匹配，这就为缓冲区溢出埋下隐患。操作系统所使用的缓冲区又被称为堆栈，在各个操作进程之间，指令被临时存储在堆栈当中，堆栈也会出现缓冲区溢出。

上溢

当一个超长的数据进入到缓冲区时，超出部分被写入上级缓冲区，

上级缓冲区存放的可能是数据、上一条指令的指针，或者是其他程序的输出内容

，这些内容都被覆盖或者破坏掉。可见一小部分数据或者一套指令的溢出就可能导致一个程序或者操作系统崩溃。

下溢

当一个超长的数据进入到缓冲区时，超出部分被写入下级缓冲区，

下级缓冲区存放的是下一条指令的指针，或者是其他程序的输出内容。

缓冲区攻击的日渐泛滥，微软并未任其张扬，陆陆续续推出了各种保存措施。其中重要的有GS，SafeSeh，ASLR，DEP等，接下来我们针对这些措施进行原理分析：

①.GS保护原理：

通过VC++编译器在函数前后添加额外的处理代码，前部分用于由伪随机数生成的cookie并放入.data节段，当本地变量初始化，就会向栈中插入cookie，它位于局部变量和返回地址之间在缓冲区溢出利用时，如果将恶意代码从局部变量覆盖到返回地址，那么自然就会覆写cookie，当检测到与原始cookie不同时，就会触发异常，最后终止进程。

②.SafeSeh保护

为了防止SEH节点被攻击者恶意利用，微软在．net编译器中加入/sdeseh编译选项引入SafeSEH技术。编译器在编译时将PE文件所有合法的异常处理例程的地址解析出来制成一张表，放在PE文件的数据块(LQAJ)一C0N—FIG)中，并使用shareuser内存中的一个随机数加密，用于匹配检查。

如果该PE文件不支持safesEH，则表的地址为0。当PE文件被系统加载后，表中的内容被加密保存到ntdl1．dll模块的某个数据区。在PE文件运行期间，如果发生异常需要调用异常处理例程，系统会逐个检查该例程在表中是否有记录：如果没有则说明该例程非法，进而不执行该异常例程。

③.ASLR保护

ASLR（地址空间布局随机化）技术的主要功能是通过对系统关键地址的随机化，防止攻击者在堆栈溢出后利用固定的地址定位到恶意代码并加以运行。

④.DEP保护

数据执行保护 (DEP) 是一套软硬件技术，能够在内存上执行额外检查以防止在不可运行的内存区域上执行代码

这些保护机制的出现，一度使得攻击难度大大增加，但攻击者们也不是吃素的，他们也在研究绕过这些保护的办法。所谓千里之堤溃于蚁穴，对于上面的保护，攻击者只要找到了它们的一个弱点，便可以突破所有防线，实现攻击。攻击与防护，不断在对抗，可以预见，在未来一段时间，这种游戏还将持续上演。

但是，现在的漏洞门槛比十年前高了N倍，笔者在实际中也常常遇到有漏洞却不能利用的情况。但是也不要灰心，老的技术被淘汰，新的技术又会出来，本属正常，但像缓冲区溢出这种经典的东西，无论什么时候，都值得我们学习。

读写者问题是用进程实现的还是线程实现的？（来自网络）

（不作为回答内容：这题网上没答案吧，我看读者写者进程、线程实现都可以，根据武老师上课说，我们第二章之后讲的都以进程作为例子，推测是进程）

读写者问题实现：

读写者问题是经典进程同步问题，是用进程实现的。

如何组织：

文件组织是指文件的构造方式。文件用户按照自己的使用要求，把构成文件的元素组织起来，文件的这种结构叫文件逻辑结构。

文件的逻辑组织文件的逻辑组织通常分为两种形式，即有结构文件（记录文件）和无结构文件（字符流文件）。1）有结构文件又称作记录式文件，它在逻辑上可被看成一组连续记录的集合，即文件是由若干个相关的记录组成。每个记录是一组相关的数据集合，用于描述一个对象某个方面的属性。记录式文件按其记录的长度是否相同又可分为：定长记录文件和变长记录文件两种。（1）定长记录文件：指文件中所有记录的长度都相同。文件的长度可用记录的数目来表示。定长记录处理方便，开销小，被广泛用于数据处理中。（2）变长记录文件：指文件中各记录的长度不相同。在处理之前每个记录的长度是已知的。2）无结构文件无结构文件是指文件内部不再划分记录，它是由一组相关信息组成的有序字符流，即流式文件，其长度直接按字节计算。如大量的源程序、可执行程序、库函数等采用的文件形式是无结构文件形式。在UNIX系统中，所有的普通文件都被看做是流式文件，系统不对文件进行格式处理。 ●常用的记录式结构有：连续结构、多重结构、转置结构和顺序结构。 ●常用的存取方法有顺序存取法、随机存取法（直接存取法）和按键存取法。文件的物理组织 ●常用的文件物理结构有连续文件、串联文件和索引文件。 1）连续文件连续文件（又称做顺序文件）是基于磁带设备的最简单的物理文件结构，它是把一个逻辑上连续的文件信息存放在连续编号的物理块（或物理记录）中。连续文件的优点是在顺序存取时速度较快，常用于存放系统文件，如操作系统文件、编译程序文件和其它由系统提供的实用程序文件，因为这类文件往往被从头至尾依次存取。但连续文件也存在如下缺点：

（1）要求建立文件时就确定它的长度，依此来分配相应的存储空间，这往往很难实现。

（2）不便于文件的动态扩充。

（3）可能出现外部碎片，就是在存储介质上存在很多空闲块，但它们都不连续，无法被连续的文件使用，从而造成浪费。 2）串联文件为克服连续文件的缺点，可把一个逻辑上连续的文件分散存放在不同的物理块中，这些物理块不要求连续，也不必规则排列。为了使系统能找到下一个逻辑块所在的物理块，可在各物理块中设立一个指针（称为连接字），它指示该文件的下一个物理块。串连文件克服了连续文件的缺点，但它又带来新的问题：

（1）一般仅适于对信息的顺序访问，而不利于对文件的随机存取。

（2）每个物理块上增加一个连接字，为信息管理添加了一些麻烦。 FAT格式通过把文件分配表（FAT，File Allocation Table ）放在一个内存表格中的方式加以克服串联文件的缺点。 3）索引文件索引文件是实现非连续分配的另一种方案：系统为每个文件建立一个索引表。其中的表项指出存放该文件的各个物理块号，而整个索引表由文件说明项指出。这种结构除了具备串连文件的优点之外，还克服了它的缺点。它可以方便地进行随机存取。但是这种组织形式需要增加索引表带来的空间开销。如果这些表格仅放在盘上，那么在存取文件时首先得取出索引表，然后才能查表、得到物理块号。这样就至少增加了一次访盘操作，从而降低了存取文件的速度，加重了 I/O负担。一种改进办法是同时把索引表部分或全部地放人内存。这是以内存空间为代价来换取存取速度的改善。树型目录结构树型目录结构可能是目录结构中，考的比较多的，考的也简单。

同步问题PV大题

操作系统原理题源探秘（9）必须要会的PV大题

1. 医院中的就医流程通常是：某个医生若没有病人，则医生休息，当有病人挂号就诊且分配到该医生时则叫号看病；病人到医院后首先到自助挂号终端挂号，自助挂号终端一段时间只能一个人操作；病人挂号成功后拿着挂号…

https://zhuanlan.zhihu.com/p/604618115?utm_psn=1768304108451491841

非常全面的讲解捏↑

生产者-消费者问题（有限缓冲问题）

假定缓冲池有n个缓冲项，每个缓冲项能存一个数据项。

信号量mutex提供了对缓冲池访问的互斥要求，并初始化为1

信号量empty用来表示空缓冲项的个数，empty初始化为n

信号量full表示满缓冲项的个数，初始化为0

读者-写者问题

一个数据库可以为多个并发进程所共享。其中，有的进程可能只需要读数据库，而其他进程可能要更新(即读和写)数据库。为了区分这两种类型的进程，将前者称为读者，而将后者称为写者。

显然，如果两个读者同时访问共享数据，那么不会产生什么不利的结果。然而，如果一个写者和其他线程(既不是读者也不是写者)同时访问共享对象，很可能混乱。

该问题有多个变种，都与优先级有关。

最为简单的，通常称为第一读者-写者问题，要求没有读者需要保持等待除非已有一个写者已获得允许以使用共享数据库。换句话说，没有读者会因为有一个写者在等待而会等待其他读者的完成。

第二读者-写者问题要求,一旦写者就绪，那么写者会尽可能快地执行其写操作。换句话说，如果一个写者等待访问对象，那么不会有新读者开始读操作。对这两个问题的解答都可能导致饥饿问题。

对第一种情况，写者可能饥饿；对第二种情况，读者可能饥饿。

对于第一读者-写者问题的解决如下：

共享以下数据结构

信号量wrt为读者和写者进程所共用，供写者作为互斥信号量（用于读者-写者和写者-写者之间的互斥），初始化为1

信号量mutex用于确保在更新变量readcount时的互斥，初始化为1

变量readcount用来跟踪有多少进程正在读对象，初始化为0

生产者-消费者问题（有限缓冲问题）

适合解决描述了“缓冲区”的题目，解决的关键一是适当使用互斥锁；二是使用empty和full这样成对的信号量来进行协作。

问题描述：一组生产者进程和一组消费者进程共享一个初始为空、大小为1的缓冲区，只有缓冲区没满时，生产者才能把消息放入缓冲区，否则必须等待；只有缓冲区不空时，消费者才能从中取出消息，否则必须等待。由于缓冲区是临界资源，它只允许一个生产者放入消息，或一个消费者从中取出消息。

问题分析：

关系分析。生产者和消贵者对缓冲区互斥访问是互斥关系，同时生产者和消费者又是一个相互协作的关系，只有生产者生产之后，消费者才能消费，它们也是同步关系。

整理思路。这里比较简单，只有生产者和消费者两个进程，正好是这两个进程存在着互斥关系和同步关系。那么需要解决的是互斥和同步 PV 操作的位置。

信号量设置。信号量 mutex 作为互斥信号量，用于控制互斥访问缓冲池，互斥信号量初值为1：信号量 full 用于记录当前缓冲池中的“满”缓冲区数，初值为0。信号量 empty 用于记录当前缓冲池中的“空” 缓冲区数，初值为n。

代码描述为：

一个更为复杂的问题描述：桌子上有一个盘子，每次只能向其中放入一个水果。爸爸专向盘子中放苹果，妈妈专向盘子中放橘子，儿子专等吃盘子中的橘子，女儿专等吃盘子中的苹果。只有盘子为空时，爸爸或妈妈才可向盘子中放一个水果：仅当盘子中有自己需要的水果时，儿子或女儿可以从盘子中取出。

问题分析：这里的关系要稍复杂一些。由每次只能向其中放入一只水果可知，爸爸和妈妈是互斥关系。爸爸和女儿、妈妈和儿子是同步关系，而且这两对进程必须连起来，儿子和女儿之间没有互斥和同步关系，因为他们是选择条件执行，不可能并发。father()和 dauthger()、mother()和 son()必须连续执行，正因为如此，也只能在女儿拿走苹果后或儿子拿走橘子后才能释放盘子，即 V(plate)操作。

代码描述：

生产者-消费者问题还可以进一步约束，比如加入对生产产品数量差的限制。例如：设自行车生产线上有一个箱子，其中有N个位置(N≥3)，每个位置可存放一个车架或一个车轮，又设有3名工人，其活动分别为：

解决这个问题的关键在于，为了避免死锁，我们需要对两个生产者的生产数量进行约束，以此保证箱子中不会全是某一种材料。实现如下：

另一种情况是限制了两种产物的数量差，例如：在一个仓库中可以存放A和B两种产品，要求①每次只能存入一种产品。②A产品数量-B产品数量＜M。③B产品数量-A产品数量<N。

此时我们需要借助信号量维护二者之间的差距，其基本思想是记二者之差分别为信号量Sa = M, Sb = N的话，每当生产一个A产品，需要先保证Sa被P一下（防止A比B多M个以上），生产完后V一下Sb（A生产一个，B的总数要比A多N个以内，那么其生产的总数可以多一个了）。实现如下：

读者-写者问题

读者-写者问题有一个关键的特征，即有一个互斥访问的计数器 count，因此遇到一个不太好解决的同步互斥问题时，要想一想用互斥访问的计数器 count 能否解决问题。

问题描述：有读者和写者两组并发进程，共享一个文件，当两个或以上的读进程同时访问共享数据时不会产生副作用，但若某个写进程和其他进程（读进程或写进程）同时访问共享数据时则可能导致数据不一致的错误。因此要求：①允许多个读者可以同时对文件执行读操作：②只允许一个写者往文件中写信息：③任一写者在完成写操作之前不允许其他读者或写者工作；④写者执行写操作前，应让己有的读者和写者全部退出。

代码：

在上面的算法中，读进程是优先的，即当存在读进程时，写操作将被延迟，且只要有一个读进程活跃，随后而来的读进程都将被允许访问文件。这样的方式会导致写进程可能长时间等待，且存在写进程“饿死”的情况。

若希望写进程优先，即当有读进程正在读共享文件时，有写进程请求访问，这时应禁止后续读进程的请求，等到己在共享文件的读进程执行完毕，立即让写进程执行，只有在无写进程执行的情况下才允许读进程再次运行。为此，增加一个信号量并在上面程序的 writer()和 reader()函数中各增加一对 PV 操作，就可以得到写进程优先的解决程序：

哲学家干饭问题

问题描述：一张圆桌边上坐着 5 名哲学家，每两名哲学家之间的桌上摆一根筷子，两根筷子中间是一碗米饭。哲学家们倾注毕生精力用于思考和进餐，哲学家在思考时，并不影响他人。只有当哲学家饥饿时，才试图拿起左、右两根筷子（一根一根地拿起）。若筷子己在他人手上，则需要等待。饥饿的哲学家只有同时拿到了两根筷子才可以开始进餐，进餐完毕后，放下筷子继续思考。

为防止死锁发生，可对哲学家进程施加一些限制条件，比如至多允许 4 名哲学家同时进餐；仅当一名哲学家左右两边的筷子都可用时，才允许他抓起筷子：对哲学家顺序编号，要求奇数号哲学家先拿左边的筷子，然后拿右边的筷子，而偶数号哲学家刚好相反。

采用第二种方法，可以这样实现：

吸烟者问题

问题描述：假设一个系统有三个抽烟者进程和一个供应者进程。每个抽烟者不停地卷烟并抽掉它，但要卷起并抽掉一支烟，抽烟者需要有三种材料：烟草、纸和胶水。三个抽烟者中，第一个拥有烟草，第二个拥有纸，第三个拥有胶水。供应者进程无限地提供三种材料，供应者每次将两种材料放到桌子上，拥有剩下那种材料的抽烟者卷一根烟并抽掉它，并给供应者一个信号告诉己完成，此时供应者就会将另外两种材料放到桌上，如此重复(让三个抽烟者轮流地抽烟)。

问题分析：