EEL 602 -
Operating Systems
Spring 2007
Indian Institute of
Technology Delhi, New Delhi
Assignment # 3
Multithreading
In a bank there are 5 counters, one for printing the passbook, one for making the cheque/DD and 3 for cash-withdrawal. There are independent queues for each counter and of finite length. The customers in the bank come for either;
(i) cash-deposit/withdrawal – 3 counters,
(ii) making cheque/DD or – 1 counter,
(iii) printing the passbook – 1 counter.
There is a guard which guides the customers to there respective queues. The customers coming for making cheque/DD or for printing the passbook cannot migrate to another queue. However, the customers coming for the cash-deposit/withdrawal can migrate to another queue so that the customer load on each window can be approximately the same. The customers coming for printing passbook or making cheque/DD are directed by the guard, but the guard schedules the customers coming for cash transaction one by one into the three queues, i.e. first into the cash-queue-1 then cash-queue-2 then cash-queue-3 and then cash-queue-1.
The distribution of customers coming for the service is given below. Since the bank can service limited number of customers at a time, on reaching the limit, service for a customer has to be finished, before next customer can enter into the bank. This can be done by the guard thread, which doesn’t allow more customers inside the bank.
The probability distribution of customer is as given below:
Customers Probability
Printing the passbook 1/4
Making cheque/DD 1/4
Making cash deposit 1/4
Cash withdrawal by cheque 1/8
Cash withdrawal from account 1/8
Use some kind of identification for the customers for the purpose they are coming.
The customer takes the following time at the teller window:
The cash deposit takes X amount of time.
The cash withdrawal with cheque takes Y amount of time.
The cash withdrawal from account takes Z amount of time.
The passbook printing takes A amount of time.
The cheque making takes B amount of time.
There is a time P after which the customers in the cash queues are rescheduled such that customer load are
- Equal (if possible) or
- customers_cash_queue1> customers_cash_queue2= customers_cash_queue3 or
- customers_cash_queue1= customers_cash_queue2> customers_cash_queue3.
Where, customers_cash_queue1 refers to number of customers in queue 1.
The customers who come first should be served first.
The bank may want to check the current scenario inside the bank at any instant of time. For the same the bank maintains a log book which has the transaction details of customers. The bank also keeps track of the number of customers in each queue.
Let us take A<X<Y<Z<B
Take P=1.5*Y
For our problem, take X=1.3*A, Y=1.7*A, Z=2.1*A, B=2*A.
The threads exchanging messages with each other can be visualized in the following manner.
Implementation:
Implement the above problem with threads such that the above given conditions are fulfilled. The tellers, the guards, queue-scheduler and the record printer (log book entry) should be implemented using POSIX threads. Create a thread pool of customers with different thread identification numbers and are sleeping initially. The customers in the thread pool are distributed according to the probability given above.
1. The thread pool has a constant number of 200 threads representing the customers which are all in sleeping state.
2. The guard thread awakes, lets say N (which can be set by the user) threads of customers from the pool by passing the message ‘awake’.
3. The awaken threads are scheduled to the respective queues by the guard.
4. The threads at the front of a queue send message to the teller for the service they want and go for sleep along with the teller for that amount of time (This sleep is simulating transaction here).
5. After the service time both teller and the customer wake up and this customer is removed from the queue and put back to the pool, due to which a new customer picked at random from pool of threads is scheduled into the queue by the guard in the fashion listed above.
6. The queue represents the thread identification of the customers which is rescheduled by the queue-scheduler thread at some interval of time.
7. The scheduling inside the queue is done by message passing between the scheduler thread and customer thread.
8. The thread id must be printed along with the transaction details by the record printer thread. The output has to go to a log-book (file).
At the end, provide the average service time of the teller during the simulation.
Deliverable:
Marks Distribution
Late submission ® -5 (Only one day late submission is allowed)
Failed/Improper demo ® -5
Code clarity ® you would get 0 in code clarity section if variable names are not upto the mark and the improper indentation or inadequate comments
Submission
Readme file: your login and how you submitted
The cpp fle: your file should be named as entry_no_assignment_no.c or entry_no_assignment_no.cpp
The tar file: your tar file should be named as entry_no_assignment_no.tar or entry_no_assignment_no.tar.gz
The tar file can be uploaded in assignment # 3 using this link. Please make sure that you upload the assignment only once. In case of multiple submissions, ONLY first submission will be used for grading.
Demo
You will have to show the demo on 10.10.1.5 machine. Please prepare your deliverables accordingly. The schedule posted for demo will not change. If you fail to demo your implementation as per schedule, your demo will not be rescheduled and ZERO will be awarded.
Deadline
The submission deadline for the assignment # 3 is 15/03/2007 [23:59 Hrs].
Questions
If you have any further questions relating to this assignment, you may contact the TA, Shashwat Agrawal.