进程

发表于 | 分类于 | |

A process generally also includes the process stack, which contains temporary data(such as function parameters, return addresses, and local variables), and a data section, which contains global variables. A process may also include a heap, which is memory that is dynamically allocated during process run time.

A program becomes a process when an executable file is loaded into memory.

进程描述和控制

操作系统必须满足的大多数需求表示都涉及进程：

  • 操作系统必须交替执行多个进程，在合理的响应时间范围内使处理器的利用率最大
  • 操作系统必须按照特定的策略给进程分配资源，同时避免死锁。
  • 操作系统可以支持进程间的通信和用户创建进程，它们对构造应用程序很有帮助

从本质上看，如果两个进程为了继续进行而需要相同的两个资源，而它们每人都拥有其中的一个资源，这时就会发生死锁。每个进程都将无限地等待自己没有的那个资源。

什么是进程

进程以下几个定义：

  • 正在执行的程序
  • 正在计算机上执行的程序实例
  • 能分配给处理器并由处理器执行的实体
  • 具有以下特征的活动单元：一组指令序列的执行、一个当前状态和相关的系统资源集。

进程的两个基本的元素是程序代码和代码相关联的数据集。在进程执行时，任意给定一个时间，进程都可以唯一地被表征为以下元素：

  • 标识符：跟这个进程相关的唯一标识付，用来区别其他进程。
  • 状态：如果进程正在执行，那么进程处于运行态。
  • 优先级：相对于其他进程的优先级。
  • 程序计数器：程序中即将被执行的下一条指令的地址。
  • 内存指针：包括程序代码和进程相关数据的指针，还有和其他进程共享内存快的指针。
  • 上下文数据：进程执行时处理器的寄存器中的数据。
  • I/O状态信息：包括显式的I/O请求、分配给进城的I/O设备和被进程使用的文件列表等。
  • 记账信息：可能包括处理器时间总和、使用的时钟数总和、时间限制、记账号等。

前述的列表信息存放在一个叫做进城控制块的数据结构中，该控制块由操作系统创建和管理。

进程状态（Process State）

A process may be in one of the following states:

  • New： The process is being created.
  • Running： Instructions are being executed.
  • Waiting： The process is waiting for some event to occur(such as an I/O completion or reception of a signal).
  • Ready： The process is waiting to be assigned to a processor.
  • Terminated： The process hash finished execution.

状态如下:

  • 运行态：该进程正在执行。
  • 就绪态：进城做好了准备，只要有机会就开始执行。
  • 阻塞/等待态：进程在某些事件发生前不能执行，如I/O操作完成。
  • 新建态：刚刚创建的进程，操作系统还没有把它加入到可执行进程组中。通常是进程控制块已经创建但还没有加载到内存中的新进程。
  • 退出态：操作系统从可执行进程组中释放出的进程，或者是因为它自身停止了，或者是因为某种原因被取消。

进程描述

操作系统构造并维护它所管理的每个实体的信息表。操作系统维护着4种不同类型的表：内存、I/O、文件和进程。

内存表用于跟踪内存和外存（虚拟内存）。内存表必须包括以下信息：

  • 分配给进程的内存。
  • 分配给进程的外存。
  • 内存块和虚拟内存块的任何保护属性，如哪些进程可以访问某些共享内存区域。
  • 管理虚拟内存所需要的任何信息。

操作系统使用I/O表管理计算机系统的I/O设备和通道。

操作系统还维护着文件表，这些表提供关于文件是否存在、文件在外存中的位置、当前状态和其他属性的信息。

操作系统为了管理进程必须维护进程表。

与每个进程相关联的还有操作系统用于控制进程的许多属性，通常，属性的集合称作进城控制块（proccess control block）。

Process Control Block

