帐前卒专栏

code, software architect, articles and novels.
代码，软件架构，博客和小说

Posted on Edited on Word count in article: 502 Reading time ≈ 1 mins.

第一个程序:

1
2
3
4
5
6
7
8
9
10
11
12
13
public class Hello

{

    public static void main(String[] args)

    {

        System.out.println("Hello");

    }

}

算术符号：
<<左移  低位填充零

右移  这是符号右移，如果为正则高位填充零，如果为负高位填充一

右移 不管是否为负，高位均填零
char  byte short进行移位时先转化为int
他们进行运算时也是先转换为int型了

浮点数系统能表示的精度

2∗(M−m+1)∗bp−1+12*(M-m+1)*b^{p-1}+1

IEEE使用：M=1023,m=-1022,p = 53,b=2;
小数可以有的位数为：264−2542^{64}-2^{54}

^异或运算符
~非运算符

boolean型不允许转换为其他类型。
float f4 = 1e-45f; // 10 to the power
1*pow(10,45);后面必须加f表示是float型，否则编译器报错。认为是double型的
Math.random()可以直接使用。。。。。

Posted on Edited on Word count in article: 6.7k Reading time ≈ 6 mins.

##最初的算法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
//System Shedule Algorithm  
//include the Priority First Algorithm and the Time Slice Algorithm  
//Version 2.0  
//author:chillyCreator

#include<string>  
#include<iostream>  
#include<iomanip>  
using namespace std;

class process  
{  
private:  
string name;//the name of process  
int pri;//the priority,the bigger is the higher. the number is from 0 to 99  
int round;// the time slice.  
int cpuTime;//the process used by cpu  
int needTime;//the time need to finish the process  
int state;// 1 is ready, 0 is Run, -1 is Finish  
process* next;//to the next  
public :  
//constructor  
process(string Name,int Pri,int NeedTime,int roundTime = 10,int State = 1,int
CpuTime=0,process * Next = NULL)  
{  
name  = Name;  
pri = Pri;  
round = roundTime;  
cpuTime = CpuTime;  
needTime = NeedTime;  
state = State;  
next = Next;  
}  
//gettors and settors  
string getName()  
{  
return name;  
}  
int getPri()  
{  
return pri;  
}  
int getNeedTime()  
{  
return needTime;  
}  
int getCpuTime()  
{  
return cpuTime;  
}  
int getState()  
{  
return state;  
}  
process* getNext()  
{  
return next;  
}  
void setState(int State)  
{  
state = State;  
}  
void setCpuTime(int Time)  
{  
cpuTime += Time;  
}  
void setNeedTime(int Time)  
{  
needTime -= Time;  
}  
void setPri(int Pri)  
{  
pri -= Pri;  
}  
void setNextProcess(process* Next)  
{  
next = Next;  
}  
void print()  
{  
//for print  
cout <<setw(14)<<name << setw(2)<<state<<setw(7)<<needTime  
<<setw(10)<<pri<<setw(5)<<cpuTime<<endl;  
}  
};

