0%

面经1

发表于 更新于 分类于 ，

进程与线程的概念

基本概念：

进程是对运行时程序的封装，是系统进行资源调度和分配的的基本单位，实现了操作系统的并发；

线程是进程的子任务，是CPU调度和分派的基本单位，用于保证程序的实时性，实现进程内部的并发；线程是操作系统可识别的最小执行和调度单位。每个线程都独自占用一个虚拟处理器：独自的寄存器组，指令计数器和处理器状态。每个线程完成不同的任务，但是共享同一地址空间（也就是同样的 动态内存，映射文件，目标代码等等），打开的文件队列和其他内核资源。

区别：

  • 通信：由于同一个进程间共享内存资源，因此线程间的通信较简单，通过简单的全局变量即可，也可以结合信号量，互斥量等实现互同步互斥等。而进程间的通信需要通过内核，借助IPC方式
  • 开销：线程的切换开销小。由于每个进程的资源是独立分配的，因此进程的创建和销毁都伴随着资源分配和释放，创建更慢。而一个进程中的多个线程只需要分配独立的栈，其他的资源则是共享的，因此创建开销小。同时线程的切换速度也快，因为进程的地址空间是独立的，进程之间的页表不同，当进程切换，页表需要重新从内存（或外存）中重新加载到缓存中（多级页表可能是分布式存储需要从外存加载）使得切换速度慢，而同一进程的线程切换只需要设置少量的cpu寄存器状态即可。
  • 调试和应用场景：线程调试困难可靠性低，一个线程挂掉会导致整个进程挂掉，适合多核场景；进程调试简单可靠性高，一个进程崩掉不会影响其他的进程，且多核多机的场景都适合。
  • 性质：线程是任务调度的最小单位，而进程是资源分配的最小单位

从Linux实现上，它其实并没有专门区分进程和线程的概念。它使用了相同函数去创建进程/线程，通过设置是否共享资源的入口参数来创建进程/线程。

多进程和多线程的使用场景

多进程应用场景

  • 例如 谷歌浏览器的每个页面就是一个单独的进程
  • 电脑中每个软件就是一个独立的进程，这个软件崩了不会影响其他的软件
  • 多机分布式环境

多线程场景

  • 需要频繁创建和销毁的场景使用线程效率更高，例如web服务器处理客户的连接，一个线程一个连接
  • 对于需要频繁的数据共享的场景，使用线程可以降低通信的开销
  • 对于需要快速响应的场景，例如GUI界面，如果算法耗时很多，就会导致界面假死无法响应用户的请求

内核线程和用户线程

这里讲的用户线程是编译层面通过编程语言实现的用户线程，即协程。内核线程就是常规的线程（还有一种内核线程的称呼是指只运行在内核态的线程，是操作系统创建的用于完成操作系统事务的线程，也叫守护线程，它和普通的线程一样被同等调度）但是这里讨论的实际是协程和线程的区别。

协程是用户在编译器层面使用编程语言模拟出的线程，不通过系统调用，不用陷入内核，这时候创建新线程比较快，这就是用户线程。多个协程运行在一个线程上，OS感知不到协程的存在，它只是对承载这些协程的线程进行调度，因此如果协程中有IO阻塞操作导致线程被阻塞，那么所有的协程都无法再被调度。这种情况需要程序员自己避免，可以使用异步IO代替阻塞IO，手动调度协程。

而常规的线程是 由操作系统维护的，它的创建和调度都要从用户态陷入内核态，所以线程的切换代价高于协程。但是由于操作系统调度，所以不会因为一个线程的IO阻塞而饿死其他线程。

协程的优点：

  • 协程极高的执行效率。因为子程序切换不是线程切换，而是由程序自身控制，因此，没有线程切换的开销，和多线程比，线程数量越多，协程的性能优势就越明显
  • 第二大优势就是不需要多线程的锁机制，因为只有一个线程，也不存在同时写变量冲突，在协程中控制共享资源不加锁，只需要判断状态就好了，所以执行效率比多线程高很多

为什么进程切换比线程慢

