# xv6 Doubts

Q1. Is it mandatory to have the mp2 changes here?

## 1) Modified Priority Based Scheduler

Q1. Could you please explain the significance of the 'set priority' function and also how to check if our PBS scheduling is functioning correctly or not?

Q2. Since the scheduler is non-preemptive, a process once scheduled will run till completion. So the number of times the process has been scheduled will always be zero, so how can it be used to break ties?

Q3. Initially, before implementing the `set_priority` function, the priorities of all processes should be the same and the tiebreaker will only be the start time of the processes i.e. without the `set_priority` function, Priority-Based Scheduling (PBS) should function as First-Come First-Served (FCFS). As for FCFS, since you mentioned that both of the following outputs are acceptable, for PBS as well, both outputs should be acceptable naa ??

Process 5 finished Process 0 finished
Process 6 finished Process 1 finished
Process 7 finished Process 2 finished
Process 8 finished Process 3 finished
Process 9 finished or Process 4 finished
Process 0 finished Process 5 finished
Process 1 finished Process 6 finished
Process 2 finished Process 7 finished
Process 3 finished Process 8 finished
Process 4 finished Process 9 finished

where, Processes 0, 1, 2, 3 and 4 are I/O bound processes and Processes 5, 6, 7, 8 and 9 are CPU-bound processes

Q4. Do we need to make any changes to schedulertests.c and usertests.c for PBS scheduling ?

Q5. Till when does the default value of RBI holds for processes which are not scheduled first? Basically if I am setting the RBI value to default as 25 then when do I start calculating the RBI according to the given formula?

Q6. If the scheduler is non-preemptive, wont process just get scheduled once? why are we using this as a tie breaker at all? I cant see a case scenario where this would be needed

Q7. Running time has been defined as "the total time the process has been running since it was last scheduled". Since PBS is non-preemptive, a process runs until it is complete. Then, what is the point of running time in RBI calculation, if we are going to reset it when it is no longer runnable anyway? Even if the current running process's priority goes up, there is no tangible benefit since there is no preemption. Please clarify.

Q8. `In case two or more processes have the same priority, we use the number of times the process has been scheduled to break the tie.` Should a process which has been scheduled more number of times be given higher priority, or one which has been scheduled fewer number of times? Or are we allowed to make any assumption regarding this?

Q9. If this scheduler is non-premptive, then all the processes arriving at the same time (such as in schedulertest.c) will be done in an FCFS fashion, what is the point of keeping a dynamic property then?

Q10. Why do we need a RTtime (running ticks counter) to change the dynamic property/rbi? If the process is non pre-emptive then while scheduling any process its RTtime will always be zero (since its non premptive, the process will always complete once given CPU without yeidling it and thus wont be scheduled again and we wont update its RTtime). We will end up never using the rbi/dp to schedule the process and it will just end up happening in an FCFS manner this way.

Q11. For RBI, what does default value of 25 mean i.e under what circumstances does a process qualify to have its RBI set to the default value ?

Q12. (Following Q9) So basically if 10 process arrive at the same time, instead of the FCFS fashion, we implement them using Priority, but if they arrive at different times it is simply FCFS?

Q13. How can we modify schedulertest to make morethan one process arrive at the same time?

Q14. How many CPUS will this be tested on?

Q15. (With reference to the answer to Q4) by a *lower priority*, do you mean a lower static priority value or a higher static priority value?

Q16. Who will provide the input for the setpriority system call?

Q17. WTIME is defined as `The total time the process has spent in the ready queue waiting to be scheduled.`. Is this also intended to be `since the process was last scheduled`, like STIME and RTIME, or is it since the process was created? Should we make this an assumption?

Q18. The set_priority function should reschedule if the new priority of process becomes higher than original priority. Does this mean that if a 'process X' was scheduled by PBS and is currently running, and if 'process X' calls set_priority to make priority of 'process Y' higher than before, then should 'process X' yield the CPU at that very point and allow for the scheduler to find highest priority process again, or should it wait for 'process X' to end?

Q19. Is PBS supposed to function as FCFS if setpriority isn't called?

Q20. In case the priority of the process increases(the value is lower than before), then rescheduling should be done.In this line prirority mean static or dynamic ?

Q21. Do we need to modify makefile to add scheduler flag or do we just overwrite the default round robin code?

Q22. Could you provide more details about the context in which we encounter the 'test reparent: FAILED' error?

Q23. What is the significance of default value of RBI because we will have to update RBI before scheduling the process hence before scheduling the process for the first time we will update the RBI value hence the initial value will be overwritten and hence won't be of any use.

Q24. If a process P1 ran for 2 seconds, got yielded but got scheduled immediately again and then is currently running at its 3'rd second after re-scheduling. Will the rtime for this process at the current point of time be 3 seconds (the time it has been using the CPU for since being rescheduled) or 5 seconds? (since it was scheduled immediately again do we treat it as it never stopped running? 2 + 3 = 5)

