Operating System (EXAM NOTES) Why study Operating Systems?

- To understand interaction between

Topic 1: Introduction the hardware and applications
- To understand basic principles in
Definition the design of computer systems
Operating System is a program/software - To cater the increasing need for
that acts as an intermediary between the specialized operating systems
user of a computer and the computer
hardware. Types of Operating Systems
Key notes: 1. Batch OS
- Acts as an intermediary The system divides similar tasks into
- Serves as an interface batches for easy processing and faster
- Provides an environment response.
2. Multitasking OS
4 core components of a Computer Allocates time to a particular task and
System Structure switching between tasks frequently.
1. Hardware 3. Distributed OS
2. Operating System Interconnected computers
3. Applications Programs communicating with each other via
4. Users communication lines or shared networks.
4. Network OS
Functions of an Operating System Installed on a server providing users with
A. Booting the capability to manage data, user
B. Memory Management groups, and applications.
C. Data Security 5. Real-time OS
D. Loading and Execution Provide support to real-time systems that
E. Drive/Disk Management require observance of strict time
F. Device Control requirements. (e.g. Missile/Medical/Air
G. User Interface Traffic Control systems)
H. Process Management 6. Mobile OS
Run exclusively on small devices such as
Goals of an Operating System smartphones, tablets, and wearables.
● Simplify the execution of user
programs and solve problems Types of Computing Environments
easier. 1. Traditional
● Use computer hardware efficiently. Stand-alone general purpose machine
● Make software portable and 2. Mobile
versatile. Handheld smartphones, tablets, etc.
● Provide isolation, security, and 3. Distributed
protection among programs. Collection of systems networked together
● Improve overall system reliability. 4. Client-Server
Servers responding to requests generated
2 components to manage computer by clients (e.g database)
programs and applications 5. Peer-to-peer
- Kernel (inner core component) All nodes are considered peers and each
(note: Kernel is the one program running can act as client, server, or both
at all times; hardware level) 6. Virtualization
- Shell (outer layer component) Allows OS to run applications within other
(note: Shell manages the interaction OSes (e.g VMware)
between the user and the OS) 7. Cloud Computing
Composed of traditional, VMMs, and
cloud management tools
Topic 2: System Structure - The system call invokes intended
system call in OS kernel and
View of Operating System Services returns status of the system call
and any return values
- The caller just needs to obey API
and understand what OS will do as
a result call

Types of System Calls:

● File Management
● Device Management
● Information Maintenance
Operating System Services
● Communications
● User Interface
● Protection
● Program Execution
● I/O Operations
OS Design and Implementation
● File System Manipulation
- User Goals: should be convenient
● Communications
and easy to learn.
● Error Detection
- System Goals: should be easy to
● Resource Allocation
design, implement, and maintain.
● Accounting
- Policy: decide what will be done
● Protection and Security
- Mechanism: how to do it

User Operating System Interface

OS System Structures
A. Command Line Interface (CLI)
Simple Structure
- Allows direct command entry;
Layered Structure
sometimes in the kernel or by
Microkernel System Structure
systems program
Modular Structure
- Primarily fetches a command from
Hybrid Systems
user and executes it
B. Graphical User Interface (GUI)
Kernighan’s Law:
- User friendly desktop metaphor
Debugging is twice as hard as writing the
interface (mouse, keyboard,
code in the first place. Therefore, if you
monitor)
write the code as cleverly as possible, you
C. Touchscreen Interfaces
are, by definition, not smart enough to
- Actions and selection based on
debug it.
gestures; virtual keyboard for text
entry
System Boot:
- ROM holds the initial boot code
System Calls
- OS must be made available to
- Interfaces provided by an OS that
hardware so hardware can start it
allow user-level programs to
- Kernel loads = system runs
request services from the kernel.
- Acts as a bridge between the
Topic 3: Process Management
user-level programs and the
low-level hardware.
Process in Memory:
- Mostly accessed by programs via a
high-level Application
Programming Interface (API)

System Call Implementation

- A number is associated with each
system call
Process State: Scheduling Queues
● New 1. Job Queue
Process is being created. As processes enter, they are put into a job
● Running queue which consists of all processes in
Instructions are being executed. the system.
● Waiting 2. Ready Queue
The process is waiting for some event to Processes residing in main memory and
occur. are ready/waiting to be executed are kept
● Ready on a list.
The process is waiting to be assigned to a
processor. Types of Schedulers
● Terminated A. Long Term Scheduler
The process has finished execution. ● Selects processes from secondary
memory and loads them into the
Process Control Block (PCB) main memory.
● Also known as job scheduler
● Controls the number of processes
in the memory.
B. Short Term Scheduler
● Also called as CPU scheduler
● Selects processes that are ready
to execute and allocates CPU to
one of them.
1. Process State ● Makes the decision of which
2. Process Number: shows the unique process to execute next.
number of the particular process. C. Medium Term Scheduler
3. Program Counter: contains the address ● Swapping of running processes
of the next instruction. ● In this case, processes suspend
4. Registers: the registers used by the from main memory and place on
process. (e.g. accumulators, index, stack the secondary, after a while, it will
pointers) be reloaded again in the main
5. CPU Scheduling Information: includes memory and continued where they
process priority, pointers to scheduling left earlier.
queues, & other parameters.
6. Memory Management Information: value Thread
of the base and limit registers, tables, etc. ● Single-threaded (1 execution at a
7. I/O Status Information: list of I/O devices time)
used by the process, list of files, etc. ● Multithreaded (Multiple execution
8. Accounting Information: amount of CPU within a single process)
and real-time used, time limits, job or
process numbers, etc. Scheduling Algorithm
A. First-Come, First-Served (FCFS)
Process Scheduling: - Simplest CPU-scheduling algorithm
● Multiprogramming - “First-In, First-Out”
Maximize CPU utilization; some processes - Implementation of the FCFCS policy is
running at all times. easily managed with FIFO queue
● Time-sharing - Non-preemptive
Switch the CPU among processes so - If two processes came at the same time,
users can interact with each program rely on the process ID.
while it’s running. - Criteria : Arrival Time
Example: C. Shortest-Remaining-Time-First
Given: P AT BT (SRTF)
P1 0 8 - Preemptive version of Shortest Job Next
P2 1 5 - Processor is allocated to the job closest
P3 2 10 to completion
P4 3 11 - Criteria: Burst Time
Answer:
Example:
P1 P2 P3 P4
Given: P AT BT
0 8 13 23 34
P1 3 4
P2 5 9
P AT BT CT TAT WT P3 8 4
P4 0 7
P1 0 8 8 8 0
P5 12 6
P2 1 5 13 12 7 Answer:

