Skip to main content

阿德莱德COMP SCI 3004/7064课业解析

By May 15, 2020No Comments

题意:学习调度算法来设计一个在线售票系统解析:系统会根据忠诚度将用户分成七个优先级,这就需要使用多级队列实现调度算法,只有当上一级优先队列为空时才轮到下一级的队列中的客户进行服务,相同优先级的按照时间顺序进行处理。当用户在当前优先级被处理三次后,其优先数会增加,当优先数大于三时,将会被移动至下一队列。同时需要注意低优先级的队列可能会出现的饥饿现象,就需要采取一定的策略进行分配。涉及知识点:调度算法,时间片,c++编程更多可加微信讨论微信号:lili_950826pdf全文COMP SCI 3004/7064 – Operating Systems Assignment 1DUE: 23:30pm, 16th Sept, 2019Important Notes• Handins:– The deadline for submission of your assignment is 23:30pm, 16th Sept, 2019.– For undergraduate students, you may do this assignment as a team of two students and hand in one submission per team.– For postgraduate students, you have to do this assignment individually and make individual submissions.– All implementations have to be done in C++.– You need to submit your source code using the web submission system. You should attach you and your partner’s name and student number in your submission.– Late submissions will attract a penalty: the maximum mark you can obtain will be reduced by 25% per day (or part thereof) past the due date or any extension you are granted.• Marking scheme:– 20 marks for 10 randomly generated tests (2 marks per test).If you have any questions, please send them to the student discussion forum. This way you can all help each other and everyone gets to see the answers.The assignmentThe aim of this assignment is to improve your learning experience in the process scheduling algorithms. You are required to design an online ticketing system for Coopers Stadium. Specifically, there are two seat sections: red section for public booking via this system; non-red section for private booking via hot line. Figure 1 shows the distribution of the seat sections.In the system, all the customers are grouped into seven priority classes(numbers), ranged from 1 to 7, according to their loyalty (accumulated points) to this ticketing system. A smaller priority number indicates a higher priority. All ticketing processes (purchase/cancellation) generated by a customer are assigned with the same priority number of that customer. To maximisethe system service performance, you are required to implement a scheduling algorithm using multi-level queue strategy with two queues: a high priority Queue 1 and a low priority Queue 2. Queue 1 has absolute priority over Queue 2. In other words, customer request in Queue 2 will only be processed if there is no customer in Queue 1. There is a threshold (=3) that isused to determine whether a customer should remain in Queue 1 (priority number ≤ threshold) or Queue 2 (priority number > threshold). Detailed actions in these two queues are listed below:Queue 1: This is the high priority queue(priority number ≤ threshold). Customers in this queue are treated in the way of combined Highest Priority First (HPF) and Weighted Round Robin (WRR — definition see below) on priority as follows: Select the highest priority customer(customers with the same priority are processed in their arrival order), and then process thiscustomer’s request for a ticket quota of N=\frac{weighted_time_quantum}{5 time units}5timeunitsweightedtimequantum tickets non-preemptively, thenmove this customer to the end of (the priority-subqueue of) Queue 1, where• weighted time quantum = (8 − customer’s priority number) × 10• 1 ticket costs 5 time units to process.• customer’s priority number is the customer’s current priority number.Weighted Round Robin (WRR): Given n processes P_1P1, P_2P2, …P_nPn, where process P_iPi has a weight w_iwi(1≤ i≤ n),W RR allocates P_iPi a weighted time quantum of w_iwi time units (i.e. a share of \frac{wi}{\sum_{i=1}^{n} w_i}∑i=1nwiwiCPU time). In this assignment, to simplify the implementation, a process’ weight is (8 − customer’s priority number), and customer’s priority number is the customer’s current priority number.Customers of the same priority are processed in their arrival order. The priority of a customer in this queue is decreased by one every 3 runs of this customer, i.e. when a customer has been processed 3 times under its current priority, its priority number will be increased by 1. When a customer’s priority number goes above the threshold (=3), it will be demoted from Queue 1 to Queue 2.For example, The priority number 2 in this queue is decreased by one run of this customer,i.e. once booked the first N =\frac{(8−2)×10}{5}5(8−2)×10=12 tickets its priority will become 3 and its ticket quota for the next run will book N =\frac{(8-3)×10}{5}5(8−3)×10=10(instead of 12 in its first run).Queue 2: This is the low priority queue (priority number > threshold). Customers in this queue are handled in Round Robin. That is, select the customer with First Come First Serve, regardless of their priorities. And process this customer’s request for a fixed time quantum of 20 tickets (= 100 time units) preemptively (to any a new arrival or promoted cust omer in Queue 1), then move this customer to the end of Queue 2. Note: once a running customer X in this queue is interrupted by a promoted or new customer from Queue 1, customer X will leave his/her time quantum immediately and the newly customer in Queue 1 will get the CPU to run. If the priority number of a customer in this queue goes equal to or below the threshold (=3) by the following Ageing mechanism, that customer is promoted from Queue 2 to Queue 1.Ageing mechanism Because Queue 1 has priority over Queue 2, and the HPF strategy is applied, starvation may occur. Namely, some customers in Queue 2 may never get to run because there is always a job with higher priority in Queue 1. To address 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 every 9th customer. That is, if a customer has waited 8 runs (the interrupted customer is counted as one run) of other customers since his/her last run, his/her priority number will be decreased by one. In this way, the priority number of each customer in Queue 2 decreases gradually in proportion to the waiting time since the last run.Note:• Order of simultaneous arrivals of same-priority customers:For customers arriving at the same time with the same priority to both queues, we assume their arrival order follows the increasing order of their customer IDs.• Order of new arrivals, preemption and promotion• For Queue 1, there may be three types of customers with the same priority arriving simultaneously at the end of (the priority subqueue of) Queue 1 — a new arrival customer A to Queue 1, a customer B with this priority of Queue 1 moved to the end of Queue 1 (by Weighted-Round-Robin), and a promoted customer C from Queue to Queue 1. In this case, their execution) order in Queue 1 will be Queue1 → A → B → C• For Queue 2, there may be two types of customers arriving simultaneously at the end of Queue 2 — a new arrival customer A to Queue 2 and a customer B of Queue 2 moved to the end of Queue 2 (by Round-Robin), their (execution) order in Queue 2 will be Queue2 → B → A . Note that a demoted customer from Queue 1 is regraded as customer B.TestInputWe have N customers, Each customer is identified by a line in the input file. The line describes the customer ID, arrival time(Can be divisible by 5), priority, age and the total tickets required. For example a1 5 1 0 50 describes a customer a1 which arrived at time 5 with priority number 1 and age 0, and requires 50 tickets.OutputThe output includes N+1 lines. it provides information of each customer execution. First line is string include ”name arrival end ready running waiting”. The next N lines (sorted by termination time) should report the customer
ID, arrival and termination times, ready time (the first time the system processes his/her request) and durations of running and waiting.Web-submission instructions• First, type the following command, all on one line (replacing xxxxxxx with your studentID):svn mkdir –parents -m ”OS”• Then, check out this directory and add your files:svn co assignment1svn add TicketBooker.cppsvn add StudentFile1.cppsvn add StudentFile2.cpp· · ·svn commit -m ”assignment1 solution”• Next, go to the web submission system at: to 2019, Semester 2, Operating Systems, Assignment 1. Then, click Tab ”Make Submission” for this assignment and indicate that you agree to the declaration. The automark script will then check whether your code compiles. You can make as many resubmissions as you like. If your final solution does not compile you won’t get any marks for this solution.• We will test your codes by the following Linux commands:g++ TicketBooker.cpp -o TicketBooker./TicketBooker input.txt>output.txt


Author admin

More posts by admin