OS & SYSTEM PROGRAMMING Flashcards
1
Q
What is Von Neumann Architecture also known as?
A
Stored-program computer
2
Q
What is a Stored-program computer?
A
A computer that stores program instructions in memory
3
Q
Does Reprogramming require any change in hardware?
A
NO
4
Q
What are the Architecture 3 main components?
A
- CPU
- Memory
- I/O Interface
5
Q
What is the CPU?
A
Heart of the Computing System
Includes:
- Control Unit (CU)
- Arithmetic Logic Unit (ALU)
6
Q
What is Memory?
A
The computer’s memory stores program data & instructions
7
Q
What are I/O Interfaces?
A
They are used to receive or send information from the connection.
- Connected devices are called peripheral devices.
8
Q
How are programs executed on Von Neumann Computers?
A
- 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
9
Q
What is ALU?
A
Union of the circuits for performing Arithmetic & Logical Operations
10
Q
What is CU role?
A
Responsible for step-by-step execution of instructions during a program execution.
11
Q
What are Registers?
A
- Small storage element, located close to ALU
- Used as temporary storage during computation
- ALU can read & write from Registers very fast
12
Q
What are the advantages of using Registers?
A
- 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
13
Q
Does CPU need Registers?
A
No, can use memory to store all the data
14
Q
How long does it take to read/write data?
A
4ms
15
Q
How long does Arithmetic take?
A
1ms
16
Q
How is Memory Organised?
A
- Memory consists of small ‘cells’
- Each cell stores a small piece of data
- Cells have addresses 0 to n-1
17
Q
What is Memory Access?
A
- Read & Stores operations, CPU generates addresses
- Memory Management unit reads or writes from/to memory location
18
Q
What is Decimal Representation?
A
- Base 10 system
- 0-9 are digits
19
Q
What is Binary Representation?
A
- Base 2 System
- Digits are 0&1
- Digits called ‘bits’
- 8 ‘bits’ are called a ‘byte’
eg: 1110 = 14
20
Q
What is Hexadecimal Representation?
A
- Base 16 System
- Digits: 0,1,2,3,4,5,6,7,8, A,B, C,D, E, F
e.g : A3B = 2114
21
Q
What is the General Structure of a C Program?
A
- Execution begins at main()
- Header of file contains imports / pre-defined libraries
22
Q
Examples of Control Flows?
A
- if statements: conditional computation
- if-else : Multiple Branching
- Switch Statements
- For / while/ do-while loops
23
Q
Basic if statement implementation?
A
if (condition) {
statement;
}
24
Q
Example of if-else
A
if (condition) {
statement;
}
else if (condition) {
statement
}
else{
statement
}
25
Example of Switch
```
switch (condition){
case (A):
statement
break;
case (B):
statement
break;
default:
statement
break;
}
```
26
Example of For loop
```
for (int i; i < MAXRANGE; i++){
statement
}
```
27
Example of Conditional While Loop
```
while(condition){
statement
// Change condition or Not
}
```
28
Example of Infinite While Loop
```
while(1){
statement
// Can break the code
}
```
29
Example of Do While Loop
```
do {
statement
}
while (condition){
statement
}
// RUN THE CODE ONCE AND THEN DOES IT AGAIN IN WHILE LOOP
```
30
What does 'continue;' do?
- skips the current iteration
- Jumps to the beginning of the next iteration
31
What does 'break;' do?
- Comes out of the loop and the loop gets terminated.
32
Arrays in C?
int a[4] ; // Uninsialised
int b[3] = {2,3,4}
- Fixed-size
- Sequential collection of elements of the same type
33
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
34
How are Undefined Behaviours created?
- Out-of-bound access
- Signed int overflow
- Div by Zero
## Footnote
- UB hit, the program can theoretically do anything
35
Example of Function?
```
return_type func_name (arguments ) {
local variables declared
statements
return data of type declared
}
```
36
Format of printf() function:
printf("%format",variable_name);
## Footnote
format:
The Type for Variable name
37
What does printf() do?
- Prints values into the standard output
- Defined in stdio.h library
38
What does scanf() do?
- Receive inputs from keyboards
- Defined in stdio.h library
39
Format of scanf() function:
scanf("%format",&variableName);
## Footnote
- format is placeholder for Data type
- &variableName is a pointer to store input into memory
40
What is a String?
- String of chars is a 1D array of chars
- Terminated by '\0' == Null Char
- Can be read by scanf
41
What is strcpy()?
- Copies a string to another memory location / a list of chars
## Footnote
strcpy(newCharLoc, aString);
42
What is strcat()?
- concatenates 2 strings
## Footnote
strcat(string1, string2);
43
What is strlen()?
- Gets the length of the string
## Footnote
- strlen(string1);
44
What is strcmp()?
- Compares 2 Strings
## Footnote
- strcmp(str1,str2);
-- str1 == str2 = 0
-- str1 /= str2 = 1/-1
45
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
46
Solutions to String Problems?
- The partial solution is to use the 'safe' function
47
What is the difference between C and Java?
Java:
- Memory allocated by compiler & length of string checked at runtime
- Buffer overflows are impossible
48
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))
49
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.
50
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
51
What is & / 'Address of'?
p = &c
- Assigns Address of c to p
52
What is * "INDIRECTION / DEREFERENCING"?
c = *p
- *p hold the data c has
53
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]
54
What is scale factor?
Hint: data types
No. of Bytes used by the Data type
55
What does p++ or p+1 do if 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
56
What is the array name equal to?
It is an Address
57
What is Array Name synonymous with?
Location of the Initial Element
## Footnote
int *p = &a[0] <==> int *p = a
58
Can A pointer with direct Initialization be changed?
No, causes Segmentation fault & program crashes
## Footnote
example:
char *ptr = "Comp Sci"
59
Format for printing pointers?
print("%p",p1);
60
Format for Returning Pointers?
```
type int *fun() {
Statement;
}
```
61
Define scope?
Part of program where variables can be used
62
What is held in Text or Code Segment?
Contains executable instructions/Programs
63
What does the Data Segments Contain?
- Initialized and Uninitialized Global & Static Variables
64
What are static variables?
- Stores in data segment NOT STACK
- Preserve their values even after they are out of their scope
65
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
66
What Does Stack Segment Store?
All Local or Automatic Variable , Arguments of Functions are also stored in stack.
67
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
68
What are Local Variables?
Scope is within function & allocated in the stack frame of the function
69
What does the Heap Segment store?
The storage of the dynamic memory allocation
70
What does .malloc() do?
- Allocates requested number of bytes of contiguous memory from the heap
- Returns a pointer of the first byte of allocated space
- Memory Allocation fails, will return NULL POINTER
71
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 available memory
72
What can I use to check for Memory Leaks?
Use Valgrind
73
What happens if you access memory after freeing it?
- Memory is not owned by the program
- Re-accessing the freed memory can cause UNDEFINED BEHAVIOUR (UB)
74
DON'Ts of Freeing?
- Don't free something that didn't come from Malloc
- Don't free the same thing twice
75
Does C have Classes?
No
76
What does C have instead of Classes?
Structs / Structures
## Footnote
{User-defined Data Types }
77
What does Struct do?
Groups Items of 'Possibly' different types into a single type
78
Format of Struct?
```
struct tag_name {
T1 member1;
T2 member2;
}tag_name;
```
## Footnote
// Need a separate function to initialize the members in the struct
79
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
80
Format of a Function pointer?
type (*func) (arguments);
## Footnote
// func is a pointer to a function
81
What does scanf() do?
Takes Inputs until space
82
What does printf() do?
Outputs values
83
What does getchar() do?
Gets a Char from a Standard Input
84
What does putchar() do?
Writes a Char from a Standard Output
85
What is the getline() format?
getline(input, bufferSize, where its from)
86
What does getline() do?
- Reads entire Line
- Must be freed at the end
87
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)
```
88
What happens when fp = NULL in fopen?
It was unable to open the specified file
89
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
90
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
91
What is the function of File Write (W)?
- If the file exists it gets overwritten
- Else creates a new one
92
What is the function of File Write (W+)?
- Opens a reading & writing a new file
- Overwrite if file exists
93
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
94
What is the function of File Appending (A+)?
- Open file for reading/writing from the last char in file
95
What does getc() do?
Reads a char from a file
96
What does putc() do?
Write a char to a file
97
What does fprintf() do?
Writes into file with file pointer
98
What does fscanf() do?
Reads into file with file pointer
99
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
100
What is Random Access to File?
Can directly jump to a type byte-number in a file without reading previous data using fseek()
101
What does fseek(fp,-m,1) do?
Moves back by m bytes from the current byte
102
What does fseek(fp,m,0) do?
Moves to the m+1 th byte in the file
103
What are Command Line Arguments?
Arguments inputted on cmd line that the program has requested or been modified to receive
104
What is argc?
- An int
- Stores the number of arguments on cmd line passed by user
105
What is argv?
- Argument Vector
- Array of all the arguments (Excluding white space)
- argv[0] -- Name of program
-- argv[1] -- 1st Argument
106
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
107
MakeFile Format?
108
Typical File Types in MakeFile?
- .c (for C)
- .h
- .o (Compiled Machine code)
109
What does preprocessor do in C?
Runs before compilation & does text situations
## Footnote
- Like pasting file locations of the libraries
110
What is a Macro?
USEFUL TO AVOID CALL OVERHEAD FOR SMALL FUNCTIONS BUT USE WITH CARE
## Footnote
- If the function is going to be used multiple times
111
Format of Macro?
define MACRO(x) ((x) = (x) + 5 )
112
Format of Constant?
#define CONSTANTS 3.14159
113
What are Sockets?
- Connects client to server
114
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
115
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)
116
What is the coherence of data?
- Quality of being logical & consistent, during program execution, data remains coherent
- On MCS
117
# Sockets
What happens 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.
118
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).
119
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.
## Footnote
ERRORS cause coherence problems & protocols are needed.
120
What is a concurrent server?
- Serves all clients at once; they 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.
121
What's a Thread?
- Thread of execution is the smallest sequence of programmed instructions.
- Managed independently by scheduler (part of OS).
## Footnote
Each Thread has its own copy of stack-related info.
122
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.
123
What does PThread contain?
- Id of Thread.
- Constants that control thread attributes.
- Function(s) to be executed.
- Argument of Function.
124
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.
125
Problem with Threads?
- Can't rely on all threads being executed.
- Adding sleep function would make sure all threads are executed (BAD FIX).
126
What are shared between concurrent threads?
- Global data objects.
- Heap objects.
- Files.
127
What happens if the data objects are not shared?
Lack of sync leads to chaos and wrong calculations.
128
What are 3 ways to sync Threads?
- Joins.
- Mutual Exclusion.
- Condition Variables.
129
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 leads to incorrect results.
130
What is the RACE CONDITION of JOINS?
- RACE CONDITION: 2+ Threads perform operations on the same data, but the results are dependent on the order in which the operations are performed.
131
What is Mutual 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).
132
How does Mutual Exclusion resolve the JOINS race condition?
Threads get exclusive access to shared resources in turn.
133
What are the pitfalls of Mutual Exclusion?
2 Mutex Threads locking both will cause a deadlock and the code will hang forever.
134
What is trylock()?
- Tries to lock mutex object.
- Returns 0 if it can.
- Otherwise non-zero & will not wait to be freed.
135
What are Condition Variables?
- Used to sync threads based on the value of data.
- Waits till data reaches a particular value OR certain event occurs.
- 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).
136
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.
137
What are the main functions of OS?
- Resource Allocator.
- Control System.
138
What does the Resource Allocator do?
- Manages all hardware resources
- Decides between conflicting requests for efficient & fair resources.
139
What does the Control System do?
Controls execution of programs to prevent errors & improper use of the computer.
140
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)).
141
What does ROM stand for?
Read-Only Memory.
142
What does EPROM stand for?
Erasable Programmable ROM.
143
What are examples of firmware?
BIOS (Basic, Input, Output, System).
144
How does OS share 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.
145
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.
146
What is an Interrupt Vector?
Reserved part of memory, tracking which interrupts need to be handled.
147
What is the process the Operating System follows to handle 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.
OR
-It temporarily halts the current execution of the CPU so that it can address the urgent task associated with the interrupt.
- Once the interrupt is handled, the CPU resumes its prior activity.
148
How can software programs generate Interrupts?
- Through System calls (Like when an error occurs).
- Software-generated interrupt is called a TRAP.
149
What is Main Memory?
- Large storage that the CPU can access directly.
- Volatile (Memory not saved when laptop turned off).
- RAM.
150
What is Secondary Storage?
- Large non-volatile storage (Flash memory, Magnetic Disk & CDs).
151
What are the services of OS?
- UI.
- Processes.
152
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.
153
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.
154
What are examples of OS functions?
- Program Execution: System must be able to load a program into memory and run that program.
- 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.
- Interprocess Communication (IPC): Allowing the process to share data through message passing or shared memory.
155
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.
156
What is 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 functions.
157
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.
158
What are common APIs in System Calls?
- Win32 for Windows.
- POSIX API for UNIX-based system.
159
What are 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).
160
What are System Calls for Read File operation?
- Read data from the file.
- Returns No. of bytes read or 0 for EOF.
161
What are System Calls for Write File operation?
- Write data to a file. Returns No. of bytes written.
162
What are System Calls for Close File Operation?
- De-register the file with the OS.
- No further operations on the file are possible.
163
What does the System Calls return when an error occurs?
- These system calls return a -ve number on error.
## Footnote
Can use error-function to display error.
164
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.
165
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.
166
What is Modular Kernel Implementation?
- Most modern OS implement Kernel modules.
- Object-oriented approach.
- Each core component is separate.
- Each talks to the others over known interfaces.
167
What is a Modular Kernel?
- Similar to layered architecture but with flexibility.
- Separation of the modules is still logical since all kernel code runs in the same privileged address space.
168
What's in the kernel core?
- Device & Bus Drivers.
- Scheduling Classes.
- File Systems.
- Loadable System Class.
- Executable Formats.
- Streams Module.
- Miscellaneous Modules.
169
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.
170
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.
171
Give a Drawback of Microkernel.
- Overhead of user space or kernel space communication.
172
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.
173
What is VM History?
- Appeared in IBM mainframes in 1972.
- Multiple execution environments can share the same hardware.
174
Pros of VM?
- Used for development and testing, due to easy reversal accidentally destroyed OS back to previous state.
175
What is the Open Virtualisation Format?
The standard format of VM, which allows it to run within many different VM Platforms.
176
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.
177
What is para-virtualisation?
- Presents guests with system similar but not identical hardware.
- Guest OS must be modified to run on para-virtualisation 'hardware'.
178
How is para-virtualisation hardware modified?
- Kernel is recompiled with all code that uses privileged instructions replaced by hooks into the virtualization layer.
179
What is VMWare Architecture?
- Implements full virtualisation, such that guest OS don't require modification to run upon the VM.
180
What are device drivers?
Software that allows other programs to interface with external devices through the device controllers.
181
What does OPEN do in System Calls?
Make device available.
182
What does READ do in System Calls?
Read from device.
183
What does WRITE do in System Calls?
Write to device.
184
What does IOCTL do in System Calls?
Perform operations on devices.
185
What does CLOSE do in System Calls?
Make devices unavailable.
186
What is Kernel Side?
Each file may have a function associated with it which is called when corresponding system calls are made.
187
How are Devices Categorised?
- Physical Dependencies: Between devices (Connected to USB-hub).
- Buses: Channels between processors & 1 or more devices.
- Classes: Set of devices of the same type (e.g., keyboards or mice).
188
How are Interrupts handled in Device Drivers?
- Device sends interrupt.
- CPU selects the appropriate interrupt handler.
- Interrupt handler processes.
189
What 2 important tasks does the Interrupt handler process?
- Data to be transferred to/from device.
- Waking up processes which wait for data transfer to be finished.
190
How important is the Interrupt Processing Time?
- Must be fast.
- Data transfer is fast; the rest of the processing is slow.
191
What are the 2 Halves of the interrupt?
- Top Half: Directly by the interrupt handler.
- Bottom Half: Runs in Interrupt context & does the rest of the processing.
192
What is Memory Management?
Management of a limited resource; sophisticated algorithms needed, together with support from HW & the compiler & Loader.
193
Key Point for Memory Management?
The program's view memory is a set of memory cells at address 0x0 & finishing at some value (LOGICAL ADDRESS).
194
Hardware for Memory Management?
Set of memory cells starting at address 0x0 & finishing at some value (PHYSICAL ADDRESS).
195
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.
196
What is External Fragmentation?
Small holes appear in memory over time.
197
What is Internal Fragmentation?
Programs are only a little smaller than the hole, so the leftover is too small to qualify as a hole.
198
What is Swapping?
- Memory Management Technique.
- Too high memory demand: Memory of some processes is transferred to disk.
199
What can be done by a Special Program?
Execution Time: Needs Hardware support
200
What is Dynamic Linking?
Use only one copy of the system library. OS has to help: the same code accessible to more than one process.
201
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.
202
What are the Problems of Swapping?
- Big Transfer Time
- What to do with pending I/O
- Not principal memory management technique.
203
What are Strategies for Choosing Holes?
- First-fit
- Rotating First Fit
- Best Fit
- Buddy System.
204
What is First-fit?
Start from the beginning & use the first available hole.
205
What is Rotating First Fit?
Start after the last assigned part of memory.
206
What is the Best Fit?
Find the smallest usable space.
207
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.
208
# c
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.
209
What hardware support is Mandatory for Paging?
- Small Page Tables
- Fast Registers
- Large Page Tables
- Stored in Main Memory
- Caches most recent entry.
210
How is memory protected in paging?
Info stored in a page table.
211
What is Segmentation?
Divides memory according to its usage by programs. Requires Hardware support.
212
What is Virtual Memory?
Complete separation of logical & physical memory.
213
What is the problem with Virtual Memory?
Enormous difference between memory access speed & disk access speed.
214
What is Demand Paging?
- Virtual Memory implemented as demand paging.
- Memory divided into same-size pages, with valid/invalid bit.
215
What is a Swapper?
'Swap out' process (move whole memory to disk & block process).
216
What is a Pager?
'Which pages to move' when the move is needed.
217
Why is it crucial to have a minimal rate of page faults?
10% slowdown due to page fault, then fault rate: HHD: p < 10^(-6), SSD: p < 10^(-4).
218
What are the 2 Strategies made in Demand paging?
Pager & Swapper.
219
What are Page replacement Algorithms?
- First In First Out
- Optimal Algorithm
- Least-Recently Used.
220
What is First In First Out?
- Easy to implement.
- Doesn't take locality into account.
221
What is an Optimal Algorithm?
Select a page which will be reused at the latest time.
222
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.
223
What is a CON for Least-Recently used?
Requires a lot of hardware support.
224
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.
225
What is the second Chance algorithm?
FIFO.
226
What replacement algorithm should you use?
FIFO, but it skips reference bit 1 & resets them to 0.
227
What is Thrashing?
- Page fault rate is high, when the process locks frames it constantly uses.
228
What are the 2 solutions for Thrashing?
- Working-set model (BASED ON LOCALITY).
- Page Fault Frequency (Direct approach).
229
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.
230
For the working set what is the Difficulty?
Determining the Working set.
231
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.
232
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.
233
What is Memory Management in Linux Kernel?
- 4 Segments in Total:
- Kernel Code
- Kernel Data
- User Code
- User Data.
234
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.
235
What is the 64-bit architecture?
- Kernel space address and user space address are split in half.
236
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.
237
Give a Summary of Device Drivers:
Implement open, read, write & close with common structure.
238
Give a Summary of Memory Management:
- Management of limited resources -> serious effort required.
- Need to isolate memory for each process.
239
What is Kernel Programming?
- Has access to all resources.
- Programs not subject to any constraints from memory access or hardware access.
240
What is the result of Faulty Programs?
System Crash.
241
What are System Calls?
The kernel provides its function only via special functions.
242
Does there have to be a strict separation of kernel data & data for user programs?
YES.
243
What functions are used for strict separation?
- copy_to_user()
- copy_from_user().
244
How do Interrupts work in Kernel?
- Asks Hardware to perform a certain action.
245
What are the 2 Main Modes for kernel code?
- Process Context
- Interrupt Context.
246
What is Process Context?
Kernel code works for user programs by executing a system call.
247
What is Interrupt Context?
Kernel code handling an Interrupt (by a device).
248
What are Kernel Modules?
- Add code to the running kernel.
- Useful for providing device drivers which are required only if hardware is present.
249
What is modprobe?
Inserts module into running kernel.
250
What is rmmod?
Removes modules from running kernel.
251
What is lsmod?
List Currently running module.
252
Why is concurrency handling important?
- Manipulation of data structures which are shared between code running in process mode & code running in interrupt mode.
253
What are 2 ways to achieve Mutual exclusion?
- Semaphores/Mutex
- Spinlocks.
254
What is Semaphores?
- Entering the critical section fails, the current process is put to sleep until the critical region is available.
255
What are the Semaphore Functions?
- DEFINE_MUTEX()
- mutex_lock()
- mutex_unlock().
256
What is Spinlocks?
- Processor tries repeatedly to enter the critical section.
257
What are the disadvantages of Spinlocks?
Have busy waiting.
258
What are the Spinlock Functions?
- spin_lock_init()
- spin_lock()
- spin_unlock().
259
What are the 2 Kinds of Semaphores?
- Normal Semaphores
- Read-Write Semaphores.
260
What is a Read-Write Semaphore?
It is useful if some critical region only reads shared data structs & this happens often.
261
Explain how the Programming data transfers between userspace & Kernel?
- Linux maintains a directory called proc as an interface between user space & kernel.
262
What are the major parts of the Kernel?
- DEVICE DRIVERS : subdirectory drivers, sorted according to category.
- FILE SYSTEM: In subdirectory fs.
263
What is the variety of programs the OS executes?
- BATCH SYSTEM: jobs.
- TIME-SHARED SYSTEMS: User programs/tasks.
264
What do processes include?
- Program
- Stack
- Program Counter
- Data Section.
265
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).
266
What states go to NEW state?
NONE.
267
What states go to READY State & HOW?
- NEW (Newly-admitted process).
- WAITING (Completion of an I/O event).
- RUNNING (Pre-empted / Awaiting its turn on the CPU).
268
What states go to RUNNING State & HOW?
- READY (Scheduler Dispatch).
269
What states go to WAITING State & HOW?
- RUNNING (I/O or Event Wait).
270
What states go to TERMINATED State & HOW?
- RUNNING (Exit).
271
What is a Process Control Block?
- Info associated with each process, which is stored as various fields within kernel data.
272
How are Process Created?
- Parent process creates the children process, which creates other methods, making a tree of processes.
273
What is PID and what does it stand for?
PID (Process Identifier) - Identifies & Manages Processes.
274
How does resource sharing between parent and child process?
- Parent & Child share all resources.
- Child share subset of parent's resources.
- Share no resources.
275
How are parent & child executed?
- Parent & Child execute concurrently.
- Parent waits until terminates.
276
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.
277
Explain process termination?
- Executes last statement & asks OS to delete it (EXIT).
- Output data from child to parent.
278
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.
279
What is the problem with scheduling?
- Processes Competing for resources.
- Import OS functions: define a schedule to manage access of process to these resources.
280
Give the 3 Scheduling Queues.
- Job Queue
- Ready Queue
- Device Queue.
281
What is the Job Queue?
Set of all processes in the system.
282
What is the Ready Queue?
Set of all processes residing in Main Memory, ready & waiting to execute.
283
What is the Device Queue?
Set of processes waiting for I/O devices.
284
Can Processes migrate among various queues?
YES.
285
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%.
286
What are the Scheduling Criteria?
- CPU Utilization
- Turnaround Time
- Throughput
- Waiting Time
- Response Time
287
What is the purpose of the Scheduling Criteria?
Conflicting criteria to measure the success of scheduling
288
What is Turnaround Time in Scheduling?
The time it takes for each process to be executed
289
What is Throughput in Scheduling?
No. of processes completed within a given time
290
What is the Waiting Time for Scheduling?
The time spent in the Ready Queue
291
What is the Response Time for Scheduling?
The time between the submission of the Request and the production of the first output
292
What are the 2 Categories of Processes?
- I/O Bound Processes
- CPU - BOund Processes
293
What are I/O Bound Processes?
- Spends more time doing I/O than computation
- Many short CPU bursts
294
What are CPU-Bound Processes?
- More time doing computation
- Few very Long CPU Bursts
295
What are the Scheduling Algorithms?
- First-Come-First-Serve
- Round-Robin
- (Theoretical) Shortest Job First
- Priority Scheduling
- Multi-Level Queue Scheduling
- Processor Affinity
- Load Balancing
296
What is the First-Come-First-Served Algorithm?
- Job is put in a queue & served according to the arrival time
OR
- Jobs are executed based on the order they were called or their position in the queue.
297
Give 1 Pro & Con of First-Come-First-Served
PRO: Easy to Implement
CON: CPU, as intensive processes can have very long wait times.
298
What is the Round Robin Algorithm?
- FCFS with preemption
- It's a time-sharing system
- SPlits CPU time up so that a bit of each process can be done.
299
What is the Problem with Round Robin?
Get time Quantum (time before preemption) right
If too small then too many context switches
If too large then the Process can monopolise the CPU
300
What happens if Round Robin Preemption time is too Short?
There can be too many context switches
301
What happens if Round Robin Preemption time is too Large?
The Process can Monopolise the CPU
302
What is the Shortest Job First Algorithm?
The next process is the one with the shortest burst time
303
Why is Shortest Job First Theoretical?
As it cannot be implemented
304
What is a Pro & a Con of Shortest Job First?
CON: Not Implementable
PRO: Has the smallest AVG. wait time
305
How can we calculate the Average Wait time of the Shortest Job First if it is theoretical?
- Strategy against which to measure the others
- Approx. the burst time by extrapolating from previous behaviours done by weight times more than older ones:
T[n+1] = a*t[n] + (1 - a)*T[n]
306
What is the Assumption with Priority Scheduling?
Priority is associated with each process, CPU is allocated to the process with the highest priority
307
What do you do if 2 Processes have the same priority in priority scheduling?
Just do FCFS
308
What are the 2 variations of Priority Scheduling?
With Preemption
Without Preemption
309
What is Priority Scheduling with Preemptions?
A newly arrived process with a higher priority may gain access to the processor immediately if a process with a lower priority is running.
310
What is Priority Scheduling without Preemptions?
The newly arrived process always waits
311
What is the benefit of preemptions in Priority scheduling?
Good for ensuring quick responses for higher priority processes
312
What is a CON of Priority Scheduling?
Low Priority starvation
May never get to run low-priority task if loads of high priority are always called
313
How to fix the CON, Low Priority Starvation, for Priority Scheduling?
Increase the priority of some processes after a while (AGING)
314
What is Multi-Level Queue Scheduling?
- Used when processes can be partitioned into groups
- Splits Ready Queue into several separate queues, with separate scheduling algorithms
(The Scheduling between queues usually implemented as pre-emptive priority scheduling)
315
Give an example of a Possible Queue setup for Mulit-Level Queue Scheduling
=> System processes
=> Interactive Processes
=> Interactive Editing Processes
=> Batch Process
316
How is Scheduling done for Multiprocessor systems?
- Gets more complex with more CPUs
COMMON CASE:
Symmetric Multiprocessing (SMP)
- All processors are identical, and can be scheduled independently
- Separate Ready-Queue for each process
- OR shared Ready-Queue
317
What are the 2 types of Processor Affinity?
soft & hard affinity
318
What is Soft Affinity?
The current CPU is only preferred when rescheduled
319
What is Hard Affinity?
The Process may be bound to a specific CPU
320
What is a Pro of Processor Affinity?
The caches remain valid and avoid time-consuming cache invalidation & recovery
321
What is Load Balancing?
Use all CPUs equally
(Goes Against Processor Affinity)
322
What is Push Migration in Load Balancing?
Periodically check load & push processes to less loaded CPUs
323
What is Pull Migration in Load Balancing?
Idle CPUs pull processes from busy CPIs
324
How does Linux Implement Scheduling?
- Sever Schedulers may co-exist
- Assign a fixed % of CPU time to each scheduler
325
What are Important Schedulers in LINUX?
- Round Robin with Priorities
- Real-TIme schedulers
326
What is the Implementation for Round Robin with Priorities?
- Maintain tree of processed ordered by runtime allocated so far
- Pick the next process as one with the least runtime allocated
- Insert the new process in Ready-Queue at the appropriate place in the tree
- Priorities handled by giving weights to run times.
327
What is the background of the Critical Section Problem?
Shared resources (Memory) need safe access by concurrent processes to avoid data inconsistency
328
What is an example of a critical section problem?
- Produce writes item to a finite buffer
- Consumer reads them
- Challenges occur when ensuring proper sequencing
(e.g Consumer should wait if the buffer is empty)
329
What is the Race Condition for a critical section problem?
When multiple processes update shared data unpredictably
330
Give an example of the issues that will occur in the critical section problem's race condition.
If processes increment/ decrement a shared counter (count) in overlapping operations, the final value can become incorrect
Example Order:
One process calculates a cal, while another reads the old value leading to inconsistencies
331
Give the 3 solution Criteria to fix Race Conditions.
- Mutual Exclusion
- Progress
- Bound Waiting
332
What is mutual exclusion in solution criteria?
One process accesses the resources at a time
333
What is Progress in solution criteria?
A process must not be indefinitely blocked if it can safely enter
334
What is Bound Waiting in Solution Criteria?
No Process waits indefinitely while others repeatedly enter
335
What is the producer code in the producer-consumer code?
```
while(true){
while (count == BUFFER_SIZE);
buffer[in] = nextProduced;
in = (in + 1)% BUFFER_SIZE;
count++;
}
```
336
What is the consumer code in the producer-consumer code?
```
while(true){
while (count == 0);
nextConsumed = buffer[out];
out = (out + 1)% BUFFER_SIZE;
count--;
}
```
337
Explain the producer code.
The producer generates items & adds them to a bounded buffer if space is available
338
Explain the consumer code.
The consumer removes items from the buffer if it's not empty
339
What is the issue with the producer & consumer code?
Without proper synchronisation, simultaneous updates to count may cause data races, resulting in inconsistency
340
What is the Peterson's Algorithm?
- A Solution for the Critical Problem
- Two processes sharing a turn
- Each process signals its intent & alternates access using a turn variable
341
What are the limitations of Peterson's Algorithms?
- Only works for 2 processes
- Assumes some CPU operations are atomic, which isn't always true
342
What are the Pros of Peterson's algorithm?
Simple & ensures fairness (processes alternate access)
343
What is the code for the Peterson's Algorithms?
```
do {
wants_in[i] = True;
turn = j;
while (wants_in[j] && turn == j);
wants_in[i] = False;
} while (true)
```
344
What 2 processes share 2 variables in Peterson's algorithms?
- int turn;
- Boolean wants_in[2]
345
What does turn indicate in Peterson's algorithm?
Indicates whose turn it is to enter the critical section
346
What does the array wants_in used for?
To indicate if a process is ready to process is ready t enter the critical section
- Flags showing which process wants access
- wants_in[I] = True implies that the process is ready
347
what does P_i represent?
A process
348
What is Hardware Synchronization?
Special hardware mechanisms are used to ensure proper synchronisation of processes or threads.
349
Give an example of the Atomic Instructions.
- TestAndSet lets processes lock resources without being interrupted mid-operation
- Simple Implementation can still lead to inefficiencies like busy waiting (Constant checking of resource status)
350
Give the code for TestAndSet.
```
boolean TestAndSet (boolean *target){
boolean original = *target
*target = True;
return original;
}
do {
while (TestAndSet(&lock));
lock = False;
} while (True);
```
351
Give an Explanation of the TestAndSet code.
- TestAndSet automatically sets lock to True & returns the old Value
352
What is the drawback of the TestAndSet code?
High CPU usage from busy waiting
353
Explain a Real Problem: Priority Invasion?
This occurs when a low-priority process locks a resource that a high-priority one needs, causing delays.
354
What is the Sleep-Based Mutex Locking code?
```
do{
while(TestAndSet(&lock)){
sleep();
}
wake_up(all);
lock = False;
} while(True)
```
355
Explain The sleep+based Mutex Locking Code.
- To avoid CPU waste in busy waiting, processes sleep and only wake up when the critical section is free
- Issues arise if wake signals are missed, requiring a more advanced synchronisation mechanism
356
What are Semaphores?
- Intro to reduce CPU overhead
- (High-Level Solution)
357
What are the 2 key operations in Semaphores?
- wait()(p): blocks the process if access isn't available
- signal()(v); Releases the lock & potentially wakes a blocked process
358
What is the application of semaphores?
Manage Reader/Writers or buffer capacities
359
What is the general structure for Semaphores? (CODE)
```
semaphore mutex;
do{
wait (mutex);
signal(mutex);
} while(True)
```
360
What is the Bounded Buffer with semaphores?
Use semaphores for mutex, empty_slots & full_slots to balance producer & consumer operations
361
What is the Bounded Buffer with semaphores code?
PRODUCER:
```
while(true){
wait(empty_slots);
wait(mutex);
signal(mutex);
signal(full_slots);
}
```
CONSUMER:
```
while(true){
wait(full_slots);
wait(mutex);
signal(mutex);
signal(empty_slots);
}
```
362
Explain the Bounded Buffer with Sempahores code.
- empty_slots: track available buffer slots
- full_slots: Tracks available items in the buffer
- mutex: Protects shared buffer operations
363
What is the Readers-Writers Problem?
BALANCE FAIRNESS:
- Allow simultaneous readers if no writers
- Prevents writers from intervening when readers hold the lock
364
What is the Reader code for the Reader-Writers problem?
```
while(true){
wait(mutex);
read_count++;
if(read_count ==1)
wait(wrt);
signal(mutex);
wait(mutex);
read_count--;
if(read_count == 0)
signal(wrt);
signal(mutex);
}
```
365
What is the Writer code for the Reader-Writers problem?
```
while(true){
wait(wrt);
signal(wrt);
}
```
366
Give an Explanation of the Reader code.
Multiple Readers can access simultaneously if no writer is active.
367
Give an Explanation of the Writer code.
Writers have exclusive access, preventing both readers and other writers from gaining access
368
What is the File System?
- Crucial component of an OS
- Manages how data is stored & retired on storage devices
- This document provides an in-depth understanding of how file systems, the data structure use & strategies for optimising their performances
369
What is the logical view of the File System?
- Programmer & end-users, the file system appears as a hierarchical tree structure
- It comprises files (data containers) & directories (Organisation units for files & other directories)
- Common operations include creating, reading, writing & deleting files
370
What is the Physical view of the File System?
- On the storage medium, data is stored in blocks(FIXED SIZE)
- The OS must map the logical blocks of data to physical blocks on the disk.
371
What are the Popular approaches to implementing a File system?
- Linked List Allocation
- Indexed Allocation
372
Explain the Linked List Allocation.
- Each block stores both data & pointer to the next block
- Simple to implement & suited for sequential access
373
What is a Drawback of the Linked List Allocation?
- Inefficient for random access because every preceding block in the chain must read a specific position
374
Explain the Indexed Allocation.
- Special index block contains all the pointers to the data blocks of a file
(SIMILAR TO PAGE TABLE IN M.MANAGMENT)
- Supports random access efficiently, as all locations are available in one place
- Accommodate varying file sizes, additional layers of indexing are used for large files
(Indirect Index Blocks)
375
What are blocks called in Linux?
Inodes
376
What do Inodes what type of metadata?
- File size
- Permissions
- Ownership Info
377
What does the FAT File System Stand for?
File Allocation Table
378
What is FAT an example of?
Fundamental example of linked list allocation
379
What are the Key Concepts of FAT?
CLUSTERS:
- Logical units consisting of one or more sectors (smallest physical storage unit) 512 bytes
FAT TABLE:
- Maintains a Linked List of clusters belonging to a file
- Stores cluster chain, where each entry indicates either the next cluster or an EOF marker
380
What is the Structure of a FAT File System?
BOOT SECTOR:
- Contains basic file system metadata
FAT Area:
- Stores the Linked List (Cluster Chain) for all file
ROOT Directory:
- Fixed-size table storing file metadata
(e.g size, name, starting cluster)
Data Area:
- Contain the file contents
381
What are the drawbacks of the FAT Files System?
FILESIZE LIMITS:
- FAT16 Supports up to 2GB
- FAT32 extends these limits but remains inefficient for modern needs
CLUSTER WASTE:
- Large Cluster size can lead to internal fragmentation
(Unused space within the allocated cluster )
382
How can you improve the Performance of FAT File Systems?
-CACHING
- JOURNALING
- DISK ACCESS OPTIMISATION
383
Explain Caching (FAT).
- Frequently accessed disk blocks (directories or file content) are cached in memory to reduce disk read/write operation)
- Improves performance but can lead to inconsistencies during system crashes (data loss in writes)
384
Explain Journaling (FAT).
- Mitigates data loss during crashes, and journaling files (e.g ext3,ext4, NTFS) borrow concepts from databases:
TRANSACTION POINTS:
- Ensure consistent states by periodically writing cached data to the disk
LOG:
- Maintain a log of pending write operations. In case of crashes, the log is replayed to restore the system to its last consistent state
385
Explain the 3 steps involved in Disk Access Optimisation.
SEEK TIME:
- Time taken to move the read/write head to the appropriate track
ROTATIONAL LATENCY:
- Waiting for the desired Block to rotate under the head
Transfer Time
- Actual Time to read/write the data
386
What is the performance of HHDs for Disk Access Optimisation?
seek time & latency dominate access time, necessitating scheduling algorithms
387
What are the Scheduling Algorithms for Disk Access Optimisation?
- First-Come-First-Serve
- Shortest Seek TIme First
- SCAN (Elevator Algorithm)
- LOOK scheduling
388
What is First-Come-First-Serve in Disk Access Optimisation?
- Simple Strategy
- Can Lead to high seek time if disk requests are scattered
389
What is the Shortest Seek Time First in Disk Access Optimisation?
- Select the request closets to the current head position
- Reduces seek time but can cause starvation for distant requests
390
What is the SCAN in Disk Access Optimisation?
- Head moves in one direction, servicing all requests until the end of the disk, then reverse
- Eliminates starvation but may have fairness issues
391
What is the LOOK Scheduling in Disk Access Optimisation?
- Refined version of SCAN
- Head stop at the last request instead of going to the disk's end
392
Explain the Special Case: SSDs
- SSDs have negligible seek & latency time, simple scheduling (e.g FIFO or No-op) suffices
393
What is Virtual File System (VFS)?
- Provides a unified interface for different file systems (e.g ext4, FAT, NTFS)
394
How does the Virtual File System (VFS) handle operations?
MANAGING INODES:
- Metadata blocks for files & directories
CACHING:
- Frequently used directory entries
SUPERBLOCKS:
- Metadata for entire file systems
395
How does VFS work?
- All system calls (e.g open, read, write) are directed the operation accordingly
- VFS determines the appropriate underlying file system & delegates the operation accordingly
396
What are Linux Device Drivers?
- Low level software components
- Manage interactions between OS & Hardware
397
# Linux Device Drivers
What does Isolation mean?
- Applications never interact with hardware directly
- Interact via drivers
398
# Linux Device Drivers
What is Hardware Abstraction?
Drivers abstract hardware-specofoc operations & present a standard interface to application & kernel components
399
# Linux Device Drivers
Give the categories for the Drivers .
- Char Driver
- Block Driver
- Network Driver
400
# Linux Device Drivers
What are Char Drivers?
- Read/Write data sequentially (e.g serial ports)
- E.g */dev/ttyySO* for serial communications
401
# Linux Device Drivers
What are Block Drivers?
- Manage data is fixed-size block (disk drivers)
- E.g */dev/Sda* for hard drives
402
# Linux Device Drivers
What are Networkd Drivers?
- Facilitates sending/revcieving network packets (Ethernet interface)
- Each driver type handles specifi hardware & intergrated within the Linux Kernel to respomf to system calls interrupts
403
# Linux Device Drivers
How to interact with Device Drivers?
- For a user-space (app runs outside the kernel)
- Device are asscoaited with speacial files found in the */dev* directory
- (*/dev/Sda* for storage devices)
404
# Linux Device Drivers
What are the 5 primary device interaction that involve system calls?
- Open
- Read
- Write
- ioctl
- close
405
# Linux Device Driver
What does open do?
Prepares a device for communications (opening a file)
406
# Linux Device Driver
What does read do?
Retrieves data from the devices
407
# Linux Device Driver
What does write do?
Sends data to the device
408
# Linux Device Drivers
What does ioctl stand for?
Input/Output Control
409
# Linux Device Drivers
What does ioctl do?
Executes device-specific operations, such as configuring the device setting
## Footnote
(Optional)
410
# Linux Device Drivers
What does close do?
Closes access to the devices
411
# Kernel Side Implementation
What does the kernel side have?
- Each file in */dev* can have correspondings functions listed above
- These functions handle system calls when invoked by a user program
412
# Kernel Side Implementation
What does the call *open("/dev/deviceName")* do?
- *"open"* function is triggered within the kernel to make the device avaliable for use
413
# Kernel Side Implementation
What does read invoke?
It invokes a Kernel-level *"read"* function
414
# Kernel Side Implementation
What does header file *linux/fs.h* defines?
It defines the set of avaliable file operations to ensure standardised implementation across device drivers
415
# Category of devices (LINUX)
What are physical dependencies?
Device connected via a USB hub & depends on the hub for operations
416
# Category of devices (LINUX)
What are Buses?
- Comms channels between processors & devices (e.g USB, PCI)
- These channels can be physical (hardware-based) or logical
417
# Category of devices (LINUX)
What are Classes?
Device grouped by type, such as keyboard or mice
418
# Category of Devices (LINUX)
How do the devices help kernel?
Orginisation helps the kernel efficently mamage devices & their interactions with applications
419
# Linux
How to handle interrupts?
When a device generates an interrupt (signal to notify the processor of an event)
420
How is the Flow of handle interrupts?
- Device singnals the CPU
- CPU slects the appropriate interrupt handler to process the event
421
What are the Interrupt Handlers 2 Primary Actions?
- Transfers data between the device & kernel
- Wakes up processes waiting fordata transfer to compete
422
What is the Interrupt Bit Reset?
Handler resets the device's interrupt bit to allow future interupts
423
# Min Interrupt Porcessing Time
What is the Optimized Performance?
| There are 2 halves
Top Half:
-Driectly invoked by the interrupt handler
- Quickly trnasfer data to/from the device to kernel buffer
- Schedules the bottom hald for additional processing
Bottom Hald:
- Operates in the interrupt context
- Handles time-consuming task (e.g working thrugh a protocol stack, notifying waiting processes)
424
# Min Interrupt Porcessing Time
What benefits does the division ensures?
- Related actions are fast
- Preventing system slowdown
425
What does the File Operation Struct do?
Binds system calls *(e.g, open, read, write)* to their corresponding kernel-levl implemntations
426
File Operation Struct Code?
```
static struct file_operations device_fops = {
.open = device_open,
.read = device_read,
.write = device_write,
.release = device_close
};
```
427
# File Operation Struct
What are .open, .read, .write, .release ?
They are pointers to functions that define behaviour for these operations
428
# File Operation Struct
What are device_open, device_read, device_write?
They are defined functions performing hardware-sepcific tasks
429
What is the Top half code of interrupt handler and give its purpose?
```
irqreturn_t my_interrupt_handler(int irq, void * dev_id) {
transfer_data_to_kernel();
schedule_bottom_half();
return IRQ_HANDLED; // Signals success
}
```
| Purpose: Top half quickly transfers data
430
What is the Bottom Half code of interrupt handler
```
void bottom_half_handler(struct work_struct *work){
process_protocol_stack();
wake_up_process();
}
```
431
What is Simplified Boot Process?
- Kernel intialise data structures & then continuously assigns CPU time to processes base on scheduling logic
- When process completes or a timer event occurs, the kernel selects then next appropriate process
| Forms the basic operating loop of the kernel
432
# Kernel Programming Characteristics
What does Full Access to Resources allow?
- Kernel access hardware & memory acccess
- Faulty or Poorly written kernel code can crash entire system (As it operates without the constraints applied to the program)
433
# Kernel Programming Characteristics
What are System calls ?
- Interactions Between user apps & Kernel occurs through system calls
- Data transfer between user space & kernel space occurs explicitly via functions
| functions : **copy_to_user & copy_from_user**
434
# Proceses Creation
What does fork() do?
Creates a new process
435
What does exec() do?
Replaces the current process image with a new program, Resource sharing between parent & child can vary
436
A simpler summary of Context Switching
- Mechanism for switching the CPU between processes:
**Save Current State:** Outgoing process' context is saved in its Process control block
**Load New State ** Incoming process' context is restored from its Process Control Block
## Footnote
Neccessary for multitasking, contexting switching incur a computational cost
437
Give an overview for Linux task_struct.
- Core data structs to manage processes
- Includes Fields like:
-*volatile long state* (Process State)
- void * stack (Process Memory)
- pid_t pid (Process ID)
- struct list_head tasks(Linked List for task Managment )
- Accessible through */proc/pid*
438
What are Windows Data Strucutres?
*EPROCESS & PEB*
- Tracks enviromental variables, process management details & resources
439
# Process Termination
What triggers child processes to be aborted by parent?
- Resource overuse
- Redundency of Child process
- Parent Process Termination (cascading effect in some OS)
- Terminating parent & cause all children to terminate
440
# Sockets
Pthread_create () Code :
```
int pthread_create(
pthread_t *thread_id, // ID number for thread
const pthread_attr_t *attr, // controls thread attributes
void *(*function)(void *), // function to be executed
void *arg // argument of function
);
```
441
# Sockets & Threads
pthread_join CODE:
```int pthread_join(
pthread_t thread_id, // ID of thread to "join"
void **value_pntr // address of function’s return value
);
```
**OR **
```int pthread_join(
pthread_t thread_id, // ID of thread to "join"
NULL
);
```
442
# Sockets & Threads
Code for Mutex Locking / Mutal Exclusion:
```
pthread_mutex_lock(&mutex1);
counter++;
pthread_mutex_unlock(&mutex1);
```
443
# Thread & Sockets
Large Piece of Mutex Lock/Unlock CODE:
```pthread_mutex_t mutex1 =
PTHREAD_MUTEX_INITIALIZER;
int counter = 0;
int main() {
int rc1, rc2;
pthread_t thread1, thread2;
// Two threads execute functionC() concurrently
pthread_create(&thread1, NULL, &functionC, NULL);
pthread_create(&thread2, NULL, &functionC, NULL);
pthread_join(thread1, NULL);
pthread_join(thread2, NULL);
return 0;
}
void *functionC() {
pthread_mutex_lock(&mutex1);
counter++;
printf("Counter value: %d\n", counter);
pthread_mutex_unlock(&mutex1);
}
```
444
# Thread & Sockets
What Code makes it Mutex Lock Fail
```// Thread1
void *do_one_thing() {
...
pthread_mutex_lock(&mutex1);
pthread_mutex_lock(&mutex2);
...
pthread_mutex_lock(&mutex2);
pthread_mutex_lock(&mutex1);
...
}
/ /Thread2
void *do_one_thing() {
...
pthread_mutex_lock(&mutex1);
pthread_mutex_lock(&mutex2);
...
pthread_mutex_lock(&mutex2);
pthread_mutex_lock(&mutex1);
...
}
```
BOTH THREADS STALL INDEFINITELY
DEADLOCK
445
# Threads & Sockets
trylock() CODE:
```int pthread_mutex_trylock(pthread_mutex_t *mutex);
```
446
# Threads
CODE for Condition Variables:
```pthread_cond_t condition_cond = PTHREAD_COND_INITIALIZER;
```
447
# Sockets
Code for thread that goes into waiting stae based on a condtion
`pthread_cond_wait(&condition_cond, &condition_mutex);`
448
# Threads
Waking a Thread based on Condition CODE:
```pthread_cond_signal(&condition_cond);
```
449
What are Interrupts?
- An interrupt is a signal sent to the CPU by hardware or software to indicate the occurrence of an event that requires immediate attention.
