1. 进程与线程的区别和联系

• 进程是具有一定独立功能的程序关于某个数据集合上的一次运行活动，进程是系统进行资源分配和调度的一个独立单位。
• 线程是进程的一个实体，是CPU调度和分派的基本单位，它是比进程更小的能独立运行的基本单位。

进程和线程的关系

（1）一个线程只能属于一个进程，而一个进程可以有多个线程，但至少有一个线程。线程是操作系统可识别的最小执行和调度单位。

（2）资源分配给进程，同一进程的所有线程共享该进程的所有资源。 同一进程中的多个线程共享代码段(代码和常量)，数据段(全局变量和静态变量)，扩展段(堆存储)。但是每个线程拥有自己的栈段，栈段又叫运行时段，用来存放所有局部变量和临时变量。

（3）处理机分给线程，即真正在处理机上运行的是线程。

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

进程与线程的区别？

（1）进程有自己的独立地址空间，线程没有

（2）进程是资源分配的最小单位，线程是CPU调度的最小单位

（3）进程和线程通信方式不同(线程之间的通信比较方便。同一进程下的线程共享数据（比如全局变量，静态变量），通过这些数据来通信不仅快捷而且方便，当然如何处理好这些访问的同步与互斥正是编写多线程程序的难点。而进程之间的通信只能通过进程通信的方式进行。)

（4）进程上下文切换开销大，线程开销小

（5）一个进程挂掉了不会影响其他进程，而线程挂掉了会影响其他线程

（6）对进程进程操作一般开销都比较大，对线程开销就小了

2. 一个进程可以创建多少线程，和什么有关

(1)对于Linux来说：
linux创建一个线程会占用多少内存，这取决于分配给线程的调用栈大小，可以用ulimit -s命令来查看大小（一般常见的有10M或者是8M）,一个进程的虚拟内存是4G，在Linux32位平台下，内核分走了1G，留给用户用的只有3G，于是我们可以想到，创建一个线程占有了10M内存，总共有3G内存可以使用。于是可想而知，最多可以创建差不多300个左右的线程。

进程最多可以创建的线程数是根据：

• 分配给调用栈的大小
• 操作系统（32位和64位不同）

(2)对于Windows来说：

• 默认情况下，一个线程的栈要预留1M的内存空间, 而一个进程中可用的内存空间只有2G，所以理论上一个进程中最多可以开2048个线程, 但是内存当然不可能完全拿来作线程的栈，所以实际数目要比这个值要小。
• 即使物理内存再大，一个进程中可以起的线程总要受到2GB这个内存空间的限制。 比方说你的机器装了64GB物理内存，但每个进程的内存空间还是4GB，其中用户态可用的还是2GB。

3. 一个程序从开始运行到结束的完整过程（四个过程）

（1）一个程序开始运行，首先进行创建进程，操作系统首先为该程序申请一个空白的PCB，然后向这个PCB中填入一些控制和管理进程的相关信息。然后分配所需要的资源，跳入就绪状态。

（2）程序进入就绪状态，等待处理机时间片的到来，进程被调度，获得对应的时间片，就由就绪状态跳转到运行状态。注意，时间片完了之后，进程会自动从运行状态跳到就绪状态，等待下一个时间片的到来。

（3）如果程序运行过程中请求某一个资源，例如IO资源，这个时候IO资源正在忙碌，此时程序主动进入阻塞状态，等待IO资源的空闲。

（4）当IO资源空闲，会主动由另外一个进程唤醒正在阻塞的进程，这个时候进程转为就绪状态，等待时间片的到来。

（5）运行完成之后，进行结束状态，操作系统回收一些资源的工作。

4. 进程通信方法（Linux和windows下），线程通信方法（Linux和windows下）

（1）linux下进程的通信方法：1.管道 2.信号量 3.共享内存 4.消息队列 5.套接字

• 管道：

  管道是单向的、先进先出的、无结构的、固定大小的字节流，它把一个进程的标准输出和另一个进程的标准输入连接在一起。写进程在管道的尾端写入数据，读进程在管道的道端读出数据。数据读出后将从管道中移走，其它读进程都不能再读到这些数据。管道提供了简单的流控制机制。进程试图读空管道时，在有数据写入管道前，进程将一直阻塞。同样地，管道已经满时，进程再试图写管道，在其它进程从管道中移走数据之前，写进程将一直阻塞。

  注1：无名管道只能实现父子或者兄弟进程之间的通信，有名管道（FIFO）可以实现互不相关的两个进程之间的通信。

  注2：用FIFO让一个服务器和多个客户端进行交流时候，每个客户在向服务器发送信息前建立自己的读管道，或者让服务器在得到数据后再建立管道。使用客户的进程号（pid）作为管道名是一种常用的方法。客户可以先把自己的进程号告诉服务器，然后再到那个以自己进程号命名的管道中读取回复。

• 信号量：

  信号量是一个计数器，可以用来控制多个进程对共享资源的访问。它常作为一种锁机制，防止某进程正在访问共享资源时，其它进程也访问该资源。因此，主要作为进程间以及同一进程内不同线程之间的同步手段。

• 共享内存：

  共享内存允许两个或多个进程访问同一个逻辑内存。这一段内存可以被两个或两个以上的进程映射至自身的地址空间中，一个进程写入共享内存的信息，可以被其他使用这个共享内存的进程，通过一个简单的内存读取读出，从而实现了进程间的通信。如果某个进程向共享内存写入数据，所做的改动将立即影响到可以访问同一段共享内存的任何其他进程。共享内存是最快的IPC方式，它是针对其它进程间通信方式运行效率低而专门设计的。它往往与其它通信机制（如信号量）配合使用，来实现进程间的同步和通信。

• 消息队列：

  是一个在系统内核中用来保存消 息的队列，它在系统内核中是以消息链表的形式出现的。消息队列克服了信号传递信息少、管道只能承载无格式字节流以及缓冲区大小受限等缺点。

• 套接字：

  套接字也是一种进程间通信机制，与其它通信机制不同的是，它可用于不同机器间的进程通信。

（2）windows下进程通信的方法：1.文件映射 2. 共享内存（是文件映射的一种特殊情况）；3.邮件槽（mailslot）（点对点消息队列）; 4.匿名管道；5；命名管道； 6.socket；

• 文件映射

  文件映射(Memory-Mapped Files)能使进程把文件内容当作进程地址区间一块内存那样来对待。因此，进程不必使用文件I/O操作，只需简单的指针操作就可读取和修改文件的内容。

  Win32 API允许多个进程访问同一文件映射对象，各个进程在它自己的地址空间里接收内存的指针。通过使用这些指针，不同进程就可以读或修改文件的内容，实现了对文件中数据的共享。

• 共享内存

  Win32 API中共享内存(Shared Memory)实际就是文件映射的一种特殊情况。进程在创建文件映射对象时用0xFFFFFFFF来代替文件句柄(HANDLE)，就表示了对应的文件映 射对象是从操作系统页面文件访问内存，其它进程打开该文件映射对象就可以访问该内存块。由于共享内存是用文件映射实现的，所以它也有较好的安全性，也只能 运行于同一计算机上的进程之间。

• 匿名管道

  管道(Pipe)是一种具有两个端点的通信通道：有一端句柄的进程可以和有另一端句柄的进程通信。管道可以是单向－一端是只读的，另一端点是只写的；也可以是双向的一管道的两端点既可读也可写。

• 命名管道

  命 名管道(Named Pipe)是服务器进程和一个或多个客户进程之间通信的单向或双向管道。不同于匿名管道的是命名管道可以在不相关的进程之间和不同计算机之间使用，服务器 建立命名管道时给它指定一个名字，任何进程都可以通过该名字打开管道的另一端，根据给定的权限和服务器进程通信。

  命名管道提供了相对简单的编程接口，使通过网络传输数据并不比同一计算机上两进程之间通信更困难，不过如果要同时和多个进程通信它就力不从心了。

• 邮件槽

  邮件槽(Mailslots)提供进程间单向通信能力，任何进程都能建立邮件槽成为邮件槽服务器。其它进程，称为邮件槽客户，可以通过邮件槽的名字给邮件槽服务器进程发送消息。进来的消 息一直放在邮件槽中，直到服务器进程读取它为止。一个进程既可以是邮件槽服务器也可以是邮件槽客户，因此可建立多个邮件槽实现进程间的双向通信。

  邮 件槽与命名管道相似，不过它传输数据是通过不可靠的数据报(如TCP/IP协议中的UDP包)完成的，一旦网络发生错误则无法保证消息正确地接收，而命名 管道传输数据则是建立在可靠连接基础上的。不过邮件槽有简化的编程接口和给指定网络区域内的所有计算机广播消息的能力，所以邮件槽不失为应用程序发送和接 收消息的另一种选择。

