CS 111 Scribe Notes Lecture 5, 2012-4-17

By Troy Sankey, Ji Huang

Orthogonality in OS Design

In Mathematics, orthogonal components are at right angles to each other which helps keep them independent of each other. Scaling one component has no affect on the others, so the result is easy to determine.

In operating systems, orthogonal components are also independent of each other. Orthogonal design goals include simplicity and consistency. It tries to avoid use of function calls with side effects that may propagate to other components and cause problems where one might least expect it. For example, adding memory to the system should not affect how the API for accessing memory works.

At the kernel level all processes and files work the same, and use a small set of simple instructions (system calls). The graphic below shows how the process table is organized in memory (assume number of file descriptors is 1024 in GNU/Linux).

    processes      file descriptors
-----------------------------------------------
1               |                    |
2               |                    |
3               |                    |
4   ..|regs|..  |   ..|3|4|..        |
.               |                    |
.               |                    |
-----------------------------------------------
^
process ids

Processes:

• int fork();
• int exit(int status);
• int waitpid(int pid);
• int execvp(char const *file, char * const *argv);
  • If execvp fails, it will always return -1 (no need to check).
  • Otherwise, it succeeds and we don't exist anymore...running other program now.
• int kill(pid_t p, int sig);
  • kill(getpid(), SIGABRT) is equivalent to abort()

Here is what we can do with some of the above system calls. Blue and red code are two alternative solutions to handle forked processes that lock up.

void printdate(void) {
  int status;
  pid_t p = fork();
  switch (p) {
    case -1: error(): /* magical error function */
    case 0:  alarm(5);
             execvp("/bin/date", (char **) {"/bin/date", 0});
             error();
    default: sleep(5);
             kill(p, SIGKILL);
             if(waitpid(p, &status, 0) < 0)
               error();
             if(!WIFEXITED(status) || WEXITSTATUS(status) != 0)
               error();
  }
}

Both the red and the blue implementations work, but the blue version guarantees a five second delay after calling fork, whereas the red version can continue running the parent immediately after the forked process is complete (or after five seconds of lock up).

Files:

• int open(const char *path, int oflag, ... );
• ssize_t read(int fildes, void *buf, size_t nbyte);
• ssize_t write(int fildes, const void *buf, size_t nbyte);
• int close(int fildes);
• int dup(int fd);
  
  • finds the next open slot in the file descriptor table and makes that point to the same file description as fd.
• int dup2(int fd1, int fd2);
  
  • allows user to specify a desired file descriptor by making fd2 point to the same file description as fd1.
• int pipe(int fd[2]);

Pipes

Pipes allow high throughput transfer of data between two processes. Here is what "p1 | p2" is represented by:

p1 has a write-only file descriptor and p2 has a read-only file descriptor to the pipe.

Virtual	Actual
pipe ---------------- p1 -> > > -> p2 ----------------	pipe ---------------- |--data--| ---------------- ^ ^ p2 p1

"p1 | p2" needs 3 processes: one to set up the pipe (shell), and one at each end of the pipe. There are three candidates for forking the two extra processes:

case 1	case 2	case 3
shell / \ / \ p1 p2	shell / p1 \ p2	shell \ p2 / p1

The shell needs the exit status of p2, so p2 must be a direct child of the shell, which rules out case 2. Here is sample setup code for case 1:

int fd[2];
pipe(fd);
p1 = fork();
if(p1 > 0) {
  p2 = fork();
  if (p2 > 0) {
    /* we are the shell, don't need any access to the pipe. */
    close(fd[0]);
    close(fd[1]);
    /* shell does work here */
  } else {
    /* we are p2, don't need write end of the pipe. */
    close(fd[1]);
    /* p2 does work here */
  }
} else {
  /* we are p1, don't need read end of the pipe. */
  close(fd[0]);
  /* p1 does work here */
}

Things that can go wrong

What can go wrong with pipes?

1. last writer dies
   • reader gets 0.
2. reader dies
   • writer gets killed.
3. writer forks
   • writes are interleaved nicely (small writes respected, large ones are not).
4. reader forks
   • reads are interleaved

5. char buf[1024];
   int fd[2];
   if(pipe(fd) < 0) error();
   int n = read(fd[1], buf, sizeof buf); /* hangs forever */
   

What can go wrong with file descriptors?

1. forget to close write end.
   • EOF never gets written to the pipe, so the reader reads past the last byte written.

2. fd = open("file1, O_RDONLY);
   read(fd, ...);
   fd = open("file2, ...); /* calling open again without first closing.
                            * this is a memory leak.  */
   

3. fd = open("/dev/usb/27");
   read(fd, ... );
   /* unplug USB */
   read(fd, ... ); /* returns -1 and sets errno to EIO */
   

4. fd = open("/tmp/foo");
   read(fd, ...);
   /* rm /tmp/foo */
   read(fd, ...);
   /* nothing happens, read keeps working.
    * read/write is isolated from file linking.  */
   

Creating an empty file

Say we are writing a program that needs to write data to a temporary file. We can make a file with a predetermined name:

int fd = open("/tmp/sort-tmp", O_RDWR|O_CREAT|O_TRUNC, 0666);
if(fd < 0) error();
/* do stuff */
if(unlink("/tmp/sort-tmp") < 0) error();

Three flags were used to open the file:

• O_RDWR - open with read and write capabilities.
• O_CREAT - create the file if it doesn't already exists.
• O_TRUNC - truncate/empty the file if it already exists

The problem with creating a file with such a simple name, "sort-tmp", is that another program may want to use that same name (at the same time). One potential workaround is to create the filename using the pid of the current process:

char const template[] = "/tmp/sort-tmp%" PRIdMAX;
char tmpname[sizeof(template) - 2 + sizeof(int) * CHAR_BIT];
int max_t p = getpid();
sprintf(tmpname, template, p);
int fd = open(tmpname, O_RDWR|O_CREAT|O_TRUNC);

And anoher potential workaround is to randomly generate the filename:

for(;;) {
  struct stat st;
  genrandom(tmpname);
  if(stat(tmpname, st) != 0)
    break;
}
/* what if some other process wrote to same file here? or created same file. */
open(tmpname, ...

However, the preferred method for opening files that may be confilcting with other running programs is to use the O_EXCL open flag. This causes the open to fail if the file exists. Therefore, race conditions are no longer a problem since the system call is atomic.