互联网公司笔经面经之操作系统

1、进程同步在多道程序环境下，当程序并发执行时，由于资源共享和进程合作，使同处于一个系统中的诸进程之间可能存在着以下两种形式的制约关系。直接制约：这种制约主要源于进程间的合作。例如，有一输入进程A通过单缓冲向进程B提供数据。当该缓冲空时，进程B因不能获得数据而阻塞，而当进程A把数据输入缓冲区后，便将进程B唤醒；反之，当缓冲区已满时，进程A因不能再向缓冲区投放数据而阻塞，当进程B将缓冲区数据取走后便可唤醒A。间接制约：这种制约主要源于资源共享。例如，多个进程共享一个打印机。进程同步的主要任务是对多个相关进程在执行次序上进行协调，以使并发执行的诸进程之间能有效地共享资源和相互合作，从而程序的执行具有可

2、再现性。线程概念：操作系统能够调度的最小单位。它被包含在进程之中，是进程中的实际运作单位。状态：就绪、运行、阻塞。进程和线程的区别：1. 进程是资源分配的基本单位，线程是处理机调度的基本单位。2. 线程是进程内的一个执行单元，一个进程可以拥有多个线程。3. 进程有独立的地址空间，线程没有独立的地址空间。4. 进程拥有资源，一个进程的所有线程共享该进程的资源。5. 线程之间的通信比较方便。同一进程下的线程共享数据（比如全局变量，静态变量），通过这些数据来通信不仅快捷而且方便，当然如何处理好这些访问的同步与互斥正是编写多线程程序的难点。而进程之间的通信只能通过进程间通信的方式进行。多进程和多线程的

3、区别：维度多进程多线程总结数据共享、同步数据是分开的:共享复杂，需要用IPC;同步简单多线程共享进程数据：共享简单；同步复杂各有优势内存、CPU占用内存多，切换复杂，CPU利用率低占用内存少，切换简单，CPU利用率高线程占优创建销毁、切换创建销毁、切换复杂，速度慢 创建销毁、切换简单，速度快 线程占优 编程调试编程简单，调试简单编程复杂，调试复杂进程占优 可靠性进程间不会相互影响 一个线程挂掉将导致整个进程挂掉进程占优分布式 适应于多核、多机分布 ；如果一台机器不够，扩展到多台机器比较简单适应于多核分布进程占优进程/线程同步方法常见的

4、进程/线程同步方法有互斥锁（或称互斥量Mutex）、读写锁（rdlock）、条件变量（cond）、信号量（Semophore）等。在windows系统中，临界区（Critical Section）和事件对象（Event）也是常用的同步方法。递归锁/非递归锁Mutex可以分为递归锁（recursive mutex）和非递归锁（non-recursive mutex）。 递归锁也叫可重入锁（reentrant mutex），非递归锁也叫不可重入锁（non-reentrant mutex）。二者唯一的区别是：同一个线程可以多次获取同一个递归锁，不会产生死锁。如果一个线程多次获取同一个非递归锁，则会产

5、生死锁。Windows下的Mutex和Critical Section是可递归的。Linux下的pthread_mutex_t锁是默认是非递归的。可以通过设置PTHREAD_MUTEX_RECURSIVE属性，将pthread_mutex_t锁设置为递归锁。线程同步：互斥量、读写锁、条件变量、信号量、临界区、事件。临界区速度快、效率高，但是只能用来同步本进程内的线程，不能用来同步多个进程中的线程。互斥量、信号量、事件可以跨进程使用，但涉及到用户态和内核态的切换，开销较大。互斥量只能用于一个资源的互斥访问，它不能实现多个资源的多线程互斥问题。信号量可以实现多个同类资源的多线程互斥和同步。(互斥量

6、的获得与释放是同一个线程)条件变量：特别适用于多个线程等待某个条件的发生。临界区：进程中用于访问临界资源的那段代码。临界区只能是在一个进程内部而无法跨进程，因为其不是一个内核对象，我们无法定义一个临界区对象来告知其他进程(临界区对其他进程来说是不可见的)，而像Mutex和SpinLock都可以。锁的类型：互斥锁(pthread_mutex_t)、读写锁(共享互斥锁)、自旋锁锁的粒度：如果锁的粒度太粗，就会出现很多线程阻塞等待相同的锁，这可能并不能改善并发性。如果锁的粒度太细，那么过多的锁开销会使系统性能受到影响，而且代码变得复杂。作为一个程序员，需要在满足锁需求的情况下，在代码复杂性和性能之间

