go嚴格上說沒有多態(tài)，但可以利用接口進行，對于都實現(xiàn)了同一接口的兩種對象，可以進行類似地向上轉型，并且在此時可以對方法進行多態(tài)路由分發(fā)。慕課網上線的新版Go語言不僅有提到這一點，還提到了Go在不面對對象的情況下是怎么完成封裝和繼承的，老師講得很通透，搭配經典算法、典型例題、微型項目深入講授go語言。然后還會教學員從零開始搭建分布式爬蟲系統(tǒng)，學會用go語言處理復雜項目。
成都創(chuàng)新互聯(lián)公司是專業(yè)的源城網站建設公司，源城接單;提供成都網站設計、網站建設,網頁設計,網站設計,建網站,PHP網站建設等專業(yè)做網站服務;采用PHP框架,可快速的進行源城網站開發(fā)網頁制作和功能擴展;專業(yè)做搜索引擎喜愛的網站,專業(yè)的做網站團隊,希望更多企業(yè)前來合作!
八皇后問題是一個古老而著名的問題，是回溯算法的典型例題。該問題是十九世紀著名的數(shù)學家高斯1850年提出：在8X8格的國際象棋上擺放八個皇后，使其不能互相攻擊，即任意兩個皇后都不能處于同一行、同一列或同一斜線上，問有多少種擺法。
高斯認為有76種方案。1854年在柏林的象棋雜志上不同的作者發(fā)表了40種不同的解，后來有人用圖論的方法解出92種結果。事實上就是有92種解法。
對于八皇后問題的實現(xiàn)，如果結合動態(tài)的圖形演示，則可以使算法的描述更形象、更生動，使教學能產生良好的效果。下面是筆者用Turbo C實現(xiàn)的八皇后問題的圖形程序，能夠演示全部的92組解。八皇后問題動態(tài)圖形的實現(xiàn)，主要應解決以下兩個問題。
1．回溯算法的實現(xiàn)
（1）為解決這個問題，我們把棋盤的橫坐標定為i，縱坐標定為j,i和j的取值范圍是從1到8。當某個皇后占了位置(i,j)時，在這個位置的垂直方向、水平方向和斜線方向都不能再放其它皇后了。用語句實現(xiàn)，可定義如下三個整型數(shù)組：a[8],b[15],c[24]。其中：
a[j-1]=1 第j列上無皇后
a[j-1]=0 第j列上有皇后
b[i+j-2]=1 (i,j)的對角線（左上至右下）無皇后
b[i+j-2]=0 (i,j)的對角線（左上至右下）有皇后
c[i-j+7]=1 (i,j)的對角線（右上至左下）無皇后
c[i-j+7]=0 (i,j)的對角線（右上至左下）有皇后
（2）為第i個皇后選擇位置的算法如下：
for(j=1;j=8;j++) /*第i個皇后在第j行*/
if ((i,j)位置為空)） /*即相應的三個數(shù)組的對應元素值為1*/
{占用位置（i,j） /*置相應的三個數(shù)組對應的元素值為0*/
if i8
為i+1個皇后選擇合適的位置；
else 輸出一個解
}
2．圖形存取
在Turbo C語言中，圖形的存取可用如下標準函數(shù)實現(xiàn)：
size=imagesize(x1,y1,x2,y2) ;返回存儲區(qū)域所需字節(jié)數(shù)。
arrow=malloc(size);建立指定大小的動態(tài)區(qū)域位圖，并設定一指針arrow。
getimage(x1,y1,x2,y2,arrow);將指定區(qū)域位圖存于一緩沖區(qū)。
putimage(x,y,arrow,copy)將位圖置于屏幕上以（x，y）左上角的區(qū)域。
3． 程序清單如下
＃i nclude graphics.h
＃i nclude stdlib.h
＃i nclude stdio.h
＃i nclude dos.h
char n[3]={0,0};/*用于記錄第幾組解*/
int a[8],b[15],c[24],i;
int h[8]={127,177,227,277,327,377,427,477};/*每個皇后的行坐標*/
int l[8]={252,217,182,147,112,77,42,7};/*每個皇后的列坐標*/
void *arrow;
void try(int i)
{int j;
for (j=1;j=8;j++)
if (a[j-1]+b[i+j-2]+c[i-j+7]==3) /*如果第i列第j行為空*/
{a[j-1]=0;b[i+j-2]=0;c[i-j+7]=0;/*占用第i列第j行*/
putimage(h[i-1],l[j-1],arrow,COPY_PUT);/*顯示皇后圖形*/
delay(500);/*延時*/
if(i8) try(i+1);
else /*輸出一組解*/
{n[1]++;if (n[1]9) {n[0]++;n[1]=0;}
bar(260,300,390,340);/*顯示第n組解*/
outtextxy(275,300,n);
delay(3000);
}
a[j-1]=1;b[i+j-2]=1;c[i-j+7]=1;
putimage(h[i-1],l[j-1],arrow,XOR_PUT);/*消去皇后，繼續(xù)尋找下一組解*/
delay(500);
}
}
int main(void)
{int gdrive=DETECT,gmode,errorcode;
unsigned int size;
initgraph(gdrive,gmode,"");
errorcode=graphresult();
if (errorcode!=grOk)
{printf("Graphics error\n");exit(1);}
rectangle(50,5,100,40);
rectangle(60,25,90,33);
/*畫皇冠*/
line(60,28,90,28);line(60,25,55,15);
line(55,15,68,25);line(68,25,68,10);
line(68,10,75,25);line(75,25,82,10);
line(82,10,82,25);line(82,25,95,15);
line(95,15,90,25);
size=imagesize(52,7,98,38); arrow=malloc(size);
getimage(52,7,98,38,arrow);/*把皇冠保存到緩沖區(qū)*/
clearviewport();
settextstyle(TRIPLEX_FONT, HORIZ_DIR, 4);
setusercharsize(3, 1, 1, 1);
setfillstyle(1,4);
for (i=0;i=7;i++) a[i]=1;
for (i=0;i=14;i++) b[i]=1;
for (i=0;i=23;i++) c[i]=1;
for (i=0;i=8;i++) line(125,i*35+5,525,i*35+5);/*畫棋盤*/
for (i=0;i=8;i++) line(125+i*50,5,125+i*50,285);
try(1);/*調用遞歸函數(shù)*/
delay(3000);
closegraph();
free(arrow);
}
八皇后問題的串行算法
1 八皇后問題
所謂八皇后問題,是在8*8格的棋盤上,放置8個皇后。要求每行每列放一個皇后,而且每一條對角線和每一條反對角線上不能有多于1個皇后,也即對同時放置在棋盤的兩個皇后(row1,column1)和(row2,column2),不允許(column1-column2)=(row1-row2)或者(column1+row1)=(column2+row2)的情況出現(xiàn)。
2 八皇后問題的串行遞歸算法
八皇后問題最簡單的串行解法為如下的遞歸算法:
(2.1)深度遞歸函數(shù):
go(int step,int column)
{int i,j,place;
row[step]=column;
if (step==8)
outputresult( ); /*結束遞歸打印結果*/
else /*繼續(xù)遞歸*/
{for(place=1;place=8;place++)
{for(j=1;j=step;j++)
if(collision(j ,row[j],step+1,place))
/*判斷是否有列沖突、對角線或反對角線*/
goto skip_this_place;
go(step+1,place);
skip_this_place:;
}
}
}/* go */
(2.2)主函數(shù):
void main( )
{int place,j;
for(place=1;place=8;place++)
go(1,place);
}/* main */
八皇后問題的并行算法
該算法是將八皇后所有可能的解放在相應的棋盤上,主進程負責生成初始化的棋盤，并將該棋盤發(fā)送到某個空閑的子進程,由該子進程求出該棋盤上滿足初始化條件的所有的解。這里，我們假定主進程只初始化棋盤的前兩列，即在棋盤的前兩列分別放上2個皇后,這樣就可以產生8*8=64個棋盤。
1 主進程算法
主進程等待所有的子進程,每當一個子進程空閑的時侯，就向主進程發(fā)送一個Ready(就緒)信號。主進程收到子進程的Ready信號后,就向該子進程發(fā)送一個棋盤。當主進程生成了所有的棋盤后,等待所有的子進程完成它們的工作。然后向每個子進程發(fā)送一個Finished信號,打印出各個子進程找到的解的總和，并退出。子進程接收到Finished信號也退出。
2 子進程算法
每個子進程在收到主進程發(fā)送過來的棋盤后,對該棋盤進行檢查。若不合法,則放棄該棋盤。子進程回到空閑狀態(tài),然后向主進程發(fā)送Ready信號,申請新的棋盤;若合法,則調用move_to_right(board,rowi,colj)尋找在該棋盤上剩下的6個皇后可以擺放的所有位置,move_to_right(board,rowi,colj)是個遞歸過程, 驗證是否能在colj列rowi行以后的位置是否能放一個皇后。
1)首先將more_queen設置成FALSE；
以LEAF,TRUE和FLASE區(qū)分以下三種情況:
A)LEAF:成功放置但是已到邊緣,colj現(xiàn)在已經比列的最大值大1,回退兩列,檢查是否能將待檢查皇后放在哪一行:如果能,把more_queen設成TRUE;
B)TRUE:成功放置皇后,檢查這一列是否能有放置皇后的其他方式,如有,把more_queen設成TRUE;
C)FALSE:不能放置,回退一列再試,如果能把more_queen設成TRUE ,如果皇后已在最后一行,必須再檢查上一列。
2)如果more_queens=TRUE,仍需再次調用move_to_right(),為新棋盤分配空間,用xfer()將現(xiàn)有棋盤拷貝到nextboard，并進行下列情況的處理：
TRUE:得到一個皇后的位置,增大列數(shù)再試；
FALSE:失敗,如果more_queen為真, 取回棋盤,保存上次調用的棋盤。將列數(shù)減小,取走皇后,增加行數(shù),再調用move_to_right()；
LEAF:得到一種解法,solution增一,將解法寫入log_file,由于已到邊緣,列數(shù)回退1,檢查是否放置一個皇后,如果能,新加一個皇后后,調用move_to_right；如果不能,檢查more_queen如果more_queen為真,將棋盤恢復到上次調用時保存的棋盤,將待檢查的皇后下移,調用move_to_right。
八皇后問題的高效解法-遞歸版
// Yifi 2003 have fun! : )
//8 Queen 遞歸算法
//如果有一個Q 為 chess[i]=j;
//則不安全的地方是 k行 j位置,j+k-i位置,j-k+i位置
class Queen8{
static final int QueenMax = 8;
static int oktimes = 0;
static int chess[] = new int[QueenMax];//每一個Queen的放置位置
public static void main(String args[]){
for (int i=0;iQueenMax;i++)chess[i]=-1;
placequeen(0);
System.out.println("\n\n\n八皇后共有"+oktimes+"個解法 made by yifi 2003");
}
public static void placequeen(int num){ //num 為現(xiàn)在要放置的行數(shù)
int i=0;
boolean qsave[] = new boolean[QueenMax];
for(;iQueenMax;i++) qsave[i]=true;
//下面先把安全位數(shù)組完成
i=0;//i 是現(xiàn)在要檢查的數(shù)組值
while (inum){
qsave[chess[i]]=false;
int k=num-i;
if ( (chess[i]+k = 0) (chess[i]+k QueenMax) ) qsave[chess[i]+k]=false;
if ( (chess[i]-k = 0) (chess[i]-k QueenMax) ) qsave[chess[i]-k]=false;
i++;
}
//下面歷遍安全位
for(i=0;iQueenMax;i++){
if (qsave[i]==false)continue;
if (numQueenMax-1){
chess[num]=i;
placequeen(num+1);
}
else{ //num is last one
chess[num]=i;
oktimes++;
System.out.println("這是第"+oktimes+"個解法 如下:");
System.out.println("第n行: 1 2 3 4 5 6 7 8");
for (i=0;iQueenMax;i++){
String row="第"+(i+1)+"行: ";
if (chess[i]==0);
else
for(int j=0;jchess[i];j++) row+="--";
row+="++";
int j = chess[i];
while(jQueenMax-1){row+="--";j++;}
System.out.println(row);
}
}
}
//歷遍完成就停止
Goroutine調度是一個很復雜的機制，下面嘗試用簡單的語言描述一下Goroutine調度機制，想要對其有更深入的了解可以去研讀一下源碼。
首先介紹一下GMP什么意思：
G ----------- goroutine: 即Go協(xié)程，每個go關鍵字都會創(chuàng)建一個協(xié)程。
M ---------- thread內核級線程，所有的G都要放在M上才能運行。
P ----------- processor處理器，調度G到M上，其維護了一個隊列，存儲了所有需要它來調度的G。
Goroutine 調度器P和 OS 調度器是通過 M 結合起來的，每個 M 都代表了 1 個內核線程，OS 調度器負責把內核線程分配到 CPU 的核上執(zhí)行
模型圖：
避免頻繁的創(chuàng)建、銷毀線程，而是對線程的復用。
1）work stealing機制
當本線程無可運行的G時，嘗試從其他線程綁定的P偷取G，而不是銷毀線程。
2）hand off機制
當本線程M0因為G0進行系統(tǒng)調用阻塞時，線程釋放綁定的P，把P轉移給其他空閑的線程執(zhí)行。進而某個空閑的M1獲取P，繼續(xù)執(zhí)行P隊列中剩下的G。而M0由于陷入系統(tǒng)調用而進被阻塞，M1接替M0的工作，只要P不空閑，就可以保證充分利用CPU。M1的來源有可能是M的緩存池，也可能是新建的。當G0系統(tǒng)調用結束后，根據(jù)M0是否能獲取到P，將會將G0做不同的處理：
如果有空閑的P，則獲取一個P，繼續(xù)執(zhí)行G0。
如果沒有空閑的P，則將G0放入全局隊列，等待被其他的P調度。然后M0將進入緩存池睡眠。
如下圖
GOMAXPROCS設置P的數(shù)量，最多有GOMAXPROCS個線程分布在多個CPU上同時運行
在Go中一個goroutine最多占用CPU 10ms，防止其他goroutine被餓死。
具體可以去看另一篇文章
【Golang詳解】go語言調度機制 搶占式調度
當創(chuàng)建一個新的G之后優(yōu)先加入本地隊列，如果本地隊列滿了，會將本地隊列的G移動到全局隊列里面，當M執(zhí)行work stealing從其他P偷不到G時，它可以從全局G隊列獲取G。
協(xié)程經歷過程
我們創(chuàng)建一個協(xié)程 go func()經歷過程如下圖：
說明：
這里有兩個存儲G的隊列，一個是局部調度器P的本地隊列、一個是全局G隊列。新創(chuàng)建的G會先保存在P的本地隊列中，如果P的本地隊列已經滿了就會保存在全局的隊列中；處理器本地隊列是一個使用數(shù)組構成的環(huán)形鏈表，它最多可以存儲 256 個待執(zhí)行任務。
G只能運行在M中，一個M必須持有一個P，M與P是1：1的關系。M會從P的本地隊列彈出一個可執(zhí)行狀態(tài)的G來執(zhí)行，如果P的本地隊列為空，就會想其他的MP組合偷取一個可執(zhí)行的G來執(zhí)行；
一個M調度G執(zhí)行的過程是一個循環(huán)機制；會一直從本地隊列或全局隊列中獲取G
上面說到P的個數(shù)默認等于CPU核數(shù)，每個M必須持有一個P才可以執(zhí)行G，一般情況下M的個數(shù)會略大于P的個數(shù)，這多出來的M將會在G產生系統(tǒng)調用時發(fā)揮作用。類似線程池，Go也提供一個M的池子，需要時從池子中獲取，用完放回池子，不夠用時就再創(chuàng)建一個。
work-stealing調度算法：當M執(zhí)行完了當前P的本地隊列隊列里的所有G后，P也不會就這么在那躺尸啥都不干，它會先嘗試從全局隊列隊列尋找G來執(zhí)行，如果全局隊列為空，它會隨機挑選另外一個P，從它的隊列里中拿走一半的G到自己的隊列中執(zhí)行。
如果一切正常，調度器會以上述的那種方式順暢地運行，但這個世界沒這么美好，總有意外發(fā)生，以下分析goroutine在兩種例外情況下的行為。
Go runtime會在下面的goroutine被阻塞的情況下運行另外一個goroutine：
用戶態(tài)阻塞/喚醒
當goroutine因為channel操作或者network I/O而阻塞時（實際上golang已經用netpoller實現(xiàn)了goroutine網絡I/O阻塞不會導致M被阻塞，僅阻塞G，這里僅僅是舉個栗子），對應的G會被放置到某個wait隊列(如channel的waitq)，該G的狀態(tài)由_Gruning變?yōu)開Gwaitting，而M會跳過該G嘗試獲取并執(zhí)行下一個G，如果此時沒有可運行的G供M運行，那么M將解綁P，并進入sleep狀態(tài)；當阻塞的G被另一端的G2喚醒時（比如channel的可讀/寫通知），G被標記為，嘗試加入G2所在P的runnext（runnext是線程下一個需要執(zhí)行的 Goroutine。）， 然后再是P的本地隊列和全局隊列。
系統(tǒng)調用阻塞
當M執(zhí)行某一個G時候如果發(fā)生了阻塞操作，M會阻塞，如果當前有一些G在執(zhí)行，調度器會把這個線程M從P中摘除，然后再創(chuàng)建一個新的操作系統(tǒng)的線程(如果有空閑的線程可用就復用空閑線程)來服務于這個P。當M系統(tǒng)調用結束時候，這個G會嘗試獲取一個空閑的P執(zhí)行，并放入到這個P的本地隊列。如果獲取不到P，那么這個線程M變成休眠狀態(tài)， 加入到空閑線程中，然后這個G會被放入全局隊列中。
隊列輪轉
可見每個P維護著一個包含G的隊列，不考慮G進入系統(tǒng)調用或IO操作的情況下，P周期性的將G調度到M中執(zhí)行，執(zhí)行一小段時間，將上下文保存下來，然后將G放到隊列尾部，然后從隊列中重新取出一個G進行調度。
除了每個P維護的G隊列以外，還有一個全局的隊列，每個P會周期性地查看全局隊列中是否有G待運行并將其調度到M中執(zhí)行，全局隊列中G的來源，主要有從系統(tǒng)調用中恢復的G。之所以P會周期性地查看全局隊列，也是為了防止全局隊列中的G被餓死。
除了每個P維護的G隊列以外，還有一個全局的隊列，每個P會周期性地查看全局隊列中是否有G待運行并將其調度到M中執(zhí)行，全局隊列中G的來源，主要有從系統(tǒng)調用中恢復的G。之所以P會周期性地查看全局隊列，也是為了防止全局隊列中的G被餓死。
M0
M0是啟動程序后的編號為0的主線程，這個M對應的實例會在全局變量rutime.m0中，不需要在heap上分配，M0負責執(zhí)行初始化操作和啟動第一個G，在之后M0就和其他的M一樣了
G0
G0是每次啟動一個M都會第一個創(chuàng)建的goroutine，G0僅用于負責調度G，G0不指向任何可執(zhí)行的函數(shù)，每個M都會有一個自己的G0，在調度或系統(tǒng)調用時會使用G0的棧空間，全局變量的G0是M0的G0
一個G由于調度被中斷，此后如何恢復？
中斷的時候將寄存器里的棧信息，保存到自己的G對象里面。當再次輪到自己執(zhí)行時，將自己保存的棧信息復制到寄存器里面，這樣就接著上次之后運行了。
我這里只是根據(jù)自己的理解進行了簡單的介紹，想要詳細了解有關GMP的底層原理可以去看Go調度器 G-P-M 模型的設計者的文檔或直接看源碼
參考： ()
()
重慶分公司
重慶分公司