Q25. A process is scheduled based on the dynamic priority which depends on the live runtime, waittime and sleeptime. So it is necessary to recalculate the RBI and then dynamic priority everytime before checking processes for scheduling. Hence i don't see any need to store RBI in the `struct proc`.
The function set_priority says `calling this system call will also reset the Recent Behaviour Index (RBI) of the process to 25`. But this says to store it in struct proc, though anyways i don't find any case when it will come to use. So how will this affect the scheduling?

Q26. For PBS,what parameters will be there in graph

Q27. In continaution to Q24, yield is called every tick, does that mean that the rtime of a process will only either be 0 or 1?

Q28. If the priority of 2 processes is the same then the document says the number of times the process is scheduled is the tie breaker. Do we prioritize the process scheduled less or the other way round?

Q29. Now that PBS is preemptive, could some clarification be provided on when to yield (yield at every tick makes RTime go to 1 and be reset to 0) and when to reset RTime, STime and WTime?

Q30.

If the tie remains, use the start-time of the process to break the tie(processes with lower start times should be scheduled further).

Does this mean that processes which arrived earlier should be scheduled earlier in case of a tie with other parameters?

Q31. (Follow up to Q18) Can we choose not to call yield() immediately, since yield() will be called once every tick anyway?

Q32. (Follow up to Q31) By this, I mean that whenever set_priority is called, we DON'T call yield(). This is because, yield() will be called once every tick anyway, so current process can be preempted then. Is this implementation of set_priority acceptable? (Writing this as a query because of the answer to Q18).

Q33. (Follow up to Q17 and Q27) If rTime is always either 0 or 1, and wTime is the time that the process has been waiting since the process was created, then RBI will be 0 most of the time (because wTime is large and so -wTime is a large -ve value, and 3*rTime is either 0 or 1.). This means that DP depends only on SP most of the time because DP = min(SP + RBI, 100). This would make RBI redundant. What are we expected to do in this case? (In this case, because RBI is 0 most of the time, and DP = SP, if SP is the same for all processes, then tie breaking would take place by number of times the process was scheduled => our scheduler is a glorified RR).

Q34. (Follow up to Q30) Pls clarify 'earlier' or 'further'? If creation times of p1 and p2 are 10 and 20 ticks respectively, then should p1 be scheduled or p2?

Q35. Please clarify the need for rbi in this question. Most of the time it will be 0 so scheduling is only based on sp. what do we even do in report regarding this?

## 2) Copy On Write fork (CoW)

Q1. Do we need to make a report for CoW? (steps of implementation)

Q2. Do we have to keep a flag for CoW while running make or is it fine to edit the existing xv6 implemenation code?

Q3. Should CoW be implemented only for user processes or do we need to implement it for kernel and init process as well?

Q4. Does textwrite usertest work for CoW?

# Concurrency Doubts
Q1. We don't necessarily have to have all our code in just ```1.c``` and ```2.c```, right?

## 1) Cafe Sim

Q1. What should we do if a customer who has placed his/her order, leaves the cafe (because his/her tolerance time is up) before some barista gets assigned to the order (because all the baristas were busy at the moment), then do we still need to process that order (when some barista gets free) or do we need to ignore that order and move on to process the next order (of some customer who is still present in the cafe)(Can we assume that the order will still be prepared and the coffee will just get wasted)?

Q2. Can we assume that every time; the barista with the lowest index which is available will serve the next sequenced order?

Q3. If 2 customers arrive at the same time then can we serve any one of them first?

Q4. Adding on to Q1, in case a barista is free to take an order but we can calculate that under no circumstance will the order be completed before the customer's tolerance is over, do we still allocate that barista to the order? And if we do, does the barista stop making the order once the customer leaves?

Q5. According to the answer to Q1, shouldn't the sample data have 0 coffee wasted, as there is no barista free to prepare order for customer 3, and customer leaves before any coffee is prepared?

Q6. In the example given shouldn't the statement "Customer 3 arrives at 3 second(s)" be printed before "Customer 2 orders Espresso", since the order is placed 1 second after the arrival of customer; Therefore because customer 2 and 3 arrives at the same time ,i.e., 3 seconds, so arrival of customer 3 should be printed before the order of customer 2 and 3.

Q7. Can the statements that are to be printed at the same second (say time = 7 seconds in the example given), be printed in any order?
In the example the statements are printed in the below order

Barista 2 completes the order of customer 2 at 7 second(s)
Customer 2 leaves with their order at 7 second(s)
Customer 3 leaves without their order at 7 second(s)

Can they be printed in any other order? Like:

Customer 3 leaves without their order at 7 second(s)
Customer 2 leaves with their order at 7 second(s)
Barista 2 completes the order of customer 2 at 7 second(s)

Q8. Is this a valid output?

