Bootstrapping & Synchronization

Bootstrapping

What is it?

Turning the computer on
From pressing the power bottom to the screen loading

Storage

Hardware stores this bootstrapping code into a small volatile (non-erasing) memory ROM
This memory is only used to boot up the system
Therefore it is safe to say that the memory is reserved for bootstrapping

Bootstrapping Code

BIOS sets up RAM & I/O devices
Scans buses to detect attached devices (whether the necessary I/o devices are not attached then it prompts and does not continue until they are)
Determines boot device, boot device is the space where OS is found. So it finds that boot device where the OS is located and then it executes the OS from there
The first section in the boot device that is executed is called the bootloader

Steps

BIOS
1^st Bootloader
2^nd Bootloader (loads the OS)

Loading means moving 1^st and 2^nd bootloader into main memory

Startup

Machine starts in the system mode, so the kernel code can execute immediately
System mode is a mode that is only used for system start up
System mode is the same as kernel node

OS Initialization

Initialize internal data structures (PCB)
Create first process (example shell in unix command line)
Switch mode to user mode and start running the first process
Wait for something to happen (curser blinking)

Memory Layout

OS Heap
Boot thread stack
All other OS code
Exception Vector Code
Stack
Heap
Static Data
Code

From Program to Process:

Code file, source file “.c” -> converted to “.o” file

Suppose I import from math library in my “.c” file then that library file also gets converted into “.o” file

All “.o” file -> becomes an executable binary file
When this binary file gets executed it becomes a process. When does it get executed?

Unix Shells

This code is used to execute a binary file

 while(1) {
  char *cmd =  read_command();
  int child_pid = fork()l
  if (child_pid == 0) {
     exec(cmd);
  }
  else {
     wait(child_pid);
  } 
 }

Fork – starts a new process, copies a parent process into child process or creates 2 identical processes in the memory address
Exec – picks up our created binary file and copies its code in to the child process’s text section, also places PCB into the ready queue

Communication between user & kernel mode

Kernel and user mode communicate through system calls

Getting to kernel mode – How do we get to the kernel mode?

Through system mode which is kernel mode
Through commands such as printf & fopen which go to system calls
Through hardware interrupts (pressing a key in hardware goes to OS which runs in kernel mode and the to the user mode)
Software trap or execution (Ctrl + C uses software to stop program)
To exit program we need to go through kernel mode

The System Calls Model

PICTURE

System Call Operations

Kernel mode must verify arguments that are passed
System calls can send arguments (eg printf(“…”))
A fixed number of arguments can be passed into registers (kernel must copu data from user space into its own buffers)
Result of system call is returned in register
An argument is passed on as address to memory location containing the data to be used then it copied to kernel memory

Introduction to Synchronization

Cooperating Processes

A process is independent if it cannot affect or be affect by other processes executing in the system
Independent processes do not share data
A process is cooperating if it’s not independent
Cooperating process must be able to communicate with each other and to synchronize their action

Interprocess Communication

Cooperating processes need to exchange information using either Shared Memory (fork) or Message Passing
Message passing model is the one that we spoke out in the previous section Send(P, msg) – send msg to process P, Receive(Q, msg) – receive a msg from process Q

Motivating Example

Withdraw(acct, amt) {
   balance = get_balance(acct);
   balance = balance - amt;
   put_balance(acct, balance)
   return balance;
}

Deposit(acct,amt){
   balance = get_balance(acct);
   balance = balance + amt;
   put_balance(acct, balance)
   return balance;
}

Suppose you share the account with your sister so at an ATM you’ve deposited and she withdrew at the same time. The only one process executes
The problem is that execution of the two processes can be interleaved

Schedule A:

Model5

Context switching occurs randomly at absolutely any time but our aim is that the execution of the next process should wait for the current one to computer or else shared memory can make errors

Schedule B:

Model6

If context switch occurs in this manner then we are able to do things as planned
However there is no guarantee of how the context switch will occur so we need a solution
Problem: Two concurrent threads manipulate a shared resource (the account) without any synchronization
We need to ensure that only 1 thread at a time can manipulate the shared resource so we need synchronization
Solution: Let only one thread access the shared resource at a time, this is called synchronization
All other threads must wait for the completion of the first one
When the thread leaves the shared memory/critical section only then the other thread may enter

On the side: What data is shared between threads?

