2018-11-06
这一块操作系统主要分为两个部分，一个部分是书本上操作系统的知识，还有一部门是linux的相关知识：
###（1） 进程与线程的区别和联系
进程概念
进程是表示资源分配的基本单位，又是调度运行的基本单位。例如，用户运行自己的程序，系统就创建一个进程，并为它分配资源，包括各种表格、内存空间、磁盘空间、I/O设备等。然后，把该进程放人进程的就绪队列。进程调度程序选中它，为它分配CPU以及其它有关资源，该进程才真正运行。所以，进程是系统中的并发执行的单位。
线程概念
线程是进程中执行运算的最小单位，亦即执行处理机调度的基本单位。如果把进程理解为在逻辑上操作系统所完成的任务，那么线程表示完成该任务的许多可能的子任务之一。例如，假设用户启动了一个窗口中的数据库应用程序，操作系统就将对数据库的调用表示为一个进程。假设用户要从数据库中产生一份工资单报表，并传到一个文件中，这是一个子任务；在产生工资单报表的过程中，用户又可以输人数据库查询请求，这又是一个子任务。这样，操作系统则把每一个请求――工资单报表和新输人的数据查询表示为数据库进程中的独立的线程。线程可以在处理器上独立调度执行，这样，在多处理器环境下就允许几个线程各自在单独处理器上进行。操作系统提供线程就是为了方便而有效地实现这种并发性
引入线程的好处
（1）易于调度。
（2）提高并发性。通过线程可方便有效地实现并发性。进程可创建多个线程来执行同一程序的不同部分。
（3）开销少。创建线程比创建进程要快，所需开销很少。。
（4）利于充分发挥多处理器的功能。通过创建多线程进程（即一个进程可具有两个或更多个线程），每个线程在一个处理器上运行，从而实现应用程序的并发性，使每个处理器都得到充分运行。
进程和线程的关系
（1）一个线程只能属于一个进程，而一个进程可以有多个线程，但至少有一个线程。线程是操作系统可识别的最小执行和调度单位。
（2）资源分配给进程，同一进程的所有线程共享该进程的所有资源。 同一进程中的多个线程共享代码段(代码和常量)，数据段(全局变量和静态变量)，扩展段(堆存储)。但是每个线程拥有自己的栈段，栈段又叫运行时段，用来存放所有局部变量和临时变量。
（3）处理机分给线程，即真正在处理机上运行的是线程。
（4）线程在执行过程中，需要协作同步。不同进程的线程间要利用消息通信的办法实现同步。
线程与进程的比较
线程具有许多传统进程所具有的特征，故又称为轻型进程(Light—Weight Process)或进程元；而把传统的进程称为重型进程(Heavy—Weight Process)，它相当于只有一个线程的任务。在引入了线程的操作系统中，通常一个进程都有若干个线程，至少需要一个线程。下面，我们从调度、并发性、 系统开销、拥有资源等方面，来比较线程与进程。
1．调度
在传统的操作系统中，拥有资源的基本单位和独立调度、分派的基本单位都是进程。而在引入线程的操作系统中，则把线程作为调度和分派的基本单位。而把进程作 为资源拥有的基本单位，使传统进程的两个属性分开，线程便能轻装运行，从而可显著地提高系统的并发程度。在同一进程中，线程的切换不会引起进程的切换，在 由一个进程中的线程切换到另一个进程中的线程时，将会引起进程的切换。
2．并发性
在引入线程的操作系统中，不仅进程之间可以并发执行，而且在一个进程中的多个线程之间，亦可并发执行，因而使操作系统具有更好的并发性，从而能更有效地使 用系统资源和提高系统吞吐量。例如，在一个未引入线程的单CPU操作系统中，若仅设置一个文件服务进程，当它由于某种原因而被阻塞时，便没有其它的文件服 务进程来提供服务。在引入了线程的操作系统中，可以在一个文件服务进程中，设置多个服务线程，当第一个线程等待时，文件服务进程中的第二个线程可以继续运 行；当第二个线程阻塞时，第三个线程可以继续执行，从而显著地提高了文件服务的质量以及系统吞吐量。
3．拥有资源
不论是传统的操作系统，还是设有线程的操作系统，进程都是拥有资源的一个独立单位，它可以拥有自己的资源。一般地说，线程自己不拥有系统资源(也有一点必 不可少的资源)，但它可以访问其隶属进程的资源。亦即，一个进程的代码段、数据段以及系统资源，如已打开的文件、I/O设备等，可供问一进程的其它所有线 程共享。
4．系统开销
###（2） 一个进程可以创建多少线程，和什么有关
1.操作系统给一个进程创建的虚拟空间最大为2G，一个线程的栈大小是1M，所以理论上最多只能创建2048个线程。
2.和本机的内存可由关系，线程堆栈的大小也是可以修改的。
###（3） 一个程序从开始运行到结束的完整过程（四个过程）
1.一个程序开始运行，首先进行创建进程，操作系统首先为该程序申请一个空白的PCB，然后向这个PCB中填入一些控制和管理进程的相关信息。然后分配所需要的资源，跳入就绪状态。
2.程序进入就绪状态，等待处理机时间片的到来，进程被调度，获得对应的时间片，就由就绪状态跳转到运行状态。注意，时间片完了之后，进程会自动从运行状态跳到就绪状态，等待下一个时间片的到来。
3.如果程序运行过程中请求某一个资源，例如IO资源，这个时候IO资源正在忙碌，此时程序主动进入阻塞状态，等待IO资源的空闲。
4.当IO资源空闲，会主动由另外一个进程唤醒正在阻塞的进程，这个时候进程转为就绪状态，等待时间片的到来。
5.运行完成之后，进行结束状态，操作系统回收一些资源的工作。
###（4） 进程通信方法（Linux和windows下），线程通信方法（Linux和windows下）
linux下进程的通信方法：1.管道 2.信号量 3.共享内存 4.消息队列 5.套接字
windows下进程通信的方法：2. 共享内存（是文件映射的一种特殊情况）；3.邮件槽（mailslot）（点对点消息队列）; 4.匿名管道；5；命名管道； 6.socket；
1.文件映射
2.共享内存
Win32 API中共享内存(Shared Memory)实际就是文件映射的一种特殊情况。进程在创建文件映射对象时用0xFFFFFFFF来代替文件句柄(HANDLE)，就表示了对应的文件映 射对象是从操作系统页面文件访问内存，其它进程打开该文件映射对象就可以访问该内存块。由于共享内存是用文件映射实现的，所以它也有较好的安全性，也只能 运行于同一计算机上的进程之间。
3.匿名管道
管道(Pipe)是一种具有两个端点的通信通道：有一端句柄的进程可以和有另一端句柄的进程通信。管道可以是单向－一端是只读的，另一端点是只写的；也可以是双向的一管道的两端点既可读也可写。
4.命名管道
命 名管道(Named Pipe)是服务器进程和一个或多个客户进程之间通信的单向或双向管道。不同于匿名管道的是命名管道可以在不相关的进程之间和不同计算机之间使用，服务器 建立命名管道时给它指定一个名字，任何进程都可以通过该名字打开管道的另一端，根据给定的权限和服务器进程通信。
命名管道提供了相对简单的编程接口，使通过网络传输数据并不比同一计算机上两进程之间通信更困难，不过如果要同时和多个进程通信它就力不从心了。
5.邮件槽
邮件槽(Mailslots)提供进程间单向通信能力，任何进程都能建立邮件槽成为邮件槽服务器。其它进程，称为邮件槽客户，可以通过邮件槽的名字给邮件槽服务器进程发送消息。进来的消 息一直放在邮件槽中，直到服务器进程读取它为止。一个进程既可以是邮件槽服务器也可以是邮件槽客户，因此可建立多个邮件槽实现进程间的双向通信。
邮 件槽与命名管道相似，不过它传输数据是通过不可靠的数据报(如TCP/IP协议中的UDP包)完成的，一旦网络发生错误则无法保证消息正确地接收，而命名 管道传输数据则是建立在可靠连接基础上的。不过邮件槽有简化的编程接口和给指定网络区域内的所有计算机广播消息的能力，所以邮件槽不失为应用程序发送和接 收消息的另一种选择。
6.Sockets
Windows Sockets规范是以U.C.Berkeley大学BSD UNIX中流行的Socket接口为范例定义的一套Windows下的网络编程接口。除了Berkeley Socket原有的库函数以外，还扩展了一组针对Windows的函数，使程序员可以充分利用Windows的消息机制进行编程。
windows线程通信：1.全局变量，2，message消息队列机制
###（5） 进程调度方法详细介绍
1.一个程序开始运行，首先进行创建进程，操作系统首先为该程序申请一个空白的PCB，然后向这个PCB中填入一些控制和管理进程的相关信息。然后分配所需要的资源，跳入就绪状态。
2.程序进入就绪状态，等待处理机时间片的到来，进程被调度，获得对应的时间片，就由就绪状态跳转到运行状态。注意，时间片完了之后，进程会自动从运行状态跳到就绪状态，等待下一个时间片的到来。
3.如果程序运行过程中请求某一个资源，例如IO资源，这个时候IO资源正在忙碌，此时程序主动进入阻塞状态，等待IO资源的空闲。
4.当IO资源空闲，会主动由另外一个进程唤醒正在阻塞的进程，这个时候进程转为就绪状态，等待时间片的到来。
5.运行完成之后，进行结束状态，操作系统回收一些资源的工作。
###（6） 页面置换方法详细介绍
页面置换算法就是只内存需要和外存替换数据，选择调出的页面的算法就称为页面置换算法，目前常见的页面置换算法有以下几种：
1.最佳置换算法（OPT）：选择被淘汰的页面将是以后永远不适用的，无法预估，该算法理想算法，无法实现。
2.先进先出算法（FIFO）：优先淘汰最早进入内存的页面，存在问题，当分配的物理块增大时，页面故障不减少反而增大的现象。
3.最近最久未使用置换算法（LRU）：选择最近最长时间未访问过的页面予以淘汰，性能较好。
###（7） 死锁的必要条件（怎么检测死锁，解决死锁问题）
死锁有四个必要条件：
（1）互斥条件：一个资源每次只能被一个进程使用。
（2）请求与保持条件：一个进程因请求资源而阻塞时，对已获得的资源保持不放。
（3）不剥夺条件:进程已获得的资源，在末使用完之前，不能强行剥夺。
（4）循环等待条件:若干进程之间形成一种头尾相接的循环等待资源关系。
检测死锁：利用死锁定理化简资源分配图以检测死锁的存在
解决死锁：
1.资源剥夺法：挂起某些死锁的进程，并抢夺它的资源，以便让其他进程继续推进
2.撤销进程法：强制撤销部分，甚至全部死锁进程，并剥夺资源
3.进程回退法：让进程回退到避免死锁的地步
###（8） 海量数据的bitmap使用原理
原理：bitmap是一个十分实用的结构。所谓的Bit-map就是用一个bit位来标记某个元素相应的Value， 而Key即是该元素。因为採用了Bit为单位来存储数据，因此在存储空间方面，能够大大节省。
适用范围：可进行数据的高速查找。判重。删除，一般来说数据范围是int的10倍下面
基本原理及要点：使用bit数组来表示某些元素是否存在，比方8位电话号码
实际解决方案：对于这种问题，我们通常还有一种更好的方法，那就是位图，位图也是hash的一种应用。对于这些无符号整数我们完全没有必要用4个字节来表示，因为现在我们只需要找这个数存在还是不存在，只有两种状态，所以我们可以用一个bit位来表示一个数存在还是不存在，0表示不存在，1表示存在。所以现在40亿个无符号整数只需要500M就可以表示了。要找这个数存在还是不存在，只需要计算这个数在bitmap中的位置，再看这一位是0还是1就可以了。
###（9） 布隆过滤器原理与优点
原理：如果想判断一个元素是不是在一个集合里，一般想到的是将所有元素保存起来，然后通过比较确定。链表，树等等数据结构都是这种思路. 但是随着集合中元素的增加，我们需要的存储空间越来越大，检索速度也越来越慢。不过世界上还有一种叫作散列表（又叫哈希表，Hash table）的数据结构。它可以通过一个Hash函数将一个元素映射成一个位阵列（Bit Array）中的一个点。这样一来，我们只要看看这个点是不是 1 就知道可以集合中有没有它了。这就是布隆过滤器的基本思想。
Hash面临的问题就是冲突。假设 Hash 函数是良好的，如果我们的位阵列长度为 m 个点，那么如果我们想将冲突率降低到例如 1%, 这个散列表就只能容纳 m/100 个元素。显然这就不叫空间有效了（Space-efficient）。解决方法也简单，就是使用多个 Hash，如果它们有一个说元素不在集合中，那肯定就不在。如果它们都说在，虽然也有一定可能性它们在说谎，不过直觉上判断这种事情的概率是比较低的。
优点：
相比于其它的数据结构，布隆过滤器在空间和时间方面都有巨大的优势。布隆过滤器存储空间和插入/查询时间都是常数。另外, Hash 函数相互之间没有关系，方便由硬件并行实现。布隆过滤器不需要存储元素本身，在某些对保密要求非常严格的场合有优势。
布隆过滤器可以表示全集，其它任何数据结构都不能；
k 和 m 相同，使用同一组 Hash 函数的两个布隆过滤器的交并差运算可以使用位操作进行。
缺点：
但是布隆过滤器的缺点和优点一样明显。误算率（False Positive）是其中之一。随着存入的元素数量增加，误算率随之增加。但是如果元素数量太少，则使用散列表足矣。
另外，一般情况下不能从布隆过滤器中删除元素. 我们很容易想到把位列阵变成整数数组，每插入一个元素相应的计数器加1, 这样删除元素时将计数器减掉就可以了。然而要保证安全的删除元素并非如此简单。首先我们必须保证删除的元素的确在布隆过滤器里面. 这一点单凭这个过滤器是无法保证的。另外计数器回绕也会造成问题。
###（10） 布隆过滤器处理大规模问题时的持久化，包括内存大小受限、磁盘换入换出问题
布隆过滤器应用在一些需要快速判断某个元素是否属于集合，但是并不严格要求100%正确的场合
哈希表和位图的问题是当数据量大时会出现哈希冲突，为了降低冲突，布隆过滤器使用多个哈希函数，而不是一个。
哈希表的内存消耗随着数据量的增大也比较严重：就算只有1亿个URL，每个URL只算50个字符，就需要5GB内存。
优点：
节约缓存空间（空值的映射），不再需要空值映射，由于BF所用的空间非常小，所有BF可以常驻内存，Key-Value系统中Value 保存在磁盘中，使用布隆过滤器可以快速判断某个Key对应的Value是否存在，因此可以避免很多不必要的磁盘IO操作。
缺点：一般情况下不能从布隆过滤器中删除元素.我们很容易想到把位列阵变成整数数组，每插入一个元素相应的计数器加1，这样删除元素时将计数器减掉就可以了。然而要保证安全的删除元素并非如此简单。首先我们必须保证删除的元素的确在布隆过滤器里面.这一点单凭这个过滤器是无法保证的。
###（11） 同步IO和异步IO
同步IO：用户进程发出IO调用，去获取IO设备数据，双方的数据要经过内核缓冲区同步，完全准备好后，再复制返回到用户进程。而复制返回到用户进程会导致请求进程阻塞，直到I/O操作完成。
异步IO：用户进程发出IO调用，去获取IO设备数据，并不需要同步，内核直接复制到进程，整个过程不导致请求进程阻塞。
###（12） 文件读写使用的系统调用
文件读写会涉及到的系统调用：
1.open：打开某个文件，并配置响应的权限
2.close：关闭文件描述符
3.read：读取函数，设置缓存区，及缓存区的大小
4.write：写操作函数，指定写入数据的大小
5.lseek：指定文件偏移量函数，文件偏移量指的是当前文件操作位置相对于文件开始位置的偏移。
6.fstat：获取文件状态
mmap()映射后，让用户程序直接访问设备内存，相比较在用户控件和内核空间互相拷贝数据，效率更高。在要求高性能的应用中比较常用。mmap映射内存必须是页面大小的整数倍，面向流的设备不能进行mmap，mmap的实现和硬件有关。
8.fcntl：文件属性的调用
9.ioctl: ioctl()函数通过对文件描述符的发送命令来控制设备。
读文件
1、进程调用库函数向内核发起读文件请求；
2、内核通过检查进程的文件描述符定位到虚拟文件系统的已打开文件列表表项；
3、调用该文件可用的系统调用函数read()
4、在inode中，通过文件内容偏移量计算出要读取的页；
5、通过inode找到文件对应的address_space；
6、在address_space中访问该文件的页缓存树，查找对应的页缓存结点：
（1）如果页缓存命中，那么直接返回文件内容；
7、文件内容读取成功。
写文件
前5步和读文件一致，在address_space中查询对应页的页缓存是否存在：
6、如果页缓存命中，直接把文件内容修改更新在页缓存的页中。写文件就结束了。这时候文件修改位于页缓存，并没有写回到磁盘文件中去。
8、一个页缓存中的页如果被修改，那么会被标记成脏页。脏页需要写回到磁盘中的文件块。有两种方式可以把脏页写回磁盘：
（1）手动调用sync()或者fsync()系统调用把脏页写回
（2）pdflush进程会定时把脏页写回到磁盘
同时注意，脏页不能被置换出内存，如果脏页正在被写回，那么会被设置写回标记，这时候该页就被上锁，其他写请求被阻塞直到锁释放。
参考：
###（13） 线程池的了解、优点、调度处理方式和保护任务队列的方式
了解：
当有很多任务需要采用线程执行的时候，而且有时可能会创建很多线程的时候，最好使用下线程池。
不使用线程池的话，所创建的线程数无法控制，比如一下子创建了几百几千个线程，电脑一下子就崩溃了。创建销毁线程，消耗资源较多。
优点：
1:提高效率 创建好一定数量的线程放在池中，等需要使用的时候就从池中拿一个，这要比需要的时候创建一个线程对象要快的多。
2:方便管理 可以编写线程池管理代码对池中的线程统一进行管理，比如说系统启动时由该程序创建100个线程，每当有请求的时候，就分配一个线程去工作， 如果刚好并发有101个请求，那多出的这一个请求可以排队等候，避免因无休止的创建线程导致系统崩溃
###（14） 怎么回收线程
1.线程退出有多种方式，如return，pthread_exit,pthread_cancel等；
2.线程分为可结合的（joinable）和 分离的（detached）两种，如果没有在创建线程时设置线程的属性为PTHREAD_CREATE_DETACHED，则线程默认是可结合的。
3.可结合的线程在线程退出后不会立即释放资源，必须要调用pthread_join来显式的结束线程。
4.分离的线程在线程退出时系统会自动回收资源。
###（15） 僵尸进程问题
一个进程结束了，但是他的父进程没有等待（调用wait / waitpid）他，那么他将变成一个僵尸进程。
1.父进程通过wait和waitpid等函数等待子进程结束，这会导致父进程挂起。执行wait（）或waitpid（）系统调用，则子进程在终止后会立即把它在进程表中的数据返回给父进程，此时系统会立即删除该进入点。在这种情形下就不会产生defunct进程。
2.如果父进程很忙，那么可以用signal函数为SIGCHLD安装handler。在子进程结束后，父进程会收到该信号，可以在handler中调用wait回收。
3.如果父进程不关心子进程什么时候结束，那么可以用signal（SIGCLD, SIG_IGN）或signal（SIGCHLD, SIG_IGN）通知内核，自己对子进程的结束不感兴趣，那么子进程结束后，内核会回收，并不再给父进程发送信号
4.fork两次，父进程fork一个子进程，然后继续工作，子进程fork一个孙进程后退出，那么孙进程被init接管，孙进程结束后，init会回收。不过子进程的回收还要自己做。
###（16） memcache了解
MemCache是一个自由、源码开放、高性能、分布式的分布式内存对象缓存系统，用于动态Web应用以减轻数据库的负载。它通过在内存中缓存数据和对象来减少读取数据库的次数，从而提高了网站访问的速度。 MemCaChe是一个存储键值对的HashMap，在内存中对任意的数据（比如字符串、对象等）所使用的key-value存储，数据可以来自数据库调用、API调用，或者页面渲染的结果。MemCache设计理念就是小而强大，它简单的设计促进了快速部署、易于开发并解决面对大规模的数据缓存的许多难题，而所开放的API使得MemCache能用于Java、C/C++/C#、Perl、Python、PHP、Ruby等大部分流行的程序语言。
###（17） 异常和中断的区别
中断和异常的作用是指示系统中的某个地方发生一些事件, 需要引起处理器(包括正在执行中的程序和任务)的注意. 当中断和异常发生时, 典型的结果是迫使处理器将控制从当前正在执行的程序或任务转移到另一个历程或任务中去. 该例程叫做中断处理程序, 或者异常处理程序. 如果是一个任务, 则发生任务切换.
1.中断(Interrupt)
中断包括硬件中断和软中断.
硬件中断是由外围硬件设备发出的中断信号引发的, 以请求处理器提供服务. 当I/O接口发出中断请求时, 会被像8259A和I/O APIC这样的中断控制器收集, 并发送到处理器. 硬件中断完全是随机产生的, 与处理器的执行并不同步. 当中断发生时, 处理器要先执行完当前的指令, 然后才对中断进行处理.
软中断是由 int n 指令引发的中断处理, n是中断号或者叫类型吗.
2.异常(Exception)
异常就是16位汇编中的内部中断. 它们是处理器内部产生的中断, 表示在指令执行的过程中遇到了错误的状况. 当处理器执行一条非法指令, 或者因条件不具备, 指令不能正常执行时, 将引发这种类型的中断. 以上所列都是异常情况, 所以内部中断又叫异常或者异常中断. 比如在执行除法指令 div/idiv 时, 遇到了被0除的情况(除数是0); 在比如, 使用jmp指令发起任务切换时, 指令的操作数不是一个有效的TSS描述符选择子.
异常分为三种, 第一种是程序错误异常, 指处理器在执行指令的过程中, 检测到了程序中的错误, 并由此而引发的异常.
第二种是软件引发的异常. 这类异常通常由into, int3和bound指令主动发起. 这些指令允许在指令流的当前点上检查实施异常处理的条件是否满足. 举个例子, into指令在执行时, 将检查EFLAGS的OF标志, 如果满足为1的条件, 则引发异常.
第三种是机器检查异常. 这种异常是处理器型号相关的, 也就是说, 每种处理器都不太一样. 无论如何, 处理器提供了一种对硬件芯片内部和总线处理进行检查的机制, 当检测到错误是, 将引发异常.
###（18） 一般情况下在Linux/windows平台下栈空间的大小
1.Windows下程序栈空间的大小，VC++ 6.0 默认的栈空间是1M。
VC6.0中修改堆栈大小的方法：
1.选择 “Project->Setting”.
2.选择 “Link”.
3.选择 "Category"中的 “Output”.
4.在 "Stack allocations"中的"Reserve:"中输栈的大小
在VS中设置堆栈大小的方法为：
1.选择"项目->属性".
2.选择"链接器".
3.选择"系统".
4.在"堆栈保留大小"中输栈的大小
2 .Linux下程序栈空间的大小
linux下非编译器决定栈大小，而是由操作系统环境决定；而在Windows平台下栈的大小是被记录在可执行文件中的（由编译器来设置)，即：windows下可以由编译器决定栈大小，而在Linux下是由系统环境变量来控制栈的大小的。
在Linux下通过如下命令可查看和设置栈的大小：
命令： ulimit -a # 显示当前栈的大小 （ulimit为系统命令，非编译器命令）
命令： ulimit -s 32768 # 设置当前栈的大小为32M bytes