操作系统基础

1：文件的I/O方式

阻塞式文件I/O

阻塞式文件I/O模式是最普遍使用的文件I/O模式。大部分应用程序在对文件进行访问的时候使用的都是阻塞模式的I/O。 缺省情况下，标准输入输出读写，管道的读写、连接建立完成后的套接字都采用阻塞I/O 模式。如图14-1 所示，一旦进程期望读取数据，就调用read/write函数，进程从调用这些函数开始，一直到返回这段时间内都处理阻塞状态。当recv正常返回时，进程继续其他操作。

这种模式的优点在于操作简单，但整个进程在等待过程中处于阻塞状态，不能申请到CPU执行其他操作。

非阻塞式文件I/O

如果设置某个文件IO操作为非阻塞I/O,即相当于告诉内核:如果当前没有数据可操作, 将不阻塞当前进程，而是立即返回一个错误信息。如图14-2所示为非阻塞I/O操作模型。使用非阻塞I/O方式虽然不阻塞当前进程，但需要反复尝试。例如，为了从文件中获取数据，当前进程需要反复调用read/recv函数直至读取到数据。

多路复用I/O

多路复用方式仍然是以阻塞方式等待文件 IO 准备好，但其可以同时等待多个文件描述符，如果当前有一个或多个 socket 有状态发生变化 则从阻塞状态返回，转而处理该文件描述符 IO 操作，如图 14-3 所示。

多路复用技术一方面受限于阻塞的文件描述符数量的限制，另一方面，从系统角度来说，仍然只有一个进程与系统其他进程竞争资源 如果过量的文件 IO 操作必然影响当前服务性能。

信号驱动I/O

前面3种模式都是以同步方式去获取数据，因此，内核提供了另一种异步数据处理方式，其让内核在文件描述符就绪后产生SIGIO 信号，通知用户进程数据或者空间准备好，如图 14-4所示，这种模式称为信号驱动异步 I/O模式。这种处理方式使得用户进程不需要重复询问内
核该文件描述符对象是否准备好，从而大大提高了当前进程效率。

阻塞与非阻塞对比

在处理数据的传送与接收时，有阻塞和非阻塞两种操作方法。

1. 阻塞方式

   默认情况下 read/write 函数为阻塞方式，如果将 flag设置为0, recv/send函数也采用阻塞方式，即如果没有数据可操作，则该进程将被阻塞，当有数据时才继续执行并返回。

2. 非阻塞方式

   如果没有数据可接收就立即返回 -1, 表示接收失败，并修改系统全局变量errno 的值为 EAGAIN 表示数据未准备好。

2：(socket 多路复用)select , poll ,epoll

select( )

系统调用 select( )提供轮循等待的方式从多个文件描述符中获取状态变化后的情况 该函数声明如下

select机制的问题

1. 每次调用select，都需要把fd_set集合从用户态拷贝到内核态，如果fd_set集合很大时，那这个开销也很大
2. 同时每次调用select都需要在内核遍历传递进来的所有fd_set，如果fd_set集合很大时，那这个开销也很大
3. 为了减少数据拷贝带来的性能损坏，内核对被监控的fd_set集合大小做了限制，并且这个是通过宏控制的，大小不可改变(限制为1024)

poll( )

poll ppoll 函数可以实现比 select/pselect 函数更强大的功能，更细粒的等待时间。两函数声明如下：

poll的机制与select类似，与select在本质上没有多大差别，管理多个描述符也是进行轮询，根据描述符的状态进行处理，但是poll没有最大文件描述符数量的限制。也就是说，poll只解决了上面的问题3，并没有解决问题1，2的性能开销问题。

epoll( )

相对于select来说，epoll没有描述符个数限制，使用一个文件描述符管理多个描述符，将用户关心的文件描述符的事件存放到内核的一个事件表中，这样在用户空间和内核空间的copy只需一次。

epoll是Linux内核为处理大批量文件描述符而作了改进的poll，是Linux下多路复用IO接口select/poll的增强版本，它能显著提高程序在大量并发连接中只有少量活跃的情况下的系统CPU利用率。原因就是获取事件的时候，它无须遍历整个被侦听的描述符集，只要遍历那些被内核IO事件异步唤醒而加入Ready队列的描述符集合就行了。

epoll除了提供select/poll那种IO事件的水平触发（Level Triggered）外，还提供了边缘触发（Edge Triggered），这就使得用户空间程序有可能缓存IO状态，减少epoll_wait/epoll_pwait的调用，提高应用程序效率。

水平触发（LT）：默认工作模式，即当epoll_wait检测到某描述符事件就绪并通知应用程序时，应用程序可以不立即处理该事件；下次调用epoll_wait时，会再次通知此事件