• Sockets

  Windows Sockets规范是以U.C.Berkeley大学BSD UNIX中流行的Socket接口为范例定义的一套Windows下的网络编程接口。除了Berkeley Socket原有的库函数以外，还扩展了一组针对Windows的函数，使程序员可以充分利用Windows的消息机制进行编程。

  ——linux下线程通信：线程之间是整个地址空间的资源都是共享的，所以只能做好同步互斥即可，在线程中同步互斥用到的工具有：锁机制，信号机制等

  ——windows线程通信：1.全局变量，2，message消息队列机制

  http://blog.csdn.net/richerg85/article/details/7655840

5.文件读写使用的系统调用

文件读写会涉及到的系统调用：

open：打开某个文件，并配置响应的权限

close：关闭文件描述符

read：读取函数，设置缓存区，及缓存区的大小

write：写操作函数，指定写入数据的大小

lseek：指定文件偏移量函数，文件偏移量指的是当前文件操作位置相对于文件开始位置的偏移。

fstat：获取文件状态

mmap：

• 建立内存映射函数，mmap()函数将普通文件映射到内存中，普通文件被映射到进程地址空间后，进程可以像访问普通内存一样对文件进行访问，不必再调用read()，write（）等操作。mmap()系统调用使得进程之间通过映射同一个普通文件实现共享内存。
• mmap()映射后，让用户程序直接访问设备内存，相比较在用户控件和内核空间互相拷贝数据，效率更高。在要求高性能的应用中比较常用。mmap映射内存必须是页面大小的整数倍，面向流的设备不能进行mmap，mmap的实现和硬件有关。

**fcntl：**文件属性的调用

**ioctl: ioctl()**函数通过对文件描述符的发送命令来控制设备。

（1）读文件

• 进程调用库函数向内核发起读文件请求；

• 内核通过检查进程的文件描述符定位到虚拟文件系统的已打开文件列表表项；

• 调用该文件可用的系统调用函数read()

• read()函数通过文件表项链接到目录项模块，根据传入的文件路径，在目录项模块中检索，找到该文件的inode；

• 在inode中，通过文件内容偏移量计算出要读取的页；

• 通过inode找到文件对应的address_space；

• 在address_space中访问该文件的页缓存树，查找对应的页缓存结点：

  1）如果页缓存命中，那么直接返回文件内容；

  2）如果页缓存缺失，那么产生一个页缺失异常，创建一个页缓存页，同时通过inode找到文件该页的磁盘地址，读取相应的页填充该缓存页；重新进行第6步查找页缓存；

• 文件内容读取成功。

（2）写文件

• 前5步和读文件一致，在address_space中查询对应页的页缓存是否存在：

• 如果页缓存命中，直接把文件内容修改更新在页缓存的页中。写文件就结束了。这时候文件修改位于页缓存，并没有写回到磁盘文件中去。

• 如果页缓存缺失，那么产生一个页缺失异常，创建一个页缓存页，同时通过inode找到文件该页的磁盘地址，读取相应的页填充该缓存页。此时缓存页命中，进行第6步。

• 一个页缓存中的页如果被修改，那么会被标记成脏页。脏页需要写回到磁盘中的文件块。有两种方式可以把脏页写回磁盘：
  1）手动调用sync()或者fsync()系统调用把脏页写回

  2）pdflush进程会定时把脏页写回到磁盘

同时注意，脏页不能被置换出内存，如果脏页正在被写回，那么会被设置写回标记，这时候该页就被上锁，其他写请求被阻塞直到锁释放。

参考：
https://www.cnblogs.com/huxiao-tee/p/4657851.html

6. 怎么回收线程

• 线程退出有多种方式，如return，pthread_exit,pthread_cancel等；
• 线程分为可结合的（joinable）和分离的（detached）两种，如果没有在创建线程时设置线程的属性为PTHREAD_CREATE_DETACHED，则线程默认是可结合的。
• 可结合的线程在线程退出后不会立即释放资源，必须要调用pthread_join来显式的结束线程。
• 分离的线程在线程退出时系统会自动回收资源。

7. 守护进程、僵尸进程和孤儿进程

• 守护进程：守护进程就是在后台运行，不与任何终端关联的进程，通常情况下守护进程在系统启动时就在运行，它们以root用户或其他特殊用户运行，并能处理一些系统级的任务。
• 孤儿进程：父进程退出，而它的一个或多个子进程还在运行，那么那些子进程将成为孤儿进程。孤儿进程将被init进程（进程号为1）所收养，并由init进程对它们完成状态收集工作。
• 僵尸进程：一个进程使用fork创建子进程，如果子进程退出，而父进程并没有调用wait或waitpid获取子进程的状态信息，那么子进程的进程描述符仍然保存在系统中，这种进程称之为僵尸进程。

8. 处理僵尸进程的两种经典方法

方法一：父进程回收法
wait函数将使其调用者阻塞，直到其某个子进程终止。故父进程可调用wait函数回收其僵尸子进程。除此之外，waitpid函数提供更为详尽的功能( 增加了非阻塞功能以及指定等待功能 )，请读者自行查阅相关资料。
代码实现

 1 #include <unistd.h>2 #include <sys/wait.h>3 #include <stdio.h>4 #include <stdlib.h>5 6 int main()7 {8     int pid;9     int *status;
10 
11     printf("%s\n", "启动父进程");
12 
13     if ((pid = fork()) < 0) {
14         printf("%s\n", "创建子进程失败");
15         exit(1);
16     }
17     else 
18         if (pid ==0) {
19             printf("%s\n", "进入子进程");
20             sleep(4);
21             // 终止子进程
22             exit(0);
23         }
24     else {
25         // 进入父进程
26         // 回收僵尸子子进程
27         wait(status);
28         printf("%s\n", "回收完毕");
29     }
30 
31     exit(0);
32 }

结果分析
第三行的“回收完毕”是在程序执行四秒后才显示的。这说明尽管我将子进程阻塞了4秒，父进程并不会先于子进程终止。因为它调用了wait函数，故需要等待一个子进程结束并将其回收，否则就一直阻塞在那里。

方法二：init进程回收法

• 上面的这种解决方案需要父进程去等待子进程，但在很多情况下，这并不合适，因为父进程也许还有其他任务要做，不能阻塞在这里。在讲述下面这种不用父进程等待就能完成回收子进程的方法之前，先请明白以下两个概念：
  1）如果父进程先于子进程结束，那么子进程的父进程自动改为 init 进程。

  2）如果 init 的子进程结束，则 init 进程会自动回收其子进程的资源而不是让它变成僵尸进程。

代码实现

 1 #include "apue.h"2 #include <sys/wait.h>3 4 int5 main(void)6 {7     pid_t    pid;8 9     if ((pid = fork()) < 0) {    // 创建第一个子进程
10         err_sys("fork error");
11     } else if (pid == 0) {    // 进入第一个子进程
12         if ((pid = fork()) < 0)    // 创建第二个子进程
13             err_sys("fork error");
14         else if (pid > 0) // 进入第一个子进程 
15             exit(0);    // 终止第一个子进程    
16         // 第二个子进程在睡眠2S后才执行，这样一般情况下第一个子进程会先终止。
17         sleep(2);
18         // 这时，第一个子进程肯定终止了，那么它的父进程就自动变成了init。
19         printf("second child, parent pid = %d\n", getppid());
20         exit(0);
21     }
22 
23     // 父进程等待并回收第一个子进程
24     if (waitpid(pid, NULL, 0) != pid)    
25         err_sys("waitpid error");
26 
27     // 父进程执行到这里以后，可以退出，也可以执行其他的任务。
28     // 对于刚才那第二个子进程，它继承了父进程的资源，同时它终止后也会被init进程回收，
29     // 不会成为僵尸进程。
30     exit(0);
31 }

说明

• fork创建子进程以后，子进程拥有的是父进程的一个资源副本，而不是和它共享资源。
• 子进程终止后变成僵尸进程并不是系统BUG，而是因为子进程终止后，其一些信息操作系统或者用户以后还可能会用到。

转载于:https://www.cnblogs.com/muchen/p/6354573.html

9. 进程终止的几种方式

1）、main函数的自然返回，return
2）、调用exit函数
3）、调用_exit函数
4）、调用abort函数
5）、接受能导致进程终止的信号:

其中1、2、3为正常终止，4、5异常终止

• exit和_exit函数都是用来终止进程的。当程序执行到exit和_exit时，进程会无条件的停止剩下的所有操作，清除包括PCB在内的各种数据结构，并终止本程序的运行。
• exit函数和_exit函数的最大区别在于exit函数在退出之前会检查文件的打开情况，把文件缓冲区中的内容写回文件，也就是清理I/O缓冲。

