Flashcards

Operating Systems Revision

ChristosD English 48 cards

Cards in this deck (48)

1What is an OS?An OS is a program that:
1) manages the computer hardware.
2) provides the basis on which application programs can be built and run.
3) acts as an intermediary between the user and the hardware.
2What are the 4 main functions of an OS?1) Extended Virtual Machine
2) Resource Management
3) Control
4) Protect applications from each other
3System CallAn assembly language instruction that causes a jump into the kernel, e.g.:
1) Process Control
2) Communications
3) Device Manipulation
4Asymmetric multiprocessingA master CPU controls the system, and runs key kernel
tasks.
 Other CPUs do what the master tells them.
5Symmetric multiprocessing (SMP)All CPUs are equal; each runs kernel tasks, and communicate with each other as needed.
6Asymmetric clusteringone node runs application, others provide a hot standby.
7Symmetric clusteringall nodes run parts of the application.
8Program Status Word (PSW)Contains:
1) Condition Code Bits (set by various comparison instructions)
2) CPU Priority
modes:
1) User-mode: only a subset of instructions and features are accessible
2) kernel-mode: all instructions and features are accessible
9RelocationIn relocation, the program thinks that it has the entire address space when in actuality it has a limited subset. Hence, we need to map the virtual address space that the program has with the physical one. This is done by the Memory Management Unit (MMU).
10Context SwitchThe switch from one user program to another or the user program to the OS.
11OS procedure when Context Switching Save the PC, Stack Pointer, PSW.
 Save the contents of the registers.
 Reprogram the MMU registers.
 Wait while the instructions in the CPU pipeline are trashed.
 Wait for cache lines to load from new program’s memory.
12DaemonsProcesses that perform background tasks and are not associated with individual users.
13Process CreationAll processes except the kernel are started by a pre-existing process.
14fork()A UNIX system call that clones an existing process. If the pID is 0 then it is the child process. Otherwise it is the parent.
15execve()A UNIX system call that replaces current program with a new one.
16Process Termination1) Normal Exit - Process finished what it set out to do or the user stopped it.
2) Error - The process discovers a fatal error and terminates itself.
3) Fatal Error - Process did something illegal and exits unexpectedly.
4) Killed by Another Process - A process with sufficient permission kills another process.
173 Process States1) Running - Currently using CPU
2) Ready - Runnable, but stopped to let another process run
3) Blocked - Unable to run until some external event occurs
18Process State: Running -> BlockedProcess discovers it cannot run right now, e.g. Process reads from a pipe and there is no data currently available.
19Process State: Blocked -> ReadyThe external event that the process was waiting for occurs, e.g. Data arrives from pipe, enabling a read to occur.
20Process State: Running -> Ready, Ready -> RunningCaused by process scheduler because:
1) Scheduler decides process has had enough time, and decides to let another process run now.
2) Difficult to balance the competing demands of many different processes, some interactive, some not.
A Clock Interrupt occurs to make the transition.
21Thread StacksEach thread has its own stack:
Stores local variables.
Keeps track of where a function should return to.
22SchedulingThe task of deciding which process to run next is called scheduling, and is performed by the scheduler.
23Ready QueueProcesses in ready state are kept on an ordered list, the ready queue:
generally implemented as a linked list (of PCBs) with head & tail pointers
Kept ordered -- order depends on scheduling alg. but next to run is at head.
24Types of Schedulers?Non-preemptive: a process is allowed to run until it blocks on I/O (however long that takes).
Preemptive: a process is only run for a certain length of time. After that another process is selected to run.
25First-Come First-Served Scheduling AlgorithmsSimple FIFO job queue.
 Process at head of queue runs until it blocks.
 When it unblocks, rejoins tail of queue.
