操作系统
进程、线程、协程
进程 | 线程 | 协程 | |
---|---|---|---|
定义 | 系统进行资源调度和分配的基本单位 | CPU调度和分派的基本单位 | 用户态的轻量级线程,线程内部调度的基本单位 |
切换情况 | 进程CPU环境(栈、寄存器、页表和文件句柄等)的保存以及新调度的进程CPU环境的设置 | 保存和设置程序计数器、少量寄存器和栈的内容 | 先将寄存器上下文和栈保存,等切换回来的时候再进行恢复 |
切换者 | 操作系统 | 操作系统 | 用户 |
切换过程 | 用户态->内核态->用户态 | 用户态->内核态->用户态 | 用户态 |
调用栈 | 内核栈 | 内核栈 | 用户栈 |
拥有资源 | CPU资源、内存资源、文件资源和句柄等 | 程序计数器、寄存器、栈和状态字 | 拥有自己的寄存器上下文和栈 |
并发性 | 不同进程之间切换实现并发,各自占有CPU实现并行 | 一个进程内部的多个线程并发执行 | 同一时间只能执行一个协程,而其他协程处于休眠状态,适合对任务进行分时处理 |
系统开销 | 切换虚拟地址空间,切换内核栈和硬件上下文,CPU高速缓存失效、页表切换,开销很大 | 切换时只需保存和设置少量寄存器内容,因此开销很小 | 直接操作栈则基本没有内核切换的开销,可以不加锁的访问全局变量,所以上下文的切换非常快 |
通信方面 | 进程间通信需要借助操作系统 | 线程间可以直接读写进程数据段(如全局变量)来进行通信 | 共享内存、消息队列 |
进程与线程的区别?
答案一:
- 单位:进程是资源分配的基本单位,线程是CPU调度的基本单位。两者均可并发执行。
- 从属:一个线程只能属于一个进程,而一个进程可以有多个线程,但至少有一个线程。线程依赖于进程而存在。
- 资源:进程之间的资源是独立的,进程在执行过程中拥有独立的内存单元,而多个线程共享进程的内存。
- 资源分配给进程,同一进程的所有线程共享该进程的所有资源。
- 同一进程中的多个线程共享代码段(代码和常量),数据段(全局变量和静态变量),扩展段(堆存储)。但是每个线程拥有自己的栈段,栈段又叫运行时段,用来存放所有局部变量和临时变量。
- 系统开销:在创建或撤销进程时,系统都要为之分配或回收资源,系统开销显著大于创建或撤销线程的开销。
- 在进行进程切换时,设计到整个当前进程CPU环境的保存以及新被调度运行的进程的CPU环境的设置。
- 而线程切换只需要保存和设置少量寄存器的内容,并不涉及存储管理方面的操作。
- 切换进程的开销也远大于切换线程的开销。
- 进程编程调试简单可靠性高,但是创建、销毁、切换开销大;线程正相反,但是编程调试相对复杂
- 进程之间不会相互影响,一个进程崩溃后,在保护模式下不会对其他进程产生影响,但是一个线程崩溃会导致整个进程崩溃。所以多进程比多线程健壮。
答案二:根本区别就是多进程每个进程有自己的地址空间,线程则是共享地址空间。
- 速度:线程创建速度快,线程间通信快、切换快,因为它们在同一地址空间内
- 资源利用率:线程的资源利用率比较好也是因为它们在同一地址空间
- 同步问题:线程使用公共变量/内存时需要使用同步机制,也是因为它们在同一地址空间内。
协程
- 是一种比线程更加轻量级的存在。一个线程可以拥有多个协程;协程不是被操作系统内核管理,而完全是由程序所控制。
- 协程的开销远远小于线程;
- 协程拥有自己寄存器上下文和栈。协程调度切换时,将寄存器上下文和栈保存到其他地方,在切换回来的时候, 恢复先前保存的寄存器上下文和栈。
- 每个协程表示一个执行单元,有自己的本地数据,与其他协程共享全局数据和其他资源。
- 跨平台、跨体系架构、无需线程上下文切换的开销、方便切换控制流,简化编程模型;
- 协程又称为微线程,协程的完成主要靠yeild关键字,协程执行过程中,在子程序内部可中断,然后转而执行别 的子程序,在适当的时候再返回来接着执行;
- 协程极高的执行效率,和多线程相比,线程数量越多,协程的性能优势就越明显;
- 不需要多线程的锁机制;
进程的状态转换
进程包括三种状态:就绪、运行、阻塞
就绪 --> 运行:对就绪状态的进程,当进程调度程序按一种选定的策略从中选中一个就绪进程,为之分配处理机后,该进程便由就绪状态变为执行状态
运行 --> 阻塞:正在执行的进程因发生某等待事件而无法运行,则进程由执行状态变为阻塞状态,如进程提出输入/输出请求而变成带带外部设备传入信息的状态;进程申请资源(主存空间或外部设备)得不到满足时编程等待资源状态,进程运行中出现了故障(程序出错或主存储器读写错误等)编程等待干预状态等;
阻塞 --> 就绪:处于阻塞状态的进程,其等待的事件已经发生,如输入/输出完成;资源得到满足;或错误处理完毕时,处于等待状态的进程并不马上转入运行状态,而是先转入就绪状态,再由系统进程调度程序在适当的时候将改进成转为执行状态。
运行 --> 就绪 :正在执行的进程,因时间片用完而被暂停运行;或在采用抢占式优先级调度算法的系统中,当有更高优先级的进程要运行而被迫让出处理机时,该进程便从运行状态转变为就绪状态
进程调度算法有哪些?
- 先来先服务调度算法
- 有利于长作业,但不利于短作业。
- 时间片轮转调度算法
- 因为进程切换都要保存进程的信息并且载入新进程的信息,如果时间片太小,会导致进程切换得太频繁,在进程切换上就会花过多时间。
- 而如果时间片过长,那么实时性就不能得到保证。
- 短作业优先调度算法
- 长作业有可能会饿死,处于一直等待短作业执行完毕的状态。因为如果一直有短作业到来,那么长作业永远得不到调度。
- 最短剩余时间优先调度算法:
- 是针对最短进程优先增加了抢占机制的版本
- 高响应比优先调度算法:
- 主要用于作业调度,该算法是对先来先服务调度算法和短作业优先调度算法的一种综合平衡,同时考虑每个作业的等待时间和估计的运行时间
- 优先级调度算法
进程间的通信方式有哪些?
进程间通信是指在不同的进程之间传递数据或共享资源。由于每个进程都有自己的地址空间,因此进程间通信需要使用特殊的技术来实现,如管道、消息队列、共享内存和套接字等。
管道
管道主要包括普通管道和命名管道:普通管道可用于具有亲缘关系的父子进程间的通信,有名管道除了具有管道所具有的功能外,它还允许无亲缘关系进程的通信。
普通管道PIPE(无名管道):
- 半双工(数据只能在一个方向上流动),具有固定的读端和写端
- 只能用于具有亲缘关系的进程间通信(父子进程)
- 它可以看成是一种特殊的文件,对于它的读写也可以使用普通的read、write等函数。但是它不是普通的文件,不属于其他任何文件系统,并且只存在于内存中。
int pipe(int fd[2]);
当一个管道建立时,会创建两个文件文件描述符,要关闭管道只需将这两个文件描述符关闭即可。
命名管道FIFO:
- 可以在无关的进程之间交换数据
- 有路径名与之相关联,以一种特殊设备文件形式存在于文件系统中
int mkfifo(const char* pathname,mode_t mode);
消息队列
消息队列 MQ是把消息和队列结合起来,称之为消息队列(Message Queue)。把要传输的数据(消息)与队列进行绑定,用队列先进先出机制来实现消息传递。消息队列由 生产者 和 消费者 两部分构成;生产者主要负责产生消息并把消息放入队列中,再由消费者去处理。消费者可以到指定队列中获取消息,或者订阅相应的队列,最后由MQ服务端进行消息推送。
订阅:订阅就是为消费者服务的,消费者提前订阅,当消息队列中有消息产出时,自动去获取消息进行消费。生活中有很多这种例子,比如购买腾讯、优酷等视频会员时就会有订阅模式,当你的会员到期时,会自动帮你完成续费。
共享内存
- 共享内存指两个或多个进程共享一块指定的存储区,不同进程可以即时看到对方进程中对共享内存中数据的更新;
- 因为多个进程可以同时操作,所以需要进行同步;
- 信号量和共享内存通常结合在一起使用,信号量用来同步对共享内存的访问;
- 共享内存是最快的一种进程通信方式,因为进程是直接对内存进行存取。
套接字 SOCKET
是应用层与TCP/IP协议族通信的中间软件抽象层,是一组接口。通过调用接口中已经实现的方法建立用于不同主机之间的进程通信。
服务器的工作流程:
(1)创建 socket:创建服务端的socket。
(2)绑定 bind:把服务端用于通信的地址和端口绑定到socket上。
(3)监听 listen:把socket设置为监听模式。
(4)接受连接 accept:接受客户端的连接。
(5)通信 recv( ) / send( ) :与客户端通信,接收客户端发过来的报文后,回复处理结果,重复此过程。
(6)关闭 close( ):关闭socket,释放资源。
客户端工作流程:
(1)创建 socket:创建客户端的socket。
(2)发送连接 connect( ):向服务器发起连接请求。(TCP三次握手)
(3)通信 recv( ) / send( ):与服务端通信,发送一个报文后等待回复,然后再发下一个报文。重复此过程,直到全部的数据被发送完。
(4)关闭 close( ):关闭socket,释放资源。
线程的通信方式有哪些?
线程间通信是指在同一个进程内的不同线程之间传递数据或共享资源。由于所有线程都共享同一个地址空间,因此线程间通信比进程间通信更容易实现。常用的线程间通信方式包括互斥锁、条件变量和信号量等。
(1)临界区:
通过多线程的串行化来访问公共资源或一段代码,速度快,适合控制数据访问;
(2)信号量:
- 信号量的值=这种资源的剩余数量(信号量的值如果小于0,说明此时有进程在等待这种资源)
- P(S)——申请一个资源S,如果资源不够就阻塞等待
V(S)——释放一个资源S,如果有进程在等待该资源,则唤醒一个进程
sem_wait(sem_t *sem):
以原子操作的方式将信号量-1
,如果信号量值小于0
,则sem_wait
将被阻塞,直到这个信号量具有非0 值
。sem_post(sem_t *sem):
以原子操作将信号量值+1
。当信号量大于0
时,其他正在调用sem_wait
等待信号量的线程将被唤醒。
(3)互斥锁:
互斥锁主要用于线程互斥,不能保证按序访问,可以和条件锁一起实现同步。当进入临界区时,需要获得互斥锁并且加锁;当离开临界区时,需要对互斥锁解锁,以唤醒其他等待该互斥锁的线程。其主要的系统调用如下:
- pthread_mutex_init: 初始化互斥锁
- pthread_mutex_destroy:销毁互斥锁
- pthread_mutex_lock:以原子操作的方式给一个互斥锁加锁,如果目标互斥锁已经被上锁,pthread_mutex_lock 调用将阻塞,直到该互斥锁的占有者将其解锁。
- pthread_mutex_unlock: 以一个原子操作的方式给一个互斥锁解锁。
(4)事件(信号),Wait/Notify:
通过通知操作的方式来保持多线程同步,还可以方便的实现多线程优先级的比较操作
(5)条件变量:
条件变量,又称条件锁,用于在线程之间同步共享数据的值。条件变量提供一种线程间通信机制:当某个共享数据达到某个值时,唤醒等待这个共享数据的一个/多个线程。即,当某个共享变量等于某个值时,调用signal/broadcast。此时操作共享变量时需要加锁。其主要的系统调用如下:
- pthread_cond_init: 初始化条件变量
- pthread_cond_destroy:销毁条件变量
- pthread_cond_signal:唤醒一个等待目标条件变量的线程。哪个线程被唤醒取决于调度策略和优先级。
- pthread_cond_wait:等待目标条件变量。需要一个加锁的互斥锁确保操作的原子性。该函数中在进入
wait
状态前首先进行解锁,然后接收到信号后会再加锁,保证该线程对共享资源正确访问。
守护进程、孤儿进程、僵尸进程
守护进程
指在后台运行的,没有控制终端与之相连的进程。它独立于控制终端,周期性地执行某种任务。Linux的大多数服务器就是用守护进程的方式实现的,如Web服务器进程HTTP等。
孤儿进程
是指一个父进程退出后,而它的一个或多个子进程还在运行,那么这些子进程将成为孤儿进程。孤儿进程将被init进程(进程号为1 是内核启动的第一个用户级进程)所收养,并且由init进程对它们完成状态收集工作。
僵尸进程
是指一个进程使用fork函数创建子进程,如果子进程退出,而父进程并没有回收子进程,释放子进程占用的资源,那么子进程的进程描述符仍然保存在系统中,占用系统资源,这种进程称为僵尸进程。
区别是:孤儿进程是父进程已退出,子进程未退出;而僵尸进程是父进程未退出,子进程已退出。
如何解决僵尸进程?
(1)一般为了防止产生僵尸进程,在fork子进程之后我们都要及时使用wait系统调用;同时,当子进程退出的时候,内核都会给父进程一个SIGCHLD信号,所以我们可以建立一个捕获SIGCHLD信号的信号处理函数,在函数体中调用wait(或waitpid),就可以清理退出的子进程以达到防止僵尸进程的目的。
(2)使用kill命令。
打开终端并输入下面命令:
ps aux | grep Z
会列出进程表中所有僵尸进程的详细内容。
然后输入命令:
kill -s SIGCHLD pid(父进程pid)
这样子进程退出后,父进程就会收到信号了。
或者可以强制杀死父进程:
kill -9 pid(父进程pid)
这样父进程退出后,这些子进程将成为孤儿进程。孤儿进程将被init进程(进程号为1)所收养,并且由init进程对它们完成状态收集工作。
内存管理
置换算法有哪些?
当访问一个内存中不存在的页,并且内存已满,则需要从内存中调出一个页或将数据送至磁盘对换区,替换一个页,这种现象叫做缺页置换。当前操作系统最常采用的缺页置换算法如下:
最佳置换(OPT)算法:从主存中移出永远不再需要的页面;如无这样的页面存在,则选择最长时间不需要访问的页面。
先进先出(FIFO)算法:置换最先调入内存的页面,即置换在内存中驻留时间最久的页面。按照进入内存的先后次序排列成队列,从队尾进入,从队首删除。
最近最少使用(LRU)算法: 置换最近一段时间以来最长时间未访问过的页面。根据程序局部性原理,刚被访问的页面,可能马上又要被访问;而较长时间内没有被访问的页面,可能最近不会被访问。
时钟(CLOCK)置换算法:最佳置换算法性OPT能最好,但无法实现;先进先出置换算法实现简单,但算法性能差;最近最久未使用置换算法性能好,是最接近OPT算法性能的,但是实现起来需要专门的硬件支持,算法开销大。
所以操作系统的设计者尝试了很多算法,试图用比较小的开销接近LRU的性能,这类算法都是CLOCK算法的变体,因为算法要循环扫描缓冲区像时钟一样转动。所以叫clock算法。
时钟置换算法是一种性能和开销较均衡的算法,又称CLOCK算法,或最近未用算法(NRU,Not Recently Used)
简单的CLOCK算法实现方法:为每个页面设置一个访问位,再将内存中的页面都通过链接指针链接成一个循环队列。当某页被访问时,其访问位置为1。当需要淘汰-一个页面时,只需检查页的访问位。如果是0,就选择该页换出;如果是1,则将它置为0,暂不换出,继续检查下一个页面,若第- - ~轮扫描中所有页面都是1,则将这些页面的访问位依次置为0后,再进行第二轮扫描(第二轮扫描中一定会有访问位为0的页面,因此简单的CLOCK算法选择–个淘汰页面最多会经过两轮扫描)
LRU算法及实现
LRU算法用于缓存淘汰。思路是将缓存中最近最少使用的对象删除。实现方式:利用链表和hashmap。
当需要插入新的数据项的时候,如果新数据项在链表中存在(一般称为命中),则把该节点移到链表头部,如果不存在,则新建一个节点,放到链表头部,若缓存满了,则把链表最后一个节点删除即可。在访问数据的时候,如果数据项在链表中存在,则把该节点移到链表头部,否则返回-1。这样一来在链表尾部的节点就是最近最久未访问的数据项。
#include<bits/stdc++.h>
using namespace std;
class LRU
{
public:
LRU(int capacity): cap(capacity){}
int get(int key){
if(map.find(key) == map.end()) return -1;
auto key_value = *map[key]; // 迭代器解引用
cache.erase(map[key]);
cache.push_front(key_value);
map[key] = cache.begin();
cout << key_value.second <<endl;
return key_value.second;
}
void put(int key, int value) {
if (map.find(key) == map.end()) {
if (cache.size() == cap) {
map.erase(cache.back().first);
cache.pop_back();
}
}
else {
cache.erase(map[key]);
}
cache.push_front({key, value});
map[key] = cache.begin();
}
private:
int cap;
list<pair<int,int>> cache;
unordered_map<int,list<pair<int,int>>::iterator> map;
};
int main(){
LRU lRUCache = LRU(2);
lRUCache.put(1, 1); // 缓存是 {1=1}
lRUCache.put(2, 2); // 缓存是 {1=1, 2=2}
lRUCache.get(1); // 返回 1
lRUCache.put(3, 3); // 该操作会使得关键字 2 作废,缓存是 {1=1, 3=3}
lRUCache.get(2); // 返回 -1 (未找到)
lRUCache.put(4, 4); // 该操作会使得关键字 1 作废,缓存是 {4=4, 3=3}
lRUCache.get(1); // 返回 -1 (未找到)
lRUCache.get(3); // 返回 3
lRUCache.get(4); // 返回 4
}
分页和分段的区别?
- 段是信息的逻辑单位,它是根据用户的需要划分的,因此段是对用户可见的;页是信息的物理单位,是为了管理主存的方便而划分的,对用户是透明的;
- 段的大小不固定,有它所完成的功能决定;页的大小固定,由系统决定
- 段向用户提供二维地址空间;页向用户提供的是一维地址空间
- 段是信息的逻辑单位,便于存储保护和信息共享,页的保护和共享收到限制
抖动是什么?
刚刚换出的页面马上又要换入内存,刚刚换入的页面马上又要换出外存,这种频繁的页面调度行为称为抖动,或颠簸。产生抖动的主要原因是进程频繁访问的页面数目高于可用的物理块数(分配给进程的物理块不够)
为进程分配的物理块太少,会使进程发生抖动现象。为进程分配的物理块太多,又会降低系统整体的并发度,降低某些资源的利用率为了研究为应该为每个进程分配多少个物理块,Denning 提出了进程工作集”的概念
物理内存、虚拟内存、物理地址、逻辑地址的概念?
物理内存
寄存器:速度最快、量少、价格贵。
高速缓存:次之。
主存:再次之。
磁盘:速度最慢、量多、价格便宜。
虚拟内存:
虚拟内存是一种内存管理技术,它会使程序自己认为自己拥有一块很大且连续的内存,然而,这个程序在内存中不是连续的,并且有些还会在磁盘上,在需要时进行数据交换。虚拟内存与物理内存存在映射关系,通过页表寻址完成虚拟地址和物理地址的转换。
物理地址:
它是地址转换的最终地址,进程在运行时执行指令和访问数据最后都要通过物理地址从主存中存取,是内存单元的真正地址
逻辑地址:
是指用户看到的地址。逻辑地址并不一定是元素存储的真实地址,即数组元素的物理地址(在内存条中的所处的位置)并非是连续的,只是通过操作系统通过地址映射,将逻辑地址映射成连续的,这样使用更符合人们的直观思维
逻辑地址转物理地址
一句话来说:逻辑地址左移四位加偏移地址就是物理地址
逻辑地址 = 段地址:偏移地址
具体运算:段地址×16(左移四位,也就是2的四次方,相当于乘16)+偏移地址=物理地址(可以理解为段地址末尾补一个零)
逻辑地址是 1000H:0001H
那么物理地址为1000H×16+0001H=10001H
因为地址本身一般都是十六进制数,所以只需要把段地址左移一位末尾补0再和偏移地址加起来就是物理地址
虚拟内存的好处和坏处?
虚拟内存的好处
- 扩展了可用的内存空间:虚拟内存使得每个进程可以拥有比物理内存更大的地址空间。当物理内存不足时,操作系统可以将一部分暂时不使用的数据或代码存储在磁盘上,从而释放出物理内存供其他进程使用。
- 提供了更高的内存管理灵活性:虚拟内存允许操作系统将物理内存中的数据映射到磁盘上的文件,或者将磁盘文件映射到进程的地址空间中。这使得进程可以方便地读取和写入磁盘文件,而不需要关心具体的物理存储位置。
- 实现了内存保护和隔离:每个进程都有自己的虚拟地址空间,彼此之间是隔离的。这样可以防止一个进程意外地访问或修改其他进程的内存,提高了系统的稳定性和安全性。
- 提高了程序的执行效率:虚拟内存可以将物理内存中的数据按需加载到内存中,而不是一次性将整个程序加载到内存中。这样可以减少启动时间和内存占用,并且允许操作系统在需要时将不常用的数据置换到磁盘上,从而提高了整体的执行效率。
虚拟内存的代价:
- 虚存的管理需要建立很多数据结构,这些数据结构要占用额外的内存
- 虚拟地址到物理地址的转换,增加了指令的执行时间。
- 页面的换入换出需要磁盘I/O,这是很耗时的
- 如果一页中只有一部分数据,会浪费内存。
wait()函数
wait函数是用来及时回收我们的进程资源的。
进程一旦调用了wait函数,就立即阻塞自己本身,然后由wait函数自动分析当前进程的某个子进程是否已经退出,当找到一个已经变成僵尸的子进程,wait就会收集这个子进程的信息,并把它彻底销毁后返回;如果没有找到这样一个子进程,wait就会一直阻塞,直到有一个出现为止。函数原型如下:
#include<sys/types.h>
#include<sys/wait.h>
pid_t wait(int* status);
子进程的结束状态值会由参数status返回,而子进程的进程识别码也会一起返回。如果不需要结束状态值,则参数status可以设成 NULL。
fork()函数
fork函数用来创建一个子进程。对于父进程,fork()函数返回新创建的子进程的PID。对于子进程,fork()函数调用成功会返回0。如果创建出错,fork()函数返回-1。
#include <unistd.h>
pid_t fork(void);
fork()函数不需要参数,返回值是一个进程标识符PID。返回值有以下三种情况:
(1) 对于父进程,fork()函数返回新创建的子进程的PID。 (2) 对于子进程,fork()函数调用成功会返回0。 (3) 如果创建出错,fork()函数返回-1。
fork()函数创建一个新进程后,会为这个新进程分配进程空间,将父进程的进程空间中的内容复制到子进程的进程空间中,包括父进程的数据段和堆栈段,并且和父进程共享代码段。这时候,子进程和父进程一模一样,都接受系统的调度。因为两个进程都停留在fork()函数中,最后fork()函数会返回两次,一次在父进程中返回,一次在子进程中返回,两次返回的值不一样,如上面的三种情况。
其他
什么是并发和并行?
并发:对于单个CPU,在一个时刻只有一个进程在运行,但是线程的切换时间则减少到纳秒数量级,多个任务不停来回快速切换。
并行:对于多个CPU,多个进程同时运行。
区别:并行的"同时"是同一时刻可以多个任务在运行,并发的"同时"是经过不同线程快速切换,使得看上去多个任务同时都在运行的现象。
同步与异步、阻塞与非阻塞的区别?
同步:同步是指一个进程在执行请求需要一段时间才能返回信息,那么这个进程将会一直等待下去,直到收到返回信息才继续执行下去。
异步:异步是指进程不需要一直等下去, 而是继续执行下面的操作,当有消息返回时系统会通知进程进行处理,这样可以提高执行的效率。
阻塞:调用者调用了某个函数,等待这个函数返回,期间什么也不做,不停的检查这个函数有没有返回,必须等这个函数返回后才能进行下一步动作。
非阻塞:非阻塞等待,每隔一段时间就去检查IO事件是否就绪。没有就绪就可以做其他事情。
阻塞和非阻塞是线程的一种状态,同步和异步是指的是线程执行方法的一种方式,当然同步执行时,一般都伴随着线程的阻塞。
内核态与用户态的区别?
内核态与用户态:内核态(系统态)与用户态是操作系统的两种运行级别。内核态拥有最高权限,可以访问所有系统指令;用户态则只能访问一部分指令。
什么时候进入内核态:
系统调用(Trap) :用户态进程 主动 要求切换到内核态的一种方式,主要是为了使用内核态才能做的事情比如读取磁盘资源。系统调用的机制其核心还是使用了操作系统为用户特别开放的一个中断来实现。
中断(Interrupt) :当外围设备完成用户请求的操作后,会向 CPU 发出相应的中断信号,这时 CPU 会暂停执行下一条即将要执行的指令转而去执行与中断信号对应的处理程序,如果先前执行的指令是用户态下的程序,那么这个转换的过程自然也就发生了由用户态到内核态的切换。比如硬盘读写操作完成,系统会切换到硬盘读写的中断处理程序中执行后续操作等。
异常(Exception):当 CPU 在执行运行在用户态下的程序时,发生了某些事先不可知的异常,这时会触发由当前运行进程切换到处理此异常的内核相关程序中,也就转到了内核态,比如缺页异常。
其中,系统调用是主动的,另外两种是被动的。
为什么区分内核态与用户态:
在CPU的所有指令中,有一些指令是非常危险的,如果错用,将导致整个系统崩溃。比如:清内存、设置时钟等。所以区分内核态与用户态主要是出于安全的考虑。
中断流程?
中断是指当出现需要时,CPU暂时停止当前进程的执行,转而执行处理新情况的中断处理程序。当执行完该中断处理程序后,则重新从刚才停下的位置继续当前进程的运行。
为了区分不同的中断,每个设备有自己的中断号。系统有0-255一共256个中断。系统有一张中断向量表,用于存放256个中断的中断服务程序入口地址。每个入口地址对应一段代码,即中断服务程序。
外中断和异常有什么区别?
外中断是指由 CPU 执行指令以外的事件引起,如 I/O 完成中断,表示设备输入/输出处理已经完成,处理器能够发送下一个输入/输出请求。此外还有时钟中断、控制台中断等。
异常时由 CPU 执行指令的内部事件引起,如非法操作码、地址越界、算术溢出等。
什么是系统调用?
运行的用户程序中,凡是与系统态级别的资源有关的操作(如文件管理、进程控制、内存管理等),都必须通过系统调用方式向操作系统提出服务请求,系统调用和普通的函数调用非常相似。区别仅仅在于,系统调用由操作系统核心提供,运行于核心态;而普通的函数调用由函数库或用户自己提供,运行于用户态。
系统调用的过程可以简单分为以下几个步骤:
- 用户态的程序发起系统调用,因为系统调用中涉及一些特权指令(只能由操作系统内核态执行的指令),用户态程序权限不足,因此会中断执行,也就是 Trap(Trap 是一种中断)。
- 发生中断后,当前 CPU 执行的程序会中断,跳转到中断处理程序。内核程序开始执行,也就是开始处理系统调用。
- 内核处理完成后,主动触发 Trap,这样会再次发生中断,切换回用户态工作。
什么是死锁,产生的条件,如何解决、避免?
由于系统中存在一些不可剥夺资源,当两个或两个以上进程在执行过程中,因争夺资源而造成的相互等待,使每个进程都无法向前推进的现象。
产生的条件:死锁发生有四个必要条件:
- 互斥条件:进程对所分配到的资源不允许其他进程访问,若其他进程访问该资源,只能等待,直至占有该资源的进程使用完成后释放该资源;
- 请求和保持条件:进程获得一定的资源后,又对其他资源发出请求,但是该资源可能被其他进程占有,此时请求阻塞,但该进程不会释放自己已经占有的资源;
- 不可剥夺条件:进程已获得的资源,在未完成使用之前,不可被剥夺,只能在使用后自己释放;
- 环路等待条件:进程发生死锁后,必然存在一个进程-资源之间的环形链,链中每个进程已获得的资源同时被链中下一个进程所请求。
如何解决:
- 破坏请求和保持条件:
- 一次性分配所有资源,这样就不会再有请求了
- 只要有一个资源得不到分配,就不给这个进程分配其他资源
- 破坏不可剥夺资源:
- 当进程新的资源未得到满足时,释放已占有的资源,从而破坏不可剥夺的条件
- 破坏环路等待条件:
- 资源有序分配法:系统给每类资源赋予一个序号,每个进程按编号递增的请求资源,释放则相反,从而破坏环路等待的条件
- 鸵鸟策略:把头埋在沙子里,假装根本没发生问题。忽略死锁。
几种典型锁?
读写锁
- 多个读者可以同时进行读
- 写者必须互斥(只允许一个写者写,也不能读者写者同时进行)
- 写者优先于读者(一旦有写者,则后续读者必须等待,唤醒时优先考虑写者)
互斥锁
一次只能一个线程拥有互斥锁,其他线程只有等待
互斥锁是在抢锁失败的情况下主动放弃CPU进入睡眠状态直到锁的状态改变时再唤醒,而操作系统负责线程调度,为了实现锁的状态发生改变时唤醒阻塞的线程或者进程,需要把锁交给操作系统管理,所以互斥锁在加锁操作时涉及上下文的切换。互斥锁实际的效率还是可以让人接受的,加锁的时间大概100ns左右,而实际上互斥锁的一种可能的实现是先自旋一段时间,当自旋的时间超过阀值之后再将线程投入睡眠中,因此在并发运算中使用互斥锁(每次占用锁的时间很短)的效果可能不亚于使用自旋锁
条件变量
互斥锁一个明显的缺点是他只有两种状态:锁定和非锁定。而条件变量通过允许线程阻塞和等待另一个线程发送信号的方法弥补了互斥锁的不足,他常和互斥锁一起使用,以免出现竞态条件。当条件不满足时,线程往往解开相应的互斥锁并阻塞线程然后等待条件发生变化。一旦其他的某个线程改变了条件变量,他将通知相应的条件变量唤醒一个或多个正被此条件变量阻塞的线程。总的来说互斥锁是线程间互斥的机制,条件变量则是同步机制。
自旋锁
自旋锁的提出背景 由于在多处理器环境中某些资源的有限性,有时需要互斥访问(mutual exclusion),这时候就需要引入锁的概念,只有获取了锁的线程才能够对资源进行访问,由于多线程的核心是CPU的时间分片,所以同一时刻只能有一个线程获取到锁。那么就面临一个问题,那么没有获取到锁的线程应该怎么办?
通常有两种处理方式:一种是没有获取到锁的线程就一直循环等待判断该资源是否已经释放锁,这种锁叫做自旋锁,它不用将线程阻塞起来(NON-BLOCKING);还有一种处理方式就是把自己阻塞起来,等待重新调度请求,这种叫做互斥锁。
定义:当一个线程尝试去获取某一把锁的时候,如果这个锁此时已经被别人获取(占用),那么此线程就无法获取到这把锁,该线程将会等待,间隔一段时间后会再次尝试获取。这种采用循环加锁 -> 等待的机制被称为自旋锁(spinlock)。
悲观锁
总是假设最坏的情况,每次去拿数据的时候都认为别人会修改,所以每次在拿数据的时候都会上锁。
- 先获取锁,再进行业务操作,一般就是利用类似 SELECT … FOR UPDATE 这样的语句,对数据加锁,避免其他事务意外修改数据。
- 当数据库执行SELECT … FOR UPDATE时会获取被SELECT中的数据行的行锁,SELECT FOR UPDATE获取的行锁会在当前事务结束时自动释放,因此必须在事务中使用。
乐观锁
顾名思义,就是很乐观,每次去拿数据的时候都认为别人不会修改,所以不会上锁,但是在更新的时候会判断一下在此期间别人有没有去更新这个数据。先进行业务操作,只在最后实际更新数据时检查数据是否被更新过 如果没有发生冲突则直接修改,如果发生冲突则不做任何修改,然后把结果返回给用户,让用户自行处理。
五种IO模型
IO(Input/Output,输入/输出)即数据的读取(接收)或写入(发送)操作。通常用户进程中的一个完整IO分为两阶段:用户进程空间与内核空间之间的相互切换、内核空间与设备空间的相互切换(磁盘、网络等)。我们通常说的IO是指网络IO和磁盘IO两种。Linux中进程无法直接操作I/O设备,其必须通过系统调用请求内核来协助完成I/O动作;内核会为每个I/O设备维护一个缓冲区。对于一个输入操作来说,进程IO系统调用后,内核会先看缓冲区中有没有相应的缓存数据,没有的话再到设备中读取,因为设备IO一般速度较慢,需要等待;内核缓冲区有数据则直接复制到进程空间。所以,对于一个网络输入操作通常包括两个不同阶段:
- 等待网络数据到达网卡→读取到内核缓冲区,数据准备好;
- 从内核缓冲区复制数据到进程空间。
5种IO模型如下:
- 阻塞IO:进程发起IO系统调用后,进程被阻塞,转到内核空间处理,整个IO处理完毕后返回进程。操作成功则进程获取到数据。调用者将一直等待,不停的检查这个函数有没有返回,必须等这个函数返回后才能进行下一步动作。
- 非阻塞IO:进程发起IO系统调用后,进程被阻塞,内核数据还没好,不想让进程等待,就返回一个错误,这样进程就不阻塞了。进程每隔一段时间就发起IO系统调用去检查IO事件是否就绪。这样就实现非阻塞了。每个进程都有一个时间片,轮询的时候读取IO,时间片到了就要换另一个进程做其他事情了,这样就做到了每隔一段时间发起IO系统调用。
- IO多路复用:Linux用select/poll函数实现IO复用模型,这两个函数也会使进程阻塞,但是和阻塞IO所不同的是这两个函数可以同时阻塞多个IO操作。而且可以同时对多个读操作、写操作的IO函数进行检查。select/poll会监听所有的IO,直到有数据可读或可写时,才真正调用IO操作函数。
- 信号驱动IO:Linux用套接口进行信号驱动IO,安装一个信号处理函数,进程继续运行并不阻塞,当IO事件就绪,进程收到SIGIO信号,然后处理IO事件。这个好理解,这个信号直接通知进程数据到了。
- 异步IO:进程发起IO系统调用后立即返回,当内核将数据拷贝到缓冲区后,再通知应用程序。用户可以直接去使用数据。具体操作是进程调用aio_read函数告诉内核描述字缓冲区指针和缓冲区的大小、文件偏移及通知的方式,然后立即返回。
前四种属于同步IO,原因就在于进程发起IO系统调用读取数据时,这个真正拿到数据的过程依然是阻塞的,直到完成数据读取还要把数据拷贝到用户空间中,进程才能继续做其他事。 而异步IO就不一样了,进程完全做自己的事情,数据都不需要它读取,而是由内核读取数据并将数据拷贝到缓冲区后,再通知应用程序。用户可以直接去使用数据。
I/O 多路复用( IO multiplexing)
IO多路复用就是通过一个进程可以监视多个描述符,一旦某个描述符就绪(一般是读就绪或者写就绪),能够通知程序进行相应的读写操作的一种机制。
I/O多路复用的本质是使用select ,poll 或 epoll函数,挂起进程,当一个或多个IO事件发生之后,将控制返回给用户进程。
以服务器编程为例,传统的多进程(多线程)并发模型,在处理用户连接时都是开启一个新的线程或进程去处理一个新的连接,而IO多路复用则是可以在一个进程(线程)中同时监听多个网络IO事件,也就是多个文件描述符
I/O复用函数本身是阻塞的,能提高程序效率的原因在于它们具有同时监听多个I/O事件的能力。
select
int select (int n, fd_set *readfds, fd_set *writefds, fd_set *exceptfds, struct timeval *timeout);
每次调用select,都需要把监听的文件描述符集合 fd_set从用户态拷贝多内核态,从算法角度来说就是$O(N)$的时间开销
每次调用select返回之后都需要遍历所有文件描述符,判断哪些文件描述符有读写事件发生,也是$O(N)$的时间开销
内核对被监控的文件描述符的集合大小做了限制,并且这个是通过宏控制的,大小不可改变,为1024。这一点和上一个缺点是矛盾的,文件描述符设大了,遍历时间就长,其效率也会下降
poll
int poll (struct pollfd *fds, unsigned int nfds, int timeout);
struct pollfd {
int fd; /* file descriptor */
short events; /* requested events to watch */
short revents; /* returned events witnessed */
};
- poll和select本质上没有差别,管理多个描述符也是进行轮询,根据描述符的状态进行处理,但是poll没有最大文件描述符数量的限制。
- select采用fdset(fdset采用了bitmap),poll采用了数组,所以表示的描述符比select大
- poll和select同样存在一个缺点就是,文件描述符的数组被整体复制于用户态和内核态的地址空间之间,而不管这些文件描述符是否有事件,它们的开销随着文件描述符数量的增加而线性增大。
- poll返回后,也需要遍历整个描述符的数组才能得到有事件的描述符
epoll
int epoll_create(int size);//创建一个epoll的句柄,size用来告诉内核这个监听的数目一共有多大
int epoll_ctl(int epfd, int op, int fd, struct epoll_event *event);
int epoll_wait(int epfd, struct epoll_event * events, int maxevents, int timeout);
- epoll解决了select和poll在文件描述符集合拷贝和遍历上的问题,能够在一个进程中监听多个文件描述符,并且十分高效
- 在内核当中epoll是以红黑树的方式组织监听事件的,所以查询开销是O(logn)。采用回调的方式检测就绪事件,时间复杂度是O(1)
在注册监听事件时从用户态将数据传入内核态;当返回时需要将就绪队列的内容拷贝到用户空间
对于select和poll来说,所有文件描述符都是在用户态被加入其文件描述符集合的,每次调用都需要将整个集合拷贝到内核态;epoll则将整个文件描述符集合维护在内核态,每次添加文件描述符的时候都需要执行一个系统调用。系统调用的开销是很大的,而且在有很多短期活跃连接的情况下,epoll可能会慢于select和poll由于这些大量的系统调用开销。
- select使用线性表描述文件描述符集合,文件描述符有上限;poll使用链表来描述;epoll底层通过红黑树来描述,并且维护一个ready list,将事件表中已经就绪的事件添加到这里,在使用epoll_wait调用时,仅观察这个list中有没有数据即可。
- select和poll的最大开销来自内核判断是否有文件描述符就绪这一过程:每次执行select或poll调用时,它们会采用遍历的方式,遍历整个文件描述符集合去判断各个文件描述符是否有活动;epoll则不需要去以这种方式检查,当有活动产生时,会自动触发epoll回调函数通知epoll文件描述符,然后内核将这些就绪的文件描述符放到之前提到的ready list中等待epoll_wait调用后被处理。
- select和poll都只能工作在相对低效的LT模式下,而epoll同时支持LT和ET模式。
- 综上,当监测的fd数量较小,且各个fd都很活跃的情况下,建议使用select和poll;当监听的fd数量较多,且单位时间仅部分fd活跃的情况下,使用epoll会明显提升性能。
LT(电平触发)
假设委托内核检测读事件 -> 检测fd的读缓冲区 读缓冲区有数据 - > epoll检测到了会给用户通知 a.用户不读数据,数据一直在缓冲区,epoll 会一直通知 b.用户只读了一部分数据,epoll会通知 c.缓冲区的数据读完了,不通知 LT(level - triggered)是缺省的工作方式,并且同时支持 block 和 no-block socket。在这种做法中,内核告诉你一个文件描述符是否就绪了,然后你可以对这个就绪的 fd 进行 IO 操作。如果你不作任何操作,内核还是会继续通知你的。
效率会低于ET触发,尤其在高并发大流量的情况下。但是LT对代码编写要求比较低,不容易出现问题。LT模式服务编写上的表现是:只要有数据没有被获取,内核就不断通知你,因此不用担心时间丢失的情况。
ET(边缘触发)
假设委托内核检测读事件 -> 检测fd的读缓冲区 读缓冲区有数据 - > epoll检测到了会给用户通知 a.用户不读数据,数据一致在缓冲区中,epoll下次检测的时候就不通知了 b.用户只读了一部分数据,epoll不通知 c.缓冲区的数据读完了,不通知 ET(edge - triggered)是高速工作方式,只支持 no-block socket。在这种模式下,当描述符从未就绪变为就绪时,内核通过epoll告诉你。然后它会假设你知道文件描述符已经就绪,并且不会再为那个文件描述符发送更多的就绪通知,直到你做了某些操作导致那个文件描述符不再为就绪状态了。但是请注意,如果一直不对这个 fd 作 IO 操作(从而导致它再次变成未就绪),内核不会发送更多的通知(only once)。ET 模式在很大程度上减少了 epoll 事件被重复触发的次数,因此效率要比 LT 模式高。epoll工作在 ET 模式的时候,必须使用非阻塞套接口,以避免由于一个文件句柄的阻塞读/阻塞写操作把处理多个文件描述符的任务饿死。效率非常高,在高并发大流量的情况下,会比LT少很多epoll的系统调用,因此效率高。但是对编程要求高,需要细致的处理每个请求,否则容易发生丢失事件的情况。
对于采用LT工作模式的文件描述符,当epoll_wait检测到其上有事 件发生并将此事件通知应用程序后,应用程序可以不立即处理该事件。 这样,当应用程序下一次调用epoll_wait时,epoll_wait还会再次向应用 程序通告此事件,直到该事件被处理。而对于采用ET工作模式的文件 描述符,当epoll_wait检测到其上有事件发生并将此事件通知应用程序 后,应用程序必须立即处理该事件,因为后续的epoll_wait调用将不再 向应用程序通知这一事件。
- EPOLLIN : 表示对应的文件描述符可以读(包括对端SOCKET正常关闭);
- EPOLLOUT: 表示对应的文件描述符可以写;
- EPOLLPRI: 表示对应的文件描述符有紧急的数据可读(这里应该表示有带外数据到来);
- EPOLLERR: 表示对应的文件描述符发生错误;
- EPOLLHUP: 表示对应的文件描述符被挂断;
- EPOLLET: 将 EPOLL设为边缘触发(Edge Triggered)模式(默认为水平触发),这是相对于水平触发(Level Triggered)来说的。
EPOLLONESHOT: 只监听一次事件,当监听完这次事件之后,如果还需要继续监听这个socket的话,需要再次把这个socket加入到EPOLL队列
epoll_create()
创建红黑树的根节点epoll_ctl()
add,del,mod 增加、删除、修改结点epoll_wait()
把就绪队列的结点copy到用户态放到events里面,跟recv函数很像。等待事件的产生