首先无论进程还是线程切换都需要保存寄存器值，例如SP 栈寄存器，PC程序计数器指向下一条要执行的指令，EAX累加寄存器，用于加法乘法的确信寄存器等。但是 每个进程都有自己的虚拟地址空间， 进程内的所有线程共享进程的虚拟地址空间，进程切换涉及虚拟地址空间的切换而线程不会。把虚拟地址空间转换为物理地址是通过页表实现的，为了加速页表的查找速度，通常要使用缓存来存储常用的地址映射，即TLB。每个进程有自己的页表，当进程切换后，缓存就失效了，导致命中率低，那么虚拟地址转换为物理地址就会变慢，表现出来的就是程序运行会变慢，而线程切换则不会导致TLB失效，因为线程线程无需切换地址空间，因此我们通常说线程切换要比较进程切换快，原因就在这里。（为了加速虚拟地址的转换速度，会将常用的地址映射存放在缓存中，进程切换，页表也改变会导致缓存命中率低，同时就需要重新从内存中将新的页表加载进缓存，所以进程切换比线程切换慢的原因就在这儿）

进程间通信的方式

进程间通信主要包括管道、消息队列、信号量、信号、共享内存、以及套接字socket。

  1. 管道：分为无名管道 和 有名管道，他们都只支持半双工的通信，通信时接收双方必须同时存在，由于传输的是字节流，需要程序自行定义通信协议。管道是存在于内存中，只是形式和文件类似，当消息被读取出便不再存在。

    • 无名管道：只能用于有亲缘关系的进程之间通信。

    • 有名管道：有路径名称与之关联，以一种特殊的文件形式存在于内存中。所以可以用于没有关系的进程之间通信。

  2. 消息队列：消息队列，是消息的链接表，存放在内核中。一个消息队列由一个标识符（即队列ID）来标记。 (消息队列克服了信号传递信息少，管道只能承载无格式字节流以及缓冲区大小受限等特点)具有写权限得进程可以按照一定得规则向消息队列中添加新信息；对消息队列有读权限得进程则可以从消息队列中读取信息；

    • 消息队列是面向记录的，其中的消息具有特定的格式以及特定的优先级。
    • 消息队列独立于发送与接收进程。进程终止时，消息队列及其内容并不会被删除
    • 消息队列可以实现消息的随机查询,消息不一定要以先进先出的次序读取,也可以按消息的类型读取

  3. 信号量：是一个计数器，用来控制进程间的同步或互斥访问。

    • 如果要传递信息，则需要结合共享内存，来实现同步或者互斥访问
    • 信号量基于 操作系统 的 P V操作，程序对信号的操作都是原子操作
    • P V，不仅只能对信号量的减加 还 可以加减任意正整数 当信号量为0时，进程休眠
    • 支持信号量组

  4. 信号： 用于通知接收进程某个事件已经发生

  5. 共享内存：它使得多个进程可以访问同一块内存空间，不同进程可以及时看到对方进程中对共享内存中数据得更新。这种方式需要依靠某种同步操作，如互斥锁和信号量等

    • 是速度最快的一种 IPC 因为 进程是直接对内存进行存取
    • 因为多个进程可以同时操作，所以需要进行同步。信号量+共享内存通常结合在一起使用，信号量用来同步对共享内存的访问

  6. 套接字SOCKET：它用于不同主机之间的进程通信

线程间通信的方式：

  1. 临界区：通过多线程的串行化来访问公共资源或一段代码，速度快，适合控制数据访问。如果有多个线程试图同时访问临界区，那么 在有一个线程进入后其他所有试图访问此临界区的线程将被挂起，并一直持续到进入临界区的线程离开。 * EnterCriticalSection() 进入临界区
    • LeaveCriticalSection()离开临界区
  2. 互斥量Synchronized/Lock：采用互斥对象机制，只有拥有互斥对象的线程才有访问公共资源的权限。因为互斥对象只有一个，所以可以保证公共资源不会被多个线程同时访问。
  3. 信号量 Semphare：为控制具有有限数量的用户资源而设计的，它允许多个线程在同一时刻去访问同一个资源，但一般需要限制同一时刻访问此资源的最大线程数目。
  4. 事件(信号)，Wait/Notify：通过通知操作的方式来保持多线程同步，还可以方便的实现多线程优先级的比较操作

对比：临界区是非内核对象，它运行在用户态，因此只能用于同一个进程中的线程之间的互斥访问，但是临界区的效率是最高的。而后面都是内核对象可以用于不同进程的线程之间的同步互斥。

Linux虚拟地址空间