Each process is represented in the operating system by a process control block(PCB)-also called a task control block. It contains many pieces of information associated with a specific process, including these:

  • Process state. The state may be new, ready, running, waiting, halted, and so on.
  • Program counter. The counter indicates the address of the next instruction to be executed for this process.
  • CPU registers. The registers vary in number and type, depending on the computer architecture. They include accumulators, index registers, stack pointers, and general-prupose registers, plus any condition-code information. Along with the program counter, this state information must be saved when an interrupt occurs. to allow the process to be continued correctly afterward.
  • CPU-scheduling information. This information includes a process priority, pointers to scheduling queues, and any others scheduling parameters,.
  • Memory-management information. This information may include such items as the value of the base and limit resigters and the page tables, or the segment tables, depending on the memory used by the operating system.
  • Accounting information. This information includes the amount of CPU and real time used, time limits, account numbers, job or process numbers, and so on.
  • I/O status information. This information includes the list of I/O devices allocated to the process, a list of open files, and so on.

In brief. the PCB simply serves as the repository for any information that may vary from process to process.

可以把进程控制块信息分成三类：

  • 进程标识信息
  • 处理器状态信息
  • 进程控制信息

进程标识符，每个进程都分配了一个唯一的数字标识符。进程标识符可以简单地表示为主进程表中的一个索引。

进程控制

非特权态常称作用户态。特权态可称作内核态。

创建一个新进程的步骤：

  1. 给新进程分配一个唯一的进程标识符。
  2. 给进程分配空间。
  3. 初始化进程控制块。
  4. 设置正确的连接。
  5. 创建或扩充其他数据结构。

大多数操作系统区分两种类型的系统中断。一种称为中断，另一种称为陷阱。

  • 时钟中断：操作系统确定当前正在运行的进程的执行时间是否已经超过了最大允许时间（时间片，即进程在被中断前可以执行的最大时间段），如果超过了，进程必须切换到就绪态，调入另一个进程。
  • I/O中断：操作系统确定是否发生了I/O活动。
  • 内存失效：处理器访问一个虚拟内存地址，且此地址单元不在内存中时，操作系统必须从外存中把包含这个引用的内存块调入内存中。

对于陷阱，操作系统确定错误或异常条件是否是致命的。

I/O消耗性和处理器消耗型

前者指进程得大部分时间用来提交I/O请求或是等待等待I/O请求。因此，这样的进程经常处于可运行状态，但通常都是运行短短的一会儿，因为它在等待更多的I/O请求时最后总会阻塞。

相反，处理器消耗型进程把时间大多用在执行代码上，除非被抢占，否则它们通常都一直不停滴运行，因为它们没有太多的I/O需求。但是，因为它们不属于I/O驱动类型，所以从系统响应速度考虑，调度器不应该经常让他们运行。对于处理器消耗型的进程，调度策略是尽量降低它们的运行频率，对他们而言，延长其运行时间会更合适些。处理器消耗型进程的极端例子就是无限循环地执行。

调度策略通常要在两个矛盾的目标中间寻找平衡：进程响应迅速和最大系统利用率（高吞肚量）。

线程、对称多处理（SMP）和微内核

进程和线程

多线程是指操作系统在单个进程内支持多个并发执行路径的能力。

在一个进程中，可能有一个或多个线程，每个线程有：

  • 线程执行状态。
  • 在未运行时保存的线程上下文；从某种意义讲，线程可以被看成做进程内的一个被独立地操作的程序计数器。
  • 一个执行栈。
  • 用于每个线程局部变量的静态存储空间。
  • 与进程内的其他线程共享的对进程的内存和资源的访问。

从性能比较可以看出线程的重要优点如下：

  1. 在一个已有进程中创建一个新线程比创建一个全新进程所需的时间要少许多。
  2. 终止一个线程比终止一个进程花费的时间少。
  3. 同一进程内线程间切换比进程间切换花费的时间少。
  4. 线程提高了不同的执行程序见通信的效率。

有4种与线程状态改变相关的基本操作：

  • 派生：在典型情况下，当派生一个新进程时，同时也为该进程派生了一个线程。随后，进程中的线程可以在同一个进程中派生另一个线程，并为新线程提供指令指针和参数；新线程拥有自己的寄存器上下文和栈空间，且被放置在就绪队列中。
  • 阻塞：当线程需要等待一个事件时，它将被阻塞，此时处理器转而执行另一个处于同一进程中或不同进程中的就绪线程。
  • 解除阻塞：当阻塞一个线程的事件发生时，该线程被转移到就绪队列中。
  • 结束：当一个线程完成时，其寄存器上下文和栈都被释放。

