代写algorithms、Java/C/C++编程代写、代做C/C++/Python语言程序留学生

日期：2018-10-05 09:54

The aim of this assignment is to improve your learning experience in the process scheduling

algorithms. You are required to design an online service system for a large ITS enterprise to

handle customer requests. In the system, all the customers are grouped into six priority classes,

ranged from 1 to 6, according to their membership status. A larger priority number indicates

a higher priority. To maximise the system service performance, you are required to implement

a scheduling algorithm using multi-level queue strategy with three queues: : a high priority

Queue 1 (customers with priority number 6 and 5), a medium priority Queue 2 (priority number

4 and 3) and a low priority Queue 3 (priority number 2 and 1). Queue 1 has absolute priority

over Queue 2 and Queue 3, and Queue 2 has absolute priority over Queue 3. In other words,

customer requests in Queue 2 will be processed only if there is no customer in Queue 1, and

customer requests in Queue 3 will be processed only if no customer is in Queue 1 and Queue 2.

There are two thresholds (=5, 3) that are used to determine whether a customer should remain

1

in Queue 1 (priority ≥ 5), in Queue 2 (3 ≥ priority < 5) and Queue 3 (priority < 3), respectively.

Detailed actions in these three queues are listed below:

此任务的目的是改善您在流程安排中的学习体验

算法。您需要为大型ITS企业设计在线服务系统

处理客户要求。在系统中，所有客户分为六个优先级，

根据其会员身份，范围从1到6。较大的优先级数字表示

更高的优先级。要最大化系统服务性能，您需要实施

使用具有三个队列的多级队列策略的调度算法::高优先级

队列1（优先级为6和5的客户），中等优先级队列2（优先级编号

4和3）和低优先级队列3（优先级号2和1）。队列1具有绝对优先级

在队列2和队列3上，队列2的优先级高于队列3.换句话说，

只有队列1中没有客户时，才会处理队列2中的客户请求

仅当队列1和队列2中没有客户时，才会处理队列3中的客户请求。

有两个阈值（= 5,3）用于确定客户是否应该保留

1

在队列1（优先级≥5），队列2（3≥优先级<5）和队列3（优先级<3）中。

下面列出了这三个队列中的详细操作：

Queue 1: This is the high priority queue. Customers in this queue are treated in the way of

combined Highest Priority First (HPF) and Round Robin. That is, select the highest priority

customer (customers with the same priority are selected in their arrival order), and process

this customer’s request for a time quantum of 5 time units non-preemptively, then move this

customer to the end of a sub-queue (in same priority) of Queue 1. The priority of a customer

in this queue is decreased by one every 5 runs of this customer, i.e. once having been serviced

25 time units overall in Queue 1.

Queue 2 and Queue 3: These are the medium/low priority queue. Customers in these queues

are handled in Round Robin. That is, select the customer with First Come First Serve, and

process this customer’s request for a time quantum of 10 time units for Queue 2 and 20 time

units for Queue 3 preemptively as described below, then move this customer to the end of its

queue. If the priority of a customer in these queues reaches the threshold (5 in Queue 2 and

3 in Queue 3) by the following Aging mechanism, that customer is promoted from Queue 2 to

Queue 1 (or from Queue 3 to Queue 2). There’s one more thing need to be noted: The priority

of a customer in Queue 2 is decreased by one every 2 runs of this customer, i.e. once having

been serviced 20 time units overall.

队列1：这是高优先级队列。此队列中的客户受到了处理

结合最高优先级（HPF）和循环。也就是说，选择最高优先级

客户（在到货订单中选择具有相同优先级的客户）和流程

这个客户要求非抢先的5个时间单位的时间量，然后移动这个

客户到队列1的子队列（相同优先级）的末尾。客户的优先级

在该队列中，每5次运行该客户减少一次，即一次服务

队列1中总共25个时间单位。

队列2和队列3：这些是中/低优先级队列。这些队列中的客户

在Round Robin中处理。也就是说，选择先到先服务的客户，然后

处理此客户对队列2和20时间的10个时间单位的时间量的请求

队列3的单位抢先如下所述，然后将此客户移至其末尾

队列。如果这些队列中的客户的优先级达到阈值（队列2和队列中的5）

3在队列3）中通过以下老化机制，该客户从队列2升级到

队列1（或从队列3到队列2）。还有一件事需要注意：优先级

队列2中的客户每2次运行减少一次，即一次拥有

整体服务20个单位。

Preemption: Once a running customer in Queue 2 (or Queue 3) is interrupted by a new

arrival customer from Queue 1 (or from Queue 2), this customer will leave its time quantum

immediately and moved to the end of its queue.

Aging: Because Queue 1 has priority over Queue 2 and Queue 3, and the HPF strategy is

applied, starvation may occur. That is, some customers in Queue 2 and Queue 3 may never

get to run because there is always a customer with higher priority in Queue 1. To solve the

starvation issue, you must implement a mechanism which ages each customer. This need not be

done every time a customer run as this will slow the system down, but say once after every 7

customer runs. That is, if a customer has waited 7 runs of other customers since its last run, its

priority number will be increased by one. In this way, the priority of each customer in Queue 2

and Queue 3 increases gradually in proportion to the waiting time since the last run.

Note: If at time t, there are three customers with the same priority: a new arrival customer

A to Queue 1, a customer B moved to the end of Queue 1, a promoted customer C from Queue

2 to Queue 1, their order will be A → B → C. Same rule applies to Queue 2 and 3 regardless

of the priority.

抢占：一旦队列2（或队列3）中正在运行的客户被新的中断

从队列1（或从队列2）到达客户，该客户将留下其时间量

立即移动到队列的末尾。

老化：因为队列1优先于队列2和队列3，所以HPF策略是

应用，可能会发生饥饿。也就是说，队列2和队列3中的某些客户可能永远不会

得到运行，因为在队列1中始终有一个客户具有更高的优先级。解决问题

饥饿问题，你必须实施一个老化每个客户的机制。这不一定是

每次客户运行时都会这样做，因为这会降低系统速度，但每隔7次就会说一次

客户运行。也就是说，如果一个客户自上次运行以来已经等待了7次其他客户，那么就是这样

优先号将增加一个。这样，队列2中每个客户的优先级

并且队列3与自上次运行以来的等待时间成比例地逐渐增加。

注意：如果在时间t，有三个具有相同优先级的客户：新到货客户

A到队列1，客户B移到队列1的末尾，来自队列的升级客户C.

2到队列1，他们的顺序将是A→B→C。同样的规则适用于队列2和3，无论如何

优先权

Test

Input

Each customer is identified by a line in the input file. The line describes the customer ID,

arrival time, priority, age and the total time units required. For example s1 3 1 0 50 describes

a customer s1 who arrived at time 3 with priority 1 and age 0, and requires 50 time units.

Output

The output provides information of each customer execution. The line starts with the customer

ID, priority, arrival and termination times, ready time (the first time the system processes its

request) and durations of running and waiting.

测试

输入

每个客户都由输入文件中的一行标识。 该行描述了客户ID，

到达时间，优先级，年龄和所需的总时间单位。 例如，s1 3 1 0 50描述

客户s1在时间3到达，优先级为1，年龄为0，需要50个时间单位。

产量

输出提供每个客户执行的信息。 该行从客户开始

ID，优先级，到达和终止时间，就绪时间（系统首次处理它）

请求）和运行和等待的持续时间。