//this is nonpreempt system  
class System  
{  
private:  
process* head;  
process* tail;  
int length;  
//auto test  
void test1(int n)  
{  
head = new process("Head",-1,0,0);  
length = 0;  
process* temp = head;  
for(int i=0;i<n;i++)  
{  
temp->setNextProcess(new process("NameIsForTest "+i,20-i,30+i));  
length++;  
temp = temp->getNext();  
}  
tail = temp;  
}  
//user test  
void test2(int n)  
{  
head = new process("Head",-1,0,0);  
length = 0;  
process* temp = head;  
string name;  
int priority,needtime;  
for(int i=0;i<n;i++)  
{  
cin>>name>>priority>>needtime;  
temp->setNextProcess(new process(name,priority,needtime));  
length++;  
temp = temp->getNext();  
}  
tail = temp;  
}  
public:  
//testN is for the various of tests. 1 is using the default test. 2 is using
the User test.  
System(int testN,int num)  
{  
//num is the number of processes  
if(testN == 1)  
test1(num);  
else  
test2(num);  
}  
//delete a process  
void deleteProcess(process* a)  
{  
process* temp = tail;  
toQueueEnd(a);  
delete a;  
tail = temp;  
tail->setNextProcess(NULL);  
length--;  
}  
void toQueueEnd(process* a)  
{  
if(a->getNext()==NULL)  
return;  
process* temp = findP(a);  
temp->setNextProcess(a->getNext());  
tail->setNextProcess(a);  
tail = a;  
tail->setNextProcess(NULL);  
}  
//put the process to the end of the queue  
void toQueueHead(process* a)  
{  
if(head->getNext()==a)  
return;  
process* temp = findP(a);  
temp->setNextProcess(a->getNext());

if(a==tail)  
tail = temp;  
a->setNextProcess(head->getNext());  
head->setNextProcess(a);  
}  
//find parent  
process* findP(process* a)  
{  
process* temp = head;  
while(temp->getNext() != a)  
temp = temp->getNext();  
return temp;  
}  
//when the process is sheduled into the CPU  
void use(process* pro,int RunTime,int dePriority)  
{  
if(pro->getState()==1)  
{  
if(RunTime < pro->getNeedTime())  
{  
toQueueHead(pro);  
pro->setCpuTime(RunTime);  
pro->setNeedTime(RunTime);  
pro->setPri(dePriority);  
toQueueEnd(pro);  
}  
else  
{  
toQueueHead(pro);  
pro->setCpuTime(pro->getNeedTime());  
pro->setNeedTime(pro->getNeedTime());  
pro->setState(-1);  
cout << endl<<pro->getName()<<" finally use the cpu time is
"<<pro->getCpuTime()<<endl;  
deleteProcess(pro);  
}  
}  
}  
void printAll()  
{  
//All of the process are printed  
cout << setw(14)<<"name " << setw(2)<<"state  "<<setw(5)<<"needTime "  
<<setw(3)<<"pri "<<setw(5)<<"cpuTime  "<<endl;  
for(process* temp = head->getNext();temp!=NULL;temp= temp->getNext())  
{  
temp->print();  
}  
}  
//find the Highest priority  
process* findHighest()  
{  
if(head->getNext()==NULL)  
return NULL;  
process* temp = head->getNext();  
process* first = NULL;  
int i=-1;  
for(;temp!=NULL;temp=temp->getNext())  
{  
if(i < temp->getPri())  
{  
i = temp->getPri();  
first = temp;  
}  
}  
return first;  
}  
// the priority First Algorithm  
void FP()  
{  
while(length > 0)  
{

process* fir = findHighest();  
if(fir != NULL)  
{  
printAll();  
use(fir,10,2);  
}  
}  
}  
//the Time slice Algorithm  
void TS(int RunTime)  
{  
  
while(length>0)  
{  
process* temp = head->getNext();  
printAll();  
if(temp != NULL)  
use(temp,RunTime,0);  
}  
}  
};  
//test  
int main()  
{  
System a(1,4);  
a.FP();  
cout<<endl<<endl<<endl;  
System b(1,4);  
b.TS(10);  
return 0;  
}

今天终于把上面的代码调试成功了！

不过感觉还不够好。如果队列能写成一个单独的类就好了。

而且今天编写队列的删除，进程移至队尾和队首的算法时，思路没有整理好。故白白浪费了太多时间。

对于移至队尾的操作应该记住要把最后一个节点的next指针赋为null.

移至队首的操作也要注意队尾的变化。

对于队列某个元素的删除操作,可以先将元素置尾再删除。或者查找指向它的前一个元素，再通过基本的操作进行删除。

这段程序代码使用的是链表队列。所以考虑的事件较多。如果使用数组的话会省些时间。

此外process 类的gettors and settors太多。简单的可以将私有的变量成员变为共有的。不过安全性不高。这个类中有些变量并没有什么作用，只不过为以后方便模拟。

##继续优化cpu调度算法

如果在system类中加一个这样函数

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
//find the process which is not used.  
//the process will be older with the Time.  
void findOld(int RunT)  
{  
const int increasePri = -2;  
static int time=1;  
process* temp = head->getNext();  
while(temp!=NULL)  
{  
if((temp->getCpuTime() - time*RunT) < 0)  
temp->setPri(increasePri);  
temp = temp->getNext();  
}  
time++;  
cout <<time;  
}

而void FT（）算法中这样调用：

// the priority First Algorithm  
void FP()  
{  
int TimeSlice = 10;  
int oldTimer=0;  
while(length > 0)  
{  
  
process* fir = findHighest();  
if(oldTimer%4==1)  
{  
findOld(TimeSlice);  
//  cout << oldTimer;  
}  
if(fir != NULL)  
{  
printAll();  
use(fir,10,2);  
}  
oldTimer++;  
}  
}

