文章目录
实现线程包的方法：
线程放在用户空间：
运行时系统：
一种介乎编译(Compile)和解释(Interpret)的运行方式，由编译器(Compiler)首先将源代码编译为一种中间码，在执行时由运行时(Runtime)充当解释器(Interpreter)对其解释。
具体方法：
线程在一个运行时系统的顶部运行，这个运行时系统是一个【管理线程的过程】的集合。在用户空间管理线程时，每个进程需要有专门的线程表，由运行时系统管理，用来追踪该进程中的所有线程。
if(线程引起本地阻塞){
/*调用一个运行时系统的过程*/
检查该线程是否必须进入阻塞状态
if(必须进入阻塞状态){
保存该线程的寄存器
查看表中可运行的就绪线程
将新线程的保存值重新装入机器的寄存器
/*只要堆栈指针和程序计数器一被切换，就运行新的线程*/
}
}
优点：
1）这样的线程切换比陷入内核快一个数量级（不需要陷阱，不需要上下文切换，不需要对高速缓存进行刷新）
2）用户级线程包可以在不支持线程的操作系统上实现，可以用函数库实现线程
3）允许每个进程有自己定制的调度线程算法（每个进程各自实现自己的线程在什么时候停止什么时候运行）
缺点：
进程间通信
进程间通信（IPC）不是中断
进程间通信要解决的问题：
1.如何传递信息
2.如何确保进程间在关键活动中不会出现交叉
3.正确的顺序
同样的问题和解决方法也适用于线程
竞争与互斥
竞争条件：两个或多个进程读写某些共享数据，而最后的结果取决于进程运行的精确时序
例如：两个进程都去修改原有数字，一个加，一个减，得到的结果却可能是只加或只减，而并非想象中的既加又减。
问题的症结在于，在进程A对共享变量的使用未结束之前，进程B就使用该共享变量
为解决该问题，就要实现互斥，使得
1）互斥：两个进程不能同时处于临界区中
2）不应该对CPU的速度和数量做任何假设
3）无忙等待：等待着的进程可以去睡眠
4）有限等待：不得使进程无限期等待进入临界区
临界区：对共享内存进行访问的程序片段
当一个进程在临界区中更新共享内存时，其他进程将不会进去其临界区，也不会带来任何麻烦
实现互斥
基于硬件的解决方法（仅适用于单处理器）
1.屏蔽中断
在每个进程刚刚进入临界区后立刻屏蔽所有中断（包括时钟中断），并在将要离开之前再打开中断
缺点：
1）对于多处理器的系统，其它CPU仍可以访问该共享内存
2）整个系统都会因此为你而停下来，影响了系统其他本应执行而且当前进程无关的操作
3）只能用于临界区很小的情况
2.锁变量（不可行）
缺点：
同样可能出现恰好在进程A锁变量之前，进程B被调度并提前锁了进程，无法解决竞争
3.严格轮换法（不可行）
缺点：
违反了“临界区外运行的进程不得阻塞其他进程”的原则
基于软件的解决方法（复杂）
4.Peterson解法（两个线程）
#define FALSE 0
#define TRUE 1
#define N 2 /*进程数量*/
int turn; /*现在轮到谁？*/
int interested[N]; /*所有值初始化为0*/
void enter_region(int process);/*进程号是0或1*/
{
int other; /*其他进程号*/
other = 1-process; /*另一方进程*/
interested[process] = TRUE; /*表明所感兴趣的*/
turn = process; /*设置标志*/
while (turn == process && interested[other] == TRUE);/*空语句*/
}
/* 后调用enter_region的进程1会因为先调用的进程0把interested[0]=TRUE而陷入死循环，
直到进程0调用leave_region*/
void leave_region(int process)/*进程：谁离开？*/
{
interested[process] = FALSE;/*表示离开临界区*/
}
5.Bakery算法：（n个线程）
Bakery算法就像是去银行，每个进来的人都要取号，按照号码大小来先后服务。如果恰好两个人的号码一致，则根据两个人各自的ID（例如身份证号）的大小来比较。
这两种方法的缺点是：
1）需要忙等待
2）如果没有硬件的保证，软件解决方案都不可行
3）相对复杂
原子指令（单处理器或多处理器均可）
原子指令指的是利用特殊的指令——TSL指令或exchange指令，来实现互斥
TSL指令的特别之处在于，执行TSL指令的CPU会在执行完成前锁住内存总线，不允许其他程序读写该寄存器
/*单条TSL指令包含三步：
1）从某一寄存器中读值
2）判断该值是否为1（并返回真或假）
3）将该寄存器赋值为1*/
boolean TestAndSet(boolean *target)
{
boolean rv = *target;
*target = TRUE;
return rv;
}
实现算法：
//忙等待
//缺点：线程在循环的等待过程会不停消耗CPU周期
class LOCK{
int value = 0;
}
LOCK::Acquire(){
while(TestAndSet(value))
;//spin
}
LOCK::Realease(){
value = 0;
}
为了解决忙等待问题，可以把等待着的进程放到队列中，就可以把CPU让出来给其他进程使用。退出的进程还要进行唤醒操作，来使得等待着的进程再次判断（TSL）
//无忙等待
class LOCK{
int value = 0;
WaitQueue q;
}
LOCK::Acquire(){
while(TestAndSet(value)){
add this TCB to wait queue q;
schedule();
;}//spin
}
LOCK::Realease(){
value = 0;
remove one thread t from q;
wakeup(t);
}
但其实忙等待更好，因为不需要上下文切换，而上下文切换同样需要很大的开销
同理，可以将TSL指令更换成exchange指令，令LOCK初始值为0，每个进程都拥有KEY。
当Acquire时，进程自身的KEY赋值为1，交换LOCK和KEY的值，KEY=1时进入循环，KEY=0时跳过循环进入临界区
当Release时，LOCK=0
优点：
1）实现简单
2）容易扩展到N个进程
3）开销小
缺点：
1）忙等待可能会有较大开销；
2）while判断会去抢LOCK，而这是一个随机的过程，从而可能有饥饿现象（某个进程很不幸一直不能进入临界区）；
3）会出现死锁（低优先级的进程一直不能进入临界区）