操作系统基础知识

进程

进程是正在执行的程序，是操作系统资源分配的基本单位。一般包含指令、数据和PCB。

孤儿进程是指父进程退出，还在运行的子进程。孤儿进程会被init进程（id为1）收养，不会对系统造成危害。

僵尸进程是指子进程的进程描述符在退出时不会释放，父进程同时也没有进行wait()或waitpid()操作获取子进程信息，因此子进程的进程描述符还会保存在系统中。由于进程号是有限的，如果产生大量的僵尸进程，将会没有可用的进程号而导致系统不能产生新的进程。解决办法是杀死父进程。使之成为孤儿进程。

守护进程(daemon)是运行在后台的一种特殊进程，它是独立于控制终端的，并在周期性地执行某些任务。

线程

线程是进程内部的不同执行路径，是操作系统独立调度的基本单位。一个进程可以有多个线程，线程共享进程资源。浏览器进程有多个线程，如http请求线程、事件响应线程和渲染线程等等，可并发执行。

进程与线程的区别

拥有资源：进程是资源分配的基本单位，但线程不拥有资源，线程可以访问隶属于进程的资源。

调度：线程是独立调度的基本单位。

系统开销：创建、撤销和切换进程时的开销大于创建、撤销和切换线程时的开销。由于执行进程的操作时，系统需要分配或回收资源，如内存空间、I/O设备。进程切换时，需要保存当前cpu环境，进行新进程cpu环境的设置；而线程切换时只需要保存和设置少量寄存器内容，开销小。

通信方面：线程间可以通过直接读写同一进程的数据进行通信，而进程之间需要进行IPC进程间通信。

线程有哪两种？

用户级线程：有关线程管理的工作都应用程序完成。用户级线程的好处时非常高效，不需要进入内核空间，但并发效率不高。

内核级线程：有关线程管理的工作都有内核完成。应用程序调用内核线程的接口来进行线程管理。优点是内核可以将不同线程更好地分配到不同CPU，以实现真正地并行计算。

现代操作系统往往组合方式实现多线程，线程创建完全在用户空间中完成，并且一个应用程序中的多个用户级线程被映射到一些内核级线程中。

并发和并行

并发是一段时间内，多个任务都会被处理；但某一时刻，只有一个任务在执行。单核处理器可以做到并发。

并行是在同一时刻，有多个任务在执行。需要多核处理器。

分时系统和实时系统

分时系统就是系统把CPU时间分成很短的时间片，轮流地分配给多个作业。对多个用户的多个作业都可以保证足够快的响应时间，并且有效提高了资源利用率。

实时系统是系统对外部输入的信息，能够在规定的时间内处理完毕并做出反应。优点时集中地及时地处理并作出反应，高可靠，安全性。

进程状态

创建、就绪、运行、终止和阻塞。

就绪状态是进程获得除了CPU之外的一切所需资源，一旦得到CPU即可运行。

阻塞状态为等待某资源或I/O。

运行态->阻塞态往往是由于等待外设，等待主存等资源分配或等待人工干预。

运行态->就绪态往往是时间片用完或更高优先级的进程抢占处理器。

进程调度算法

先来先服务：有利于长作业，不利于短作业。短作业等待时间过长。对I/O密集型进程也不利。

短作业优先：按估计运行时间最短的顺序进行调度。长作业可能会饿死，一直有短作业到来，长作业就永远得不到调度。

最短剩余时间优先：短作业优先的抢占版。

时间片轮转：将所有就绪进程按先来先服务排成队列，每次调度，把CPU时间分配给队首进程，执行一个时间片。时间片用完时，将进程送往就绪队列的末尾，同时继续把CPU时间进行分配。

时间片太小进程切换的时间花费多。

时间片过长则实时性就不能保证。

优先级调度：每个进程分配优先级，抢占式。为防止低优先级得不到调度，可以随着时间的增加，增加等待进程的优先级。

抢占式：操作系统可以强行将运行的进程暂停，调度器将CPU分配给其他就绪进程。

非抢占式：调度器一旦把处理机分配给某进程，便可以一直让他运行下去，知道阻塞或完成。

上下文切换

是一种将CPU资源从一个进程分配到另一个进程的机制。

死锁

在两个或多个并发进程中，如果一个进程集合中的每个进程都在等待只能由该进程集合中的其他进程才能引发的事件，那么该进程集合就产生了死锁。

死锁条件：（1）互斥：每个资源要么已经分配给了一个进程，要么就是可用的。（2）占有和等待：已经得到了某个资源的进程可以再请求新的资源。（3）不可抢占：已经分配给一个进程的资源不能强制性地被抢占，只能被占有进程显式地释放。（4）环路等待：有2个或2个以上的进程组成一条环路，每个进程等待下一个进程所占有的资源。

解决办法：

鸵鸟策略：直接忽略死锁。解决死锁代价很高，但死锁影响没那么大，发生概率不高。

死锁预防：破坏4个必要条件，避免发生死锁。

死锁避免：允许3个必要条件，但通过算法判断资源请求是否可能导致循环等待的形成并相应决策，来避免死锁点的产生。线程启动拒绝：如果一个线程的请求会引发死锁，则不允许其启动。资源分配拒绝：如果一个线程增加的资源请求会导致死锁，则不允许此申请。

死锁检测和恢复：维护一个系统的资源分配图，定期进行死锁检测，如果有则解决死锁。

进程同步

临界区、互斥量、信号量、管程。

进程间通信：

管道：实质为内核缓冲区，可看成循环队列。半双工。

命名管道：FIFO，提供了一个路径名与之关联，不具有亲缘关系的进程也可以彼此通信。

消息队列：消息的链表，存放在内存中。存在唯一标识。

共享内存：多个进程可以直接读写同一块内存空间。

信号量：控制多个进程对共享资源的访问。

socket：套接字，不在同一主机的两个进程网络通信。

磁盘调度算法

先来先服务：按照磁盘请求顺序调度。优点是公平和简单。但平均寻道时间可能会较长。

最短寻道时间优先：优先调度与当前磁头最近的磁道。可能会发生饥饿。

电梯算法scan扫描算法：总是保持一个方向运行，直到该方向没有请求为止。解决了饥饿问题。

虚拟内存

物理内存扩充成更大的逻辑内存，从而让程序获得更多的可用内存。使用部分加载的技术，从而能加载更多的进程，看起来内存变大了，磁盘或者硬盘。

页面替换算法

最佳算法：选择被换出的页面最长时间内不再被访问，通常可以保证获得最低的缺页率。理论算法。

先进先出：但也可能会把经常访问的页面换出。

LRU：根据过去判断。将最近最久未使用的页面换出。维护一个链表。页面访问则将之移动到表头。由于需要更新链表，因此LRU代价很高。

时钟算法：时钟算法使用环形链表，0则不替换，1则替换。