Question

The SPF strategy can be proven to be optimal in the sense that it minimizes average response times. In this problem, you will demonstrate this result empirically by examining all possible orderings for a given set of five processes. Suppose five different processes are waiting to be processed, and that they require 1, 2, 3, 4 and 5 time units, respectively. Write a program that produces all possible permutations of the five processes (5! = 120) and calculates the average waiting time for each permutation. Sort these into lowest to highest average waiting time order and display each average time side by side with the permutation of the processes. Comment on the results.

Answer 1

Answer:

Program;

#include <iostream>

#include <vector>

#include <algorithm>

using namespace std;

int main() {

vector<int> order = {1, 2, 3, 4, 5}; // initial job order

vector<pair<float, vector<int> > > data; // each pair is {average waiting time, jobs order}

int c = 0;

do {

// calculate average waiting time for the order

float avg_wait = 0;

for(int i = 0; i < order.size() - 1; ++i) {

avg_wait += order[i];

}

avg_wait /= 5;

data.push_back(make_pair(avg_wait, order));

} while(next_permutation(order.begin(), order.end()));

// sort according to average wait time

sort(data.begin(), data.end());

// display the result

cout << "avg_wait_time\tpermutation\n\n";

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

cout << data[i].first << "\t\t";

for(int j = 0; j < 5; ++j) {

cout << data[i].second[j] << " ";

}

cout << endl;

}

Explanation:

See attachment for code screenshot