程序拥有自己的地址空间，这个地址空间被分割成多个块，每一块称为一页。这些页被映射到物理内存，但不需要映射到连续的物理内存，也不需要所有页都必须在物理内存中。当程序引用到不在物理内存中的页时，由硬件执行必要的映射，将缺失的部分装入物理内存并重新执行失败的指令。还有进程运行过程中，要动态分配内存，比如 malloc时，也只是分配了虚拟内存，即为这块虚拟内存对应的页表项做相应设置，当进程真正访问到此数据时，才引发缺页异常。

好处：

  1. 可以控制物理内存的访问权限，对特定的地址设置保护，防止在用户模式下执行错误的指令而意外改写内核数据
  2. 每个进程的地址空间独立，通过页表映射到物理地址，可以防止不同进程之间相互干扰，一个进程无无法访问其他进程的地址空间
  3. 通过页面的换入换出可以在小内存中运行大程序。另一方面由于逻辑地址不是全部都映射到具体的物理地址的，只有在读写时引发缺页异常才会进行映射，因此可以在内存上同时保留多个进程，提高系统的并发度
  4. 可以将连续的逻辑地址映射到不连续的物理地址上，提高内存利用率

虚拟内存的代价：

  1. 虚存的管理需要建立很多数据结构，这些数据结构要占用额外的内存
  2. 虚拟地址到物理地址的转换，增加了指令的执行时间
  3. 页面的换入换出需要磁盘I/O，这是很耗时的
  4. 如果一页中只有一部分数据，会浪费内存

请你回答一下为什么要有page cache，操作系统怎么设计的page cache

加快从磁盘读取文件的速率。page cache 中有一部分磁盘文件的缓存，因为从磁盘中读取文件比较慢，所以读取文件先去page cache 中去查找，如果命中，则不需要去磁盘中读取，大大加快读取速度。

当系统需要读取某个文件的对应位置的数据时，首先根据打开的文件的 inode 找到 address_space 结构，address_space是建立内存和文件关联的桥梁，其中保存有该文件的 基数树，通过文件的偏移 在基数树中查找页缓存，如果缓存命中直接读取，否则分配一块缓存页并将磁盘中的对应数据拷贝到内存缓存页中。（最后害有一个双向链表来实现LRU？）

操作系统程序的内部结构

32位系统 一个程序的可寻址空间位 4G ， 其中0-3G是用户态空间，3-4G是内核空间。从低地址到高地址，依次为代码段，数据段，bss段，堆区，mmap映射区，栈区。

  • 代码段：存放的是机器代码 和 字符常量，只读，在可执行文件生成的时候以已经写入。
  • 数据段：存放的是初始化了的且初始值不为0的全局变量和局部静态变量。在可执行文件生成的时候已经写入。
  • bss段：存放的是初始值为0或者未初始化的全局变量或者静态变量，单独分出这个区域的目的是减少可执行文件的尺寸，在可执行文件中只记录该区域的大小。
  • 堆区：前三个大小都是固定的。后两个是在程序运行时新增的区域。堆区为程序员动态分配的空间，在运行中可以动态改变，由低地址向高地址生长。堆的效率比栈要低的多。
  • 栈区：用于存放函数调用时函数的返回值，返回地址等信息，该部分内存由操作系统管理，栈区是从高地址位向低地址位增长的，是一块连续的内存区域，并且每个栈的最大地址有限制，超出了会异常。

缺页中断

malloc mmap 函数分配空间只是分配的虚拟内存，只有当程序访问虚拟空间，并发现虚拟内存和物理内存没有建立映射关系时，就会出发缺页中断。在请求分页系统中，可以通过查询页表中的状态位来确定所要访问的页面是否存在于内存中。此时操作系统会根据页表中的外存地址在外存中找到所缺的一页，将其调入内存。

缺页本身是一种中断，与一般的中断一样，需要经过4个处理步骤：

  1. 保护CPU现场
  2. 分析中断原因
  3. 处理缺页中断
  4. 恢复CPU现场，继续执行

但是缺页中断所要访问的页面不在内存时，由硬件所产生的一种特殊的中断，因此与一般中断存在的区别是：

  1. 在指令执行期间产生和处理缺页中断信号
  2. 一条指令在执行期间，可能产生多次缺页中断
  3. 缺页中断返回是，执行产生中断的一条指令，而一般的中断返回是，执行下一条指令。

请你回答一下fork和vfork的区别