exit可输出缓冲区数据

#include <stdio.h>
#include <stdlib.h>int main()
{printf("Using exit\n");printf("This is the content in buffer");exit(0);
}

//运行结果：
Using exit

_exit无法输出缓冲区数据

#include <stdio.h>
#include <stdlib.h>
#include <unistd.h>
int main()
{printf("Using exit\n");printf("This is the content in buffer");_exit(0);
}

//运行结果：
Using exit

abort()是使异常程序终止，同时发送SIGABRT信号给调用进程。
使用实例：

#include <stdio.h>
#include <stdlib.h>
int main()
{FILE *stream;if((stream = fopen("nofilehere", "r")) == NULL){perror("Can not open");abort();}else{fclose(stream);}return 0;
}

运行结果：

Can not open: No such file or directory
Aborted (core dumped)

10. linux中异常和中断的区别

1）.中断

• 当我们在敲击键盘的同时就会产生中断，当硬盘读写完数据之后也会产生中断，所以，我们需要知道，中断是由硬件设备产生的，而它们从物理上说就是电信号，之后，它们通过中断控制器发送给CPU，接着CPU判断收到的中断来自于哪个硬件设备（这定义在内核中），最后，由CPU发送给内核，有内核处理中断。下面这张图显示了中断处理的流程：
  
  2）.异常

• 我们在学习《计算机组成原理》的时候会知道两个概念，CPU处理程序的时候一旦程序不在内存中，会产生缺页异常；当运行除法程序时，当除数为0时，又会产生除0异常。所以，大家也需要记住的是，异常是由CPU产生的，同时，它会发送给内核，要求内核处理这些异常，下面这张图显示了异常处理的流程：
  
  3.异同

• 相同点：

  1> 最后都是由CPU发送给内核，由内核去处理

  2> 处理程序的流程设计上是相似的

• 不同点：

  1> 产生源不相同，异常是由CPU产生的，而中断是由硬件设备产生的

  2> 内核需要根据是异常还是中断调用不同的处理程序

  3> 中断不是时钟同步的，这意味着中断可能随时到来；异常由于是CPU产生的，所以，它是时钟同步的

  4> 当处理中断时，处于中断上下文中；处理异常时，处于进程上下文中

  转自 https://blog.csdn.net/u011068464/article/details/10284741 Linux内核–异常和中断的区别

11. 一般情况下在Linux/windows平台下栈空间的大小

1.Windows下程序栈空间的大小，VC++ 6.0 默认的栈空间是1M。

VC6.0中修改堆栈大小的方法：

1). 选择 "Project->Setting".
2). 选择 "Link".
选择 "Category"中的 "Output".
在 "Stack allocations"中的"Reserve:"中输栈的大小

在VS中设置堆栈大小的方法为：

1). 选择 "项目->属性".
2). 选择 "链接器".选择 "系统".在 "堆栈保留大小"中输栈的大小

2 .Linux下程序栈空间的大小

linux下非编译器决定栈大小，而是由操作系统环境决定；
而在Windows平台下栈的大小是被记录在可执行文件中的（由编译器来设置)，
即：windows下可以由编译器决定栈大小，而在Linux下是由系统环境变量来控制栈的大小的。在Linux下通过如下命令可查看和设置栈的大小：命令： ulimit -a            # 显示当前栈的大小 （ulimit为系统命令，非编译器命令）       命令： ulimit -s 32768      # 设置当前栈的大小为32M bytes

12. 五种IO模型

• 阻塞IO
• 非阻塞IO
• IO多路复用
• 信号驱动IO
• 异步 IO

（1）阻塞IO

• 通俗：阻塞IO就是当应用B发起读取数据申请时，在内核数据没有准备好之前，应用B会一直处于等待数据状态，直到内核把数据准备好了交给应用B才结束。
• 术语：在应用调用recvfrom读取数据时，其系统调用知道数据包到达切被复制到应用缓冲区中或者发送错误时才返回，在此期间一直会等待，进程从调用到返回这段时间内都是被阻塞的成为阻塞IO；
  
  流程：
  1）、应用进程向内核发起recfrom读取数据。
  2）、准备数据报（应用进程阻塞）。
  3）、将数据从内核负责到应用空间。
  4）、复制完成后，返回成功提示。
  

（2）非阻塞IO**

• 俗语：非阻塞IO就是当应用B发起读取数据申请时，如果内核数据没有准备好会即刻告诉应用B，不会让B在这里等待。

• 术语：非阻塞IO是在应用调用recvfrom读取数据时，如果该缓冲区没有数据的话，就会直接返回一个EWOULDBLOCK错误，不会让应用一直等待中。在没有数据的时候会即刻返回错误标识，那也意味着如果应用要读取数据就需要不断的调用recvfrom请求，直到读取到它数据要的数据为止。

  流程：
  1）、应用进程向内核发起recvfrom读取数据。
  2）、没有数据报准备好，即刻返回EWOULDBLOCK错误码。
  3）、应用进程向内核发起recvfrom读取数据。
  4）、已有数据包准备好就进行一下 步骤，否则还是返回错误码。
  5）、将数据从内核拷贝到用户空间。
  6）、完成后，返回成功提示。
  

（3）IO复用模型

• 在并发的环境下，可能会N个人向应用B发送消息，这种情况下我们的应用就必须创建多个线程去读取数据，每个线程都会自己调用recvfrom去读取数据。那么此时情况可能如下图：
  

产生的问题：

• 并发情况下服务器很可能一瞬间会收到几十上百万的请求，这种情况下应用B就需要创建几十上百万的线程去读取数据，同时又因为应用线程是不知道什么时候会有数据读取，为了保证消息能及时读取到，那么这些线程自己必须不断的向内核发送recvfrom请求来读取数据；
• 那么问题来了，这么多的线程不断调用recvfrom请求数据，先不说服务器能不能扛得住这么多线程，就算扛得住那么很明显这种方式是不是太浪费资源了，线程是我们操作系统的宝贵资源，大量的线程用来去读取数据了，那么就意味着能做其它事情的线程就会少。

解决方法：

• 提供一种方式，可以由一个线程监控多个网络请求（我们后面将称为fd文件描述符，linux系统把所有网络请求以一个fd来标识），这样就可以只需要一个或几个线程就可以完成数据状态询问的操作，当有数据准备就绪之后再分配对应的线程去读取数据，这么做就可以节省出大量的线程资源出来，这个就是IO复用模型的思路。
  
  正如上图，IO复用模型的思路就是系统提供了一种函数可以同时监控多个fd的操作，这个函数就是我们常说到的select、poll、epoll函数，有了这个函数后，应用线程通过调用select函数就可以同时监控多个fd，select函数监控的fd中只要有任何一个数据状态准备就绪了，select函数就会返回可读状态，这时询问线程再去通知处理数据的线程，对应线程此时再发起recvfrom请求去读取数据。

术语描述：进程通过将一个或多个fd传递给select，阻塞在select操作上，select帮我们侦测多个fd是否准备就绪，当有fd准备就绪时，select返回数据可读状态，应用程序再调用recvfrom读取数据。

总结：复用IO的基本思路就是通过slect或poll、epoll 来监控多fd ，来达到不必为每个fd创建一个对应的监控线程，从而减少线程资源创建的目的。

**（4）信号驱动IO **

问题：

• 采用轮询的方式来监控多个fd的，通过不断的轮询fd的可读状态来知道是否就可读的数据，而无脑的轮询就显得有点暴力，因为大部分情况下的轮询都是无效的，所以有人就想，能不能不要我总是去问你是否数据准备就绪，能不能我发出请求后等你数据准备好了就通知我，所以就衍生了信号驱动IO模型。

解决方法：

• 信号驱动IO是在调用sigaction时候建立一个SIGIO的信号联系，当内核数据准备好之后再通过SIGIO信号通知线程数据准备好后的可读状态，当线程收到可读状态的信号后，此时再向内核发起recvfrom读取数据的请求，因为信号驱动IO的模型下应用线程在发出信号监控后即可返回，不会阻塞，所以这样的方式下，一个应用线程也可以同时监控多个fd。
  
  术语描述：首先开启套接口信号驱动IO功能，并通过系统调用sigaction执行一个信号处理函数，此时请求即刻返回，当数据准备就绪时，就生成对应进程的SIGIO信号，通过信号回调通知映应用线程调用recvfrom来读取数据。
  
  总结： IO复用模型里面的select虽然可以监控多个fd了，但select其实现的本质上还是通过不断的轮询fd来监控数据状态， 因为大部分轮询请求其实都是无效的，所以信号驱动IO意在通过这种建立信号关联的方式，实现了发出请求后只需要等待数据就绪的通知即可，这样就可以避免大量无效的数据状态轮询操作。

（5）异步 IO

