OS & System Programming Flashcards
Revise This Module for Exams
What is Von Neumann Architecture also known as?
Stored-program computer
What is a Stored-program computer
A computer that stores program instructions in memory
Does Reprogramming require any change in hardware?
NO
What are the Architecture 3 main components?
- CPU
- Memory
- I/0 Interface
What is the CPU?
Heart of the Computing System
Includes:
- Control Unit (CU)
- Arithmetic Logic Unit (ALU)
What is Memory?
The computer’s memory stores program data & instructions
What I/O Interfaces?
They are used to receive or send information from the connection.
- Connected devices are called peripheral devices.
How are programs executed on Von Neumann Computers?
- Program is stored in memory
- Translated in Machine code
1) CU understands that data needs to be provided by the user.
2) Data is Read from input device & bought to the CPU
What is ALU?
Union of the circuits for performing Arithmetic & Logical Operations
What is CU role?
Responsible for step-by-step execution of instructions during a program execution.
What are Registers?
- Small storage element, located close to ALU
- Used as temporary storage during computation
- ALU can read & write from Registers very fast
What are the advantages of using Registers?
- Fast, does computation in Registers without constantly storing new values
- Improves processing speed
- Allows us to read data from memory once(Registers Store Immediate Data)
- Reading Registers tend to have zero-time overhead
Does CPU need Registers?
No, can use memory to store all the data
How long does it take to read/write data?
4ms
How long does Arithmetic take?
1ms
How is Memory Organised?
- Memory consists of small ‘cells’
- Each cell stores a small piece of data
- cells have addresses 0 to n-1
Memory Access?
- Read & Stores operations, CPU generates addresses
- Memory Management unit reads or writes from/to memory location
Decimal Representation :
- Base 10 system
- 0-9 are digits
Binary Representation:
- Base 2 System
- digits are 0&1
- digits called ‘bits’
- 8 ‘bits’ are called a ‘byte’
eg: 1110 = 14
Hexadecimal Representation:
- Base 16 System
- Digits: 0,12,3,4,5,6,7,8, A,B, C,D, E, F
e.g : A3B = 2114
What is the General Structure of a C Program?
- Execution begins at main()
- Header of file contains imports / pre-defined libraries
Examples of Control Flows?
- if statements: conditional computation
- if-else : Multiple Branching
- Switch Statements
- For / while/ do-while loops
Basic if statement implementation?
if (condition) {
statement;
}
Example of if-else
if (condition) {
statement;
}
else if (condition) {
statement
}
else{
statement
}
Example of Switch
switch (condition){
case (A):
statement
break;
case (B):
statement
break;
default:
statement
break;
}
Example of for loop
for (int i; i < MAXRANGE; i++){
statement
}
Example of Conditional While Loop
while(condition){
statement
// Change condition or Not
}
Example of Infinite While Loop
while(1){
statement
// Can break the code
}
Example of Do While Loop
do {
statement
}
while (condition){
statement
}
// RUN THE CODE ONCE AND THEN DOES IT AGAIN IN WHILE LOOP
What does ‘continue;’ do?
- skips the current iteration
- Jumps to the beginning of the next iteration
What does ‘break;’ do?
- Comes out of the loop and the loop gets terminated.
Arrays in C?
int a[4] ; // Uninsialised
int b[3] = {2,3,4}
- Fixed-size
- Sequential collection of elements of the same type
What are errors with Arrays in C?
- Compiler does not check array limit
- Memory Protection was violated and the program crashed due to segmentation fault
How are Undefined Behaviours created?
- Out-of-bound access
- Signed int overflow
- Div by Zero
- UB hit, the program can theoretically do anything
Example of Function?
return_type func_name (arguments ) {
local variables declared
statements
return data of type declared
}
Format of printf() function:
printf(“%format”,variable_name);
format:
The Type for Variable name
What does printf() do?
- Prints values into the standard ouptut
- Defined in stdio.h library
What does scanf() do?
- Receive inputs from keyboards
- Defined in stdio.h library
Format of scanf() function:
scanf(“%format”,&variableName);
- format is placeholder for Data type
- &variableName is a pointer to store input into memory
What is a String?
-String of chars is a 1D array of chars
-Terminated by ‘\0’ == Null Char
- Can be read by scanf
What is strcpy()?
- Copies a string to another memory location / a list of chars
strcpy(newCharLoc, aString);
What is strcat()?
- concatenates 2 strings
strcat(string1, string2);
What is strlen()?
- Gets the length of the string
- strlen(string1);
What is strcmp()?
-Compares 2 Strings
- strcmp(str1,str2);
– str1 == str2 = 0
– str1 /= str2 = 1/-1
What is a String Problem?
- Ensure that sufficient memory is allocated at runtime (Not done in the compiler)
- No checks at run-time, hence common source of errors
- ‘Buffer Overflow’ has been exploited to achieve execution code supplied by the attacker
Solutions to String Problems?
- The partial solution is to use the ‘safe’ function
What is the difference between C and Java?
Java:
- Memory allocated by compiler & length of string checked at runtime
- Buffer overflows are impossible
Example of Safe String Functions?
- Checks length so buffer doesn’t overflow
- strncmp:
- strncmp(str1,str2, sizeOf(str1));
- strncpy:
- strncpy(str1,str2, sizeOf(str1));
- strncat:
- strncat(str1,str2, sizeOf(str1))
Pitfalls of Strings?
The string is length 10, will need a list of size 11 for the null char
If string is length 11 but the new list of char has space 8 because it does not have enough space for remaining char.
What is a Pointer?
- A variable that contains the address of a variable
- They can be passed into a function as an argument
- Only do pass-by-ref
What is & / ‘Address of’?
p = &c
- Assigns Address of c to p
What is * “INDRIECTION / DEREFERENCING”?
c = *p
- *p hold the data c has
How to declare the pointer?
Type *p; // Declares pointer
int c = 5 , d , e[3];
int *p;
p = c; // p points to c
d = *p; // d has value 5
p = &e[0] // p points to e[0]
What is scale factor?
No. of Bytes used by the Data type
What does p++ or p+1 do is p is a pointer?
Points to the next object of the same type:
increments by:
- 4 when p is a float/int pointer
- 1 when p is a char pointer
What is the array name equal to?
It is an Address
What is Array Name synonymous with?
Location of the Initial Element
int *p = &a[0] <==> int *p = a
Can A pointer with direct Initalization be changed?
No, causes Segmentation fault & program crashes
example:
char *ptr = “Comp Sci”
Format for printing pointers?
print(“%p”p1);
Format for Returning Pointers?
type int *fun() {
Statement;
}
Define scope?
Part of program where variables can be used
What is held in Text or Code Segement?
Contains executable instructions/Programs
What does the Data Segments Contain?
- Initalized and Unintialized Global & Static Variables
What are static variables?
- Stores in data segment NOT STACK
- Preserve their values even after they are out of their scope
What are Global Variables?
- Declared outside all functions
- Can be read & Modified by all functions
- Don’t name Local Vars the same as Global Vars
What Does Stack Segment Store?
All Local or Automatic Variable , Arguments of Functions are also stored in stack.
What does Stack Segment do?
- Gives each function call, its own stack frame
- Stack grows from High to Low Address
- After function returns values, the stack frame is released and all the local variables die
What are Local Variables?
Scope is within function & allocated in the stack frame of the function
What does the Heap Segment store?
The storage of the dynamic memory allocation
What does .malloc() do?
- Allocates requested number of bytes of contiguious memory from the heap
- Returns a pointer of the first byte of allocated space
- Memory Allocation fails, will return NULL POINTER
What happens if dynamically allocated memory is not freed?
- Memory will Leak
- Memory not returned to Heap, then the program grow larger
- Large programs cause slowdowns in system performance by reducing amount of avaliable memory
What can I use to check for Memory Leaks?
Use Valgrind
What happens if you access memory after freeing it?
-Memory is not owned by the program
- Re-accessing the freed memory can cause UNDEFIEND BEHAVIOUR (UB)
DON’Ts of Freeing?
- Don’t free something that didn’t come from Malloc
- Don’t free the same thing twice
Does C have Classes?
No
What does C have instead of Classes?
Structs / Structures
{User-defined Data Types }
What does Struct do?
Groups Items of ‘Possibly’ differnet types into a single type
Format of Struct?
struct tag_name {
T1 member1;
T2 member2;
}tag_name;
// Need a separate function to initalsie the members in the struct
What is a Void Pointer?
Don’t know the type you want to point to
- You have to cast the pointer to the correct type before you will use it
Format of a Function pointer?
type (*func) (arguments);
// func is a pointer to a function
What does scanf() do?
Takes Inputs until space
What does printf() do?
Outputs values
What does getchar() do?
Gets a Char from a Standard Input
What does putchar() do?
Writes a Char from a Standard Output
What is the getline() format?
getline(input, bufferSize, where its from)
What does getline() do?
- Reads entire Line
- Must be freed at the end
How to open a file in c?
FILE *fp ; // fp is a pointer to the type FILE
fp = fopen(“filename”,”mode”);
// must close it after use
close(fp)
What happens when fp = NULL in fopen?
It was unable to open the specified file
What is the function of File Read (R)?
- File exists, opened as read-only
- sets a pointer, that points to the first char
- Else Errors
What is the function of File Read (R+)?
- Opens file for both reading & writing existing file
- Does not delete the content of the existing file
What is the function of File Write (W)?
- If the file exists it gets overwritten
- Else creates a new one
What is the function of File Write (W+)?
- Opens a reading & writing a new file
- Overwrite if file exists
What is the function of File Appending (A)?
- Opens file if it exits
- Otherwise create a new one
- Sets a pointer to the last char
- New content appears after the old one
What is the function of File Appending (A+)?
- Open file for reading/writing from the last char in file
What does getc() do?
Reads a char from a file
What does putc() do?
Write a char to a file
What does fprintf() do?
Writes into file with file pointer
what does fscanf() do?
Reads into file with file pointer
What are possible Errors for Files in C?
- Reaching beyond End-of-file
- Uses a file that has not been opened
- Opens a file with an invalid file name
- Opens a file not permitted by fopen
- Write to write-protected file
What is Random Access to File?
Can directly jump to a type byte-number in a file without reading previous data using fseek()
What does fseek(fp,-m,1)
Moves back by m bytes from the current byte
What does fseek(fp,m,0)
Moves to the m+1 th byte in the file
What are Command Line Arguments?
Arguments inputted on cmd line that the program has requested or been modified to recieve
What is argc?
- An int
- Stores the number of arguments on cmd line passed by user
What is argv?
- Argument Vector
- Array of all the arguments (Excluding white space)
- argv[0] – Name of program
– argv[1] – 1st Argument
What is a Makefile?
- Compiles Multiple C files, along with additional steps to check for errors
- Can also make warnings appear as errors as C has to be very accurate
- Links all Files for full executable code.
- Don’t need to compile code individually can be done all at once
MakeFile Format?
<target>: <file0> <file1> ... <command></command>
</file1></file0></target>
Typical File Types in MakeFile
- .c (for C)
- .h
- .o (Compiled Machine code)
What does preprocessor do in C?
Runs before compilation & does text situations
- Like pasting file locations of the libraries
What is a Macro?
USEFUL TO AVOID CALL OVERHEAD FOR SMALL FUNCTIONS BUT USE WITH CARE
- If the function is going to be used multiple time
Format of Macro?
define MACRO(x) ((x) = (x) + 5 )
Format of Constant
define CONSTANTS 3.14159
What are Sockets?
- Connects client to server
Describe the socket’s function?
- Behaves similar to files once connected (Read/Write)
- Server binds to a port listens on the socket and accepts each client
- Client connects IP/Port & read() & Write on socket
- Socket must be closed after use
Describe the multi-core system?
- Each core has its own L1 cache
- Some processors, each core has its own l2 cache
- All cores share l3 cache
- All cores share DDR RAM (Main Memory)
What is the coherence of data?
- Quality of being logical & consistent, during program execution, data remains coherent
- On MCS, data variable may reside in multiple caches & updated locally, but its local core
-ERRORS cause coherence problems & protocols are needed
What is a concurrent server?
- Serves all clients at once, don’t need to wait for others to finish
- All clients get served, even if one causes blocking, others don’t have to wait
- All parallel tasks are concurrent, but concurrent tasks aren’t parallel
What’s a Thread?
- Thread of executions is the smallest sequence of programmed instructions
- Managed independently by scheduler (part of OS)
- Each Thread has its own copy of stack-related info
Purpose of PThread?
- Must link to the PThread library using compilation flag -lpthread file.c
- Creates thread using pthread_create(), 0 if successful else non-zero
What does PThread Contain?
- Id of Thread
- Constants that control thread attributes
- Function(s) to be executed
- Argument of Function
How does Concurrent programming handle multiple arguments?
- Packs arguments into a struct & creates a wrapper
- Takes the compound argument & unpacks it
- Passes unpacked arguments to a function
Problem with Threads?
- Can’t rely on all threads being executed
- Add sleep function would make sure all threads are executed (BAD FIX)
What are shared between concurrent threads?
- Global data objects
- Heap objects
- Files
What happens if the data objects are not shared?
Lack of sync leads to chaos and wrong calculations
What are 3 ways to sync Threads?
- Joins
- Mutual Exclusion
- Condition Variables
What is JOINS?
- Blocking function
- Main only terminates when the 2 threads have joined
- Both threads have been completed, But the order can change
- Forgetting to join leaf to incorrect results
What is the RACE CONDITION of JOINS?
- RACE CONDITION: 2+ Thread perform operations on the same data, but the results are dependent on the order in which the operations are Performed
What is Mutal Exclusion?
- Mutex
- Solves the race conditions of JOINS
- Locks global resources until they get unlocked (Other locked threads will wait till the previous one is unlocked )
How does Mutal Exclusion Resolve the JOINS Race condition?
Threads get exclusive access to shared resources in turn
What are the Pitfalls of Mutual Exclusion?
2 Mutex Threads and lock both, will cause a deadlock and the code will hang forever
What is trylock()?
- Tries to lock mutex object
- Return 0, if it can
- otherwise non-zero & will not wait to be freed
What are Condition Variables?
- Used to sync threads based on the value of data
- Waits till data reaches a particular value OR certain event occurred
-Receiving signal, the waiting thread awakens (BASED ON CONDITION) - A thread goes to a waiting state based on ‘condition to happen’ by pthread_cond_wait(&condition_cond, &condition_mutex)
What is the purpose of an Operating System?
A program that acts as an intermediary between a user of the computer and the computer hardware
OR
One program that is always running on the computer, with all else being systems programs & application programs
What are the main functions of OS?
- Resource Allocator
- Control System
What does the Resource Allocator do?
Manages all hardware resources & decides between conflicting requests for efficient & fair resources
What does the Control System do?
Controls execution of programs to prevent errors & improper use of the computer
What are the basic building blocks of OS?
- Small bootstrap program is loaded at power-up or reboot (Stored in ROM or EPROM or firmware (BIOS))
What does ROM stand for?
Read-Only Memory
What does EPROM stand for?
Erasable Programmable ROM
What are examples of firmware?
BIOS
(Basic, Input, Output, System)
OS Sharing devices?
- Device controllers are hardware within laptops/Comps
- Bus connects CPUs, device controllers & Memory
- OS kernel runs within the CPU & manages the device through the device controllers
What are Device controllers?
- I/O devices and CPU execute concurrently
- Each device controller is in charge of a particular device type
- Each has a local buffer
- CPU moves data from buffers to main memory
- I/O from device to local controller
- Informs CPU that it has finished its operations via INTERRUPT
What is an Interrupt Vector?
Reserved part of memory, tracking which interrupts need to be handled
What is an Interrupt?
- For each interrupt, the os executes the appropriate ISR to handle it
- Address of Interrupt is saved so processing can carry on after completion of Interrupt
How can software programs generate Interrupts?
- Through System cells (Like when an error occurs)
- Software-generated interrupt is called a TRAP
What is Main Memory?
- Large storage that the CPU can access directly
- Volatile (Memory not saved when laptop turned off)
- RAM
What is Secondary Storage?
- Large non-volatile storage
- (Flash memory, Magnetic Disk & CDs)
What are the services of OS?
- UI
- Processes
What is UI?
- Interact indirectly through a collection of system programs that make up the OS interface
- GUI: icons & windows
- CMD interface running processes and scripts
What are Processes?
- Interact with the OS by making system calls into the OS kernel
- For stability, such calls are to be directed to the Kernel Function
What are EGs:
- Program Execution:
- System must be able to load a program into memory and run that program
- End execution, either normally or abnormally (indicating error)
- I/O Operations:
- A running program may require I/O, which may involve file or an I/O device
- File-system manipulation:
- Programs need to read and write files & directories
- Create, Delete & Search them, list file info & permission management
- Interprocess Communication (IPC):
- Allowing the process to share data through message passing or shared memory
What are services for OS?
- Error Handling:
- What if our process attempts a div 0 or tries to access a protected memory region / if a device fails?
- Resource Allocation:
- Processes may be completed for resources such as the CPU, memory, and I/O devices
- Accounting:
- How much disk space is this or that user using? how much network bandwidth are we using?
- Protection & Security:
- The owners of info stored in a multi-user networked computer system may want to control the use of that info. &concurrent processes should not interfere with each other
What are OS Architecture?
- UNIX - One big Kernel
- Consists of everything below the system call interface & above the physical hardware
- Provides the file system, CPU scheduling, memory management,& other FUNCs; Large No. functions for 1 level
- Limited to hardware support compiled into the kernel
What are System Calls?
- Programming interface to the service provided by the OS
(Open file, read file, etc.) - Typically Written in C/C++
- Accessed by programs using High-level APIs
- APIs allow application code to access the kernel without requiring required root privileges
(Controls from user mode to kernel mode)
What are common APIs in System Calls?
- Win32 for windows
- POSIX API for UNIX-based system
System Calls for Open File Operation?
- Register the file with the os
- Called before any operations on the file
- Returns an Integer called the file descriptor
(Index into the list of open files maintained by os)
System Calls for Read File operation?
- Read data from the file
- Returns No. of bytes read of 0 for EOF
System Calls for Write File operation?
- Write data to a file. Returns No. of bytes written
System Calls for Close File Operation?
- De-register the file with the OS
- No further operations on the file are possible
What does the System Calls return when an error occurs?
- These system calls return a -ve NO. on error
can use terror-function to display error
What is Trapping Kernel?
- User process calls the system call wrapper function from the standard c library.
- Wrapper Function issues low-level trap instructions to switch from user mode to kernel mode
- Some function calls may take arguments, which may be passed as pointers to struct via registers
How to fix the issue that no call can be made directly from user space to a specific function in the Kernel space?
- Issue the trap instructions, an index is stored in a well-known location
- Once switched into kernel space, the index is used to look up the desired kernel service function, which is then called
Modular Kernel Implementation?
- Most modern OS implement Kernel modules
- Object-oriented approach
- Each core component is separate
- Each talk to the others over known interfaces
- Each is loadable as needed within the kernel. Download a new device driver for your OS & load it at run-time or perhaps when the device is plugged in,
What is a Modular Kernel?
- Similar to layered architecture but with flexibility
(All drivers or kernel functionally do not need to be compiled into kernel binary) - Separation of the modules is still logical since all kernel code runs in the same privileged address space
(Writes a module that wipes out the os with no problem )
(Leads to the benefits of microkernel )
What’s in the kernel core?
- Device & Bus Drivers
- Scheduling Classes
- File Systems
- Loadable System Class
- Executable Formats
- Streams Module
- Miscellaneous Modules
What is a Microkernel?
- Moves as much as possible from the kernel into less privileged ‘user space’
- Comms take place between user modules using message-passing
- Hard disk device can run all logic in user space
- When it needs to talk directly to hardware using privileged I/O port instructions, must pass a message requesting such to the kernel
Give 3 Benefits of Microkernel?
- Easier to develop microkernel extensions
- Easier to port OS to new architecture
- More reliable (Driver fails, it gets reloaded)
- More secure, the kernel is less complete & less likely to have security holes.
- System can recover from a failed device driver.
(Cause “blue screen of death” in windows )
( “Kernel Panic” in Linux)
Give a Drawback of Microkernel?
- Overhead of user space or kernel space communication
- Linux OS & L3/L4 are examples of microkernel architecture
What is a Virtual Machine?
- VM allows to run one OS (GUEST) on another OS (HOST)
- VM provides an interface identical to the underlying bare hardware
- OS host creates the illusion that a process has its processor & VM
- Each guest is provided with a virtual copy of the underlying computer. So it is possible to install
VM History?
- Appeared in IBM mainframes in 1972
- Multiple execution environments can share the same hardware
- Protected from one another, so no interference:
- some sharing of files can be permitted, controlled
- Comms with one another & with other physical systems via networking
Pros of VM?
- Used for development, and testing, due to easy reversal accidentally destroyed OS back to previous state
What is the Open Virtualisation Format?
The standard format of VM, which allows it to run within many different VM Platform
Differences in Emulation & OVF?
- Emulation guest instructions run within a process that pretends to be the CPU
- OVF, the goal is to run guest instructions directly on the host CPU
(This means the guest OS must run on the CPU architecture of the host )
What is para-virtualisation?
- Presents guests with system similar but not identical hardware
- Guest OS must be modified to run on para-virtualisation ‘hardware’.
How is para-virtualisation hardware modified?
- Kernel is recompiled with all code that uses privileged instructions replaced by hooks into the virtualization layer
- OS has been successfully modified, para-virtualisation is very efficient & is often used for providing low-cost rented Internet services
What is VMWare Architecture?
- Implements full virtualisation, such that guest OS don’t require modification to run upon the VM
- VM & must convince the guest that it is running privileged CPU when it’s not
(Scenario - a process of the guest OS raises div 0)
What are device drivers?
Software that allows other programs to interface with external devices through the device controllers.
(Run in kernel mode, device management software may well run in user mode typically these wouldn’t be called ‘drivers’)
What does OPEN do in System Calls?
Make device available
What does READ do in System Calls?
Read from device
What does WRITE do in System Calls?
Write to device
What does IOCTL do in System Calls?
Perform operations on devices
What does CLOSE do in System Calls?
Make devices unavailable
What is Kernel Side?
Each file may have a function associated with it which is called when corresponding system calls are made.
linux/fs.h lists all available operations on files
How are Devices Categorised?
Physical Dependencies:
Between devices (Connected to USB-hub)
Buses:
Channels between processors & 1 or more devices (PHYSICAL OR LOGICAL)
Classes:
Set of devices of the same type (e.g keyboards or mice)
How are Interrupts handled in Device Drivers?
- Device sends interrupt
- CPU selects the appropriate interrupt handler
- Interrupt handler processes
What 2 important tasks does the Interrupt handler process?
- Data to be transferred to/from device
- Waking up processes which waits for data transfer to be finished
- Interrupt handler clears interrupt but of the device necessary or next interrupt to arrive
How important is the Interrupt Processing Time?
- Must be fast
- Data transfer is fast, the rest of the processing is slow
What are the 2 Halves of the interrupt?
Top Half:
- Directly by the interrupt handler
- Only transfers data between the device & appropriate kernel buffer & scheduler software interrupts to start the bottom half
Bottom Half:
- Runs in Interrupt context & does the rest of the processing
(Working through protocol stack & waking up process)
What is Memory Management?
Management of a limited resource
- Sophisticated algorithms needed, together with support from HW & the compiler & Loader
- Want to be able to store the memory of several programs in main memory at the same time.
Key Point for Memory Management?
The program’s view memory is a set of memory cells at address 0x0 & finishing at some val (LOGICAL ADDRESS)
Hardware for Memory Management?
Set of memory cells starting at address 0x0 & finishing at some val (PHYSICAL ADDRESS)
What is a suitable mapping from logical to physical addresses?
- Compile Time:
Absolute references are generated - Load Time:
This can be done by a Special Program - Execution Time:
Needs Hardware support - Dynamic Linking:
Use only one copy of the system library
OS has to help: the same code accessible to more than one process
What is External Fragmentation?
Small holes appear in memory overtime
What is Internal Fragmentation?
Programs are only a little smaller than the hole, so the leftover is too small to qualify as a hole
What is Swapping?
- Memory Management Technique
- Too high memory demand: Memory of some processes is transferred to disk
- Combined with scheduling, low-priority processes are swapped out
Problems of Swapping?
- Big Transfer Time
- What to do with pending I/O
- Not principal memory management technique
Strategies for Choosing Holes?
- First-fit
- Rotating First Fit
- Best Fit
- Buddy System
What is First-fit?
Start from the beginning & use the first available hole
What is Rotating First Fit?
Start after the last assigned part of memory
What is the Best Fit?
Find the smallest usable space
What is the Buddy System?
- Holes in size of power of 2
- Smallest possible hole used
- Split the Hole in 2 if necessary
- Recombine 2 Adjacent Holes of the same size
What is Paging?
- Assigns Memory of a fixed size (PAGE)
- Motivated by ease of allocation
- Avoid external fragmentation
- Translation of logical address to physical address done via page table
- Motivated by ease of allocation
What hardware support is Mandatory for Paging?
- Small Page Tables
- Fast Registers
- Large Page Tables
- Stored in Main Memory
- Caches most recent entry
(Instance of general principle )
How is memory protected in paging?
Info stored in a page table
What is Segmentation?
Divides memory according to its usage by programs
Data: mutable, different for each instance
Program code: immutable, same for each
instance
Symbol Table: immutable, same for each
instance, only necessary for
debugging
Requires Hardware support
Can use some principles such as paging, however, must do an overflow check
- Motivated by the use of memory
What is Virtual Memory?
Complete separation of logical & physical memory
Works due to programs using a small fraction of this memory
What is the problem with Virtual Memory?
Enormous difference between memory access speed & disk access speed
What is Demand Paging?
- Virtual Memory implemented as demand paging
- Memory divided into same-size pages, with valid/invalid bit
What is a Swapper?
‘Swap out’ process (move whole memory to disk & block process)
What is a Pager?
‘Which pages to move’ when the move is needed
Why is it crucial to have a minimal rata of page faults?
10% slowdown due to page fault, then fault rate:
- HHD:
p < 10^(-6)
- SSD
p < 10^(-4)
What are the 2 Strategies made in Demand paging?
Pager & Swapper
What are Page replacement Algorithms?
- First In First Out
- Optimal Algorithm
- Least-Recently Used
What is First In First Out?
- Easy to implement
- Doesn’t take locality into account
- An increase in the number of frames can cause an increase in the number of page faults
What is an Optimal Algorithm?
- Select a page which will be reused at the latest time
What is the Least-Recently Used Page Replacement method?
- Past as a guide for future
- Replace the page which has been unused for the longest time
What is a CON for Least-Recently used?
Requires a lot of hardware support
What are the possibilities for page replacement algorithms?
- Stack in Microcode
- Approx. using reference bit: Hardware sets the bit to 1 when bit is referenced
What is the second Chance algorithm?
FIFO
What replacement algorithm should you use?
FIFO, but it skips reference bit 1 & resets them to 0
What is Thashing?
- Page fault rate is high, when the process locks frames it constantly uses
Thus:- CPU throughput decreases dramatically
- Disastrous effect on performance
What are the 2 solutions for Thrashing?
- Working-set model (BASED ON LOCALITY)
- Page Fault Frequency (Direct approach )
What is the Working set Model?
- Define working set as a set of pages used in the most recent page reference
- Only working set in Main Memory is Kept (Achieves High CPU- utilisation & prevents thrashing )
For the working set what is the Difficulty?
Determining the Working set
What is the Approximation for the working set?
Use reference bits; copy each 10,000 references & define the working set as pages with reference bit set
What is the Page-Fault Frequency?
- Give process additional frames if the page frequency rate high
- Remove the frame from the process if page fault rate is low
What is Memory Management in Linux Kernel?
- 4 Segments in Total:
- Kernel Code
- Kernel Data
- User Code
- User Data
Uses paging, but has an elaborate permission system for pages
Separate Logical address for kernel & user memory
What is 32-bit architectures (4GB Virt Mem)?
- Kernel space address is the upper 1GB of address space
- User space address is the lower 3GB
- Kernel Memory is always mapped, but protected against access by user process
What is the 64-bit architecture?
- Kernel space address and user space address are split in half
What are Page Caches?
- Repeated cycles of allocation & freeing of the same kind of object can have a pool of pages used as a cache for these objects
- Cache maintained by application
- kmalloc uses slab caches from commonly used size
Give a Summary of Device Drivers:
Implement open, read, write & close with common structure
Give a Summary of Memory Management:
- Management of limited resources -> serious effort required
- Need to isolate memory for each process
- Memory demand too high, need to swap out part of the memory of the process (PAGING / SEGMENTATION achieves this )
- Requires Hardware support
What is Kernel Programming?
- Has access to all resources
- Programs not subject to any constraints from memory access or hardware access
What is the result of Faulty Programs?
System Crash
What are System Calls?
The kernel provides its function only via special functions
This is provided by Standard C library
Does there have to be a strict separation of kernel data & data for user programs?
YES
(Explicit copying between user program & kernel)
What functions are used for strict separation?
- copy_to_user()
- copy_from_user()
How do Interrupts work in Kernel?
- Asks Hardware to perform a certain action
- HW sends an interrupt to the kernel which performs desired action interrupts must be processed quickly
(Any code called from interrupt must not sleep)
What are the 2 Main Modes for kernel code?
- Process Context
- Interrupt Context
What is Process Context?
Kernel code works for user programs by executing a system call
What is Interrupt Context?
Kernel code handling an Interrupt (by a device)
- Have access to user data only in process context
- Any code running in process context may be pre-empted at any time by an interrupt
- Interrupt has priority levels
(Higher ones pre-empt low priority)
What are Kernel Modules?
- Add code to the running kernel
- Useful for providing device drivers which are required only if hardware is present
What is modprobe?
Inserts module into running kernel
What is rmmod?
removes modules from running kernel
what is lsmod?
List Currently running module
Why is concurrency handling important?
- Manipulation of data structures which are shared between
- code running in process mode & code running in interrupt mode
- code running in interrupt mode
- Happens only with critical regions
- Multi-processor system manipulation of data structure shared between code running in process context must happen only within a critical section
What are 2 ways to achieve Mutual exclusion?
- Semaphores/Mutex
- Spinlocks
What is Semaphores?
- Entering the critical section fails, the current process is put to sleep until the critical region is available
- Only usable if all critical regions are in process context
What are the Semaphore Functions?
- DEFINE_MUTEX()
- mutex_lock()
- mutex_unlock()
What is Spinlocks?
- Processor tries repeatedly to enter the critical section
- Usable anywhere
What are the disadvantages of Spinlocks?
Have busy waiting
What are the Spinlock Functions?
- spin_lock_init()
- spin_lock()
- spin_unlock()
What are the 2 Kinds of Semaphores?
- Normal Semaphores
- Read-Write Semaphores
What is a Read-Write Semaphore?
It is useful if some critical region only reads shared data structs & this happens often
Explain how the Programming data transfers between userspace & Kernel?
- Linux maintains a directory called proc as an interface between user space & kernel
- Files in this directory do not exist on the disk
- Read & Write operations on these files translate into kernel operations, together with data transferred between user space & kernel
- Useful mechanism for info exchange between kernel & user space
What are the major parts of the Kernel?
DEVICE DRIVERS :
- subdirectory drivers, sorted according to category
FILE SYSTEM:
- In subdirectory fs
SCHEDULING & PROCESS MANAGEMENT:
- In subdirectory Kernel
MEMORY MANAGEMENT:
- In subdirectory mn
NETWORKING CODE:
- In subdirectory net
ARCHITECTURE SPECIFIC LOW-LEVEL CODE:
- In subdirectory arch
INCLUDE-FILE:
- In the subdirectory include
What is the variety of programs the OS executes?
BATCH SYSTEM:
- jobs
TIME-SHARED SYSTEMS:
- User programs/tasks
PROCESS:
- A program in execution
- Execution must progress in a sequential fashion
What do processes include?
- Program
- Stack
- Program Counter
- Data Section
What are the 5 Process States?
- NEW (Process is being created)
- READY (The process is waiting to be assigned to a processor)
- WAITING (Process is Waiting for some event to occur)
- RUNNING (Instruction is being executed)
- TERMINATED (Process has finished execution)
What states go to NEW state?
NONE
What states go to READY State & HOW?
- NEW (admitted)
- WAITING (I/O or Event Completion)
- RUNNING (Pre-empted)
What states go to RUNNING State & HOW?
- READY (Scheduler Dispatch)
What states go to WAITING State & HOW?
- RUNNING (I/O or Event Wait)
What states go to TERMINATED State & HOW?
- RUNNING (Exit)
What is a Process Control Block?
- Info associated with each process, which is stored as various fields within kernel data:
- PROCESS STATE
- PROGRAM COUNTER
- CPU REGISTERS
- CPU SCHEDULING INFO
- MEMORY MANAGEMENT INFO
- ACCOUNTING INFO
- I/O STATUS INFO
How are Process Created?
- Parent process creates the children process, which creates other methods, making a tree of processes
What is PID and what does it stand for?
PID (Process Identifier)
- Identifies & Manages Processes
How does resource sharing between parent and child process?
- Parent & Child share all resources
- Child share subset of parent’s resources
- Share no resources
How are parent & child executed?
- Parent & Child execute concurrently
- Parent wairs until terminates
Up to the compiler whether it executes the parent/child process
Give an example of how the Processes work.
- Fork system call creates a new process
- exec system call used after a fork to replace the process’ memory space with a new program
Explain process termination?
Executes last statement & asks OS to delete it (EXIT)
- Output data from child to parent
- Resources are deallocated by OS
A parent may terminate the execution of the Child Process (ABORT)
- Child exceeded allocating resources
- Task assigned to a child no longer required
- Parent Exiting:
Some OS doesn’t allow the child to continue if its parent terminates - all children terminated (CASCADING TERMINATION)
Explain Concurrency through Context Switching?
- CPU switches to another process, the system must save the state of the old process & load the saved state for a new process via context switching
- Context of process represented in PCB
- Context - Switch is overhead; the system does no useful work while switching
- Time-dependent on hardware support
What is the problem with scheduling?
- Processes Competing for resources
- Import OS functions: define a schedule to manage access of process to these resources
- Done by having queues of processes waiting for specific resources & selecting a process in a queue.
Give the 3 Scheduling Queues.
- Job Queue
- Ready Queue
- Device Queue
What is the Job Queue?
- Set of all processes in the system
What is the Ready Queue?
- Set off all processes residing in Main Memory, ready & waiting to execute
What is the Device Queue?
- Set of processes waiting for l/O devices
Can Processes migrate among various queues?
YES
What are the Prerequisites for successful scheduling?
CPU-I/O-Burst Cycle:
- I/O occurs after a fixed amount of time greater than or equal to 90%
- Appropriate time for rescheduling
Preemptive Scheduling:
- Process can be forced to relinquish the processor
What are the Scheduling Criteria?
Why do we have the Scheduling Criteria