Customer 3 arrives at 3 second(s)
Customer 1 arrives at 0 second(s)
Customer 2 arrives at 3 second(s)
Customer 1 orders a Cappuccino
Barista 1 begins preparing the order of customer 1 at 1 second(s)
Customer 2 orders a Espresso
Customer 3 orders a Espresso
Barista 2 begins preparing the order of customer 2 at 4 second(s)
Barista 2 successfully completes the order of customer 2
Customer 2 leaves with their order at 7 second(s)
Barista 2 begins preparing the order of customer 3 at 7 second(s)
Customer 3 leaves without their order at 7 second(s)
Barista 1 successfully completes the order of customer 1
Customer 1 leaves with their order at 11 second(s)

1 coffee wasted

Q9. Is wait time of a customer who never got his coffee considered while calculating average wait time?

Q10. Can we assume that the customer i will always come before or at the same time as i + 1?

Q11. Do we have to simulate it realtime like the code should take 11 seconds to exit if the entire process of cafe takes 11 seconds?

Q12. What do you mean by "Coffee prep time is not part of waiting time"? Does this mean that waiting time is only the time between their arrival and a barista starting to prepare their order?

Q13. Say a customer arrives at t = 10 seconds, and his coffee takes 3 seconds to make, but he has a tolerance time of 3 seconds. Now, he is supposed to wait until t = 13 seconds for his coffee to be made. Will he then leave at t = 14 seconds? Assuming the barista starts preparing the coffee at t = 11 seconds, his coffee would also be done preparing at t = 14 seconds, so, is he supposed to leave without picking up his coffee (because his patience had already run out by then)?
While accounting for average wait time, do we count that he has waited for 3 seconds (tolerance time), or that he has waited for 4 seconds (time at which he left - arrival time)?

Q14. (Ref A5) Is there a compulsion that ```Barista 2 begins preparing the order of customer 3 at 8 second(s)``` and not ```... at 7 second(s)```? Since ```Barsita 2``` is not occupied after ```Barista 2 completes the order of customer 2 at 7 second(s)```, they can start at ```7 second(s)``` also.

Q15. Can a customer arriving at 't' be given a coffee prepared before 't+1'?

Q16. In the output provided in the answer to Q5 , shouldn't the second last statement be ```Barista 2 completes the order of customer 3``` instead of customer 2?

Q17. Are we allowed to assume that all the input will be provided in one go? Basically, are we allowed to assume that input will be redirected from a file? (so that the code works as expected, when you depend on time from a clock).

Q18. Are we permitted to use ```pthread_tryjoin_np```?

Q19. Can we assume that the input will be given in the sorted order of arrival times?

Q20. As per the sample input given in the MP3 website, both customer 2 and customer 3 come at same time, currently in my code it is random whether customer 3 or customer 2 coffee is prepared first. Is it necessary to have that only less index should be made the coffee if both arrive at same time. I dont think it is required.. I dont wanna touch and break the code again :(

Q21. Is this output valid?

Customer 1 arrives at 0 second(s)
Customer 1 orders a Cappuccino
Barista 2 begins preparing the order of customer 1 at 1 second(s)
Customer 3 arrives at 3 second(s)
Customer 3 orders a Espresso
Customer 2 arrives at 3 second(s)
Customer 2 orders a Espresso
Barista 1 begins preparing the order of customer 2 at 4 second(s)
Barista 1 completes the order of customer 2 at 7 second(s)
Customer 2 leaves with their order at 7 second(s)
Barista 1 begins preparing the order of customer 3 at 8 second(s)
Customer 3 leaves due to tolerance at 9 second(s)
Barista 2 completes the order of customer 1 at 11 second(s)
Customer 1 leaves with their order at 11 second(s)
Barista 1 completes the order of customer 3 at 11 second(s)
Number of coffee wasted: 1

Q22. Would we be losing any marks if Barista x picks up a customer's order even when Barista x-1 is free (like in the output of Q21 above)?

Q23. Can a customer have 0 tolerance time? If so, is their waiting time always 0?

Q24. When is our program supposed to terminate? Is it after all customers leave, or after all baristas are done preparing their orders, max() of both?

Q25. Do we HAVE to use multi threading to do this? I don't see why we need to use seperate threads, as to have the events print in chronologic order, we need to make sure that each thread is at a specific point of execution and that defeats the purpose of multi threading.

Q26. Can we assume that the time to make any coffee is non-zero?

Q27. Given example statement:

Barista 2 is done with the order at 7 seconds, but the customer 3 arrived much earlier. Even then the Barista 2 is preparing 1 second later. So can we assume that the Barista always takes 1 second after completion of an order before moving onto the next order?
Q28. Can we do it without semaphores?

Q29. Can you explain what you meant in Q13 2nd part

Q30. Is is neccesary to print the output in the order of time of completion?

Q32. Can we use sleep?

Q33. 
1)Customer 2 arrives at 3 second(s)
Customer 2 orders an Espresso
Barista 2 begins preparing the order of customer 2 at 4 second(s)
Customer 2 leaves without their order at 4 second(s)

customer arrives at 3
 at (3+1) what should print
 
