操作系统

线程池

线程池就是首先创建一些线程，他们的集合称为线程池。使用线程池可以很好地提高性能，线程池在系统启动时即创建大量空闲的线程，程序将一个任务传给线程池，线程池就会启动一条线程来执行这个任务，执行结束以后，该线程并不会死亡，而是再次返回线程池中成为空闲状态，等待执行下一个任务。

1、设置一个生产者消费者队列，作为临界资源

2、初始化n个线程，并让其运行起来，加锁去队列取任务运行

3、当任务队列为空的时候，线程阻塞

4、当生产者队列来了一个任务后，先对队列加锁，把任务挂在队列上，然后使用条件变量去通知阻塞中一个线程

进程和线程概念及区别

进程：进程是对运行时程序的封装，是系统进行资源调度和分配的基本单位，实现了操作系统的并发；进程=程序+数据+PCB(进程控制块)

线程：是进程的子任务，是CPU调度与分配的基本单位，用于保证程序的实时性，实现了线程内部的并发。

区别：

• 线程属于进程，一个线程只能属于一个进程，进程可以拥有多个线程，线程依赖于进程存在
• 进程是资源分配的基本单位，线程是CPU调度的基本单位
• 进程执行的过程中拥有独立内存单元，线程共享进程的内存
• 进程切换资源开销大，线程小
• 进程间不会相互影响，一个线程挂了整个进程就会挂掉

进程的通信

可以通过管道、系统IPC实现进程的通信

管道是半双工的，具有固定的读端和写端，它可以用于具有亲缘关系的进程之间的通信。

系统IPC：

消息队列：消息的链接表，存放在内核中，一个消息队列由一个标识符来标记。面向记录

信号量：就是一个计数器，可以用来控制多个进程对共享资源的访问。用于实现进程间的互斥与同步

共享内存：他使得多个进程可以访问同一块内存空间，不同进程可以及时看到对方进程对共享内存数据的更新。

进程调度策略

• 先来先服务(FCFS)： 队列实现，非抢占的，先请求先分配CPU
• 最短作业优先调度(SJF)： 平均等待时间最短，但难以知道下一个CPU区间长度
• 优先级调度算法： 优先级高的先分配，相同优先级的先到先服务。容易出现饥饿
• 时间片轮转调度： 每个进程执行只分配一个时间片的CPU时间，时间片结束，进程被抢占并放回就绪队列

进程的五种基本状态

创建状态：进程正在被创建

就绪状态：进程被加入到就绪队列中等待CPU调度运行

执行状态：进程正在被运行

等待阻塞状态：进程因为某种原因，比如等待I/O，等待设备，而暂时不能运行

终止状态：进程运行完毕

就绪状态被调度变为执行状态，发生时间片到了或者高优先级则会从执行变为就绪

执行状态因等待某事件而睡眠变为等待阻塞

等待阻塞因等待事件发生而唤醒变为就绪

上下文切换

上下文切换(Context Switch)是一种将CPU资源从一个进程分配给另一个进程的机制 。在切换的过程中，操作系统需要先存储当前进程的状态(包括内存空间的指针，当前执行完的指令等等)，再读入下一个进程的状态，然后执行此进程。（ 程序计数器、CPU寄存器状态等数据 ）

进程切换一般分两步：

• 切换页目录以使用新的地址空间（只有进程需要做）
• 切换内核栈和硬件上下文（线程与进程都要做）确实

进程交换过程

进程交换技术： 换出一部分进程到外存，腾出内存空间

将内存暂时不能运行的进程，或者暂时不用的数据和程序，换出到外存，来腾出足够的内存空间，把已经具备运行条件的进程，或进程所需的数据和程序换入到内存。

挂起状态： 进程被交换到外存，进程状态就成为了挂起状态

活动阻塞：进程在内存中，但由于某种原因被阻塞了

静止阻塞：进程在外存，同时被某种原因阻塞了

活动就绪：进程在内存，处于就绪状态，只要给CPU和调度就可以运行

静止就绪：进程在外存，处于就绪状态，只要调度到内存，给CPU和调度就可以运行

活动就绪到静止就绪（内存不够，调到外存）

活动阻塞到静止阻塞（内存不够，调到外存）

执行到静止就绪（时间片用完）

系统分配的资源

处理器、存储器、I/O 设备以及信息

线程的通信及同步

线程通信主要通过：使用全局变量、使用消息实现通信、使用事件实现通信

线程同步的方式：

临界区：通过多线程的串行化来访问公共资源或一段代码、速度快、适合控制数据访问

互斥量：采用互斥对象机制、只有拥有互斥对象的线程才有访问公共资源的权限。因为互斥对象只有一个、所以保证公共资源不会被多个线程同时访问

信号量：为具有有限数量的用户资源而设计的，它允许多个线程在同一时刻去访问同一个资源（但一般需要限制同一时刻访问此资源的最大线程数目）

事件：通过通知操作的方式来保持多线程同步，还可以方便实现多线程优先级的比较操作

守护、僵尸、孤儿进程的概念

• 守护进程：运行在后台的一种特殊进程，独立于控制终端并周期性地执行某些任务。
• 僵尸进程：一个进程 fork 子进程，子进程退出，而父进程没有wait/waitpid子进程，那么子进程的进程描述符仍保存在系统中，这样的进程称为僵尸进程。
• 孤儿进程：一个父进程退出，而它的一个或多个子进程还在运行，这些子进程称为孤儿进程。（孤儿进程将由 init 进程收养并对它们完成状态收集工作）

死锁

死锁指两个或两个以上的线程，因资源的争夺而相互等待的现象

