磁碟調度演算法的模擬

⑴ 一篇文章帶你深度解析python線程和進程

使用Python中的線程模塊，能夠同時運行程序的不同部分，並簡化設計。如果你已經入門Python，並且想用線程來提升程序運行速度的話，希望這篇教程會對你有所幫助。

線程與進程

什麼是進程

進程是系統進行資源分配和調度的一個獨立單位 進程是具有一定獨立功能的程序關於某個數據集合上的一次運行活動,進程是系統進行資源分配和調度的一個獨立單位。每個進程都有自己的獨立內存空間，不同進程通過進程間通信來通信。由於進程比較重量，占據獨立的內存，所以上下文進程間的切換開銷（棧、寄存器、虛擬內存、文件句柄等）比較大，但相對比較穩定安全。

什麼是線程

CPU調度和分派的基本單位 線程是進程的一個實體，是CPU調度和分派的基本單位,它是比進程更小的能獨立運行的基本單位.線程自己基本上不擁有系統資源,只擁有一點在運行中必不可少的資源(如程序計數器,一組寄存器和棧),但是它可與同屬一個進程的其他的線程共享進程所擁有的全部資源。線程間通信主要通過共享內存，上下文切換很快，資源開銷較少，但相比進程不夠穩定容易丟失數據。

進程與線程的關系圖

線程與進程的區別：

進程

現實生活中，有很多的場景中的事情是同時進行的，比如開車的時候 手和腳共同來駕駛 汽車 ，比如唱歌跳舞也是同時進行的，再比如邊吃飯邊打電話；試想如果我們吃飯的時候有一個領導來電，我們肯定是立刻就接聽了。但是如果你吃完飯再接聽或者回電話，很可能會被開除。

注意：

多任務的概念

什麼叫 多任務 呢？簡單地說，就是操作系統可以同時運行多個任務。打個比方，你一邊在用瀏覽器上網，一邊在聽MP3，一邊在用Word趕作業，這就是多任務，至少同時有3個任務正在運行。還有很多任務悄悄地在後台同時運行著，只是桌面上沒有顯示而已。

現在，多核CPU已經非常普及了，但是，即使過去的單核CPU，也可以執行多任務。由於CPU執行代碼都是順序執行的，那麼，單核CPU是怎麼執行多任務的呢？

答案就是操作系統輪流讓各個任務交替執行，任務1執行0.01秒，切換到任務2，任務2執行0.01秒，再切換到任務3，執行0.01秒，這樣反復執行下去。表面上看，每個任務都是交替執行的，但是，由於CPU的執行速度實在是太快了，我們感覺就像所有任務都在同時執行一樣。

真正的並行執行多任務只能在多核CPU上實現，但是，由於任務數量遠遠多於CPU的核心數量，所以，操作系統也會自動把很多任務輪流調度到每個核心上執行。 其實就是CPU執行速度太快啦！以至於我們感受不到在輪流調度。

並行與並發

並行（Parallelism）

並行：指兩個或兩個以上事件（或線程）在同一時刻發生，是真正意義上的不同事件或線程在同一時刻，在不同CPU資源呢上（多核），同時執行。

特點

並發（Concurrency）

指一個物理CPU(也可以多個物理CPU) 在若幹道程序（或線程）之間多路復用，並發性是對有限物理資源強制行使多用戶共享以提高效率。

特點

multiprocess.Process模塊

process模塊是一個創建進程的模塊，藉助這個模塊，就可以完成進程的創建。

語法：Process([group [, target [, name [, args [, kwargs]]]]])

由該類實例化得到的對象，表示一個子進程中的任務（尚未啟動）。

注意：1. 必須使用關鍵字方式來指定參數；2. args指定的為傳給target函數的位置參數，是一個元祖形式，必須有逗號。

參數介紹：

group：參數未使用，默認值為None。

target：表示調用對象，即子進程要執行的任務。

args：表示調用的位置參數元祖。

kwargs：表示調用對象的字典。如kwargs = {'name':Jack, 'age':18}。

name：子進程名稱。

代碼：

除了上面這些開啟進程的方法之外，還有一種以繼承Process的方式開啟進程的方式：

通過上面的研究，我們千方百計實現了程序的非同步，讓多個任務可以同時在幾個進程中並發處理，他們之間的運行沒有順序，一旦開啟也不受我們控制。盡管並發編程讓我們能更加充分的利用IO資源，但是也給我們帶來了新的問題。

當多個進程使用同一份數據資源的時候，就會引發數據安全或順序混亂問題，我們可以考慮加鎖，我們以模擬搶票為例，來看看數據安全的重要性。

加鎖可以保證多個進程修改同一塊數據時，同一時間只能有一個任務可以進行修改，即串列的修改。加鎖犧牲了速度，但是卻保證了數據的安全。

因此我們最好找尋一種解決方案能夠兼顧：1、效率高（多個進程共享一塊內存的數據）2、幫我們處理好鎖問題。

mutiprocessing模塊為我們提供的基於消息的IPC通信機制：隊列和管道。隊列和管道都是將數據存放於內存中 隊列又是基於（管道+鎖）實現的，可以讓我們從復雜的鎖問題中解脫出來， 我們應該盡量避免使用共享數據，盡可能使用消息傳遞和隊列，避免處理復雜的同步和鎖問題，而且在進程數目增多時，往往可以獲得更好的可獲展性（ 後續擴展該內容 ）。

