文章目錄

• • 1 銀行家算法的分析與實(shí)現(xiàn)

1 銀行家算法的分析與實(shí)現(xiàn)

問(wèn)題描述：

• 研究一個(gè)銀行家如何將總數(shù)一定的資金，安全的借給若干個(gè)顧客，使顧客既能滿足對(duì)資金的需求，也使銀行家可以收回自己的全部資金，不至于破產(chǎn)。

一些限制條件：

• 每個(gè)顧客在借款前必須提前說(shuō)明所需資金總額。
• 每次借錢都是以一個(gè)單位進(jìn)行（如：一個(gè)單位為1萬(wàn)人民幣）。
• 顧客在拿到一個(gè)單位的借款前可能需要等待。
• 銀行保證顧客的等待時(shí)間是有限的（借或不借）。

算法示例：

算法策略：

• 將資金優(yōu)先借予資金需求較少的客戶。

應(yīng)用場(chǎng)景：

• 操作系統(tǒng)內(nèi)核中的進(jìn)程管理。
• 數(shù)據(jù)庫(kù)內(nèi)核中的頻繁事務(wù)管理。

Qt中的算法實(shí)現(xiàn)方案：

• 使用多線程機(jī)制模擬客戶和銀行。
• 銀行有限分配資源給最小需求的客戶。
• 當(dāng)客戶的資源需求無(wú)法滿足的時(shí)候：
  • 收回已分配的資源。
  • 強(qiáng)制結(jié)束線程。

銀行家算法常用于資源分配的場(chǎng)合：

• 解決的問(wèn)題：
  • 保證資源分配的安全性。
• 算法策略：
  • 優(yōu)先選擇需求量較少的客戶進(jìn)行資源分配。

編程實(shí)驗(yàn)：銀行家算法的實(shí)現(xiàn)

#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(); }

---

參考資料：

QT實(shí)驗(yàn)分析教程

總結(jié)

以上是生活随笔為你收集整理的银行家算法的分析与实现的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

如果覺(jué)得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。