2)the movement customer's order gets barista, coustomer had already left .So will barista begins prepairng?
3)does always index wise arrival time is non-decreasing ?

Q34. can we use condition variable along with semaphore?

Q35. Can we use sem_timedwait instead of sleep?

Q36. Can we finish these concurrency questions using only semaphores (so, for mutex, you just use a binary semaphore)?

Q37. Can we use time.h?

Q38. It's not compulsory to make the program run for 11 seconds, if the simulation runs for 11 "seconds" right? To be clear, I'm asking whether it's alright for the simulation to print and finish as soon as possible, i.e. no sleeps, and it just runs to completion.

Q39. As a follow up to Q22, is it valid if, supposing 3 orders can be taken at a particular time t, out of the free baristas, the ones with the lowest 3 numbers are arbitrarily assigned those 3 orders? To be clear, I am asking if it is ok if, when there is more than one order and more than one free barista, it is ok if the lowest barista does not get the order which was placed earliest and has the lowest customer index, but instead gets one of the other orders (since there are more than one). If there is a single order, then the barista with the lowest index is guaranteed to take it.

Q40. If a customer doesn't get its order, does the wait time of that customer equal to its tolerance time or the time it waited for a barista to get assigned?

Q41. Can we use `pthread_setaffinity_np` from `pthread.h`? And Should the simulation also be possible on a single-core CPU?

Q42. According to the reply to question 1, the barista need not prepare the order of a customer that has already left. 
1. If the barista does not prepare the order of a customer that has already left, then how is their wait-time calculated? ```Time of leaving - Time of arrival```?

2. In my current implementation, if I choose that a barista prepares the coffee of a customer that has already left, can I consider the wait-time as 

Q43. Is continuation creation and deletion of threads allowed? (Like creating and deleting the same threads in a while loop)

Q44. Can we use sem_open instead of sem_init, as the latter does not work on mac ?

Q45. Is this a Valid Output ?

Customer 1 arrives at 0 second(s)
Customer 1 orders an Cappuccino
Barista 1 begins preparing the order of customer 1 at 1 second(s)
Customer 2 arrives at 3 second(s)
Customer 2 orders an Espresso
Customer 3 arrives at 3 second(s)
Customer 3 orders an Espresso
Barista 2 begins preparing the order of customer 2 at 4 second(s)
Barista 2 successfully completes the order of customer of 2 at 7 second(s)
Customer 2 leaves with their order at 7 second(s)
Barista 2 begins preparing the order of customer 3 at 8 second(s)
Customer 3 leaves without their order at 8 second(s)
Barista 1 successfully completes the order of customer of 1 at 11 second(s)
Customer 1 leaves with their order at 11 second(s)
Barista 2 successfully completes the order of customer of 3 at 11 second(s)

1 coffee wasted

Also if we have Barista 1 and Barista 2 both waiting , Can we randomly wake up a thread or do we need to wake up only Barista 1 ?

Q46. A25: "You must print the simultaneous events as an when they occur/complete."
A13: "No, it depends on what order you check events happening at every second."
So, are we doing it simultaneously or not?
Also, do we need separate threads for all producers and consumers? Or threads for different events will do?

Q47. (Follow up to Q45) would we be penalized if both Barista 1 and Barista 2 are free, we wake up Barista 2 first but Barista 2 sees that Barista 1 is free and so non-deterministically wakes up one of the free baristas, and this keeps going on until Barista 1 is woken up?

Q48. Can we assume that Customer i is given before Customer i+1 while giving the input?

Q49. Referring to ans for Q14, will we be penalised for implementing in a way that Barista will accept the order at 7 sec itself?

Q50. Going by A2: "Also, any other reasonable assumptions being made must be mentioned in the report.", I have simulated each barista using an independent thread that atomically checks the list of customer requests (as if they are going to the counter in a real world cafe), starts preparing for the lowest customer id and unlocks the list (leaves the counter).
However, this was nullified by A45 that asks us to enforce an ordering on baristas too. Can we please ignore this? This was not mentioned in the specification and kills off the last spec of concurrency? The baristas are anyway identical in their abilities, unlike the ice cream machines.

Q51. So wait time for a customer that enters at 0, order starts getting prepared at 1, gets order and leaves at 5 is 1? (Given the formula in A40)
Does it not make more sense for it to be 0 sec instead of 1?
It makes more sense for wait time to be ((barista assigned time) - (cutomer arrival time + 1)).

Q52.Real Life: One customer gives order,and leaves coz tolerance time .Why would he inform barista to cancel order as he have already paid Money.
Barista should still make order and cofee gets wasted.
Is above implementaion valid

Q53 Can we use sched_yield()?

Q53 if customer leaves at

## 2) Ice Cream Parlor Sim

Q1. We are required to print the statements when the machine starts and stops working - in orange color - but we can't print orange text in C, so which color should we use then?

Q2. It is mentioned in the question that each topping takes time t_t to be put onto the ice-cream but input of t_t is not provided! Should we just assume that each topping can be put instantaneously?

