Operating Systems

Operating Systems

1. Artefacts

   • People design them
   • Trade-offs made
   • Personal choice affects design
   • OS interface very difficult to change now
     • Specifications written to it.
   • Acts as interface between user and computer, prevents stupidity from destroying things.

2. Stacks

   • FIFO data structure
   • Can be used to keep track of where we need to go back to once we've finished executing code.
     • Processor stack stores locations that we've come from in code.
       • Top of stack stores where we go after executing THIS code
   • "jsr xx" adds current location to stack, transfers control to xx.
     • "ret" pops previous location off stack and returns there.
   • Stores stack frames, both location and parameter data.
   • memory allocation and release simple

3. Interrupts

   • Allow processors to do other things while waiting for slow processes, like data transfer.
   • CPU checks for interrupts at end of each instruction carried out
     • If there is one, CPU "vectors" to handler, and then resumes afterwards
     • CPU must save register values (like PC) before vectoring to handler to ensure that the program can run fine afterwards.
   • There can be many interrupt lines in a bus and an interrupt controller to decide which one to listen to.
   • Good solution, but not perfect, when reading from device to memory all data goes down bus to processor, and then again down to memory.

4. DMAs

   • Means that device has access to memory itself
   • Interrupt only occurs when data is finished transferring

5. Controls action of all other programs

   • Controls allocation of resources between processes

6. Development

   • Monolithic OS
     • Applications have full access to all software, so no fault containment and no information hiding.
     • Device drivers in software direct link to hardware
     • Single user systems
   • Kernel-Based OS
     • device drivers, file system, system calls and scheduler are all hidden from user by the kernel.
     • Applications must go through kernel to access everything.
       • Thus need a way for secure transition between user and kernel modes, an unprivileged instruction typically called a software interrupt.
         • Allows access to system calls.
   • Microkernel OS
     • Place some system calls into servers in user mode, access servers via interprocess communication (IPC) schemes
       • Some servers may still operate in kernel mode, be privileged.
       • But IPC adds overhead, microkernels tend to perform less well. Implementation is trickier.
     • Noone really sure if kernel-based or microkernel is better

7. Protection

   • Dual-Mode Operation
     • OS can either be in user mode, or kernel mode, determined by a mode bit in hardware. Some operations are restricted to kernel mode.
   • I/O & Memory
     • Make I/O instructions privileged, so applications can't control devices
     • Protect memory by restricting each program's list of memory locations it can access, by supplying a base and limit.
     • Hardware checks each memory address is within base and limit, if not then vectors to OS with an error. Update of base and limit only in kernel mode.
   • CPU
     • Cant let any one application hog CPU usage
     • Set up a timer to countdown until interrupt occurs and control switches elsewhere.
       • Only OS can load timer, and interrupt cannot be "masked" (ignored)

8. Processes

   • Processes exist in queues
     • Job Queue contains processes waiting for admission
     • Ready queue contains process awaiting execution
     • Wait queue contains processes waiting on I/O events
     • Schedulers
       • job scheduler decides which processes join the ready queue
       • CPU scheduler decides which process should get CPU next
         • occasions when we can choose a new process:
           • a running process blocks
           • a timer expires
           • a waiting process unblocks
           • a process terminates
         • If scheduler follows above rules, then have a non-preemptive scheduler
           • simple to implement, but open to DOS
         • Otherwise scheduler is preemptive
           • solves DOS problem, but harder to implement and get concurrency issues
             • need some kind of timer in hardware support
         • Idle system, what if no process is ready to execute?
           • can halt processor until instruction arrives, saves time and heat, and increases processor lifetime, but may take too long to start up again
           • Can "busy wait" in scheduler, keeps polling scheduler, gives quick response time, but useless.
           • Can invent an idle process, that s always ready to run, gives uniform structure and can be doing something useful, but takes up memory and may slow interrupt response
   • Process Creation
     • Most systems are hierarchical, so parent processes create children processes.
       • Can share resources in one of three ways
         • share all
         • share some
         • share none
       • Execution in one of two ways
         • parent and children can run concurrently
         • parent can wait for child's termination
       • Address space allocated in one of two ways
         • Child duplicate of parent
         • Child has program loaded into it
   • Process Termination
     • Process may be terminated for 3 reasons
       • Process finishes execution, asks operating system to delete it (exit)
         • output data from child to parent (wait)
         • or have its resources deallocated by OS
       • Process performs and illegal operation, like:
         • Attempts to access memory it's not authorised to
         • Attempts to execute privileged instruction
       • Parent may terminate child (abort, kill) because
         • child has exceeded allocated resources
         • The task assigned to the child is no longer required
         • parent is exiting, causing "cascading termination"
   • Process Blocking
     • process tends to block on an event, (until an event occurs) I/O finishes, other process notifies
     • Need to handle concurrency issues
   • CPU-I/O Burst Cycle
     • process execution consists of a cycle of CPU execution followed by I/O handling
     • A process is either
       • CPU bound, where its speed is bound by speed of processing and amount of CPU scheduled, as it does very little I/O but has long CPU bursts
       • I/O bound, where its speed is bound by speed of I/O handling, as it does much more I/O between short bursts of CPU
   • Scheduling
     • Scheduling citeria
       • CPU utilisation by processes
       • Throughput, # of processes completing per unit time
       • Turnaround time, amount of time to execute a particular process
       • Waiting time, total amount of time process spent in ready queue
       • Response time, amount of time between a request being submitted, and first response to it
       • liveness and fairness, need to show you're doing something to a user or network
     • Scheduling Algorithms
       • First Come First Served (FCFS)
         • order of execution depends on order of process arrival
           • suffers from convoy effect
       • Shortest Job First (SJF)
         • No matter who arrived first, schedule the shortest job next
           • optimal in terms of average waiting time
           • tie breaker can be FCFS, urgency or randomised (non-deterministic)
       • Shortest Remaining time first (SRTF)
         • Preemptive version of SJF, if new process arrives with shorter remaining burst time than current process, switch to it
         • If shorter processes always butt in, may never finish current one
       • Predict Next CPU Burst Length
         • Exponential Averaging
           • \[ \tau_{n+1} = \alpha t_n + (1-\alpha) \tau_n \]
         • We choose value of alpha depending on the weight we give to history. alpha = 1 implies history irrelevant, alpha = 0 implies history all that matters
       • Round Robin
         • Define small, fixed unit of time, quantum
         • Each process runs for at most one quantum
         • Context switch on time out or process blocks
         • It is fair and live, good response time, worse turnaround time
         • Tricky to choose correct quantum size
     • Priority
       • Static
         • Assign int priority 2 processes. Low number = high p.
           • CPU given to > p
           • Problems! Starvation of < p
       • Dynamic
         • Static base and dynamic effective ps
         • If not run 4 k secs, effective++. Reset effective on run