• 问题：为什么我们明明是想读取数据，什么非得要先发起一个select询问数据状态的请求，然后再发起真正的读取数据请求,能不能有一种一劳永逸的方式，我只要发送一个请求我告诉内核我要读取数据，然后我就什么都不管了，然后内核去帮我去完成剩下的所有事情？
• 解决方法：只需要向内核发送一个read 请求,告诉内核它要读取数据后即刻返回；内核收到请求后会建立一个信号联系，当数据准备就绪，内核会主动把数据从内核复制到用户空间，等所有操作都完成之后，内核会发起一个通知告诉应用，我们称这种一劳永逸的模式为异步IO模型。
  
  术语描述： 应用告知内核启动某个操作，并让内核在整个操作完成之后，通知应用，这种模型与信号驱动模型的主要区别在于，信号驱动IO只是由内核通知我们合适可以开始下一个IO操作，而异步IO模型是由内核通知我们操作什么时候完成。
  

总结：

• 异步IO的优化思路是解决了应用程序需要先后发送询问请求、发送接收数据请求两个阶段的模式，在异步IO的模式下，只需要向内核发送一次请求就可以完成状态询问和数拷贝的所有操作。
• 在IO模型里面如果请求方从发起请求到数据最后完成的这一段过程中都需要自己参与，那么这种我们称为同步请求；反之，如果应用发送完指令后就不再参与过程了，只需要等待最终完成结果的通知，那么这就属于异步。
• 同步阻塞、同步非阻塞，他们不同的只是发起读取请求的时候一个请求阻塞，一个请求不阻塞，但是相同的是，他们都需要应用自己监控整个数据完成的过程。
• 为什么之后异步非阻塞 而没有异步阻塞呢，因为异步模型下请求指定发送完后就即刻返回了，没有任何后续流程了，所以它注定不会阻塞，所以也就只会有异步非阻塞模型了。

13. 守护进程

https://blog.csdn.net/mijichui2153/article/details/81394387 创建守护进程的步骤

14. 程序从堆中动态分配内存时，虚拟内存上怎么操作的

在Linux下，glibc 的malloc提供了下面两种动态内存管理的方法：堆内存分配和mmap的内存分配，此两种分配方法都是通过相应的Linux 系统调用来进行动态内存管理的。具体使用哪一种方式分配，根据glibc的实现，主要取决于所需分配内存的大小。一般情况中，应用层面的内存从进程堆中分配，当进程堆大小不够时，可以通过系统调用brk来改变堆的大小，但是在以下情况，一般由mmap系统调用来实现应用层面的内存分配：A、应用需要分配大于1M的内存，B、在没有连续的内存空间能满足应用所需大小的内存时。

(1)、调用brk实现进程里堆内存分配

在glibc中，当进程所需要的内存较小时，该内存会从进程的堆中分配，但是堆分配出来的内存空间，系统一般不会回收，只有当进程的堆大小到达最大限额时或者没有足够连续大小的空间来为进程继续分配所需内存时，才会回收不用的堆内存。在这种方式下，glibc会为进程堆维护一些固定大小的内存池以减少内存脆片。

(2)、使用mmap的内存分配

在glibc中，一般在比较大的内存分配时使用mmap系统调用，它以页为单位来分配内存的（在Linux中，一般一页大小定义为4K），这不可避免会带来内存浪费，但是当进程调用free释放所分配的内存时，glibc会立即调用unmmap，把所分配的内存空间释放回系统。

注意：这里我们讨论的都是虚拟内存的分配（即应用层面上的内存分配），主要由glibc来实现，它与内核中实际物理内存的分配是不同的层面，进程所分配到的虚拟内存可能没有对应的物理内存。如果所分配的虚拟内存没有对应的物理内存时，操作系统会利用缺页机制来为进程分配实际的物理内存。

15. 交换空间与虚拟内存的关系

• 虚拟内存和交换空间，这两个概念要和操作系统一起说，window下的“虚拟内存”实际上是存在磁盘上的页面文件，和linux的交换空间概念一样，都是物理上实际存在的东西，如果内存够用，没有缺页，你禁掉这两个东西不会影响虚拟存储器；
• 然而撇开操作系统，只谈理论，虚拟内存还是一种技术，它允许执行进程不必完全放在内存中。这两种其实都属于交换技术，交换技术除了因为内存紧张要使用之外，还有在一些操作系统如分时系统中为了改善进程组合(CPU密集型和IO密集型)也要用它进行中期调度。

（1）交换空间:

• Linux 中的交换空间（Swap space）在物理内存（RAM）被充满时被使用。如果系统需要更多的内存资源，而物理内存已经充满，内存中不活跃的页就会被移到交换空间去。虽然交换空间可以为带有少量内存的机器提供帮助，但是这种方法不应该被当做是对内存的取代。交换空间位于硬盘驱动器上，它比进入物理内存要慢。
• 交换空间可以是一个专用的交换分区（推荐的方法），交换文件，或两者的组合。
• 交换空间的总大小应该相当于你的计算机内存的两倍和 32 MB这两个值中较大的一个，但是它不能超过 2048 MB（2 GB）。

（2）虚拟内存:

• 虚拟内存是文件数据交叉链接的活动文件。是WINDOWS目录下的一个"WIN386.SWP"文件，这个文件会不断地扩大和自动缩小。
• 就速度方面而言,CPU的L1和L2缓存速度最快，内存次之，硬盘再次之。但是虚拟内存使用的是硬盘的空间，为什么我们要使用速度最慢的硬盘来做为虚拟内存呢？因为电脑中所有运行的程序都需要经过内存来执行，如果执行的程序很大或很多，就会导致我们只有可怜的256M/512M内存消耗殆尽。而硬盘空间动辄几十G上百G，为了解决这个问题，Windows中运用了虚拟内存技术，即拿出一部分硬盘空间来充当内存使用。

16. 堆和栈的区别；从堆和栈上建立对象哪个快？（考察堆和栈的分配效率比较）

（1）堆和栈的区别：

• 栈是机器系统提供的数据结构，而堆是C/C++函数库提供的。
• 现代计算机，都直接在代码底层支持栈的数据结构。这体现在，有专门的寄存器指向栈所在的地址，有专门的机器指令完成数据入栈出栈的操作。这种机制的特点是效率高，支持的数据有限，一般是整数，指针，浮点数等系统支持的数据类型，并不直接支持其他的数据结构。
• 堆的数据结构并不是由系统支持的，而是有函数库提供的。基本的malloc/realloc/free函数维护了一套内部的堆数据结构。当程序使用这些函数去获得新的内存空间时，这套函数首先试图从内部堆中寻找可用的内存空间，如果没有可以使用的内存空间，则试图利用系统调用来动态增加程序数据段的内存大小

原因：

• 系统调用可能不支持任意大小的内存分配。有些系统的系统调用只支持固定大小及其倍数的内存请求（按页分配)；这样的话对于大量的小内存分类会造成浪费。
• 系统调用申请内存代价昂贵，涉及用户态和核心态的转换。
• 没有管理的内存分配在大量复杂内存的分配释放下很容易造成内存碎片。

（2）申请效率：

• 栈由系统自动分配，速度较快。但程序员是无法控制的。
• 堆是由new分配的内存，一般速度比较慢，而且容易产生内存碎片,不过用起来最方便.
  另外，在WINDOWS下，最好的方式是用VirtualAlloc分配内存，他不是在堆，也不是在栈是直接在进程的地址空间中保留一快内存，虽然用起来最不方便。但是速度快，也最灵活。

17. 内存泄漏和内存溢出

（1）内存溢出

• 内存溢出是指程序在申请内存时没有足够的内存空间供其使用。原因可能如下：
• 1)内存中加载的数据过于庞大；
• 2)代码中存在死循环；
• 3)递归调用太深，导致堆栈溢出等；
• 4)内存泄漏最终导致内存溢出；

（2）内存泄漏

• 内存泄漏是指使用new申请内存， 但是使用完后没有使用delete释放内存，导致占用了有效内存。

  内存泄漏的分类：

  1）、堆内存泄漏 （Heap leak）。对内存指的是程序运行中根据需要分配通过malloc,realloc new等从堆中分配的一块内存，再是完成后必须通过调用对应的 free或者delete 删掉。如果程序的设计的错误导致这部分内存没有被释放，那么此后这块内存将不会被使用，就会产生Heap Leak。

  2）、系统资源泄露（Resource Leak）。主要指程序使用系统分配的资源比如 Bitmap,handle ,SOCKET等没有使用相应的函数释放掉，导致系统资源的浪费，严重可导致系统效能降低，系统运行不稳定。

  3）、没有将基类的析构函数定义为虚函数。当基类指针指向子类对象时，如果基类的析构函数不是virtual，那么子类的析构函数将不会被调用，子类的资源没有正确是释放，因此造成内存泄露。

