點進去沒用的系統演算法

Ⅰ 操作系統是演算法嗎

操作系統不是演算法。演算法的定義是有規范的輸入，在一定有限時間內獲得所要求的輸出的指令的集合。從定義看它與操作系統是兩個概念，當然具體到操作系統本身來說是由很多不同的演算法來執行，比如說磁碟調度演算法、進程調度演算法等等。
操作系統（Operating System，簡稱OS）是管理和控制計算機硬體與軟體資源的計算機程序，是直接運行在「裸機」上的最基本的系統軟體，任何其他軟體都必須在操作系統的支持下才能運行。
操作系統是用戶和計算機的介面，同時也是計算機硬體和其他軟體的介面。操作系統的功能包括管理計算機系統的硬體、軟體及數據資源，控製程序運行，改善人機界面，為其它應用軟體提供支持，讓計算機系統所有資源最大限度地發揮作用，提供各種形式的用戶界面，使用戶有一個好的工作環境，為其它軟體的開發提供必要的服務和相應的介面等。實際上，用戶是不用接觸操作系統的，操作系統管理著計算機硬體資源，同時按照應用程序的資源請求，分配資源，如：劃分CPU時間，內存空間的開辟，調用列印機等。

Ⅱ 人臉識別考勤系統一般用什麼演算法

Ⅲ 與操作系統有關的一些經典演算法

哦 ,kmp演算法就是一種經典演算法.KMP演算法
一種改進的字元串匹配演算法，由D.E.Knuth與V.R.Pratt和J.H.Morris同時發現，因此人們稱它為克努特——莫里斯——普拉特操作（簡稱KMP演算法）。
完全掌握KMP演算法思想
學過數據結構的人，都對KMP演算法印象頗深。尤其是新手，更是難以理解其涵義，搞得一頭霧水。今天我們就來面對它，不將它徹底搞懂，誓不罷休。
如今，大夥基本上都用嚴蔚敏老師的書，那我就以此來講解KMP演算法。(小弟正在備戰考研，為了節省時間，很多課本上的話我都在此省略了，以後一定補上。)
嚴老的《數據結構》79頁講了基本的匹配方法，這是基礎。
80頁在講KMP演算法的開始先舉了個例子，讓我們對KMP的基本思想有了最初的認識。目的在於指出「由此，在整個匹配的過程中，i指針沒有回溯，」。
我們繼續往下看：
現在討論一般情況。
假設 主串：s: 『s(1) s(2) s(3) ……s(n)』 ; 模式串 ：p: 『p(1) p(2) p(3)…..p(m)』
現在我們假設 主串第i個字元與模式串的第j(j<=m)個字元『失配』後，主串第i個字元與模式串的第k(k<j)個字元繼續比較
此時，s(i)≠p(j), 有
主串： S(1)…… s(i-j+1)…… s(i-1) s(i) ………….
|| (相配) || ≠(失配)
匹配串： P(1) ……. p(j-1) p(j)
由此，我們得到關系式
『p(1) p(2) p(3)…..p(j-1)』 = 』 s(i-j+1)……s(i-1)』
由於s(i)≠p(j)，接下來s(i)將與p(k)繼續比較，則模式串中的前(k-1)個字元的子串必須滿足下列關系式，並且不可能存在 k』>k 滿足下列關系式：(k<j),
『p(1) p(2) p(3)…..p(k-1)』 = 』 s(i-k+1)s(i-k+2)……s(i-1)』
即：
主串： S(1)……s(i-k +1) s(i-k +2) ……s(i-1) s(i) ………….
|| (相配) || || ?(有待比較)
匹配串： P(1) p(2) …… p(k-1) p(k)
現在我們把前面總結的關系綜合一下
有：
S(1)…s(i-j +1)… s(i-k +1) s(i-k +2) …… s(i-1) s(i) ……
|| (相配) || || || ≠(失配)
P(1) ……p(j-k+1) p(j-k+2) ….... p(j-1) p(j)
|| (相配) || || ?(有待比較)
P(1) p(2) ……. p(k-1) p(k)
由上，我們得到關系：
『p(1) p(2) p(3)…..p(k-1)』 = 』 s(j-k+1)s(j-k+2)……s(j-1)』
接下來看「反之，若模式串中存在滿足式(4-4)。。。。。。。」這一段。看完這一段，如果下面的看不懂就不要看了。直接去看那個next函數的源程序。(偽代碼)
K 是和next有關系的，不過在最初看的時候，你不要太追究k到底是多少，至於next值是怎麼求出來的，我教你怎麼學會。
你照著源程序，看著那個例子慢慢的推出它來。看看你做的是不是和課本上正確的next值一樣。
然後找幾道練習題好好練練，一定要做熟練了。現在你的腦子里已經有那個next演算法的初步思想了，再回去看它是怎麼推出來的，如果還看不懂，就繼續做練習，做完練習再看。相信自己！！！
附：
KMP演算法查找串S中含串P的個數count
#include <iostream>
#include <stdlib.h>
#include <vector>
using namespace std;
inline void NEXT(const string& T,vector<int>& next)
{
//按模式串生成vector,next(T.size())
next[0]=-1;
for(int i=1;i<T.size();i++ ){
int j=next[i-1];
while(T!=T[j+1]&& j>=0 )
j=next[j] ; //遞推計算
if(T==T[j+1])next=j+1;
else next=0; //
}
}
inline string::size_type COUNT_KMP(const string& S,
const string& T)
{
//利用模式串T的next函數求T在主串S中的個數count的KMP演算法
//其中T非空，
vector<int> next(T.size());
NEXT(T,next);
string::size_type index,count=0;
for(index=0;index<S.size();++index){
int pos=0;
string::size_type iter=index;
while(pos<T.size() && iter<S.size()){
if(S[iter]==T[pos]){
++iter;++pos;
}
else{
if(pos==0)++iter;
else pos=next[pos-1]+1;
}
}//while end
if(pos==T.size()&&(iter-index)==T.size())++count;
} //for end
return count;
}
int main(int argc, char *argv[])
{
string S="";
string T="ab";
string::size_type count=COUNT_KMP(S,T);
cout<<count<<endl;
system("PAUSE");
return 0;
}
補上個Pascal的KMP演算法源碼
PROGRAM Impl_KMP;
USES
CRT;
CONST
MAX_STRLEN = 255;
VAR
next : array [ 1 .. MAX_STRLEN ] of integer;
str_s, str_t : string;
int_i : integer;
Procere get_nexst( t : string );
Var
j, k : integer;
Begin
j := 1; k := 0;
while j < Length(t) do
begin
if ( k = 0 ) or ( t[j] = t[k] ) then
begin
j := j + 1; k := k + 1;
next[j] := k;
end
else k := next[k];
end;
End;
Function index( s : string; t : string ) : integer;
Var
i, j : integer;
Begin
get_next(t);
index := 0;
i := 1; j := 1;
while ( i <= Length(s) ) and ( j <= Length(t) ) do
begin
if ( j = 0 ) or ( s = t[j] ) then
begin
i := i + 1; j := j + 1;
end
else j := next[j];
if j > Length(t) then index := i - Length(t);
end;
End;
BEGIN
ClrScr;
Write(s = );
Readln(str_s);
Write(t = );
Readln(str_t);
int_i := index( str_s, str_t );
if int_i <> 0 then
begin
Writeln( Found , str_t, in , str_s, at , int_i, . );
end
else
Writeln( Cannot find , str_t, in , str_s, . );
END.
index函數用於模式匹配，t是模式串，s是原串。返回模式串的位置，找不到則返回0