线程的实现可以分为两大类：用户级线程和内核级线程。

线程和进程间的关系

线程：进程 描述 示例系统
1:1 执行的每个线程是唯一的进程，有它自己的地址空间和资源。 传统的UNIX
M:1 一个进程定义了一个地址空间和动态资源所有权。可以在该进程中创建和执行多个线程。 Windows NT、Solaris、Linux、OS/2
1:M 一个线程可以从一个进程环境迁移到另一个进程环境。这允许线程可以很容易地在不同系统中移动。 RS
M:N 结合了M:1和1:M情况下的属性。 TRIX

对称多处理

明确SMP体系结构处于整个并行处理器类别的什么位置是有用的。Flynn首先提出的对并行处理器系统给的分类仍然是最常用的分类法，他把计算机系统分为以下4类：

  • 单指令单数据（SISD）流：单处理器执行单个指令流，对保存在单个内存中的数据进行操作。

  • 单指令多数据（SIMD）流： 一个机器指令控制许多处理部件步伐一致地同时进行。

  • 多指令单数据（MISD）流：一系列数据被传送到一组处理器上，每个处理器执行不同的指令序列。这个机构从未实现过。

  • 多指令多数据（MIMD）流：一组处理器同时在不同的数据集上执行不同的指令序列。

    ​

并发性：互斥和同步

和并发相关的关键术语

术语 说明
原子操作 一个或者多个指令的序列，对外是不可分的；即没有其他进程可以看到其中间状态或者中断此操作
临界区 是一段代码，在这段代码中进程将访问共享资源，当另一一个进程已经在这段代码中运行时，这个进程就不能在这段代码中执行
死锁 两个或者两个以上的进程因其中的每个进程都在等待其他进程做完某些事情而不能继续执行，这样的情形叫做死锁
活锁 两个或两个以上进程为了响应其他进程中的变化而持续改变自己的状态但不做有用的工作，这样的情形叫做活锁
互斥 当一个进程在临界区访问共享资源时，其他进程不能进入该临界区访问任何共享资源，这种情形叫做互斥
竞争条件 多个线程或进程在读一个共享数据时，结果依赖于它们执行的相对时间，这种情形叫做竞争
饥饿 是指一个可运行的进程尽管能继续执行，但被调度器无限期地忽视，而不能被调度执行的情况

并发的原理

为了提供对互斥的支持，必须满足如下要求：

  1. 必须强制实施互斥：在于相同资源或共享对象的临界区有关的所有进程中，一次只允许一个进程进入临界区
  2. 一个在非临界区停止的进程不能干涉其他进程
  3. 决不允许出现需要访问临界区的进程被无限延迟的情况，即不会产生死锁和饥饿
  4. 当没有进程在临界区，任何需要进入临界区的进程必须能攻立即进入
  5. 对相关进程对执行速度和处理器的数目没有任何要求和限制
  6. 一个进程驻留在临界区中的时间必须是有限的

Synchronization Hardware（硬件支持）

中断禁用

The critical-section problem could be solved simply in a single-processor environment if we could prevent interrupts from occurring while a shared variable was being modified. In this way, we could be sure that the current sequence of instructions would be allowed to execute in order without preemption. No other instructions would be run, so no unexpected modifications could be made to the shared variable. This is often the approach taken by nonpreemptive kernels.

在单处理器中，并发进程不能重叠，只能交替。此外，一个进程将一直运行，直到它用了一个系统服务或被中断。因此为保证互斥，只需要保证一个进程不被中断就可以了，这种能力可以通过系统内核为启用和禁止中断定义的语句来提供。

1
2
3
4
5
6
7
while(true)
{
    /*禁用中断*/
    /*临界区*/
    /*启用中断*/
    /*其余部分*/
}