18. 常见内存分配方式和错误

（1）.内存分配未成功，却使用了它。
（2）.内存分配虽然成功，但是尚未初始化就引用它。
（3）.内存分配成功并且已经初始化，但操作越过了内存的边界。
（4）.忘记了释放内存，造成内存泄露。
（5）.释放了内存却继续使用它。

• 1）程序中的对象调用关系过于复杂，实在难以搞清楚某个对象究竟是否已经释放了内存，此时应该重新设计数据结构，从根本上解决对象管理的混乱局面。
• 2）函数的return语句写错了，注意不要返回指向“栈内存”的“指针”或者“引用”，因为该内存在函数体结束时被自动销毁。
• 3）使用free或delete释放了内存后，没有将指针设置为NULL。导致产生“野指针”。

【规则1】用malloc或new申请内存之后，应该立即检查指针值是否为NULL。防止使用指针值为NULL的内存。
【规则2】不要忘记为数组和动态内存赋初值。防止将未被初始化的内存作为右值使用。
【规则3】避免数组或指针的下标越界，特别要当心发生“多1”或者“少1”操作。
【规则4】动态内存的申请与释放必须配对，防止内存泄漏。
【规则5】用free或delete释放了内存之后，立即将指针设置为NULL，防止产生“野指针”。

19. 堆内存和栈内存的区别

管理方式：对于栈来讲，是由编译器自动管理，无需手动控制；对于堆来说，分配和释放都是由程序员控制的。

空间大小：总体来说，栈的空间是要小于堆的。一般来讲在32位系统下，堆内存可以达到4G的空间，从这个角度来看堆内存几乎是没有什么限制的；但是对于栈来讲，一般是有一定的空间大小的。

碎片问题：对于堆来讲，由于分配和释放是由程序眼控制的(利用new/delete 或 malloc/free)，频繁的操作势必会造成内存空间的不连续，从而造成大量的内存碎片，使程序效率降低。对于栈来讲，则不会存在这个问题，因为栈是先进后出的数据结构，在某一对象弹出之前，它之前的所有对象都已经弹出。

生长方向：对于堆来讲，生长方向是向上的，也就是沿着内存地址增加的方向，对于栈来讲，它的生长方式是向下的，也就是沿着内存地址减小的方向增长。

分配方式：堆都是动态分配的，没有静态分配的堆。栈有两种分配方式：静态分配和动态分配，静态分配是编译器完成的，比如局部变量的分配；动态分配由alloca函数进行分配，但是栈的动态分配和堆是不同的，它的动态分配是由编译器实现的，无需我们手工实现。

分配效率：栈是机器系统提供的数据结构，计算机会在底层对栈提供支持，分配专门的寄存器存放栈的地址，压栈出栈都有专门的指令执行，这就决定了栈的效率很高。堆则是C/C++函数提供的，它的机制是很复杂的，例如为了分配一块内存，库函数会按照一定的算法在堆内存中搜索可用的足够大小的空间，如果没有足够大小的空间(可能是由于碎片太多)，就有可能调用系统功能去增加程序数据段的内存空间，这样就有机会分到足够大小的内存，然后进行返回。显然，堆的效率要比栈底的多。

20. 可重入函数和可重入内核

可重入内核在ULK（深入理解linux内核）中的定义是指若干个进程可以同时在内核态下执行，也就是说多个进程可以在内核态下并发执行内核代码。这里的可重入，是指可以多个进程进入内核，并不是重复/重新进入内核。

对于linux来说，可重入内核代码包含可重入函数和非可重入函数。

可重入函数的理解其实比较麻烦，可以从以下阐述：
（1）.可重入是与多线程无关的，一个函数被同一个线程调用2次以上，得到的结果具有可再现性。则这个函数是可重入的。
（2）.可重入讲究的是结果可再现性，因此，使用全局（静态）变量的函数，再次调用其函数的结果是不可再现的，这就是前面说的为何要求该函数只修改局部变量
故可重入函数，描述的是函数被多次调用但是结果具有可再现性
可重入函数条件：

• 1），不在函数内部使用静态或者全局数据
• 2），不返回静态或者全局数据，所有的数据都由函数调用者提供
• 3），使用本地数据，或者通过制作全局数据的本地拷贝来保护全局数据
• 4）， 如果必须访问全局数据，使用互斥锁（自旋锁）来保护
• 5），不调用不可重入函数 6），可重入函数必须是线程安全的

21. 操作系统动态内存分配的几种策略

第一种：单一连续分配方式

适用于单用户、单任务的操作系统。没什么好讲的。

第二种：固定分区分配

此种分配方式把内存空间分为固定大小的区域，每个分区允许一个作业被装入。分区大小可以不相同。通常会建立一张分区使用表来记录每个分区的起始地址、分区大小、状态。没有足够大的分区则拒绝分配内存。此种分配方式是最早的多道程序的存储管理方式。

缺点：限制了进程的数目，内存空间利用率比较低。

第三种：动态分区分配

此种方式涉及到相应的数据结构（分区表、分区链），分区分配算法和回收操作。

分区分配算法有：首次适应算法 （ 以链表结构为例，下同。从链首开始顺序查找，找到一个符合条件的分区即可进行相应的分配，没有符合条件的则分配失败 ） 、循环首次适应算法（从上一次符合条件的分区进行循环查找 ） 、最佳适应算法（首先需要把空闲分区链表按容量排序 [ 排序的目的是为了加速查找，否则就要遍历整个链表 ] ，然后从链首进行顺序查找 ） 、最坏适应算法（ 选择最大的空闲分区，然后进行分配 ） 、快速适应算法 （ 分类搜索算法，采取分区表加上相同类别管理的链表进行记录，仅需根据进程的长度，即可分配相应的内存空间　）。

回收内存的方式：只要回收空间与空闲分区相邻接，那么仅需与空闲分区合并即可；否则，需为回收区单独建立一项新的表，然后把回收区的首地址插入到空闲链中相应的位置。

缺点：相应分配的算法比较复杂，回收空间需要合并分区，系统开销大。

第四种：伙伴系统

规定：已分配区间或空闲区间的大小均为２的k次幂。

具体：当进程需要一个长度为ｎ的空间时，需要计算一个ｉ值，使得2的i-1次方小于n,２的i次方大于等于ｎ。然后根据计算结果，得到空闲分区链表中查找大小为２的ｉ次方的空闲分区，如果不存在这样的分区，则将2的ｉ＋１次方化成两个２的i次方的空闲分区，以此类推，总有符合的空闲分区。回收与分配空间的方式恰好相反。

第五种：哈希算法

在分类搜索算法的基础上，利用哈希快速查找的优点，快速到查找相同容量类别的链表，实现最佳的分配策略。

第六种：可重定位分区分配

此种算法考虑到的情况是：有很多内存碎片。对于一个进程来说，没有任何一个碎片能够满足进程所需的容量要求，但是碎片的容量总和能够满足一个或者多个进程的容量要求。

解决方案：①把内存中的所有作业全部移动，让他们紧凑在一起，这样内存碎片便集中在一起了。（需要对移动的程序地址进行修改才行）

分区分配算法：与动态分区分配算法类似，不过多了“紧凑”的操作。

第七种：对换

将占用内存却没有干什么事情的进程给放到对换区（外存分为文件区和对换区）。

22. 内部碎片和外部碎片

内部碎片是已经被分配出去的的内存空间大于请求所需的内存空间。

外部碎片是指还没有分配出去，但是由于大小太小而无法分配给申请空间的新进程的内存空间空闲块。

固定分区存在内部碎片，可变式分区分配会存在外部碎片；

页式虚拟存储系统存在内部碎片；段式虚拟存储系统，存在外部碎片

为了有效的利用内存，使内存产生更少的碎片，要对内存分页，内存以页为单位来使用，最后一页往往装不满，于是形成了内部碎片。

为了共享要分段，在段的换入换出时形成外部碎片，比如5K的段换出后，有一个4k的段进来放到原来5k的地方，于是形成1k的外部碎片。

23. 系统调用进入内核态的过程

https://blog.csdn.net/agoni_xiao/article/details/79034290 linux系统调用用户态到内核态流程

24. 内核态和用户态的区别

（1）.操作系统需要两种CPU状态

• 内核态（Kernel Mode）：运行操作系统程序，操作硬件
• 用户态（User Mode）：运行用户程序

（2）.指令划分

• 特权指令：只能由操作系统使用、用户程序不能使用的指令。 举例：启动I/O 内存清零 修改程序状态字 设置时钟 允许/禁止终端 停机
• 非特权指令：用户程序可以使用的指令。 举例：控制转移 算数运算 取数指令 访管指令（使用户程序从用户态陷入内核态）

