Lab 8: Solution

We are in the middle of grading Lab 8. In the mean time, take a look at one possible solution below:

int main()
{
     // code removed for brevity         
        :
        :   
     } else {
    //  loop through each commands, setup pipes.
            int i;
            int fd[2*MAX_PIPE_LENGTH];
            for (i = 0; i < num_of_cmds; i++) {
                // for k cmds, there should be k-1 pipes.
                // the ith cmd reads from fd[2i-2], write to fd[2i+1].
                if (i < num_of_cmds - 1) {
                    pipe(&fd[2*i]);
                }
                pid = fork();
                int read_from = (i<<1)-2;
                int write_to  = (i<<1)+1;
                switch (pid) {
                    case -1: perror("fork"); exit(1);
                    case  0: 
                        if (i != 0) {
                            if (dup2(fd[read_from], STDIN_FILENO) == -1)
                                perror("dup2");
                            close(fd[read_from+1]);
                        } 
                        if (i != num_of_cmds-1) {
                            if (dup2(fd[write_to], STDOUT_FILENO) == -1)
                                perror("dup2");
                            close(fd[write_to-1]);
                        }
                        execvp(args[i][0], args[i]);
                        perror(args[i][0]);
                        close(fd[read_from]);
                        close(fd[write_to]);
                        exit(1);
                    default:
                        if (i > 0) {
                            if (close(fd[2*i-2]) == -1) {
                                perror("close");
                            }
                            if (close(fd[2*i-1]) == -1) {
                                perror("close");
                            }
                        }
                        break;
                }
            }
            for (i = 0; i < num_of_cmds; i++)
                waitpid(-1, NULL, 0);
        }
        free(command);
    }
    return 0;
}
Posted in lab

Lab 6: Comments, Part II

The grading for Lab 6 is done. As usual, please email me if the grade is not what you expected or you have any questions about the given remarks.

Disappointingly, many of you throw away precious points, just like that, by not following instructions on how to name files and the length of pages.

Many of you also did not explain the graphs, but merely describe what the graph looks like in words. Describing pictures is easy — given the graphs, anyone can describe what it looks like without know what is RR or MLFQ. The lab question specifically ask you to explain (i) and (ii). If you describe the graphs rather than explaining them, you would loose two points.

Here are the key points to mention:

  1. Turnaround/waiting time increases as number of CPU bound jobs increases. WHY: CPU bound jobs spend more time computing than blocking for I/O — so CPU is kept busy, queues are longer, jobs take longer time to complete.
  2. Response time increases slowly as number of CPU bound jobs increases. WHY: response time matters more for I/O jobs — so increasing the number of CPU jobs has little effect.
  3. The increment is more for RR than MLFQ. WHY: there is no differentiation between I/O-bound jobs and CPU-bound jobs in RR. So I/O bound job would have to wait behind more CPU-bound jobs if percentage of CPU-bound job increases. MLFQ gives priority to I/O bound jobs, which tends to stay at high priority while CPU-bound jobs get lower priority. More CPU-bound jobs do not have significant effect on the I/O-bound jobs.
  4. MLFQ has smaller turnaround/waiting time than RR. WHY: MLFQ approximates the behavior of shortest job first, so short jobs finish faster — leading to smaller turnaround/waiting time.
  5. MLFQ and RR have almost the same turnaround/waiting time at 10% and 90%. WHY: When most jobs are I/O-bound or CPU-bound, the jobs fall into the same queue in MLFQ.
  6. MLFQ has much lower response time than RR. WHY: MLFQ gives priority to I/O jobs.
Posted in lab

Lab 7: Comments

Lab 7 has been graded and posted on IVLE gradebook.  Mr. Fang graded the lab and has the following comments for you:

The average score of lab 7 is 13.7 out of 15, most of the students get a very good grade for this lab. Below are some comments on some of the common mistakes.

For question 1(b), some students think that the difference in program counter is due to the function call printf(). However, this is not the case. We can verify this by duplicating the line of printf() a few times, and observe the output.

For question 3(b), some students did not indicate the unit and some students get confuse with milliseconds (ms), microseconds (us) and nanosecond (ns).

Some of the questions require the answer to be within 500 characters, this is to encourage the students to answer only what is asked instead of putting down everything on the topic.

We received several emails about 3(c).  The right solution equation takes the form of (m+h = ..) and (m + 4h = ..) If you got this wrong, you should make sure that you understand why this is so.  I think understanding this part means that you have a good understanding of how page access/page faults work.

Lab 6: Comments

Part 1 of Lab 6 (MLFQ implementation) has been graded and the grades are available through IVLE gradebook. Hong Dai Thanh graded this lab, and he has the following comments for you.

Grading Scheme

  • mlfq_create_job: 2 marks
  • mlfq_next_job: 2 marks
  • mlfq_ready_job: 3 marks
  • mlfq_preempt_job: 3 marks

First of all, I would like to comment on the coding practice. I observed a lot of submissions that don’t initialize job->priority in mlfq_create_job, hard code number instead of using the given macro, using a “waterfall” of if statements, using features that are compiler-dependent, etc. Since this is not a software engineering module, I don’t penalize for those errors. However, you should be aware that writing program in that way will make the code very hard to modify when the specification changes.

Most of the submissions implements mlfq_create_job correctly. There are quite a number of submissions that don’t initialize job->priority. Technically, this is a programming error, since malloc doesn’t guarantee the memory allocated will be initialized to 0. However, I don’t penalize for this error.