7、找到正确的平衡。 死锁：如果线程试图对同一个互斥量加锁两次，那么它自身就会陷入死锁状态。其他：环路等待。产生死锁的原因主要是：（1） 因为系统资源不足。（2） 进程运行推进的顺序不合适。（3） 资源分配不当等。产生死锁的四个必要条件：（1）互斥条件：一个资源每次只能被一个进程使用。（2）请求与保持条件：一个进程因请求资源而阻塞时，对已获得的资源保持不放。（3）不剥夺条件:进程已获得的资源，在末使用完之前，不能强行剥夺。（4）循环等待条件:若干进程之间形成一种头尾相接的循环等待资源关系。可重入函数：可重入函数主要用于多任务环境中，一个可重入的函数简单来说就是可以被中断的函数，也就是说，可以在这个

8、函数执行的任何时刻中断它，转入OS调度下去执行另外一段代码，而返回控制时不会出现什么错误；而不可重入的函数由于使用了一些系统资源，比如全局变量区，中断向量表等，所以它如果被中断的话，可能会出现问题，这类函数是不能运行在多任务环境下的。线程安全：如果一个函数在同一时刻可以被多个线程安全地调用，就称该函数是线程安全的。如果一个函数对多个线程来说是可重入的，就说这个函数是线程安全的。如果多线程的程序运行结果是可预期的，而且与单线程的程序运行结果一样，那么说明是“线程安全”的。用户态、核心态：特权级别的概念虽然用户态下和内核态下工作的程序有很多差别，但最重要的差别就在于特权级的不同，即权力的不同。运行

9、在用户态下的程序不能直接访问操作系统内核数据结构和程序。用户态指非特权状态。在此状态下，执行的代码被硬件限定，不能进行某些操作，比如写入其他进程的存储空间，以防止给操作系统带来安全隐患。内核禁止此状态下的代码进行潜在危险的操作，比如写入系统配置文件、杀掉其他用户的进程、重启系统等。进程间通信管道：管道是一种半双工的通信方式，数据只能单向流动，而且只能在具有亲缘关系的进程间使用。命名管道：可用于无亲缘关系的进程间通信。信号：用于通知接收进程某个事件已经发生。信号量：信号量是一个计数器，可以用来控制多个进程对共享资源的访问。主要作为进程间以及同一进程内不同线程之间的同步手段。消息队列：消息队列是消

10、息的链表。消息队列克服了信号传递信息少、管道只能承载无格式字节流以及缓冲区大小受限等缺点。共享内存：共享内存就是映射一段能被其他进程所访问的内存。共享内存是最快的IPC方式。往往与其他通信机制，如信号量，配合使用，来实现进程间的同步和通信。套接字：与其他通信机制不同的是，它可用于不同机器间的进程间通信。管道的实现：在Linux中，管道是一种使用非常频繁的通信机制。从本质上说，管道也是一种文件，但它又和一般的文件有所不同，管道可以克服使用文件进行通信的两个问题，具体表现为：·      限制管道的大小。实际上，管道是一个固定大

11、小的缓冲区。在Linux中，该缓冲区的大小为1页，即4K字节，使得它的大小不象文件那样不加检验地增长。使用单个固定缓冲区也会带来问题，比如在写管道时可能变满，当这种情况发生时，随后对管道的write()调用将默认地被阻塞，等待某些数据被读取，以便腾出足够的空间供write()调用写。·      读取进程也可能工作得比写进程快。当所有当前进程数据已被读取时，管道变空。当这种情况发生时，一个随后的read()调用将默认地被阻塞，等待某些数据被写入，这解决了read()调用返回文件结束的问题。注意：从管道读数据是一次性操作，数据

12、一旦被读，它就从管道中被抛弃，释放空间以便写更多的数据。1. 管道的结构     在 Linux 中，管道的实现并没有使用专门的数据结构，而是借助了文件系统的file结构和VFS的索引节点inode。通过将两个 file 结构指向同一个临时的 VFS 索引节点，而这个 VFS 索引节点又指向一个物理页面而实现的。如图 7.1所示。  图7.1  管道结构示意图图7.1中有两个 file 