Ⅳ 深度優先搜索的系統演算法

所有的搜索演算法從其最終的演算法實現上來看，都可以劃分成兩個部分──控制結構和產生系統。正如前面所說的，搜索演算法簡而言之就是窮舉所有可能情況並找到合適的答案，所以最基本的問題就是羅列出所有可能的情況，這其實就是一種產生式系統。
我們將所要解答的問題劃分成若干個階段或者步驟，當一個階段計算完畢，下面往往有多種可選選擇，所有的選擇共同組成了問題的解空間，對搜索演算法而言，將所有的階段或步驟畫出來就類似是樹的結構（如圖）。
從根開始計算，到找到位於某個節點的解，回溯法（深度優先搜索）作為最基本的搜索演算法，其採用了一種「一隻向下走，走不通就掉頭」的思想（體會「回溯」二字），相當於採用了先根遍歷的方法來構造搜索樹。
上面的話可能難於理解，沒關系，我們通過基本框架和例子來闡述這個演算法，你會發現其中的原理非常簡單自然。

Ⅳ 操作系統模擬電梯調度演算法C語言程序

多級反饋隊列調度演算法 多級反饋隊列調度演算法是一種CPU處理機調度演算法，UNIX操作系統採取的便是這種調度演算法。 多級反饋隊列調度演算法即能使高優先順序的作業得到響應又能使短作業(進程)迅速完成。（對比一下FCFS與高優先響應比調度演算法的缺陷）。 多級(假設為N級)反饋隊列調度演算法可以如下原理： 1、設有N個隊列（Q1,Q2....QN），其中各個隊列對於處理機的優先順序是不一樣的，也就是說位於各個隊列中的作業(進程)的優先順序也是不一樣的。一般來說，優先順序Priority(Q1) > Priority(Q2) > ... > Priority(QN)。怎麼講，位於Q1中的任何一個作業(進程)都要比Q2中的任何一個作業(進程)相對於CPU的優先順序要高（也就是說，Q1中的作業一定要比Q2中的作業先被處理機調度），依次類推其它的隊列。 2、對於某個特定的隊列來說，裡面是遵循時間片輪轉法。也就是說，位於隊列Q2中有N個作業，它們的運行時間是通過Q2這個隊列所設定的時間片來確定的（為了便於理解，我們也可以認為特定隊列中的作業的優先順序是按照FCFS來調度的）。 3、各個隊列的時間片是一樣的嗎？不一樣，這就是該演算法設計的精妙之處。各個隊列的時間片是隨著優先順序的增加而減少的，也就是說，優先順序越高的隊列中它的時間片就越短。同時，為了便於那些超大作業的完成，最後一個隊列QN(優先順序最高的隊列)的時間片一般很大(不需要考慮這個問題)。 多級反饋隊列調度演算法描述： 1、進程在進入待調度的隊列等待時，首先進入優先順序最高的Q1等待。 2、首先調度優先順序高的隊列中的進程。若高優先順序中隊列中已沒有調度的進程，則調度次優先順序隊列中的進程。例如：Q1,Q2,Q3三個隊列，只有在Q1中沒有進程等待時才去調度Q2，同理，只有Q1,Q2都為空時才會去調度Q3。 3、對於同一個隊列中的各個進程，按照時間片輪轉法調度。比如Q1隊列的時間片為N，那麼Q1中的作業在經歷了N個時間片後若還沒有完成，則進入Q2隊列等待，若Q2的時間片用完後作業還不能完成，一直進入下一級隊列，直至完成。 4、在低優先順序的隊列中的進程在運行時，又有新到達的作業，那麼在運行完這個時間片後，CPU馬上分配給新到達的作業（搶占式）。 我們來看一下該演算法是如何運作的： 假設系統中有3個反饋隊列Q1,Q2,Q3，時間片分別為2，4，8。 現在有3個作業J1,J2,J3分別在時間 0 ，1，3時刻到達。而它們所需要的CPU時間分別是3，2，1個時間片。 1、時刻0 J1到達。於是進入到隊列1 ， 運行1個時間片 ， 時間片還未到，此時J2到達。 2、時刻1 J2到達。 由於時間片仍然由J1掌控，於是等待。 J1在運行了1個時間片後，已經完成了在Q1中的 2個時間片的限制，於是J1置於Q2等待被調度。現在處理機分配給J2。 3、時刻2 J1進入Q2等待調度，J2獲得CPU開始運行。 4、時刻3 J3到達，由於J2的時間片未到，故J3在Q1等待調度，J1也在Q2等待調度。 5、時刻4 J2處理完成，由於J3，J1都在等待調度，但是J3所在的隊列比J1所在的隊列的優先順序要高，於是J3被調度，J1繼續在Q2等待。 6、時刻5 J3經過1個時間片，完成。 7、時刻6 由於Q1已經空閑，於是開始調度Q2中的作業，則J1得到處理器開始運行。 8、時刻7 J1再經過一個時間片，完成了任務。於是整個調度過程結束。