Most of the submissions also implements mlfq_next_job correctly. If mlfq_next_job does not work correctly (e.g. only check the queue of the highest priority) then no mark will be given.

For mlfq_ready_job and mlfq_preempt_job, I observed many different implementations. The most straight-forward implementation will record the current priority in job->priority and update the job->time_left, job->max_time_quantum and enqueue the job accordingly. Some implementations do not use job->priority, and use a loop to compare the current max time quantum with the list of time quantum to derive the current priority level. Some implementations calculate the time quantum instead of taking it from the array mlfq.time_quantum (this is a bad programming practice). I give all those implementations full mark, as long as they are correct within the specification given.
Earlier I made a post about resetting the time left of the job when it moves up a level. AS an exercise, you can try doing it and compare the result. Since this is not mentioned in the lab sheet, I don’t penalize if you don’t reset the time left.

I will take off 1 mark for each error in this part. If you use a property without updating it, I will consider it an error. If you make the same error twice in two functions, it will be counted twice.

Max time quantum not updated: -1 each function
Job not properly enqueued: -1 each function
Off-by-one for mlfq_preempt_job: -0.5

The implementation of job_generator has a very low chance of generating a set of data in which a process gets demoted to the lowest priority level and stays there. Therefore, the program usually has a very high chance of producing the correct input even though it has an off-by-one error in mlfq_preempt_job.

I still see some cases of format violation. One or two cases submit a .tar file but is actually a .zip or .rar file renamed to .tar. Marks are deducted accordingly.

Posted in lab

Lab 8: On zombies, wait() and signal()

Many students have reported problems with zombies in Lab 8.

I did not think it would be this hard to prevent zombies, so this is unintended, partly due to last minute change of platform (from Linux to Solaris), and confusion due to the skeleton code given.

I would rather you spend time handling the pipes properly (remember to close every unused ends!) than worrying about zombies.

So, here is a way to remove zombies in Lab 8.

replace the line

 
waitpid(pid, NULL, NULL)

with

for (i = 0; i < num_of_cmds; i++)
    waitpid(-1, NULL, NULL);

This line ensures that the parent will wait as many times as child processes forked before returning to the prompt.

Next, I will describe several other ways that does not work or tricky to get it to work.

One solution that you might have done is to move the waitpid() statement into the for loop. So, in effect, bush is calling fork(), wait(), fork(), wait().. The impact of this change is that, the second command in the pipeline will not start until after the first command finishes execution. This is problematic, because the first command might not exit or might wait for the second command to read from the pipe (e.g., when the pipe is full). Example of a pipe that can cause trouble for this solution is “yes | head”.

Another solution is to wait() asynchronously with signals like what you have done in Lab 4. Using signal is not strictly necessary in Lab 8 since we do not support background processes. But it is not wrong to use signal either. The problem, however, comes from the subtle different semantic of signal() on Linux and Solaris. While on Linux, once you install a signal, it is there to stay. On Solaris, however, after the signal handler is called, the signal handler is reset back to the default handler. To make the signal handler you installed persistent, you have to reinstall it again and again by calling signal() within the signal handler. So if you have used this approach, either use sigaction() or call signal() from within the signal handler to reinstall the handler.

Week 13: Changes to Lab and Tutorial Schedules

As Monday, 7 November 2011, is a public holiday, we loose the opportunity to enjoy the lab and tutorial sessions on Monday.

There is no tutorial sessions for next week (including the Thursday sessions). Instead, the answers to the questions will be posted and discussed online.

There will be four additional lab sessions on Wednesday, 9 November, 2011.

  • 12noon – 1pm
  • 1pm – 2pm
  • 2pm – 3pm
  • 5pm – 6pm

Students from Monday’s lab group can come to any of the lab sessions.  Lab TAs will be available to help.

Lab 8: Pipes

Here is your Lab 8.

Lab 8 is a graded exercise. You have two weeks to complete. Submit your solution to the IVLE workbin before Sunday, 13 November 2011, 10:00pm.

Note that this lab is to be completed on SunFire, to reduce the dependencies on Linux machines in the OS lab.

PCs in OS Lab Fixed

A router hung.  It is fixed now. Please try and report if there are still issues.

The deadline for Lab 7 has been extended until Tuesday, 1 November 2011, 10:00pm.

Students who did not managed to work on the lab last Thursday are welcome to attend the lab sessions on this coming Monday.  If you have time table clashes and not able to attend the class on Monday, please feel free to contact your lab TAs if you need any help with the lab.

Lab 5: More comments

  1. When grading your lab 5 submissions, we noticed that there are quite a few of you which made the following errors: (a) you did not call pthread_mutex_init or pthread_cond_init to initialize the mutex nor condition variables; (b) you lock a mutex in one thread, and unlock it in another; (c) you pass a mutex to pthread_cond_wait in one thread, that is locked by another thread.

    The pthread implementation on Linux is surprisingly forgiving about the errors, thus many of you are not aware that you made the error. We graded the lab using a pthread implementation that is more strict, and were able to catch many of these, leading to low marks for many of you (for instance, if you do not initialize the mutex, locking has no effect). We have taken a second, more careful look at these submissions, and reward appropriately if you have the right logic but your code did not work because of the errors above. However, we discovered that further errors on a few submission, which lead to a lower score than before for a few students.

  2. There are also quite a number of you who did not rename your directory appropriately. We had to take off 3 points for these students. This is quite painful as you have worked hard on the lab, and loosing 3 points for not following instruction is a real pity. So, please and follow the instructions exactly and carefully for Lab 7 and 8.
Posted in lab