读《计算机的心智》,另一个角度看操作系统

关于线程

线程模式: 一个进程至少包含一个线程，也可以包含多个线程。

线程提高多核CPU利用率： 让不同的线程运行在不同的处理器上，提高进程的执行速度。

线程管理: 线程控制表维护线程的各种信息。同一进程内的线程共享一块内存空间。

线程共享与独享资源划分

共享 独享
地址空间，全局变量，打开的文件，子进程，信号… 程序计数器，寄存器，栈，状态字

线程的三种实现方式

内核级线程实现方式(1:1线程模型)：

内核线程建立和销毁都是由操作系统负责、通过系统调用完成的。线程管理的所有工作由内核完成，应用程序没有进行线程管理的代码，只有一个到内核级线程的编程接口.内核为进程及其内部的每个线程维护上下文信息(线程表)，调度也是在内核基于线程架构的基础上完成。

一对一线程映射:内核线程驻留在内核空间，它们是内核对象。有了内核线程，每个用户线程被映射或绑定到一个内核线程。用户线程在其生命期内都会绑定到该内核线程。一旦用户线程终止，两个线程都将离开系统。

特点：当某个线程希望创建一个新线程或撤销一个已有线程时，它进行一个系统调用

优势：

  1. 多处理器系统中，内核能够并行执行同一进程内的多个线程
  2. 如果进程中的一个线程被阻塞，能够切换同一进程内的其他线程继续执行（用户级线程的一个缺点）
  3. 所有能够阻塞线程的调用都以系统调用的形式实现，代价很小
  4. 信号是发给进程而不是线程的，线程可以“注册”它们感兴趣的信号

缺陷：

  1. 效率低，每次线程切换都需要陷如内核
  2. 占用系统内核资源多，操作系统需要维护线程表

用户级线程实现方式(1:n线程模型)：

有关线程管理的所有工作都由应用程序完成，内核意识不到线程的存在. 应用程序可以通过使用线程库设计成多线程程序.

用户级线程仅存在于用户空间中，此类线程的创建、撤销、线程之间的同步与通信功能，都无须利用系统调用来实现。用户进程利用线程库来控制用户线程。由于线程在进程内切换的规则远比进程调度和切换的规则简单，不需要用户态/核心态切换，所以切换速度快。多见于一些历史悠久的操作系统。

用户级线程对于操作系统是不可见的，因此无法被调度到处理器内核。任意给定时刻每个进程只能够有一个线程在运行，而且只有一个处理器内核会被分配给该进程。

库调度器从进程的多个线程中选择一个线程，然后该线程和该进程允许的一个内核线程关联起来。内核线程将被操作系统调度器指派到处理器内核。用户级线程是一种”多对一”的线程映射。

特点：内核对线程包一无所知。从内核角度考虑，就是按正常的方式管理，即单线程进程（存在运行时系统）

优点：

  1. 可以在不支持线程的操作系统中实现。
  2. 创建和销毁线程、线程切换代价等线程管理的代价比内核线程少得多, 因为保存线程状态的过程和调用程序都只是本地过程
  3. 线程能够利用的表空间和堆栈空间比内核级线程多
  4. 不需要内陷，不需要上下文切换，也不需要对内存高速缓存进行刷新，使得线程调用非常快捷

缺陷：

  1. 线程发生I/O或页面故障引起的阻塞时，会阻塞整个进程从而阻塞所有线程
  2. 一个单独的进程内部，没有时钟中断，所以不可能用轮转调度的方式调度线程
  3. 资源调度按照进程进行，多个处理机下，同一个进程中的线程只能在同一个处理机下分时复用(无法利用计算机多核)

混合型线程(n:m线程模型)：

用户态的执行系统负责进程内部的线程在非阻塞时的切换；内核态的操作系统负责阻塞线程的切换，同时实现内核态和用户态线程管理。(用户态线程被多路复用到内核态线程上)

Java线程模型

Java线程的实现

