Computer Systems and Operating System Architectures
undefined
C
o
m
p
u
t
e
r
S
y
s
t
e
m
s
Operating systems
Jakub Yaghob
O
p
e
r
a
t
i
n
g
s
y
s
t
e
m
–
r
o
l
e
Abstract machine
Presented by kernel
API
System calls
Hide HW complexity
Resource manager
All HW managed by
OS
Sharing HW among
applications
C
P
U
m
o
d
e
s
User mode
Available to all application
Limited
or no access to some resources
Registers, instructions
Kernel (system) mode
More privileged
Used by OS or by only part of OS
Full access to all resources
A
r
c
h
i
t
e
c
t
u
r
e
–
m
o
n
o
l
i
t
h
i
c
Monolithic systems
Big mess – no structure
“Early days”
Linux
Collection of procedures
Each one can call another one
No information hiding
Efficient use of resources, efficient code
Originally no extensibility
Now able to load modules dynamically
Entry point
Service
proc
Utility
proc
A
r
c
h
i
t
e
c
t
u
r
e
–
l
a
y
e
r
e
d
Evolution of monolithic system
Organized into hierarchy of layers
Layer n+1 uses exclusively services supported by
layer n
Easier to extend and evolve
A
r
c
h
i
t
e
c
t
u
r
e
–
m
i
c
r
o
k
e
r
n
e
l
Microkernel architecture
Move as much as possible from the kernel space
to the user space
Communication between user modules
Message passing
Client/server
Extendable
Secure
Reliable
μ
Kernel
Svc 1
Svc 2
App
L
i
n
u
x
k
e
r
n
e
l
a
r
c
h
i
t
e
c
t
u
r
e
W
i
n
d
o
w
s
k
e
r
n
e
l
a
r
c
h
i
t
e
c
t
u
r
e
D
e
v
i
c
e
s
Terminology
Device
“a thing made for a particular purpose”
Device controller
Handles “electrically” connected devices
Signals on a “wire”, A/D converters
Devices connected in a topology
Device driver
SW component, part of OS
Abstract interface to the upper layer in OS
Specific for a controller or a class/group of controllers
D
e
v
i
c
e
s
t
o
p
o
l
o
g
y
DC
Bus
Dev1
Dev2
Dev3
DC
Dev1
Dev2
Dev3
Ring
Star
DC
Dev1
Dev2
Dev3
Dev4
Tree
DC
Dev1
Dev2
Dev3
Dev4
Hub1
D
e
v
i
c
e
h
a
n
d
l
i
n
g
1.
Application issues an I/O request
2.
Language library makes a system call
3.
Kernel decides, which device is
involved
4.
Kernel starts an I/O operation using
device driver
5.
Device driver initiates an I/O operation
on a device controller
6.
Device does something
7.
Device driver checks for a status of the
device controller
8.
When data are ready, transfer data
from device to the memory
9.
Return to any kernel layer and make
other I/O operation fulfilling the user
request
10.
Return to the application
User I/O libraries
Device independent
I/O
Device
driver
Device
driver
Device
controller
Device
controller
Device
Device
User
Kernel
HW
D
e
v
i
c
e
i
n
t
e
r
c
o
m
m
u
n
i
c
a
t
i
o
n
Polling
CPU actively checks device status change
Interrupt
Device notifies CPU that it needs attention
CPU interrupts current execution flow
IRQ handling
CPU has at least one pin for requesting interrupt
DMA (Direct Memory Access)
Transfer data to/from a device without CPU attention
DMA controller
Scatter/gather
I
n
t
e
r
r
u
p
t
t
y
p
e
s
External
HW source using an IRQ pin
Masking
Exception
Unexpectedly triggered by an instruction
Trap or fault
Predefined set by CPU architecture
Software
Special instruction
Can be used for system call mechanism
I
n
t
e
r
r
u
p
t
r
e
q
u
e
s
t
h
a
n
d
l
i
n
g
What happens, when an interrupt occurs?
CPU decides the source of the interrupt
Predefined
IRQ controller
CPU gets an address of interrupt handler
Fixed
Interrupt table
Current stream of instructions is interrupted, CPU begins
execution of interrupt handler’s instructions
Usually between instructions
Privilege switch usually happens, interrupt handler is part of a kernel
Interrupt handler saves the CPU state
Interrupt handler do something useful
Interrupt handler restores the CPU state
CPU continues with original instruction stream
CPU
IRQ
controller
INT
#INT
P
r
o
c
e
s
s
i
n
g
Program
A passive set of instruction and data
Created by a compiler/linker
Process
An instance of a program created by OS
It contains program code and data
Process address space
The program is “enlivened” by an activity
Instructions are executed by CPU
Owns other resources
Thread
One activity in a process
Stream of instructions executed by CPU
Unit of kernel scheduling
Fiber
Lighter unit of scheduling
Cooperative scheduling
Running fiber explicitly yields
Heap
Code
Static data
Stack for thread 1
Stack for thread 2
T1
T2
P
r
o
c
e
s
s
i
n
g
Scheduler
Part of OS
Uses scheduling algorithms to assign computing resources to
scheduling units
Multitasking
Concurrent executions of multiple processes
Multiprocessing
Multiple CPUs in one system
More challenging for the scheduler
Context
CPU (and possibly other) state of a scheduling unit
Registers (including PC)
Context switch
Process of storing the context of a scheduling unit, which is now paused,
and restoring the context of another scheduling unit, which resumes its
execution
R
e
a
l
-
t
i
m
e
s
c
h
e
d
u
l
i
n
g
Real-time scheduling
RT process has a start time (release time) and a stop
time (deadline)
Release time – time at which the process must start
after some event occurred
Deadline – time by which the task must complete
Hard – no value to continue computation after the deadline
Soft – the value of late result diminishes with time after the
deadline
U
n
i
t
o
f
s
c
h
e
d
u
l
i
n
g
s
t
a
t
e
Created
Awaits admission
Terminated
Until parent process
waits for result
Ready
Wait for scheduling
Running
CPU assigned
Blocked
Wait for resources
Created
Blocked
Ready
Running
Terminated
(zombie)
M
u
l
t
i
t
a
s
k
i
n
g
Cooperative
OS does not initiate context switch
Unit of scheduling must explicitly and voluntarily yield control
All processes must cooperate
Scheduling in OS reduced on starting the process and making
context switch after the yield
Preemptive
Each running unit of scheduling has assigned a time-slice
OS needs some external source of interrupt
Timer
If the unit of scheduling blocks or is terminated before the time-
slice ends, nothing interesting will happen
If the unit of scheduling consumes the whole time-slice, it will be
interrupted by the external source, OS will make context switch,
and the unit of scheduling is moved to the READY state
S
c
h
e
d
u
l
i
n
g
Objectives
Maximize CPU utilization
Fair allocation of CPU
Maximize throughput
Number of processes that complete their execution per time
unit
Minimize turnaround time
Time taken by a process to finish
Minimize waiting time
Time a process waits in READY state
Minimize response time
Time to response for interactive applications
S
c
h
e
d
u
l
i
n
g
–
p
r
i
o
r
i
t
y
Priority
A
number expressing the importance of the process
Unit of scheduling with greater priority should be scheduled
before unit of scheduling with lower priority
Static priority
Assigned at the start of the process
Users hierarchy or importance
Dynamic priority
Adding fairness to the scheduling
The priority of the process is the sum of a static priority and dynamic
priority
Once in a time the dynamic priority is increased for all READY units
of scheduling
The dynamic priority is initialized to 0 and is reset to 0 after the unit of
scheduling is scheduled for execution
S
c
h
e
d
u
l
i
n
g
a
l
g
o
r
i
t
h
m
s
–
n
o
n
-
p
r
e
e
m
p
t
i
v
e
First Come, First Serve (FCFS)
Simple queue, process enters the queue on the
tail, the head process has CPU assigned and
runs, then is removed from the queue
Shortest Job First
Maximizes throughput
Expected job execution time must be known in
advance
Longest Job first
S
c
h
e
d
u
l
i
n
g
a
l
g
o
r
i
t
h
m
s
–
p
r
e
e
m
p
t
i
v
e
Round Robin
Like FCFS, there is a queue
Each unit of scheduling has assigned time-slice
If the unit of scheduling consumes whole time-
slice or is blocked, it will be assigned to the tail of
the queue
US
US
US
US
CPU
S
c
h
e
d
u
l
i
n
g
a
l
g
o
r
i
t
h
m
s
–
p
r
e
e
m
p
t
i
v
e
Multilevel feedback-queue
Multiple queues
Each level has assigned greater time-slice
If the unit of scheduling consumes the whole time-slice, it will be
assigned to the lower queue
If the unit of scheduling blocks before consuming the whole time-
slice, it will be assigned to the higher queue
Schedule head unit of scheduling from the highest non-empty
queue
US
US
US
US
CPU
US
US
US
US
US
US
US
US
S
c
h
e
d
u
l
i
n
g
a
l
g
o
r
i
t
h
m
s
-
p
r
e
e
m
p
t
i
v
e
Completely fair scheduler (CFS)
Implemented in Linux kernel
Processes are in red-black tree
Indexed by execution time
Maximum execution time
Time-slice calculated for each process
The time waiting to run divided by the total number of processes
Scheduling algorithm
The leftmost node is selected (lowest execution time)
If the process completes its execution, it is removed from scheduling
If the process reaches its maximum execution time or is somehow
stopped or interrupted, it is reinserted into the tree based on its new
execution time
F
i
l
e
File
Collection of related information
Stored on secondary storage (?)
Abstract stream of data
Operations
Open, close, read, write, seek
Access
Sequential, random
Type
Extension
Attributes
Name, timestamps, size, access, …
F
i
l
e
d
i
r
e
c
t
o
r
y
Directory
Collection of files
Efficiency – a file can be located more quickly
Naming – better navigation for users
Grouping – logical grouping of files
Usually represented as a file of a special type
Store file attributes
Hierarchy or structure
Root
Operations
Create/delete/rename file/subdirectory
Search for a name
List members
F
i
l
e
s
y
s
t
e
m
File system
Controls, how and where data are stored
Creates an abstraction for files and directories
Responsibility
Name translation
File data location
Free blocks management
Bitmap, linked list
Local file system
Stored on HDD, SSD, removable media
FAT, NTFS, ext234, XFS, …
Network file system
Access to files/directories over a network stack
NFS, CIFS/SMB, …
F
A
T
File Allocation Table (FAT)
Simple, old, MS-DOS, many variants used today
One structure (FAT) for managing free blocks and file data
location
Directory
Sequence of entries with fixed size and attributes
Starting cluster, name+ext, size, timestamps, attributes
Root in fixed position
Directory
a.txt
13
b.txt
3
0
2
10
3
0
4
-1
5
0
6
0
7
5
8
0
9
15
10
0
11
0
12
8
13
-1
14
14
15
0
16
0
17
Boot record
FAT1
Data
FAT2
FAT
Root directory
e
x
t
2
Second extended file system (ext2)
Simple, old, Linux
Inode (index node)
Represents one file/directory
Directory
Sequence of entries with fixed structure
Inode, name
Boot record
Block group 0
Block group 1
Block group N
Superblock
Descriptor
Data bitmap
Inode bitmap
Data block
Inode table
Info
Block 0
Block 1
Block 11
Block 12 (I)
Block 13 (DI)
Block 14 (TI)
Data
block
Data
block
Data
block
Block 0
Block 127
Data
block
Data
block
H
a
r
d
d
i
s
c
m
e
c
h
a
n
i
c
s
Other names
Block – the same sector on all platters
Cluster – the same track on all platters
Flying height – distance between head and platter (~5 nm)
Rotational speed – 5400, 7200, 10k, 15k rpm
spindle
platter
RW head
arm
track
sector
D
i
s
k
s
c
h
e
d
u
l
i
n
g
a
l
g
o
r
i
t
h
m
s
What?
Scheduling of I/O requests for the disk
Originally done by OS, now by disk itself
Why?
Disk access time = Seek Time + Rotational Latency + Transfer time
Seek Time – time to locate the arm to a track (~ms)
Rotational latency – time to rotate a sector to the fixed position of heads
Transfer time – time to transfer data
Minimize disk access time for multiple I/O requests
Examples
All algorithms demonstrated with the same pattern of I/O requests and
initial position
I/O requests - 82, 170, 43, 61, 24, 16, 190
Initial position - 50
D
i
s
k
s
c
h
e
d
u
l
i
n
g
a
l
g
o
r
i
t
h
m
s
FCFS
First Come First Served
Pros
Fair chance for all requests
Simple, good for light load
Cons
No optimization – usually not the best
0
16
43
24
50
82
61
170
190
199
D
i
s
k
s
c
h
e
d
u
l
i
n
g
a
l
g
o
r
i
t
h
m
s
SSTF
Shortest Seek Time First
Pros
Average access time decreases
Increased throughput
Cons
Possible starvation for distant requests, when new short seek requests arrive
0
16
43
24
50
82
61
170
190
199
D
i
s
k
s
c
h
e
d
u
l
i
n
g
a
l
g
o
r
i
t
h
m
s
SCAN
Elevator
Has direction
Pros
High throughput – good for heavy loads
Low variance in access time
Cons
Long waiting times for new request just visited by the arm
0
16
43
24
50
82
61
170
190
199
D
i
s
k
s
c
h
e
d
u
l
i
n
g
a
l
g
o
r
i
t
h
m
s
CSCAN
Circular SCAN
Pros
More uniform time compared to SCAN
0
16
43
24
50
82
61
170
190
199
D
i
s
k
s
c
h
e
d
u
l
i
n
g
a
l
g
o
r
i
t
h
m
s
LOOK/CLOOK
Like SCAN/CSCAN but does not visit ends of the disk
FSCAN
Two queues
Compute algorithm only for 1
st
queue, new requests are
inserted to the 2
nd
one
0
16
43
24
50
82
61
170
190
199
V
i
r
t
u
a
l
m
e
m
o
r
y
Basic concepts
All memory accesses from instructions work with virtual
address
Virtual address space
Even instruction fetch
Operating memory provides physical memory
Physical address space
Always 1-dimensional
Memory controller uses physical addresses
Translation mechanism
Implemented in HW (MMU)
Translates a virtual address to a physical address
The translation (mapping) may not exist
Exception
Two basic mechanisms – segmentation, paging
V
i
r
t
u
a
l
m
e
m
o
r
y
Heap
Code
Uninitialized static data
Stack for thread
n
Stack for thread 1
Constants
Initialized static data
VAS = process address space
MMU
VA
PAS = available memory
PA
V
i
r
t
u
a
l
m
e
m
o
r
y
Why?
More address space
VAS can be larger then PAS
IA-32 can have larger PAS then VAS
Add a secondary storage as a memory backup/swap
This is no longer the primary reason today
Security
Process address space separation
“Separation” of logical segments in a process address
space
S
e
g
m
e
n
t
a
t
i
o
n
Concepts
Virtual (process) address space divided into logical segments
Segments are numbered
Virtual address has two parts
[segment number; segment offset]
Offsets 0-based for each segment
Segment table
In memory, for each process
Stores base physical address, length, and attributes for each segment
Indexed by the segment number
Segment fault
seg
VA
offs
Seg table
BPA
len
+
Heap
Code
Uninitialized static data
Stack for thread
Constants
Initialized static data
offs
Constants
Code
Heap
Stack for thread
offs
P
a
g
i
n
g
Concepts
VAS divided into equal parts
Page, 2
n
size
PAS divided into equal parts
Frame, equal size with page
VA 1-dimensional
Page table
In memory, for each process
Indexed by a page number
Each entry contains a frame number and attributes (P)
Page fault
0
1
2
p
2
N-n
-1
offs
p
offs
Virtual address
0
n-1
N-1
f
0
1
f
2
P-n
-1
offs
f
offs
Physical address
0
n-1
P-1
P
a
g
e
t
a
b
l
e
–
1
-
l
e
v
e
l
0
1
2
14
2
N-n
-1
123
1111
3333
456
2
N-n
-1
17
NA
222
0
1
2
17
2
P-n
-1
222
456
Page fault
P
a
g
e
t
a
b
l
e
–
p
r
o
b
l
e
m
s
Size
1-level page table, 32-bit VA/PA, 4k pages/frames (12 bits)
Size of the page table entry?
Size of the page table?
Do we really need the whole VA?
Multilevel page tables
1
st
level always in memory
Other levels can be missing
Speed
Each memory access from an instruction means at least one
other memory access to the page table
TLB (Translation Lookaside Buffer)
Associative memory
Cache for translating page number to a frame number
0-level page tables
P
a
g
e
t
a
b
l
e
–
2
-
l
e
v
e
l
PT index 1
PT index 2
offset
Virtual address
0
11
21
31
10
PT1
PTAR
4k
1024 entries
10
PT2
4k
1024 entries
offs
4k
P
a
g
e
t
a
b
l
e
–
r
e
a
l
A
M
D
6
4
e
x
a
m
p
l
e
P
a
g
i
n
g
–
a
d
d
r
e
s
s
t
r
a
n
s
l
a
t
i
o
n
Steps for address translation
Take page number from VA, keep offset
Check TLB for mapping
If exists, retrieve frame number, otherwise continue
Go through page table
Divide page number into multiple PT indices
Index 1
st
level PT
If there is no mapping for 2
nd
level PT, raise page fault exception
Retrieve PA for 2
nd
level PT and continue
Go through all levels of PTs
If there is no mapping in any PT level, raise page fault exception
If all PT levels are mapped, retrieve frame number
Save retrieved mapping to TLB
Update A and D bits in page table/TLB
Assemble PA by “gluing” the retrieved frame number and the
original offset from VA
P
a
g
i
n
g
–
p
a
g
e
f
a
u
l
t
e
x
c
e
p
t
i
o
n
h
a
n
d
l
i
n
g
An instruction raises the page fault exception
OS interrupt handler
Determine the cause of the fault
Unauthorized access
Out of allocated virtual space
Store to R/O page, access to kernel memory
Valid address but not mapped
Create mapping
Find a free frame
Either there is one unoccupied
Or find a victim
Page replacement algorithms
Save dirty victim frame
Remove mapping from TLB
Load content to the free frame
Construct/fill corresponding page tables
Return back from handler and retry the instruction
P
a
g
e
r
e
p
l
a
c
e
m
e
n
t
a
l
g
o
r
i
t
h
m
s
Using
Any situation, when you need to find a victim from
a limited space
Frames, TLB, cache, …
Optimal page algorithm
Replace the page that won’t be used for the
longest period of time
Lowest page-fault rate
Theoretical, we don’t have an oracle for foretelling
the future
1
A=0
0
A=0
P
a
g
e
r
e
p
l
a
c
e
m
e
n
t
a
l
g
o
r
i
t
h
m
s
Clock
Frames organized in a
circular manner
Clock hand points to the
next frame to replace
If the frame has A!=0,
set A=0 and advance
the hand
If the frame has A==0,
select this frame
2
3
4
5
A=1
A=1
A=0
A=1
A=0
A=1
P
a
g
e
r
e
p
l
a
c
e
m
e
n
t
a
l
g
o
r
i
t
h
m
s
NRU
Not Recently Used
Clear A bits periodically
Use A and D bits to classify frames into four
classes
Select random frame from the lowest non-empty
class
P
a
g
e
r
e
p
l
a
c
e
m
e
n
t
a
l
g
o
r
i
t
h
m
s
LRU
Least Recently Used
Use the recent past as a prediction of the near future
Replace the page that hasn’t been referenced for the
longest time
Existing HW implementations
Cache
Bit matrix
SW implementation
Stack
Too complicated and space consuming
Use an approximation
P
a
g
e
r
e
p
l
a
c
e
m
e
n
t
a
l
g
o
r
i
t
h
m
s
NFU
Not Frequently Used
Each frame has a counter
Periodically scan page table and increase the counter
for a frame, when A==1
Always clear A
Select the frame with lowest counter
Problem: frames that were previously heavy used will
never be selected
Aging
Periodically divide counters by 2
A
d
v
a
n
c
e
d
p
a
g
i
n
g
Shared memory
Part of a virtual memory space shared amongst processes
The block is probably placed on different starting virtual address
Memory-mapped files
File as a backing store for paging
Direct access to the file content using CPU instructions
Problems with file size and with appending data
VAS1
PAS
PT1
VAS2
PT2
VAS
File
V
i
r
t
u
a
l
m
a
c
h
i
n
e
a
n
d
c
o
n
t
a
i
n
e
r
s
VM = Emulation of a computer system
Full virtualization
Substitute for a real machine, allows execution of entire OS
Hypervisor shares real HW, native execution, virtual HW
Isolation, encapsulation, compatibility
Process VM
Runs as an application inside OS
Provides platform-independent programming environment
Abstract machine (instructions, memory, registers, …)
Java VM, .NET CLR
Slow execution
JIT, AOT
Container = OS-level virtualization
OS kernel allows existence of multiple isolated user space
instances
P
h
y
s
i
c
a
l
m
a
c
h
i
n
e
Physical HW
CPU, RAM, disks,
I/O
Underutilized HW
SW
Single active OS
OS controls HW
V
i
r
t
u
a
l
m
a
c
h
i
n
e
HW-level abstraction
Virtual HW: CPU, RAM,
disks, I/O
Virtualization SW
Decouples HW and OS
Multiplexes physical HW
across multiple guest VMs
Strong isolation between
VMs
Manages physical
resources, improves
utilization
Encapsulation – VM
represented as a set of files,
can be easily distributed
An exploration of computer systems and operating system architectures, covering topics such as CPU modes, monolithic and layered architectures, microkernel architecture, Linux and Windows kernel architectures, as well as devices and their terminology. The content delves into the roles, structures, and evolution of different operating system designs and hardware management concepts.
Download Presentation
Please find below an Image/Link to download the presentation.
The content on the website is provided AS IS for your information and personal use only. It may not be sold, licensed, or shared on other websites without obtaining consent from the author. Download presentation by click this link. If you encounter any issues during the download, it is possible that the publisher has removed the file from their server.
E N D
Presentation Transcript
Computer Systems Operating systems Jakub Yaghob
Operating system role Abstract machine Presented by kernel API System calls Hide HW complexity Resource manager All HW managed by OS Sharing HW among applications
CPU modes User mode Available to all application Limited or no access to some resources Registers, instructions Kernel (system) mode More privileged Used by OS or by only part of OS Full access to all resources
Architecture monolithic Monolithic systems Big mess no structure Early days Linux Collection of procedures Each one can call another one No information hiding Efficient use of resources, efficient code Originally no extensibility Now able to load modules dynamically Entry point Service proc Utility proc
Architecture layered Evolution of monolithic system Organized into hierarchy of layers Layer n+1 uses exclusively services supported by layer n Easier to extend and evolve
Architecture microkernel Microkernel architecture Move as much as possible from the kernel space to the user space Communication between user modules Message passing Client/server Extendable Secure Reliable Svc 1 Svc 2 App Kernel
Devices Terminology Device a thing made for a particular purpose Device controller Handles electrically connected devices Signals on a wire , A/D converters Devices connected in a topology Device driver SW component, part of OS Abstract interface to the upper layer in OS Specific for a controller or a class/group of controllers
Devices topology DC DC Bus Ring Dev1 Dev2 Dev3 Dev1 Dev3 Dev2 Tree DC Dev1 Dev2 Star DC Dev1 Dev2 Hub1 Dev3 Dev4 Dev3 Dev4
Device handling Application issues an I/O request Language library makes a system call Kernel decides, which device is involved Kernel starts an I/O operation using device driver Device driver initiates an I/O operation on a device controller Device does something Device driver checks for a status of the device controller When data are ready, transfer data from device to the memory Return to any kernel layer and make other I/O operation fulfilling the user request Return to the application 1. 2. User User I/O libraries 3. 4. Device independent I/O 5. Kernel Device driver Device driver 6. 7. Device controller Device controller 8. HW 9. Device Device 10.
Device intercommunication Polling CPU actively checks device status change Interrupt Device notifies CPU that it needs attention CPU interrupts current execution flow IRQ handling CPU has at least one pin for requesting interrupt DMA (Direct Memory Access) Transfer data to/from a device without CPU attention DMA controller Scatter/gather
Interrupt types External HW source using an IRQ pin Masking Exception Unexpectedly triggered by an instruction Trap or fault Predefined set by CPU architecture Software Special instruction Can be used for system call mechanism
Interrupt request handling What happens, when an interrupt occurs? CPU decides the source of the interrupt Predefined IRQ controller CPU gets an address of interrupt handler Fixed Interrupt table Current stream of instructions is interrupted, CPU begins execution of interrupt handler s instructions Usually between instructions Privilege switch usually happens, interrupt handler is part of a kernel Interrupt handler saves the CPU state Interrupt handler do something useful Interrupt handler restores the CPU state CPU continues with original instruction stream IRQ controller #INT INT CPU
Processing Program A passive set of instruction and data Created by a compiler/linker Process An instance of a program created by OS It contains program code and data Process address space The program is enlivened by an activity Instructions are executed by CPU Owns other resources Thread One activity in a process Stream of instructions executed by CPU Unit of kernel scheduling Fiber Lighter unit of scheduling Cooperative scheduling Running fiber explicitly yields Code T1 T2 Static data Stack for thread 1 Stack for thread 2 Heap
Processing Scheduler Part of OS Uses scheduling algorithms to assign computing resources to scheduling units Multitasking Concurrent executions of multiple processes Multiprocessing Multiple CPUs in one system More challenging for the scheduler Context CPU (and possibly other) state of a scheduling unit Registers (including PC) Context switch Process of storing the context of a scheduling unit, which is now paused, and restoring the context of another scheduling unit, which resumes its execution
Real-time scheduling Real-time scheduling RT process has a start time (release time) and a stop time (deadline) Release time time at which the process must start after some event occurred Deadline time by which the task must complete Hard no value to continue computation after the deadline Soft the value of late result diminishes with time after the deadline
Unit of scheduling state Created Awaits admission Terminated Until parent process waits for result Ready Wait for scheduling Running CPU assigned Blocked Wait for resources Terminated (zombie) Created Running Ready Blocked
Multitasking Cooperative OS does not initiate context switch Unit of scheduling must explicitly and voluntarily yield control All processes must cooperate Scheduling in OS reduced on starting the process and making context switch after the yield Preemptive Each running unit of scheduling has assigned a time-slice OS needs some external source of interrupt Timer If the unit of scheduling blocks or is terminated before the time- slice ends, nothing interesting will happen If the unit of scheduling consumes the whole time-slice, it will be interrupted by the external source, OS will make context switch, and the unit of scheduling is moved to the READY state
Scheduling Objectives Maximize CPU utilization Fair allocation of CPU Maximize throughput Number of processes that complete their execution per time unit Minimize turnaround time Time taken by a process to finish Minimize waiting time Time a process waits in READY state Minimize response time Time to response for interactive applications
Scheduling priority Priority A number expressing the importance of the process Unit of scheduling with greater priority should be scheduled before unit of scheduling with lower priority Static priority Assigned at the start of the process Users hierarchy or importance Dynamic priority Adding fairness to the scheduling The priority of the process is the sum of a static priority and dynamic priority Once in a time the dynamic priority is increased for all READY units of scheduling The dynamic priority is initialized to 0 and is reset to 0 after the unit of scheduling is scheduled for execution
Scheduling algorithms non- preemptive First Come, First Serve (FCFS) Simple queue, process enters the queue on the tail, the head process has CPU assigned and runs, then is removed from the queue Shortest Job First Maximizes throughput Expected job execution time must be known in advance Longest Job first
Scheduling algorithms preemptive Round Robin Like FCFS, there is a queue Each unit of scheduling has assigned time-slice If the unit of scheduling consumes whole time- slice or is blocked, it will be assigned to the tail of the queue CPU US US US US
Scheduling algorithms preemptive Multilevel feedback-queue Multiple queues Each level has assigned greater time-slice If the unit of scheduling consumes the whole time-slice, it will be assigned to the lower queue If the unit of scheduling blocks before consuming the whole time- slice, it will be assigned to the higher queue Schedule head unit of scheduling from the highest non-empty queue CPU US US US US US US US US US US US US
Scheduling algorithms - preemptive Completely fair scheduler (CFS) Implemented in Linux kernel Processes are in red-black tree Indexed by execution time Maximum execution time Time-slice calculated for each process The time waiting to run divided by the total number of processes Scheduling algorithm The leftmost node is selected (lowest execution time) If the process completes its execution, it is removed from scheduling If the process reaches its maximum execution time or is somehow stopped or interrupted, it is reinserted into the tree based on its new execution time
File File Collection of related information Stored on secondary storage (?) Abstract stream of data Operations Open, close, read, write, seek Access Sequential, random Type Extension Attributes Name, timestamps, size, access,
File directory Directory Collection of files Efficiency a file can be located more quickly Naming better navigation for users Grouping logical grouping of files Usually represented as a file of a special type Store file attributes Hierarchy or structure Root Operations Create/delete/rename file/subdirectory Search for a name List members
File system File system Controls, how and where data are stored Creates an abstraction for files and directories Responsibility Name translation File data location Free blocks management Bitmap, linked list Local file system Stored on HDD, SSD, removable media FAT, NTFS, ext234, XFS, Network file system Access to files/directories over a network stack NFS, CIFS/SMB,
FAT File Allocation Table (FAT) Simple, old, MS-DOS, many variants used today One structure (FAT) for managing free blocks and file data location Directory Sequence of entries with fixed size and attributes Starting cluster, name+ext, size, timestamps, attributes Root in fixed position Boot record Directory FAT FAT1 2 0 3 10 4 0 5 -1 a.txt 13 6 0 7 0 8 5 9 0 FAT2 b.txt 10 15 11 0 12 0 13 8 3 Root directory 14 -1 15 14 16 0 17 0 Data
ext2 Second extended file system (ext2) Simple, old, Linux Inode (index node) Represents one file/directory Directory Sequence of entries with fixed structure Inode, name Superblock Descriptor Data bitmap Inode bitmap Data block Data block Info Boot record Data block Block 0 Block 1 Block group 0 Data block Block group 1 Inode table Block 11 Block 12 (I) Block 13 (DI) Block 14 (TI) Data block Block 0 Block group N Data block Block 127
Hard disc mechanics arm track spindle sector platter RW head Other names Block the same sector on all platters Cluster the same track on all platters Flying height distance between head and platter (~5 nm) Rotational speed 5400, 7200, 10k, 15k rpm
Disk scheduling algorithms What? Scheduling of I/O requests for the disk Originally done by OS, now by disk itself Why? Disk access time = Seek Time + Rotational Latency + Transfer time Seek Time time to locate the arm to a track (~ms) Rotational latency time to rotate a sector to the fixed position of heads Transfer time time to transfer data Minimize disk access time for multiple I/O requests Examples All algorithms demonstrated with the same pattern of I/O requests and initial position I/O requests - 82, 170, 43, 61, 24, 16, 190 Initial position - 50
Disk scheduling algorithms FCFS First Come First Served Pros Fair chance for all requests Simple, good for light load Cons No optimization usually not the best 0 16 43 24 50 61 82 170 190 199
Disk scheduling algorithms SSTF Shortest Seek Time First Pros Average access time decreases Increased throughput Cons Possible starvation for distant requests, when new short seek requests arrive 0 16 24 43 50 61 82 170 190 199
Disk scheduling algorithms SCAN Elevator Has direction Pros High throughput good for heavy loads Low variance in access time Cons Long waiting times for new request just visited by the arm 43 24 50 82 61 0 16 170 190 199
Disk scheduling algorithms CSCAN Circular SCAN Pros More uniform time compared to SCAN 0 16 24 43 50 61 82 170 190 199
Disk scheduling algorithms LOOK/CLOOK Like SCAN/CSCAN but does not visit ends of the disk FSCAN Two queues Compute algorithm only for 1st queue, new requests are inserted to the 2nd one 0 16 24 43 50 61 82 170 190 199
Virtual memory Basic concepts All memory accesses from instructions work with virtual address Virtual address space Even instruction fetch Operating memory provides physical memory Physical address space Always 1-dimensional Memory controller uses physical addresses Translation mechanism Implemented in HW (MMU) Translates a virtual address to a physical address The translation (mapping) may not exist Exception Two basic mechanisms segmentation, paging
Virtual memory VAS = process address space PAS = available memory Code Constants VA Initialized static data Uninitialized static data Stack for thread 1 MMU PA Stack for thread n Heap
Virtual memory Why? More address space VAS can be larger then PAS IA-32 can have larger PAS then VAS Add a secondary storage as a memory backup/swap This is no longer the primary reason today Security Process address space separation Separation of logical segments in a process address space
Segmentation Concepts Virtual (process) address space divided into logical segments Segments are numbered Virtual address has two parts [segment number; segment offset] Offsets 0-based for each segment Segment table In memory, for each process Stores base physical address, length, and attributes for each segment Indexed by the segment number Segment fault Code Seg table VA Heap offs Constants seg offs offs Constants Initialized static data + Uninitialized static data Stack for thread Stack for thread BPA Code len Heap
Paging Concepts VAS divided into equal parts Page, 2n size PAS divided into equal parts Frame, equal size with page VA 1-dimensional Page table In memory, for each process Indexed by a page number Each entry contains a frame number and attributes (P) Page fault 0 1 2 Virtual address n-1 N-1 0 1 Physical address P-1 n-1 0 offs f f offs 0 offs p p offs f 2N-n-1 2P-n-1
Page table 1-level 0 1 2 0 1 2 14 456 17 123 17 222 1111 NA 456 3333 222 Page fault 2P-n-1 2N-n-1 2N-n-1
Page table problems Size 1-level page table, 32-bit VA/PA, 4k pages/frames (12 bits) Size of the page table entry? Size of the page table? Do we really need the whole VA? Multilevel page tables 1st level always in memory Other levels can be missing Speed Each memory access from an instruction means at least one other memory access to the page table TLB (Translation Lookaside Buffer) Associative memory Cache for translating page number to a frame number 0-level page tables
Page table 2-level Virtual address 21 31 11 0 PT index 1 PT index 2 offset 10 10 PT1 PT2 PTAR offs 4k 4k 1024 entries 4k 1024 entries
Page table real AMD64 example
Paging address translation Steps for address translation Take page number from VA, keep offset Check TLB for mapping If exists, retrieve frame number, otherwise continue Go through page table Divide page number into multiple PT indices Index 1st level PT If there is no mapping for 2nd level PT, raise page fault exception Retrieve PA for 2nd level PT and continue Go through all levels of PTs If there is no mapping in any PT level, raise page fault exception If all PT levels are mapped, retrieve frame number Save retrieved mapping to TLB Update A and D bits in page table/TLB Assemble PA by gluing the retrieved frame number and the original offset from VA
Paging page fault exception handling An instruction raises the page fault exception OS interrupt handler Determine the cause of the fault Unauthorized access Out of allocated virtual space Store to R/O page, access to kernel memory Valid address but not mapped Create mapping Find a free frame Either there is one unoccupied Or find a victim Page replacement algorithms Save dirty victim frame Remove mapping from TLB Load content to the free frame Construct/fill corresponding page tables Return back from handler and retry the instruction
Page replacement algorithms Using Any situation, when you need to find a victim from a limited space Frames, TLB, cache, Optimal page algorithm Replace the page that won t be used for the longest period of time Lowest page-fault rate Theoretical, we don t have an oracle for foretelling the future
Page replacement algorithms Clock Frames organized in a circular manner Clock hand points to the next frame to replace If the frame has A!=0, set A=0 and advance the hand If the frame has A==0, select this frame 0 A=0 A=1 5 1 A=0 A=1 A=1 2 4 A=0 A=0 3 A=1