線程

Python的threading模塊

Python 供了幾個用於多線程編程的模塊，包括 thread, threading 和 Queue 等。thread 和 threading 模塊允許程序員創建和管理線程。thread 模塊 供了基本的線程和鎖的支持，而 threading 供了更高級別，功能更強的線程管理的功能。Queue 模塊允許用戶創建一個可以用於多個線程之間 共享數據的隊列數據結構。

python創建和執行線程

創建線程代碼

1. 創建方法一:

2. 創建方法二:

進程和線程都是實現多任務的一種方式，例如：在同一台計算機上能同時運行多個QQ（進程),一個QQ可以打開多個聊天窗口（線程）。資源共享：進程不能共享資源，而線程共享所在進程的地址空間和其他資源，同時，線程有自己的棧和棧指針。所以在一個進程內的所有線程共享全局變數，但多線程對全局變數的更改會導致變數值得混亂。

代碼演示:

得到的結果是：

首先需要明確的一點是GIL並不是Python的特性，它是在實現Python解析器(CPython)時所引入的一個概念。就好比C++是一套語言（語法）標准，但是可以用不同的編譯器來編譯成可執行代碼。同樣一段代碼可以通過CPython，PyPy，Psyco等不同的Python執行環境來執行（其中的JPython就沒有GIL）。

那麼CPython實現中的GIL又是什麼呢？GIL全稱Global Interpreter Lock為了避免誤導，我們還是來看一下官方給出的解釋：

主要意思為:

因此，解釋器實際上被一個全局解釋器鎖保護著，它確保任何時候都只有一個Python線程執行。在多線程環境中，Python 虛擬機按以下方式執行:

由於GIL的存在，Python的多線程不能稱之為嚴格的多線程。因為 多線程下每個線程在執行的過程中都需要先獲取GIL，保證同一時刻只有一個線程在運行。

由於GIL的存在，即使是多線程，事實上同一時刻只能保證一個線程在運行， 既然這樣多線程的運行效率不就和單線程一樣了嗎，那為什麼還要使用多線程呢？

由於以前的電腦基本都是單核CPU，多線程和單線程幾乎看不出差別，可是由於計算機的迅速發展，現在的電腦幾乎都是多核CPU了，最少也是兩個核心數的，這時差別就出來了：通過之前的案例我們已經知道，即使在多核CPU中，多線程同一時刻也只有一個線程在運行，這樣不僅不能利用多核CPU的優勢，反而由於每個線程在多個CPU上是交替執行的，導致在不同CPU上切換時造成資源的浪費，反而會更慢。即原因是一個進程只存在一把gil鎖，當在執行多個線程時，內部會爭搶gil鎖，這會造成當某一個線程沒有搶到鎖的時候會讓cpu等待，進而不能合理利用多核cpu資源。

但是在使用多線程抓取網頁內容時，遇到IO阻塞時，正在執行的線程會暫時釋放GIL鎖，這時其它線程會利用這個空隙時間，執行自己的代碼，因此多線程抓取比單線程抓取性能要好，所以我們還是要使用多線程的。

GIL對多線程Python程序的影響

程序的性能受到計算密集型(CPU)的程序限制和I/O密集型的程序限制影響,那什麼是計算密集型和I/O密集型程序呢?

計算密集型：要進行大量的數值計算，例如進行上億的數字計算、計算圓周率、對視頻進行高清解碼等等。這種計算密集型任務雖然也可以用多任務完成，但是花費的主要時間在任務切換的時間，此時CPU執行任務的效率比較低。

IO密集型：涉及到網路請求(time.sleep())、磁碟IO的任務都是IO密集型任務，這類任務的特點是CPU消耗很少，任務的大部分時間都在等待IO操作完成（因為IO的速度遠遠低於CPU和內存的速度）。對於IO密集型任務，任務越多，CPU效率越高，但也有一個限度。

當然為了避免GIL對我們程序產生影響，我們也可以使用，線程鎖。

Lock&RLock

常用的資源共享鎖機制：有Lock、RLock、Semphore、Condition等，簡單給大家分享下Lock和RLock。

Lock

特點就是執行速度慢，但是保證了數據的安全性

RLock

使用鎖代碼操作不當就會產生死鎖的情況。

什麼是死鎖

死鎖：當線程A持有獨占鎖a，並嘗試去獲取獨占鎖b的同時，線程B持有獨占鎖b，並嘗試獲取獨占鎖a的情況下，就會發生AB兩個線程由於互相持有對方需要的鎖，而發生的阻塞現象，我們稱為死鎖。即死鎖是指多個進程因競爭資源而造成的一種僵局，若無外力作用，這些進程都將無法向前推進。

所以，在系統設計、進程調度等方面注意如何不讓這四個必要條件成立，如何確定資源的合理分配演算法，避免進程永久占據系統資源。

死鎖代碼

python線程間通信

如果各個線程之間各干各的，確實不需要通信，這樣的代碼也十分的簡單。但這一般是不可能的，至少線程要和主線程進行通信，不然計算結果等內容無法取回。而實際情況中要復雜的多，多個線程間需要交換數據，才能得到正確的執行結果。

