进程管理

进程与线程

进程

进程是程序关于某个数据集合的运行过程，进程是一个活动实体。进程是系统进行资源分配的基本单位。

守护进程

Linux Daemon（守护进程）是运行在后台的一种特殊进程。它独立于控制终端并且周期性地执行某种任务或等待处理某些发生的事件。它不需要用户输入就能运行而且提供某种服务，不是对整个系统就是对某个用户程序提供服务。Linux系统的大多数服务器就是通过守护进程实现的。常见的守护进程包括系统日志进程syslogd、 web服务器httpd、邮件服务器sendmail和数据库服务器mysqld等。

它们常常在系统引导装入时启动，仅在系统关闭时才终止。守护进程经常以超级用户（root）权限运行，因为它们要使用特殊的端口（1-1024）或访问某些特殊的资源。

用户层守护进程的父进程是 init进程（进程ID为1）。对于用户层守护进程，因为它真正的父进程在 fork 出子进程后就先于子进程 exit 退出了，所以它是一个由 init 继承的孤儿进程。

僵尸进程

在一个进程调用了exit之后，该进程并非马上就消失掉，而是留下一个称为僵尸进程（Zombie）的数据结构。在Linux进程的5种状态中，僵尸进程是非常特殊的一种，它已经放弃了几乎所有内存空间，没有任何可执行代码，也不能被调度，仅仅在进程列表中保留一个位置，记载该进程的退出状态等信息供其他进程收集，除此之外，僵尸进程不再占有任何内存空间。

收割僵尸进程的方法是通过kill命令手工向其父进程发送SIGCHLD信号。如果其父进程仍然拒绝收割僵尸进程，则终止父进程，使得init进程收养僵尸进程。init进程周期执行wait系统调用收割其收养的所有僵尸进程。

孤儿进程

孤儿进程：一个父进程退出，而它的一个或多个子进程还在运行，那么那些子进程将成为孤儿进程。孤儿进程将被init进程(进程号为1)所收养，并由init进程对它们完成状态收集工作。

线程

线程是进程中的一个实体，是操作系统进行调度的基本单位，但不是资源分配的基本单位。线程除了必须的PC和寄存器外，几乎不拥有系统资源。

进程与线程的关系

一个进程可以由多个线程组成
进程是资源分配的最小单位，线程是程序执行的最小单位
进程有自己独立的地址空间，同一个进程内的线程共享该进程的所有资源，共享该进程的地址空间。因此线程切换开销较小
线程之间的通信更方便，同一进程下的线程共享全局变量、静态变量等数据，而进程之间的通信需要以通信的方式（IPC)进行。
每个线程有自己的堆栈和局部变量

协程

协程是一种用户态的轻量级线程。协程拥有自己的寄存器上下文和栈。协程调度切换时，将寄存器上下文和栈保存到其他地方，在切回来的时候，恢复先前保存的寄存器上下文和栈。因此：协程能保留上一次调用时的状态（即所有局部状态的一个特定组合），每次过程重入时，就相当于进入上一次调用的状态，换种说法：进入上一次离开时所处逻辑流的位置；

协程的优点：

跨平台，跨体系结构
无需线程上下文切换的开销
无需原子操作锁定及同步的开销，因为只有一个线程，也不存在同时写变量冲突，在协程中控制共享资源不加锁，只需要判断状态就好了
方便切换控制流，简化编程模型
高并发，高扩展

协程的缺点

无法利用多核资源：协程的本质是个单线程
可以通过多进程+协程的方法来利用CPU的多核，既充分利用多核，又充分发挥协程的高效率，可获得极高的性能。

进程间通信 IPC

管道/匿名管道(pipe)

管道是半双工的，数据只能向一个方向流动；需要双方通信时，需要建立起两个管道
只能用于父子进程或者兄弟进程之间
数据的读出和写入：一个进程向管道中写的内容被管道另一端的进程读出。写入的内容每次都添加在管道缓冲区的末尾，并且每次都是从缓冲区的头部读出数据

有名管道（FIFO）

允许无亲缘关系进程间的通信

信号量（semaphore）

信号量是一个计数器，用于多进程对共享数据的访问
主要作为进程间以及同一进程不同线程之间的同步手段

