操作系统知识点
并发和并行
并发：宏观上两个程序在同时运行，实际上是交织运行的，单个周期只运行了一个指令，用于提高效率。
并行：物理意义上的同时运行，如多核cpu，运行在不同的核上，互不影响。
进程和线程的概念，区别，使用场景
进程：资源分配的基本单位，实现了操作系统的并发。
线程：线程是进程的子任务，是CPU调度的基本单位，不拥有资源，但可以使用进程所属的资源。每个进程都有一个主线程，实际上是主线程来执行main函数中的代码。
进程在创建，撤销，切换时的开销都显著大于线程，系统要为之分配，回收，切换资源。
一个线程只属于一个进程，进程间不会相互影响，一个线程挂掉将影响整个进程挂掉。
线程并不是越多越好，每个线程都需要一个独立的堆栈空间，线程之间的切换需要保存很多中间状态，耗费程序运行时间。多线程开销远远小于多进程。
进程在同一时间只能干一件事，进程在执行过程中如果阻塞，整个进程就会挂起，然后其中有些工作并不依赖阻塞的资源，却还是卡在那里。因此引入线程，减少程序在并发时付出的时空开销。
一个进程可以创建多少个线程
理论上，一个进程可用虚拟空间是2G，默认情况下，线程的栈的大小是1MB，所以理论上最多只能创建2048个线程。如果要创建多于2048的话，必须修改编译器的设置。
因此，一个进程可以创建的线程数由可用虚拟空间和线程的栈的大小共同决定，只要虚拟空间足够，那么新线程的建立就会成功。如果需要创建超过2K以上的线程，减小你线程栈的大小就可以实现了，虽然在一般情况下，你不需要那么多的线程。过多的线程将会导致大量的时间浪费在线程切换上，给程序运行效率带来负面影响。
进程间通信方式
有时候想要在两个进程之间实现数据传输等操作，但进程之间又是相互独立的，有独立的虚拟地址空间，因此内核提供公共资源让两个线程都可以访问就可以实现进程通信了。
- 管道
- 普通管道PIPE：半双工，数据单向流动，返回一个包含两个整数的数组，一个用于读一个用于写。只能用于有父子进程和兄弟进程之间，只存在于内存中，其实就是内核中的一段缓存，子进程会复制父进程的fd[0],fd[1]，然后就可以实现进程间的通信。
- 命名管道FIFO：有具体的路径名，存在于文件系统中，因此可以在无关进程中交换数据。
- 套接字socket：可以用于不同主机间进行通讯
系统IPC
消息队列：消息的链接表，存放在内核中。具有写权限的进程可以向队列中添加消息，有读权限的进程可以从队列中读取信息。- 消息具有特定的格式和优先级，克服了信号传递信息少，管道只能承载无格式字节流已经缓冲区大小受限等特点
- 独立于发送和接收进程，进程终止是，消息队列及其内容不会被删除
可以实现消息的随机查询，不一定要先进先出地读取
信号量：计数器，控制多进程对共享资源的访问。（可以认为是一种特殊的锁）用于实现进程间的互斥和同步，不用于存储进程间的通信数据。一般需要结合共享内存和PV操作使用。
信号：在异常情况下用于通知接收进程某个事件已经发生
共享内存：使得多个进程可以访问同一块内存，不同进程可以及时看到对方进程中对共享内存的数据更新。这一块物理内存会映射成不同的虚拟地址空间，也就可以让不同的进程都看到这块内存。
- 最快的IPC，进程直接对内存进行存取，不需要对内存进行拷贝
- 并未提供同步机制，需要和互斥锁和信号量一起结合使用
进程同步
进程通信：进程间传送（大量）数据
进程同步：进程间共同完成一项任务时之间的直接制约关系，即执行先后顺序。
进程互斥：保证每次只有一个进程使用临界资源。
- 临界区：对临界资源进行访问的那端代码称为临界区。
- 同步与互斥：
- 进程同步：进程间共同完成一项任务时之间的直接制约关系，即执行先后顺序。
- 进程互斥：保证每次只有一个进程使用临界资源。
- 信号量：一般是整形变量，用来执行PV操作，即up和down操作。
注意不能先加锁再判empty，因为一旦加锁后发现缓冲区为0，就进入睡眠。此时缓冲区已经被加锁了，消费者就无法执行up(empty)操作，双方进入无限等待。
信号量实现生产者消费者问题：1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
typedef int semaphore;
semaphore mutex = 1;
semaphore empty = 100;
semaphore full = 0;
void producer() {
while (TRUE) {
int item = produce_item();
down(&empty);
down(&mutex);
insert_item(item);
up(&mutex);
up(&full);
}
}
void consumer() {
while (TRUE) {
down(&full);
down(&mutex);
int item = remove_item();
consume_item(item);
up(&mutex);
up(&empty);
}
}线程间通信/同步方式
同个进程下的线程之间都是共享进程的资源，只要是共享变量都可以做到线程间通信，比如全局变量，所以对于线程间关注的不是通信方式，而是关注多线程竞争共享资源的问题，信号量也同样可以在线程间实现互斥与同步
线程同步：即当有一个线程在对内存进行操作时，其他线程都不可以对这个内存地址进行操作，直到该线程完成操作，其他线程才能对该内存地址进行操作，而其他线程又处于等待状态，实现线程同步的方法有很多，临界区对象就是其中一种。
- 临界区：多个线程访问一个独占共享资源时，可以使用临界区对象，其它线程想访问，会被挂起，直到拥有临界区的线程放弃位置。
- 事件：允许一个线程在处理完之后，主动唤醒另外一个线程执行任务。
- 互斥量：互斥对象机制，拥有互斥对象的线程才有访问公共资源的权限。
- 信号量：允许多个线程在同一时刻访问同一个资源，但一般需要限制数目。
线程同步和进程同步的本质区别在于锁放在哪，放在私有的进程空间还是放在多进程共享的空间，并且看锁是否具备进程共享的属性。
Linux锁机制
- 互斥锁：mutex，用于保证任何时刻只能有一个线程访问该对象。当获取锁操作失败时，线程会主动放弃CPU，进入睡眠，直到锁被释放时唤醒。
- 读写锁：rwlock，分为读锁和写锁。允许多个线程同时读，但只能有一个线程写。写优先于读，一旦有写，则读必须等待。适用于读频率远远大于写的情况。
- 自旋锁：在任何时刻只能有一个线程访问对象，但是获取锁操作失败时，不会进入睡眠，而是在原地自旋（一直尝试获取锁），直到锁被释放。节省了线程从睡眠到被唤醒的消耗。但如果加锁时间很短，纯粹在浪费CPU，因此适用于加锁时间短的场景。
fork和vfork
fork()创建一个子进程，返回2次，一次在子进程中返回0，一次在父进程中返回子进程的pid，
子进程和父进程共享内存空间，采用写时复制，即父子可以同时读取内存，但如果需要对内存进行修改的话，就会复制一份该进程单独使用。毕竟一开始就进行内存复制是很浪费效率的。
vfork创建的子进程先于父进程运行，父子进程共用数据段，但若子进程依赖父进程操作，就会产生死锁。
进程状态切换
就绪态通过调度算法获得CPU时间，进入运行态；时间片用完进入就绪态，等待下一次调度。
运行态因确实资源（函数迟迟不返回），进入阻塞态，获得资源后进入就绪态。
分页系统地址映射
内存管理单元（MMU）实现了虚拟地址和物理地址之间的转换，其中的页表（数组）存储着程序地址空间和物理内存空间的映射表。
一个虚拟地址分成两个部分，一部分存储页面号，一部分存储偏移量。例如对于虚拟地址（0010 000000000100），前 4 位是存储页面号 2，读取表项内容为（110 1），页表项最后一位表示是否存在于内存中，1 表示存在。后 12 位存储偏移量。
物理地址 = 内存块号 * 页面大小 + 页内偏移量
进程调度算法
- 先来先服务FCFS：
非枪占式，按请求顺序进行调度。如果前面的进程太长，导致后面作业等待时间过长。 - 短作业优先SJF：
非抢占式，按估计运行时间最短的顺序进行调度。如果短作业一直来，长作业容易饿死。 - 最短剩余时间优先SRTN：
抢占式，按剩余运行时间进行调度。一个新作业来时，与当前进程的剩余时间进行比较。 - 时间片轮转：
按FCFS分配成一个队列，每个进程轮流执行一个时间片。效率和时间片大小有很大关系。时间片太短，进程切换太频繁；时间片太长，实时性无法保证。 - 优先级调度
给每个进程分配一个优先级，按优先级调度。为了防止低优先永远等不到，可以随着时间推移增加优先级。 - 多级反馈队列
设计出多个队列，每个队列时间片大小都不同，时间片小的队列优先级越高。
例如：一个进程先去时间片为1的队列，若出队后没有执行完，就去时间片2的队列队尾，以此类推。
可以看成是时间片轮转+优先级调度结合，效率较高。
OS缺页置换算法，虚拟内存置换方式
当访问内存中一个不存在的页时，且内存已满，就需要从内存中替换一个页。
- FIFO（先进先出）：置换最先进来的页面，即逗留时间最久的页面。
- LFU：最不经常访问淘汰算法
- LRU（最近最少访问）：置换最近一段时间内最久没被访问过的页面。
死锁
多个进行相互等待对方资源，在得到所有资源继续运行之前，都不会释放自己已有的资源，这样造成了循环等待的现象，称为死锁。
产生死锁的的四个条件：
- 互斥条件：一个资源每次只能被一个进程使用；
- 请求与保持条件：一个进程因请求资源而阻塞时，对已获得的资源保持不放；
- 不剥夺条件：进程已获得的资源，在没使用完之前，不能强行剥夺；
- 循环等待条件：多个进程之间形成一种互相循环等待资源的关系。
预防：
- 破坏环路等待
- 破坏互斥条件
- 破坏占有和等待条件
- 破坏不可抢占条件
解决死锁开销非常之大，目前没有一个操作系统可以实现。因此最好的办法是预防，而不是解决。而一般来说，大多数操作系统解决死锁的策略仅仅是忽略它。
预防（程序运行时防止）：银行家算法，在进行系统资源分配之前，先计算此次资源分配的安全性。若此次分配不会导致系统进入不安全状态，则将资源分配给进程；否则，让进程等待。
解除：
- 剥夺资源：从其它进程剥夺足够数量的资源给死锁进程，以解除死锁状态
- 撤消进程：可以直接撤消死锁进程或撤消代价最小的进程，直至有足够的资源可用，死锁状态消除为止；所谓代价是指优先级、运行代价、进程的重要性和价值等。
用户态和内核态
由于需要限制不同程序之间的访问能力，防止获取别的内存数据进行随意读写，产生了用户态和内核态。当程序需要申请外部资源就会由用户态进入内核态。
内核态：系统程序在内核态运行。该状态下，CPU可以访问内存的所有数据，包括外围设备，例如硬盘、网卡等。
用户态：应用程序只在用户态运行。该状态下只能受限的访问内存且不允许访问外设，占用CPU的能力被剥夺，导致CPU资源可以被其他程序获得。
用户态切换内核态：
- 系统调用：进程主动要求切换到内核态的一种方式，很多事情直接让程序去做是很危险的，于是内核态提供一些系统调用，程序通过这些系统调用让危险的事交由内核来执行。如fork，open，write，malloc等。
- 异常：异常是由CPU产生的，用户态程序发生未知异常，如常见的运行错误，除0，地址访问错误等等，转换到内核态处理此异常的相关程序中。如缺页异常。
- 中断：中断是由硬件设备产生的，设备完成用户请求操作后，会向CPU发出中断信号，然后内核放下手头的工作去处理中断信号。如硬盘读写结束后，发出中断信号，内核态处理该信号。
僵尸进程，孤儿进程，守护进程
僵尸进程：
kill掉子进程，父进程会收到SIGCHILD信号，子进程变成僵尸进程。僵尸进程没有任何作用，仅仅只是在进程列表中保留一项而已。
一个子进程结束了，但父进程还活着。因为内核认为父进程可能还需要子进程的一些信息，所以就没有将他关闭。
解决掉僵尸进程方式有：重启电脑，或者把父进程kill掉。
如何避免？
- 我们应该坚决不允许僵尸进程的存在。所以对于fork行为，我们应该拦截到SIGCHILD信号，然后使用waitpid获取子进程终止状态（返回0表示获取到子进程已被关闭）。
- 两次fork()也可以解决僵尸进程，子进程直接退出，让孙进程执行我们想要执行的任务，子进程先于孙子进程退出，孙进程就变成孤儿进程最后会被init进程接管了。但其实子进程还是得自己处理。
- signal(SIGCHLD,SIG_IGN)让父进程忽略该信号，交由内核回收。
补充：1
2
3
pid_t wait(int * statloc);
pid_t waitpid(pid_t pid,int *statloc,int options);
wait会阻塞直到某个子进程终止，而waitpid可以通过选项设置为非阻塞，而且是等待指定的pid的进程终止。
孤儿进程：
一个父进程退出，而它的一个或多个子进程还在运行，那么那些子进程将成为孤儿进程。孤儿进程将被init进程(进程号为1)所收养，并由init进程对它们完成状态收集工作。
把父进程杀死之后，僵尸进程就变成孤儿进程，而孤儿进程并不会有什么危害，因为自然有init进程对它进行回收。真正对系统有危害的是僵尸进程。
为什么要分配init进程收养孤儿进程？
进程的PCB是内核资源，是必须由父进程释放的。
守护进程：
一般来说生存周期长，随着操作系统一起开启和关闭。与终端无关联，不会占用终端。