python中Queue是消息隊列，提供線程間通信機制，python3中重名為為queue，queue模塊塊下提供了幾個阻塞隊列，這些隊列主要用於實現線程通信。

在 queue 模塊下主要提供了三個類，分別代表三種隊列，它們的主要區別就在於進隊列、出隊列的不同。

簡單代碼演示

此時代碼會阻塞，因為queue中內容已滿，此時可以在第四個queue.put('蘋果')後面添加timeout，則成為 queue.put('蘋果'，timeout=1)如果等待1秒鍾仍然是滿的就會拋出異常，可以捕獲異常。

同理如果隊列是空的，無法獲取到內容默認也會阻塞，如果不阻塞可以使用queue.get_nowait()。

在掌握了 Queue 阻塞隊列的特性之後，在下面程序中就可以利用 Queue 來實現線程通信了。

下面演示一個生產者和一個消費者，當然都可以多個

使用queue模塊，可在線程間進行通信，並保證了線程安全。

協程

協程，又稱微線程，纖程。英文名Coroutine。

協程是python個中另外一種實現多任務的方式，只不過比線程更小佔用更小執行單元（理解為需要的資源）。為啥說它是一個執行單元，因為它自帶CPU上下文。這樣只要在合適的時機， 我們可以把一個協程 切換到另一個協程。只要這個過程中保存或恢復 CPU上下文那麼程序還是可以運行的。

通俗的理解：在一個線程中的某個函數，可以在任何地方保存當前函數的一些臨時變數等信息，然後切換到另外一個函數中執行，注意不是通過調用函數的方式做到的，並且切換的次數以及什麼時候再切換到原來的函數都由開發者自己確定。

在實現多任務時，線程切換從系統層面遠不止保存和恢復 CPU上下文這么簡單。操作系統為了程序運行的高效性每個線程都有自己緩存Cache等等數據，操作系統還會幫你做這些數據的恢復操作。所以線程的切換非常耗性能。但是協程的切換只是單純的操作CPU的上下文，所以一秒鍾切換個上百萬次系統都抗的住。

greenlet與gevent

為了更好使用協程來完成多任務，除了使用原生的yield完成模擬協程的工作，其實python還有的greenlet模塊和gevent模塊，使實現協程變的更加簡單高效。

greenlet雖說實現了協程，但需要我們手工切換，太麻煩了，gevent是比greenlet更強大的並且能夠自動切換任務的模塊。

其原理是當一個greenlet遇到IO(指的是input output 輸入輸出，比如網路、文件操作等)操作時，比如訪問網路，就自動切換到其他的greenlet，等到IO操作完成，再在適當的時候切換回來繼續執行。

模擬耗時操作：

如果有耗時操作也可以換成，gevent中自己實現的模塊，這時候就需要打補丁了。

使用協程完成一個簡單的二手房信息的爬蟲代碼吧！

以下文章來源於Python專欄 ，作者宋宋

文章鏈接：https://mp.weixin.qq.com/s/2r3_ipU3HjdA5VnqSHjUnQ

⑵ 主存空間的分配和回收，

#include "iostream.h"
#include "iomanip.h"

#define nofreearea 2
#define noadequacyarea 3
#define allocated 4

#define noprocess 2
#define nosuchprocess 3
#define reclaimed 4

typedef struct TUN
{
int address;
int size;
char name;
struct TUN *next;
} usedarea , *usedtable;

typedef struct TFN
{
int address;
int size;
struct TFN *next;
} freearea, *freetable;

usedtable usedTable = NULL;
freetable freeTable = NULL;

int alloc( char processname , int processsize )
{

if( freeTable == NULL )
return 1;
freetable p = freeTable;
freetable q = p;

while( p != NULL && p->size < processsize )
{
q = p;
p = p->next;
}

if( p == NULL )
return 3;

usedtable x = new usedarea;
x->address = p->address;
x->size = processsize;
x->name = processname;
x->next = NULL;

if( p->size > processsize )
{
p->size -= processsize;
p->address += processsize;
}

else
{
if( p == freeTable )
freeTable = NULL;
else
q->next = p->next;
delete p;
}

usedtable r = usedTable;
usedtable t = r;

while( r != NULL && r->address < x->address )
{
t = r;
r = r->next;
}

if( usedTable == NULL )
usedTable = x;
else
{
x->next = r;
t->next = x;
}

return 4;
}

int Reclaim( char processname )
{
if( usedTable == NULL )
return 1;
usedtable p = usedTable;
usedtable q = p;
while( p != NULL && p->name != processname )
{
q = p;
p = p->next;
}

if( p == NULL )
return 3;

freetable r = freeTable;
freetable t = r;
freetable x;
while( r != NULL && r->address < p->address )
{
t = r;
r = r->next;
}

x = new freearea;
x->address = p->address;
x->size = p->size;
x->next = NULL;

if( r == freeTable )
{
x->next = r;
freeTable = x;
t = freeTable;
}
else
{
x->next = r;
t->next = x;
}

while( t->next != NULL && t->address + t->size == t->next->address )
{
t->size += t->next->size;
r = t->next;
t->next = t->next->next;
delete r;
}

if( p == usedTable )
{
usedTable = usedTable->next;
}
else
q->next = p->next;
delete p;

return 4;
}