Ⅵ 操作系統的主要演算法都有哪些

一、進程(作業)調度演算法
l 先來先服務調度演算法（FCFS）：每次調度是從就緒隊列中，選擇一個最先進入就緒隊列的進程，把處理器分配給該進程，使之得到執行。該進程一旦佔有了處理器，它就一直運行下去，直到該進程完成或因發生事件而阻塞，才退出處理器。特點：利於長進程，而不利於短進程。

l 短進程（作業）優先調度演算法(SPF)：它是從就緒隊列中選擇一個估計運行時間最短的進程，將處理器分配給該進程，使之佔有處理器並執行，直到該進程完成或因發生事件而阻塞，然後退出處理器，再重新調度。

l 時間片輪轉調度演算法 ：系統將所有的就緒進程按進入就緒隊列的先後次序排列。每次調度時把CPU分配給隊首進程，讓其執行一個時間片，當時間片用完，由計時器發出時鍾中斷，調度程序則暫停該進程的執行，使其退出處理器，並將它送到就緒隊列的末尾，等待下一輪調度執行。

l 優先數調度演算法 ：它是從就緒隊列中選擇一個優先權最高的進程，讓其獲得處理器並執行。

l 響應比高者優先調度演算法：它是從就緒隊列中選擇一個響應比最高的進程，讓其獲得處理器執行，直到該進程完成或因等待事件而退出處理器為止。特點：既照顧了短進程，又考慮了進程到達的先後次序，也不會使長進程長期得不到服務，因此是一個比較全面考慮的演算法，但每次進行調度時，都需要對各個進程計算響應比。所以系統開銷很大，比較復雜。