1
2
3
4
#include <sys/types.h>
#include <unistd.h>
pid_t fork(void);
pid_t vfork(void);
  1. fork的发展：但是在早期 Unix系统中，调用fork，fork创造的子进程是父进程的完整副本，复制了父亲进程的资源，包括内存的内容和task_struct内容。逐页的复制方式是十分耗时的。现代的Unix系统采用了写时复制的方法，而不是对父进程空间进程整体复制。
  2. 为何会有vfork： 由于早期 fork 全盘复制的弊端，常规用途中 往往直接在子进程中使用 exec 加载其他映像文件，并不需要全部复制父进程的东西。因此 出现了vfork 。
  3. vfork 作用： vfork( ) 避免了地址空间的按页复制。在这个过程中，父进程和子进程共享相同的地址空间和页表项。实际上vfork( )只完成了一件事：复制内部的内核数据结构。因此，子进程也就不能修改地址空间中的任何内存。而且子进程将先于父进程运行，只有在 子进程调用 exec 或者 _exit 时，才会唤醒父进程。
  4. 写时复制：写时复制是一种采取了惰性优化方法来避免复制时的系统开销。如果有多个进程要读取它们自己的那部门资源的副本，每个进程只要保存一个指向这个资源的指针就可以了。如果一个进程要修改自己的那份资源“副本”，那么就会复制那份资源，并把复制的那份提供给进程，这个进程就可以修改复制后的资源了，同时其他的进程仍然共享那份没有修改过的资源。
  5. 写时复制的具体实现：在使用虚拟内存的情况下，写时复制（Copy-On-Write）是以页为基础进行的。所以，只要进程不修改它全部的地址空间，那么就不必复制整个地址空间。如果有进程试图修改一个页，就会产生一个缺页中断。内核处理缺页中断的方式就是对该页进行一次透明复制。这时会清除页面的COW属性，表示着它不再被共享。

fork 与 vfork 区别：

  1. fork( )的子进程拷贝父进程的数据段和代码段；vfork( )的子进程与父进程共享数据段 直至子进程使用execve启动新的应用程序为止
  2. fork( )的父子进程的执行次序不确定；vfork( )保证子进程先运行，在调用exec或exit之前与父进程数据是共享的，在它调用exec或exit之后父进程才能被调度运行，如果在调用这两个函数之前子进程依赖于父进程的进一步动作，则会导致死锁。

请问如何修改文件最大句柄数

1
2
3
4
5
ulimit -n 2048   # 将最大文件句柄数修改为2048 但是新开一个 shell 会失效
ulimit -a        # 查询 Linux 的相关参数，其中open files为最大文件数
vi /etc/security/limits.conf  ## 要永久修改 最大文件数 在 conf 文件中添加  修改以后保存，注销当前用户，重新登录，修改后的参数就生效了
*　　soft　　nofile　　65536
*　　hard　　nofile　　65536

并发(concurrency)和并行(parallelism)

并发：宏观上两个程序好像在同时运行，但是某一时刻只有一个程序在运行，两个程序交替执行一个小时间片，并发能提高程序的效率。

并行：并行需要硬件支持，例如多核或者多机。两个程序可以在不同核中同时运行，也就是运行了两个指令，互不影响。

MySQL的端口号是多少，如何修改这个端口号

mysql 的默认端口是 3306，修改端口号 在 /etc/my.cnf 文件 中修改即可

1
2
3
## 登录 mysql 使用命令
show global variables like 'port'   ## 查看端口号  
vim my.cnf   ### 修改端口号

说一说操作系统中的页表寻址

页式内存管理，内存分成固定长度的一个个页片。操作系统为每一个进程维护了一个从虚拟地址到物理地址的映射关系的数据结构，叫页表，页表的内容就是该进程的虚拟地址到物理地址的一个映射。页表中的每一项都记录了这个页的基地址。通过页表，由逻辑地址的高位部分先找到逻辑地址对应的页基地址，再由页基地址偏移一定长度就得到最后的物理地址，偏移的长度由逻辑地址的低位部分决定。一般情况下，这个过程都可以由硬件完成，所以效率还是比较高的。页式内存管理的优点就是比较灵活，内存管理以较小的页为单位，方便内存换入换出和扩充地址空间。