int Init()
{
freeTable = new freearea;
freeTable->address = 0;
freeTable->size = 128;
freeTable->next = NULL;
return 1;
}

void processrequest()
{
char processname;
int processsize;
cout<<"...................."<<endl;
cout<<"作業名: ";
cin >> processname;
cout<<"作業長度: ";
cin >> processsize;
if(processsize<=128)
{int i;
if( alloc( processname , processsize) == 4 )
{
i=i+processsize;
if(i>128)
{cout<<"該作業超出空間"<<endl;
}
if(i<=128)
cout<<"該作業已成功獲得所需空間"<<endl;
i=i+processsize;
cout<<"........................................"<<endl;

}
else
cout<<"該作業超出空間,沒有獲得所需空間"<<endl;
cout<<"........................................"<<endl;
return;
}
if(processsize>128)
{cout<<"該作業超出空間"<<endl;
cout<<"........................................"<<endl;
}

}

void processreclaim()
{
int processname;
cout<<"...................."<<endl;
cout<<"作業名: ";
cin >>processname;
int result = Reclaim( processname );
if( result == 4 )
cout<<"該作業已成功回收"<<endl;
else if( result == 2 || result == 1 )
cout<<"系統沒有作業或該作業不存在"<<endl;
cout<<"...................."<<endl;

}

void freeTablePrint()
{
cout<<endl<<endl<<endl<<"***********************************"<<endl;
cout<<setw(10)<<"address"<<setw(10)<<"length"<<setw(10)<<"state"<<endl<<endl;
freetable p = freeTable;
usedtable q = usedTable;
int x , y;
while( p || q )
{
if( p )
x = p->address;
else
x = 0x7fffffff;
if( q )
y = q->address;
else
y = 0x7fffffff;

if( x < y )
{
cout<<setw(10)<<p->address<<setw(10)<<p->size<<setw(10)<<"空閑"<<endl;
p = p->next;
}
if( x > y )
{
cout<<setw(10)<<q->address<<setw(10)<<q->size<<setw(10)<<"已分配"<<setw(10)<<"ID="<<q->name<<endl;
q = q->next;
}
}
cout<<endl<<endl<<endl<<"************************************"<<endl<<endl<<endl;

}

void main()
{
Init();
int choose;
bool exitFlag = false;
while( !exitFlag )
{

cout<<"************************0 - 退出 ************************"<<endl;
cout<<"************************1 - 分配主存 ************************"<<endl;
cout<<"************************2 - 回收主存 ************************"<<endl;
cout<<"************************3 - 顯示主存 ************************"<<endl<<endl<<endl;
cout<<"************************選擇所要執行的操作:";
cin>>choose;
switch( choose )
{
case 0:
exitFlag = true;
break;
case 1:
processrequest();
break;
case 2:
processreclaim();
break;
case 3:
freeTablePrint();
break;
}
}
}

⑶ hadoop的maprece常見演算法案例有幾種

基本MapRece模式

計數與求和
問題陳述:
有許多文檔，每個文檔都有一些欄位組成。需要計算出每個欄位在所有文檔中的出現次數或者這些欄位的其他什麼統計值。例如，給定一個log文件，其中的每條記錄都包含一個響應時間，需要計算出平均響應時間。
解決方案:
讓我們先從簡單的例子入手。在下面的代碼片段里，Mapper每遇到指定詞就把頻次記1，Recer一個個遍歷這些詞的集合然後把他們的頻次加和。

1 class Mapper
2 method Map(docid id, doc d)
3 for all term t in doc d do
4 Emit(term t, count 1)
5
6 class Recer
7 method Rece(term t, counts [c1, c2,...])
8 sum = 0
9 for all count c in [c1, c2,...] do
10 sum = sum + c
11 Emit(term t, count sum)

這種方法的缺點顯而易見，Mapper提交了太多無意義的計數。它完全可以通過先對每個文檔中的詞進行計數從而減少傳遞給Recer的數據量:

1 class Mapper
2 method Map(docid id, doc d)
3 H = new AssociativeArray
4 for all term t in doc d do
5 H{t} = H{t} + 1
6 for all term t in H do
7 Emit(term t, count H{t})

如果要累計計數的的不只是單個文檔中的內容，還包括了一個Mapper節點處理的所有文檔，那就要用到Combiner了:

1 class Mapper
2 method Map(docid id, doc d)
3 for all term t in doc d do
4 Emit(term t, count 1)
5
6 class Combiner
7 method Combine(term t, [c1, c2,...])
8 sum = 0
9 for all count c in [c1, c2,...] do
10 sum = sum + c
11 Emit(term t, count sum)
12
13 class Recer
14 method Rece(term t, counts [c1, c2,...])
15 sum = 0
16 for all count c in [c1, c2,...] do
17 sum = sum + c
18 Emit(term t, count sum)

應用：Log 分析, 數據查詢

整理歸類

