银行家算法演示程序

source.cpp

// 银行家算法演示程序

#include "third-party-table_printer.h"

#include <cassert>
#include <ctime>
#include <vector>
#include <iostream>

using namespace std;
using TablePrinter = bprinter::TablePrinter;

const int NUMBER_OF_PROCESS = 5;  // 系统中进程的总量 P1, P2, P3, ..., Pn
const int TYPE_OF_RESOURCES = 3;  // 系统中资源的种类 R1, R2, R3, ..., Rn

const int RAND_MIN_NUMBER_OF_RESOURCE = 5;  // 随机生成的系统资源的下界
const int RAND_MAX_NUMBER_OF_RESOURCE = 20; // 随机生成的系统资源的上界


// 系统中各种资源的总量
// 
// eg. 系统中Ri资源的总量为TOTAL_RESOURCE[i-1]。
vector<int> TOTAL_RESOURCE(TYPE_OF_RESOURCES);


// 系统中进程对资源的最大需求量
// 
// eg. 系统中进程Pi对资源Rj的最大需求量为MAX_REQUEST[i-1][j-1]。
vector<vector<int>> MAX_REQUEST(NUMBER_OF_PROCESS);


// 随机生成系统资源数量以及进程对资源的最大需求量。
void init() {
	srand(time(nullptr));

	// 随机产生系统资源数量。
	for (int& res : TOTAL_RESOURCE) {
		res = rand() % (RAND_MAX_NUMBER_OF_RESOURCE - RAND_MIN_NUMBER_OF_RESOURCE + 1);
		res += RAND_MIN_NUMBER_OF_RESOURCE;
	}

	// 随机产生进程对资源的最大需求量。
	for (vector<int>& request : MAX_REQUEST) {
		request = move(vector<int>(TYPE_OF_RESOURCES));  // 用一维数组保存进程对每种资源的需求量。
		for (int i = 0; i < TYPE_OF_RESOURCES; ++i) {
			request[i] = rand();
			request[i] %= TOTAL_RESOURCE[i] + 1; // 进程对Ri的最大需求量不得超过资源的总量。
		}
	}
}


// 打印系统中进程的数量。
void printNumberOfProcess() {
	cout << "系统中进程的数量：" << NUMBER_OF_PROCESS << endl;
}


// 打印系统中的资源总量。
void printTotalResoure() {
	cout << "系统中资源的种类：" << TYPE_OF_RESOURCES << endl;
	cout << "系统中资源的总量：" << endl;

	TablePrinter tp(&std::cout);
	for (int i = 1; i <= TYPE_OF_RESOURCES; ++i) {
		tp.AddColumn(string("R") + to_string(i), 4);
	}

	tp.PrintHeader();
	for (const int res : TOTAL_RESOURCE) {
		tp << res;
	}
	tp.PrintFooter();
}


// 打印进程对资源的最大需求量。
void printMaxRequest() {
	cout << "进程对资源的最大需求量：" << endl;

	TablePrinter tp(&std::cout);
	tp.AddColumn("Px", 4);
	for (int i = 1; i <= TYPE_OF_RESOURCES; ++i) {
		tp.AddColumn(string("R") + to_string(i), 4);
	}

	tp.PrintHeader();
	for (int i = 1; i <= NUMBER_OF_PROCESS; ++i) {
		tp << (string("P") + to_string(i));
		for (auto& resourceNumber : MAX_REQUEST[i - 1]) {
			tp << resourceNumber;
		}
	}
	tp.PrintFooter();
}


// 当前系统中可供分配的资源
vector<int> availableResource(TOTAL_RESOURCE);


// 当前系统中进程占用的资源
vector<vector<int>> accquiredResource;


// isFinished[i]表示进程i+1是否运行完毕。
vector<bool> isFinished(NUMBER_OF_PROCESS);


// Request.first + 1 表示申请资源的进程编号
// Request.second 表示申请申请资源的数量
using Request = pair<int, vector<int>>;