（3）.特权级别

• 特权环：R0、R1、R2和R3
• R0相当于内核态，R3相当于用户态；
• 不同级别能够运行不同的指令集合；

（4）.CPU状态之间的转换

• 用户态—>内核态：唯一途径是通过中断、异常、陷入机制（访管指令）
• 内核态—>用户态：设置程序状态字PSW

（5）.内核态与用户态的区别

• 内核态与用户态是操作系统的两种运行级别，当程序运行在3级特权级上时，就可以称之为运行在用户态。因为这是最低特权级，是普通的用户进程运行的特权级，大部分用户直接面对的程序都是运行在用户态；
• 当程序运行在0级特权级上时，就可以称之为运行在内核态。
• 运行在用户态下的程序不能直接访问操作系统内核数据结构和程序。当我们在系统中执行一个程序时，大部分时间是运行在用户态下的，在其需要操作系统帮助完成某些它没有权力和能力完成的工作时就会切换到内核态（比如操作硬件）。

这两种状态的主要差别是

• 处于用户态执行时，进程所能访问的内存空间和对象受到限制，其所处于占有的处理器是可被抢占的
  处于内核态执行时，则能访问所有的内存空间和对象，且所占有的处理器是不允许被抢占的。

（6）. 通常来说，以下三种情况会导致用户态到内核态的切换

• 1）系统调用
  这是用户态进程主动要求切换到内核态的一种方式，用户态进程通过系统调用申请使用操作系统提供的服务程序完成工作。比如前例中fork()实际上就是执行了一个创建新进程的系统调用。

  而系统调用的机制其核心还是使用了操作系统为用户特别开放的一个中断来实现，例如Linux的int 80h中断。

  用户程序通常调用库函数，由库函数再调用系统调用，因此有的库函数会使用户程序进入内核态（只要库函数中某处调用了系统调用），有的则不会。

• 2）异常

  当CPU在执行运行在用户态下的程序时，发生了某些事先不可知的异常，这时会触发由当前运行进程切换到处理此异常的内核相关程序中，也就转到了内核态，比如缺页异常。

• 3）外围设备的中断

  当外围设备完成用户请求的操作后，会向CPU发出相应的中断信号，这时CPU会暂停执行下一条即将要执行的指令转而去执行与中断信号对应的处理程序，

  如果先前执行的指令是用户态下的程序，那么这个转换的过程自然也就发生了由用户态到内核态的切换。比如硬盘读写操作完成，系统会切换到硬盘读写的中断处理程序中执行后续操作等。

这3种方式是系统在运行时由用户态转到内核态的最主要方式，其中系统调用可以认为是用户进程主动发起的，异常和外围设备中断则是被动的。

25. 常见的进程调度算法以及linux的进程调度

调度种类

• 高级调度：(High-Level Scheduling)又称为作业调度，它决定把后备作业调入内存运行；
• 低级调度：(Low-Level Scheduling)又称为进程调度，它决定把就绪队列的某进程获得CPU；
• 中级调度：(Intermediate-Level Scheduling)又称为在虚拟存储器中引入，在内、外存对换区进行进程对换。

非抢占式调度与抢占式调度

• 非抢占式：分派程序一旦把处理机分配给某进程后便让它一直运行下去，直到进程完成或发生进程调度进程调度某事件而阻塞时，才把处理机分配给另一个进程。
• 抢占式：操作系统将正在运行的进程强行暂停，由调度程序将CPU分配给其他就绪进程的调度方式。

调度策略的设计

• 响应时间: 从用户输入到产生反应的时间
• 周转时间: 从任务开始到任务结束的时间
• CPU任务可以分为交互式任务和批处理任务，调度最终的目标是合理的使用CPU，使得交互式任务的响应时间尽可能短，用户不至于感到延迟，同时使得批处理任务的周转时间尽可能短，减少用户等待的时间。

调度算法：

1）FIFO或First Come, First Served (FCFS)先来先服务

• 调度的顺序就是任务到达就绪队列的顺序。
• 公平、简单(FIFO队列)、非抢占、不适合交互式。
• 未考虑任务特性，平均等待时间可以缩短。

2) Shortest Job First (SJF)

• 最短的作业(CPU区间长度最小)最先调度。
• SJF可以保证最小的平均等待时间。

3) Shortest Remaining Job First (SRJF)

• SJF的可抢占版本，比SJF更有优势。
• SJF(SRJF): 如何知道下一CPU区间大小？根据历史进行预测: 指数平均法。

4) 优先权调度

• 每个任务关联一个优先权，调度优先权最高的任务。
• 注意：优先权太低的任务一直就绪，得不到运行，出现“饥饿”现象。

5) Round-Robin(RR)轮转调度算法

• 设置一个时间片，按时间片来轮转调度（“轮叫”算法）
• 优点: 定时有响应，等待时间较短；缺点: 上下文切换次数较多；
• 时间片太大，响应时间太长；吞吐量变小，周转时间变长；当时间片过长时，退化为FCFS。

6) 多级队列调度

• 按照一定的规则建立多个进程队列
• 不同的队列有固定的优先级（高优先级有抢占权）
• 不同的队列可以给不同的时间片和采用不同的调度方法
• 存在问题1：没法区分I/O bound和CPU bound；
• 存在问题2：也存在一定程度的“饥饿”现象；

7) 多级反馈队列

• 在多级队列的基础上，任务可以在队列之间移动，更细致的区分任务。
• 可以根据“享用”CPU时间多少来移动队列，阻止“饥饿”。
• 最通用的调度算法，多数OS都使用该方法或其变形，如UNIX、Windows等。

多级反馈队列调度算法描述:

• 进程在进入待调度的队列等待时，首先进入优先级最高的Q1等待。
• 首先调度优先级高的队列中的进程。若高优先级中队列中已没有调度的进程，则调度次优先级队列中的进程。例如：Q1,Q2,Q3三个队列，只有在Q1中没有进程等待时才去调度Q2，同理，只有Q1,Q2都为空时才会去调度Q3。
• 对于同一个队列中的各个进程，按照时间片轮转法调度。比如Q1队列的时间片为N，那么Q1中的作业在经历了N个时间片后若还没有完成，则进入Q2队列等待，若Q2的时间片用完后作业还不能完成，一直进入下一级队列，直至完成。
• 在低优先级的队列中的进程在运行时，又有新到达的作业，那么在运行完这个时间片后，CPU马上分配给新到达的作业（抢占式）。

一个简单的例子
假设系统中有3个反馈队列Q1,Q2,Q3，时间片分别为2，4，8。现在有3个作业J1,J2,J3分别在时间 0 ，1，3时刻到达。而它们所需要的CPU时间分别是3，2，1个时间片。

时刻0 J1到达。 于是进入到队列1 ，运行1个时间片 ，时间片还未到，此时J2到达。

时刻1 J2到达。 由于时间片仍然由J1掌控，于是等待。J1在运行了1个时间片后，已经完成了在Q1中的2个时间片的限制，于是J1置于Q2等待被调度。现在处理机分配给J2。

时刻2 J1进入Q2等待调度，J2获得CPU开始运行。

时刻3 J3到达，由于J2的时间片未到，故J3在Q1等待调度，J1也在Q2等待调度。

时刻4 J2处理完成，由于J3，J1都在等待调度，但是J3所在的队列比J1所在的队列的优先级要高，于是J3被调度，J1继续在Q2等待。

时刻5 J3经过1个时间片，完成。

时刻6 由于Q1已经空闲，于是开始调度Q2中的作业，则J1得到处理器开始运行。 J1再经过一个时间片，完成了任务。于是整个调度过程结束。

26. 中断、陷阱、故障和终止

异常的类别

（1）中断：中断是异步发生的，来自处理器外部IO设备的信号（区别于同步异常：执行一条指令的结果），它不是由任何一条专门的指令造成的。例如网络适配器、磁盘控制器通过向处理器芯片上的一个管脚发信号，并将异常号放在系统总线上，来触发中断，这个异常号标识了引起中断的设备。中断处理程序总是返回到当前指令的下一条指令。

（2）陷阱：陷阱是同步异常，是执行一条指令的结果。陷阱最重要的用途是在用户程序和内核之间提供系统调用接口。陷阱总返回到当前指令的

下一条指令。

（3）故障：故障由错误引起，它可能被故常处理程序修正，如果修正成功，将返回到当前正在执行的指令，重新执行。否则处理程序返回到内核的abort历程，将终止故障程序。故障的一个典型是缺页异常。

（4）终止：由不可恢复的知名错误造成的结果，处理程序将返回到内核中的abort例程，终止应用程序。

27. 线程互斥和同步的方法