問題陳述:
有一系列條目，每個條目都有幾個屬性，要把具有同一屬性值的條目都保存在一個文件里，或者把條目按照屬性值分組。 最典型的應用是倒排索引。
解決方案：
解決方案很簡單。 在 Mapper 中以每個條目的所需屬性值作為 key，其本身作為值傳遞給 Recer。 Recer 取得按照屬性值分組的條目，然後可以處理或者保存。如果是在構建倒排索引，那麼 每個條目相當於一個詞而屬性值就是詞所在的文檔ID。
應用：倒排索引， ETL
過濾 (文本查找)，解析和校驗
問題陳述:
假設有很多條記錄，需要從其中找出滿足某個條件的所有記錄，或者將每條記錄傳換成另外一種形式（轉換操作相對於各條記錄獨立，即對一條記錄的操作與其他記錄無關）。像文本解析、特定值抽取、格式轉換等都屬於後一種用例。
解決方案:
非常簡單，在Mapper 里逐條進行操作，輸出需要的值或轉換後的形式。
應用：日誌分析，數據查詢，ETL，數據校驗

分布式任務執行

問題陳述:
大型計算可以分解為多個部分分別進行然後合並各個計算的結果以獲得最終結果。
解決方案: 將數據切分成多份作為每個 Mapper 的輸入，每個Mapper處理一份數據，執行同樣的運算，產生結果，Recer把多個Mapper的結果組合成一個。
案例研究： 數字通信系統模擬
像 WiMAX 這樣的數字通信模擬軟體通過系統模型來傳輸大量的隨機數據，然後計算傳輸中的錯誤幾率。 每個 Mapper 處理樣本 1/N 的數據，計算出這部分數據的錯誤率，然後在 Recer 里計算平均錯誤率。
應用：工程模擬，數字分析，性能測試
排序
問題陳述:
有許多條記錄，需要按照某種規則將所有記錄排序或是按照順序來處理記錄。
解決方案: 簡單排序很好辦 – Mappers 將待排序的屬性值為鍵，整條記錄為值輸出。 不過實際應用中的排序要更加巧妙一點， 這就是它之所以被稱為MapRece 核心的原因（「核心」是說排序？因為證明Hadoop計算能力的實驗是大數據排序？還是說Hadoop的處理過程中對key排序的環節？）。在實踐中，常用組合鍵來實現二次排序和分組。
MapRece 最初只能夠對鍵排序， 但是也有技術利用可以利用Hadoop 的特性來實現按值排序。想了解的話可以看這篇博客。
按照BigTable的概念，使用 MapRece來對最初數據而非中間數據排序，也即保持數據的有序狀態更有好處，必須注意這一點。換句話說，在數據插入時排序一次要比在每次查詢數據的時候排序更高效。
應用：ETL，數據分析

非基本 MapRece 模式

迭代消息傳遞 (圖處理)

問題陳述：
假設一個實體網路，實體之間存在著關系。 需要按照與它比鄰的其他實體的屬性計算出一個狀態。這個狀態可以表現為它和其它節點之間的距離， 存在特定屬性的鄰接點的跡象， 鄰域密度特徵等等。
解決方案：
網路存儲為系列節點的結合，每個節點包含有其所有鄰接點ID的列表。按照這個概念，MapRece 迭代進行，每次迭代中每個節點都發消息給它的鄰接點。鄰接點根據接收到的信息更新自己的狀態。當滿足了某些條件的時候迭代停止，如達到了最大迭代次數（網路半徑）或兩次連續的迭代幾乎沒有狀態改變。從技術上來看，Mapper 以每個鄰接點的ID為鍵發出信息，所有的信息都會按照接受節點分組，recer 就能夠重算各節點的狀態然後更新那些狀態改變了的節點。下面展示了這個演算法：

1 class Mapper
2 method Map(id n, object N)
3 Emit(id n, object N)
4 for all id m in N.OutgoingRelations do
5 Emit(id m, message getMessage(N))
6
7 class Recer
8 method Rece(id m, [s1, s2,...])
9 M = null
10 messages = []
11 for all s in [s1, s2,...] do
12 if IsObject(s) then
13 M = s
14 else // s is a message
15 messages.add(s)
16 M.State = calculateState(messages)
17 Emit(id m, item M)

一個節點的狀態可以迅速的沿著網路傳全網，那些被感染了的節點又去感染它們的鄰居，整個過程就像下面的圖示一樣：

案例研究： 沿分類樹的有效性傳遞
問題陳述：
這個問題來自於真實的電子商務應用。將各種貨物分類，這些類別可以組成一個樹形結構，比較大的分類（像男人、女人、兒童）可以再分出小分類（像男褲或女裝），直到不能再分為止（像男式藍色牛仔褲）。這些不能再分的基層類別可以是有效（這個類別包含有貨品）或者已無效的（沒有屬於這個分類的貨品）。如果一個分類至少含有一個有效的子分類那麼認為這個分類也是有效的。我們需要在已知一些基層分類有效的情況下找出分類樹上所有有效的分類。
解決方案：
這個問題可以用上一節提到的框架來解決。我們咋下面定義了名為 getMessage和 calculateState 的方法：

1 class N
2 State in {True = 2, False = 1, null = 0},
3 initialized 1 or 2 for end-of-line categories, 0 otherwise
4 method getMessage(object N)
5 return N.State
6 method calculateState(state s, data [d1, d2,...])
7 return max( [d1, d2,...] )