Java中最常用的JVM是Oracle/Sun研发的HotSpot VM。在这个JVM的较新版本所支持的所有平台上，它都是使用内核级线程模型。

这种方式实现的线程，是直接由操作系统内核支持的——由内核完成线程切换，内核通过操纵调度器（Thread Scheduler）实现线程调度，并将线程任务反映到各个处理器上。内核线程是内核的一个分身。程序一般不直接使用该内核线程，而是使用其高级接口，即轻量级进程（LWP），也即线程。

线程调度(Java使用的线程调度方式是抢占式调度)

程调度是指系统为线程分配处理器使用权的过程，主要调度方式有两种，分别是协同式线程调度（Cooperative Threads-Scheduling）和抢占式线程调度（Preemptive Threads-Scheduling）。

如果使用协同式调度的多线程系统，线程的执行时间由线程本身来控制，线程把自己的工作执行完了之后，要主动通知系统切换到另外一个线程上。协同式多线程的最大好处是实现简单，而且由于线程要把自己的事情干完后才会进行线程切换，切换操作对线程自己是可知的，所以没有什么线程同步的问题。缺陷是会出现阻塞问题。

如果使用抢占式调度的多线程系统，那么每个线程将由系统来分配执行时间，线程的切换不由线程本身来决定（在Java中，Thread.yield（）可以让出执行时间，但是要获取执行时间的话，线程本身是没有什么办法的）。在这种实现线程调度的方式下，线程的执行时间是系统可控的，也不会有一个线程导致整个进程阻塞的问题。

Java的线程优先级

Java语言一共设置了10个级别的线程优先级（Thread.MIN_PRIORITY至Thread.MAX_PRIORITY），在两个线程同时处于Ready状态时，优先级越高的线程越容易被系统选择执行。Java的线程是通过映射到系统的原生线程上来实现的，所以线程调度最终还是取决于操作系统，操作系统的 优先级不一定和Java的会一一对应(Linux 1~99,Window 7种)，导致Java线程优先级不一定可靠。

Java线程状态转换

  1. 新建（New）：创建后尚未启动的线程处于这种状态。
  2. 运行（Runable）：Runable包括了操作系统线程状态中的Running和Ready，也就是处于此状态的线程有可能正在执行，也有可能正在等待着CPU为它分配执行时间。
  3. 无限期等待（Waiting）：处于这种状态的线程不会被分配CPU执行时间，它们要等待被其他线程显式地唤醒。以下方法会让线程陷入无限期的等待状态：
		没有设置Timeout参数的Object.wait（）方法。
		没有设置Timeout参数的Thread.join（）方法。
		LockSupport.park（）方法。
  1. 限期等待（Timed Waiting）：处于这种状态的线程也不会被分配CPU执行时间，不过无须等待被其他线程显式地唤醒，在一定时间之后它们会由系统自动唤 醒。以下方法会让线程进入限期等待状态：
		Thread.sleep（）方法。
		设置了Timeout参数的Object.wait（）方法。
		设置了Timeout参数的Thread.join（）方法。
		LockSupport.parkNanos（）方法。
		LockSupport.parkUntil（）方法。

5.阻塞（Blocked）：线程被阻塞了，“阻塞状态”与“等待状态”的区别是：“阻塞状态”在等待着获取到一个排他锁，这个事件将在另外一个线程放弃这个锁的时候发生；而“等待状态”则是在等待一段时间，或者唤醒动作的发生。在程序等待进入同步区域的时候，线程将进入这种状态。

6.结束（Terminated）：已终止线程的线程状态，线程已经结束执行。

image

线程同步

线程同步的目的：不管多线程之间的执行如何穿插，运行结果都是正确的。(保证多线程执行下结果的确定性)

多个线程争相执行同一段代码或访问同一资源的现象称为竞争，造成竞争的代码段或者资源称为临界区，通过协调限制任何时刻都只有一个线程在临界区里，称为互斥

