Untitled

进程概念

进程

一个进程包括：
- text/code section 文本/代码段
- data section 数据段：存放全局变量
- stack：存放程序运行环境，例如函数参数、局部变量、返回地址
- heap：动态分配内存
- program counter 程序计数器

Untitled

内存中的进程占用的大部分空间是未知的部分

进程状态

每个进程可能处于以下状态：
- new：进程正在创建
- running：指令正在执行
- waiting：进程等待发生某个事件，例如 I/O 完成
- ready：进程等待分配处理器
- terminated：进程已经完成执行

进程状态图

进程控制块（Process Control Block, PCB）

采用进程控制块结构来表示进程，便于操作系统控制进程

进程控制块保存了进程状态、程序计数器、CPU 寄存器、CPU 调度信息、内存管理信息、记账信息、I/O 状态信息。

PCB 不一定保存的是当前运行状态的信息，而是上一次发生进程切换时保存下来的信息

PCB 的更新发生在进程切换时

进程间的 CPU 切换

Linux 操作系统的进程控制块采用 C 语言结构task_struct来表示，它位于内核源代码目录内的头文件 <linux/sched.h>。

进程调度

调度队列

作业队列（job queue）：系统内所有的进程

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

设备队列（device queue）：等待特定 I/O 设备的进程（每个 I/O 设备有一个对应的设备队列）

进程调度通常用队列图（queueing diagram）表示

Untitled

CPU 调度就是从就绪队列中选出一个进程去占用 CPU，不能直接从设备队列中选，对应进程状态 waiting 不能直接转为 running 而要经过 ready。

调度程序

长期调度程序（long-term scheduler）：从磁盘的缓冲池中选择进程，加到内存中运行

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

两种调度程序的区别主要是执行效率，短期调度程序必须经常为 CPU 选择新的进程，长期调度程序执行并不频繁。

目前长期调度程序已经几乎不需要，因为可以由人来决定选择哪个进程，而不需要操作系统决定。

中期调度程序（medium-term scheduler）：可将进程从内存中换出（swap out）从而降低多道程序程度（内存中的进程数量）。之后进程可被重新换入（swap in）内存并从中断处继续执行。

Untitled

I/O 密集型进程（I/O-bounded process）：执行 I/O 比执行计算需要花费更多时间

CPU 密集型进程（CPU-bounde process）：很少产生 I/O 请求，更多时间用于执行计算

上下文切换（Context Switch）

切换 CPU 到另一个进程需要保存当前进程状态和恢复另一个进程的状态的任务称为上下文切换。

进程运行

进程创建

父进程通过系统调用的方式创建子进程，每个新进程可以再创建其它进程，形成进程树。

子进程可以从操作系统直接获取资源，也可以只从父进程那里获得资源子集（由父进程分配或共享）。

限制子进程只能使用父进程的资源可以防止创建过多进程，导致系统超载。

当进程创建新进程时，有两种执行可能：
- 父进程与子进程并发执行
- 父进程等待，直到某个或全部子进程执行完
新进程的地址有两种可能：
- 子进程是父进程的复制
- 子进程是加载另一个新程序

在 UNIX 中，通过系统调用fork()创建新进程，之后有一个进程使用系统调用exec()，以用新程序来取代进程的内存空间。

Untitled

int main()
{
    pid_t  pid;
    /* fork another process **/* 
    pid = fork();
    **if (pid < 0) { */** error occurred */
        fprintf(stderr, "Fork Failed"); 
        exit(-1);
    }
    else if (pid == 0) { /* child process */ 
        execlp("/bin/ls", "ls", NULL);
    }
    else { /* parent process */
        /** parent will wait for the child to complete */
        wait (NULL);
        printf ("Child Complete"); 
        exit(0);
    }
}

进程终止

当进程完成执行最后语句并通过系统调用exit()请求操作系统删除自身时，进程终止。

如果终止子进程，则父进程需要知道这些子进程的标识符，因此当一个进程创建新进程时，新进程的标识符要传递到父进程。

父进程终止子进程的原因包括：
- 子进程使用了超过它所分配的资源
- 分配给子进程的任务不再需要
- 父进程正在退出，而且操作系统不允许无父进程的子进程继续执行（级联终止）

当一个进程终止时，操作系统会释放其资源，但它位于进程表中的条目依然存在，直到父进程调用wait()，这是因为进程表包含了进程的退出状态。

进程间通信（Interprocess Communication, IPC）

提供环境允许进程协作的优点：
- Information sharing
- Computation speed-up(Multiple CPUs)
- Modularity
- Convenience

管道（pipes）：最早在 UNIX 中提出的进程之间协同的机制

进程间通信有两种基本模型：
- 共享内存（shared memory）：建立一块供协作进程共享的内存区域，进程通过向此共享区域读出或写入数据来交换信息
- 消息传递（message passing）：通过协作进程间交换消息来实现通信

Untitled

消息传递对于交换较少数量的数据很有用，因为无需避免冲突，对于分布式系统也更易实现。

共享内存可以快于消息传递，因为消息传递的实现经常采用系统调用，因此需要消耗更多时间以便内核介入。

共享内存系统

生产者-消费者问题指生产者（producer）进程生成信息，以供消费者（consumer）进程消费，解决方法之一是共享内存。

有一个可用的缓冲区允许生产者进程和消费者进程并发执行

缓冲区的两种类型：
- 有界缓冲区（bounded-buffer）：缓冲区有可能会满
- 无界缓冲区（unbounded-buffer）：会使用的缓冲区比可用的缓冲区少得多

以下变量驻留在由生产者和消费者共享的内存区域中：

#define BUFFER_SIZE 10

typedef struct {
...
} item;

item buffer[BUFFER_SIZE];
int in = 0;
int out = 0;

采用有界缓冲区的生产者进程：

while (true) {
    Produce an item;

    while (((in + 1) % BUFFER_SIZE == out); /* do nothing -- no free buffers */

    buffer[in] = item;
    in = (in + 1) % BUFFER_SIZE;
}

采用有界缓冲区的消费者进程：

while (true) {
    while (in == out); //do nothing, nothing to consume

    Remove an item from the buffer;
    item = buffer[out];
    out = (out + 1) % BUFFER SIZE;
    return item;
}

这种方法允许缓冲区的最大值为BUFFER_SIZE-1。

要允许缓冲区的最大值为BUFFER_SIZE可以引入一个新的共享变量count统计项个数，但需要解决数据竞争问题。

消息传递系统

直接通信（Direct Communication）：需要通信的两个进程必须明确指定通信的接收者或发送者

间接通信（Indirect Communication）：通过邮箱或端口来发送和接受消息

消息传递可以是阻塞（blocking）或非阻塞（nonblocking），也称为同步（synchronous）或异步（asynchronous）：
- 阻塞发送：发送进程堵塞，直到消息由接收进程或邮箱所接收
- 非阻塞发送：发送进程发送消息，并且恢复操作
- 阻塞接收：接收进程阻塞，直到有消息可用
- 非阻塞接收：接收进程收到一个有效消息或空消息
通信进程交换的消息总是驻留在临时队列中，队列实现有三种方法：
- 零容量（zero capacity）：链路中不能有任何消息处于等待，发送者应阻塞，直到接收者接收到消息
- 有限容量（bounded capacity）：若链路已满则发送者应阻塞，直到有可用队列空间为止
- 无限容量（unboun capacity）：发送者从不阻塞