13、数据结构，但它们定义文件操作例程地址是不同的，其中一个是向管道中写入数据的例程地址，而另一个是从管道中读出数据的例程地址。这样，用户程序的系统调用仍然是通常的文件操作，而内核却利用这种抽象机制实现了管道这一特殊操作。glibc的malloc实现：对于小于128KB的请求来说，它会在现有的堆空间里面，按照堆分配算法为它分配一块空间并返回( 采用sbrk() )；对于大于128KB的请求来说，它会使用mmap()函数为它分配一块匿名空间，然后在这个匿名空间中为用户分配空间。在linux下，malloc()/free()的实现是由glibc库负责的。NUMA(Non-Uniform Memory A

14、ccess)存储器在物理上是分布式的。CPU访问本地内存的速度快于访问远地内存。Linux采用Node、Zone和页三级结构来描述物理内存在IA-32 架构上为：· DMA (16MB以下)· Normal (16MB896MB)· HighMem (896MB以上)Linux内核采用页式存储管理，进程的地址空间被划分成固定大小的“页面”；物理内存同样被分为与页面大小相同的“页帧”，由MMU在运行时将虚拟地址“映射”成某个物理内存页面上的地址。(TLB是一种cache，保存着线性地址与物理页面的对应关系)全局struct page结构体数组mem_map存放所有物

15、理页面信息。Buddy System：  Linux采用著名的伙伴系统(buddy system)算法来解决外碎片问题。把所有的空闲页框分组为11个块链表，每个块链表分别包含大小为1，2，4，8，16，32，64，128，256，512和1024个连续的页框。对1024个页框的最大请求对应着4MB大小的连续RAM块。满足以下条件的两个块称为伙伴：两个块具有相同的大小，记作b他们的物理地址是连续的第一块的第一个页框的物理地址是2*b*212的倍数缺点：由于使用 best-fit 方法的缘故，会产生内存浪费。ptmalloc：ptmalloc使用两种方法向内存索取空间：sbrk和mmap

16、。起初，brk值等于start_brk，heap大小为0。若用户请求的内存大于128KB(mmap分配阈值，可修改)，则调用mmap映射一块内存给用户，这块内存在释放时直接解除映射。若用户请求的内存小于128KB，则调用sbrk初始化一个heap。以后内存的分配和回收基于这个heap进行，如果heap满足不了用户的分配请求，就使用sbrk和mmap来满足。heap的管理涉及到两个概念，一个是chunk，一个是bin。ptmalloc使用一个chunk来表示用户请求分配的空间，用户请求释放的空间也用一个chunk来表示。chunk有两种状态，一种是正在被使用，一种是空闲。struct mallo

17、c_chunk INTERNAL_SIZE_T prev_size; /* Size of previous chunk (if free). */ INTERNAL_SIZE_T size; /* Size in bytes, including overhead. */ /整个结构体的大小，包括结构体数据和后面可用的空间的大小 struct malloc_chunk* fd; /* double links - used only if free. */ struct malloc_chunk* bk; /* Only used for large blocks: pointer to n

18、ext larger size. */ /后面用large bin再考虑 struct malloc_chunk* fd_nextsize; /* double links - used only if free. */ struct malloc_chunk* bk_nextsize;ptmalloc统一管理(heap和mmap映射区域中的)空闲的chunk。ptmalloc将相似大小的chunk用双向链表链接起来，这样的一个链表被称为一个bin。ptmalloc一共维护128个bin，并使用一个数组来存储这些bin。small bins：(编号2 -> 63，共62个)同一个smal

19、l bin中的chunk具有相同的大小，两个相邻的small bin中的chunk大小相差8 bytes。(small bin中的chunk按照最近使用顺序进行排列，最后释放的chunk被链接到链表的头部，而申请chunk是从链表尾部开始。)large bins：(编号64 -> 126，共63个)每个bin包含一个给定范围内的chunk，其中的chunk按照大小序排列，相同大小的chunk按照最近使用顺序排列。 fast bins： 为了加快小块内存的分配效率，ptmalloc引入了fast bins。回收的chunk小于max_fast(64B)，放入fast bins。当需要给用户