Q3. What if all K places in the parlour are filled and another customer arrives, should he/she be ignored and sent back or put in some sort of waiting queue until there is space in the parlour?

Q4. Can a customer have 2 or more toppings of the same type? Ex:

vanilla candy candy
chocolate caramel caramel

Q5. There is no input for how many customers will come, do we need to handle it by checking for till when input is being given? Also if a customer comes when K places are filled, what message to print then for sending them away?

Q6. Follow up to Q5, what is should we assume to be signal for end of input?

Q7. I am finding it difficult to interpret the assumptions, lets say a customer has 2 orders, O1 and O2. All of below questions are in context to this one customer only.

- What is the partial order and complete order? (is it O1/O2 and (O1 and O2)?).
- And lets say only O1 can be placed by machine M1 due to its end time (there are no other machines) , will the order still be placed? Or does a customer only place orders when both O1 and O2 are placeable on a single machine?
- Between O1 and O2 (say both are placeable by M1) how do we decide which one to place first?
- Is it necessary for both O1 and O2 (Orders of a single customer) to be fulfilled by only M1? (is it possible that O1 is placed on M1 and O2 is placed on some M2?)
- Assumption 3 states that partial orders should be rejected completely (by a machine I suppose?) but the next assumption starts with "if a customer leaves..." . How is this possible? If an order is taken completely by a machine (since it was not rejected) which has the ingredients, why would the customer leave due to ingredient shortage?

Adding some more constraints on the problem (fixed toppings per order/maximum orders per customer) will be highly appreciated as it would help with taking the input, the language of assumptions seem very confusing as well :/