早期的Linux系统使用 一级 页表，由于页表是连续的，即使一个进程可能只会使用到少部分的寻址空间，但是也需要将整个页表存储在连续的内存中，这是比较浪费内存的。因此 逐渐出现 多级页表的 结构，通过分散存储的思想，内存中往往只用存储一个一级页表和少量使用到的二级页表，其他不用的二级页表可以存储在外存中，使用时再调入。这样大大减小了存储页表需要的内存空间。寻址方式类似，首先通过CR3寄存器获得一级页表的地址，根据逻辑地址的高位，映射得到对应的二级页表的地址，然后再在二级页表中，根据逻辑地址的中间位映射，得到该逻辑地址对应的完整页的基地址，再加上逻辑地址的低位偏移得到真实的物理地址。

说一说有了进程，为什么还要有线程

进程可以使多个程序能并发执行，以提高资源的利用率和系统的吞吐量；但是其具有一些缺点。

  1. 进程中一旦有阻塞任务，整个进程都会被挂起，即使进程中有些工作不依赖于等待资源，但是仍然不会被执行。
  2. 进程的建立需要耗费更多资源。线程是一种非常"节俭"的多任务操作方式。在linux系统下，启动一个新的进程必须分配给它独立的地址空间，建立众多的数据表来维护它的代码段、堆栈段和数据段，这是一种"昂贵"的多任务工作方式。
  3. 进程间的通信复杂，因为不同进程的数据空间是独立的，要通信需要借助IPC，而线程之间共享资源，比较方便
  4. 进程切换开销大，运行于一个进程中的多个线程，它们之间使用相同的地址空间，而且线程间彼此切换所需时间也远远小于进程间切换所需要的时间。

另外：

  1. 使多CPU系统更加有效。操作系统会保证当线程数不大于CPU数目时，不同的线程运行于不同的CPU上
  2. 改善程序结构。一个既长又复杂的进程可以考虑分为多个线程，成为几个独立或半独立的运行部分，这样的程序才会利于理解和修改。

单核机器上写多线程程序，是否需要考虑加锁，为什么？

需要，如果有一个线程正在对共享数据修改，还没修改完 突然被系统挂起，调入另一个线程，此时该线程再对共享数据读，读出的就是脏数据。

线程需要保存哪些上下文，SP、PC、EAX这些寄存器是干嘛用的

保存 当前线程id和状态，寄存器状态，堆栈信息等。其中寄存器信息主要有 SP指针 存放的是堆栈地址，PC指针程序计数器指向下一条将要执行的指令，EAX累加寄存器，是加法乘法的缺省寄存器，用来存储cpu计算产生的中间结果，如果没有累加器这样的寄存器，那么每次计算加法乘法移位等后产生的中间结果都要写会内存，也许马上又要读回来，速度慢。

线程间同步的方式

（如果问线程通信的方式 就 加上 临界区，通过多线程的串行化来访问公共资源或一段代码，速度快，适合控制数据访问）

  • 用户模式：原子操作，临界区
  • 内核模式：事件，信号量，互斥量

信号量。通过PV操作来增减信号值，当信号值为0时，线程休眠。增减的操作是原子的。

1
2
3
sem_wait(sem_t* sem);   // 信号值减1，如果信号值是0 则休眠  
sem_post(sem_t* sem);   // 信号值加1  当值大于0后，其他因为没有信号值而休眠的线程将被唤醒
sem_init();   // 初始化信号量，可以设置初值，也可以选择该信号是用于局部线程还是进程间共享

互斥量/锁。主要用于线程互斥，不能保证按序访问，可以保证线程对临界区的互斥访问，也可以和条件锁一起实现线程同步。当进入临界区的时候需要获得互斥锁并且加锁，当离开临界区的时候，需要对解锁，以唤醒其他等待的线程。

1
2
3
4
pthread_mutex_init();     // 初始化互斥锁
pthread_mutex_lock();     // 以原子的方式给一个互斥锁加锁
pthread_mutex_unlock();   // 以原子的方式给互斥锁解锁
pthread_mutex_destroy();  // 销毁互斥锁

条件变量。和互斥锁不同，条件变量是当达到某个条件时，同时唤醒在等待该变量的线程，从而实现线程同步。但是为了防止出现唤醒信号丢失的情况，通常要和互斥锁配合使用，在测试条件变量的时候先加锁，防止在测试且还未睡眠时，另一个线程发出条件信号，而被当前线程错过的问题。