由于临界区不能被中断，所以可以保证互斥。但是该方法的代价非常高，由于处理器被限制于只能交替执行程序，因此执行的效率将会明显的降低。第二个问题是该方法不能用于多处理器结构中，在一个计算机系统包括多个处理器时，就有可能有一个以上的进程同时执行，在这种情况下，禁用中断是不能保证互斥的。

专用硬件指令

Many modern computer systems therefore provide special hardware instructions that allow us either to test and modify the content of a word or to swap the contents of two words atomically。

在多处理器配置中，几个处理器共享内存。在这种情况下，不存在主／从关系，处理器间行为是无关的，表现出一种对等关系，处理器之间没有支持互斥的中断机制。

比较和交换指令

1
2
3
4
5
6
7
int compare_and_swap(int *word, int testval, int newval)
{
    int oldval;
    oldval = *word;
    if(oldval == testval) *word = newval;
    return oldval;
}

该指令的一个版本是用一个测试值检查一个内存单元。如果该内存单元的当前值是testval，就用newval取代该值；否则保持不变。该指令总是返回旧内存值；因此如果返回值与测试值相同，则表示该内存单元已经被更新。由此可见，这个原子指令由两部分组成：比较内存单元值和测试值；如果值有差异，则产生交换。整个比较和交换功能按原子操作执行，即它不接受中断。

共享变量bolt被初始化为0，唯一可以进入临界区的进程是发现bold等于0的那个进程。所有试图进入临界区的其他进程进入忙等待模式。术语忙等待（busy waiting）或者自旋等待（spin waiting）指的是这样一种技术：进程在得到临界区访问权之前，它只能继续执行测试变量的指令来得到访问权，除此之外不能做其他事情。当一个进程离开临界区的时候，它把bolt重置为0，此时只有一个等待进程被允许进入临界区。

exchange指令

1
2
3
4
5
6
7
void exchange(int register, int memory)
{
     int temp;
     temp = memory;
     memory = register;
     register = temp;
}

硬件方法方法的特点

  • 适用于任意数目的进程，不管是单处理机还是多处理机；
  • 简单、容易验证其正确性。
  • 可以支持进程内有多个临界区，只需为每个临界区设立一个布尔变量。

硬件方法的缺点

  • 进程等待进入临界区时要耗费处理机时间，不能实现让权等待。
  • 从等待进程中随机选择一个进入临界区，有的进程可能一直选不上，从而导致“饥饿”现象。
  • 可能死锁

信号量（Semaphore）

常用并发机制

并发机制 说明
信号量 用于进程传递信号的一个整数值。在信号量上只有三种操作可以进行，初始化、递减和增加，这三种操作都是原子操作。递减操作可以用于阻塞一个进程，增加操作可以用于解除阻塞一个进程。也称为计数信号量或一般信号量。
二元信号量 只取0值和1值的信号量。
互斥量 类似于二元信号量。关键区别在于为其加锁（设定值为0）的进程和为其解锁（设定值为1）的进程必须为同一个进程。
条件变量 一种数据类型，用于阻塞进程或者线程，直到热定的条件为真。
管程 一种编程语言结构，在一个抽象数据类型中封装了变量、访问过程和初始化代码。管程的变量只能由管程自己的访问过程来访问，每次只能有一个进程在其中执行。访问过程即临界区。管程可以有一个等待进程队列。
事件标志 作为同步机制的一个内存字。应用程序代码可以为标志中的每个位关联不同的时间。通过测试相关的一个或多个位，线程可以等待一个事件或多个事件。在全部的所需位都被设定（AND）或者至少一个位被设定（OR）之前线程会一直被阻塞。
信箱/消息 两个进程交换信息的一种方法，也可以用于同步。
自旋锁 一种互斥机制，进程在一个无条件循环中执行，等待锁变量的值变为可用。