案例研究：廣度優先搜索
問題陳述：需要計算出一個圖結構中某一個節點到其它所有節點的距離。
解決方案： Source源節點給所有鄰接點發出值為0的信號，鄰接點把收到的信號再轉發給自己的鄰接點，每轉發一次就對信號值加1：

1 class N
2 State is distance,
3 initialized 0 for source node, INFINITY for all other nodes
4 method getMessage(N)
5 return N.State + 1
6 method calculateState(state s, data [d1, d2,...])
7 min( [d1, d2,...] )

案例研究：網頁排名和 Mapper 端數據聚合
這個演算法由Google提出，使用權威的PageRank演算法，通過連接到一個網頁的其他網頁來計算網頁的相關性。真實演算法是相當復雜的，但是核心思想是權重可以傳播，也即通過一個節點的各聯接節點的權重的均值來計算節點自身的權重。

1 class N
2 State is PageRank
3 method getMessage(object N)
4 return N.State / N.OutgoingRelations.size()
5 method calculateState(state s, data [d1, d2,...])
6 return ( sum([d1, d2,...]) )

要指出的是上面用一個數值來作為評分實際上是一種簡化，在實際情況下，我們需要在Mapper端來進行聚合計算得出這個值。下面的代碼片段展示了這個改變後的邏輯 （針對於 PageRank 演算法）：

1 class Mapper
2 method Initialize
3 H = new AssociativeArray
4 method Map(id n, object N)
5 p = N.PageRank / N.OutgoingRelations.size()
6 Emit(id n, object N)
7 for all id m in N.OutgoingRelations do
8 H{m} = H{m} + p
9 method Close
10 for all id n in H do
11 Emit(id n, value H{n})
12
13 class Recer
14 method Rece(id m, [s1, s2,...])
15 M = null
16 p = 0
17 for all s in [s1, s2,...] do
18 if IsObject(s) then
19 M = s
20 else
21 p = p + s
22 M.PageRank = p
23 Emit(id m, item M)

應用：圖分析，網頁索引

值去重 （對唯一項計數）
問題陳述: 記錄包含值域F和值域 G，要分別統計相同G值的記錄中不同的F值的數目 (相當於按照 G分組).
這個問題可以推而廣之應用於分面搜索（某些電子商務網站稱之為Narrow Search）
Record 1: F=1, G={a, b}
Record 2: F=2, G={a, d, e}
Record 3: F=1, G={b}
Record 4: F=3, G={a, b}

Result:
a -> 3 // F=1, F=2, F=3
b -> 2 // F=1, F=3
d -> 1 // F=2
e -> 1 // F=2

解決方案 I:
第一種方法是分兩個階段來解決這個問題。第一階段在Mapper中使用F和G組成一個復合值對，然後在Recer中輸出每個值對，目的是為了保證F值的唯一性。在第二階段，再將值對按照G值來分組計算每組中的條目數。
第一階段：

1 class Mapper
2 method Map(null, record [value f, categories [g1, g2,...]])
3 for all category g in [g1, g2,...]
4 Emit(record [g, f], count 1)
5
6 class Recer
7 method Rece(record [g, f], counts [n1, n2, ...])
8 Emit(record [g, f], null )

第二階段：

1 class Mapper
2 method Map(record [f, g], null)
3 Emit(value g, count 1)
4
5 class Recer
6 method Rece(value g, counts [n1, n2,...])
7 Emit(value g, sum( [n1, n2,...] ) )

解決方案 II:
第二種方法只需要一次MapRece 即可實現，但擴展性不強。演算法很簡單-Mapper 輸出值和分類，在Recer里為每個值對應的分類去重然後給每個所屬的分類計數加1，最後再在Recer結束後將所有計數加和。這種方法適用於只有有限個分類，而且擁有相同F值的記錄不是很多的情況。例如網路日誌處理和用戶分類，用戶的總數很多，但是每個用戶的事件是有限的，以此分類得到的類別也是有限的。值得一提的是在這種模式下可以在數據傳輸到Recer之前使用Combiner來去除分類的重復值。

