OC Flashcards
What is An Operating System? (Two functions)
An operation system is a software that performs 2 functions:
- Extended Machine
- Resource Manager
What is extended machine?
Extends the underlying machine architecture
(instruction set, memory org., I/O, and bus structure)
– E.g., disk driver instead of reading SATA 450-page manual
– Provides abstractions like files and processes
What is a resource manager?
- Manages resources such as CPUs, memories, timers,
disks and NICs - Allocate resources to programs
- Manages concurrent requests to resources, e.g., time
multiplexing on the CPU, space multiplexing on RAM
OS Examples UNIX
OpenBSD, FreeBSD, NetBSD, MacOS
OS Examples LINUX
- Debian (MX, Mint, Ubuntu),
- Redhat (RHEL, Fedora, CentOS)
- Arch (Manjaro)
- Gentoo (Pentoo)
- Android, …
————– not LINUX
Windows
What is the CPU? what is the loop (FDLE)?
The “brain” of the computer
In an infinite loop does:
* Fetch an instruction from memory
* Decode it
* Load its operands (if any) and
* Execute it
What does a CPU have?
-Each CPU has its instruction set: your
phones is completely different from the
one in your laptop
-CPU has a set of registers to store data
about to be used
CPU Registers
- Program Counter contains the address of the
next instruction to execute - Stack Pointer points to the top of the stack in
memory - The stack contains a frame for each function call that
has not returned yet - One frame contains input parameters, local variables,
… - Program Status Word (PSW) is set by
comparison instructions, it contains the condition
code bits
Memory hierarchy (R,C,MM,MD)
Registers, Cache, Main Memory, Magnetic Disk
What is L1 and L2 caching
L1 and L2 cache are small, high-speed memory storage areas that are built into the processor chip of a computer. The purpose of caching is to reduce the time it takes for the processor to access data from the slower main memory, which is usually DRAM (Dynamic Random Access Memory).
L1 cache (primary) is the smallest and fastest cache on the processor chip.
L2 cache (secondary) is a larger cache that is slower than L1 cache but faster than main memory.
Disks: OS as an Extended Machine
read & write: 13 parameters in 9 bytes
1) address of the disk;
2) number of surface;
3) number of cylinder;
4) number of track;
5) kind of recording mode
(continuous, interleaf, …);
6) what to do if the data is not found;
7) …
is the motor on? is the motor off?
Disk Speed
-Platters rotate at 5400, 7200, 10800 RPM
-It takes 1 msec to move the head from one
cylinder to the next
* 5 to 10 msec to move to a random one
-It takes 5 to 10 msec for a sector to be
under the arm
-Reading speeds are in the range of 50 to
160MBps
Booting-up facts
- The PC has a parentboard
- The Basic Input/Output System (BIOS) is
a program stored on the parentboard - BIOS has low-level software to use the
keyboard, screen, disks, etc. - BIOS is stored in flash RAM
BIOS - 6 Steps
- Checks how much RAM is installed and whether the
keyboard, etc., are working (USB, PS/2) - Scans for PCI and PCIe devices and installs them
- Checks in CMOS memory for a list of booting
devices and tries them
- Complementary Metal–Oxide–Semiconductor (CMOS) - Loads the first sector from the booting device
- Runs its code, which normally examines the
partition table at the end of the boot sector to
determine which partition is active - This results in running a secondary boot loader from
that partition which loads the OS
OS Booting up
- Queries the BIOS for the configuration info.
- Detect if the hardware configuration changed
since last restart - For each device, check if it has its driver
OS Types
Mainframe OS
Goliath computer! Heavily oriented toward
processing jobs at the same time
* Offer batch, transaction processing and
timesharing services
* E.g., OS/390, descendent of OS/360
Server OS
* Serve multiple users at once (Web, file printing)
* E.g., Linux server distros, Solaris, FreeBSD,
Windows Server
Multiprocessor OS
* Runs multiple CPUs into a single system
Personal OS
* E.g., Linux, Windows, FreeBSD, OpenBSD
Handheld OS
* E.g., Android
Embedded OS
* Control non-computer devices, e.g., oven
* End-user can’t install software on it
* E.g., Embedded Linux
Sensor-Node OS
* Sensors have limited power
* Run a tiny OS, often event-driven
- Respond to external event, or an internal clock
* E.g., TinyOS
Real-time OS
* Need to perform tasks within limited time
* Tasks are triggered by events
* Hard real-time OS: if an action absolutely
must occur at a certain moment or within a
certain range
-E.g., eCos
-Users can’t add their software
* Soft real-time OS: it’s acceptable, but not
desirable, to occasionally miss a deadline
What is a Process?
A process is a program in execution
A process has its address space
It also has a set of resources:
* Registers (including the program counter and stack pointer)
* List of open files
* Lists of related processes
* etc.
One main task of OS
One of the main tasks of an OS is to
decide which process runs at an instant t
* And in which processor core
-For example, you might be using Firefox
and LibreOffice at the same time on a
single-core machine
After running Firefox for a certain time, the
OS needs to pause Firefox to run LibreOffice
- In order to be able to resume Firefox once
LibreOffice’s time is over, the OS needs to
store the status of Firefox before pausing it:
* Save its address space (core image) as well as
* Other information (registers content, file pointers,
etc.)
- Process information, other than its address
space, is usually stored by the OS in a data
structure inside a process table
What is a linux time slice?
In Linux, the time slice, also known as the time quantum, is the amount of time allocated to a process for it to execute on the CPU. The time slice is determined by the kernel scheduler and can vary depending on the specific system and kernel configuration.
By default, the time slice in Linux is usually around 10 milliseconds (ms)
What happens when “gedit” is entered in shell?
this effectively asks the “shell”
process to create a new process and run “gedit” in it
- In this scenario, “gedit” is a child of “shell”. “shell” is its
parent
- A process could create many processes to help it
perform a complex operation, e.g., multiplication of
large matrices
- Linux processes form a tree
- The parent and children processes need to co- ordinate the work
* They need to use some form of inter-process
communication, e.g., by sending signals
What is a thread?
A thread is one flow (thread) of execution
within a process
A process can have one or more threads
in it
- E.g., LibreOffice
Threads share the same memory space,
making it easier for them to communicate
than different processes
Address Space
A protection mechanism is required to
prevent a program from accessing
another’s space
* Provided by the hardware, managed by OS
- Virtual memory, use the disk as an extension
of the actual physical memory
The address space as an abstraction of
the physical memory
Files
An abstraction of a collection of bytes
Organised into folders
System calls to manipulate both
Notions of
* Path
* Working directory
* File descriptor
*nix special files
- Block: randomly addressable, e.g., disks
- Character: takes input or outputs a text stream
-E.g., keyboard, modem, printers, etc. - Under /dev (e.g., /dev/lp could be a printer)
Kernel Mode
Kernel Mode
- Code has access to all CPU instructions
- Code has access to all Memory addresses
- Only accessible to most trusted parts of the OS
User Mode
- Code does not directly access hardware or
memory - Uses OS API to do so
- Crashes are recoverable
The Shell
Most common on Linux is bash.
Sometimes Desktops are called graphical
shells.
They are sorted:
application programs
system programs
hardware
System Calls
The lowest interface provided by the OS to
users
System calls to manipulate processes, files,
memory, inter-process communication, etc.
Process management: fork, waitpid, execve,
exit, …
File management: open, close, read, write,
lseek, stat, unlink, …
Folder management: mkdir, rmdir, mount,
umount
Memory: brk, malloc, free, …
Monotholic Systems
Runs entirely in kernel mode
* Including drivers
* Any crash in a procedure brings the system down
Each procedure in the system can call any other
* No layering
* No restrictions
Can have minimum structure
* A service procedure per system call
* A service utility used by one or more service procedures
E.g., Unix, Linux, OpenVMS, MS-DOS, Windows 9x
Layered Systems (OUIOMP)
The system is divided into layers
LAYER FUNCTION
5 the operator
4 user programs
3 input/output management
2 operator-process communication
1 memory and drum management
0 processor allocation and multiprogramming
Microkernel
2-10 bugs per thousand lines of code
- Linux kernel is around 5M lines of code
- Microkernel OS minimises code that runs
in kernel mode
Hybrid Kernel
Combines Monolithic and Microkernel approaches
- Runs almost all OS service in kernel space
- Used in Windows NT (including 10)
- Linus Torvalds doesn’t find enough difference
between hybrid and monolithic kernels
Time-Multiplexing
Computer resources could be shared
between processes/users using either:
* Time-multiplexing: processes take turns at the
resource
E.g., CPU core, printer (actual printing),
* Or Both (space-multiplexing)
Space-multiplexing
Computer resources could be shared
between processes/users using either:
Space-multiplexing: multiple processes can
use/share the resource at the same time
- E.g., hard-drive, RAM, printer’s buffer (if available)
* Or Both (Time-Multiplexing)
Process States - Which steps result in/from calling the
scheduling algorithm?
All! Running, Ready, Blocked
I/O Operations
I/O operations are usually much slower
than CPU instructions
What does the scheduler do?
The Scheduler chooses the next process
to run.
Process Queue
* The process queue(s) can be ordered in
different ways
- FIFO
- Priority
Fairness in processes?
- Fairness: each process gets a “fair share”
Throughput
- Throughput: number of processes that
complete their execution per time unit
Turnaround time
- Turnaround time: time from submission to
completion
Waiting time
- Waiting time: the amount of time a process
spends in the ready queue
Response time
- Response time: the amount of time from
submission to the first response
Non-preemptive
- A running process will release the CPU only
when it exits or is blocked
Non-preemptive scheduling is typically more suitable for batch systems than interactive ones as jobs are submitted in advance.
If no clock interrupts are available, non- preemptive scheduling is the only option
Preemptive scheduling
- A running process can be suspended after some
time - Requires a clock interrupt at the end of time
intervals (e.g., 50Hz, 60Hz)
Dispatcher
Switching the CPU from process A to a
new one
Context Switching steps
Steps
* Switch from user mode to kernel mode
* Save A’s state (e.g., registers)
* Select process B
* Load B’s state
* Start B
The time it takes is the Dispatch Latency
First-Come, First-Served (FCFS) Scheduling
The CPU is allocated to processes in their
order of arrival
* FIFO process queue
- Each process owns the CPU until it is
done or blocked
This is a non-preemptive algorithm
FCFS suitable for
* Batch systems
FCFS Advantages and Disadvantages
Advantages
* Simple to implement
Disadvantages
* Waiting time can be large if short requests
wait behind the long ones
* Not suitable for multiprogramming systems
Shortest-Job-First (SJF) Scheduling
For each process, determine the length of its
next CPU burst.
Run processors in their ascending burst
length order.
SJF is both a non-preemptive and preemptive algorithm.
SJF suitable for batch systems
In SJF, if A (L=20) is available at t=0 and B (L=1)
arrives at t=1
* A will run from 0 to 20, B runs from 20 to 21
SJF Advantages and Disadvantages
Advantage
* SJF minimises the average waiting time
Disadvantages
* Difficult to get a good estimate of the burst
length
- Easier if similar tasks ran in the past
* Starvation
- The longest process(es) might never get to run
Shortest Remaining Time next (SRT)
SRT takes into consideration the fact that processes
arrive at different times
* When a new process arrives, interrupt the running process
if its remaining time is longer than the new process
- With SRT
* A runs from 0 to 1
* At 1, B arrives, B’s length (1) is shorter than A’s remaining
time (19)
* Run B from 1 to 2, Run A from 2 to 21
SRT is preemptive
Typically used in interactive systems where response time is critical
Round-Robin (RR)
The most intuitive multiprogramming
algorithm
* Split the timeline into equally long segments
1. Give each process a segment
2. Once all present processes had a segment each, go
to 1.
* The length of the segment is called quantum
- Usually 10-100ms
* At the end of the timeslot, the process is pre-empted
More suited for interactive systems
RR Facts
If the quantum is too short
* The cost of context switches becomes the
main performance criteria
If the quantum is too long
* Becomes FCFS
Performance criteria
* Length of time quantum
* Number of context switches
* Length of CPU bursts
RR Advantages & Disadvantages
Advantages
* Simple to implement (circular queue)
* Very suitable for multi-programming
Disadvantages
* Challenging to find the optimal value of the
quantum
* Assumes all processes are equally important
Priority Scheduling
Each process has a priority value
* Lower integer value higher priority
- The scheduler picks processes in their
descending priority order
Two variants
* Preemptive: pause the current process if a higher
priority one arrives
* Non-preemptive: current process cannot be
interrupted by higher-priority processes
Priority Scheduling Advantages & Disadvantages
Advantages
* Can define more sophisticated policies
- E.g., SJF can be seen as priority scheduling where
the priority value is the length of CPU burst time
Disadvantages
* Starvation for low-priority processes
- Can include an ageing factor: increase the priority of
waiting for processes with time
What is a semaphore?
Semaphores are an abstract data type used for synchronization between multiple threads or processes in a concurrent system.
Semaphores can be used to protect shared resources or critical sections of code, by ensuring that only one thread or process can access them at a time. They can also be used to signal events between threads or processes
What is true about process scheduling?
The waiting time is always larger than or equal to the response time.
What is the waiting time in process scheduling?
The time spent by a process in the ready queue waiting for CPU time
What is the response time in process scheduling?
The time between a user request and the first response produced by the system.
A page fault occurs when:
A requested virtual memory page is not present in RAM.
The address space of a process refers to the space it uses in the ______?
RAM
In an OS that implements paging, what statement is accurate?
The size of a virtual memory page has to be identical to the size of a page frame.
A binary file can be defined as:
A file that uses 8 bits out of each byte
For which of the following systems is nonpreemptive scheduling more suitable?
Batch Systems
In preemptive priority scheduling, if the current running process has a priority of 3 and a process of priority 10 arrives, then what does the scheduler do?
Nothing, the current process has a higher priority
“On average, only 50% of each memory page will contain useful data.”
Is this true?
False, only the last memory page of a process will, on average, contain 50% useful data.
Examples of “Character” special files include (select two)
- a network interface
- a terminal
Which of the following statements is correct:
1- SJF is suitable for interactive operating systems
2- SRT is preemptive
3- Both preemptive and non-preemptive variants of priority scheduling are suitable for a smartphone OS
Only 2
Is SRT non-preemptive or preemptive
preemptive
Which of the following statements is true? (select two)
- A process can have multiple threads in it
- A thread can have multiple processes in it
- Threads from the same process share the process’ local
variables - Processes from the same thread share the thread’s local variables
- A process can have multiple threads in it
- Threads from the same process share the process’ local
variables
A process references memory address 2000. If it is running on an OS that uses dynamic relocation where the base address of that process is 3000 and its limit is 1000, then…
The access request will fail because 1000<2000
In dynamic relocation, the OS maps the logical address of a process to a physical address by adding the base address of the process to the logical address. Therefore, in this case, the logical address of the process is 2000, and the base address is 3000, which gives a physical address of 5000.
A stack frame is created when…
a function is called.
In the context of file management systems, “random access” refers to
No need to read bytes 1 to n-1 before reading or writing byte n
How do you calculate the number of page frames in the physical memory?
To calculate the number of page frames in physical memory, we need to divide the total physical memory size (e.g. 2GB = 2^31 bytes) by the page size (e.g. 2^12 bytes) = 2^19 pages.
we need to round down the number of pages to the nearest power of 2 that is less than or equal to the number of page frames.
The largest power of 2 that is less than or equal to 2^19 is 2^18, so the number of page frames is:
2^18 = 262,144
Is the following statement true or false?
Using the Hoare implementation, a signal will immediately transfer ownership of the monitor to the one thread woken by the signal. Under the Mesa implementation, a signal wakes at least one waiting thread, which will then compete normally to obtain ownership of the monitor in competition with any other threads that are trying to obtain ownership of that monitor.
True
what implementation of monitors transfers ownership of the monitor immediately to the thread that is woken up by a signal.
Hoare implementation of monitors transfers ownership of the monitor immediately to the thread that is woken up by a signal. This means that the woken thread gains exclusive access to the monitor and continues executing its critical section without interference from other threads.
what implementation only wakes up one waiting thread when a signal is sent.
Mesa implementation only wakes up one waiting thread when a signal is sent.
The woken thread then competes with other threads that are waiting to acquire the monitor by using a lock or semaphore mechanism.
This means that the woken thread may not immediately gain access to the monitor and may have to wait until it acquires the lock or semaphore
The bounded buffer problem is also known as the _______________ problem.
Producer-Consumer.
The producers generate data items and add them to the buffer, while the consumers remove data items from the buffer and process them. The problem is to ensure that the producers do not add items to the buffer when it is full, and the consumers do not remove items from the buffer when it is empty.
When the method release() of the Java Semaphore class is called, it will:
sometimes unblock a waiting thread that called acquire().
What are the advantages of using the Synchronized keyword (i.e. Intrinsic Monitors) over the ReentrantLock class (i.e. Extrinsic Monitors)?
- Guarantees that ownership is released at the end of methods that invoke the mutual exclusion protection
- less error-prone.
advantages that Monitors have over Semaphores:
- Clear recommended programming pattern
- Has separate and clear syntax for mutual exclusion
- Programming less prone to errors
- No constructor arguments are required.
What kind of storage do we need
Need:
* Long-term storage
* Bigger size
* Non-volatile
* Easier sharing
* With hardware abstraction
- Read block k
- Write block k
Files
- Files are persistent logical units of
information - Created and manipulated by processes
- File (Management) System is the part of
the OS dedicated to file structures, names,
uses, etc. - Process, Address Space and Files are the
most important abstractions an OS
provides
Files Systems Timeline
Big names for end-user computers include:
* 1984: FAT-16 created by IBM and Microsoft and used
in MS-DOS, then in Window 95 and 98
* 1987: Minix V1 FS created by Andrew Tanenbaum for
Minix 1.0
* 1992: ext and ext2 (1993) created by Remy Card for
Linux
* 1993: NTFS 1.0 introduced in Windows NT 3.1
* 1996: FAT-32 introduced in Windows 98
* 1999: ext3
* 2006: ext4
File Extensions
Windows
* Extensions dictate the choice of the program
to open the file, e.g., jpg, pptx, etc.
Linux
* Less binding between extensions and
programs
File Types
Files types:
* Regular: your files, ASCII or binary
* Directories (folders): contain collections of
files
* “Character” special files: model serial I/O
devices, such as terminals, printers and
networks
* “Block” special files: model disks
Under Linux, use “ls -l“
Regular and Binary Files
ASCII files
* Lines terminated by a carriage return, line feed, or
both (Windows)
Binary files start with magic numbers that identify
their formats
* 50 4B 03 04 (PK??) for zip (and derivatives, e.g.,
JAR)
* 7F 45 4C 46 (.ELF) for ELF files
* 25 50 44 46 2d (%PDF-) guess!
* 4D 5A (MZ) Windows Executables, Mark Zbikowski
* https://en.wikipedia.org/wiki/List_of_file_signatures
OS must, by default, be able to parse its own
executable formats
Files Access
Sequential: access a file byte-by-byte or
record-by-record
* Inconvenience: if you want to read the nth
byte, then you must read everything before it!
* Can rewind a file, name from magnetic tape
age!
- Before disks
Random access: access any byte/record
out of order