20、分配的chunk小于或等于64B，ptmalloc首先会在fast bins中查找相应的空闲块，然后才会去查找bins。在某个特定的时候，ptmalloc会遍历fast bins中的chunk，将相邻的空闲chunk进行合并，并将合并后的chunk放入unsorted bin中。(然后再将unsorted bin中的chunk加入bins中)unsorted bin：固定占据Bin1。如果被用户释放的chunk大于max_fast，或者fast bins中的空闲chunk合并后，这些chunk会被放到unsorted bin队列中。(unsorted bin可以看做是bins的一个缓冲区，增加

21、它只是为了加快分配的速度。)ptmalloc实际执行流程： ptmalloc首先会查找fast bins，如果不能找到匹配的chunk，则查找small bins。若还是不行，合并fast bins，把chunk 加入 unsorted bin，在unsorted bin中查找。若还是不行，把unsorted bin中的chunk加入large bins中，并查找large bins。若以上方法都失败了，则ptmalloc会考虑使用top chunk。若top chunk也不能满足分配要求，使用sbrk或mmap。slab分配器：简单理解Memcached的Slab Allocation实际上

22、，缓冲区就是主存中的一片区域，把这片区域划分为多个块，每块就是一个Slab，每个Slab由一个或多个页面组成，每个Slab中存放的就是对象。Linux中引入Slab的主要目的是为了减少对伙伴算法的调用次数。避免小块内存申请造成的内碎片问题。The slab allocator has three principle aims:· The allocation of small blocks of memory to help eliminate internal fragmentation that would be otherwise caused by the buddy sys

23、tem;· The caching of commonly used objects so that the system does not waste time allocating, initialising and destroying objects. Benchmarks on Solaris showed excellent speed improvements for allocations with the slab allocator in use;· The better utilisation of hardware cache by aligning

24、 objects to the L1 or L2 caches.  每个Slab的首部都有一个小小的区域是不用的，称为“着色区（coloring area）”。着色区的大小使Slab中的每个对象的起始地址都按高速缓存中的”缓存行（cache line）”大小进行对齐（80386的一级高速缓存行大小为16字节，Pentium为32字节）。因为Slab是由1个页面或多个页面（最多为32）组成，因此，每个Slab都是从一个页面边界开始的，它自然按高速缓存的缓冲行对齐。但是，Slab中的对象大小不确定，设置着色区的目的就是将Slab中第一个对象的起始地址往后推到与缓冲行对齐的位置。

25、因为一个缓冲区中有多个Slab，因此，应该把每个缓冲区中的各个Slab着色区的大小尽量安排成不同的大小，这样可以使得在不同的Slab中，处于同一相对位置的对象，让它们在高速缓存中的起始地址相互错开，这样就可以改善高速缓存的存取效率。磁盘组成：磁盘分区的最小单位是柱面（Cylinder）磁盘存储的最小单位是扇区（Sector）文件系统的最小单位是区块（Block）扇区一般取512 bytes大小。磁盘的第一个扇区主要记录了两个重要的信息：1. 主引导分区(Master Boot Record，MBR)，可以安装引导加载程序的地方，有446 bytes。2. 分区表(partition table

26、)，记录整块硬盘分区的状态，有64 bytes。分区类型：主分区、扩展分区。(逻辑分区是由扩展分区持续切割出来的分区)BIOS是一组设置硬件的电脑程序，保存在主板上的一块ROM芯片中。Boot loader储存有操作系统(OS)的相关信息，比如操作系统名称，操作系统内核 (kernel)所在位置等。常用的boot loader有GRUB和LILO。实际上，我们可以在多个分区安装boot loader，每个boot loader对应不同的操作系统，在读取MBR的时候选择我们想要启动的boot loader。这就是多操作系统的原理。(boot loader除了可以安装在MBR之外，还可以安装在每个

27、分区的引导扇区(boot sector)。)linux开机流程：BIOS -> MBR -> boot loader -> kernel计算机执行BIOS对应程序。接下来BIOS会去分析计算机里面有哪些存储设备。以硬盘为例，BIOS会依据用户的设置去取得能够开机的硬盘，并且到该硬盘里面去读取第一个扇区的MBR位置。MBR里面放置了引导加载程序boot loader。boot loader加载内核文件。 kernel会首先预留自己运行所需的内存空间，然后通过驱动程序(driver)检测计算机硬件。这样，操作系统就可以知道自己有哪些硬件可用。随后，kernel会启动一个init进程。它是Linux系统中的