l 多級隊列調度演算法

基本概念：

作業周轉時間（Ti）＝完成時間(Tei)－提交時間(Tsi)

作業平均周轉時間(T)＝周轉時間/作業個數

作業帶權周轉時間（Wi）＝周轉時間/運行時間

響應比＝（等待時間＋運行時間）/運行時間

二、存儲器連續分配方式中分區分配演算法
n 首次適應分配演算法（FF）：對空閑分區表記錄的要求是按地址遞增的順序排列的，每次分配時，總是從第1條記錄開始順序查找空閑分區表，找到第一個能滿足作業長度要求的空閑區，分割這個空閑區，一部分分配給作業，另一部分仍為空閑區。

n 循環首次適應演算法：每次分配均從上次分配的位置之後開始查找。

n 最佳適應分配演算法(BF)：是按作業要求從所有的空閑分區中挑選一個能滿足作業要求的最小空閑區，這樣可保證不去分割一個更大的區域，使裝入大作業時比較容易得到滿足。為實現這種演算法，把空閑區按長度遞增次序登記在空閑區表中，分配時，順序查找。

三、頁面置換演算法
l 最佳置換演算法（OPT) ：選擇以後永不使用或在最長時間內不再被訪問的內存頁面予以淘汰。

l 先進先出置換演算法（FIFO）：選擇最先進入內存的頁面予以淘汰。

l 最近最久未使用演算法（LRU）：選擇在最近一段時間內最久沒有使用過的頁，把它淘汰。

l 最少使用演算法（LFU）：選擇到當前時間為止被訪問次數最少的頁轉換。

四、磁碟調度
n 先來先服務（FCFS）：是按請求訪問者的先後次序啟動磁碟驅動器，而不考慮它們要訪問的物理位置

n 最短尋道時間優先（SSTF）：讓離當前磁軌最近的請求訪問者啟動磁碟驅動器，即是讓查找時間最短的那個作業先執行，而不考慮請求訪問者到來的先後次序，這樣就克服了先來先服務調度演算法中磁臂移動過大的問題

n 掃描演算法（SCAN）或電梯調度演算法：總是從磁臂當前位置開始，沿磁臂的移動方向去選擇離當前磁臂最近的那個柱面的訪問者。如果沿磁臂的方向無請求訪問時，就改變磁臂的移動方向。在這種調度方法下磁臂的移動類似於電梯的調度，所以它也稱為電梯調度演算法。

n 循環掃描演算法（CSCAN）：循環掃描調度演算法是在掃描演算法的基礎上改進的。磁臂改為單項移動，由外向里。當前位置開始沿磁臂的移動方向去選擇離當前磁臂最近的哪個柱面的訪問者。如果沿磁臂的方向無請求訪問時，再回到最外，訪問柱面號最小的作業請求。

Ⅶ 求這道操作系統調度演算法類題目的答案。

首先在一個程序進行IO操作的時候，CPU可以釋放出來給另一個程序進行計算
然後系統可以同時進行兩個計算，即雙核CPU可同時工作用於程序的計算
設每個字母代表一個時間片長度20ms，C表示計算， I表示IO，D表示等待
則各程序的時間片分配如下：
P1：C I I I I CC
P2：CCCCCCC I CC
P3：DCCCCDDC I I I I CC
其中P1和P2的優先順序最高，按所給操作用時直接分配即可
P3優先順序最低，第一個時間片P1和P2在同時計算，所以P3要等待
隨後P1進入IO，其CPU空閑，可以分配給P3進行計算
在計算了4個時間片80ms後，P1結束IO搶佔了P3的CPU，所以P3又繼續等待2個時間片
後面P1程序結束，不會再搶佔CPU，P3按剩餘操作用時直接分配即可
所以最短用時為最後P3完成所需的時間，共14個時間片，280ms

