操作系統演算法

1. 計算機操作系統可以稱為演算法嗎為什麼

操作系統不是演算法。演算法的定義是有規范的輸入，在一定有限時間內獲得所要求的輸出的指令的集合。從定義看它與操作系統是兩個概念，當然具體到操作系統本身來說是由很多不同的演算法來執行，比如說磁碟調度演算法、進程調度演算法等等。操作系統（Oper...

2. 操作系統的調度演算法

1)10:00Job1到達並投入運行。此時內存中有作業:Job1
2)10:05 Job2到達並進入內存。此時，Job1運行時間剩餘是25min， Job2運行剩餘時間是20min，根據SRTF，Job2開始運行。
3)10:25 Job2運行結束。Job3、Job4在後備隊列中，據SJF，Job3進入內存，據SRTF，Job3開始運行。內存：Job1、Job3
4)10:30 Job3運行結束。Job4在後備隊列中，Job4進入內存，據SRTF，Job4開始運行。內存：Job1、Job4
5)10:40 Job4運行結束。Job1重新繼續運行。
6)11:05 Job1運行結束。

3. 操作系統相關演算法：SJF和SPF的區別

SJF的調度演算法是從後備隊列中選擇一個或若干個估計運行時間最短的作業，將它們調入內存運行；而SPF調度演算法是從就緒隊列中選出一個估計運行時間最短的進程，將處理機分配給它，使它立即執行並一直執行到完成，或發生某事件而被阻塞放棄處理機時再重新調度。

4. 操作系統頁面置換演算法：第二次機會演算法是什麼

第二次機會演算法：

與FIFO、OPT、LRU、NRU等同為操作系統中請求分頁式管理方式的頁面置換演算法。

第二次機會演算法的基本思想是與FIFO相同的，但是有所改進，避免把經常使用的頁面置換出去。當選擇置換頁面時，依然和FIFO一樣，選擇最早置入內存的頁面。但是二次機會法還設置了一個訪問狀態位。所以還要檢查頁面的的訪問位。如果是0，就淘汰這頁；如果訪問位是1，就給它第二次機會，並選擇下一個FIFO頁面。當一個頁面得到第二次機會時，它的訪問位就清為0，它的到達時間就置為當前時間。如果該頁在此期間被訪問過，則訪問位置為1。這樣給了第二次機會的頁面將不被淘汰，直至所有其他頁面被淘汰過（或者也給了第二次機會）。因此，如果一個頁面經常使用，它的訪問位總保持為1，它就從來不會被淘汰出去。

第二次機會演算法可視為一個環形隊列。用一個指針指示哪一頁是下面要淘汰的。當需要一個存儲塊時，指針就前進，直至找到訪問位是0的頁。隨著指針的前進，把訪問位就清為0。在最壞的情況下，所有的訪問位都是1，指針要通過整個隊列一周，每個頁都給第二次機會。這時就退化成FIFO演算法了。

5. 操作系統優先順序演算法計算題

把字母ABCDE按順序換成CDBEA，其他的不用動 答案不變

6. 操作系統的時間片輪轉法具體的演算法

四、演算法實現
1）系統初始化時給每一個進程賦以一個needtime，並將所有進程按needtime從小到大的次序排成一個隊列。
2） 取隊頭進程,並投入運行。
3） 採用相對固定時間片（Time_piece），進程每執行一次，進程佔用的CPU時間加Time_piece。
4） 若進程沒有運行完，進程needtime減Time，並排到就緒隊列的尾部。
5） 如果尚有進程在隊列中,那麼轉入2）
PCB結構：N 進程個數
name 進程名
Time_piece 進程優先數/進程輪轉時間片
Cpu_time 進程佔用的CPU時間
Need_time 進程到完成還要的時間
Count 計數器
State 進程狀態(P,W,F)
Arrive_time到達時間
next 鏈指針
run 當前運行進程指針
start 就緒隊列頭指針
end 就緒隊列尾指針
finish 完成隊列頭指針
void insert(PCB *p) //時間片插入函數
void create() //時間片演算法創建進程函數
void roundrobin() //時間片演算法函數
void firstin() //運行就緒隊列的第一個進程

你可以到這個地址下載文章看一下。
'http://wenku..com/view/f3bca1d333d4b14e85246830.html'

7. 操作系統的計算環境包括那三方面

個人電腦

個人電腦市場從硬體架構上來說目前分為兩大陣營，PC機與Apple電腦。
它們支持的操作系統：
1.Windows系列操作系統
由微軟公司生產；
2.Unix類操作系統
如SOLARIS,BSD系列（FREEBSD，openbsd，netbsd，pcbsd）；
3.linux類操作系統
如UBUNTU，suse linux，fedora，等
4.Mac操作系統
由蘋果公司生產（Darwin），一般安裝於MAC電腦。

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

哦 ,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

9. 《操作系統》—進程調度演算法

搶占式調度演算法可能導致高優先順序的進程一直佔用CPU，而那些低優先順序的進程可能一直得不到CPU而餓死。

10. 操作系統這門課中所說的演算法是一個什麼樣的概念啊

個人認為，操作系統這門課中所說的演算法一般是C語言或匯編語言實現的
一、下面是網上找到的幾個關於演算法的概念，個人比較傾向第1個：
1、演算法是在有限步驟內求解某一問題所使用的一組定義明確的規則。通俗點說，就是計算機解題的過程。在這個過程中，無論是形成解題思路還是編寫程序，都是在實施某種演算法。前者是推理實現的演算法，後者是操作實現的演算法。
2、「演算法」一詞最早來自公元9世紀波斯數學家比阿勒·霍瓦里松的一本影響深遠的著作《代數對話錄》。20世紀的
英國數學家圖靈提出了著名的圖靈論點，並抽象出了一台機器，這台機器被我們稱之為圖靈機。圖靈的思想對演算法的發展起到了重要的作用。
演算法是計算機處理信息的本質，因為計算機程序本質上是一個演算法，告訴怠定糙剮孬溉茬稅長粳計算機確切的步驟來執行一個指定的任務，如計算職工的薪水或列印學生的成績單。
一般地，當演算法在處理信息時，數據會從輸入設備讀取，寫入輸出設備，可能保存起來以供以後使用。
3、演算法是指完成一個任務准確而完整的描述。也就是說給定初始狀態或輸入數據，經過計算機程序的有限次運算，能夠得出所要求或期望的終止狀態或輸出數據。演算法不單單可以用計算機程序來實現，也可以在人工神經網路、電路或者機械設備上實現。