OS unit 3 and 4 Flashcards
(20 cards)
Define concurrency in the context of process/thread synchronization.
What is mutual exclusion in operating systems?
Concurrency: Multiple processes/threads simultaneously
Mutex: prevents multiple processes from entering in critical state at the same time
Utilized using sempahores and locks
Characteristics:
1 One process in CS at a time
2 Other processes wait
3 Used to prevent deadlocks and race condition
Conditions for deadlock. Break down the strategies used for deadlock prevention into their core principles.
1 Mutual Exclusion (shareable resources or multiple instances of one resource)
2 Hold and wait (requests all required resources before execution)
3 No pre-emption (allow pre-emption)
4 Circular Wait (ordering of resource types - allow according to enum number)
What is the Ostrich Algorithm in the context of deadlock?
List the necessary conditions for a deadlock to occur.
The Ostrich Algorithm is a non-preventive approach to handling deadlocks.
Used When: Deadlocks are extremely rare and the cost of prevention, detection, or recovery outweighs the impact of the deadlock itself.
Typical Use Case: UNIX or Windows, where deadlocks may occur very infrequently, and system reboot or manual intervention can resolve them.
Critical section problem prevention
Mutual Exc
Progress (no forcing each other)
Bounded Wait (No indefinite time)
H/W | S/W mutex
H/W
Adv: Faster execution, low overhead, reliability
Disadv: limited protability, h/w dependence
S/W
Adv: portability, felxibility, easy to implement
Disadv: higher overhead, more prone to error
Semaphore | Monitor (7)
1 controls access to shared resources | high-level synch method for shared resources
2 low-level synch primitive | high-level synch primitive
3 complex to implement | easy due to encapsulation
4 manual resource management | automatic resource management
5 does not provide mutex inherently | provides through lock mech
6 can implemented in both h/w, s/w | implemented using lock and combination values
7 uses explicit signal and wait | uses implicit signal through condition variables
mutex | semaphore (8)
1 allow only one process to access | allow access to shared resources
2 only one process can lock | counting lock multiple processes can
3 owned by process that locks it | no ownership
4 binary | can have counting value
5 protects critical section | manage shared resources
6 operations: lock and unlock | operations: signal and wait
7 can lead to starvation | less prone to starvation due to fifo
8 simple to implement | complex to implement
What is memory management in an operating system?
Memory management in an operating system (OS) refers to the process of controlling and coordinating computer memory, assigning portions called blocks to various running programs to optimize overall system performance.
Allocation, Deallocation
Tracking
Protectio
Paging and Segmentation
Fixed partitioning | Dynamic partitioning (adv disadv)
Dynamic -
adv: efficient, better utilization, flexible allocation
disadv: external frag, complex management, compaction overhead
Fixed-
adv: simplicity, fast allocation, low overhead
disadv: internal frag, limited flexibility, static nature
Buddy system
It is a memory allocation technique used in operating systems to manage memory efficiently and reduce fragmentation.
- Total memory is treated as a single block of size 2^U
- A minimum block size 2^L
adv: reduce fragmentation, fast merging, efficient splitting
disadv: complexity, internal frag
Why is relocation in memory management necessary?
1 Multiprogramming: Multiple processes to coexist in memory.
2 Dynamic memory allocation: Programs can be moved during execution.
3 Efficient memory use: OS can relocate processes to compact free space.
Types:
Static (compile time), Dynamic (run time)
How would you implement a Least Recently Used (LRU) page replacement algorithm in a system with virtual memory?
LRU - page replacement algorithm
Keep track of least recently used pages in memory
DS = HashMap (maps page numbers to nodes in LL)+ Doubly Linked List (maintains order of the pages)
Process:
If page in memory :
If page not in memory:
-If memory full:
–Remove page from tail (least recently used)
-Insert new from head
-Add to map
TC = O(1)
SC = O(N)
Virtual memory
Memory management technique used by OS to create illusion of larger main memory (RAM)
Key Components:
1 Abstraction (each process its own address)
2 Paging
3 Page table
4 Demand paging (Pages loaded only when need onto RAM)
If a process requires more memory than its allocated partition in dynamic partitioning, how would the system handle it?
1 Swapping
2 Memory Compaction
3 Paging/Segmentation
4 Dynamic Expansion
5 Process Termination or Error
Explain the concept of page replacement in virtual memory.
What happens during a page fault in demand paging?
Page replacement - replacing pages when demanded page not in main memory and RAM full
- no free frame availavble
- page not available in main mem
- methods (FIFO, LRU, Optimal)
Demand Paging - not loaded until demand - exist in secondary swap space
Page Fault - interrupt when access to non existent page asked by process
1 Page fault interrupt
2 OS searches page table for missing frame
3 Locate on disk : Fetch page from sec memory (swap space)
4 Find free frame
5 Update page table
6 Resume execution
How would you assess the efficiency of different page replacement algorithms (FIFO, LRU, Optimal)?
FIFO
-des: first in first out
- Simple and easy to implement
-drawback: may cause more page faults
LRU
-des: least recently used
- assumes recent past = future
-drawback: more efficient than FIFO but complex to implement
Optimal
-des: removes least future use
- Theoretically most ideal
-drawback: impossible to implement
1 Simulate Algorithms (same seq pages, same no of pages)
2 Analyze with patterns
3 Compare complexity and efficiency
Analyze how thrashing can occur in a system with virtual memory and how it can be mitigated.
performance degradation condition in a system using virtual memory, where the CPU spends more time swapping pages in and out of memory than executing actual instructions.
1 Page Fault Frequency (PFF) Control
2 Reduce Degree of Multiprogramming
3 Use Better Page Replacement Algorithms
4 Memory Allocation Adjustments
How buddy system handles non power of 2
Round up to nearest power of 2
Allocate block and maintain
Find or split block
Dynamic partitioning handles memory frag issues
Memory utilization
Fragementation metrics
Simulated load testing
Failed allocation despite free memory
Paging | Segmentation
Fixed size block | Variable
Internal frag | External
Address space broken into fixed called pages| broken into variable called seg
Page table | Segment table
Faster in mem access | Slow
Does not allow sharing procedures | Allows
Paging address space is 1d | Many independent address spaces
H/W decided page size | User decides seg size