共享内存

使得多个进程可以可以直接读写同一块内存空间
由于多个进程共享一段内存，因此需要依靠某种同步机制（如信号量）来达到进程间的同步及互斥

消息队列

消息队列是存放在内核中的消息链表，每个消息队列由消息队列标识符表示
消息队列克服了信号承载信息量少，管道只能承载无格式字节流以及缓冲区大小受限等缺点

信号

用于通知接受进程有某种事件发生，除了用于进程间通信外，进程还可以发送信号给进程本身

套接字

更为一般的进程间通信机制，可用于不同机器之间的进程间通信

线程通信

线程通信方式

全局变量

由于多个线程可能更改全局变量，因此全局变量最好声明为volatile

消息传递

每一个线程都可以拥有自己的消息队列

事件

可以通过对事件的触发状态进行改变，从而实现线程间的通信和同步

线程同步方式

线程间通信的主要目的是用于线程同步，所以线程没有像进程通信中用于数据交换的通信机制。主要包括互斥锁，读写锁，条件变量。

互斥锁与临界区

互斥锁是一种用于多线程编程中，防止多个线程同时对同一公共资源（比如全局变量）进行读写的机制
临界区域指的是一块对公共资源进行访问的代码

自旋锁

用于多线程同步的一种锁，线程反复检查锁变量是否可用
由于线程在这一过程中保持执行，因此是一种忙等待。一旦获取了自旋锁，线程会一直保持该锁，直至显式释放自旋锁
自旋锁避免了进程上下文的调度开销，因此对于线程只会阻塞很短时间的场合是有效的

问题：

递归死锁：
过多占用CPU资源：

读写锁

读写锁允许多个线程同时读共享数据，而对写操作是互斥的

读优先的读写锁

class rwLock() {
publicn
    rwLock() : read_count(0) {
        pthread_mutex_init(&read_mtx, NULL);
        pthread_mutex_init(&write_mtx, NULL);
    }
    ~rwLock() {
        pthread_mutex_destroy(&read_mtx);
        pthread_mutex_destroy(&write_mtx);
    }
    void readLock() {
        pthread_mutex_lock(&read_mtx);
        if (++read_count == 1) {
            pthread_mutex_lock(&write_mtx);
        }
        pthread_mutex_unlock(&read_mtx);
    }

    void readUnlock() {
        pthread_mutex_lock(&read_mtx);
        if (--read_count == 0) {
            ptrhead_mutex_unlock(&write_mtx);
        }
        pthread_mutex_unlock(&read_mtx)
    }

    void writeLock() {
        pthread_mutex_lock(&write_mtx);
    }

    void writeUnlock() {
        pthread_mutex_unlock(&write_mtx);
    }

private:
    pthread_mutex_t read_mtx;
    pthread_mutex_t write_mtx;
    size_t read_count;
};

写优先的读写锁

class rwLock() {
public:
    rwLock() : refCount(0), readWaiter(0), writeWaiter(0) {
        pthread_mutex_init(&rwMutex, NULL);
        pthread_cond_inti(&readCond, NULL);
        pthread_cond_inti(&writeCond, NULL);
    }

    ~rwLock() {
        pthread_mutex_destroy(&rwMutex);
        pthread_cond_destroy(&readCond);
        pthread_cond_destroy(&writeCond);
    }

    void readLock() {
        pthread_mutex_lock(&rwMutex);
        while (refCount < 0) {
            ++readWaiter;
            ptreahd_cond_wait(&readCond, &rwMutex);
            --readWaiter;
        }
        ++refCount;
        pthread_mutex_unlock(&rwMutex);
    }

    void writeLock() {
        pthread_mutex_lock(&rwMutex);
        while (refcount != 0) {
            ++writeWaiter;
            pthread_cond_wait(&writeCond, &rwMutex);
            --writeWaiter;
        }
        refCount = -1;
        pthread_mutex_unlock(&rwMutex);
    }