1 class Mapper
2 method Map(null, record [value f, categories [g1, g2,...] )
3 for all category g in [g1, g2,...]
4 Emit(value f, category g)
5
6 class Recer
7 method Initialize
8 H = new AssociativeArray : category -> count
9 method Rece(value f, categories [g1, g2,...])
10 [g1', g2',..] = ExcludeDuplicates( [g1, g2,..] )
11 for all category g in [g1', g2',...]
12 H{g} = H{g} + 1
13 method Close
14 for all category g in H do
15 Emit(category g, count H{g})

應用：日誌分析，用戶計數
互相關
問題陳述：有多個各由若干項構成的組，計算項兩兩共同出現於一個組中的次數。假如項數是N，那麼應該計算N*N。
這種情況常見於文本分析（條目是單詞而元組是句子），市場分析（購買了此物的客戶還可能購買什麼）。如果N*N小到可以容納於一台機器的內存，實現起來就比較簡單了。
配對法
第一種方法是在Mapper中給所有條目配對，然後在Recer中將同一條目對的計數加和。但這種做法也有缺點：
使用 combiners 帶來的的好處有限，因為很可能所有項對都是唯一的
不能有效利用內存

1 class Mapper
2 method Map(null, items [i1, i2,...] )
3 for all item i in [i1, i2,...]
4 for all item j in [i1, i2,...]
5 Emit(pair [i j], count 1)
6
7 class Recer
8 method Rece(pair [i j], counts [c1, c2,...])
9 s = sum([c1, c2,...])
10 Emit(pair[i j], count s)

Stripes Approach（條方法？不知道這個名字怎麼理解）
第二種方法是將數據按照pair中的第一項來分組，並維護一個關聯數組，數組中存儲的是所有關聯項的計數。The second approach is to group data by the first item in pair and maintain an associative array (「stripe」) where counters for all adjacent items are accumulated. Recer receives all stripes for leading item i, merges them, and emits the same result as in the Pairs approach.
中間結果的鍵數量相對較少，因此減少了排序消耗。
可以有效利用 combiners。
可在內存中執行，不過如果沒有正確執行的話也會帶來問題。
實現起來比較復雜。
一般來說， 「stripes」 比 「pairs」 更快

1 class Mapper
2 method Map(null, items [i1, i2,...] )
3 for all item i in [i1, i2,...]
4 H = new AssociativeArray : item -> counter
5 for all item j in [i1, i2,...]
6 H{j} = H{j} + 1
7 Emit(item i, stripe H)
8
9 class Recer
10 method Rece(item i, stripes [H1, H2,...])
11 H = new AssociativeArray : item -> counter
12 H = merge-sum( [H1, H2,...] )
13 for all item j in H.keys()
14 Emit(pair [i j], H{j})

應用：文本分析，市場分析
參考資料：Lin J. Dyer C. Hirst G. Data Intensive Processing MapRece
用MapRece 表達關系模式
在這部分我們會討論一下怎麼使用MapRece來進行主要的關系操作。
篩選（Selection）

1 class Mapper
2 method Map(rowkey key, tuple t)
3 if t satisfies the predicate
4 Emit(tuple t, null)

投影（Projection）
投影只比篩選稍微復雜一點，在這種情況下我們可以用Recer來消除可能的重復值。

1 class Mapper
2 method Map(rowkey key, tuple t)
3 tuple g = project(t) // extract required fields to tuple g
4 Emit(tuple g, null)
5
6 class Recer

⑷ 如何實現hadoop 的安全機制

為了增強Hadoop的安全機制， 從2009年起， Apache專門抽出一個團隊，為Hadoop增加安全認證和授權機制，至今為止，已經可用。

Apache Hadoop 1.0.0版本和Cloudera CDH3之後的版本添加了安全機制，如果你將Hadoop升級到這兩個版本，可能會導致Hadoop的一些應用不可用。

Hadoop提供了兩種安全機制：Simple和Kerberos。Simple機制（默認情況，Hadoop採用該機制）採用了SAAS協議。 也就是說，用戶提交作業時，你說你是XXX（在JobConf的user.name中說明），則在JobTracker端要進行核實，包括兩部分核實，一是你到底是不是這個人，即通過檢查執行當前代碼的人與user.name中的用戶是否一致；然後檢查ACL（Access Control List）配置文件（由管理員配置），看你是否有提交作業的許可權。一旦你通過驗證，會獲取HDFS或者maprece授予的delegation token（訪問不同模塊由不同的delegation token），之後的任何操作，比如訪問文件，均要檢查該token是否存在，且使用者跟之前注冊使用該token的人是否一致。

⑸ 求用c++程序設計的實驗:模擬分頁式存儲管理中硬體的地址轉換和用先進先出調度演算法(FIFO)處理缺頁中斷。

#include<iostream.h>
#include<stdlib.h>
#include<iomanip.h>
#include"windows.h"
#include"os.h"
#define n 64//實驗中假定主存的長度
#define m 4//實驗中假定每個作業分得主存塊塊數
int p[m];//定義頁
struct
{
short int lnumber;//頁號
short int flag;//表示該頁是否在主存，「1」表示在主存，「0」表示不在主存
short int pnumber;//該頁所在主存塊的塊號
short int write;//該頁是否被修改過，「1」表示修改過，「0」表示沒有修改過
short int dnumber;//該頁存放在磁碟上的位置，即磁碟塊號
short int times;//被訪問的次數，用於LRU演算法
}page[n];//定義頁表
//各個函數的實現如下：
computer::computer()
{
int i;
for(i=0;i<n;i++)
{
page[i].lnumber = i;
page[i].flag = 0;
page[i].pnumber = 10000;//用10000表示為空
page[i].write = 0;
page[i].dnumber = i;
page[i].times = 0;
}//初始化頁表

for(i=0;i<m;i++)
{
page[i].pnumber = i;
}

for(i=0;i<m;i++)
{
p[i] = i;
page[i].flag = 1;
}//初始化頁
}
void computer::showpagelist()
{
int i;
cout<<"頁號"<<"\t"<<"是否在主存中"<<"\t"<<"塊 號"<<"\t"<<"是否被修改過"<<"\t"<<"磁碟塊號"<<"\t"<<"訪問次數"<<endl;
for(i=0;i<n;i++)
{
cout<<page[i].lnumber<<"\t"<<page[i].flag<<" "<<page[i].pnumber<<"\t"<<page[i].write<<" "<<page[i].dnumber<<" \t"<<page[i].times<<endl;
}
}
void computer::showpage()
{
int i;
for(i=0;i<m;i++)
{
cout<<"\t"<<p[i];
}
cout<<endl;
}
void computer::transformation()
{
unsigned logicAddress,logicNumber,innerAddress,physicsAddress,physicsNumber;
int i,head=0,fail = 0;
int method,temppage=0;
short int times = 10000;
cout<<"請輸入一個邏輯地址（四位十六進制數）:";
cin>>hex>>logicAddress;//讀入邏輯地址
logicNumber = logicAddress >> 10;//得到頁號
cout<<"頁號為:"<<logicNumber<<endl;
innerAddress = logicAddress & 0x03ff;//得到頁內地址
cout<<"頁內地址為:"<<innerAddress<<endl;
for(i=0;i<n;i++)
{
if(logicNumber==(unsigned)page[i].lnumber)
{
if(page[i].flag == 1)
{
cout<<"請求的頁面在主存中!"<<endl;
page[i].times++;
physicsNumber = page[i].pnumber;//由頁號得到塊號
cout<<"請求的主存塊號為:"<<physicsNumber<<endl;
physicsAddress = physicsNumber << 10 |innerAddress;//得到物理地址
cout<<"請求的物理地址為:"<<physicsAddress<<endl;//輸出物理地址
break;
}
else
{

cout<<"請求的頁面不在主存中! 將進行缺頁中斷處理!"<<endl<<"請選擇演算法!"<<endl;
cout<<"1.先進先出"<<endl<<"2.最近最少用"<<endl<<"請選擇置換演算法:";
cin>>method;
if(method == 1) //採用先進先出演算法
{
cout<<"採用先進先出演算法!"<<endl;
fail = p[head];
cout<<"第"<<fail<<"頁將被替換!"<<endl;
p[head] = logicNumber;
head = (head+1) % m;
if(page[fail].write == 1)
cout<<"第"<<fail<<"頁曾被修改過!"<<endl;
page[fail].flag = 0;
page[logicNumber].flag = 1;
page[logicNumber].write = 0;
page[logicNumber].pnumber = page[fail].pnumber;
page[fail].pnumber = 10000;
page[logicNumber].times++;
break;
}
else if(method == 2) //採用最近最少用演算法
{
cout<<"採用最近最少用演算法!"<<endl;
for(i=0;i<n;i++)
{
if(page[i].flag == 1)
{
if(page[i].times<times)
{
times = page[i].times;
temppage = page[i].lnumber;
}
}
}
cout<<"第"<<temppage<<"頁將被替換!"<<endl;
for(i=0;i<m;i++)
{
if(p[i] == temppage)
{
p[i] = logicNumber;
}
}
if(page[temppage].write == 1)
cout<<"第"<<temppage<<"頁曾被修改過!"<<endl;
page[temppage].flag = 0;
page[logicNumber].flag = 1;
page[logicNumber].write = 0;
page[logicNumber].pnumber = page[temppage].pnumber;
page[temppage].pnumber = 10000;
page[logicNumber].times++;
break;
}
else
{ cout<<"你輸入有誤，即將退出!";
exit(1);
}
}
}
}
}
void main()
{
char c,d;
computer os;
cout<<"頁表正在初始化中...，3秒鍾後為你顯示頁和頁表！"<<endl;
Sleep(3000);
os.showpage();
os.showpagelist();
T:
os.transformation();
cout<<"是否顯示頁和頁表？（Y/N）";
cin>>c;
switch(c)
{
case 'y':
os.showpage();
os.showpagelist();
case 'n':
cout<<"是否繼續進行請求分頁？（Y/N）";
cin>>d;
if (d=='Y'||d=='y')
goto T;
else if (d=='N'||d=='n')
exit(1);
else
cout<<"輸入錯誤！"<<endl;
default:cout<<"輸入錯誤！"<<endl;
}

}

⑹ 虛擬機是什麼，有什麼好處

虛擬機（Virtual Machine）指通過軟體模擬的具有完整硬體系統功能的、運行在一個完全隔離環境中的完整計算機系統。

虛擬系統通過生成現有操作系統的全新虛擬鏡像，它具有真實windows系統完全一樣的功能，進入虛擬系統後，所有操作都是在這個全新的獨立的虛擬系統裡面進行，可以獨立安裝運行軟體，保存數據，擁有自己的獨立桌面，不會對真正的系統產生任何影響 ，而且具有能夠在現有系統與虛擬鏡像之間靈活切換的一類操作系統。

(6)磁碟調度演算法的模擬擴展閱讀：

虛擬機技術最早由 IBM 於上世紀六七十年代提出，被定義為硬體設備的軟體模擬實現，通常的使用模式是分時共享昂貴的大型機。 虛擬機監視器（Virtual Machine Monitor，VMM）是虛擬機技術的核心，它是一層位於操作系統和計算機硬體之間的代碼，用來將硬體平台分割成多個虛擬機。

VMM 運行在特權模式，主要作用是隔離並且管理上層運行的多個虛擬機，仲裁它們對底層硬體的訪問，並為每個客戶操作系統虛擬一套獨立於實際硬體的虛擬硬體環境（包括處理器，內存，I/O 設備）。VMM 採用某種調度演算法在各個虛擬機之間共享 CPU，如採用時間片輪轉調度演算法