FIT1047 – Week 6
Operating Systems (Part 1 & Part 2) Assignment Discussion
FIT1047 Monash University
Important People
https://en.wikipedia.org/wiki/Dennis_Ritchie
FIT1047 Monash University
Important People
https://en.wikipedia.org/wiki/Bill_Gates
FIT1047 Monash University
Important People
https://time.com/3726660/steve-jobs-homebrew/
FIT1047 Monash University
Important People
https://en.wikipedia.org/wiki/Linus_Torvalds
FIT1047 Monash University
What does an OS do?
FIT1047 Monash University
What does an OS do?
FIT1047 Monash University
What does an OS do?
FIT1047 Monash University
What does an OS do?
FIT1047 Monash University
What does an OS do?
An OS is a level of abstraction between hardware and user software:
FIT1047 Monash University
What does an OS do?
● Process management
○ A process is a running program
● Memory management ● I/O
(it does more, but that’s what we will cover)
A bit of history
FIT1047 Monash University
First Operating Systems
● Just a library
○ A library is a collection of subroutines that programmers can include in
their programs
● No support for multiprogramming
○ Only a single program could run at a time ● No protection
○ Running program could read/write entire memory and disk
FIT1047 Monash University
Multiprogramming
● OS runs multiple processes “simultaneously”
● Improves CPU utilisation
● Important when computers were very expensive
This requires protection:
● Protect memory of other processes
● Protect files of other users
Gave rise to the UNIX family of operating systems
FIT1047 Monash University
Modern Operating Systems
● Hundreds of processes running at any point in time
● Provide access to diverse hardware
● Full network support built-in
● Are somewhat related to UNIX
○ Linux: free re-implementation of UNIX
○ macOS: based on BSD UNIX
○ Windows: not directly related but heavily influenced
Goals of an Operating System
FIT1047 Monash University
Main Goal: Ease of Use
For end users:
● Provide consistent user interface
● Manage multiple applications simultaneously
● Protect users from running malicious or buggy code
For programmers:
● Provide programming interface (uses a lot of library subroutines via O.S)
● Enable access to hardware and I/O (via O.S)
● Manage system resources (memory, disk, network)
Introduce a level of abstraction between hardware and software.
FIT1047 Monash University
Abstraction
The most important concept in IT!
● Hide complexity from users
● Provide clean, well-defined interface to functionality Simple example: MARIE multiplication subroutine
● User does not need to know how it’s implemented
● Provides a simple interface
FIT1047 Monash University
Abstraction in OSs
Virtualisation
● Provide virtual form of each physical resource for each process
This means you can code as if your program
● Has the entire CPU to itself
● Has a large, contiguous block of memory just for itself
● Can use system resources through library functions
○ e.g. keyboard, graphics, disk, network
FIT1047 Monash University
The OS kernel
Modern operating systems have many different functions. We are only looking at the core functionality.
The part of the OS that implements this is called the kernel.
FIT1047 Monash University
Virtualising the CPU
A CPU can only execute one instruction at a time.
How can we make it run several programs simultaneously?
Timesharing!
● OS kernel switches periodically between processes
● If switching is fast and occurs often, it creates the illusion of concurrency
● Illusion works both for programmers and end users
FIT1047 Monash University
Managing processes
Mechanisms:
● How to virtualise the CPU
● Rest of this lecture
Policies:
● When to switch between processes
FIT1047 Monash University
Processes
● Created by loading code into memory
● Can be in one of three states:
create
running
wait for I/O
de-schedule schedule
blocked
ready
I/O done
Terminated
FIT1047 Monash University
Process states
Time
1
2
3
4
5
6
7
8
9
10
Media Player (MP)
Running
Web browser (WB)
Ready
Description
FIT1047 Monash University
Process states
Time
1
2
3
4
5
6
7
8
9
10
Media Player (MP)
Running
Running
Running
Web browser (WB)
Ready
Ready
Ready
Description
MP initiates I/O
FIT1047 Monash University
Process states
Time
1
2
3
4
5
6
7
8
9
10
Media Player (MP)
Running
Running
Running
Blocked
Blocked
Web browser (WB)
Ready
Ready
Ready
Running
Running
Description
MP initiates I/O
Switch to WB
FIT1047 Monash University
Process states
Time
1
2
3
4
5
6
7
8
9
10
Media Player (MP)
Running
Running
Running
Blocked
Blocked
Ready
Ready
Web browser (WB)
Ready
Ready
Ready
Running
Running
Running
Running
Description
MP initiates I/O
Switch to WB
I/O finished
FIT1047 Monash University
Process states
Time
1
2
3
4
5
6
7
8
9
10
Media Player (MP)
Running
Running
Running
Blocked
Blocked
Ready
Ready
Running
Running
Ready
Web browser (WB)
Ready
Ready
Ready
Running
Running
Running
Running
Ready
Ready
Running
Description
MP initiates I/O
Switch to WB
I/O finished
Switch to MP
Switch to WB
FIT1047 Monash University
Challenges
Performance
● CPU virtualisation should not create huge overhead
Control
● OS must stay in control
● Enable fair scheduling (each process gets fair amount of time)
● Protect against malicious and buggy code
This requires hardware support!
Limited Direct Execution
FIT1047 Monash University
Limited Direct Execution
Application code runs directly on the CPU
So while application is running, clearly the OS is not! Two problems:
● How can the OS restrict what the program can do without affecting performance?
● How can the OS stop a process and switch to another one?
FIT1047 Monash University
Restricting what programs can do
Solution: CPUs have two different modes! Kernel mode:
● Code runs without any restrictions
● The OS runs in kernel mode
● Any interrupt triggers a switch into kernel mode
User mode:
● Only a limited subset of instructions is allowed
● E.g. No! I/O instructions
● Normal applications run in user mode
FIT1047 Monash University
Restricting what programs can do
Remember:
Kernel mode: no restrictions User mode: limited
Problem: how can a user application do I/O?
FIT1047 Monash University
System calls
Special instructions that expose OS functionality to user programs. Examples:
● Perform file I/O
● Access the network interface
● Communicate with other processes
● Allocate memory (we’ll talk about that later)
FIT1047 Monash University
System calls
OS has a table of system call handlers.
When a process makes a system call with number n,
● Save process context (registers etc) into memory
● Switch CPU to kernel mode
● Jump to handler n and execute it
● Restore process context
● Switch CPU to user mode
● Return to calling process
Sounds familiar? … interrupts, interrupt handlers etc..
FIT1047 Monash University
Software Interrupts
Recap of interrupts:
● Hardware triggers flag in the CPU
● CPU jumps to special code and then returns to running program
● Context switch makes sure program continues as if no interrupt had occurred
To implement systems calls:
● Add an instruction that causes an interrupt
● Also called software interrupt
● software interrupt: an interrupt generated within a CPU by executing an
instruction. Software interrupts are often used to implement system calls because they result in a subroutine call with a CPU
FIT1047 Monash University
Summary: Limited Direct Execution
● Application code runs directly on the CPU
● But we need to restrict what it can do
● CPU has two modes
○ Kernel mode (no restrictions)
○ User mode (some instructions are not allowed)
● System calls enable user code to call OS functions
Process Switching
FIT1047 Monash University
Process switching
Remember: User code runs directly on CPU, so while it’s running, no OS code is running.
How can the OS regain control over a running process?
Solution: any interrupt causes the switch from user code to kernel.
Recap from week 4: An interrupt performs a context switch and executes an interrupt handler.
Only difference with process switching is – it return to a different process.
FIT1047 Monash University
Process switching
Two variants:
● Cooperative (non-preemptive):
○ Switch into kernel when user code makes a system call, or when a hardware
interrupt happens
○ In cooperative scheduling, the processes cannot be scheduled.
○ the operating system never initiates a context switch from a running process
to another process
● Preemptive:
○ Wait for a timer interrupt
○ Preemptive scheduling can be preempted; the processes can be scheduled.
○ the operating system will initiates a context switch from a running process to
another process
FIT1047 Monash University
Cooperative timesharing
OS regains control when user mode process makes a system call.
● OS then checks whether to switch processes
● If no, just handle the system call and return to running process
● If yes, put running process into ready state, switch some other process from
ready state into running state
FIT1047 Monash University
Properties of Cooperative Timesharing
● Easy to implement
● But what if processes don’t cooperate?
● E.g. infinite loop without system calls
FIT1047 Monash University
Preemptive timesharing
OS sets up timer interrupt
● Timer is implemented in special hardware (Wait for a timer interrupt)
● “Fires” e.g. every 10 milliseconds
● Interrupt switches into kernel mode and executes interrupt handler
● Interrupt handler is part of OS, so OS can then switch to different process
FIT1047 Monash University
Properties of Preemptive Timesharing
● Needs hardware for timer interrupt
● Now OS always regains control at regular intervals!
FIT1047 Monash University
Summary Part 1
● OS makes hardware easier and safer to use
● Virtualisation:
○ Makes it look as if each process has exclusive access to the hardware
○ CPU has user and kernel mode
● System calls give user code access to OS (file system, network, memory, …)
● Cooperative vs. preemptive timesharing
FIT1047 – Week 6 Operating Systems (Part 2)
Process scheduling
● When to switch between processes
Virtual memory
● How to virtualise the RAM
FIT1047 Monash University
Part 2 learning objectives
Process scheduling
● When to switch between processes
Virtual memory
● How to virtualise the RAM
Process scheduling (when to switch)
FIT1047 Monash University
Scheduling policies
We’ve seen the mechanisms for process switching:
● User and kernel modes in the CPU
● Context switching
● Timer interrupts (for preemptive timesharing)
Now we need to look at policies:
● How long is each process allowed to run?
FIT1047 Monash University
Scheduling
Can aim for different goals: ● Turnaround time:
How long does a process take from arrival to finish?
● Fairness:
All processes get a fair share of processing time
FIT1047 Monash University
Poor turnaround
Schedule processes in some arbitrary order. E.g. first come first served:
On average, each process waits 7.6 time units to complete.
FIT1047 Monash University
Good turnaround
Order the processes from shortest to longest:
● Called as Shortest Job Next (SJN) or also known as Shortest Job First(SJF)
Average goes down to 5.4 time units! (this is in fact optimal)
FIT1047 Monash University
Turnaround scheduling
Works well if:
● All processes have known duration
● All processes are ready to run at the same time
● The goal is to reduce average turnaround
Unrealistic in modern operating systems:
● We don’t know how long a process will take to finish
● Some processes don’t finish at all as long as the computer is running
● We want multiple processes to run simultaneously
FIT1047 Monash University
Fairness – Round Robin Scheduling
Allocate time slices(quantum) for each process, schedule them in a round-robin fashion:
FIT1047 Monash University
Fairness – Round Robin Scheduling
Allocate time slices(quantum) for each process, schedule them in a round-robin fashion:
FIT1047 Monash University
Fairness – Round Robin Scheduling
Allocate time slices(quantum) for each process, schedule them in a round-robin fashion:
FIT1047 Monash University
Fairness – Round Robin Scheduling
Allocate time slices for each process, schedule them in a round-robin fashion:
FIT1047 Monash University
Fairness – Round Robin Scheduling
Allocate time slices for each process, schedule them in a round-robin fashion:
FIT1047 Monash University
Fairness
Allocate time slices for each process, schedule them in a round-robin fashion:
FIT1047 Monash University
Fairness – Round Robin Scheduling
Allocate time slices for each process, schedule them in a round-robin fashion:
FIT1047 Monash University
Fairness – Round Robin Scheduling
Allocate time slices for each process, schedule them in a round-robin fashion:
FIT1047 Monash University
Fairness – Round Robin Scheduling
Allocate time slices for each process, schedule them in a round-robin fashion:
FIT1047 Monash University
Fairness
Allocate time slices for each process, schedule them in a round-robin fashion:
FIT1047 Monash University
Fairness – Round Robin Scheduling
Allocate time slices for each process, schedule them in a round-robin fashion:
FIT1047 Monash University
Fairness – Round Robin Scheduling
Allocate time slices for each process, schedule them in a round-robin fashion:
FIT1047 Monash University
Fairness – Round Robin Scheduling
The shorter the time slice, the fairer the schedule!
But: each context switch takes time. OS needs to find the right compromise.
Modern OSs use a form of round-robin scheduling.
FIT1047 Monash University
Summary: scheduling
OS needs to decide when to run which process. Modern OS’s use a form of round-robin scheduling.
Virtual Memory
Virtual Memory
VIRTUAL MEMORY
FIT1047 Monash University
Virtual Memory
Reminder: user programs run directly on the CPU.
User mode: programs can only access I/O through system calls.
How can we prevent a process from accessing the memory of another process? Virtualise the memory!
FIT1047 Monash University
Virtual Memory
Goal: no process can access any memory except its own. Mechanism: each process has its own address space.
FIT1047 Monash University
Single process
Early computers:
● OS is just a library of subroutines
● Process has entire memory to itself
FIT1047 Monash University
Multiprogramming
● Every process gets a fixed block of memory
● But for the process it looks as if that
block starts at address 0
● OS/hardware ensures protection How can we make this work?
FIT1047 Monash University
Virtual addresses
Each process “thinks” its addresses start at 0.
i.e., programmers can write code as if addresses start at 0.
OS/Hardware translates these virtual addresses to physical memory locations. We call this abstraction virtual memory.
FIT1047 Monash University
Virtual memory: simple approach
Each process has a base address X, the start address of its address space in physical memory.
When a process accesses a virtual address Y, the CPU must access the physical address X + Y.
● Add a new register B (base register)
● When OS switches between processes: set B to process base address
● All instructions use B (base register)
● E.g. Load X now loads from address B+X
FIT1047 Monash University
Virtual memory: simple approach
Load 200
Add 300
Store 200
Halt
When switching to process A:
● Set (Base register B) to 0000A000
● Load from 0000A000+200
● Add from 0000A000+300
● Store into 0000A000+200
FIT1047 Monash University
Memory protection
Using Base register:
● Process cannot access any memory lower than B
How to protect from access beyond its address space?
Similarly simple fix:
● Add bounds to the register
(largest address that the current process may access)
● All instructions check that memory access is between B and bounds
● If access is outside of address space, raise an error
(an interrupt that gives control back to the OS)
FIT1047 Monash University
Virtual memory (realistic systems) Problems with the simple approach:
● Each process needs to get a fixed block
● No way to dynamically shrink or enlarge
Modern approach:
● Hardware and OS allocate smaller chunks of memory (called pages)
● Each process has a set of pages it can access
● Pages can be added and removed from processes
● Physical addresses of pages are mapped dynamically into process address
space
FIT1047 Monash University
Huge virtual memory
RAM is limited
● E.g. 8 GB may not be enough for all processes at the same time
Virtual memory is the solution:
● Save currently unused pages to external storage (hard disk)
● When a process tries to access an unavailable page: hardware creates interrupt (called “page fault”)
● OS handles interrupt and can load page back from external storage, swapping it for an unused page
Works very well if swapping is not too frequent!
FIT1047 Monash University
Summary
Scheduling
● Round-robin style scheduling with time slices to achieve fairness
Virtual memory
● Programmers can write code as if their program had entire memory to itself
● OS/hardware map virtual addresses to physical addresses
FIT1047 Monash University
Assignment 1 Discussion
FIT1047 Monash University
FIT1047 Monash University
Given the following truth table:
Take the truth table to obtain the standard Sum-of-Products expression.
Working from the Truth Table, for each row with a true output (i.e., containing 1) list the state of the input variables as a product term (i.e., an AND expression)
The AND expressions from each selected row can then be OR’ed together, yielding the Sum of Products form:
A
B
C
Output (F)
0
0
0
0
0
0
1
1
0
1
0
0
0
1
1
0
1
0
0
1
1
0
1
0
1
1
0
1
1
1
1
0
Sum of Products:
• •
•
𝑻𝒉𝒊𝒔 𝒊𝒔 𝒕𝒉𝒆 𝒓𝒆𝒒𝒖𝒊𝒓𝒆𝒅 (𝑺𝑶𝑷) 𝒃𝒐𝒐𝒍𝒆𝒂𝒏 𝒆𝒒𝒖𝒂𝒕𝒊𝒐𝒏 = 𝑭 𝑨,𝑩,𝑪 = 𝑨𝑩𝑪+𝑨𝑩𝑪+𝑨𝑩𝑪
a) Write a Boolean expression in the Sum-of-Products standard format that represents the logic function performed by this circuit.
Learn to reduce Sum of Products (SOP) using Karnaugh Map. Reduction rules for SOP using K-map Now we will write down the marked groups
and find the reduced expression.
Quad pair= W’Y’ 1st pair = XYZ 2nd pair = X’YZ’
Now the results of the reduced final expression is:-
F = W’Y’ + XYZ + X’YZ’
Sum of Products:
To obtain the standard Sum-of-Products expression.
Working from the Truth Table, for each row with a true output (i.e., containing Ones “1” ) list the state of the input variables as a product term (i.e., an AND expression).
The AND expressions from each selected row can then be OR’ed together, yielding the Sum of Products form:
• •
Exercise 2
Given the following truth table:
Working from the truth table, for each row with a zero output.
List the state of the input variables as a product term and complement this sum of products to get product of sums:
𝐹 = 𝐴 ̅ 𝐵 𝐶 ̅ + 𝐴 ̅ 𝐵 𝐶 ̅ + 𝐴 ̅ 𝐵 𝐶 + 𝐴 𝐵 𝐶 + 𝐴 𝐵 𝐶 𝐹 = 𝐴 ̅ 𝐵 𝐶 ̅ + 𝐴 ̅ 𝐵 𝐶 ̅ + 𝐴 ̅ 𝐵 𝐶 + 𝐴 𝐵 𝐶 + 𝐴 𝐵 𝐶
𝐹 = 𝐴 ̅ 𝐵 𝐶 ̅ 𝐴 ̅ 𝐵 𝐶 ̅ 𝐴 ̅ 𝐵 𝐶 𝐴 𝐵 𝐶 𝐴 𝐵 𝐶
𝑇h𝑖𝑠 𝑖𝑠 𝑡h𝑒 𝑟𝑒𝑞𝑢𝑖𝑟𝑒𝑑 𝑃𝑂𝑆 𝑏𝑜𝑜𝑙𝑒𝑎𝑛 𝑒𝑞𝑢𝑎𝑡𝑖𝑜𝑛
A
B
C
Output (F)
0
0
0
0
0
0
1
1
0
1
0
0
0
1
1
0
1
0
0
1
1
0
1
0
1
1
0
1
1
1
1
0
Product of Sums:
= 𝐹 𝐴,𝐵,𝐶
= ( 𝑨 + 𝑩 + 𝑪 ) ( 𝑨 + 𝑩 + 𝑪 ) ( 𝑨 + 𝑩 + 𝑪 ) ( 𝑨 + 𝑩 + 𝑪 ) ( 𝑨 + 𝑩 + 𝑪 )
b) From the truth table: convert the logic function into the Product-of-Sums standard format.
Learn to reduce Product of Sum (POS) using Karnaugh Map. Reduction rules for POS using K-map Product of Sums: Working from the truth
table, for each row with a zero output,
list the state of the input variables as a product term and complement this sum of products to get product of sums
Now we will write down the marked groups and find the reduced expression.
Quad pair= WY’
1st pair = X’YZ 2nd Pair = XYZ’
Now the results of the reduced final expression is:- F’ = WY’ + X’YZ + XYZ’
F= WY’ + X’YZ + XYZ’
F= WY’ X’YZ XYZ’
F = (W’+Y) (X+Y’+Z’) (X’+Y’+Z)
FIT1047 Monash University
FIT1047 Monash University
FIT1047 Monash University
FIT1047 Monash University
FIT1047 Monash University
FIT1047 Monash University
Unicode or ASCII table = https://naveenr.net/unicode-character-set-and-utf- 8-utf-16-utf-32-encoding/
Assignment 1 submission reminder
• Upload one single zip file
(see instructions on assignment specifications for files inclusion):
Submission format:
Prepare for Assignment 1 submission
PDF for the written tasks,
LogiSim circuit files for task 1
MARIE assembly files for task 2
All files(zipped) must be uploaded electronically via Moodle.
Submit your assignment and click submit, Don’t leave it in “Draft mode”
+
Reflective Journal/Diary for Lab/Tutorial week-1 to week-5 (500 Words to be submitted along with the Assignment-1)
• Deadline this week approaching Friday 11:55 PM (Week-6)
Due date is 18th December 2020 Extended until 11:55 PM.
• Late submission is possible (with a penalty). One day late means 5% minus marks