UTSA CS 3733 Operating Systems Assignment 3 Comments Fall 2001

CS 3733 Operating Systems, Fall 2001 Assignment 3 Comments

The assignment was graded on a basis of 30 points.

This assignment explored the difference between output that was determined by the program and output that was determined by outside influences such as scheduling parameters. In the first run you should have found that the output was always the same, no matter how many times the program was run. This was not because the program made the output appear that way, but because the scheduling algorithm was such that the output was always the same.

Our goal is to write program that have deterministic output even whan the scheduling of the processes is not within our control. For this simple example, it could be accomplished by inserting a wait in the appropriate place. Some alternates include passing a token around the ring (as in the extra credit) or to use semaphores.

Part 1

configuration output order determined by program? Why was it this way?

1. standard Always the same order, in order of pid. No, it is determined by the scheduling of the processes. Since there is no preemption and no blocking on I/O, the first process (the original parent) completes before the next process gets the CPU. Because it is FCFS, the processes get the CPU in the order in which they were created.

2. after fork: child Always the same order, first the last child, then the processes in order of pid. No, it is determined by the scheduling of the processes. Each process gives up the CPU to its child and does not get the CPU back until the last child completes. Then the processes get the CPU in order of creation.

3. after fork: either The order may vary between runs. No, it is determined by the scheduling of the processes. If will vary depending on which process gets the CPU after the fork. If after the first fork, the parent gets the CPU, it will output first. Otherwise, it depends on what happens after each fork.

4. after fork: random The order may vary between runs. No, it is determined by the scheduling of the processes. This will be similar to the one above, but with additional possibilities.

5. choose process: random This is just like the original configuration. No, it is determined by the scheduling of the processes. Since each process runs until completion, when it finishes, there is only one child process and so these is only one process to choose from.

6. choose process: random
scheduling: rr 5 This looks just like the original configuration. No, it is determined by the scheduling of the processes. Each process executes 5 instructions before losing the CPU and each process needs to execute about the same number of instructions after the fork before printing. From the Gantt chart it seems that it takes only one additional CPU burst after the fork to complete. The child process does not get to fork before it loses the CPU and so there is only one other process active when a process finishes. Because of this, the random choice of processes from the ready queue has no effect.

7. choose process: random
scheduling: rr n The order of the output can vary with some values of the quantum. No, it is determined by the scheduling of the processes. If the quantum is at least 8, there can be more than one other process ready when a quantum expired. This will allow some randomness in the order of the output. If the quantum is very long (at least 15), then it does not expire before a process completes, and the randomness disappears.

8. print not atomic The output will be garbled with parts of the output from one process appearing in the middle of the output from other processes. No, it is determined by the scheduling of the processes. The original parent outputs part of its message and then loses the CPU. The only other process, its child will then print part of its message and lose the CPU. At this point there should be two other processes in the ready queue, with the original parent first. It will output some characters. After this it becomes more complicated which process will output next. Since the simulator outputs in color you can see which characters are produces by each process, but in a real program you could not tell.

9. wait before the fprintf The output will be in reverse order of process creation all of the time. Yes. Before a process can print its child must exit. Therefore each child prints before its parent.

10. wait before the fprintf
print not atomic The output will be just as in the previous part. Yes. The scheduling algorithm now has no affect on the output since each child must finish its output before its parent can output anything.

Part 2

If the child breaks instead of the parent, a ring is still produced the the ring is in the opposite order, with the parent sending the the last child rather than the first one. In this case we have a process fan rather than a process tree.
If neither process breaks out we get a tree of processes. The processes are still connected in a ring, but the processes and pipes need to be moved around quite a bit to see this.

The tree from created when no processes break out of the loop.

The processes and pipes still form a ring.

To do Extra Credit 1, use the following code after the ring is created. The first process skips the read while the others block on the read until the previsou process has written to the pipe.