// 随机挑选一个未完成的进程，并随机申请资源。
Request randomRequest() {
	int randProcess;
	do {
		randProcess = rand() % NUMBER_OF_PROCESS;
	} while (isFinished[randProcess]);  // 随机挑选一个未完成的进程

	vector<int> randResource(TYPE_OF_RESOURCES); // 进程对每类资源的需求数量。
	for (int i = 0; i < TYPE_OF_RESOURCES; ++i) { // 随机生成进程对每类资源的需求。
		// 进程申请的资源数量不得超过自己实际所需要的资源的数量。
		randResource[i] = rand() % (MAX_REQUEST[randProcess][i] - accquiredResource[randProcess][i] + 1);
	}

	return make_pair(randProcess, randResource);
}


// 打印申请资源的进程号以及申请资源的数量。
void printRequest(Request request) {
	cout << "进程" << to_string(request.first + 1) << "申请：";
	cout << "(" << request.second[0];
	for (int i = 1; i < request.second.size(); ++i) {
		cout << ", " << request.second[i];
	}
	cout << ")" << endl;
}


// 获取系统的一个安全序列。
vector<int> getSafeSequence() {
	vector<int> safeSequence;

	// 将全局作用域中的变量复制到局部作用域中。
	vector<int> availableResource = ::availableResource;
	vector<vector<int>> accquiredResource = ::accquiredResource;
	vector<bool> isFinished = ::isFinished;

	// 遍历进程列表。
	for (int tail = -1, p = 0; p != tail; p = (p + 1) % NUMBER_OF_PROCESS) {
		if (!isFinished[p]) {
			bool meetRequirement = true;

			// 判断当前系统系统资源能否满足对应进程的需求。
			for (int i = 0; meetRequirement && i < TYPE_OF_RESOURCES; ++i) {
				if (availableResource[i] < MAX_REQUEST[p][i] - accquiredResource[p][i]) {
					meetRequirement = false;
				}
			}

			if (meetRequirement) { // 若系统能满足进程对资源的需求。
				safeSequence.push_back(p);
				isFinished[p] = true; // 置进程完成标志。
				for (int i = 0; i < TYPE_OF_RESOURCES; ++i) { // 回收进程占用的资源。
					availableResource[i] += accquiredResource[p][i];
				}
				tail = p;
			}
		}
	}

	return safeSequence.size() == NUMBER_OF_PROCESS ? safeSequence : vector<int>();
}


// 打印安全序列。
void printSafeSequence(vector<int> sequence) {
	if (sequence.empty()) {
		cout << "当前系统中没有安全序列。" << endl;
	}
	else {
		cout << "当前系统中的一个安全序列为：";
		for (auto id : sequence) {
			cout << " " << (id + 1);
		}
		cout << endl;
	}
}


// 尝试进行资源分配。
void tryAllocate(Request request) {
	for (int i = 0; i < request.second.size(); ++i) {
		int process = request.first;
		int resource = request.second[i];

		assert(availableResource[i] - resource >= 0);
		assert(accquiredResource[process][i] + resource <= MAX_REQUEST[process][i]);

		availableResource[i] -= resource;
		accquiredResource[process][i] += resource;
	}
}


// 取消资源分配。
void undoAllocate(Request request) {
	cout << "拒绝进程" << to_string(request.first + 1) << "的资源申请。" << endl;
}


// 确认资源分配。
void commitAllocate(Request request) {
	cout << "允许进程" << to_string(request.first + 1) << "的资源申请。" << endl;
}


// 判断是否所有进程都运行完毕。
bool allProcessIsFinised() {
	for (bool finished : isFinished) {
		if (!finished) return false;
	}
	return true;
}