    void unlock() {
        pthread_mutex_lock(&rwMutex);
        if (refCount == -1) {
            refCount = 0;
        } else {
            refCount--;
        }
        if (refCount == 0) {
            if (writeWaiter > 0) {
                pthread_cond_signal(&writeCond);
            } else if (readWaiter > 0) {
                pthread_cond_signal(&readCond);
            }
        }
        pthread_mutex_unlock(&rwMutex);
    }
private:
    int refCount;
    int readWaiter;
    int writeWaiter;
    pthread_mutex_t rwMutex;
    pthread_cond_t readCond;
    pthread_cond_t writeCond;
};

条件变量

条件变量可以以原子的方式阻塞进程，直到某个特定条件为真为止。对条件的测试是在互斥锁的保护下进行的。条件变量始终与互斥锁一起使用

信号量机制

包括无名线程信号量与有名线程信号量

信号机制

类似于进程间信号通信

进程调度

死锁

产生死锁的四个必要条件

保持并请求：进程已占用一部分资源，申请更多资源，且不会释放已占有的资源
不可剥夺：进程已经占用的资源，不可以被抢占
互斥：任一时刻只允许一个进程对该资源进行访问
循环等待：请求资源的进程形成环状

死锁处理

死锁预防

采用某种策略限制进程对资源的请求，系统任何时刻都不满足死锁的必要条件。死锁预防主要是针对死锁的四个必要条件进行的。

破坏互斥条件：某些设备可以通过SPOOLING技术将独占资源转换共享资源
破坏不可抢占条件：当一进程占有一独占性资源后又申请一独占性资源而无法满足，则退出原占有的资源。
破坏保持并请求条件：采用资源预先分配策略，即进程运行前申请全部资源，满足则运行，不然就等待，这样就不会占有且申请。
破坏循环等待条件：资源有序分配

死锁避免

某一时刻，若系统能按某种顺序为每个进程分配所需资源，是每个进程都能顺利完成，则此时系统处于安全状态。否则，为不安全状态。

银行家算法

死锁检测与恢复

资源分配图：

系统死锁，可利用资源分配图来描述。用圆圈代表一个进程，用框代表一类资源。由于一种类型的资源可能有多个，用框中的一个点代表一类资源中的一个资源。从进程到资源的有向边叫请求边，表示该进程申请一个单位的该类资源；从资源到进程的边叫分配边，表示该类资源已经有一个资源被分配给了该进程。

死锁定理

可以通过将资源分配图简化的方法来检测系统状态S是否为死锁状态。简化方法如下：

在资源分配图中，找出既不阻塞又不是孤点的进程 \(P_i\)（即找出一条有向边与它相连，且该有向边对应资源的申请数量小于等于系统中已有空闲资源数量。若所有的连接该进程的边均满足上述条件，则这个进程能继续运行直至完成，然后释放它所占有的所有资源）。消去它所有的请求边和分配边，使之成为孤立的结点。
进程 \(P_i\) 所释放的资源，可以唤醒某些因等待这些资源而阻塞的进程，原来的阻塞进程可能变为非阻塞进程。若能消去图中所有的边，则称该图是可完全简化的。

S为死锁的条件是当且仅当S状态的资源分配图是不可完全简化的，该条件为死锁定理。

死锁恢复：

资源剥夺法：挂起某些死锁进程，并抢占它的资源，将这些资源分配给其他的死锁进程。
撤销进程法：强制撤销部分、甚至全部死锁进程并剥夺这些进程的资源。撤销的原则可以按进程优先级和撤销进程代价的高低进行。
进程回退法：让一（多）个进程回退到足以回避死锁的地步，进程回退时自愿释放资源而不是被剥夺。要求系统保持进程的历史信息，设置还原点。

内存管理

进程的内存布局

进程对应的内存空间中所包含的5种不同的数据区

程序代码段 text：存储目标文件的一部分或包含可执行指令的程序的虚拟地址空间的相应部分的位置，并且通常是只读且固定大小的。
数据段 data：存储已初始化的常量和静态变量
bss段：存储未初始化的常量和静态变量
heap 堆：在.bss数据段的末尾开始，向高地址增长。用于存放进程运行中被动态分配的内存段
stack 栈：挨着heap，两者相对增长。存放程序临时创建的局部变量。此外，在函数被调用时，其参数也会被压入发起调用的进程栈中，并且待到调用结束后，函数的返回值也会被存放回栈中。由于栈的先进先出特点，所以栈特别方便用来保存/恢复调用现场。