信号量的基本原理：两个或者多个进程可以通过简单的信号进行合作，一个进程可以被迫在某一位置停止，直到它接收到一个特定的信号。任何复杂的合作需求可以通过适当的信号结构得到满足。为了发信号，需要使用一个称作信号量的特殊变量。为通过信号量s传送信号，进程可以执行原语semSignal(s);为通过信号量s接收信号，进程可执行原语semWait(s);如果相应的信号仍然没有发送，则进程被挂起，直到发送完为止。

为达到预期效果，可把信号量看做是一个具有整数值的变量，在它之上定义三个操作：

  1. 一个信号量可以初始化非负数。
  2. semWait操作使信号量减1.如果值变为负数，则执行semWait的进程被阻塞。否则进程继续执行。
  3. semSignal操作使信号量加1。如果值小于或者等于零，则被semWait操作阻塞的进程被解除阻塞。

A semaphore S is an integer variable that, apart from initialization, is accessed only through two standard atomic operations: wait() and signal().

The wait() operation was originally termed P (from the Dutch proberen, “to test”); signal() was originally called V (from verhogen, “to increment”). The definition of wait() is as follows: 

1
2
3
4
5
wait(S) {
    while (S <= 0)
     // busy wait
     S--;
}

The definition of signal() is as follows:

1
2
3
signal(S) { 
	S++;
}

All modifications to the integer value of the semaphore in the wait() and signal() operations must be executed indivisibly. That is, when one process modifies the semaphore value, no other process can simultaneously modify that same semaphore value. In addition, in the case of wait(S), the testing of the integer value of S (S ≤ 0), as well as its possible modification (S–), must be executed without interruption.

所有通过wait和signal对信号量的修改必须不可分割的执行。那就是说当一个进程修改了值，就不允许其他程序同时修改相同的信号值。另外，在wait这方面，它的执行一定不能中断。

Operating systems often distinguish between counting and binary semaphores. The value of a counting semaphore can range over an unrestricted domain. The value of a binary semaphore can range only between 0 and 1.

To implement semaphores under this definition, we define a semaphore as follows:

1
2
3
4
5
typedef struct{
    int value;
    struct process *list; 
} 
semaphore;

Each semaphore has an integer value and a list of processes list. When a process must wait on a semaphore, it is added to the list of processes. A signal() operation removes one process from the list of waiting processes and awakens that process.

Now, the wait() semaphore operation can be defined as

1
2
3
4
5
wait(semaphore *S) {
	S->value--;
	if (S->value < 0) 
	{add this process to S->list;}
}

wait操作，S.value–，表示进程请求一个该类资源，当S.value<0时，表示该类资源已分配完毕，因此进程应调用block原语，进行自我阻塞，放弃处理机，并插入到该类资源的等待队列S.L中，可见该机制遵循了“让权等待”的准则。

and the signal() semaphore operation can be defined as 

1
2
3
4
5
6
signal(semaphore *S) { 
	S->value++;
	if (S->value <= 0) {
	remove a process P from S->list; wakeup(P);
	} 
}

signal操作，表示进程释放一个资源，使系统中可供分配的该类资源数增1，故S.value++。若加1后仍是S.value<=0，则表示在S.L中仍有等待该资源的进程被阻塞，故还应调用wakeup 原语，将S.L中的第一个等待进程唤醒

强信号量保证不会饥饿，而弱信号量不能。

生产者/消费者问题
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
/* program boundedbuffer */
const int sizeofbufer = /* 缓冲区大小 */
semaphore n = 0, s= 1, e = sizeofbuffer;
void producer()
{
    while (true) {
         produce();
         semWait(e);
         semWait(s);
         append();
         semSignal(s);
         semSignal(n);
    }
}
void consumer()
{
    while (true) {
        semWait(n);
        semWait(s);
        take();
        semSignal(s);
        semSignal(e);
        consume();
    }
}
void main()
{
    parbegin (producer, consumer);
}
信号量的实现

