Operating systems Flashcards
to study
1
Q
What defines a process in deadlock ?
A
if every process in the set is
waiting for an event that can be caused only by another process in the set.
2
Q
What is a pre-emptible resource ?
A
A pre-emptible resource is one that can be taken away from a process with no ill effect to the process; e.g., memory.
3
Q
What is a non pre-emptible resource ?
A
A non-preemptible resource is one that cannot be taken away from its user since it will make the user fails; e.g., printers
4
Q
What are the four necessary conditions for deadlock to occur ?
A
- Mutual exclusion condition. Only one process at a time can use the resource.
- Hold and wait condition. A process holding at least one resource is waiting to acquire additional resources held by other processes.
- No pre-emption condition. A resource can be released only voluntarily by the process holding it after that process has completed its task.
- Circular wait condition. There exists a set {P0, P1, …, Pn} of waiting processes such that P0 is waiting for a resource that is held by P1, P1 is waiting for a resource that is held by P2, …, Pn-1 is waiting for a resource that is held
by Pn, and Pn is waiting for a resource that is held by P0.
5
Q
Name the 3 methods for HANDLING deadlock ?
A
- Use a protocol to ensure that the system will never reaches
deadlock
– Using deadlock prevention and/or deadlock avoidance techniques - Allow the system to enter a deadlock state and then recover
– needs deadlock detection and deadlock recovery algorithms - Ignore the problem and pretend that deadlocks never occur in
the system
– used by most OS, including UNIX
6
Q
Name the 3 deadlock prevention techniques.
A
- Deny mutual exclusion. ( Note this can only be used with shareable resources).
- Deny hold and wait. (Must guarantee that whenever a process requests a resource, it does not hold any
other resources). - Prevent no pre-emption (i.e., allow pre-emption)
- Deny circular wait. (All resources are ordered and each resource must request increasing order of resources.
7
Q
Name some techniques for the deny hold and wait technique and state an issue with it.
A
- Each process is granted all resources before it starts
- Allows a process to request resources only when it has none
Problems:
- Resource utilisation is low
- Possible starvation.
8
Q
Describe the no pre-emption technique and give a problem with it.
A
When a process holding some resources requests other resource that cannot
be immediately allocated, it must release all resources currently being held .
Problem:
Can be applied easily to resources whose state can be saved easily (e.g.,
memory), but not so easily for others (e.g., printer)
9
Q
Name a problem with the deny circular wait technique.
A
It may be impossible to find a resource ordering
that satisfies everyone
10
Q
what is the safe state ?
A
When a process requests an available resource, the system checks if its allocation keeps the system in safe state
The system is in safe state if there exists a safe sequence of all processes
11
Q
What is deadlock avoidance and what is it used for?
A
Used to keep a system in a safe state.
The system must have some additional priori information
about which resources a process will request and use during its lifetime.
The deadlock-avoidance algorithm dynamically examines the resource-allocation state to ensure that there can never be a circular-wait condition
12
Q
What is the banker’s algorithm ?
A
Each process must have a priori claim that states the maximum number of instances of each resource type that it may need .
13
Q
Name and describe the 2 types of deadlock detection ?
A
- For single instance of each resource type:
Maintain a wait for graph and invoke an algorithm that searches for a cycle in the graph - For several instances of a resource type:
Uses data structures.
Available: a vector of length M.
Allocation: n x m matrix. Defines the number of resources of each type currently allocated to each
process.
Request: n × m matrix. Indicates the current request of each process
14
Q
What are the 2 deadlock recover techniques?
A
- Terminate processes
Kill (abort) all deadlocked processes
Kill one process at a time until deadlock cycle eliminated - Pre-empt a resource from a process
15
Q
Name a problem with the termination of a process technique?
A
what if the process is in the middle of updating a file?
Aborting the process may lead to incorrect file
16
Q
Nam a problem with the pre-empt a recourse from a process technique.
A
Starvation – same process may always be picked as victim
17
Q
Define memory
A
Memory is a large array of words or bytes, each with its own address
18
Q
What is a volatile sortrage device ?
A
It loses its contents in the case of system failure.
19
Q
What 3 things are the OS responsible for when it comes to memory?
A
- Keep track of which parts of memory are being used and by whom.
- Decide which processes to load next when memory space becomes available.
- Allocate and deallocate memory.
20
Q
What is binding ?
A
mapping from one address space to another
21
Q
What are the 3 types of binding time ?
A
- Compile time:
- Load time: binding is delayed until code loaded into memory.
- Execution time: binding is delayed until run time
22
Q
What is the difference between logical and physical address space ?
A
Logical address – generated by the CPU.
Physical address – address seen by the memory unit.
Logical and physical addresses are the same in compile-time and load-time address-binding schemes.
Logical and physical addresses are different in execution-time address binding scheme.
23
Q
What is the MMU ?
A
Memory-management unit
A piece of hardware.
The run-time mapping from virtual to physical addresses is done by the MMU.
24
Q
What is dynamic loading ?
A
Routine is not loaded until it is called.
To have a better memory-space utilization.
Useful when large amounts of code are needed to handle infrequently occurring cases.
No special support from the OS is required.
25
What is dynamic linking ?
Linking is delayed until execution time.
Used for system libraries
Small piece of code, Stub, is used to locate the appropriate memory-resident library routine.
OS needs to check if the routine is in process’ memory address.
26
What is contiguous allocation
each process is in one contiguous memory location
27
What is memory fragmentation ?
2 Types:
1. External :
total memory space exists to satisfy a request, but
it is not contiguous.
2. Internal:
the
allocated memory may be slightly larger than requested memory.
28
What is compaction
Used to reduce external fragmentation
Shuffle memory contents to place all free memory together in one large block.
is possible only if relocation is dynamic, and is done at
execution time.
must determine the cost à the size of memory contents that have to be moved; the less the better.
29
What is paging ?
Another solution to the external fragmentation
may create internal fragmentation.
A process is allocated physical memory when it is available.
The physical memory is divided into fixed-sized blocks called frames.
The logical memory is divided into fixed-sized blocks called pages.
30
What is the modify bit ?
Also known as the dirty bit.
Used to to reduce overhead of page transfer
Each page is associated with a dirty bit
– When a page is modified, set its dirty bit
– Only modified pages are written back to disk
31
What is thrashing ?
each process is busy swapping pages in and
out
Thus, spending more time paging than executing
Thrashing results in severe performance problems
This occurs because:
If a process does not have enough frames, the page-fault
rate is very high. This leads to:
– Low CPU utilization
– OS thinks that it needs to increase the degree of
multiprogramming
32
Name the 2 algorithms used to reduce the effect of thrashing
1. Local:
-Only replace frames belonging to this process.
-Only slows this process down dramatically
-Slows others as well, but not as much
-Stops other processes thrashing.
2. Priority:
- Only high priority process can steal frames from low
priority processes.
- Low priority processes can be thrashing
- Low priority processes decrease speed.
33
What is demand paging ?
- Processes reside on secondary memory (usually disk).
- Bring a page (not entire process) into memory only when it is needed
```
advantages:
– Less I/O needed.
– Less memory needed.
– Faster response.
– More users.
```
-Needs hardware support to distinguish between those pages that are in memory and those pages that are on disk.
34
What is prepaging ?
When reloading a suspended process, load all the working set of pages to prevent many page faults on restart.
Problem: for some cases, many of the pages brought into memory by prepaging are not used.
35
What is virtual memory?
-separation of user logical memory from physical memory
-allows the execution of program that is only partially in memory
-advantages:
1. A program is not constrained by the amount of available
physical memory.
2. With the available physical memory, more programs can
be run at the same time.
3. Less I/O would be needed to load/swap user program
into memory à program runs faster.
36
What is the working set model ?
- Used to prevent thrashing.
- is based on the assumption of locality.
- starts by looking at how many frames a process is actually using.
- uses a parameter, , to define the working-set window
- then examine the most recent page references. The set of pages in the most recent page references is the working set .
- If a page is in active use, it will be in the working set
37
What is a locality model ?
the locality model states that, as a process executes, it moves from locality to locality. A locality is a set of pages that are actively used together
38
What is TLB ?
- Also called translation look-aside buffers
| - it is a special fast-lookup hardware cache used to solve the two memory access problem
39
What is an inverted table ?
It uses ONLY one table that has one entry for each real page of memory.
Each entry consists of the virtual address of the page stored in that real memory location, with information about the process (e.g.,PID) that owns that page.
-This scheme decreases memory needed to store each page table, but increases time needed to search the table when a page reference occurs.
40
What is a page fault ?
If the process tries to access a page that was not brought into memory? Access to a page marked invalid causes a page fault.
41
What are the 6 main steps involved in servicing a page fault ?
1. Check if reference address is valid (from internal table in PCB).
2. If invalid, terminate with an error.
3. Else, find a free frame in memory (use the free frame list).
4. Schedule a disk read operation to read the page into allocated frame.
5. After reading, modify the page table.
6. Restart instruction that was interrupted by the trap.
42
Name and describe the 3 main disc allocation methods.
1. Contiguous:
-Each file occupies a set of contiguous blocks on the disk.
-Simple
-Support sequential and direct accesses.
Disadvantages:
– How to find the best space for a new file (dynamic storage-allocation problem)
– Files can not grow.
2. Linked:
-Each file is a linked list of disk blocks.
-Allocate as needed, link together
-Each block contains a pointer to next block.
-No external fragmentation, and files can grow as long as there are free blocks.
Disadvantages:
– Efficient only for sequential accesses.
– Reliability issue: if a pointer is lost/damaged.
– 4 of 512 bytes used for pointers.
3. Indexed:
- Each file has its own index block – an array of disk block
addresses.
- It stores all pointers together in the index block.
- i-th entry in the index block points to the i-th block of the file.
- It supports dynamic access without external fragmentation, but have overhead of the index block.
43
What is a device controller ?
Basic hardware element of an OS
can support memory-mapped I/O.
the device-control registers are mapped into the address space of the processor.
The CPU executes I/O requests using the standard data-transfer instructions to read and write the device-control registers at their mapped locations in physical memory.
44
Name some advantaged of placing I/O functionality in the device controller rather then the kernal ?
-Bugs are less likely to cause an operating system crash.
-Performance can be improved by utilizing dedicated
hardware and hard-coded algorithms.
-The kernel is simplified by moving algorithms out of it.
45
Name some disadvantaged of placing I/O functionality in the device controller rather then the kernal ?
-Bugs are harder to fix - a new firmware version or new
hardware is needed.
-Improving algorithms likewise require a hardware update
rather than just a kernel or device driver update.
-Embedded algorithms could conflict with application’s
use of the device, causing decreased performance.
46
What does RAID stand for ?
Redundant array of independant disks.
47
Describe RAID level 0
Goal: to improve performance and capacity, NOT reliability.
Disks are divided into blocks.
– User and system data are distributed across all the disks in the array.
– Different requests for different blocks located in different disks can be issued in parallel.
For n-disk array, the first n logical strips are physically stored as the first strip on each of the n disks, the second n strips are distributed as the second strip on each disk and so on.
higher data transfer capacity.
0 reduces queuing time for each request; thus
higher I/O request rate.
48
Describe RAID level 1
Known as mirrored.
improves reliability by simply duplicating all the data.
When one drive fails, the data may still be accessed from the second drive.
49
Describe RAID level 2
uses parallel access technique so that all disks participate
in the execution of every I/O request.
Error-correcting code is calculated across corresponding bits on each data disk.
The number of redundant disk is proportional to the log value ofthe number of data disks.
should be used only if there are many disk errors.
50
Describe RAID level 3
similar to RAID 2, but RAID 3 requires only 1 redundant disk
Uses a parity bit to represent all drives.
employs parallel data access with data distributed in small strips.
When there is a drive failure, parity drive is accessed and data is reconstructed from the remaining devices.
Data is stripped in very small strips: very high data transfer rates; good for large transfers.
Only one I/O request can be executed at a time à does not improve I/O rate
51
Describe RAID level 4
uses relatively large data strips.
uses independent access technique.
Each member disk operates independently, thus separate I/O request can be satisfied in parallel.
Good for applications with high I/O request rates; NOT for application with high data transfer rates.
parity bits are stored in a parity disk for reliability
52
Describe RAID level 5
is similar to RAID 4, but RAID 5 distributes
the parity strips across all disks.
This avoids the potential I/O bottleneck in parity
disk found in RAID 4.
53
Describe RAID level 6
It stores extra redundant information to handle multiple disk failures
Use error correcting code instead of parity in RAID 5
Need 2 bits of redundant data for every 4 bits of data à more expensive than RAID 5
54
what are a cache and a buffer and what is the difference between them ?
Buffer is a memory area that stores data being transferred
between two devices or between a device and an application.
A cache is a part of fast memory to hold copies of data item
Buffer may hold the only existing copy of data item
Cache holds a copy of data item on a faster storage (e.g., memory) that resides elsewhere (e.g., disk).
55
What is a DMA ?
direct-memory-access controller
a special-purpose processor
To initiate a DMA transfer, the host writes a DMA command block into memory. This block contains a pointer to the source of a transfer, a pointer to the destination of the transfer, and a count of the number of bytes to be transferred.
perform transfers without the help of the main CPU
56
What are the two levels of open-file-tables?
1. Per-process table: keeps information of all open files for each process.
2. System-wide open-file-table: contains information which is process-independent
57
List some responsibilities of the OS that involve I/O management.
Free-space management.
– Storage allocation.
– Disk scheduling.
58
What is the access matrix ?
An abstract model that views protection as a matrix
```
Each row is a domain.
Each column is an object.
Each entry is a set of access rights:
access (i, j): the set of operations that a process in Domaini
can invoke on Objectj
```
59
What is a trap door ?
A hole in the software purposely left by the software’s designer that can be used only by the designer.
hard to detect, we have to analyse all the source code for all components of the system.
60
What is a logic bomb?
Security hole that is created only when a predefined condition is met.
E.g., delete all files when the system programmer is no longer employed!
61
What is a Trojan Horse ?
Code segment that misuses its environment
| Exploit mechanisms to allow programs written by some user to be executed byother users
62
What is Stack and Buffer Overflow
Some authorized user may use this for privilege escalation to gain privileges beyond those allowed for that user.
Exploits a bug in a program
Attacker can:
-Overflow an input field or input buffer until it writes into
system stack.
-Overwrite the current return address on the stack with
the exploit code loaded.
-Write a code for the next space in the stack which the
attacker wants to execute
63
What is the differences between the Confidentiality, Integrity, and Availability security violations.
Integrity: unauthorized modification of data
Confidentiality: unauthorized reading of data (information theft)
Availability: unauthorized destruction of data.
64
What are the two intrusion detection approaches ?
Signature-based: check for known behavior or patterns (signatures) that indicate attack
Anomaly detection: check for anomalous behaviors in the system
65
What is the difference between a policy and a mechanism ?
Mechanism: How it will be done.
| Policy Decide what will be done.
66
What are the 4 levels of security measures ?
Physical. Physically secure the location of the computer system against entry from intruders.
Human. Users must be screened so that the chance for authorizing a user who then gives access to an intruder is reduced
OS. It must be protected against denial of service attack, stack overflow, etc.
Network. It must be protected against data interception
67
Name some reasons for protection
1. To prevent intentional violation of access rights by bad users.
2. To prevent unintentional access by incompetence users
3. To ensure that each program in a system uses
resources consistent with the stated policies for the
uses of the resources.
4. To improve reliability by detecting latent errors at the
interfaces between component subsystems.
68
List the ways of implementing access matrix's
1. Global table:
-it consists of a set of ordered triples
-
-Large table
-It cannot be in memory, and thus requires disk I/O (virtual
memory techniques)
2. Access lists
- One list per object / column
- Each object Oj has a list of
- The list represents all domains with access rights for the OS.
- Fast as many operations will not need to search the list.
3. Capability lists:
-A capability list for a domain is a list of objects together with the operations allowed on those objects
– List of for each domain Di.
69
What is an identical resource ?
allocation of any instance of the type will satisfy process’s request.
70
What is the circular wait deadlock avoidance technique ?
deadlock-avoidance algorithm dynamically examines the
resource-allocation state to ensure that there can never be a
circular-wait condition
71
What defines a resource-allocation state
The number of available and allocated resources, and
| The maximum demands of the processes
72
What is swapping ?
A process can be swapped temporarily out of memory to a backing store, and then brought back into memory for continued execution.
Major part of swap time is transfer time
73
How does mapping protection work ?
can be done using relocation and limit registers
– Relocation register contains the value of the smallest physical address
– Limit register contains range of logical addresses – each logical address must be less
than the limit register
– The relocation-register scheme is used to protect user processes from each other, and
from accessing OS memory
– The registers are loaded by dispatcher as part of context switch
74
What are the 3 dynamic storage allocation techniques
First-fit: Allocate the first hole that is big enough.
Best-fit: Allocate the smallest hole that is big enough.
Worst-fit: Allocate the largest hole.
75
What is the Page table base register (PTBR) ?
points to the page table.
76
What is the Page table length register (PTLR) ?
shows size of the page table.
77
What is Hierarchical paging ?
each level is stored as a separate table in memory
converting a logical address to a physical one may take four memory accesses (for four-level paging system).
78
What are hashed page tables ?
Is commonly used when address spaces > 32 bits
The virtual page number is hashed into a page table.
79
what is segmentation ?
memory-management scheme that supports user view of
memory.
Each segment has a name and length; the addresses specify both the segment name and an offset.
Program specifies each address by two quantities: a segment name, and an offset (within the segment).
80
What is COW ?
Copy-on-Write (COW) allows both parent and child processes to initially share the same pages in memory.
81
What is the difference between global and local allocation ?
Global replacement:
- Process selects a replacement frame from the set of all
frames
-Disadvantage: a process cannot control its own page-fault
rate
Local replacement
– Each process selects from only its own set of allocated
frames.
– The number of frames allocated to a process does not
change.
82
What is slab allocation ?
Many type of objects in the kernel are quickly allocated and de-allocated
There is a single cache to store each unique type of kernel data structure /object
A cache consists of one or more slabs
three possible states:
1. Full – all objects in the slab are “used”
2. Empty – all objects in the slab are “free”
3. Partial – some objects in the slab are “free” some others are “used”
Advantage
- No internal fragmentation
- Fast memory allocation / de-allocation
83
What is the difference between sequential and direct access ?
Sequential access:
Information in the file is processed in order, one record after the other.
Direct access (relative access):
A file is made up of fixed-length logical records that allow
programs to read and write records in no particular order.
Based on disk model à allow random access to any file block,
