程序顺序执行特征

顺序性：按照程序结构所指定的次序执行
封闭性：独享计算机所有资源
可再现性：初始条件相同则结果相同

程序并发执行特征

间断性：并发程序具有“执行—-暂停——执行”这种间断性的活动规律。
非封闭性：多个程序共享资源
不可再现性：在初始条件相同的情况下，程序执行结果取决于执行次序

竞争

定义

多个程序在读写一个共享数据时结果依赖顺序。

所以如果不依赖顺序，只是读写共享数据也不能说它是竞争。

判断——Bernstein条件

定义

$$R(SI)$$

SI的读子集，代表着进程SI需要读的资源
$$W(SI)$$
SI的写子集，代表着进程SI需要写的资源

条件

两个进程S1和S2可并发，当且仅当下列条件同时成立：
$$\eqalign{ & R(S1) \cap W(S2) = \emptyset \cr & W(S1) \cap R(S2) = \emptyset \cr & W(S1) \cap W(S2) = \emptyset \cr} $$
不然就会发生竞争，运行结果将不确定。

其他定义

临界资源：一次只能允许一个进程访问的资源叫临界资源
临界区：进程中访问临界资源的那一段代码
临界区管理需满足：空闲让进，忙则等待，有限等待，让权等待。

进程

特征

动态性：是程序的执行过程，可生可死可睡觉
异步性：各自独立以不可预知的速度执行
并发性：和其他进程一起并发执行
独立性：是传统OS中独立运行的基本单位

产生

可以由Fork产生

fork有三种返回值，正数，0和负数。
不要只记住正数和0.

执行状态

进程有以下三种基本执行状态。

线程

定义

进程的可执行单元

引入目的

减少并发程序执行时所付出的时空开销，使得并发粒度更细、并发性更好

每个线程都有自己的栈。

与进程的关系

实现方式

用户级线程

定义

线程在用户空间,通过library模拟的thread,不需要或仅需要极少的kernel支持。

特点

优点：

切换无需经过内核
调度由程序决定
可运行在任何系统上

缺点：

内核不知用户态下线程的状态，阻塞时只能全部阻塞
无法实现并行执行，因为内核对其的分配以进程为单位

内核级线程

定义

内核级线程就是kernel有好几个分身,一个分身可以处理一件事
内核线程

特点

优点：

内核感知线程，可以将线程安排到多个处理器上并行执行
内核感知线程，可以实现精确阻塞
内核中的处理可通过多线程完成。

缺点：

线程切换经过内核，降低了效率

混合级线程

定义

线程在用户空间创建和管理，但需要实现从用户空间的线程到内核空间线程（轻量级进程）的映射
混合级线程

特点

折中了前面两种方法。

进程同步与互斥

互斥是由于访问临界资源而产生的关系，不是人为的，是为了保证正确性，且不保证顺序。
同步是人为设置的次序，为了合作完成某一任务，保证顺序。

忙等待互斥算法

面包店算法

设置一个发号器，按由小到大的次序发放号码。进程进入临界区前先抓取一个号码，然后按号码从小到大的次序依次进入临界区。若多个进程抓到相同的号码则按进程编号依次进入。

Entry Section (i) { // i → process i
    while (true) {
        Choosing[i] = 1;
        Number[i] = 1 + max(Number[1],...,Number[N]);
        Choosing [i] = 0;
        for (j=1; j＜=N; ++j) {
            while (Choosing[j] != 0) { }
            // wait until process j receives its number,等待所有进程抓号完毕
            while ((Number[j]!=0) && ((Number[j],j) ＜(Number[i],i))) { }
            // wait until processes with smaller numbers, or with the 
            // same number, but with higher priority, finish their work
            // 还有比该进程号小的，或者号相同但是编号大的没访问临界区，所以继续忙等
        }
    // critical section... 临界区
    Number[i] = 0;
    // non-critical section... 非临界区
    }
}

TS指令

是一种不可中断的基本原语（指令）。它会写值到某个内存位置并传回其旧值。

语义

TestAndSet(boolean_ref lock) { 
    boolean initial = lock; 
    lock = true; 
    return initial;
}

可行的互斥实现

houselock的值为0，假如绿色进程先acquire，那么就会得到houselock的0值，并改houselock的值为1，由于不满足while条件，绿色进程进入了临界区。此时红色进程进行acquire，就会得到houselock的1值，并改houselock的值为1，满足while条件，触发忙等待。直到绿色进程将houselock的值改为0，破坏了红色进程的忙等。

Swap指令

语义

Swap(boolean *a, Boolean *b)
{
    Boolean temp;
    Temp = *a;
    *a = *b;
    *b = temp;
}

可行的互斥实现

Boolean k = true; // 初始化为1，局部变量
Boolean use = false; // 初始资源空闲，全局变量
while（k != 0）{
    Swap（&use, &k）; //进入区
}
Critial_region（）; //临界区
Swap（&use, &k）; //退出区
Other_region（）;

第一个进程进来时，k为1，use为0，进行交换后，k变为了0，use变为了1，不满足while条件，进入临界区，此时第二个进程执行swap，由于k和use都是1，所以交换后k还是1，满足while条件，进行忙等，直到第一个进程执行swap，把use变为0，才会破坏第二个进程的忙等。

忙等互斥缺陷

忙等:浪费CPU资源
会造成优先级反转

信号量互斥算法

信号量

定义

是一个确定的二元组(s, q)，其中s是一个具有非负初值的整型变量，q是一个初始状态为空的队列。
q是一个初始状态为空的队列，当有进程被阻塞时就会进入此队列。
使用中，s为正代表还有几个资源可用，为负代表队列中有几个进程在等待。

所以所见并非所得，你看到的它是一个像整型的变量，但实际上它是一个二元组，只不过q是被系统隐藏的。

分类

二元信号量，取值仅为0，1。主要用于互斥，你可以认为他就是锁
一般信号量，取值不限，初值为可用物理资源的总数，用于进程间的协作同步问题。
所以做题的时候，想实现互斥，就二极管信号量，如果是同步，就一般信号量。

信号量集
AND型信号量集
将进程需要的所有共享资源一次全部分配给它；待该进程使用完后再一起释放。
筷子要两根一起拿~

一般信号量集
在AND型信号量集的基础上进行扩充：进程对信号量Si的测试值为ti（用于信号量的判断，即 Si >= ti，表示资源数量低于ti时，便不予分配），占用值为di（用于信号量的增减，即Si = Si - di和Si = Si + di）
SP(S,d,q)代表对于信号量S，每次申请q个资源，当资源少于d个时，不予通过。