这样改动后就可以让进程随时间的增加而优先级提高。当一个进程在队列中很长一段时间后，进程就会出现老化情况。为了防止老化（就是很难再得到利用）的发生，过一段时间后就会检测进程。当发现长时间没有用到的进程时，优先级会升高。

不过void findOld(int RunT)并不严谨。可能会出现所以进程都提高优先级的情况。所以还要进行优化。

另外在上一次的代码中有可能会出现进程优先级为负数的情况。可以这样修改类process

1
2
3
4
5
6
7
8
9
10

void setPri(int Pri)  
{  
    if(pri-Pri<0)  
        return;  
    if(pri-Pri>100)  
        return;  
    pri -= Pri;  
}

Posted on Edited on Word count in article: 3k Reading time ≈ 3 mins.

ex6.html

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
<html>

<head>

    <head>

    <body>
        <script language="javascript">
            var currentDate = new Date();
            document.write("<table border=1 cellpadding=3 cellspacing=0>");
            document.write("<tr>");
            document.write("<td colspan=7 align='center'>" +
                7 + "</td>");
            document.write("<tr>");
            document.write("<td align='center'>Sun</td>");
            document.write("<td align='center'>Mon</td>");
            document.write("<td align='center'>Tue</td>");
            document.write("<td align='center'>Wes</td>");
            document.write("<td align='center'>The</td>");
            document.write("<td align='center'>Fri</td>");
            document.write("<td align='center'>Sat</td>");
            document.write("</tr>");
            if (currentDate.getDay() != 0) {
                document.write("<tr>");
                for (i = 0; i < currentDate.getDay(); i++) {
                    document.write("<td>&nbsp;</td>");
                }
            }
            document.write("</table>");
            document.write("<br><br><br><hr>");
            document.write(document.URL);
            document.write("<br>");
            var Surl = document.URL.split("//");
            var part = Surl[1].split("//");
            for (var i = 0; i < part.length; i++) {
                var cho = "choice" + i;
                document.write("<a href = document.URL+" + cho +
                    ">" + cho + "</a><br>");
            }

            function newDoc() {
                document.open();
                document.write("byebye");
                document.close();
            }
        </script>
        <a href="#" onClick="newDoc();">New Document</a>
    </body>

</html>

ex7.html

1
2
3
4
5
6
7
8
9
10
11
12
<html>

<head>
    <script>
        window.location = " [ http://www.google.com/ ](http://www.google.com/) ";
    </script>
</head>

<body>
</body>

</html>

ex8.html

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
<html>

<head>

</head>

<body>
    <form>
        Enter a URL: <input type="text" name="url">
        <input type="button" value="Go" onClick="window.location = this.form.url.value">
    </form>

</body>

</html>

ex9.html

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
<html>

<head>
    <script language="javascript">
        var placeHold = window.open("PageLoading.html", "placeholder",
            "width = 200, height = 200");
    </script>
    <title>
        The Main Page
    </title>
</head>

<body onLoad="placeHold.close()">
    Main Page...
</body>

</html>

PageLoading.html

<html>

<head>
    <title>
        The Page is loading
    </title>
</head>

<body>
    The Page is loading........
</body>

</html>

Posted on Edited on Word count in article: 992 Reading time ≈ 1 mins. 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33


var thisDate = new Date();  
document.writeln(thisDate.toString());用于显示当前的时间

if ((thisDate.getDate() >= 1 && thisDate.getDate() <=6) &&
(thisDate.getHours() >= 9 && thisDate.getHours()<= 15))  
用这样的语句可以使网页在一定的时间里做出if语句里的动作

thisDate.getDay()得到当前是星期几.

var Surl = document.URL.split("//");表示用//分割  
var part = Surl[1].split("//");表示用/分割.因为/"会变为转意字符.

function newDoc()  
{  
document.open();  
document.write("byebye");  
document.close();  
}//这是在script中写的

<a href = "#" onClick = "newDoc();">New Document</a>这在外面写  
这是一种打开新页的方法

window.location = “http://www.yahoo.com/”;用这句就可以打开google网站了.  
不过要注意加http://否则就会到硬盘的相对路径上.