边缘触发（ET）： 当epoll_wait检测到某描述符事件就绪并通知应用程序时，应用程序必须立即处理该事件。如果不处理，下次调用epoll_wait时，不会再次通知此事件。（直到你做了某些操作导致该描述符变成未就绪状态了，也就是说边缘触发只在状态由未就绪变为就绪时只通知一次）。

epoll是Linux目前大规模网络并发程序开发的首选模型。在绝大多数情况下性能远超select和poll。目前流行的高性能web服务器Nginx正式依赖于epoll提供的高效网络套接字轮询服务。但是，在并发连接不高的情况下，多线程+阻塞I/O方式可能性能更好。

3：进程通信方式及优缺点

1、管道（pipe）：管道是一种半双工的通信方式，数据只能单向流动，而且只能在具有亲缘关系的进程间使用。进程的亲缘关系通常是指父子进程关系。

2、有名管道（named pipe）：有名管道也是半双工的通信方式，但是它允许无亲缘关系进程之间的通信。
3、消息队列（message queue）：消息队列是消息的链表，存放在内核中并由消息队列表示符标示。消息队列克服了信号传递信息少，管道只能承载无格式字节流以及缓冲区大小受限制等缺点。
4、共享内存（shared memory）：共享内存就是映射一段内被其它进程所访问的内存，共享内存由一个进程创建，但是多个进程都可以访问。共享内存是最快的IPC，它是针对其它进程通信方式运行效率低的而专门设计的。它往往与其它通信机制。如信号量，配合使用，来实现进程间的同步和通信。
5、套接字（socket）：套接字也是进程间的通信机制，与其它通信机制不同的是，它可以用于不同机器间的进程通信。
6、信号（signal）：信号是一种比较复杂的通信方式，用于通知接受进程进程某个时间已经发生。
7、信号量（semaphore）：信号量是一个计数器，可以用来控制多个进程对共享资源的访问。它常作为一种锁的机制，防止某进程正在访问共享资源时，其它进程也访问该资源。因此它主要作为不同进程或者同一进程之间不同线程之间同步的手段。

4：进程、线程和协程

一、进程

  进程，直观点说，保存在硬盘上的程序运行以后，会在内存空间里形成一个独立的内存体，这个内存体有自己独立的地址空间，有自己的堆，上级挂靠单位是操作系统。操作系统会以进程为单位，分配系统资源（CPU时间片、内存等资源），进程是资源分配的最小单位

二、线程

线程，有时被称为轻量级进程(Lightweight Process，LWP），是操作系统调度（CPU调度）执行的最小单位

三：进程、线程区别与联系

【区别】：

调度：线程作为调度和分配的基本单位，进程作为拥有资源的基本单位；

并发性：不仅进程之间可以并发执行，同一个进程的多个线程之间也可并发执行；

拥有资源：进程是拥有资源的一个独立单位，线程不拥有系统资源，但可以访问隶属于进程的资源。进程所维护的是程序所包含的资源（静态资源）， 如：地址空间，打开的文件句柄集，文件系统状态，信号处理handler等；线程所维护的运行相关的资源（动态资源），如：运行栈，调度相关的控制信息，待处理的信号集等；

系统开销：在创建或撤消进程时，由于系统都要为之分配和回收资源，导致系统的开销明显大于创建或撤消线程时的开销。但是进程有独立的地址空间，一个进程崩溃后，在保护模式下不会对其它进程产生影响，而线程只是一个进程中的不同执行路径。线程有自己的堆栈和局部变量，但线程之间没有单独的地址空间，一个进程死掉就等于所有的线程死掉，所以多进程的程序要比多线程的程序健壮，但在进程切换时，耗费资源较大，效率要差一些。

【联系】：

一个线程只能属于一个进程，而一个进程可以有多个线程，但至少有一个线程；

资源分配给进程，同一进程的所有线程共享该进程的所有资源；

处理机分给线程，即真正在处理机上运行的是线程；

线程在执行过程中，需要协作同步。不同进程的线程间要利用消息通信的办法实现同步。

四：协程

协程，是一种比线程更加轻量级的存在，协程不是被操作系统内核所管理，而完全是由程序所控制（也就是在用户态执行）。这样带来的好处就是性能得到了很大的提升，不会像线程切换那样消耗资源。

  子程序，或者称为函数，在所有语言中都是层级调用，比如A调用B，B在执行过程中又调用了C，C执行完毕返回，B执行完毕返回，最后是A执行完毕。所以子程序调用是通过栈实现的，一个线程就是执行一个子程序。子程序调用总是一个入口，一次返回，调用顺序是明确的。而协程的调用和子程序不同。

  协程在子程序内部是可中断的，然后转而执行别的子程序，在适当的时候再返回来接着执行。

def A():
    print '1'
    print '2'
    print '3'

def B():
    print 'x'
    print 'y'
    print 'z'

假设由协程执行，在执行A的过程中，可以随时中断，去执行B，B也可能在执行过程中中断再去执行A，结果可能是：1 2 x y 3 z。

 协程的特点在于是一个线程执行，那和多线程比，协程有何优势？

极高的执行效率：因为子程序切换不是线程切换，而是由程序自身控制，因此，没有线程切换的开销，和多线程比，线程数量越多，协程的性能优势就越明显；

不需要多线程的锁机制：因为只有一个线程，也不存在同时写变量冲突，在协程中控制共享资源不加锁，只需要判断状态就好了，所以执行效率比多线程高很多。

5：死锁及解决

产生条件：

1. 互斥：至少有一个资源必须处于非共享模式，即一次只有一个进程可使用。如果另一进程申请该资源，那么申请进程应等到该资源释放为止。
2. 占有并等待：—个进程应占有至少一个资源，并等待另一个资源，而该资源为其他进程所占有。
3. 非抢占：资源不能被抢占，即资源只能被进程在完成任务后自愿释放。
4. 循环等待：有一组等待进程 {P0，P1，…，Pn}，P0 等待的资源为 P1 占有，P1 等待的资源为 P2 占有，……，Pn-1 等待的资源为 Pn 占有，Pn 等待的资源为 P0 占有。

我们强调所有四个条件必须同时成立才会出现死锁。循环等待条件意味着占有并等待条件，这样四个条件并不完全独立

有四种处理死锁的策略：
1)忽略该问题。也许如果你忽略它，它也会忽略你。
2)检测死锁并恢复。让死锁发生，检测它们是否发生，一旦发生死锁，采取行动解决问题。
3)仔细对资源进行分配，动态地避免死锁。
4)通过破坏引起死锁的四个必要条件之一，防止死锁的产生