1
2
3
4
pthread_cond_init();    // 初始化条件变量
pthread_cond_wait();    // 等待目标条件变量，如果没有信号就休眠。在调用该函数测试条件时需要先使用互斥锁加锁确保原子性。在该函数中进入wait状态前会先解锁再休眠。因此该函数入口参数还有个互斥锁变量。在被条件唤醒后，函数内部会再加上互斥锁。
pthread_cond_signal();  // 唤醒一个等待目标条件变量的线程。哪个线程被唤醒取决于调度策略和优先级。
pthread_cond_destroy(); // 销毁条件变量

游戏服务器应该为每个用户开辟一个线程还是一个进程，为什么

游戏服务器应该为每个用户开辟一个进程。因为同一进程间的线程会相互影响，一个线程死掉会影响其他线程，从而导致进程崩溃。因此为了保证不同用户之间不会相互影响，应该为每个用户开辟一个进程

缺页置换算法

进程运行过程中，如果发生缺页中断，而此时内存中有没有空闲的物理块是，为了能够把所缺的页面装入内存，系统必须从内存中选择一页调出到磁盘的对换区。但此时应该把哪个页面换出，则需要根据一定的页面置换算法（Page Replacement Algorithm)来确定

先进先出(FIFO)算法：置换最先调入内存的页面，即置换在内存中驻留时间最久的页面。按照进入内存的先后次序排列成队列，从队尾进入，从队首删除。

最近最少使用（LRU）算法: 置换最近一段时间以来最长时间未访问过的页面。根据程序局部性原理，刚被访问的页面，可能马上又要被访问；而较长时间内没有被访问的页面，可能最近不会被访问。

当前最常采用的就是LRU算法。

死锁发生的条件以及如何解决死锁

  1. 互斥条件：进程对所分配到的资源不允许其他进程访问，若其他进程访问该资源，只能等待，直至占有该资源的进程使用完成后释放该资源；
  2. 请求和保持条件：进程获得一定的资源后，又对其他资源发出请求，但是该资源可能被其他进程占有，此时请求阻塞，但该进程不会释放自己已经占有的资源
  3. 不可剥夺条件：进程已获得的资源，在未完成使用之前，不可被剥夺，只能在使用后自己释放
  4. 环路等待条件：进程发生死锁后，必然存在一个进程-资源之间的环形链

解决死锁的方法即破坏上述四个条件之一，主要方法如下（死锁预防）：

  • 静态分配资源，一次性把要用的资源都申请到 破坏请求保持条件
  • 可剥夺资源：即当进程新的资源未得到满足时，释放已占有的资源，等到进程可以同时获取两个资源后再启动，从而破坏不可剥夺的条件
  • 资源有序分配法：系统给每类资源赋予一个序号，每个进程按编号递增的请求资源，释放则相反，从而破坏环路等待的条件。例如 1，2，3资源，如果进程A 按照 1 2 3 顺序申请，而 B 按照 3 2 1 顺序申请，那必然环路，如果都按照 1 2 3 顺序申请就没事

运行时死锁状态判别

银行家算法

  1. 需要预先知道系统当前剩余的资源数量，以及各个进程已经占有的资源数量和请求的资源数量。
  2. 遍历每个进程判断 他当前球请求的资源数量是否小于系统剩余资源数量，如果是标记当前进程；然后将系统剩余资源数量加上当前进程占有的资源数量，这代表该进程释放资源后系统总的剩余资源数量。
  3. 再按照之前的步骤去遍历标记剩下的进程。最终未被标记的进程都是死锁进程。

如果有一个状态是不安全的 就应该拒绝进入这个状态

通过宏定义 重写加锁去锁算法 主要就是在上锁之前打印请求的资源号和请求的进程 从而得到一个持有的图 然后拓扑排序判断是否有环

请问虚拟内存和物理内存怎么对应

操作系统中的结构体对齐，字节对齐

需要字节对齐的原因：

  1. 平台原因：不是所有硬件平台都能随机访问任意地址的数据，可能只能从特定地址开始一次读取指定大小的数据，否则会抛出硬件异常。因此通过指定对齐方 式可以使代码方便兼容多种平台。
  2. 性能原因：数据结构应该经可能在自然边界上对齐。原因在于，为了访问非对其的内存，可能需要做两次内存访问，而对齐的内存访问只需要一次。例如如果内存只能从偶地址开始读，那么直接访问奇地址开始的两字节变量需要先访问两次偶地址的地址，然后组合得到实际的数据值。

