MSc Revision Notes - Operating Systems

Exam topics

Main topics

Processes & threads
Scheduling
Interprocess communication
Deadlocks
Memory management
IO
File systems
Multiple processor systems
Security

Processes & threads

Processes

3 process states:
1. Running
2. Ready
3. Blocked
4 transitions:
1. Running -> Ready
2. Running -> Blocked
3. Blocked -> Ready
4. Ready -> Running
Each process has an entry in the process table.

Threads

Threads allow a single process to do more than one thing at a time.
Threads share process resources (address space, open files, data) but have separate paths of execution and separate program counters, registers and stacks.
Because threads don't have resources attached to them they are easier to create and destroy than processes.
Better performance for IO bound apps so CPU and IO can overlap. No real advantage for CPU bound processes.
Threads may be implemented in user space or kernel space.
User level threads:
- Doesn't require support by the OS
- Lower overhead creating and destroying threads
- Can have customised thread scheduler
- But blocking system calls will cause the entire process to block (also page faults). This is a major downside.
Kernel threads:
- Can handle blocking system calls (will only block thread)
- But more overhead creating and destroying threads.
A hybrid system maps user level threads onto each kernel thread.

Scheduling

Preemptive used in multiprogramming system (the processor may be taken away from a process after a set time).
Non-preemptive used in batch systems (each process runs to completion or until it blocks).

Batch systems

First-come-first-served
Shortest job first - optimum, but only if all jobs known in advance
Shortest remaining time next - a preemptive version

Interactive systems

Round-Robin - each process is assigned a quantum (time interval 20-50ms)
Priority - Each process is given a priority. IO bound processes should get a higher priority so they can use the CPU quickly and then get back to doing IO while some other process runs.
Priority with Round-Robin: processes have a priority but within the priority level they are scheduled Round-Robin. Priorities will need to be adjusted so low priority processes don't starve.
Shortest process next (aging) - aT₀ + (1 - a)T₁. If a is 1/2 just add the new value to current estimate and divide by 2.
Guaranteed scheduling - each process gets the same amount of CPU time
Fair share scheduling - each user gets the same amount of CPU time
Lottery scheduling - each process gets 1 or more 'tickets' which are chosen at random. More important processes may have more tickets.

Thread scheduling

User level threads - the runtime system decides the scheduling. Kernel schedules the process, runtime system schedules the thread. Threads must co-operate with others in their process.
Kernel level threads - the kernel schedules a thread from any process

Interprocess Communication

For two processes to use a shared memory region:
1. Mutual exclusion
2. No assumption of speed of processes
3. No process running outside its critical region should block another process
4. No process should have to wait forever to enter critical region

Solutions using busy waiting

Peterson's solution
```
   1 #define FALSE 0
   2 #define TRUE  1
   3 #define N     2                                     /* number of processes */
   4 int turn;                                           /* whose turn is it? */
   5 int interested[N];                                  /* all values initally 0 (FALSE) */
   6 
   7 void enter_region(int process) {                    /* process is 0 or 1 */
   8     int other = 1 - process;                            /* number of the other process */
   9     interested[process] = TRUE;                     /* show that we are interested */
  10     turn = process;                                 /* set flag */
  11     while (turn == process && interested[other] == TRUE)  /* null statement */
  12 }
  13 
  14 void leave_region(int process) {
  15     interested[process] = FALSE;                    /* leaving critical region */
  16 }
```
- Before entering critical region a process calls enter_region with its own process number. When it leaves the critical region it calls leave_region

Test and Set Lock

Requires hardware support

Reads contents of a lock variable and if it was 0 sets it to 1. If it was 1, the lock was already set so loops

enter_region:
  TSL REGISTER,LOCK    ; copy lock to register and set lock to 1
  CMP REGISTER,#0      ; was lock zero?
  JNE enter_region     ; if it was non zero, lock was set, so loop
  RET                  ; return. critical region entered.

leave_region:
  MOVE LOCK,#0         ; store a 0 in lock
  RET                  ; return

Semaphores

A variable that counts the number of wakeups for future use.

down

if 0 then sleep else decrement value of semaphore

increment value and wakeup a sleeping process and allow it to perform a down.

Use semaphores for synchronization. Eg, producer goes to sleep when the buffer is full.
Use binary semaphores (mutexes) for mutual exclusion - protecting some shared resource.
Mutexes are initialized to 1.

Producer-consumer with semaphores:

   1 #define N 100          /* number of slots in buffer */
   2 typedef int semaphore;
   3 semaphore mutex = 1;   /* mutex controls access to critical region */
   4 semaphore empty = N;   /* number of free slots */
   5 semaphore full = 0;    /* number of full slots */
   6 
   7 void producer(void) {
   8     int item;
   9     while (TRUE) {
  10         item = produce_item();
  11         down(&empty);
  12         down(&mutex);
  13         insert_item(item);
  14         up(&mutex):
  15         up(&full);
  16     }
  17 }
  18 
  19 void consumer(void) {
  20     int item;
  21     while(TRUE) {
  22         down(&full);
  23         down(&mutex);
  24         item = remove_item();
  25         up(&mutex);
  26         up(&empty);
  27         consume_item(item);
  28     }
  29 }

File systems

File allocation

Windows uses FAT - Table in memory of linked list of disk blocks. Disadvantage - must be kept in memory.
UNIX uses I-nodes - Each file has an i-node that lists the file's disk blocks. Only need to keep in memory the number of open files.

Directories

Windows - directory entry contains the file name and the number of the first disk block of the file.
UNIX - directory entry contains the file name and the i-node number.

Memory management

Paging

The virtual address space is divided into pages. These are mapped to physical memory page frames using a page table.
A page table maps virtual pages onto page frames.
A page fault occurs when a virtual page is not mapped to physical memory. It must be fetched from disk.

Page replacement algorithms

FIFO - Linked list of pages. When a page fault occurs the oldest page is removed and the new one goes to the back of the list.
Second chance - Same as FIFO but if the page's R bit is set it is cleared and put on the end of the list for a second chance.
Least Recently Used - The least recently used page is removed.
Belady's Anomaly - states that it is possible to have more page faults when increasing the number of page frames.
Working set - is the set of pages in use by a process. If the entire working set is in memory then there will be few page faults. WS page replacement algorithm records the time of last use of a page and the reference bit. When searching for a candidate page to remove it checks the R bit. If the R bit is set it is in the working set and the current virtual time is written. If the R bit is 0, the time is checked and if its age is older than the working set it is removed.

Deadlocks

Ordering resources numerically means that processes may only request resources in order. So at any instant a process will be holding the highest numbered resource which will prevent it from requesting any other lower numbered resources.

CategoryBbkRevision