OS General Concepts Interview Preparation Guide

Mutual Exclusion: Only one process may use a critical
resource at a time.
Hold & Wait: A process may be allocated some resources
while waiting for others.
No Pre-emption: No resource can be forcible removed from a
process holding it.
Circular Wait: A closed chain of processes exist such that
each process holds at least one resource needed by another
process in the chain.

Belady's anomaly is in context with the page faults occurring in FIFO page replacement policy. It says that on increasing the number of page frames, the no. of page faults do not necessarily decrease, they may also increase. LRU page replacement algorithm is free from Belady's anomaly.

It is a useful, memory-saving technique for multiprogrammed
timesharing systems. A Reentrant Procedure is one in which
multiple users can share a single copy of a program during
the same period. Reentrancy has 2 key aspects: The program
code cannot modify itself, and the local data for each user
process must be stored separately. Thus, the permanent part
is the code, and the temporary part is the pointer back to
the calling program and local variables used by that
program. Each execution instance is called activation. It
executes the code in the permanent part, but has its own
copy of local variables/parameters. The temporary part
associated with each activation is the activation record.
Generally, the activation record is kept on the stack.

diskcopy

divide program's logical address space in to segmwnts.
each segment will have a page table....each segment pointer
points to page table

demand paging:- not all of a process's virtual address space
needs to be loaded in main memory at any given time. Each
page can be either:
o In memory (physical page frame)
o On disk (backing store)
loading the page into the memory from disk when required is
called as demand paging

page faults:-when a process references a page that is in the
backing store,the page fault occurs

replacement algorithms:-various approaches to replace pages
from disk to memory on occurence of page fault

* Page fetching: when to bring pages into memory.
* Page replacement: which pages to throw out of memory.

Page Replacement

* Once all of memory is in use, will need to throw out
one page each time there is a page fault.
* Random: pick any page at random (works surprisingly well!)
* FIFO: throw out the page that has been in memory longest.
* MIN: The optimal algorithm requires us to predict the
future.
* Least Recently Used (LRU): use the past to predict the
future.
* Strange but true: for some placement policies, such as
FIFO, adding more memory can sometimes cause paging
performance to get worse. This is called "Belady's Anomaly"
after Les Belady, who was the first person to notice it.
* Implementing LRU: need hardware support to keep track
of which pages have been used recently.
o Perfect LRU?
+ Keep a register for each page, store
system clock into that register on each memory reference.
+ To choose page for placement, scan through
all pages to find the one with the oldest clock.
+ Hardware costs would have been prohibitive
in the early days of paging; also, expensive to scan all
pages during replacement.
o In practice nobody implements perfect LRU.
Instead, we settle for an approximation that is efficient.
Just find an old page, not necessarily the oldest.
* Clock algorithm (called second chance algorithm in
Silberschatz et al.): keep reference bit for each page
frame, hardware sets the reference bit whenever a page is
read or written. To choose page for placement:
o Start with FIFO approach: cycle through pages in
order circularly.
o If the next page has been referenced, then don't
replace it; just clear the reference bit and continue to the
next page.
o If the page has not been referenced since the
last time we checked it, then replace that page.
* Dirty bit: one bit for each page frame, set by
hardware whenever the page is modified. If a dirty page is
replaced, it must be written to disk before its page frame
is reused.
* The clock algorithm typically gives additional
preference to dirty pages. For example, if the reference but
for a page is clear, but the dirty bit is set, don't replace
this page now, but clear the dirty bit and start writing the
page to disk.
* Free page pool: some systems keep a small list of
clean pages that are available immediately for replacement.
o During replacement, take the page that has been
in the free pool the longest, then run the replacement
algorithm to add a new page to the free pool.
o Pages in the free pool have their exists bit
off, so any references to those pages cause a page fault
o If a page fault occurs for a page in the free
pool, remove it from the free pool and put it back in
service; much faster than reading from disk.
o Provides an extra opportunity for recovery if we
make a poor page replacement decision.



Usually thrashing refers to two or more processes accessing
a shared resource repeatedly such that serious system
performance degradation occurs because the system is
spending a disproportionate amount of time just accessing
the shared resource. Resource access time may generally be
considered as wasted, since it does not contribute to the
advancement of any process. This is often the case when a
CPU can process more information than can be held in
available RAM; consequently the system spends more time
preparing to execute instructions than actually executing them.

PRIMARY MEMORY STORES THE DATA TEMPORARY.FOR EXAMPLE
RAM,ROM.BUT SECONDARY MEMORY STORES THE DATA PERMANENTLY
TILL WE REQUIRE.

Syntax phase sheduler deals with the problem of deciding
which of the process in ready queue is to allocate the CPU
time for processing.

The purpose of the lexical analyzer is to partition the input text, delivering a sequence of comments and basic symbols. Comments are character sequences to be ignored, while basic symbols are character sequences that correspond to terminal symbols of the grammar defining the phrase structure of the input

when ever a program is to be compiled the syntax is
necessary and we wont receive the output until a correct
syntax is written
it shows the errors so debugging becomes easier
the best example is C language

where as in interpreter if we miss any syntax it violates
that particular line and goes to the next line
in this case we may or may not get the required output
it does not show any errors even though its violates the syntax
the best example is HTML