Q8. If the customer has given an order of multiple ice-creams and if all the ingredient requirements are fulfilled but only a few of them can be completed due to unavailability of machines , in such a case do we have to complete the ice-creams which can be made and make the customer wait till the parlour is closed or do we have to reject the order , (rejecting the order on the basis of time left to operate for the machines would be something difficult to implement because there might be cases where when you're checking whether the order can be completed or not , other ice creams might be waiting which may take up the time of machine)??

Q9. Can we assume that the input of arrival of customers is ordered in terms of their time of arrival (in non-decreasing order)?

Q10. (Same as question 17 from Cafe Sim Doubts).

Q11. Can you provide us with the input format of the topping, we need both t_t and q_t. But when taking input, it is only written q_t. Also what should I assume when there is no input given for any one of the variables?

Q12. Is the topping quantity fixed? If there are 4 cherry toppings, will it be 4 per machine or every machine has access to only 4 cherries?

Q13. Suppose all ingredient requirements are fulfilled and a customer orders 2 ice-creams say IC1 and IC2. If the machines are able to make IC1 completely but IC2 waits till the parlour is closed then do we have to print the statements of IC1 (like Machine x starts/completes preparing...... IC1 ) or do we have to print if only if we are sure that the entire order of that customer will be completed. Also will the machine start preparing the order IC1 in such a case ( cause IC2 is not going to be prepared and order of customer will be partially completed)??

Q14. After the customer's order is done and they pick it up and leave instantaneously at say, time = t seconds, will their spot become free from t+1, like it does when they leave with an unfulfilled order?

Q15. Like in the Cafe Sim, does the machine have to wait for 1 second before it starts preparing the next order, after it is done preparing its previous order?

Q16. It is stated ```If a customer leaves due to ingredient shortages, they leave the second they’re informed (at t), and their spot becomes free from the next second i.e. t+1.```. Are customers informed of ingredient shortages by the machine when it is available to take their order ? Or do we check for shortages right after the customer places the order?

Q17. Are we required to serve lower indexed customers first, before moving onto higher indexed customers? For example, say 1, 2, 3, 4 are customer indices. Now, let the capacity of the parlour be 3. After 1 has picked up their order and left, let 4 enter the next second. Can our serving order be 1, 4, 2, 3 then? Or, does it strictly have to be 1, 2, 3, 4? (as in, would we be losing *any* marks at all for implementing the former correctly?)
Q.18 In the provided example after second wont the machine takes another order even though it can't complete?

Q19. As a follow up to Q6, would the sample input with the end of input signal be,

2 3 2 3
0 7
4 10
vanilla 3
chocolate 4
caramel -1
brownie 4
strawberry 4
1 1 2
vanilla caramel
chocolate brownie strawberry
2 2 1
vanilla strawberry caramel
(this is an extra newline indicating end of input)

Q20. Continuation of A7, How do we check if a customer will be serviced or not? A machine will start taking up orders of a customer only if all of its partial orders can be completed as well as the machine does not time out while preparing the partial order. But these partial orders may be completed at different machines and it is not possible for a machine to pick a partial order of a customer without the information if all of its orders will be completed or not.In the output example itself,why would M2 prepare O2 of C1 instead of preparing the order of C2?

Q21. Explain Q17 ,Q18

Q22. Do we have get the first available machine (earliest available index) to serve a customer, or is any valid available machine that can serve a customer acceptable? For example, if both, machines 2 and 3 can serve customer 2, then can I non-deterministically choose either 2 or 3? Or, do I have to choose 2?

Q23. Are there marks for writing the implementation details in the report?

Q24. Is taking input from a file allowed? (it was not explicitly approved in A17)

Q25.
given both customer arrive at 0
2 3 2 3
0 7
0 10
vanilla 3
chocolate 4
caramel -1
brownie 4
strawberry 4
1 1 2
vanilla caramel
chocolate brownie strawberry
2 2 1
vanilla strawberry caramel

Machine 1 has started working at 0 second(s)
Customer 1 enters at 1 second(s)
Customer 1 orders 2 ice creams
Ice cream 1: vanilla caramel
Ice cream 2: chocolate brownie strawberry
Machine 1 starts preparing ice cream 1 of customer 1 at 2 second(s)
Customer 2 enters at 1 second(s)
Customer 2 orders 1 ice cream(s)
Ice cream 1: vanilla strawberry caramel
Machine 2 has started working at 4 second(s)
Machine 2 starts preparing ice cream 1 of customer 2 at 4 second(s)

is last line possible in given test??

Q26. Continued to A20. But the ingredients change with time right? While M1 took up a partial order O1 it did not reject the complete order since ingredients were there (for both O1 and O2). But later on it might happen that the order O2 did not get enough ingredients when a (possibly M1 or possibly some other machine) machine tried to serve it, but by this point of time M1 has already taken up O1 but there are not enough ingredients for O2. This results in a partial order completion. Does this mean every machine tries to take the orders of the same customer? (O1 and O2 are partial orders of customer C1)

Q27. Continuation to Q26, if every machine tries to complete the same order, M1 does not know if the partial order O2 can be fulfilled by M2 (since it is a different machine, and it might be giving an order right now and may be free'd later). Suppose M1 took up O1 (there are enough ingredients and time) but when M2 tries to take O2 it finds out that it cant fulfil it on time. M2 expires, and M1 after completing O1 did not have enough time to fulfil O2. Now O2 will never be served but we partially ordered O1. This again results in partial order and there is no way to prevent this

Q28. As a follow up to Q22, is it considered incorrect if a machine with a number higher than the lowest free machine picks up an order? I have already implemented it in a way such that it minimizes partial orders and I don't see why this is a necessity :(

Q29. Can we assume that if a customer orders icecreams O1 and O2, and there are sufficient ingredients for both, but currently machine is free only for O1, then the ingredients required for O2 are reserved until any machine is freed for O2? As in, while customer is waiting for machine to be free for creating O2, the ingredients required for creating O2 cannot be used by any furthur arriving customers?

Q30. If a customer leaves due to ingredient shortages, they leave the second they’re informed (at t), and their spot becomes free from the next second i.e. t+1.
spot means ?
1.next coustomer takes +1 sec to come, even if k is sufficiently large
Or this is correct
2.machine allocated takes +1 sec to restart

Q31. A customer A places order of icecreams I1 and I2. Ingredients are sufficient for both. If O1 is being created by machine 1 and machine 2 is currently occupied. Machine 2 becomes free, but the time left for the machine is not enough to complete I2, but another customer B places an order I3 that machine 2 can fulfill, but making that order will require the ingredients that were to be used for I2 (ingredients are sufficient only for one out of I2 or I3). Then should it be assumed that
1: Taking an order for customer A reserves the ingredients required for I1 AND I2 (even though only one is being currently prepared), thus leading to order of customer B being rejected
OR
2: As long as an order has not begun preparation (even though it has been accepted), the ingredients required for the order can still be used by furthur arriving customers, leading to customer 3's order being fulfilled.

Q32. Consider a customer orders 2 icecreams IC1 and IC2, with time required for preparation as 5 and 3 sec respectively. Both machines M1 and M2 are available but M1 can work for 4 more sec and M2 can work for 6 more sec. Here, does the lower indexing of machines and icecream need to be satisfied? Is it possible that M1 prepares IC2 and M2 prepares IC1?

Q33. If a customer arrives at a time when parlour already has K customers (max), then do we have to print anything? If they leave instantly, then can we take it to mean that they do not enter at all and there is no need to print anything?

Q34. Please correct me if I am wrong, a customer arrives and assuming no machines are free, the customer waits (provided capacity permits). When the machine becomes free, the customer is served to. If the ingredients are not available then the customer goes away. My doubt is, customer will get to know of the availability of ingredients only when a machine is free right?

Q35. Just to clarify - ```If a machine starts working at time t, and a customer was already waiting since some time <t, the machine can instantly start preparing their order.```. If the arrival time of the customer is less than the time at which the machine is available to take the customer's order, then the machine can instantly start preparation?

Q36. Given, "If a customer’s order can only be partially completed, they must be rejected completely, no part of their order should waste ingredients." suppose a customer orders two ice creams, IC1 and IC2. IC1 is prepared, then customer gets notified that IC2 is having ingredient shortage. This means, whole order is rejected. what does "no part of their order should waste ingredients" mean? should IC1 also be undone (ingredients restored)?

Q37. Suppose, M1 and M2 are available. M1 stops working in 2 seconds from now, M2 stops working in 3 seconds from now. Assume that there exists a customer whose order takes 3 seconds to prepare. Now, we check with M1 first, and M1 can't prepare it (so, M1 doesn't take the order up). Do we have to check with M2 next, and accept the order, and prepare it?

Q38. Customer A orders IC1 with 5 sec prep time, Customer B orders IC2 with 3 sec prep time. Machine M1 can work for 4 more seconds and Machine M2 can work for 6 more seconds. Can we assign Customer A to M1 and Customer B to M2 (because of indexing, but leading to order of customer A not being fulfilled) or do we have to serve in such a way that both get served (if possible)?

Q39. Continuing Q36, do we need to check initially before preparing IC1 that preparation of IC2 is possible or not or should we prepare IC1 and when we start preparing IC2 and observe unavailability of ingredients/machines we should conclude that we do not have to prepare IC2 and send customer with IC1 only. In short, do we have to prepare IC1 or not?

Q40. Since, we can have atmost k customers in the shop and we are assuming that in input the arrival time is given in sorted order do we need to consider the customers with index greater than k. Or we are saying that it might be possible that the number of customers given initally are greater than k but there will never be the case when a customer arrives and the number of customers at that moment are greater than or equal to k .i.e. few customers already got their order and they left.

Q41. Suppose we have 2 customers C1 and C2.We have three machines M1 ,M2 and M3. C1 has 2 orders O1 and O2 and the C2 has 1 order.
Now initially when C1 arrives the ingredients are sufficient for the O1(so the customer is not rejected) and O2 and M1 has sufficient time for the completion of O1.
So M1 starts with O1. But M2 doesnt have enough run time to process O2 (and also M1 has sufficient time to only process O1) . Hence O2 waits. Meanwhile C2 arrives and the current number of ingredients are such that either O2 or O3 will be processed.
M2 has sufficient time for processing O3 so it will start with it. Now when M3 starts which has suficient time for O2 but the ingredients to be used for it were used by O3.
So now C1 has partial order. So do we have to reject the C1 with Partial order made or reject C2 on arrival by precomputing that the ingredients will be needded by O2 which will be processed later.

Q42.Your answeres to Q26, Q27, Q34 and Q36 all contradict.
Consider the scenario -
T = 0
toppings t1, t2 quantity left is 2,2
Two iceream machines M1 and M2. M1 is free and has 7 sec till it closes (closes at T=7). M2 is occupied till T=5 and closes at T=11.
Say C1 arrives and orders IC1, IC2 at T=0.
IC1 - prep time 3 sec, Toppings - t1 and t2
IC2 - prep time 5 sec, Toppings - t1 and t2
Say C2 arrives orders IC3 at T=4
IC3 - prep time 3 sec, Toppings - t1 and t2
Now, -

# since there are 2 t1 and 2 t2, both orders can be ideally fulfilled for C1
M1 starts preparing IC1 at T=0
M1 done preparing IC1 at T=3
# t1, t2 left - 1,1
# At T=4, M1 is free, M2 is still occupied in some previous order, C2 orders
# IC2 of C1 cannot be prepared by M1 due to closing time and also not by M2 as its still occupied
# As you say toppings cannot be reserved, then IC3 can be prepared and so C2 order can be fulfilled
M1 starts preparing IC3 at T=4

At T=5, what happens?
M2 gets free from its previous order, and it can ideally prepare IC2, but now there is ingredient shortage as quantity is 0 for both toppings. There is no way to check this scenario beforehand(because you mention no reservation), so entire order of C1 couldn't be rejected. If C1 gets rejected at T=5, then IC1 goes wasted(Q.36).
Clarify what exactly should happen **properly with a detialed flow in this case** .

Q43. What happens here is, Machine 2 takes up the order of Customer 2 instead of the Customer 1 (as given in example output). This leads to customer 1 being not serviced and customer 2 leaving with order completed(this is exactly opposite of the example given). Output given below.

Machine 1 has started working at 0 second(s)
Customer 1 enters at 1 second(s)
Customer 1 orders 2 ice cream(s)
Ice cream 1: vanilla caramel
Ice cream 2: chocolate brownie strawberry
Machine 1 starts preparing ice cream 1 of Customer 1 at 2 second(s)
Customer 2 enters at 2 second(s)
Customer 2 orders 1 ice cream(s)
Ice cream 1: vanilla strawberry caramel
Machine 2 has started working at 4 second(s)
Machine 2 starts preparing ice cream 1 of Customer 2 at 4 second(s)
Machine 1 completes preparing ice cream 1 of Customer 1 at 5 second(s)
Machine 1 has stopped working at 7 second(s)
Machine 2 completes preparing ice cream 1 of Customer 2 at 7 second(s)
Customer 2 has collected their order(s) and left at 7 second(s)
Machine 2 has stopped working at 10 second(s)
Customer 1 was not serviced due to unavailability of machines
Parlour Closed

Is this valid??

Q44. Suppose in the start before a shift of a machine starts and a customer arrives at this time , then will this customer wait for the machines to start or it will just leave the ice cream parlour ?

Q45. Are the machines in the input given in sorted order of start times? (Does a machine with lower index have lower start time?)

Q46. Answer to Q36 mentions 'either' so which one is to be done? I mean can we make an assumption that we will waste the ice creams prepared so far for a particular customer if all the icecream orders of that customer can't be prepared or we should check for if ingrediants are available for ALL ORDERS of ice creams at the beginning and reserve the ingrediants?
In the latter case if we reserve the ingrediants then there might be a possibility that the machines might not be available in the future which will lead to ingredients wastage. Hence in any case ingredients will be wasted.

Q47. Reffering to A36, If IC1 goes wasted, that means a partial order of a customer has been taken up without completing the complete order, is that not allowed? Moreover, The website literally says ``` no part of their order should waste ingredients.``` If IC1 goes to waste we have essentially wasted ingredients. We have also voilated the condition that we should not take up partial orders which can not be completed in this case. (I have read Q42 and making an assumption for such a case seems like a huge deal because it makes no sense.)

Q48. Suppose M1(index 1) nd M2(index 2) are preparing orders, M1 will be free in say,3 secs and M2 in 2 secs. Suppose a new order comes, which machine will take the order assuming both can finish the order.

Q49. Are we allowed to use pthread barriers?

Q50. Is it fine to assume that a machine can only work on a single order at a given second? Thus, if a machine finishes preparing an icecream at 5 seconds, it will starting preparing the next icecream at 6 seconds. [Note: If a machine starts at t seconds itself, it can take an order that came at < t seconds, as mentioned in the question]

Q51. What do you mean by "acceptance" of an order and a machine "taking up" an order?
For example, suppose a customer arrives at t = 10s and they place an order. At this moment, say no machines are free. Do we still check if their order can even be prepared (by seeing if an ingredient shortage case already exists for their order), and turn them away IMMEDIATELY (not waiting for a machine to do so) if such a case arises? Is this what "accepting" an order means? (WITHOUT wasting ingredients.)
Later on, if above scenario satisfies (their order can be prepared because of the ingredients available currently), but later on while actually preparing parts of their order, a machine determines that an ingredient shortage has now occurred and thus they are turned away (AFTER wasting ingredients)? Is this what a machine "taking up" an order means?

Q52. The problem statement says `If all limited ingredients are depleted, the parlor closes for the day.` Say the ingredient list is such,

0 7
icecream1 3      
topping1 -1      
topping2 -1             
topping3 -1      
topping4 1    
< customers >

Say Customer C1 orders icecream1 with topping4. So the question wants us to close the parlour (as soon as C1's order is prepared) even if there is a possibility of serving more customers who have asked only for infinite toppings? Is it not more correct to close parlour on depletion of finite toppings only when no infinite toppings are present in the first place?

Q53. Is it valid to assume that once a machine finishes an order it can take up another order in the same second if that order was placed before the machine became free?

Q54. Building on the answer of Q51. when a machine picks up an icecream to `determine an ingredient shortage has occurred`, does the machine check:
A) sufficient ingredients for that ice cream only,
B) sufficient ingredients for all icecreams that no machine has prepared/is preparing yet, OR
C) either implementation is fine.

