1.請(qǐng)你說(shuō)一下進(jìn)程與線程的概念，其中有什么區(qū)別，他們各自又是怎么同步的
基本概念：
是對(duì)運(yùn)行時(shí)程序的封裝，是系統(tǒng)進(jìn)行資源調(diào)度和分配的的基本單位，實(shí)現(xiàn)了操作系統(tǒng)的并發(fā)；
線程是進(jìn)程的子任務(wù)，是CPU調(diào)度和分派的基本單位，用于保證程序的實(shí)時(shí)性，實(shí)現(xiàn)進(jìn)程內(nèi)部的并發(fā)；
區(qū)別：
1.一個(gè)線程只能屬于一個(gè)進(jìn)程，而一個(gè)進(jìn)程可以有多個(gè)線程。線程依賴(lài)于進(jìn)程而存在。
2.進(jìn)程在執(zhí)行過(guò)程中擁有獨(dú)立的內(nèi)存單元，而多個(gè)線程共享進(jìn)程的內(nèi)存。（資源分配給進(jìn)程，同一進(jìn)程的所有線程共享該進(jìn)程的所有資源。同一進(jìn)程中的多個(gè)線程共享代碼段（代碼和常量），數(shù)據(jù)段（全局變量和靜態(tài)變量），擴(kuò)展段（堆存儲(chǔ)）。但是每個(gè)線程擁有自己的棧段，棧段又叫運(yùn)行時(shí)段，用來(lái)存放所有局部變量和臨時(shí)變量。）
3.進(jìn)程是資源分配的最小單位，線程是CPU調(diào)度的最小單位；
4.系統(tǒng)開(kāi)銷(xiāo)進(jìn)程切換的開(kāi)銷(xiāo)也遠(yuǎn)大于線程切換的開(kāi)銷(xiāo)。
5.通信：進(jìn)程間通信IPC，線程間可以直接讀寫(xiě)進(jìn)程數(shù)據(jù)段（如全局變量）來(lái)進(jìn)行通信——需要進(jìn)程同步和互斥手段的輔助，以保證數(shù)據(jù)的一致性。在有的系統(tǒng)中，線程的切換、同步和通信都無(wú)須操作系統(tǒng)內(nèi)核的干預(yù)
6.進(jìn)程編程調(diào)試簡(jiǎn)單可靠性高，但是創(chuàng)建銷(xiāo)毀開(kāi)銷(xiāo)大；線程正相反，開(kāi)銷(xiāo)小，切換速度快，但是編程調(diào)試相對(duì)復(fù)雜。
7.進(jìn)程間不會(huì)相互影響 ；線程一個(gè)線程掛掉將導(dǎo)致整個(gè)進(jìn)程掛掉
8.進(jìn)程適應(yīng)于多核、多機(jī)分布；線程適用于多核
2.進(jìn)程間通信的方式：
進(jìn)程間通信主要包括管道、系統(tǒng)IPC（包括消息隊(duì)列、信號(hào)量、信號(hào)、共享內(nèi)存等）、以及套接字socket。
1.管道：
管道主要包括無(wú)名管道和命名管道:管道可用于具有親緣關(guān)系的父子進(jìn)程間的通信，有名管道除了具有管道所具有的功能外，它還允許無(wú)親緣關(guān)系進(jìn)程間的通信
1.1 普通管道PIPE：
1)它是半雙工的（即數(shù)據(jù)只能在一個(gè)方向上流動(dòng)），具有固定的讀端和寫(xiě)端
2)它只能用于具有親緣關(guān)系的進(jìn)程之間的通信（也是父子進(jìn)程或者兄弟進(jìn)程之間）
3)它可以看成是一種特殊的文件，對(duì)于它的讀寫(xiě)也可以使用普通的read、write等函數(shù)。但是它不是普通的文件，并不屬于其他任何文件系統(tǒng)，并且只存在于內(nèi)存中。
1.2 命名管道FIFO：
1)FIFO可以在無(wú)關(guān)的進(jìn)程之間交換數(shù)據(jù)
2)FIFO有路徑名與之相關(guān)聯(lián)，它以一種特殊設(shè)備文件形式存在于文件系統(tǒng)中。
2. 系統(tǒng)IPC：
2.1 消息隊(duì)列
消息隊(duì)列，是消息的鏈接表，存放在內(nèi)核中。一個(gè)消息隊(duì)列由一個(gè)標(biāo)識(shí)符來(lái)標(biāo)記。具有寫(xiě)權(quán)限得進(jìn)程可以按照一定得規(guī)則向消息隊(duì)列中添加新信息；對(duì)消息隊(duì)列有讀權(quán)限得進(jìn)程則可以從消息隊(duì)列中讀取信息；
2.2 信號(hào)量semaphore
信號(hào)量（semaphore）是一個(gè)計(jì)數(shù)器，可以用來(lái)控制多個(gè)進(jìn)程對(duì)共享資源的訪問(wèn)。
2.3 信號(hào)signal
信號(hào)是一種比較復(fù)雜的通信方式，用于通知接收進(jìn)程某個(gè)事件已經(jīng)發(fā)生。
2.4 共享內(nèi)存（Shared Memory）
它使得多個(gè)進(jìn)程可以訪問(wèn)同一塊內(nèi)存空間，不同進(jìn)程可以及時(shí)看到對(duì)方進(jìn)程中對(duì)共享內(nèi)存中數(shù)據(jù)得更新。這種方式需要依靠某種同步操作，如互斥鎖和信號(hào)量等
3.套接字SOCKET：
socket也是一種進(jìn)程間通信機(jī)制，它可用于不同主機(jī)之間的進(jìn)程通信。
3.線程間通信的方式
- 臨界區(qū)：通過(guò)多線程的串行化來(lái)訪問(wèn)公共資源，速度快，適合控制數(shù)據(jù)訪問(wèn)；
- 互斥量Synchronized/Lock：采用互斥對(duì)象機(jī)制，只有擁有互斥對(duì)象的線程才有訪問(wèn)公共資源的權(quán)限。因?yàn)榛コ鈱?duì)象只有一個(gè)，所以可以保證公共資源不會(huì)被多個(gè)線程同時(shí)訪問(wèn)
- 信號(hào)量Semphare：為控制具有有限數(shù)量的用戶(hù)資源而設(shè)計(jì)的，它允許多個(gè)線程在同一時(shí)刻去訪問(wèn)同一個(gè)資源，但一般需要限制同一時(shí)刻訪問(wèn)此資源的最大線程數(shù)目。
- 事件(信號(hào))，Wait/Notify：通過(guò)通知操作的方式來(lái)保持多線程同步，還可以方便的實(shí)現(xiàn)多線程優(yōu)先級(jí)的比較操作
4.進(jìn)程調(diào)度方法詳細(xì)介紹
批處理系統(tǒng)：
1.先來(lái)先服務(wù)
2.短作業(yè)優(yōu)先
3.高響應(yīng)比優(yōu)先
交互式系統(tǒng)
1.時(shí)間片輪轉(zhuǎn)算法
2.優(yōu)先級(jí)調(diào)度算法
3.多級(jí)反饋算法
5.頁(yè)面置換方法詳細(xì)介紹
1.（OPT）最佳置換算法
2.（FIFO）先進(jìn)先出算法
3.（LRU）最近最久未使用算法
class LRUCache{
public:
LRUCache(int capacity) {
cap = capacity;
}
int get(int key) {
auto it = m.find(key);
if (it == m.end()) return -1;
l.splice(l.begin(), l, it->second);
return it->second->second;
}
void put(int key, int value) {
auto it = m.find(key);
if (it != m.end()) l.erase(it->second);
l.push_front(make_pair(key, value));
m[key] = l.begin();
if (m.size() > cap) {
int k = l.rbegin()->first;
l.pop_back();
m.erase(k);
}
}
private:
int cap;
list<pair<int, int>> l;
unordered_map<int, list<pair<int, int>>::iterator> m;
};
6.請(qǐng)你說(shuō)一說(shuō)死鎖發(fā)生的條件以及如何解決死鎖
死鎖是指兩個(gè)或兩個(gè)以上進(jìn)程在執(zhí)行過(guò)程中，因爭(zhēng)奪資源而造成的下相互等待的現(xiàn)象。死鎖發(fā)生的四個(gè)必要條件：互斥、占有且等待、不可搶占、循環(huán)等待
解決死鎖的方法如下：
1.資源一次性分配，從而剝奪請(qǐng)求和保持條件
2.可剝奪資源：即當(dāng)進(jìn)程新的資源未得到滿足時(shí)，釋放已占有的資源，從而破壞不可剝奪的條件
3.資源有序分配法：系統(tǒng)給每類(lèi)資源賦予一個(gè)序號(hào)，每個(gè)進(jìn)程按編號(hào)遞增的請(qǐng)求資源，釋放則相反，從而破壞環(huán)路等待的條件
7.生產(chǎn)者消費(fèi)者問(wèn)題，讀者寫(xiě)者問(wèn)題
描述了一組生產(chǎn)者與一組消費(fèi)者，它們共享一個(gè)有界緩沖池，生產(chǎn)者向池中投入產(chǎn)品，消費(fèi)者從池中取得產(chǎn)品。假定緩沖池中有 N 個(gè)緩沖區(qū)，每個(gè)緩沖區(qū)只能存放一個(gè)類(lèi)型為 item 的產(chǎn)品，而所有的生產(chǎn)者和消費(fèi)者是相互等效的，則需要為該問(wèn)題設(shè)置三個(gè)信號(hào)量：互斥信號(hào)量 mutex，用于實(shí)現(xiàn)對(duì)緩沖池的互斥訪問(wèn)，其初值為 1；資源信號(hào)量 empty，用來(lái)表示空閑緩沖區(qū)的數(shù)量，其初值為 n；資源信號(hào)量 full，用來(lái)表示滿緩沖區(qū)的數(shù)量，即緩沖池中可供消費(fèi)的產(chǎn)品數(shù)量，其初值為 0。empty 和 full 用來(lái)同步生產(chǎn)者和消費(fèi)者進(jìn)程，即當(dāng)緩沖池全空時(shí)，消費(fèi)者進(jìn)程必須等待；緩沖池全滿時(shí)，生產(chǎn)者進(jìn)程必須等待。
int in = 0, out = 0;
Item buffer[N];
semaphore mutex, empty, full;//互斥信號(hào)量，資源信號(hào)量空和滿
void producer()
{
while(1)
{
produce an item nextp;
P(empty);//向空閑緩沖區(qū)信號(hào)量empty中申請(qǐng)一個(gè)，如果沒(méi)有，則阻塞該進(jìn)程；如果有，則繼續(xù)執(zhí)行
P(mutex);//臨界區(qū)資源需要使用互斥量，保證只有一個(gè)線程可以訪問(wèn)，避免多線程訪問(wèn)沖突。
buffer[in] = nextp;
in = (in + 1) % N;
V(mutex);//釋放一個(gè)信號(hào)量，臨界區(qū)訪問(wèn)結(jié)束
V(full);//滿緩沖區(qū)信號(hào)量full中加 1
}
}
void consumer()
{
while(1)
{
P(full);//向滿緩沖區(qū)信號(hào)量full申請(qǐng)一個(gè)，如果沒(méi)有，則阻塞該進(jìn)程；如果有，則繼續(xù)執(zhí)行
P(mutex);//同理，臨界區(qū)資源需要互斥訪問(wèn)
nextc = buffer[out];
out = (out + 1) % N;
V(mutex);
V(empty);//空閑緩沖區(qū)empty中加 1
consume the item in nextc
...
}
}
讀者寫(xiě)者問(wèn)題。讀寫(xiě)公平型偽代碼。
semaphore rw=1;//用于實(shí)現(xiàn)對(duì)文件的互斥訪問(wèn)
semaphore mutex=1;//用于實(shí)現(xiàn)對(duì)count 的互斥訪問(wèn)
semaphore w=1;//用于實(shí)現(xiàn)寫(xiě)優(yōu)先
int count=0;//用于記錄有多少個(gè)進(jìn)程同時(shí)在訪問(wèn)文件
writer()
{
while(1)
{
P(w);
P(rw);
寫(xiě)文件；
V(rw);
V(w);
}
}
reader()
{
while(1)
{
P(w);
P(mutex);
if(count==0)
P(rw);
count++;
V(mutex);
讀文件；
P(mutex);
count--;
if(count==0)
V(rw);
V(w);
}
}
8. Linux的4種鎖機(jī)制：
互斥鎖：mutex，用于保證在任何時(shí)刻，都只能有一個(gè)線程訪問(wèn)該對(duì)象。當(dāng)獲取鎖操作失敗時(shí)，線程會(huì)進(jìn)入睡眠，等待鎖釋放時(shí)被喚醒
讀寫(xiě)鎖：rwlock，分為讀鎖和寫(xiě)鎖。處于讀操作時(shí)，可以允許多個(gè)線程同時(shí)獲得讀操作。但是同一時(shí)刻只能有一個(gè)線程可以獲得寫(xiě)鎖。其它獲取寫(xiě)鎖失敗的線程都會(huì)進(jìn)入睡眠狀態(tài)，直到寫(xiě)鎖釋放時(shí)被喚醒。 注意：寫(xiě)鎖會(huì)阻塞其它讀寫(xiě)鎖。當(dāng)有一個(gè)線程獲得寫(xiě)鎖在寫(xiě)時(shí)，讀鎖也不能被其它線程獲??；寫(xiě)者優(yōu)先于讀者（一旦有寫(xiě)者，則后續(xù)讀者必須等待，喚醒時(shí)優(yōu)先考慮寫(xiě)者）。適用于讀取數(shù)據(jù)的頻率遠(yuǎn)遠(yuǎn)大于寫(xiě)數(shù)據(jù)的頻率的場(chǎng)合。
自旋鎖：spinlock，在任何時(shí)刻同樣只能有一個(gè)線程訪問(wèn)對(duì)象。但是當(dāng)獲取鎖操作失敗時(shí)，不會(huì)進(jìn)入睡眠，而是會(huì)在原地自旋，直到鎖被釋放。這樣節(jié)省了線程從睡眠狀態(tài)到被喚醒期間的消耗，在加鎖時(shí)間短暫的環(huán)境下會(huì)極大的提高效率。但如果加鎖時(shí)間過(guò)長(zhǎng)，則會(huì)非常浪費(fèi)CPU資源。
RCU：即read-copy-update，在修改數(shù)據(jù)時(shí)，首先需要讀取數(shù)據(jù)，然后生成一個(gè)副本，對(duì)副本進(jìn)行修改。修改完成后，再將老數(shù)據(jù)update成新的數(shù)據(jù)。使用RCU時(shí)，讀者幾乎不需要同步開(kāi)銷(xiāo)，既不需要獲得鎖，也不使用原子指令，不會(huì)導(dǎo)致鎖競(jìng)爭(zhēng)，因此就不用考慮死鎖問(wèn)題了。而對(duì)于寫(xiě)者的同步開(kāi)銷(xiāo)較大，它需要復(fù)制被修改的數(shù)據(jù)，還必須使用鎖機(jī)制同步并行其它寫(xiě)者的修改操作。在有大量讀操作，少量寫(xiě)操作的情況下效率非常高。
9.請(qǐng)你來(lái)介紹一下5種IO模型
1.阻塞IO:調(diào)用者調(diào)用了某個(gè)函數(shù)，等待這個(gè)函數(shù)返回，期間什么也不做，不停的去檢查這個(gè)函數(shù)有沒(méi)有返回，必須等這個(gè)函數(shù)返回才能進(jìn)行下一步動(dòng)作
2.非阻塞IO:非阻塞等待，每隔一段時(shí)間就去檢測(cè)IO事件是否就緒。沒(méi)有就緒就可以做其他事。
3.信號(hào)驅(qū)動(dòng)IO:信號(hào)驅(qū)動(dòng)IO:linux用套接口進(jìn)行信號(hào)驅(qū)動(dòng)IO，安裝一個(gè)信號(hào)處理函數(shù)，進(jìn)程繼續(xù)運(yùn)行并不阻塞，當(dāng)IO時(shí)間就緒，進(jìn)程收到SIGIO信號(hào)。然后處理IO事件。
4.IO復(fù)用/多路轉(zhuǎn)接IO:linux用 select/poll 函數(shù)實(shí)現(xiàn)IO復(fù)用模型，這兩個(gè)函數(shù)也會(huì)使進(jìn)程阻塞，但是和阻塞IO所不同的是這兩個(gè)函數(shù)可以同時(shí)阻塞多個(gè)IO操作。而且可以同時(shí)對(duì)多個(gè)讀操作、寫(xiě)操作的IO函數(shù)進(jìn)行檢測(cè)。知道有數(shù)據(jù)可讀或可寫(xiě)時(shí)，才真正調(diào)用IO操作函數(shù)
5.異步IO:linux中，可以調(diào)用aio_read函數(shù)告訴內(nèi)核描述字緩沖區(qū)指針和緩沖區(qū)的大小、文件偏移及通知的方式，然后立即返回，當(dāng)內(nèi)核將數(shù)據(jù)拷貝到緩沖區(qū)后，再通知應(yīng)用程序。
同步、異步
同步：用戶(hù)進(jìn)程發(fā)起IO后，進(jìn)行就緒判斷，輪詢(xún)內(nèi)核狀態(tài)。
異步：用戶(hù)進(jìn)程發(fā)起IO后，可以做其他事情，等待內(nèi)核通知。
阻塞、非阻塞
阻塞：用戶(hù)進(jìn)程訪問(wèn)數(shù)據(jù)時(shí)，如果未完成IO，調(diào)用的進(jìn)程一直處于等待狀態(tài)，直到IO操作完成。
非阻塞：用戶(hù)進(jìn)程訪問(wèn)數(shù)據(jù)時(shí)，會(huì)馬上返回一個(gè)狀態(tài)值，無(wú)論是否完成，此時(shí)進(jìn)程可以操作其他事情。
select,poll,epoll的區(qū)別
1.select
是最初解決IO阻塞問(wèn)題的方法。用結(jié)構(gòu)體fd_set來(lái)告訴內(nèi)核監(jiān)聽(tīng)多個(gè)文件描述符，該結(jié)構(gòu)體被稱(chēng)為描述符集。由數(shù)組來(lái)維持哪些描述符被置位了。對(duì)結(jié)構(gòu)體的操作封裝在三個(gè)宏定義中。通過(guò)輪尋來(lái)查找是否有描述符要被處理。
存在的問(wèn)題：
內(nèi)置數(shù)組的形式使得select的最大文件數(shù)受限與FD_SIZE；
每次調(diào)用select前都要重新初始化描述符集，將fd從用戶(hù)態(tài)拷貝到內(nèi)核態(tài)，每次調(diào)用select后，都需要將fd從內(nèi)核態(tài)拷貝到用戶(hù)態(tài)；
輪尋排查當(dāng)文件描述符個(gè)數(shù)很多時(shí)，效率很低；
2.poll
poll：通過(guò)一個(gè)可變長(zhǎng)度的數(shù)組解決了select文件描述符受限的問(wèn)題。數(shù)組中元素是結(jié)構(gòu)體，該結(jié)構(gòu)體保存描述符的信息，每增加一個(gè)文件描述符就向數(shù)組中加入一個(gè)結(jié)構(gòu)體，結(jié)構(gòu)體只需要拷貝一次到內(nèi)核態(tài)。poll解決了select重復(fù)初始化的問(wèn)題。輪尋排查的問(wèn)題未解決。
3.epoll
epoll：輪尋排查所有文件描述符的效率不高，使服務(wù)器并發(fā)能力受限。因此，epoll采用只返回狀態(tài)發(fā)生變化的文件描述符，便解決了輪尋的瓶頸。
epoll對(duì)文件描述符的操作有兩種模式：LT（level trigger）和ET（edge trigger）。LT模式是默認(rèn)模式
- LT模式
LT(level triggered)是缺省的工作方式，并且同時(shí)支持block和no-block socket.在這種做法中，內(nèi)核告訴你一個(gè)文件描述符是否就緒了，然后你可以對(duì)這個(gè)就緒的fd進(jìn)行IO操作。如果你不作任何操作，內(nèi)核還是會(huì)繼續(xù)通知你的。
- ET模式
ET(edge-triggered)是高速工作方式，只支持no-block socket。在這種模式下，當(dāng)描述符從未就緒變?yōu)榫途w時(shí)，內(nèi)核通過(guò)epoll告訴你。然后它會(huì)假設(shè)你知道文件描述符已經(jīng)就緒，并且不會(huì)再為那個(gè)文件描述符發(fā)送更多的就緒通知，直到你做了某些操作導(dǎo)致那個(gè)文件描述符不再為就緒狀態(tài)了(比如，你在發(fā)送，接收或者接收請(qǐng)求，或者發(fā)送接收的數(shù)據(jù)少于一定量時(shí)導(dǎo)致了一個(gè)EWOULDBLOCK 錯(cuò)誤）。但是請(qǐng)注意，如果一直不對(duì)這個(gè)fd作IO操作(從而導(dǎo)致它再次變成未就緒)，內(nèi)核不會(huì)發(fā)送更多的通知(only once)
ET模式在很大程度上減少了epoll事件被重復(fù)觸發(fā)的次數(shù)，因此效率要比LT模式高。epoll工作在ET模式的時(shí)候，必須使用非阻塞套接口，以避免由于一個(gè)文件句柄的阻塞讀/阻塞寫(xiě)操作把處理多個(gè)文件描述符的任務(wù)餓死。
3、LT模式與ET模式的區(qū)別如下：
LT模式：當(dāng)epoll_wait檢測(cè)到描述符事件發(fā)生并將此事件通知應(yīng)用程序，應(yīng)用程序可以不立即處理該事件。下次調(diào)用epoll_wait時(shí)，會(huì)再次響應(yīng)應(yīng)用程序并通知此事件。
ET模式：當(dāng)epoll_wait檢測(cè)到描述符事件發(fā)生并將此事件通知應(yīng)用程序，應(yīng)用程序必須立即處理該事件。如果不處理，下次調(diào)用epoll_wait時(shí)，不會(huì)再次響應(yīng)應(yīng)用程序并通知此事件。