26Convoy effectMix of CPU and I/O bound processing causes I/O bound job to be interspersed with long CPU-bound bursts. During these bursts, I/O device is mostly idle.
27Shortest Job FirstNon-preemptive algorithm for when run-times are known in advance.
Run job with shortest run time first.
28Shortest Remaining Time NextPreemptive version of Shortest Job First.
Always run the job whose remaining run time is the least.
29Batch System Scheduling: Three Level SchedulingAdmission Scheduler: takes jobs from the input queue. Goal: good balance of CPU and I/O bound jobs. Long timescale.
Memory Scheduler: manages swapping from disk, so as to effectively use CPU, memory and I/O. Medium Timescale (once per second)
CPU Scheduler: decides which job in memory to run. Short Timescale.
30Round Robin1) Maintain a queue of runnable processes.
2) Assign each process a time interval or quantum.
3) Run process from head of queue.
4) If process is still running at the end of its quantum, de-schedule it, and move it to the end of the queue.
31Multilevel FeedbackMove processes between queues
e.g. based on how much CPU they are using.
If process exceeds quantum, then sink a level.
32Interactive Systems Scheduling: Shortest Process NextAdaptation of Shortest Job First for Interactive Systems.
1) Run job with shortest expected run time for the next user “command”.
2) Estimate run time based on new measurement and aged past history.
33Real-Time Systems Hard Real-Time:
there are guarantees that must be met.
 Soft Real-Time:
deadlines should be met, but no hard guarantee.
34What is Swapping in memory management?ﰀ A process must be in memory to be executed.
ﰀ When it’s not being executed, it can be temporarily swapped out of disk in its entirety.
ﰁGoal is to maintain enough processes in memory to keep the CPU utilised effectively.
ﰁNot to swap too often - execution time must be long relative to swap time.
ﰀ Need to be certain no I/O operations in progress at time swap out occurs.
35Memory Allocation AlgorithmsFirst Fit: Scan the free list until the first hole is found that is large enough to fit the process to be swapped in.
Best Fit: Scan the entire list and find the smallest hole that will fit the process to be swapped in. The problem is that it leaves lots of small unusable holes.
Worst Fit: Use the largest available hole. Shown to be worse than best fit or first fit.
36Virtual Memoryﰀ Combined size of a program, its stack, and data may exceed available physical memory. So, Only the parts currently needed are kept in real memory. ﰁThe rest are kept on disk.
37Pages, Page Frames, Page TableVirtual Memory is divided up into pages.
ﰀ
Physical Memory is divided into page frames, which hold pages when they’re loaded into memory.
The page table holds the mapping between the two.
38Translation Lookaside BufferA TLB is a hardware cache in the MMU of recently used page table entries. Lookup is done in parallel using associative memory. Only if TLB misses is full page table in memory consulted.
39Page Replacement Algorithms1) Not Recently Used: Each page has reference bit and modified bit. Reference bit is cleared each clock tick. NRU removes a page at random from the lowest numbered non empty class.
2) FIFO: Maintain a linked list of all pages in the order they came into memory. The page at the beginning of the list is replaced.
3) Second Chance: Simple modification of FIFO algorithm. When page fault occurs:
(a) If first page in FIFO has reference bit clear, it is evicted.
(b) If first page in FIFO has reference bit set, it is moved to the end of the list.
4) Clock: When a page fault occurs, the page that the clock hand point to is inspected:
(a) If page has reference bit clear, it is evicted.
(b) If reference bit set, it is cleared and the hand advances.
5) Least Recently Used: Assume pages used recently will used again soon. Throws out page that has been unused for longest time.
6) Working Set Algorithm: The working set is the set of pages used by the k most recent memory references.
40Page Replacement Algorithms 26) Working Set Algorithm: The working set is the set of pages used by the k most recent memory references.
7)WSClock: Like clock, but also store last use time.
41Demand-PagingLetting a page fault cause each page to be loaded as it’s needed.
42Master Boot Record's (MBR) jobMBR program’s job is to locate the active partition, read in the first block from it (the Boot Block) and execute it.
43Journalling FileSystem DefinitionA journaling filesystem is a filesystem that maintains a special file called a journal that is used to repair any inconsistencies that occur as the result of an improper shutdown of a computer.
44RAID 0 - Block StripingData is fragmented or broken up into blocks and alternated/striped among the drives.
45RAID 1 - Disk MirroringMakes 2 or more drives mirror images of each other.
Complete redundancy, does not improve performance.
46RAID 5 – Disk Striping with ParityRAID 5 consists of block-level striping with distributed parity, i.e. parity information is distributed among the drives. It requires that all drives but one be present to operate. Upon failure of a single drive, subsequent reads can be calculated from the distributed parity such that no data is lost. RAID 5 requires at least three disks.
47I/O Mechanisms1) Programmed I/O:
48ARPAddress Resolution Protocol which determines which ethernet address to put in a packet for an IP address.

Information

Description: Flashcards on Operating Systems Revision, created by ChristosD on 20/04/2015.
Created by: ChristosD
Views: 6
Rating