所谓同步，是指在不同进程之间的若干程序片断，它们的运行必须严格按照规定的某种先后次序来运行，这种先后次序依赖于要完成的特定的任务。如果用对资源的访问来定义的话，同步是指在互斥的基础上（大多数情况），通过其它机制实现访问者对资源的有序访问。在大多数情况下，同步已经实现了互斥，特别是所有写入资源的情况必定是互斥的。少数情况是指可以允许多个访问者同时访问资源。

所谓互斥，是指散布在不同进程之间的若干程序片断，当某个进程运行其中一个程序片段时，其它进程就不能运行它们之中的任一程序片段，只能等到该进程运行完这个程序片段后才可以运行。如果用对资源的访问来定义的话，互斥某一资源同时只允许一个访问者对其进行访问，具有唯一性和排它性。但互斥无法限制访问者对资源的访问顺序，即访问是无序的。

多线程同步和互斥有几种实现方法

线程间的同步方法大体可分为两类：用户模式和内核模式。顾名思义，内核模式就是指利用系统内核对象的单一性来进行同步，使用时需要切换内核态与用户态，而用户模式就是不需要切换到内核态，只在用户态完成操作。

用户模式下的方法有：原子操作（例如一个单一的全局变量），临界区。

内核模式下的方法有：事件，信号量，互斥量。

1）、临界区:通过对多线程的串行化来访问公共资源或一段代码，速度快，适合控制数据访问。
2）、互斥量:为协调共同对一个共享资源的单独访问而设计的。
3）、信号量:为控制一个具有有限数量用户资源而设计。
4）、事 件:用来通知线程有一些事件已发生，从而启动后继任务的开始。

28. 内存对齐的规则和作用

先来看看内存对齐的规则？