Shared: Global variables and static objects (stored in the static segment, accessible by any thread)
Dynamic Objects and other heap objects (allocated from heap with malloc/free or new/del
Not Shared: Local variables, each thread has its own local variables

Critical Section Problem

Model7

Arrows indicate that Critical Section and Shared Variable can read and write each other
Each thread must request permission to enter its CS in its entry section
Critical Section may be followed by an exit section
Remaining code is in the remainder section

We want:

Mutual Exclusion

If one thread is in the CS, then no other is or can be

Progress

If no thread is in the CS and some threads want to enter the CS, it should be able to enter in definite time (immediately)

Bounded waiting

If some tread T is waiting on the CS, then there is a limit on the number of times other threads can enter CS before this thread is granted access. Don’t make it wait for too long

Performance

The code of entry & exit should be small compared to code for executing the task in CS

2-Thread Solution

2-Thread Solution – First Try

My_work(id_t id) {
   ...
   while (turn != id)
   /* critical section, access protected resource */
   turn = 1 - id
   ...
}

Benefit: only one thread at a time can be in its Critical Section
Drawback: If turn =0 then Ti may not enter even if T0 is in the code section

2-Thread Solution – Second Try

The first attempt does not have enough info about the state of each process it only remembers which process is allowed to enter the CS
Here each thread will have two flags, each thread may update its own flag and read the other threads flag
If flag[i] is true then Ti is ready to enter its CS

My_work(id_t id) {
   ...
   while (flag(1-id))
     flad[id] = true;
     /* critical section, access protected resource */
     flag[id] = false
   ...
}

Drawback: If both come to Critical Section at exactly the same time then both enter at the same time locking the system, this is called deadlock

2-Thread Solution – Third Try

Combine the key idea of the 1^st and second attempt for a correct solution
The thread share the variables turn & flag (where flag is an array as before)

Enter_region(id_t id) {
   flag[id] = true;
   turn = id;
   while (turn == id && flag[other] == true);
}

Leave_region(id_t id){
   flag[id] = false;
}

Basic Idea: if both try to enter at the same time, turn will be set to both 0 and 1 at roughly the same time. Only one assignment will last. The final value to turn decides who gets to go first

Peterson’s Algorithm – for achieving mutual exclusion

int turn;
int interested[N]

Enter_region(id_t id) {
   int other;
   other = 1 - process
   interested[process] = TRUE;
   turn = process;
   while (turn == process && interested[other] == true);
}

Leave_region(int process){
   interested[process] = False;
}

Higher level abstractions:

Locks

Very primitive, minimal semantics

Semaphores

Basic, easy to understand, hard to program with

Monitors

High-level, ideally has language support (Java)

Messages

Simple model for communication & synchronization direct application to distributed systems

Synchronized Hardware

We need help from hardware in order to built these higher level abstractions
On a uniprocessor – disable interrupts before entering the critical section, prevents context switches and doesn’t work on multiprocessor
Need some special atomic instructions

Atomic Instructions

Test-and_Set Lock (TSL)

Test and Set uses a lock variable, lock = 0 means nobody is using the lock and lock=1 means that lock is in use
In order to acquire lock, must change its value from 0 to 1
Lock is a memory address
*lock is the value at the memory address of lock

boolean test_and_set(boolean *lock){
   boolean old = *lock;
   *lock= True;
   return old;
}

Hardware executes this atomically
The semantics of test and set are:
Record the old value of the variable
Set the variable to some nonzero value
Return the old value
Lock is always true on exit in test and set
Return value is either true if it was locked already or false f it was previously available

Atomic instructions means nobody can context switch this code that is running and effectively it is a single instruction called test and set lock

A lock implemented

void acquire(boolean *lock){
   while (test_and_set(lock));
}

void release(boolean *lock){
   *lock = false;
}

Withdraw and Deposit Example with locks

Withdraw(acct, amt) {
   acquire(lock);
   balance = get_balance(acct);
   balance = balance - amt;
   put_balance(acct, balance);
   release(lock);
   return balance;
}

Deposit(acct,amt){
   acquire(lock);
   balance = get_balance(acct);
   balance = balance + amt;
   put_balance(acct, balance);
   release(lock);
   return balance;
}

Possible Schedule

acquire(lock);

balance = get_balance(acct);

balance= balance –amt

acquire(lock)

put_balance(acct,amt)

release(lock)

balance= get_balance(acct)

balance = balance + amt

put_balance(acct, balance)