Test Cases (Directions)
FAQ
NOTE: a5q2b cannot be tested using the shell script (Input redirection will probably not work because it was not specified how to end the program).
- Q: Do we need to consider that the page table is stored in the main memory, occupying a number of physical pages?
A: As a simplifying assumption, you can ignore this and assume the page table is stored in a separate portion of memory. If you have already written your program assuming the page table is stored in memory, that's fine but please mention this in your readme file.
- Q: What is a "page-out"?
A: When doing a page-replacement, if the page to be replaced has been modified, its changes should be written back to the disc. This is called a page-out, and it causes extra delay because of the disc access time. If the page is only read and has never been written to, there is no need to update the disc, and there will be therefore no page-outs.
- Q: We are not given a parameter as the size of the physical memory. How can we obtain that?
A: You can determine the size knowing how many bits are dedicated to the physical page address and offset.
- Q: Can you provide sample input/output for Q1?
A: A sample is available at the discussion page.
FAQ
- Q: What does the event queue do? What do we store in the scheduler-specific data structures? How do we distinguish between the two?
A: The event list stores all the events sorted by time. Each event is an instant of time in which some processing should be done, e.g. arrival of a process, departure of the current process, end of the current quantum. Each time, you remove the event at front of the list, advance the current time to the time of that event, and handle it. Event handling might cause new events to be inserted in the queue (e.g. when you start a job, its departure event is inserted). The statistics are gathered while handling the events, e.g. when on a departure event, the running job terminates and its turnaround time can be obtained; then the scheduler decides which job is next. If this is the first time the job gets the CPU, the response time is calculated accordingly.
The scheduler-specific data structures are required to keep track of the current state of the system. For instance, when you handle an arrival event, if the processor is currently busy, you add the newly arrived process to the ready queue (which is sorted by arrival order in FCFS, and by remaining time in SRTN). For the case of lottery scheduling, the scheduler-specific data structure can be the collection of all existing tickets - each ticket referencing its corresponding process. In this case, event handling might involve updating the tickets.
- Q: Can we assume that the time values in input files are always integers?
A: Yes.
- Q: Can we assume that the input file is sorted in order of arrival times?
A: No, the input files do not necessarily follow any specific ordering.
- Q: I do not understand the "proportionality" measure. Can you give an example?
A: Suppose we have tasks with lengths 2, 4, and 6, and turnarround times of 3, 5, and 12 respectively. Then the ratios of turnarround time to the actual length are 3/2, 5/4, and 12/6 respectively. Proportionality is the maximum of these numbers, which is 2. The lower the proportionality, the better the scheduling algorithm.
- Q: Can you give sample input/output for Q1?
A: This is a very small example for illustration. You might want to develop more complex ones on your own.
- Q: What is the rationale behind choosing 2*ceiling(length/quantum) as the number of tickets in lottery scheduling?
A: The processes are given twice as many tickets as they really need. If they are given exactly the count they need, when approaching completion there will be slim chance for them to get the CPU, and the turnaround time grows high.
- Q: In EDF, when a process takes several time-slots, do we need to output the start of each time-slot or only the first one?
A: Only the first one should be outputted (Exactly n lines of output).
Sample source code for Semaphores, unnamed pipe, named pipes ( client, server), agreement on two pipes.
FAQ
- Q: In the second practical question, do we have to worry about more/less than two parties?
A: No, the behavior of your program is important only when two parties - and exactly two - start the program before any of them starts sending the messages.
- Q: What should happen if Alice receives a message while she is entering text?
A: Although unrealistic, for simplicity we assume this situation never occurs.
Sample Test Case For Q2
FAQ
To make sure the executables can run on your system, recompile a.cpp, b.cpp, and c.cpp on your own machine.
- Q: What programming languages are we allowed to use?
A: C or C++. For the sake of simplicity you are strongly recommended to use C++.
- Q: There is no exec() system call. Are we supposed to use one of the execl(), execlp(), and other functions starting with 'exec'?
A: Yes.
- Q: Do we have to submit test inputs?
A: No. You are asked NOT to submit any file other than what listed in the spec, or you will lose marks. However, you are allowed (and recommended) to use your own test inputs to check the correctness of your program before submission.
- Q: Do a1q2a and a1q2b have to be very similar to each other?
A: This is not a strict requirement of your assignment. However, for your convenience the questions are designed in a way you can easily get a1q2b by modifying a1q2a.
- Q: When you test our code, will you be compiling our source yourself to ensure it works?
A: When testing, I will use your "makefile" to compile/link your source code and generate executables. I then use these executables to test correctness of your programs. If your makefile fails, you will lose some portion of the mark.