Von Neumann model of computing

• CPU fetches an instruction from memory.
• Figures out which instruction this is
• Executes the instruction, and go on.

What does an OS do?

• makes it easy to run programs
• Allows programs to share memory
• Enables programs to interact with devices

Virtualization

• Virtualizing CPU
• Virtualizing memory

A couple of questions

• Does OS require hardware support? If yes, why?
• Why not have OS as a library of functions that an application can use?
• Why not run one process after another, making OS code simple?

First program

#include <stdio.h>
#include <stdlib.h>
#include "common.h"

int main(int argc, char *argv[])
{
    if (argc != 2) {
    fprintf(stderr, "usage: cpu <string>\n");
    exit(1);
    }
    char *str = argv[1];

    while (1) {
    printf("%s\n", str);
    Spin(1);
    }
    return 0;
}

What happens when we run this program

prompt> gcc -o cpu cpu.c -Wall
prompt> ./cpu "A"
A
A
A
ˆC
prompt>

Another run of the same program

prompt> ./cpu A & ; ./cpu B & ; ./cpu C & ; ./cpu D &
[1] 7353
[2] 7354
[3] 7355
[4] 7356
A
B
D
C
A
B
D
C
A
C
B
D
...

Some thoughts on virtualizing CPU

• Single CPU but all four programs ran simultaneously (almost)
• Illusion that system has many more CPUs -> created by OS

Question: If two programs run want to run at the same time, which should run?

A simple model for memory

• Physical memory: array of bytes.
  • A program keeps all of its data structures in memory.
• Read
  • Specify an address to be able to access the data
• Write
  • Specify the data to be written to the given address

What happens when we run this program

prompt> ./mem
(2134) memory address of p: 00200000
(2134) p: 1
(2134) p: 2
(2134) p: 3
(2134) p: 4
(2134) p: 5
ˆC

How about running it again and again

prompt> ./mem &; ./mem &
[1] 24113
[2] 24114
(24113) memory address of p: 00200000
(24114) memory address of p: 00200000
(24113) p: 1
(24114) p: 1
(24114) p: 2
(24113) p: 2
(24113) p: 3
(24114) p: 3
...

Both programs allocated the same address, and each program updates this location

Some thoughts on virtualizing memory

• Each process accesses its own private virtual address space
• Address space mapped to physical memory by OS
• Memory reference in one program does not affect the address space of other processes

Physical memory is a shared resource, managed by the OS

The problem of concurrent access

• The OS runs process after another leading to concurreny problem
• Multi-threaded programs also exhibit the concurrency problem

Third program (Concurrency)

#include <stdio.h>
#include <stdlib.h>
#include "common.h"
#include "common_threads.h"

volatile int counter = 0; 
int loops;

void *worker(void *arg) {
    int i;
    for (i = 0; i < loops; i++) {
    counter++;
    }
    return NULL;
}

Third program (contd)

int main(int argc, char *argv[]) {
    if (argc != 2) { 
    fprintf(stderr, "usage: threads <loops>\n"); 
    exit(1); 
    } 
    loops = atoi(argv[1]);
    pthread_t p1, p2;
    printf("Initial value : %d\n", counter);
    Pthread_create(&p1, NULL, worker, NULL); 
    Pthread_create(&p2, NULL, worker, NULL);
    Pthread_join(p1, NULL);
    Pthread_join(p2, NULL);
    printf("Final value   : %d\n", counter);
    return 0;
}

Understanding the concurrency problem

• Thread: a function running within the same memory space. Each thread starts running in worker().
• worker(): increments a counter in a loop loops number of times

Running this program

prompt> gcc -o thread thread.c -Wall -pthread 
prompt> ./thread 1000
Initial value : 0
Final value : 2000

Another run

prompt> ./thread 100000
Initial value : 0
Final value   : 143012 // huh??
prompt> ./thread 100000
Initial value : 0
Final value   : 137298 // what the??

Why is the output not as expected?

Concurrency problem

• Incrementing a shared counter takes three instructions.
  • Load the value of the counter from memory into register.
  • Increment it
  • Store it back into memory

These three instructions do not execute atomically

How to persist?

• System memory -> volatile storage.

  • Power off/system crash => data loss

• Hardware (disk) + software (file system) help store data persistently

• File system -> part of OS that manages the disk.

Why not create a private, virtualized disk for each application?

Fourth program that does some I/O

#include <stdio.h>
#include <unistd.h>
#include <assert.h>
#include <fcntl.h>
#include <sys/stat.h>
#include <sys/types.h>
#include <string.h>

int main(int argc, char *argv[]) {
    int fd = open("/tmp/file", O_WRONLY | O_CREAT | O_TRUNC, S_IRUSR | S_IWUSR);
    assert(fd >= 0);
    char buffer[20];
    sprintf(buffer, "hello world\n");
    int rc = write(fd, buffer, strlen(buffer));
    assert(rc == (strlen(buffer)));
    fsync(fd);
    close(fd);
    return 0;
}

Persistence

• What OS does in order to write to disk?
  • Figure out where on disk this new data will reside
  • Issue I/O requests to the underlying storage device
• What if the system crashes during write?
  • File system handles recovery
  • Carefully ordering writes to disk

Questions to an OS designer

• How to virtualize resources (CPU, memory)?
• How to allow concurrent memory access to build a correctly working program?
• How to manage persistent data reliably?

Design goals

• Abstractions to make the system easy to use
• High performance or low OS overheads
• Protection between applications or Bad behavior of one does not harm other and the OS itself