字节对齐的规则：

  1. 结构体字节对齐规则：结构中，第一个变量的起始地址为0，其他变量的起始地址要是 变量本身大小 和 unpack指定的对齐数中 较小的整数倍。如果不是，就补齐。
  2. 结构体本身对齐规则：结构本身所占的 大小，要是 成员中最大变量的字节数 和 unpack指定对齐参数中取较小的 数的整数倍。
  3. 结构体中如果还有结构体：那么内部的结构体要对齐在它本身 元素中最大变量 的 地址上。

如何自定义对齐方式：

1
2
3
4
5
6
7
8
#program pack(2)   // n=1,2,4,8,16来改变这一系数，其中的n就是指定的“对齐系数”。
struct AA {
int a;       //长度4 > 2 按2对齐；偏移量为0；存放位置区间[0,3]
char b;      //长度1 < 2 按1对齐；偏移量为4；存放位置区间[4]
short c;     //长度2 = 2 按2对齐；偏移量要提升到2的倍数6；存放位置区间[6,7]
char d;      //长度1 < 2 按1对齐；偏移量为7；存放位置区间[8]；最后 结构体要是2的倍数 共10个字节
};
#pragma pack()     //结束对齐

进程间通信的方式

进程通信的方式有 管道，消息队列，套接字，共享内存，信号量

  • 管道：管道有 无名管道和有名管道。
    1. 他们都只支持半双工通信，且收发数据双方得同时存在管道的两端；
    2. 管道实际是将信息存储在内存中，消息取出后就不再存在于管道中了；
    3. 管道传输的是数据流，收发双发需要自定义数据格式；
    4. 其中无名管道只能用于有亲缘关系的进程，而有名管道没有这个限制
  • 消息队列：消息队列存在于内核中，一个消息队列由一个标识符（即队列ID）来标记，数据读取后仍然存在；且消息具有类型和优先级，因此读取方可以按照数据类型读取消息，而不必按照顺序读出；消息队列独立于发送与接收进程，进程终止时，消息队列及其内容并不会被删除。
  • 共享内存：它使得多个进程可以访问同一块物理内存，但是需要用户使用信号量等辅助完成同步操作。这是最快的IPC，因为进程可以直接从物理内存读取。
  • 套接字：用于不同主机中的进程通信。

虚拟内存置换的方式

比较常见的置换方法：FIFO 第二次机会算法 LRU LRU-K LFU NRU

  1. FIFO： 用一个队列实现，先进先出。完全没有考虑页面使用的冷热信息。
  2. 第二次机会算法：弥补了FIFO的缺点，当再次访问队列中已经存在的页时，将它标记为1，当需要置换页面是，从队头开始，如果其标记为1，那么将它置0并放在队尾，依次循环直到找到标记为0的页面换出。实现的时候可以使用一个环形数组实现，每次只需要移动指针即可完成对头到队尾的转变。
    • 当队列中所有的页面都标记为1时，退化成FIFO
  3. LRU：使用一个链表维护，当访问某个页面时，将该页面放在队头，当需要换出时，将队尾的页面换出。
    • 由于需要链表，速度慢；
    • 缓存污染：出现偶然数据时，会让内存存放大量冷数据；
    • 缓存颠簸：当出现交替的数据时，命中率很低，每次都要置换。例如 0 1 2 3 0 1 2 3 … 这种数据 缓存大小只有3
  4. LRU-K：为了解决LRU中缓存污染的问题。维护 一个 FIFO 加 一个 LRU，基本原理是只有当某个页面访问次数超过K次之后才使用LRU的规则置换，否则对于访问频率较少的页面直接使用FIFO的策略淘汰。具体思路是，当新加入一个页面时，先将它放入FIFO中，当访问某个页面时需要记录FIFO中每个页面的被访问次数，如果大于K，就将它从FIFO中删除并放入LRU的链表中，如果LRU缓存满了就按照LRU的规则删除链表尾部的元素。当需要删除页面时，将FIFO中先进入的页面删除。
    • 为了解决 LRU 的缓存污染问题
  5. 2Q算法就是 LRU-2
    • 当访问的数据为 ABABABA时退化为 FIFO 用不到LRU

epoll原理