线程同步方案

锁

锁的特征：

  1. 锁的初始状态是打开的
  2. 进入临界区必须获得锁
  3. 出临界区必须打开锁
  4. 如果别人持有锁，必须等待

缺陷:循环等待

Wait-Notify

sleep原语：进入睡眠，释放CPU wakeup原语:发送信号给指定进程

伪代码：

    define N 100
    int count = 0;
    void producer(void){
       while(true){
        if(count==N) sleep();
        //生产商品
        count = count + 1;
        if(count == 1)wakeup(consumer);
        }
    }
        
    void consumer(void){
        while(true){
            if(count==0) sleep();
            //获取商品
            count = count - 1;
            if(count == N -1 ) wakeup(producer);
        }
    }

缺陷：

  1. 如果消费者先获取商品，获取不到sleep，但是在sleep语句之前CPU切换，生产者生产商品，发送wakeup给消费者(此时消费者还没进入sleep）,当生产者生产完成，进入sleep之后，CPU切换为消费者，此时消费者继续进程Sleep，导致死锁。

2.count变量没有保护，会发生竞争

信号量-semphore

信号量是一个计数器，其取值为当前累积的信号数量，支持两个操作，加法操作up，减法操作down

  • up(一组原子操作):

    1. 将信号量的值加1,唤醒一个在该信号量上面等待的线程
    2. 程序继续执行

  • down(一组原子操作):

    1. 判断信号量的取值是否大于等于1
    2. true 将信号量的值减去1，继续执行
    3. false 在该信号量上等待

如果将信号量的取值限制为0和1，等效于锁。因为二元信号量是原子的，等效于锁+Wait-Notify

例子(进程B执行完再执行进程A)：

        - 进程A         进程B
        - down()        doSomeThing
        - doSomeThing   up()

伪代码：

    define N 100
    typedef int semphore;//定义信号量类型
    semphore mutex = 1;//互斥信号量
    semphore empty = N;//缓存区计数信号量,空位数量
    semphore full = 0;//缓存区计数信号量,商品数量
    
    void producer(void){
       while(true){
        down(empty);
        down(mutex);
        //生产商品
        up(mutex);
        up(full);
        }
    }
        
    void consumer(void){
        while(true){
            down(full);
            down(mutex);
            //获取商品
            up(mutex);
            up(empty);
        }
    }

缺陷：程序效率低下

管程monitor(监视器)

管程是一个程序语言级别的构造，它的正确运行由编译器保证。（Java Synchronized）

把需要同步的代码使用管程的构造框起来，即将需要保护的代码置于begin monitor 和 end monitor之间。编译器在识别到monitor包裹的代码块时，在翻译成低级代码时就会将需要的操作系统原语添加上去， 使两个线程不能同时活跃在同一个管程内。

管程的同步机制：锁(互斥) | 条件变量(控制执行的顺序)

缺陷：依赖编译器，只能在单台计算机上生效

锁的实现

线程上下文切换(切换线程)方式

中断启用和禁止来实现锁(繁忙等待)

  1. 线程自愿放弃CPU(yield之类的操作系统调用)
  2. 线程被强制放弃CPU而失去控制权(中断实现)

操作系统主要通过周期性时钟中断来获得CPU控制权。要想让一组操作变成原子操作，可以通过禁止中断，并且不自动调用yield之类让出CPU，防止进行切换，将一组操作变为原子操作。

unlock实现

    unlock(){
        disable interrupts;//启用中断
        value = FREE;//value设置为FREE
        enable interrupts;//禁止中断
    }

测试与设置指令来实现锁(繁忙等待)

测试与设置(test&set)指令 “读——修改——写”

  1. 设置操作：将x写入指定内存单元
  2. 读取操作：返回指定内存单元原来的值(写入x之前的值)

lock/unlock实现

    //value原始值=0
    lock(){
        while(test_and_set(value) == 1){
        }
    }

    unlock(){
        value = 0    
    }