Mini Project 3 Answers

# xv6 Doubts Q1. Is it mandatory to have the mp2 changes here? A1. [HG] No. ## 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? A1. [HG] It is mostly self explanatory. The syscall will change the static priority of the process which will then alter the DP of the process. Use `usertests` and `schedulertest` to test your implementations. 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 ?? A3. [HG] Yes, it will depend on the schedulertest file you use. Q4. Q4. Do we need to make any changes to schedulertests.c and usertests.c for PBS scheduling ? A4. [HG] Yes, **schedulertests will have to be changed** to icorporate the setpriority system call. Call the function so as to set a lower priority for IO bound processes. 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? A8. [HG] Make an assumption. 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? A9. [HG] As mentioned above, set a priority for each process. This will then be used to determine which process gets scheduled first. 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. A10. [SA] Correct, given the slight change in the requirement of the scheduler to be preemptive: you would now end up using RBI/DP to schedule the processes. Q13. How can we modify schedulertest to make morethan one process arrive at the same time? A13. [HG] Try and take inspiration from the forkfork() function in usertests.c. Q14. How many CPUS will this be tested on? A14. [HG] 2 CPUs. 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? A15. [HG] Lower static priority. 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? A17. [HG] Since the process was created. 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? A18. [HG] Yield at the point that point and find highest priority process. 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 ? A20. [HG] Dynamic. Q21. Do we need to modify makefile to add scheduler flag or do we just overwrite the default round robin code? A21. [HG] Modify makefile. 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) A24. [HG] Rtime will either be 0 or 1. 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? A27. [HG] Yes 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? A28. [HG] Make an assumption and list it in the README. 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? A29. [HG] The default `yield()` is fine. If you want to modify its functioning, please go ahead but do mention it clearly in the README. 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? A30. [HG] Yes. Q31. (Follow up to Q18) Can we choose not to call yield() immediately, since yield() will be called once every tick anyway? A31. [HG] Q29 answers it hopefully. ## 2) Copy On Write fork (CoW) Q1. Do we need to make a report for CoW? (steps of implementation) A1. [SA] No. Q2. Do we have to keep a flag for CoW while running make or is it fine to edit the existing xv6 implemenation code? A2. [SA] It is fine to edit the existing implementation, no need to keep a flag. # Concurrency Doubts ## 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)? A1. [JB] If a customer has already left before a barista becomes available to service their order, the order need not be prepared. Q2. Can we assume that every time; the barista with the lowest index which is available will serve the next sequenced order? A2. [JB] Yes, I recommend you serve the one with the lower index first. Also, any other reasonable assumptions being made must be mentioned in the report. Q3. If 2 customers arrive at the same time then can we serve any one of them first? A3. [JB] Serve the one with the lower index 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? A4. [JB] Yes, you still allocate the order, and the coffee goes wasted. No, a barista never stops mid making a coffee. 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? A5. [JB] Agreed, that was an edge case, the example will be updated to ``` 2 2 3 Espresso 3 Cappuccino 10 1 Cappuccino 0 15 2 Espresso 3 6 3 Espresso 3 5 ``` ``` Customer 1 arrives at 0 second(s) Customer 1 orders a 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 completes the order of customer 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 9 second(s) Barista 1 completes the order of customer 1 at 11 second(s) Barista 2 completes the order of customer 2 at 11 second(s) Customer 1 leaves with their order at 11 second(s) 1 coffee wasted ``` 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. A6. [JB] If a customer arrives at time t, they place the order at time `t`, and the coffee starts getting prepared at time `t+1`. This is mentioned in the assumptions. 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? A7. [JB] Independent statements can be printed in any order. But statements like barista completing an order => a customer picking it up and leaving should be printed in order. However, barista completing an order (of customer a) => barista starts preparing order (of customer b) => a customer (a) picking their order up and leaving are independent, and can thus be printed like this. Basically, relative ordering of dependent statements should be maintained for each second. Q8. Is this a valid output? A8. [JB] No. You're supposed to print a simulation- meaning it needs to go in increasing order of seconds, starting from 0 seconds. Q9. Is wait time of a customer who never got his coffee considered while calculating average wait time? A9. [JB] Yes. Q10. Can we assume that the customer i will always come before or at the same time as i + 1? A10. [JB] Yes. 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? A11. [JB] Yes. 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? A12. [JB] Yes, that's exactly what it means. Q13. 1. 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? 2. 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)? 3. 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)? A13. [JB] 1. A customer arriving at time `t` with tolerance `x` will print leave message at `t + x + 1` seconds. 2. No, it depends on what order you check events happening at every second. If you `complete orders pending that second` -> `checking customers' patience`, the coffee would not get wasted. [Correct, better implementation] If you `checking customers' patience` -> `complete orders pending that second`, the coffee would get wasted. [Incorrect, inefficient implementation] 3. Answered in A12. 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. A14. [JB] That implementation also works, but for simplicity it might be easier to have only one action per timestep. Therefore, for uniformity please follow the sequence in the example given. Q15. Can a customer arriving at 't' be given a coffee prepared before 't+1'? A15. [JB] No, a customer always requires a fresh coffee. Good idea though, maybe as an exercise you could implement a time frame for previous coffees to be given to new customers. 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? A16. [JB] Correct, that is a typo. Apologies. 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). A17. [JB] Yes, all input will be given in one go. Q18. Are we permitted to use ```pthread_tryjoin_np```? A18. [JB] No. Q19. Can we assume that the input will be given in the sorted order of arrival times? A19. [JB] Yes. 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 :( A20. [JB] The ideal answer would need to give preference based on ascending order of indices (if the timestamp is the same). However, partial marks will be awarded as long as the basic idea is correct. Q21. Is this output valid? A21. [RS] This output will recieve partial marks. Ideally the first free barista should take up the order.(Counting from Barista 1 onwards) 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)? A22. [RS] You will get partial marks for the above output. Q23. Can a customer have 0 tolerance time? If so, is their waiting time always 0? A23. [RS] Tolerance time will always be > 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? A24. [RS] Program is supposed to terminate after all ongoing events complete, i.e. after all the customers leave AND after all baristas are done preparing their orders. 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. A25. [RS] You must print the simultaneous events as an when they occur/complete. Multi threading is the way to implement this using threads that ensures no deadlock or starvation of resources. However, please implement the solution that you feel best works for the problem. To state it clearly, you must use multithreading. You're basically simulating this situation using threading. You're implementing multitasking using multiple threads. That is, executing several actions(each action is a thread) that take place at the same time, that use the same common pool of resources. Q26. Can we assume that the time to make any coffee is non-zero? A26. [RS] Yes that is a valid assumption. Q27. Given example statement: Barista 2 completes the order of customer 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) 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? A27. [RS] As mentioned in the question 'If a customer was already waiting, once a barista finishes their previous order, say at time t, they can start making the order of the waiting customer at time `t+1`. So, yes what you are assuming is given in the question. Q28. Can we do it without semaphores? A28. [RS] No, you must implement your solution using semaphores and mutex locks. Q29. Can you explain what you meant in Q13 2nd part A29. [JB] Say you are on timestep `t`. At this second, the coffee of customer 1 is supposed to finish preparing. You need to do 2 actions for the customer to get their coffee (once a barista has already begun preparing it): `[1]` barista finishes preparing `[2]` customer picks up coffee (involves customer checking for his coffee) If you do `[2]` -> `[1]`, the customer sees their coffee isn't prepared at `t`, barista puts it at `t`, but after the customer already checked => customer only obtains their coffee at `t+1` => they leave at `t+1`. If you do `[1]` -> `[2]`, the customer sees their coffee is ready at `t` => they can leave at `t`. So we see how implementing things in a specific order is more efficient. Keep in mind this is a simplification to help you understand the impact of certain design choices. Q30. Is is neccesary to print the output in the order of time of completion? A30. [RS] The idea is for n seconds of running of tasks, at every nth second whatever task is completed at the nth second is printed. Q31. Can we use only condition variable + lock ,without semaphores ? A31. [RS] As its mentioned to use semaphores, please use them as well in your solution. Q32. Can we use sleep? A32. [RS] Yes. Q34. can we use condition variable along with semaphore? A34. [RS] Yes. 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 ? A33. [JB] 1) At (3+1) in this case, you print the completion of the order, followed by that customer leaving with it. 2) If you check for customer's patience first, then assign a barista to a pending order => if a customer has left in that second, their order does not get prepared. 3) Yes, we will give input in increasing order of arrival time. Q35. Can we use sem_timedwait instead of sleep? A35. [RS] Yes. Q36. Can we finish these concurrency questions using only semaphores (so, for mutex, you just use a binary semaphore)? A36. You can implement with whatever you feel is enough using semaphores and/or mutex locks. There's no problem with implementing mutex locks as binary semaphores, if you feel that's the best implementation. Q37. Can we use time.h? A37. [RS] Yes. 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. A38. [JB] You will *not be penalised* if the simulation prints and finishes as soon as possible, as long as the output is correct. It just wasn't the intended implementation since it's a 'simulation'. 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. A39. [JB] The ideal implementation (without much difficulty too) should have the lowest index barista taking the lowest index order. Therefore if this does not happen, not 100% marks can be awarded; However, as long as the simulation works logically we will be lenient. 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? A40. [JB] If a customer gets their coffee: wait time = total time spent in cafe - prep time of coffee If a customer does not get their coffee: wait time = total time spent in cafe (since prep time of coffee is 0, as no coffee received) Q41. Can we use `pthread_setaffinity_np` from `pthread.h`? And Should the simulation also be possible on a single-core CPU? A41. [JB] No, and no. 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 ```Time when preparation starts (even if the customer has left) - Time of arrival```? A42. [JB] 1. Already answered in A40. 2. You cannot have a barista prepare the coffee of a customer that has already left. Q43. Is continuation creation and deletion of threads allowed? (Like creating and deleting the same threads in a while loop) A43. [JB] You can do anything as long as the library and functions are allowed. Q44. Can we use sem_open instead of sem_init, as the latter does not work on mac ? A44. [RS] Sure. Q45. Is this a Valid Output ? 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 ? A45. [RS] As mentioned in assumptions 'they collect their order only if it gets done on or before t + tol.' So the customer has to wait till atleast 3+5 = 8 seconds here to collect their order if it gets completed, and can leave at the 9th second if order is not completed. So your output is not valid. Again here priority of Baristas based on ascending order of index must be implemented. So you must wake up Barista 1 only, else partial marks will be awarded. 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." 1. So, are we doing it simultaneously or not? 2. Also, do we need separate threads for all producers and consumers? Or threads for different events will do? A46. [JB] 1. All events occuring at `t` seconds must be printed before the events occuring at `t+1` seconds. 2. Implementation is up to you. Do remember you need to give implementation details in the report. 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? A47. [JB] The implementation is not incorrect, albeit inefficient. But you won't lose marks if there isn't too much overhead. Q48. Can we assume that Customer i is given before Customer i+1 while giving the input? A48. [JB] Already answered in A33. 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? A49. [JB] Since it has been stated that you have to do it this way, if you follow another implementation, your answer would differ from the expectation. But because it is not incorrect, you will still receive partial marks. 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. A50. [JB] Doubts doc adds to the specifications, and is the same as moodle clarifications. Therefore, you are expected to check the doubts doc when questions are answered. Since your implementation makes logical sense, it shall earn partial marks. 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)). A51. [JB] The questions section is meant to more open ended, thus there can be different ways to answer, so if your calculations are backed up by explainations, it should be fine. 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 A52. [JB] No, it is not valid. Q53. Can we use sched_yield()? A53. [JB] No, you may not. ## 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? A1. [JB] You can print in orange using custom colour codes. This is one shade of orange: `\e[38;2;255;85;0m`. 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? A2. [JB] Yes, 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? A3. [JB] The customer sees that the parlour is full, and goes away. Q4. Can a customer have 2 or more toppings of the same type? Ex: ``` vanilla candy candy chocolate caramel caramel ``` A4. [JB] No, all toppings for a particular ice cream will be unique. 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? A5. [JB] Yes, you can handle it by checking for till when input is being given. If a customer comes when K places are filled, they never enter the parlour, thus you do not need to print anything. You can keep a track of how many such cases were there and print them after `Parlour Closed`. Q6. Follow up to Q5, what is should we assume to be signal for end of input? A6. [JB] You can assume `\n\n` (new line character twice in a row) will terminate the input. Q7. 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? A7. [JB] - Partial order: either O1 or O2 get prepared, but not both. Complete order: both O1 and O2 get prepared. - If a machine is scheduled to stop working, i.e. you don't have enough time to make that order, it does not get prepared by that machine. It waits for another machine with enough time to prepare it. Multiple machines can prepare the orders of a customer, customers are not restricted to any machines. - Ascending order of index. - Answered. - If O1 cannot be prepared, but O2 can, the customer is still rejected because they cannot be completely serviced. 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 (...)? A8. [JB] If ingredients unavailable -> reject. If machine unavailable -> wait till machine available. Q9. Can we assume that the input of arrival of customers is ordered in terms of their time of arrival (in non-decreasing order)? A9. [JB] Yes. Q10. (Same as question 17 from Cafe Sim Doubts). A10. [JB] Same as answer 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? A11. [JB] There is no input for `t_t`, there was confusion regarding that in Q2 as well, you can assume that every topping can be put instantaneously. All other variables will be provided, just like in the example. 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? A12. [JB] In your example, there would be 4 cherries in total, i.e. 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)?? A13. [RS] In such a case, the machines will start preparing the order as there is no ingredient shortage. So you will print the statements for IC1 since it is being made completely. For IC2, you will have to wait until a machine is free and if the parlour closes before IC2 can be completed the machine won't take it up and will print, you will print 'Customer c was not serviced due to unavailability of machines'. 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? Ans14. [RS] Yes that assumption is valid for a fulfilled order too. 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? A15. [RS] As mentioned in the assumption taken '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.' So it does not wait for 1 second. 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? A16. [RS] Customers are informed of ingredient shortage by a machine as soon as one becomes available to take their 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?) A17. [RS] Priority based on indexes is valid when we have to choose between customers, say arriving at the same time or to choose for a free machine. Else they are serviced based on when they arrive at the parlour. So implementing the former is the correct solution. Q.18 In the provided example after second wont the machine takes another order even though it can’t complete? A18. [RS] No, as the assumption taken is 'A machine cannot start preparing an order if it will have to stop working in the middle of that order.' Q19. As a follow up to Q6, would the sample input with the end of input signal be, A19. [RS] Yes. 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? A20. [RS] Basically a machine picks up a partial order if there are sufficient ingredients and time to prepare it. If ingredients are unavailable for a partial order the customers entire order is rejected and he is asked to leave. if time is insufficient, the customer is not serviced for that partial order. In the example C1 is instead of C2 due to index priority. Q21. Explain Q17 ,Q18 A21. Q17 addresses the doubt about index priority. It is valid there is point of choosing between customers, machines etc. Q18 addresses the doubt about a machine rejected a partial order as it cannot complete it before it shuts down for the day. 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? A22. [RS] For uniformity, the correct implementation will be priority based on index, so in this case choose machine 2. Q23. Are there marks for writing the implementation details in the report? A23. [RS] It's important to mention the differences or assumptions in your implementation in your report/README. Marks will be there for mentioning your implementation and answering the questions/analysis asked at the end of each specification. Q24. Is taking input from a file allowed? (it was not explicitly approved in A17) A24. [RS] Please take input from command line only. Q25. ... is it possible in given test?? A25. [RS] Explained in A20. 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) A26. [JB] You are free to **make reasonable assumptions about edge cases not specified** (which is the point of these questions), as long as you **elaborate on said reasoning in your report** and your code can give a **sensible output.** 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 A27. [JB] Same as A26. Also, handling scenarios like this is the point of these questions and another reason why multithreading is helpful for solving them. 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 :( A28. [JB] Like I answered earlier, as long as your answer makes logical sense, we will be lenient. However, 100% marks cannot be awarded for it. 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? A29. [JB] Sorry, you cannot reserve ingredients like that. 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 A30. [JB] 1 is correct, next customer take a while to enter => encapsulated in the 1 second delay. 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. A31. [JB] The fact that ingredients cannot be reserved should answer your question. 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? A32. [JB] You only follow increasing order of indexing when both cases are identical, and swapping would make no difference. Here, swapping does make a difference => M1 must prepare IC2 and M2 must prepare 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? A33. [JB] 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? A34. [JB] Ideally, (to get the correct answer) you should be performing an ingredient check when a customer places their order, and one again when a machine gets assigned to it. I hope this clarifies the doubt. 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? A35. [JB] Yes, correct. 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)? A36. [JB] No. You should either never have made IC1 or IC1 goes wasted. You cannot restore the ingredients. 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? A37. [JB] The first available machine must take the order. 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)? > *Note: This was already answered in A32, please read the previous answers before asking new questions.* A38. [JB] You only follow increasing order of indexing when both cases are identical, and swapping would make no difference. Here, swapping does make a difference => M1 must prepare IC2 and M2 must prepare IC1. 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? A39. [RS] As mentioned before, if a partial order say IC1 or IC2 does not have enough ingredients initially, the whole order of the customer i.e. both IC1 and IC2 should be rejected. Thus, for ingredients shortage of even a partial order the whole order is rejected, so you do not prepare IC1. For machine unavailibilty, the customer waits till parlour closes. Note that a customer does not leave with a partial order. 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. A40. [RS] Yes you will need to consider all customers in input, as number of customers in the parlour at any moment depends on their orders and not just the entry time. The case you have described is what your implementation needs to ensure!! So no matter how many customers are given in input, at any point of time, only k customers can be in the parlour. They might have left due to completion of order, rejection of order, or never entered as the parlour was full. Q41. 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. A41. [RS] C1 will be rejected with partial order(with ingredients wasted, this is the case we've asked you to optimize in the questions asked). Rejection based on ingredients should only be for no. of ingredients at that point in time. Rest is based on how you optimize it. 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** . A42. [JB] - A26 & A27: simply ask you to make assumptions on unspecified details. - Q34: describes a course of action on ingredient checking that might be helpful in the case asked - Q36: says '*either* never have made IC1 *or* IC1 goes wasted', disallowing the restoration of ingredients. > Since you cannot undo the creation of IC1, and you had no way of knowing that IC2 would face an ingredient shortage, IC1 must go wasted. > The statement `If a customer’s order can only be partially completed, they must be rejected completely, no part of their order should waste ingredients.` is only for the placement of the order, meaning you cannot _accept_ partial orders. When an ice cream goes wasted like in Q36, the case has already been mentioned and asked about under the section 'Questions' as > **Minimizing Incomplete Orders:** Describe your approach to redesign the simulation to minimize incomplete orders, given that incomplete orders can impact the parlor’s reputation. I hope that this explaination of the reasons for your doubt, clarifies the case asking about the same. 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. Is this valid?? A43. [RS] As mentioned before, when the machine has a choice it has to choose customers with lower index due to priority on ascending order of index. So if machine serves customer 2 instead of 1 in this case partial marks will be given. 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 ? A44. [RS] Wait for a machine to be available. Q45. Are the machines in the input given in sorted order of start times? (Does a machine with lower index have lower start time?) A45. [JB] Machines will be given in sorted order of their start times. 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. A46. [JB] [1] **Since you cannot undo the creation of IC1, and you had no way of knowing that IC2 would face an ingredient shortage, IC1 *must go wasted*.** [2] Ingredients cannot be reserved. As long as cases like [1] and condition [2] are ensured, and you do not violate any other conditions, you can make assumtions with sound reasoning. 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.) A47. [JB] The statement `If a customer’s order can only be partially completed, they must be rejected completely, no part of their order should waste ingredients.` is only for the placement of the order, meaning you **cannot _accept_ partial orders**. If ingredients get used up after the order has been accepted then it becomes a case of > **Minimizing Incomplete Orders:** Describe your approach to redesign the simulation to minimize incomplete orders, given that incomplete orders can impact the parlor’s reputation. If you do not understand from this explaination then maybe check your implementation, you might be doing something fundamentally incorrect. Else, please try asking more specific / descriptive and concise questions. 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. A48. [JB] If both machines can prepare the order, and no orders are already waiting, then the machine with the lower index will take up the order. In your case, if the machines do not become free at the same second, then the machine that becomes free first will take up the order. Q49. Are we allowed to use pthread barriers? A49. [JB] Yes, you can use them as they're part of `<pthread.h>`. 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. A50. [JB] Yes, that's correct. 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? `[Yes]`. Is this what "accepting" an order means? (WITHOUT wasting ingredients.) `[Yes]`. 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? `[Yes]`. A51. [JB] I've added the answers in the question. Glad everything is clear now. Q52. The problem statement says `If all limited ingredients are depleted, the parlor closes for the day.` Say the ingredient list is such, ```1 3 1 4 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? A52. [JB] Please just stick to what has been asked, which is `If all limited ingredients are depleted, the parlor closes for the day.` in this case. 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? A53. [JB] No, sorry, the same second case is only applicable to when a machine *begins* working. 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. A54. [JB] I'm assuming `determine an ingredient shortage has occurred` *for that ice cream* (because that's the one it is preparing), so the answer is A. 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. A55. [JB] 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. Which is the same thing Q53 says. 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?) A56. [JB] It makes more sense to have all machines free up at that timestep and then they take up orders. This allows more machines to be free in case many customers show up. 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? A57. [JB] The order will not be made with incomplete ingredients. You can choose to wait for orders in progress to complete as they may affect the number of ice creams wasted / partial orders. 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. A58. [JB] instantly close the parlor and not finish the orders in progress -> can lead to incomplete orders waiting for the orders to finish -> can lead to complete orders of ice creams already in the machine ## 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? A1. [RS] You need not submit a report for CoW. For the other specifications, the report should include - Brief implementation of each specification. - Analysis of results of each specification - Follow-up questions (if any) asked for a specification. Please add the report in the same directory as intitial-xv6 and concurrency folders. Submit a single markdown file for the report for the entire mini-project.