sprintf(buf," ",getpid());
if(i!=1)read(0,buf+strlen(buf),BUFSIZE);
fprintf(stderr,"This is Process %d with parent %d\n",getpid(),getppid());
sprintf(buf+strlen(buf)," %d",getpid());
write(1,buf,strlen(buf)+1);

The last process can write to the pipe after the first process exits. In this case there are no readers fro this pipe and a SIGPIPE signal is generated, terminating the process. It doesn;t matter here as the process will terminate anyway. This can be elininated by having the first process wait for its child before exiting:
if(i==1)read(0,buf+strlen(buf),BUFSIZE);
Put this as the last instruction in your program.

To do Extra Credit 2, you can use the following code:

pipe(fd1);
pipe(fd);
dup2(fd[0],0);
dup2(fd[1],1);
close(fd[0]);
close(fd[1]);
for(i=1;i<nprocs;i++) {
   pipe(fd1);
   pipe(fd);
   if (childpid = fork()) {
      dup2(fd[1],1);
      dup2(fd1[0],3);
   }
   else {
      dup2(fd[0],0);
      dup2(fd1[1],4);
   }
   close(fd[0]);
   close(fd[1]);
   close(fd1[0]);
   close(fd1[1]);
   if (childpid)
      break;
}
fprintf(stderr,"This is Process %d with parent %d\n",getpid(),getppid());

configuration	output order	determined by program?	Why was it this way?
1. standard	Always the same order, in order of pid.	No, it is determined by the scheduling of the processes.	Since there is no preemption and no blocking on I/O, the first process (the original parent) completes before the next process gets the CPU. Because it is FCFS, the processes get the CPU in the order in which they were created.
2. after fork: child	Always the same order, first the last child, then the processes in order of pid.	No, it is determined by the scheduling of the processes.	Each process gives up the CPU to its child and does not get the CPU back until the last child completes. Then the processes get the CPU in order of creation.
3. after fork: either	The order may vary between runs.	No, it is determined by the scheduling of the processes.	If will vary depending on which process gets the CPU after the fork. If after the first fork, the parent gets the CPU, it will output first. Otherwise, it depends on what happens after each fork.
4. after fork: random	The order may vary between runs.	No, it is determined by the scheduling of the processes.	This will be similar to the one above, but with additional possibilities.
5. choose process: random	This is just like the original configuration.	No, it is determined by the scheduling of the processes.	Since each process runs until completion, when it finishes, there is only one child process and so these is only one process to choose from.
6. choose process: random scheduling: rr 5	This looks just like the original configuration.	No, it is determined by the scheduling of the processes.	Each process executes 5 instructions before losing the CPU and each process needs to execute about the same number of instructions after the fork before printing. From the Gantt chart it seems that it takes only one additional CPU burst after the fork to complete. The child process does not get to fork before it loses the CPU and so there is only one other process active when a process finishes. Because of this, the random choice of processes from the ready queue has no effect.
7. choose process: random scheduling: rr n	The order of the output can vary with some values of the quantum.	No, it is determined by the scheduling of the processes.	If the quantum is at least 8, there can be more than one other process ready when a quantum expired. This will allow some randomness in the order of the output. If the quantum is very long (at least 15), then it does not expire before a process completes, and the randomness disappears.
8. print not atomic	The output will be garbled with parts of the output from one process appearing in the middle of the output from other processes.	No, it is determined by the scheduling of the processes.	The original parent outputs part of its message and then loses the CPU. The only other process, its child will then print part of its message and lose the CPU. At this point there should be two other processes in the ready queue, with the original parent first. It will output some characters. After this it becomes more complicated which process will output next. Since the simulator outputs in color you can see which characters are produces by each process, but in a real program you could not tell.
9. wait before the fprintf	The output will be in reverse order of process creation all of the time.	Yes.	Before a process can print its child must exit. Therefore each child prints before its parent.
10. wait before the fprintf print not atomic	The output will be just as in the previous part.	Yes.	The scheduling algorithm now has no affect on the output since each child must finish its output before its parent can output anything.