Ⅷ 短鏈接系統的演算法原理

平時我們在上網的時候，印象最深刻的有一次是短鏈接的服務。例如：平時在微信上看一個網頁的時候，如果我們選擇在瀏覽器打開的時候，會看到很長的URL，我們分享的時候，會看到一個很短URL，這就是本次所說的短鏈接的應用之一。
長鏈接示例： https://mp.weixin.qq.com/s?__biz=MzAxNzMwOTQ0NA==&mid=2653355437&idx=1&sn=&chksm=31c947&scene=0&key=01a8800b6fd6b36be097&ascene=0&uin=ODU5NDQ1NjI1&devicetype=iMac+MacBookAir6%2C2+OSX+OSX+10.12.6+build(16G29)&version=12020810&nettype=WIFI&fontScale=100&pass_ticket=IvPqxUmCJqZg9%
我用短鏈接系統生成的（長期會失效）： https://0x9.me/FAKcm

廢話少說，短鏈接就是我們很短的鏈接。我們的目的是要把長鏈接轉換成短鏈接。接下來我要提出一個問題：怎麼把長鏈接轉換成短鏈接呢？
1.壓縮
實現一種演算法，將長地址轉換成短地址。然後再實現一種逆運算，將短地址轉換成原來的地址。其實仔細的想一下，這是不可能的。
2.Hash演算法
可能是大多數人都會想到的一種方法。有人會提出，將一個長URL進行Hash運算，然後將Hash值作為這個長鏈接的唯一標示。但是通常容易想到的不一定是最優的，我們知道Hash有可能產生碰撞，Hash碰撞的解決，會增強短鏈接系統的復雜度。

顧名思義這個系統的第一個請求過來了，我們以微博為例，短鏈接系統的第一個請求我們可以給變為t.cn/0，第二個t.cn/1等等；
實現的方式也會很簡單
1、小型的系統用MySQL的自增索引就可以滿足。
2、大型系統可以考慮分布式key-value系統。

發號策略是這樣的，當一個新的鏈接過來時，發號器發一個號與之對應。往後只要有新鏈接過來，發號器不停發號就好。舉個例子，第一個進來的鏈接發號器發0號，對應的短鏈接為 xx.xxx/0，第二個進來的鏈接發號器發1號，對應的短鏈接為 xx.xxx/1，以此類推。
發號器發出的10進制號需要轉換成62進制，這樣可以大大縮短號碼轉換成字元串後的長度。比如發號器發出 10,000,000,000 這個號碼，如果不轉換成62進制，直接拼接在域名後面，得到這樣一個鏈接 xx.xxx/10000000000。將上面的號碼轉換成62進制，結果為AOYKUa，長度只有6位，拼接得到的鏈接為 xx.xxx/AOYKUa。可以看得出，進制轉換後得到的短鏈接長度變短了一些。6位62進制數，對應的號碼空間為626，約等於568億，所以基本上不用擔心發號器無號可發的情況。

上面設計看起來有一個單點，那就是發號器。如果做成分布式的，那麼多節點要保持同步加1，多點同時寫入。這樣難以避免產生單點性能瓶頸。因此我們可以考慮將單點變為多點。我們可以引入多個機器，我們可以設定機器A發號只發向100取余等於0的數字100n，同理機器B只發向100取余等於1數字 100n+1，以此類推，各個機器相互獨立互不幹擾，我們可以隨時擴展我們的機器了。

同一長鏈接，每次轉成的短鏈接不一定一樣，原因在於如果查詢緩存時，如果未命中，發號器會發新號給這個鏈接。需要說明的是，緩存應該緩存經常轉換的熱門鏈接，假設設定緩存過期時間為一小時，如果某個鏈接很活躍的話，緩存查詢命中後，緩存會刷新這個鏈接的存活時間，重新計時，這個鏈接就會長久存在緩存中。
我們也可以引入LRU演算法。進行淘汰我們不經常使用到的鏈接。

選取301，還是302？
301是永久重定向，302是臨時重定向。

如果選擇301 ：短地址生成以後就不會變化，所以用301是符合http語義的。同時對伺服器壓力也會有一定減少。這樣一來，我們就無法統計到短地址被點擊的次數了。
如果選擇302 ：選擇302雖然會增加伺服器壓力，但是可以統計到短地址被點擊的次數了，我可以針對點擊的次數來進行後期的大數據處理，機器學習，以及推薦演算法。
選擇302還是301，想必讀者心中有肯定有數了。