Q55. The answers to Q15 and Q53 contradict each other. Please resolve. We have implemented based on the answer to Q15, because it was answered ages ago.

Q56. Suppose, at t=8 seconds, Machine 3 is done preparing an order, and can pick up another order, say, Order 2 of Customer 3. Now,
say, Machine 5 can also pick this order up. Depending on which is processed first, two outcomes are possible:
If the finishing of Machine 3's order is processed first in the same timestamp, then Machine 3 picks up this Order 2 of Customer 3.
Else, Machine 5 picks up Customer 3's Order 2 first and then finishing of Machine 3's order is processed.
Is either implementation acceptable? Would we be penalised if the latter happens (because non-deterministically, when multiple events happen in the same timestamp and all these events are independent, wouldn't it make sense for us to let any happen first?)

Q57. When do we have to shut down the parlor upon all limited ingredients being completed? After processing the order that caused the limiting ingredients to be completed or instantly?

Q58. In continuation to Q57, is it a valid assumption to instantly close the parlor and not finish the orders in progress? Because waiting for the orders to finish, some other customer may arrive and there wouldn't be ingredients for them.

Q59. Please provide a test case involving wasted ingredients.

# Please answer quickly as deadline is in a few hours

## Report doubts

Q1. Could you please tell us what all we need to include in the report from each specification? An exhaustive list would be appreciated, so that we don't miss out on anything. Also, where do we have to put the report (which directory)? Should it be a Latex file, or is Markdown fine?