死锁的四个条件：

互斥条件、不可剥夺条件、请求与保持条件、环路等待条件

死锁避免：系统对进程发出的每一个系统能够满足的资源申请进行动态检查，并根据检查结果决定是否分配资源，如果分配后系统可能发生死锁，则不予分配，否则予以分配，这是一种保证系统不进入死锁状态的动态策略。

预防死锁解决办法：可剥夺资源、资源一次性分配、资源有序分配

4种锁

互斥锁：用于保证任意时刻只有一个线程访问对象，当获得锁操作失败时，线程会进入睡眠，直到锁释放时被唤醒

读写锁：分为读锁和写锁，对于读锁，允许多个线程同时获得读锁，但对于写锁，同一时刻只允许一个线程获得写锁，并且写锁会堵塞其他写锁与读锁。写锁优先与读锁。

自旋锁：和互斥锁差不多，区别在于获取锁失败线程不会睡眠，而是原地自旋等待锁释放

条件锁：同步线程之间同步贡献数据的值，当某个共享数据到达某个值时，唤醒等待这个共享数据的一个/多个线程

分页和分段的区别

段式存储管理： 将程序的地址空间划分为若干段，如代码段，数据段，堆栈段；段大小可变，所以没有内碎片（可以改变大小消除内碎片，但是在换出的时候会产生外碎片）

页式存储管理： 将程序的逻辑地址分为固定大小的页，而物理内存划分为同样大小的帧，程序加载时，将需要的一页放入内存中的任意一帧，这些帧不必连续，从而实现了离散分离。优点：没有外碎片，但会产生内碎片。

结合二者优点产生了段页式存储管理，内存分段，段内分页

不同：

• 大小不同：页的大小固定且由操作系统决定，段的长度却不固定，由其所完成的功能决定
• 地址空间不同：段向用户提供二维地址空间；页向用户提供的是一维地址空间
• 内存碎片不同：页没有外碎片有内碎片，段 相反

虚拟内存

虚拟内存是计算机管理内存的一种技术；他可以让所有进程共享同一物理内存，每一个进程只把自己当前需要的虚拟内存空间存储到物理内存中。每个进程创建时，只建立好虚拟内存和磁盘文件之间的映射，等到运行到对应程序时，通过缺页中断，来拷贝数据到物理内存中

可以扩大地址空间，当物理内存不足时可以当做一个临时的“物理内存”，保护内存。让电脑可以运行比物理内存大很多的程序

页面置换需要磁盘I/O，非常耗时，虚拟地址转物理地址，增加了指令的执行时间；内存中可以保留多个进程，提高了系统并发度

缺页中断

在请求分页系统中，可以通过查询页表中的状态位来确定所要访问的页面是否存在于内存。每当所要访问的页面不在内存中，就会产生缺页中断，此时操作系统会根据页表中的外存地址在外存中找到所缺的一页，将其调入内存

中断的4个步骤：

保护CPU现场、分析中断原因、转入缺页中断处理程序进行处理、恢复CPU现场，继续执行

页面置换算法

先进先出淘汰算法（FIFO）：最先进入的数据最先被淘汰，新加入的页面放队尾

最近最不经常访问淘汰算法（LFU）：每个数据块引用一个计数，对数据块进行计数排序，计数相同的按时间排序，每次淘汰队尾数据块

最近最少使用替换算法（LRU）：使用一个栈，新页面或者命中的页面将其移到栈低，每次替换掉栈顶的元素（其实可以用双向链表去实现，相对较快点）

在LRU基础上进行拓展有LRU-K 和2Q算法用于解决LRU缓存污染问题

缓存污染：突然大量偶发性的数据访问，会让内存中存放大量冷数据

局部性原理

• 时间上的局部性： 最近被访问的页在不久的将来还会被访问
• 空间上的局部性： 内存中被访问的页周围的页也很可能被访问

页表寻址

通过页表，有逻辑地址的高位想找到逻辑地址对应的页基地址，再由页基地址偏移一定长度就得到最后的物理地址，偏移长度有逻辑地址低位决定

页表：页表内容就是该进程的虚拟地址到物理地址的一个映射，每一项都记录了这个页的基地址

fork和vfork

fork：成功调用的话，会创建一个新的进程，它几乎与调用fork()的进程一模一样。父进程调用成功返回子进程的pid，子进程调用成功返回0，出现错误返回一个负值

vfork：在fork基础上加了，子进程必须要执行一次对exec的调用，或者调用exit_()退出。

内核态和用户态

内核态和用户态是操作系统两种工作模式，两者区别主要是特权级不同，用户态特权级较低，内核态较高。运行在用户态的程序不能直接访问系统内核数据结构和程序。但是可以通过系统调用的方式切换到内核态进行访问。

3种用户态切换内核态的方式：系统调用、异常、外围设备的中断

系统调用

用户态进程主动要求切换到内核态的一种方式

栈内存和堆内存的区别

• 栈内存：由程序自动向操作系统申请分配以及回收，速度快，使用方便，但程序员无法控制。若分配失败，则提示栈溢出错误。注意，const局部变量也储存在栈区内，栈区向地址减小的方向增长。
• 堆内存：程序员向操作系统申请一块内存，当系统收到程序的申请时，会遍历一个记录空闲内存地址的链表，寻找第一个空间大于所申请空间的堆结点，然后将该结点从空闲结点链表中删除，并将该结点的空间分配给程序。分配的速度较慢，地址不连续，容易碎片化。此外，由程序员申请，同时也必须由程序员负责销毁，否则则导致内存泄露。