解决办法：

操作系统层面：鸵鸟算法（当做什么都没发生）

银行家算法（预防）

语言层面：解决死锁问题的方法是：一种是用synchronized，一种是用Lock显式锁实现。

6：fork()和execve()

Linux中，fork()函数用来创建子进程，执行一次返回两个值，父进程中，返回子进程PID，子进程中，返回0

execve()函数用于在当前进程的上下文中加载并运行一个新程序

7：CPU调度算法

先到先服务调度算法（first-come,first-served (FCFS)

最短作业优先调度算法（shortest-job-first(SJF)schedulingalgorithm）

优先级调度算法（priority scheduling algorithm）

轮转法(round-robin,RR)

多级队列调度算法（multilevel queue scheduling algorithm）

多级反馈队列调度算法（multilevel feedback queue scheduling algorithm）

8：虚拟内存(段页式存储)

虚拟内存提供了三个重要的能力:

1. 它将主存看成是一一个存储在磁盘上的地址空间的高速缓存，在主存中只保存活动区域，并根据需要在磁盘和主存之间来回传送数据，通过这种方式，它高效地使用了主存。
2. 它为每个进程提供了一致的地址空间，从而简化了内存管理。
3. 它保护了每个进程的地址空间不被其他进程破坏。

在任意时刻，虚拟页面的集合都分为三个不相交的子集:
●未分配的: VM系统还未分配(或者创建)的页。未分配的块没有任何数据和它们相关联，因此也就不占用任何磁盘空间。
●缓存的:当前已缓存在物理内存中的已分配页。
●未缓存的:未缓存在物理内存中的已分配页。

页表：

段页存储：把虚拟地址空间先分段，再分页，方便管理和寻址

分段和分页的实现本质上是不同的：页面是定长的而段不是。

9：线程间通信方式

a) 互斥量(Mutex)：采用互斥对象机制，只有拥有互斥对象的线程才有访问公共资源的权限。比如 Java 中的 synchronized 关键词和各种 Lock 都是这种机制。

b) 信号量(Semphares)：它允许同一时刻多个线程访问同一资源，但是需要控制同一时刻访问此资源的最大线程数量。

c) 事件(Event):Wait/Notify：通过通知操作的方式来保持多线程同步，还可以方便的实现多线程优先级的比较操作。

10：孤儿进程和僵尸进程

当一个进程由于某种原因终止时，内核并不是立即把它从系统中清除。相反，进程被保持在一-种已终止的状态中，直到被它的父进程回收(reaped)。当父进程回收已终止的子进程时，内核将子进程的退出状态传递给父进程，然后抛弃已终止的进程，从此时开始，该进程就不存在了。一个终止了但还未被回收的进程称为僵尸进程(zombie)。

如果一个父进程终止了，内核会安排init进程成为它的孤儿进程的养父。init 进程的PID为1，是在系统启动时由内核创建的，它不会终止，是所有进程的祖先。如果父进程没有回收它的僵死子进程就终止了，那么内核会安排init进程去回收它们。不过，长时间运行的程序，比如shell或者服务器，总是应该回收它们的僵死子进程。即使僵死子进程没有运行，它们仍然消耗系统的内存资源。