1 银行家算法的分析与实现

问题描述：

• 研究一个银行家如何将总数一定的资金，安全的借给若干个顾客，使顾客既能满足对资金的需求，也使银行家可以收回自己的全部资金，不至于破产。

一些限制条件：

• 每个顾客在借款前必须提前说明所需资金总额。
• 每次借钱都是以一个单位进行（如：一个单位为1万人民币）。
• 顾客在拿到一个单位的借款前可能需要等待。
• 银行保证顾客的等待时间是有限的（借或不借）。

算法示例：

算法策略：

• 将资金优先借予资金需求较少的客户。

应用场景：

• 操作系统内核中的进程管理。
• 数据库内核中的频繁事务管理。

Qt中的算法实现方案：

• 使用多线程机制模拟客户和银行。
• 银行有限分配资源给最小需求的客户。
• 当客户的资源需求无法满足的时候：
  • 收回已分配的资源。
  • 强制结束线程。

银行家算法常用于资源分配的场合：

• 解决的问题：
  • 保证资源分配的安全性。
• 算法策略：
  • 优先选择需求量较少的客户进行资源分配。

编程实验：银行家算法的实现

#include <QtCore/QCoreApplication>
#include <QThread>
#include <QMutex>
#include <QList>
#include <QDebug>

class Customer : public QThread
{
protected:
    int m_need;
    volatile int m_current;
    QMutex m_mutex;

    void run()
    {
        bool condition = false;

        qDebug() << objectName() << "begin to apply money";

        do
        {
            m_mutex.lock();

            condition = (m_current < m_need);

            m_mutex.unlock();

            msleep(10);
        }
        while( condition );

        qDebug() << objectName() << "end (get enough money)";
    }
public:
    Customer(int current, int need)
    {
        m_current = current;
        m_need = need;
    }

    void addMoney(int m)
    {
        m_mutex.lock();

        m_current += m;

        m_mutex.unlock();
    }

    int backMoney()
    {
        int ret = 0;

        m_mutex.lock();

        ret = m_current;

        m_current = 0;

        m_mutex.unlock();

        return ret;
    }

    int current()
    {
        int ret = 0;

        m_mutex.lock();

        ret = m_current;

        m_mutex.unlock();

        return ret;
    }

    int need()
    {
        return m_need;
    }
};

class Bank : public QThread
{
protected:
    QList<Customer*> m_list;
    int m_total;

    void run()
    {
        int index = -1;

        qDebug() << objectName() << " begin: " << m_total;

        do
        {
            index = -1;

            for(int i=0; i<m_list.count(); i++)
            {
                if( m_list[i]->current() == m_list[i]->need() )
                {
                    qDebug() << objectName() << " take back money from " << m_list[i]->objectName() << " " << m_list[i]->need();

                    m_total += m_list[i]->backMoney();
                }
            }

            qDebug() << objectName() << " current: " << m_total;

            int toGet = 0x00FFFFFF;

            for(int i=0; i<m_list.count(); i++)
            {
                if( m_list[i]->isRunning() )
                {
                    int tmp = m_list[i]->need() - m_list[i]->current();

                    if( toGet > tmp )
                    {
                        index = i;
                        toGet = tmp;
                    }
                }
            }

            if( index >=0 )
            {
                if( toGet <= m_total )
                {
                    qDebug() << objectName() << " give money to: " << m_list[index]->objectName();

                    m_total--;

                    m_list[index]->addMoney(1);
                }
                else
                {
                    qDebug() << objectName() << " terminate: " << m_list[index]->objectName();

                    m_total += m_list[index]->backMoney();

                    m_list[index]->terminate();
                }
            }

            sleep(1);
        }
        while( index >= 0 );

        qDebug() << objectName() << " end: " << m_total;
    }
public:
    Bank(int total)
    {
        m_total = total;
    }

    void addCustomer(Customer* customer)
    {
        m_list.append(customer);
    }
};

int main(int argc, char *argv[])
{
    QCoreApplication a(argc, argv);

    Customer p(4, 8);
    Customer q(2, 3);
    Customer r(2, 11);

    Bank bank(2);

    p.setObjectName("P");
    q.setObjectName("Q");
    r.setObjectName("R");

    bank.setObjectName("Bank");

    bank.addCustomer(&p);
    bank.addCustomer(&q);
    bank.addCustomer(&r);

    p.start();
    q.start();
    r.start();

    bank.start();
    
    return a.exec();
}

参考资料：

1. QT实验分析教程