// 打印系统中可供分配的资源、进程已经取得的资源、进程还需要的资源以及进程是否已经完成。
void printSysmtemStatus() {
	// 打印系统中可提供分配资源。
	cout << "系统中可用分配的资源：";
	cout << availableResource[0];
	for (int i = 1; i < availableResource.size(); ++i) {
		cout << ", " << availableResource[i];
	}
	cout << endl;

	// 打印进程最大需求的资源、已经取得的资源和进程还需要的资源、以及进程的完成标志。
	TablePrinter tp(&std::cout);
	tp.AddColumn("Px", 4);
	tp.AddColumn("最大", 2 + 4 * TYPE_OF_RESOURCES);
	tp.AddColumn("取得", 2 + 4 * TYPE_OF_RESOURCES);
	tp.AddColumn("还需", 2 + 4 * TYPE_OF_RESOURCES);
	tp.AddColumn("完成？", 6);
	tp.PrintHeader();
	for (int p = 0; p <= NUMBER_OF_PROCESS; ++p) {
		tp << (string("P") + to_string(p));  // 进程名称

		string max, accquired, need;  // 进程最大需求的资源、已经取得的资源和还需要的资源
		for (int i = 0; i < TYPE_OF_RESOURCES; ++i) {
			if (!max.empty()) max += string(", ");
			max += to_string(MAX_REQUEST[p][i]);

			if (!isFinished[p]) {
				if (!accquired.empty()) accquired += string(", ");
				if (!need.empty()) need += string(", ");
				accquired += to_string(accquiredResource[p][i]);
				need += to_string(MAX_REQUEST[p][i] - accquiredResource[p][i]);
			}
		}

		string finishFlag = isFinished[p] ? "√" : "";  // 进程的完成标志
		tp << max << accquired << need << finishFlag;
	}
	tp.PrintFooter();

	// 打印安全序列。
	printSafeSequence(getSafeSequence());
}


// 运行银行家算法。
void run() {
	while (!allProcessIsFinised()) { // 当系统中还有进程没有结束运行时运行算法。
		auto request = randomRequest();  // 模拟进程向操作系统提出资源分配请求。
		printRequest(request);

		tryAllocate(request);  // 尝试满足进程的请求。
		auto safeSequence = getSafeSequence();  // 尝试获取一个安全序列。

		// 如果系统中存在一个安全序列，则满足进程的请求；
		// 如不存在安全序列，则否决进程的请求。
		if (safeSequence.empty()) {
			undoAllocate(request);
		}
		else {
			commitAllocate(request);
			printSysmtemStatus();  // 打印修改后的系统状态。
		}
	}
	cout << "所有进程运行完毕。" << endl;
}


int main() {
	init(); // 随机生成系统资源数量和进程需求。

	// 打印系统初始状态。
	printNumberOfProcess();
	printTotalResoure();
	printMaxRequest();

	run(); // 运行银行家算法。
}

third-party-table_printer.cpp

#include "table_printer.h"
#include <stdexcept>
#include <iomanip>
#include <stdexcept>