比较并交换指令

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
semWait(s)
{
    while (compare_and_swap(s.flag, 0, 1) == 1)
    	/* 不做任何事 */;
    s.count--;
    if (s.count < 0) {
        /* 该进程进入s.queue队列 */;
        /* 阻塞该进程（也必须将s.flag设置为0） */;
    }
    s.flag = 0;
}
semSignal(s)
{
    while (compare_and_swap(s.flag, 0, 1) == 1)
    	/* 不做任何事 */;
    s.count++;
    if (s.count < = 0) {
        /* 从s.queue队列中移除进程p */;
        /* 进程P进入就绪队列 */;
    }
    s.flag = 0;
}

中断方式

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
semWait(s)
{
	禁用中断；
	s.count--;
	if (s.count < 0) {
        /* 该进程进入s.queue队列 */;
        /* 阻塞该进程，并允许中断 */;
	}
	else
		允许中断;
}
semSignal(s)
{
    禁用中断;
    s.count++;
    if (s.count <= 0) {
        /*从s.queue队列中移除进程P*/
        /*进程P进入就绪队列*/;
    }
    允许中断;
}

管程

消息传递

消息传递系统可以有多种形式，本书将给出关于这类系统典型特征的一般介绍。消息传递的实际功能以一对原语的形式提供：

1
2
send(destination, message)
receive(source, message)

这是进程间进行消息传递所需要的最小操作集。一个进程以消息（message）的形式给另一个指定的目标（destination）进程发送信息；进程通过执行receive原语接收信息，receive原语中指明发送消息的源进程（source）和消息。

读者-写者问题

并发：死锁和饥饿

死锁的原理

In a multiprogramming environment, several processes may compete for a finite number of resources. A process requests resources; if the resources are not available at that time, the process enters a waiting state. Sometimes, a waiting process is never again able to change state, because the resources it has requested are held by other waiting processes. This situation is called a deadlock.

可以把死锁定义为一组相互竞争系统资源或进行通信的进程间的”永久”阻塞。

死锁的条件

死锁有三个必要条件：

  1. 互斥（Mutual exclusion）。一次只有一个进程可以使用一个资源。其他进程不能访问已分配给其他进程的资源。
  2. 占有且等待（Hold and wait）。当一个进程等待其他进程时，继续占有已经分配的资源。
  3. 不可抢占（No preemption）。不能强行抢占进程已占有的资源。
  4. 循环等待（Circular wait）。存在一个封闭的进程链，使得每个进程至少占有此链中下一个进程所需要的一个资源。

死锁预防

简单的讲，死锁预防策略是试图设计一种系统来排除发生死锁的可能性。可把死锁预防方法分为两类。一种是间接的死锁预防方法，即防止前面列出的三个必要条件中任何一个的发生；一种是直接的死锁预防方法，即防止循环等待的发生。

死锁避免

死锁避免允许三个必要条件，但通过明智的选择，确保永远不会到达死锁点，因此死锁避免比死锁预防允许更多的并发。

两种死锁避免的方法：

  • 如果一个进程的请求会导致死锁，则不启动此进程。
  • 如果一个进程增加的资源请求会导致死锁，则不允许此分配。
资源分配拒绝

资源分配拒绝策略，又称为银行家算法。首选需要定义状态和安全状态的概念。安全状态是指至少有一个资源分配序列不会导致死锁，不安全状态当然就是指一个不安全状态。

死锁避免的优点是它不需要死锁预防中的抢占和回滚进程，并且比死锁预防的限制少。但是，它在使用中也有许多限制：

  • 必须事先声明每个进程请求的最大资源。
  • 考虑的进程是无关的，也就是说，它们执行的顺序必须没有任何同步要求的限制。
  • 分配的资源数目必须是固定的。
  • 在占有资源时，进程不能退出。

死锁检测

哲学家就餐问题

UNIX的并发机制

管道

UNIX对操作系统开发最重要的贡献之一是管道。受协同程序概念的启发，管道是一个环形缓冲区，允许两个进程以生产者/消费者的模型进行通信。因此，这是一个先进先出队列，由一个进程写，而由另一个进程读。

有两类管道：命名管道和匿名管道。只有有“血缘”关系的进程才可以共享匿名管道，而不相关的进程只能共享命名管道。

Reference

操作系统 精髓与设计原理

operating-system concepts

More than your eyes can see