#### 联系方式

• QQ：99515681
• 邮箱：99515681@qq.com
• 工作时间：8:00-23:00
• 微信：codinghelp

#### 您当前位置：首页 >> CS作业CS作业

###### 日期：2021-04-02 11:40

CS 5/7343 Spring 2021

Programming Homework 2

Due Date: 4/3 (Sat) 11:59 pm (No extensions). 5% bonus if you hand in by 3/31 (Wed) 11:59pm

The goal of the program is to provide experience on using synchronization tools (mutex) and gain some

Application – Auctions

This program will simulate auctions. The main process will be an auctioneer which will have different

type of items (denoted by integers 1 to k) up for auction. There may be more than one item available for

auction for each type.

Customers and tables

There are a set of tables in the auction house. (Each table should have an id, similar for what you do

with the threads in program 1). Each table will sit one customer. Customers arriving will be put into a

wait queue (there is no limit on the length of the queue). For any table without a customer, it will scan

the wait queue to see if there is a customer. If there is, the table will get the customer to sit there.

Customer are assigned to tables on a first-come-first-serve basis.

Each customer has three attributes:

? An ID (as an integer)

? The total amount of money the customer has (as a positive integer)

? A list of items that he/she is interested in, represented by a list of integers. (notice that the

customer may be interested in more than one item for a certain type, so the list of integers can

have duplicates). You can assume the list will only be of integers between 1 and k.

A customer can leave any time a round of auction has finished. However, when he/she has 0 dollars left,

he/she must leave. Also, if he/she has obtained all the items he/she is interested in, he/she must leave

immediately.

Each table is represented by a thread that is created in the beginning of the program. Once each thread

is created, it is NOT joined when a customer leaves. Rather, the thread will see if there is any customer

available on the wait queue and sit one of them if available. The thread only quits when the main

process tells it to.

Each round of auction

A round of auction starts when the auctioneer (main process) announce the next item to be auctioned.

Before the auctioneer do that, he/she check which table is occupied, and will only allow those tables

that are occupied at that time to take part in that round of auction.

Each customer will then check whether he/she is interested in the item. Then he/she will bid a random

amount (not more than the amount of money he/she has). A customer will bid 0 if he/she has no

interest in the item. Any bidding amount must be an integer.

If no one bid, the auction ends and the item is discarded.

If only one customer bids, the auction ends immediately and the customer that bid will win the item.

However, if more than one customer bids, then any customer that bids will be allowed to bid one more

time. He/she must either maintain the same amount or bid a higher amount. Notice that the customer

does NOT know the amount being bid by any customers. For this program, you can assume in this case

the customer will have a 50% chance of maintaining the same bid amount, and 50% chance of increasing

the bidding amount randomly. After that, the auctioneer will determine who get the highest bid, and

declare the winner. Notice that if there is a tie, no one win the auction and the item is discarded.

Once the round finishes, the auctioneer need to inform every table that the round is done, and inform

everyone who has won the auction (or nobody wins).

Input

Your program should read an input file. The input file have the following content:

? The first line consists of six integers

o The first number is the number of tables available. It should be at least 2.

o The second number is the number of types of items (k in the description)

o The third number is the number of customers in the input file. It should be at least 2.

o The fourth number is the maximum numbers of items that are auctioned. If all the

items are auctioned, the main process should tell all customers that it is quitting (and

ask everyone to leave). On the other hand, if there is no customer left, the customer

should quit).

o The fifth number denote whether the items to be auctioned is to be generated

randomly. If it is 1, then the items are generated in a cyclic sequence of 1, 2, 3, …, k, 1,

2, 3 ….. Any other number denotes that the items is to be generated randomly.

o The sixth number is 1 if you want to run the extra credit, otherwise it is ignored.

? Each subsequent line represents a customer. Each line has the following format:

o The first number is the ID of the customer (integer)

o The second number is the amount of money the customer has in the beginning (positive

integer)

o The third number denote the number of items that the customer is interested

o The rest of the line denote the type of each item that the customer is interested in (can

have duplicates)

You can assume the input file to follow the format. If the file input format is incorrect and your program

crash, you are not responsible.

Program Structure

Your program should have the following structure:

Main Process

Pre-process and initialization

Sit the initial customers

Repeat

Determine who can participate in the next round of auction

Select an item to auction

Auction the item

Send message to threads to denote who win/lose

Until all auction ends or all customers left

Print final information

Exit the program

Initialization

Repeat

If there is no customer

Find a customer to sit join this table

Repeat

Going through each round of auction

Until customer leaves

Until told by the main program to quit

Print final information

Quit

Output Requirements

Your program should print the following statements. The output is considered a major part of this

? When a customer is added to the customer queue, you should print the following statement

“Customer <ID of the customer> added to the queue”

? When a customer is assigned to a table, you should print “Customer <ID of the customer>

assigned to table <table ID>”.

? When a customer leaves, you should print “Customer <ID of the customer> leaves, winning <the

number of auction won> auctions, amount of money spent = <amount of money spent>,

amount of money left = <amount of money left>

? For each round of auction:

o After determining who is eligible for this round, the program should print “the following

customers are eligible for this round of auction : <list of ID of customers eligible>”

o After the item is selected, the program should print “Item of type <item type> up for

auction”

o When anyone makes a bid (at any round), the program should print “Customer <ID of

the customer> at table <table ID> bids <amount being bid>”.

o When a second round of bidding is required, the program should output “Second round

of bidding needed”

o At the end of each auction, the program should print “Customer <ID> won the auction,

with amount <bid amount>”. IF no one win the auction, it should print “No one won the

auction”

o At the end of the program, you should print: “total number of item auctioned : <# of

auctioned> item, total number of item successfully auctioned: <# of item that have

actually been won by someone>, total amount: <sum of the total amount paid for the

items>”

Bonus (20 points, Required for 7343 students, optional for 5343 students)

thread structure should be like that

Repeat

Int Delay = 100000;

Int Dtry = 1;

Int x;

For (int I = 0; I < Dtry; i++)

For (int j = 0; j < Delay; j++)

X = 1;

Generate a random number between 0 and 4

If (number generated == 4)

Generate a random customer and add it to the queue

Dtry = Dtry + 1

Else

If (Dtry >: 2) then Dtry = Dtry / 2; else Dtry = 1

until received a message from the main process to quit

quit

Comment bonus

You will get a maximum of 5% bonus for comments in your program. To get that 5% you need to:

? For each function, put comment to describe each parameter, and what is the expected output

? For each mutex/semaphore used, denote what is it used for

? For each critical section, denote when is the start and end of that critical section (you can name

your critical section in various ways to distinguish among them (if necessary))

? For loops and conditional statements that do non-trivial work (you decide what is non-trivial)

put comment before it describing what it does.

What to hand in

You should put all you source code into a zip file and upload the zip file to Canvas

【上一篇】：到头了
【下一篇】：没有了