namespace bprinter
{
TablePrinter::TablePrinter(std::ostream *output, const std::string &separator)
{
    out_stream_ = output;
    i_ = 0;
    j_ = 0;
    separator_ = separator;
    table_width_ = 0;
    flush_left_ = false;
}

TablePrinter::~TablePrinter()
{
}

int TablePrinter::get_num_columns() const
{
    return column_headers_.size();
}

int TablePrinter::get_table_width() const
{
    return table_width_;
}

void TablePrinter::set_separator(const std::string &separator)
{
    separator_ = separator;
}

void TablePrinter::set_flush_left()
{
    flush_left_ = true;
}

void TablePrinter::set_flush_right()
{
    flush_left_ = false;
}

/** \brief Add a column to our table
 ** 
 ** \param header_name Name to be print for the header
 ** \param column_width the width of the column (has to be >=5)
 ** */
void TablePrinter::AddColumn(const std::string &header_name, int column_width)
{
    if (column_width < 4)
    {
        throw std::invalid_argument("Column size has to be >= 4");
    }

    column_headers_.push_back(header_name);
    column_widths_.push_back(column_width);
    table_width_ += column_width + separator_.size(); // for the separator
}

void TablePrinter::PrintHorizontalLine()
{
    *out_stream_ << "+"; // the left bar

    for (int i = 0; i < table_width_ - 1; ++i)
        *out_stream_ << "-";

    *out_stream_ << "+"; // the right bar
    *out_stream_ << "\n";
}

void TablePrinter::PrintHeader()
{
    PrintHorizontalLine();
    *out_stream_ << "|";

    for (int i = 0; i < get_num_columns(); ++i)
    {

        if (flush_left_)
            *out_stream_ << std::left;
        else
            *out_stream_ << std::right;

        *out_stream_ << std::setw(column_widths_.at(i)) << column_headers_.at(i).substr(0, column_widths_.at(i));
        if (i != get_num_columns() - 1)
        {
            *out_stream_ << separator_;
        }
    }

    *out_stream_ << "|\n";
    PrintHorizontalLine();
}

void TablePrinter::PrintFooter()
{
    PrintHorizontalLine();
}

TablePrinter &TablePrinter::operator<<(float input)
{
    OutputDecimalNumber<float>(input);
    return *this;
}

TablePrinter &TablePrinter::operator<<(double input)
{
    OutputDecimalNumber<double>(input);
    return *this;
}

} // namespace bprinter

third-party-table_printer.h

#ifndef BPRINTER_TABLE_PRINTER_H_
#define BPRINTER_TABLE_PRINTER_H_

#include <iostream>
#include <iomanip>
#include <vector>
#include <string>
#include <sstream>
#include <cmath>

namespace bprinter
{
class endl
{
};
/** \class TablePrinter
  Print a pretty table into your output of choice.
  Usage:
    TablePrinter tp(&std::cout);
    tp.AddColumn("Name", 25);
    tp.AddColumn("Age", 3);
    tp.AddColumn("Position", 30);
    tp.PrintHeader();
    tp << "Dat Chu" << 25 << "Research Assistant";
    tp << "John Doe" << 26 << "Professional Anonymity";
    tp << "Jane Doe" << tp.SkipToNextLine();
    tp << "Tom Doe" << 7 << "Student";
    tp.PrintFooter();
  \todo Add support for padding in each table cell
  */
class TablePrinter
{
public:
    TablePrinter(std::ostream *output, const std::string &separator = "|");
    ~TablePrinter();

    int get_num_columns() const;
    int get_table_width() const;
    void set_separator(const std::string &separator);
    void set_flush_left();
    void set_flush_right();

    void AddColumn(const std::string &header_name, int column_width);
    void PrintHeader();
    void PrintFooter();

    TablePrinter &operator<<(endl input)
    {
        while (j_ != 0)
        {
            *this << "";
        }
        return *this;
    }

    // Can we merge these?
    TablePrinter &operator<<(float input);
    TablePrinter &operator<<(double input);

    template <typename T>
    TablePrinter &operator<<(T input)
    {
        if (j_ == 0)
            *out_stream_ << "|";

        if (flush_left_)
            *out_stream_ << std::left;
        else
            *out_stream_ << std::right;

        // Leave 3 extra space: One for negative sign, one for zero, one for decimal
        *out_stream_ << std::setw(column_widths_.at(j_))
                     << input;

        if (j_ == get_num_columns() - 1)
        {
            *out_stream_ << "|\n";
            i_ = i_ + 1;
            j_ = 0;
        }
        else
        {
            *out_stream_ << separator_;
            j_ = j_ + 1;
        }

        return *this;
    }

private:
    void PrintHorizontalLine();

    template <typename T>
    void OutputDecimalNumber(T input);

    std::ostream *out_stream_;
    std::vector<std::string> column_headers_;
    std::vector<int> column_widths_;
    std::string separator_;

    int i_; // index of current row
    int j_; // index of current column

    int table_width_;
    bool flush_left_;
};

} // namespace bprinter

#include "table_printer.tpp.h"
#endif