var placeHold = window.open("PageLoading.html","placeholder",  
"width = 200, height = 200");//打开一个长宽为200的PageLoading.html  
window.open(pageURL,name,parameters) 这是window.open()函数  
在body中这样写即可把刚加载的页关闭.  
<body onLoad = "placeHold.close()"></body>

Posted on Edited on Word count in article: 3.6k Reading time ≈ 3 mins.

sa.js文件

1
document.write("good day");

ex1.html 文件

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
<html>

    <head>
    </head>

    <body>
        <pre>
            <script language = "javaScript">  
            //this is comment  
            document.writeln("hello");  
            var value1 = '100';  
            var value2 = "kill you";  
            var value3 = 342;  
            var value4 = 400;  
            var value5 = " world";  
            var value6 = (value5+value2).search("k");  
            var value7 = (value5+value2).replace("k",'c');  
            var myArray1 = new Array(5);  
            var myArray2 = new Array("A","B","C");  
            if(true)  
            {

            //document.write("hello");  
            document.writeln("hello");  
            }  
            document.writeln(value2);  
            document.writeln(value1);  
            document.writeln(value3);  
            document.writeln(value3+value4);  
            document.writeln(value2+value5);  
            document.writeln(value3+value5);  
            document.writeln(value6);  
            document.writeln(value7.big());  
            for(var i=0;i<5;i++)  
            {  
            myArray1[i] = i;  
            document.writeln(myArray1[i]);  
            }

            for(i=0;i<3;i++)  
            {  
            document.writeln(myArray2[i]);  
            }

            </script>  
            <noscript>  
            document.write("fefef");  
            </noscript>  
        </pre>
    </body>

</html>

ex2.html文件

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
<html>

<head>
    <title>
        for test Array
    </title>
    <script language="javascript">
        function write() {
            document.writeln("看看");
        }

        function add(a, b) {
            document.writeln(a + b);
        }

        function returnValue(a) {
            return a * a;
        }

        function hello() {
            window.alert("hello");
        }
    </script>

    <head>

    <body>
        <pre>
            <a href = "#" onClick = "hello();">onClick</a>

            <a href = "javascript:hello();">javascript</a>  
            <script language = "javascript">

            var arr = new Array(4);  
            arr[0] = "c";  
            arr[1] = "h";  
            arr[2] = "a";  
            arr[3] = "d";

            for(var i=0;i<4;i++)  
            {  
            document.writeln(arr[i]);  
            }  
            document.writeln(arr.sort());

            var mystring = "a,x,d,e";  
            var arr1 = mystring.split(",");  
            for(i=0;i<4;i++)  
            {  
            document.writeln(arr1[i]);  
            }  
            //window.alert("hello");  
            //window.confirm("bye");  
            write();  
            add(4,6);  
            document.writeln(returnValue(5));

            </script>  
        </pre>
    </body>

</html>

ex3.html文件

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
<html>

    <head>
        <script>
            <!--  
            function warning() {
                window.alert("hello");
            }

            function firm() {
                return window.confirm("Open it?");
                window.setTimeout("firm()", 5000);
            }
            window.setTimeout("firm()", 5000);
            //
            -->
        </script>
    </head>

    <body onload="warning()">
        <script>
            var ok = firm();
            if (ok == true)
                document.writeln("Ok");
        </script>
    </body>

</html>

ex4.html文件

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29

<html>

<head>
    <script>
        <!--  
        function warning() {
            window.alert("hello");
        }

        function firm() {
            window.confirm("Open it?");
            window.setTimeout("firm()", 3000);
        }
        //
        -->
    </script>
</head>

<body onUnload="warning()">
    <script>
        var a = window.setTimeout("firm()", 3000);
        window.clearTimeout(a);
    </script>
</body>

</html>


ex5.html文件

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
<html>

    <head>
    </head>

    <body>
        <script language="javascript">
            var b = document.URL;
            document.writeln(b);
            document.write("<p><strong>Dynamic Content</strong></p>");
        </script>
    </body>

</html>


Posted on Edited on Word count in article: 3k Reading time ≈ 3 mins.

在 javaSript 的注释中的语句只有在支持 javaScript 的浏览器上才能显现

不支持的浏览器要使用

一旦使用则语句块不能再被使用.调用的是 sa.js

这是两种定义字符串的方式