P3 2 10 23 21 11 P4 P4 P4 P1 P1 P3 P3 P5 P2
0 3 5 7 8 11 12 15 21 30
P4 3 11 34 31 20

P AT BT CT TAT WT
Formula Used:
- TAT : CT- AT P1 3 4 11 8 4
- WT : TAT - BT
P2 5 9 30 25 16
- ATAT : TAT Sum / # of Ps
- AWT : WT Sum / # of Ps P3 8 4 15 7 3

B. Shortest-Job-First (SJF) P4 0 7 7 7 0
- Length of the process matters P5 12 6 21 9 3
- Non-preemptive
- Criteria: Burst Time
D. Round-Robin Scheduling (RR)
- Ensures fairness in CPU allocation
Example:
- Each process runs for a fixed time
Given: P AT BT
quantum before moving to the next in a
P1 3 4
circular queue
P2 5 9
P3 8 4
Example:
P4 0 7
Given: P AT BT
P5 12 6
P1 0 8
Answer:
P2 1 5
P4 P1 P3 P5 P2 P3 2 10
0 7 11 15 21 30 P4 3 11
Answer:

P AT BT CT TAT WT P1 P2 P3 P4 P1 P3 P4 P4
0 5 10 15 20 23 28 33 34
P1 3 4 11 8 4
P AT BT CT TAT WT
P2 5 9 30 25 16
P1 0 8 23 23 15
P3 8 4 15 7 3
P2 1 5 10 9 4
P4 0 7 7 7 0
P3 2 10 28 26 16
P5 12 6 21 9 3
P4 3 11 34 31 20
Topic 4: Process Synchronization Hardware-based Approach Solutions
A. Test and Set Lock
Definition B. Swap
Process Synchronization, or concurrency, C. Unlock and Lock
is a process that operates in the system
and has the ability to both affect and be Semaphores
affected by other processes. It is a technique which helps manage
concurrent processes from accessing the
Race Condition same shared data at the same time. It
A race condition is when multiple uses integers (non-negative numbers)
processes interact with the same data and is also used to solve critical section
simultaneously without proper problems.
synchronization.
Types of Semaphores
Common Syntax of a System Process 1. Binary Semaphores (0 and 1s)
2. Counting Semaphores
(Unrestrained number of values)

Issues with Semaphores

A. Spinlocks (Busy Waiting)
Wasting the cycles other programs might
General Approaches for Critical Section have used more productively.
1. Preemptive Kernel B. Deadlocks
2. Non-preemptive Kernel Two or more processes would wait
indefinitely caused by one of the
Requirements in a Critical Section processes in the waiting state.
Problems C. Priority Inversions
- Mutual Exclusion Lower priority process takes precedence
If a process is executing in its critical over the high priority process.
section, no other processes can be
executing in their critical sections. Classic Problems of Synchronization
- Progress 1. Bounded-Buffer Problem
If no process is executing in its critical You have a box with limited space, you
section and other processes wish to enter can only put data into the box only if
their critical sections, it should not wait there’s an empty space. If it’s full, you
independently to enter. have to wait. Deals with managing access
- Bounded Waiting to a limited storage space.
There is a bound or limit on the number of 2. Readers-Writers Problem
times the other processes are allowed to Readers can read as long as no writer is
enter their critical sections. writing, but when a writer is working,
readers have to wait. Writers can only
Peterson’s Solution (Software-based start writing when there are no readers.
Approach Solution) Balancing reading and writing access to
- Used to synchronize two shared data.
processes 3. Dining-Philosophers Problem
- Uses two variables (turn and flag) Philosophers sitting at a table need two
- Turn indicates which process has forks to eat. They can only eat if they can
their turn to enter pick up both forks, which means only a
- Flag indicates if the process is certain number of philosophers can eat at
ready to enter the same time. It’s a problem of resource
allocation and avoiding deadlock.
Deadlocks
It is a situation where a set of processes
are blocked because each process is
holding a resource and waiting for another
resource acquired by some other process.

Must-Condition for Deadlock

- Mutual Exclusion
- Hold and Wait
- No Preemption
- Circular Wait

Methods for Handling Deadlocks

1. Deadlock Prevention or Avoidance
NEVER let the system enter a deadlocked
2. Deadlock Detection and Recovery
Let the deadlock occur then do
preemption to handle it once occurred
3. Ignore the problem altogether
If deadlock rare, let it happen and reboot

Banker’s Algorithm for Avoidance

Key Terms:
- Allocation Matrix
- Max Need Matrix
- Need Matrix
- Available Matrix
Formulas Needed:
1. Need = Max Need - Allocation
2. P0 Available = Total Matrix - Total
Alloc.
3. Next Available Value =
● If yes = Available + Allocation
● If no = Go to the next process
(note: Repeat until you get the same exact
value at the end to the value of the Total
Matrix).
4. Sequence = sequence of the
process executed