1.对于结构的各个成员，第一个成员位于偏移为0的位置，以后的每个数据成员的偏移量必须是 min(#pragma pack()指定的数,这个数据成员的自身长度)的倍数

2.在所有的数据成员完成各自对齐之后，结构或联合体本身也要进行对齐，对齐将按照 #pragram pack 指定的数值和结构或者联合体最大数据成员长度中比较小的那个 也就是 min(#pragram pack() , 长度最长的数据成员)；
#pragram pack(n) 表示的是设置n字节对齐，vc6默认的是8

接下来我们好好讨论一下内存对齐的作用？

1.平台原因（移植原因）：不是所有的硬件平台都能访问任意地址上的任意数据，某些硬件平台只能在某些地址处取某些特定类型的数据，否则抛出硬件异常

2.硬件原因：经过内存对齐之后，CPU的内存访问速度大大提升
cpu把内存当成是一块一块的，块的大小可以是2,4,8,16 个字节，因此CPU在读取内存的时候是一块一块进行读取的，块的大小称为（memory granularity）内存读取粒度。

我们再来看看为什么内存不对齐会影响读取速度？

假设CPU要读取一个4字节大小的数据到寄存器中（假设内存读取粒度是4），分两种情况讨论：

1）.数据从0字节开始

2）.数据从1字节开始

解析：当数据从0字节开始的时候，直接将0-3四个字节完全读取到寄存器，结算完成了。

当数据从1字节开始的时候，问题很复杂，首先先将前4个字节读到寄存器，并再次读取4-7字节的数据进寄存器，接着把0字节，4,6,7字节的数据剔除，最后合并1,2,3,4字节的数据进寄存器，对一个内存未对齐的寄存器进行了这么多额外操作，大大降低了CPU的性能。

但是这还属于乐观情况，上文提到内存对齐的作用之一是平台的移植原因，因为只有部分CPU肯干，其他部分CPU遇到未对齐边界就直接罢工了。

29. 页面置换算法

（1）最佳置换算法（OPT）（理想置换算法）：

• 从主存中移出永远不再需要的页面；如无这样的页面存在，则选择最长时间不需要访问的页面。于所选择的被淘汰页面将是以后永不使用的，或者是在最长时间内不再被访问的页面，这样可以保证获得最低的缺页率。

（2）先进先出置换算法（FIFO）：

• 是最简单的页面置换算法。这种算法的基本思想是：当需要淘汰一个页面时，总是选择驻留主存时间最长的页面进行淘汰，即先进入主存的页面先淘汰。其理由是：最早调入主存的页面不再被使用的可能性最大。

（3）最近最久未使用（LRU）：

• 这种算法的基本思想是：利用局部性原理，根据一个作业在执行过程中过去的页面访问历史来推测未来的行为。它认为过去一段时间里不曾被访问过的页面，在最近的将来可能也不会再被访问。所以，这种算法的实质是：当需要淘汰一个页面时，总是选择在最近一段时间内最久不用的页面予以淘汰。

（4）最近未使用（NRU）/ 时钟(CLOCK)置换算法：

• LRU算法的性能接近于OPT,但是实现起来比较困难，且开销大；FIFO算法实现简单，但性能差。所以操作系统的设计者尝试了很多算法，试图用比较小的开销接近LRU的性能，这类算法都是CLOCK算法的变体。
• 简单的CLOCK算法是给每一帧关联一个附加位，称为使用位。当某一页首次装入主存时，该帧的使用位设置为1;当该页随后再被访问到时，它的使用位也被置为1。对于页替换算法，用于替换的候选帧集合看做一个循环缓冲区，并且有一个指针与之相关联。当某一页被替换时，该指针被设置成指向缓冲区中的下一帧。当需要替换一页时，操作系统扫描缓冲区，以查找使用位被置为0的一帧。每当遇到一个使用位为1的帧时，操作系统就将该位重新置为0；如果在这个过程开始时，缓冲区中所有帧的使用位均为0，则选择遇到的第一个帧替换；如果所有帧的使用位均为1,则指针在缓冲区中完整地循环一周，把所有使用位都置为0，并且停留在最初的位置上，替换该帧中的页。由于该算法循环地检查各页面的情况，故称为CLOCK算法，又称为最近未用(Not Recently Used, NRU)算法。

https://www.cnblogs.com/fkissx/p/4712959.html 操作系统之页面置换算法

（5）二次机会法

• 区分读和写，enhanced clock algorithm 读和写都是访问，dirty
  bit是写位，如果写，为1，否则是0。同时使用脏位和使用位。
  修改clock算法，使它允许脏页总是在一次时钟头扫描时保留下来，以减少写回硬盘的操作（仅读的页可以直接释放）
  需要替换的页，其访问位和脏位都是0，如果都是 1，则有两次机会才被淘汰。从而让更多使用频率的页有更多的机会留在内存中。
  较为接近LRU算法，尽量保存dirty page，更好地减少了访问外存

（6）最不常用算法（least frequently used）LFU

• 选择置换访问次数最少的那个页面 对每个页面设置访问计数器，每当一个页面被访问时，++。淘汰数值最小的那个。
  硬盘计数器空间开销，排序查找时间开销；

  LRU/LFU区别：LRU考察的是多久未访问，时间越短越值得留在内存，LFU是访问次数/频度，次数越多越好。
  反例：一个页面在进程开始时使用的很多，但以后就不使用了。此时LFU就不适用了。
  把时间也考虑进去，在一段时间内考察LFU。比如，定期把次数寄存器右移一位。

https://blog.csdn.net/github_36487770/article/details/59127556 操作系统笔记（六）页面置换算法

30. 实现一个LRU页置换算法（或者FIFO置换算法）

我们这里主要看一看LRU缓存的规则：

新数据插入到链接头部
每当数据被访问，则将数据移到链表头部
当链表满的时候，则将链表尾部的数据删除，在将新数据插入链表头部

LRU：cache应该具备的两个操作：

get（key）：如果key在hashmap中存在，则直接查找其在list链表中的位置，然后将其移动到链表头部再更新其hashmap的映射
set（key，value）：如果key在hashmap中不存在，并且页面还满了，则删除尾部节点，再插入，如果存在于hashmap中，则将其从list链表中移动到链表头部，再更新其hashmap的映射
//查找时间复杂度 是hash_map 映射表 查找时间复杂度 O(1)

#include <iostream>
#include <vector>
#include <list>
#include <map>
#include <hash_map>
using namespace std;struct MyLRUnode
{int key;//形成key_value结构，通过这个唯一的键 直接可以找到这个值int value;MyLRUnode(int a, int b):key(a), value(b){}
};class LRUCache
{
public:LRUCache(int size){Lru_capacity = size;}int get(int key) //访问键为key的页面 找到 则将其重新插入到链表头{if(myhash_map.find(key) != myhash_map.end())//如果找到了{mylist.splice(mylist.begin(), mylist, myhash_map[key]);//则将mylist链表上找到的的iterator位置的元素重新链接到mylist.begin()位置上myhash_map[key] = mylist.begin();//然后将map映射表中 键为key的页面映射位置重置一下return myhash_map[key]->value;//最后返回将key对应的value返回}else//没找到 则返回-1{return -1;}}void put(int key, int value)//访问key value页面是否存在，若存在则提前“并更新value值”，不存在则创建之后再提前{if(myhash_map.find(key) == myhash_map.end())//key值不在页中{if(mylist.size() == Lru_capacity)//不在页中并且页还满了{myhash_map.erase(mylist.back().key);//将list尾部节点对应的key和其页映射关系删除mylist.pop_back();//将list尾部节点删除}MyLRUnode pnewnode(key, value);//创建新页mylist.push_front(pnewnode);//插入页链表中myhash_map[key] = mylist.begin();//key对应页面关系存入map}else//key值在页中{myhash_map[key]->value = value;//更新key对应的value值mylist.splice(mylist.begin(), mylist, myhash_map[key]);//将mylist链表上找到的的iterator位置的元素重新链接到mylist.begin()位置上myhash_map[key] = mylist.begin();//然后将map映射表中 键为key的页面映射位置重置一下}}void show_list(){list<MyLRUnode>::iterator it = mylist.begin();for(;it != mylist.end();){cout << it->key << ":" << it->value <<endl;it++;}cout << endl;}void show_map(){hash_map<int, list<MyLRUnode>::iterator>::iterator it = myhash_map.begin();while(it != myhash_map.end()){cout << it->first << ":" << (it->second)->value << endl;it++;}cout << endl;}
private:int Lru_capacity;list<MyLRUnode> mylist;//map<int, list<MyLRUnode>::iterator> mymap;//用来通过key键值 直接找到对应的双向链表节点hash_map<int, list<MyLRUnode>::iterator> myhash_map;
};int main()
{LRUCache lru(3);lru.put(1,100);lru.show_list();lru.show_map();lru.put(2,200);lru.show_list();lru.show_map();lru.put(3,300);lru.show_list();lru.show_map();lru.get(2);lru.show_list();lru.show_map();lru.put(4,400);lru.show_list();lru.show_map();return 0;
}

https://blog.csdn.net/IT_Quanwudi/article/details/99687714 LRU页面置换算法C++代码

31. 死锁的必要条件（怎么检测死锁，解决死锁问题）,银行家算法（死锁避免）

https://blog.csdn.net/wljliujuan/article/details/79614019 死锁，死锁的四个必要条件以及处理策略

32. 哲学家就餐，读者写者，生产者消费者（怎么加锁解锁，伪代码）

https://www.cnblogs.com/pangxiaodong/archive/2011/08/12/2136314.html 进程同步的几个经典题目-生产者消费者-哲学家进餐-读者写者

33. 海量数据的bitmap使用原理

https://blog.csdn.net/yangquanhui1991/article/details/52172340 海量数据处理——位图法bitmap

34. 布隆过滤器原理与优点

https://www.jianshu.com/p/2104d11ee0a2 详解布隆过滤器的原理、使用场景和注意事项

35. 布隆过滤器处理大规模问题时的持久化，包括内存大小受限、磁盘换入换出问题

Bloom过滤器处理大规模问题时的持久化，包括内存大小受限、磁盘换入换出问题
http://www.360doc.com/content/13/1226/18/15234639_340327658.shtml

布隆过滤器应用在一些需要快速判断某个元素是否属于集合，但是并不严格要求100%正确的场合

哈希表和位图的问题是当数据量大时会出现哈希冲突，为了降低冲突，布隆过滤器使用多个哈希函数，而不是一个。

哈希表的内存消耗随着数据量的增大也比较严重：就算只有1亿个URL，每个URL只算50个字符，就需要5GB内存。

优点：
节约缓存空间（空值的映射），不再需要空值映射，由于BF所用的空间非常小，所有BF可以常驻内存，Key-Value系统中Value 保存在磁盘中，使用布隆过滤器可以快速判断某个Key对应的Value是否存在，因此可以避免很多不必要的磁盘IO操作。

缺点：一般情况下不能从布隆过滤器中删除元素.我们很容易想到把位列阵变成整数数组，每插入一个元素相应的计数器加1，这样删除元素时将计数器减掉就可以了。然而要保证安全的删除元素并非如此简单。首先我们必须保证删除的元素的确在布隆过滤器里面.这一点单凭这个过滤器是无法保证的。

36. 共享内存实现

Linux共享内存实现机制的详解

内存共享： 两个不同进程A、B共享内存的意思是，同一块物理内存被映射到进程A、B各自的进程地址空间。进程A可以即时看到进程B对共享内存中数据的更新，反之亦然。由于多个进程共享同一块内存区域，必然需要某种同步机制，互斥锁和信号量都可以。

效率： 采用共享内存通信的一个显而易见的好处是效率高，因为进程可以直接读写内存，而不需要任何数据的拷贝。对于像管道和消息队列等通信方式，则需要在内核和用户空间进行四次的数据拷贝，而共享内存则只拷贝两次数据[1]： 一次从输入文件到共享内存区，另一次从共享内存区到输出文件。实际上，进程之间在共享内存时，并不总是读写少量数据后就解除映射，有新的通信时，再重新建 立共享内存区域。而是保持共享区域，直到通信完毕为止，这样，数据内容一直保存在共享内存中，并没有写回文件。共享内存中的内容往往是在解除映射时才写回 文件的。因此，采用共享内存的通信方式效率是非常高的。

共享内存实现机制
共享内存是通过把同一块内存分别映射到不同的进程空间中实现进程间通信。而共享内存本身不带任何互斥与同步机制，但当多个进程同时对同一内存进行读写操作时会破坏该内存的内容，所以，在实际中，同步与互斥机制需要用户来完成。
来看几个系统调用函数：
（1）创建共享内存

参数：key为输出型参数
size：size的大小应为1024整数倍（4k对齐）
shmflg:权限标志

（2）将共享内存映射到自己的内存空间:shmat
shmat是空间映射，通过创建的共享内存，在它能被进程访问之前，需要把该段内存映射到用户进程空间。shmaddr是用来指定共享内存映射到当前进程中的地址位置，要想改设置有用，shmflag必须设置为SHM_RND标志。大多情况下，应设置为空指针(void*)0,让系统自动选择地址，从而减小程序对硬件的依赖性。shmflag除了上面的设置外，还可以设置为SHM_RDONLY,使得映射过来的地址只读。
返回值：调用成功则返回映射地址的第一个字节，失败返回-1。
（3）解除映射:shmdt

参数为要解除的地址空间。
（4）控制共享内存

先来看第三个参数的结构体：


第二个参数cmd的选项：IPC_STAT:得到共享内存的状态，把共享内存的shmid_ds结构体复制到buf里
IPC_SET：改变共享内存的状态，把buf所指的结构体中的uid,gid,mode,复制到共享内存的shmid_ds结构体内
IPC_RMID:删除这块共享内存
BUF：共此内存管理结构体

代码实现：



共享内存的特点：

（1）共享内存就是允许两个不想关的进程访问同一个内存
（2）共享内存是两个正在运行的进程之间共享和传递数据的最有效的方式
（3）不同进程之间共享的内存通常安排为同一段物理内存
（4）共享内存不提供任何互斥和同步机制，一般用信号量对临界资源进行保护。
（5）接口简单

所有进程间通信的特点：

（1）管道
管道分为命名管道和匿名管道。匿名管道只能单向通信，且只能在有亲缘关系的进程间使用，常用于父子进程，当一个进程创建了一个管道，并调用fork创建子进程后，父进程关闭读端，子进程关闭写端，实现单向通信。管道是面向字节流，自带互斥与同步机制，生命周期随进程。
命名管道与匿名管道：命名管道允许毫不相干的两个进程之间

（2）信号量
信号量是一个计数器，可以用来控制多个线程对共享资源的访问，它不是用于交换大批数据，而用于多线程之间的同步，常作为一种锁机制，防止某进程在访问资源时其他进程也来访问，因此，主要作为进程间以及同一进程的不同线程间的同步手段。

（3）消息队列
消息队列是消息的链表，存放在内核中并由消息队列标识符标识，消息队列克服了信号传递信息少，管道只能承载无格式字节流以及缓冲区受限等特点。消息队列是UNIX下不同进程之间可以实现资源共享的 一种机制，UNIX允许不同进程将格式化的数据流以消息队列形式发送给任意进程，对消息队列具有操作权限的进程都可以使用msgget完成对消息队列的操作控制，通过使用消息类型，进程可以按顺序读信息，或为消息安排优先级顺序。

（4）共享内存
共享内存就是映射一段能被其他进程所访问的内存，这段共享内存由一个进程创建，但多个进程都可以访问，共享内存是最快的IPC方式，它是针对其他IPC方式运行效率低而专门设计的，它往往与其他机制，如信号量，配合使用，来实现进程间的同步。