1
2
var value1 = "100";
var value2 = "kill you";

这是两种定义字符串的方式

1
2
3
4
5
6
7
var value5 = " world";
var value6 = (value5+value2).search("k");
var value7 = (value5+value2).replace("k",'c');

document.writeln(value6);这里得到6
document.writeln(value7);这里得到worldcill you

下面是一些常用的函数
big: Returns the string in big tags
blink: Returns the string in blink tags
bold: Returns the string in b tags
fixed: Returns the string in tt tags (for fixed-width display)
fontcolor: Returns the string in font tags with the color
attribute set to the color you specify as an argument
fontsize: Returns the string in font tags with the size attribute
set to the size you specify as an argument
italics: Returns the string in i tags
small: Returns the string in small tags
strike: Returns the string in strike tags (for a strikethrough
effect)
sub: Returns the string in sub tags (for a subscript effect)
sup: Returns the string in sup tags (for a superscript effect)
toLowerCase: Returns the string with all lowercase characters
toUpperCase: Returns the string with all upper case characters

1
2
3
4
5
6
7
8
9
variableName.big();
variableName.fontcolor(“red”);
variableName.toLowerCase();

document.writeln(value7.big());这样字体就变大了.

var finalString =
firstString.bold().toLowerCase().fontcolor("red");以上的各个函数也可以组合使用

就是以上语句的功效就是这个：

1
<font color="”red”"><b>my string</b></font>
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37

for(var i=0;i<5;i++)
{
    myArray1[i] = i;
    document.writeln(myArray1[i]);
}

for(i=0;i<3;i++)//这样不会产生错误.和java不同.
{
    document.writeln(myArray2[i]);
}

html和javascript都是在那里错才不显示.而并不是不能用浏览器浏览.

window.alert("hello");显示警告对话框
window.confirm("bye");显示确定对话框

function hello()
{
window.alert("hello");
}

<a href = "#" onClick = "hello();">onClick</a>//点击显示警告

<a href = "javascript:hello();">javascript</a>点击显示警告
这两句必须都放在<script></script>之外

<body onLoad = "warning();">这了调用的一般不是有参数的函数.
</body>

for(var i=0;i<4;i++)循环可以这样些也可以这样

for(i=0;i<4;i++)
也就是说变量可以不声明就使用

很奇怪

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
<head>
  <script>
    <!--
    function warning() {
      window.alert("hello");
    }

    function firm() {
      return window.confirm("Open it?");
    }
    window.setTimeout("firm()", 5000);
    //
    -->
  </script>
</head>

