Lecture 5 - Orthogonality

by: Paul Eggert

January 21, 2015

Notes by: Mario Tinoco, Chris Orcutt, and Kaitlin Navarro

Eggert's Car

File Orthogonality

Process Orthogonality

Virtual Component Access Frequency
CPU - ALU High
CPU - Registers High
RAM - Primary Memory High
BUS - Devices (I/O) Low
Time
copy of registers virtual memory file descriptors
actual copy abstract description of the ram array of pointers providing indirect file access

Representing Operating System Resources

When writing programs, oftentimes it is useful (or perhaps necessary) to begin new processes or manipulate files. The operating system is responsible for keeping track of these resources and must be able to uniquely identify each process, and each file available for manipulation within a particular process. Many operating system implement this resource tracking with either small integers or pointers.

Modeling via Small Integers

Advantages: Provides a level of indirection--the operating system stores the context of each number and can choose whether to provide the context of any number.

Disadvantages: Numbers can become easily confused and developers may make the mistake of using a process ID when they meant to use a file descriptor.

Modeling via Pointers

Advantages: Harder to confuse distinct objects.

Disadvantages: Applications have direct access to the resources, no indirection.

The Unix Way

To create a new process, the fork() system call is used:

 pid_t fork(void);

Note that pid_t is just a redefinition of a signed integer type.

 int open(const char *path, int oflag, ... );
 int close(int fildes);

Note that the return types for open() and close() are both signed integers.

An Example: Fork, Open, and Close

Goal: To successfully run the following program in the shell.

 cat < a > b

Solution 1

int afd = open("a", O_RDONLY);
int bfd = open("b", O_WRONLY());
execlp("/bin/cat", (char*[]){ "cat", 0 }

Problem:

Solution 2

int afd = open("a", O_RDONLY);
int bfd = open("b", O_WRONLY());
int status;
pid_t p = fork();
if (p == 0) {
  execlp("/bin/cat", (char*[]){ "cat", 0 }
}
waitpid(p, &status, 0);

Problem:

Solution 3

close(0);
close(1);
int afd = open("a", O_RDONLY);
int bfd = open("b", O_WRONLY());
int status;
pid_t p = fork();
if (p == 0) {
  execlp("/bin/cat", (char*[]){ "cat", 0 }
}
waitpid(p, &status, 0);

Problem:

Solution 4

int status;
pid_t p = fork();
if (p == 0) {
  close(0);
  close(1);
  int afd = open("a", O_RDONLY);
  int bfd = open("b", O_WRONLY());
  execlp("/bin/cat", (char*[]){ "cat", 0 }
}
waitpid(p, &status, 0);

Modeling Pipes

du -s | sort –n

This allow us to see where our biggest directory is and be able to clean it out when we run out room

How can we implement this?

Potential Problems

What if we arrange part of the memory to act like a file system?

How can we represent this approach orthogonally?

We want this communication mechanism between du and sort to still look like a file, with respect to read and write system calls.

Pipes

A pipe is an interprocess communication that looks like a file, but set it up like a device.

Need a new operator to create a pipe, since ordinary operators talk about file names (which pipes do not have)

Let's take a look at the process tree:

Diagram of a process tree

Problems with Pipes

Read Problems:

  1. Trying to read when the pipe is empty
  2. Trying to read when the pipe is empty, and there are no writers

Problem:

Example

Now, consider the following:

Multiple Readers and Multiple Writers

(cat a&
  sed /x/y/ b) | sort

Furthermore, if we want to really cause trouble, we could have (a very strange example):

(cat a&
sed /x/y/ b) | (sort & 
                   wc)
image representation of pipe

Write Problems:

  1. Attempt to write, but pipe is full and reader never reads
  1. Attempt to write but pipe is full and there are no readers

If we apply process 4 to this, then write will return -1, causing printf to return a -1, meaning we will write forever chewing up CPU.

Now:

while(something == true)
    printf(“%d\n”, something_else());
    du | less
    //type q to exit
    //du keeps writing
    SIGPIPE
    //du dies