一个面向对象实现的银行家算法

最近完成学校《操作系统》课程的试验报告,其中的题目是用程序实现银行家算法。什么是银行家算法,这里就不详提了,具体参看Wikipedia-zh

Wikipedia的页面里面有整个银行家算法的伪代码,加起来只有12行,很清晰地表达出整个算法的思想,然而如果你到别的地方看看一些具体的银行家算法实现,往往会被吓一跳(可以看看百度百科的词条)。

银行家算法本来并不复杂,只是其运算涉及向量、集合,实现起来还是花要一点功夫。我使用C++来实现银行家算法,为了实现和伪代码描述尽可能接近,重载对象的运算符等,最后整个算法的实现和伪代码没太大差别,也就20行的样子。

伪代码

while (P != ∅) {
    found = FALSE;
    foreach (p ∈ P) {
        if (Mp − Cp ≤ A) {
             A = A + Cp ;
             P = P − {p};
             found = TRUE;
        }
    }
    if (! found) return FAIL;
}
return OK;

C++代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
while( !Processes.empty() ) {
    bool found = false;
    list<Process>::iterator i = Processes.begin();
    while ( i != Processes.end() ) {
        if(i->Maxmum - i->Current <= SystemAvaliable) {
            SystemAvaliable = SystemAvaliable + i->Current;
            Processes.erase(i);
            found = true;
            break;
        }
        ++i;
    }
    if( !found ){
        return 1;
    }
}
return 0;

使用C++来描述,因为对象特性,整个过程显得非常清晰,比起百度百科里面的C语言版本,可谓别有一种风格。两年前学校刚开设C++课程,老师一上台就给我们说什么是类、模板,什么是重载、继承……几乎没人明白他说什么。后来我做一道ACM题目的是需要实现一个7进制计数器,想起了所谓的对象特性,当完成了那个程序,忽然一片开朗,原来这才是面对对象,再后来接受Java、设计模式等的概念就容易多了。

实现这个银行家算法,我的C++用了140多行,百度百科那个版本看起来也差不多。是否面对对象,常常并不影响代码量,而是影响代码的可读性而已,再说不管高级语言怎么面向对象,在编译器里面解开了,不都是一条条的指令。当然,在设计模式的思想来说,面对对象更好地体现“设计”的理念。

不过C和C++并不是是否面对对象的区别,有些C的代码是面向对象的,看看GTK+库的实现,虽然全是void类型的指针转来转去,却是很明确的对象思想,有个很有趣的libcurl库也是那样;有些C++代码却是一点都不面向对象,看看一些Win的程序,虽然用了很多new、delete等C++特性,用上了CString,用上namespace,却这里一个全局变量,那里一个全局函数,不伦不类,没办法,教材的例子都那样。

早天在图书馆随手翻开一本《C++实践之路》(Bartosz Milewski,邮电出版社),前言那里说,C++的学习方法有两种,一是从C语言的集合开始,另一是从STL开始,而作者认为两者都过于极端,都不利于真正掌握C++。PT不敢说对C++学有所成,只不过是到目前为止代码量累积最多的语言。课堂上老师对STL只字不提,但个人觉得不懂得STL,就不算懂C++。STL的设计可谓把C++的特性发挥得淋漓尽致,不管是其设计思路,还是使用的方法,都应该由所有的C++程序员去参考和尊随。再高层的软件设计,更应该参考Java,设计模式,只有这样才有利于壮健的代码,可读的代码的质量。


银行家算法的完整代码:

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
#include    <list>
#include    <iostream>
 
using namespace std;
 
/* “资源”类,包含A、B、C、D四种“资源”
 */
class Resource{
    private:
        int A;
        int B;
        int C;
        int D;
    public:
        Resource(int A, int B, int C, int D);
        Resource operator + (const Resource &res);
        Resource operator - (const Resource &res);
        void operator = (const Resource &res);
        bool operator <= (const Resource &res);
 
    //便于stream输出
    friend ostream &
    operator << ( ostream & os, const Resource & obj )
    {
        os << "A:" << obj.A << " B:" << obj.B <<
            " C:" << obj.C << " D:" << obj.D << endl;
        return os;
    }
};
 
Resource::Resource(int A, int B, int C, int D)
{
    this->A = A;
    this->B = B;
    this->C = C;
    this->D = D;
}
 
Resource 
Resource:: operator + (const Resource &res)
{
    int A = this->A + res.A;
    int B = this->B + res.B;
    int C = this->C + res.C;
    int D = this->D + res.D;
    return Resource(A, B, C, D);
}
 
Resource 
Resource:: operator - (const Resource &res)
{
    int A = this->A - res.A;
    int B = this->B - res.B;
    int C = this->C - res.C;
    int D = this->D - res.D;
    return Resource(A, B, C, D);
}
 
void 
Resource::operator = (const Resource &res)
{
    this->A = res.A;
    this->B = res.B;
    this->C = res.C;
    this->D = res.D;
}
 
bool 
Resource::operator <= (const Resource &res)
{
    return (this->A <= res.A) && (this->B <= res.B) &&
                (this->C <= res.C) && (this->D <= res.D);
}
 
/*“线程”类,带有该“线程”当前拥有的资源Current和“线程”的最大需求Maxmum
 */
class Process {
    public:
        int id;
        Resource Maxmum;
        Resource Current;
    public:
        Process(int i, const Resource &Max, const Resource &Cur);
    friend ostream &
    operator << ( ostream & os, const Process & obj )
    {
        os << "Process " << obj.id << "n" << "MAX " << obj.Maxmum <<
            "CUR " << obj.Current;
        return os;
    }
};
 
Process::Process(int i, const Resource &Max, const Resource &Cur):
    id(i), Maxmum(Max), Current(Cur){}
 
/*
 *  银行家算法实现函数 
 */
int
BankerAlgorithm ()
{
    Resource SystemAvaliable(3,1,0,2);
 
    list<Process> Processes;
 
    Processes.push_back(
                //构建一个“进程”,参数分别为“进程号、当前拥有资源、最大需求资源“
                Process(1,Resource(3,3,2,2),Resource(1,2,0,1)));
    Processes.push_back(
                Process(2,Resource(1,2,3,4),Resource(1,2,3,3)));
    Processes.push_back(
                Process(3,Resource(1,1,5,0),Resource(1,1,2,0)));
 
    while( !Processes.empty() ) {
        bool found = false;
        list<Process>::iterator i = Processes.begin();
        while ( i != Processes.end() ) {
            cout << "---System " << SystemAvaliable;
            cout << "---For Process "<< i->id << ": n" << *i;
            if(i->Maxmum - i->Current <= SystemAvaliable) {
                cout << "---Process " << i->id 
                        << " Could be Terminated.n" << endl;
                SystemAvaliable = SystemAvaliable + i->Current;
                Processes.erase(i);
                found = true;
                break;
            }
            else {
                cout << "---Process " << i->id <<
                    " Could NOT be Terminated Now.n" << endl;
                ++i;
            }
        }
        if( !found ){
            cout << "Fail, It's an UNSAFE state." << endl;
            return 1;
        }
    }
    cout << "OK, It's a SAFE state." << endl;
    return 0;
}
 
int
main ( int argc, char *argv[] )
{
    return BankerAlgorithm();
}
文章分类 C/C++ 标签: , ,
One comment on “一个面向对象实现的银行家算法
  1. PT说道:

    留言留言~~

发表评论

电子邮件地址不会被公开。 必填项已用*标注

*