<body onLoad="warning();">
  <script>
    var ok = firm();
    ...
  </script>
  这里竟然先调用firm() 而后调用warning();
  window.setTimeout("firm()",5000);5秒后自动跳出confirm对话框 function hello() {
  window.alert(“Hello”); window.setTimeout(“hello()”,5000); }
  这个每隔5秒的跳出confirm var a = window.setTimeout("firm()",3000);
  window.clearTimeout(a);用于取消时间调度

  <body onUnload="warning()">
    退出本页面是调用函数 var haveJava =
    navigator.javaEnabled();浏览器可用java则返回true document.write("
    <p><strong>Dynamic Content</strong></p>
    ");当传入write的参数含有html标签时,输出时可以自动转换格式
    这句话就显示加粗后的字样
  </body>
</body>

Posted on Edited on Word count in article: 3.4k Reading time ≈ 3 mins.

This is famous LRU algorithm. It is used to improve cache hit rate.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
//LRU algorithm
//author:chillyCreator
//in the page_information, the bigger number means the newer page.
//if the number in the page_information is -1, it means no page is in this position. 
#include<iostream>
using namespace std;
bool isNotIn(int p_page_num);
bool isNotFull(int& position);
void insert(int p_page_num,int position);
int delOldPage();
const int MAX_INT = 32767;
int process_num;//the total number of process pages
int page_size;//the total number of pages
int page_num=0;//the number of page which in the page array 
int miss=0;//
int* page_information;//the page information array
int* page;//the page array
int old=0;//how old is a page?
int main()
{
 cout << "how many pages of processes ?"<<endl;
 cin >> process_num ;
 cout << "how many pages in the memory?"<<endl; 
 cin >> page_size;
 page_information = new int[page_size];
 page = new int[page_size];
 int i;
 for(i=0; i<page_size; i++)
 { 
  page[i] = -1;
  page_information[i] = -1;
 }
 int user_test;
 cout << "input 1 is user test, 2 is auto test"<<endl;
 cin >> user_test;
 switch(user_test)
 {
 case 1:
  for(i=0; i < process_num; i++)
  {
   int process_page_num;
   cin >> process_page_num;
   cout <<"input process page num is :" <<process_page_num<<endl;
   if(isNotIn(process_page_num))
   {
    miss++;
    int temp_position;
    if(isNotFull(temp_position))
    { 
     insert(process_page_num,temp_position);
     page_num++;
    }
    else
    {
     temp_position = delOldPage();
     insert(process_page_num,temp_position);
    }
   }
  }
 break;
 default:
  for(i=0; i < process_num; i++)
  {
   int process_page_num = rand();
   cout << process_page_num<<endl;
   if(isNotIn(process_page_num))
   {
    miss++;
    int temp_position;
    if(isNotFull(temp_position))
    { 
     insert(process_page_num,temp_position);
     page_num++;
    }
    else
    {
     temp_position = delOldPage();
     insert(process_page_num,temp_position);
    }
   }
  }
  break;
 }
 cout <<"miss is " <<miss << "/t the total process num is "<<process_num<<endl;
 cout << endl;
 cout <<"the miss percentage is miss/process_num = "<<double(miss)/process_num<<endl;
 return 0;
}
//the process page is in the page array?;
bool isNotIn(int p_page_num)
{
 for(int i=0; i<page_size; i++)
 {
  if(page[i]==p_page_num)
   return false;
 }
 return true;
}
//the page array is full or not.
//and return the empty position
bool isNotFull(int& position)
{
 if(page_size <= page_num)
  return false;
 int i;
 for(i=0; i<page_size; i++)
 {
  if(page_information[i]==-1)
   break;
 }
 position = i;
 return true;
}
//insert a process page to the page in an empty position.
//and the function protect the primite: old from flowover error. 
void insert(int p_page_num,int position)
{
  old++;
  if(old==MAX_INT)
  { 
   old = 1;
   for(int i=0; i<page_size; i++)
   {
    if(page_information[i]!=-1)
     page_information[i] = old;
   }
  }
  old++;
  page[position] = p_page_num;
  page_information[position] = old;
}
int delOldPage()
{
 int i;
 int min=page_information[0],min_i=0;
 for(i=1; i<page_size; i++)
 {
  if(min > page_information[i])
  {
   min = page_information[i];
   min_i = i;
  }
 }
 return min_i;
}

Posted on Edited on Word count in article: 5.3k Reading time ≈ 5 mins.

This is famous banker’s algorithm. It is used in advoiding Deadlock.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230

#include<iostream>
using namespace std;
int **allocate,*total,**need,*require;
int num_process,num_resource;
bool isDeadLock(int c=0);
bool findFinish();
void printALL(int**b_allocate,int** b_need,int* b_total);
bool isAllFinish(int**);
int main()
{
 cin >> num_process >> num_resource;
 need = new int* [num_process]; 
 allocate = new int*[num_process];
 total = new int [num_resource];
 require = new int[num_resource];
 int i,q;
 for(i=0;i<num_process;i++)
 {
  need[i] = new int[num_resource];
  allocate[i] = new int[num_resource];
 }
 //define the number of each resource
 for(i=0;i<num_resource;i++)
  cin >> total[i];
 for(i=0;i<num_resource;i++)
  cout <<  total[i];
 //define the processes get how much resource
 for(i=0;i<num_process;i++)
  for(q=0;q<num_resource;q++)
  cin >> allocate[i][q];
 //cheak the resource has enough to allocate
 for(i=0;i<num_resource;i++)
  for(q=0;q<num_process;q++)
  { if(total[i]-allocate[q][i]>=0)
    total[i]-=allocate[q][i];
   else 
   {
    cerr << "error!";
    return 1;
   }
  }

 //define how much resources will each process still need to get to finish itself now
 for(i=0;i<num_process;i++)
  for(q=0;q<num_resource;q++)
   cin >> need[i][q];
 printALL(allocate,need,total);
 //cheak the allocate is deadlock or not
 if(isDeadLock())
 {
  cerr << "dead Lock" ;
  return 1;
 }
 else
  cout << "System is safe"<<endl;
 //auto test
 int test;
 cout << "choose 1:auto test, else:custom test. ";
 cin >> test;
 if(test==1)
 {
  isDeadLock(test);
 }
 //custom test
 else
 {
  while(isAllFinish(need))
  {
   for(i=0;i<num_process;i++)
   {
    cout << i<<": require how much resource?"<<endl;
    for(q=0;q<num_resource;q++)
     cin >> require[q];
    //determine the data of require is right
    for(q=0;q<num_resource;q++)
    { 
     if(total[q] < require[q] || need[i][q] < require[q])
     { 
      cout << "error data information"<<endl;
      i--;
      break;
     }
     total[q]-=require[q];
     need[i][q]-=require[q];
     allocate[i][q]+=require[q];     
    }
    if(isDeadLock(1))
    {
     i--;
     cout << "System is in deadlock state"<<endl;
    }
    else
     cout << "System is safe......"<<endl;
   }
  }
 }
 return 0;
}
//if all the processes are finished,then return true; 
bool isAllFinish(int** b_need)
{
 int i,q;
 for(i=0;i<num_process;i++)
  for(q=0;q<num_resource;q++)
  {
   if(b_need[i][q]!=0)
    return false;
  }
 return true;
}
//if it is deadlock ,then return true;else return false
bool isDeadLock(int c)//c is a flag to show the information or not.
{
 int **backup_allocate,**backup_need,*backup_total;
 backup_need = new int* [num_process]; 
 backup_allocate = new int*[num_process];
 backup_total = new int[num_resource];
 int i,q;
 for(i=0;i<num_process;i++)
 {
  backup_need[i] = new int[num_resource];
  backup_allocate[i] = new int[num_resource]; 
 }
 for(i=0;i<num_process;i++)
  for(q=0;q<num_resource;q++)
  {
   backup_need[i][q] = need[i][q];
   backup_allocate[i][q] = allocate[i][q];
  }
 for(i=0;i<num_resource;i++)
  backup_total[i] = total[i];
// return findFinish();
 if(c!=0)
 printALL(backup_allocate,backup_need,backup_total);
 int flag=0,count=0;
 while(!isAllFinish(backup_need))
 {
  count=0;
  for(i=0;i<num_process;i++)
  { for(q=0;q<num_resource;q++)
   {
    if(backup_need[i][q]>backup_total[q])
    { 
     flag = 0;
     break;
    }
     flag=1;
   }
  // find a finishing process and collect the resource
   if(flag==1)
   {
    count++;
    for(q=0;q<num_resource;q++)
    {
     backup_total[q]+=backup_allocate[i][q];
     backup_allocate[i][q]=0;
     backup_need[i][q]=0;
    }
    
   }
   printALL(backup_allocate,backup_need,backup_total);
  }
//  if(c!=0)
//   printALL(backup_allocate,backup_need,backup_total);
//if no process is finished,it means no resource is collect once.Then the deadlock appears.
  if(count==0)
  {
   delete []backup_total;
   for(i=0;i<num_process;i++)
   { delete[]backup_allocate[i];
    delete[]backup_need[i];
   }
   delete []backup_allocate;
   delete []backup_need;
   return true;
  }
 }

 return false;
}
void printALL(int**b_allocate,int** b_need,int* b_total)
{
 int i,q;
 cout << "Allocate need"<<endl;
 for(i=0;i<num_process;i++)
 { 
  for(q=0;q<num_resource;q++)
  {
   cout << b_allocate[i][q]<<"  ";
  }
  cout << " ";
  for(q=0;q<num_resource;q++)
   cout << b_need[i][q]<<"  ";
  cout << endl;
 }
 cout << "total"<<endl;
 for(i=0;i<num_resource;i++)
  cout << b_total[i]<<"  ";
 cout << endl;
}

/*
bool findFinish()
{
 int i,q,flag=0,count=0;
 for(i=0;i<num_process;i++)
 { for(q=0;q<num_resource;q++)
  {
   if(need[i][q]>total[q])
   { 
    flag = 0;
    break;
   }
    flag=1;
  }
  if(flag==1)
  {
   count++;
   for(q=0;q<num_resource;q++)
   {
    total[q]+=allocate[i][q];
    allocate[i][q]=0;
   }
  }
 }
 if(count!=0)
  return true;
 return false;
}*/
0%