Operating System Chapterwise Notes of Galvin

Here we are giving chapter wise notes of operating system based on operating system concepts by galvin





these are listed under the fallowing headings::-






Introduction

Computer System Stuctures

O S Structures

CPU Scheduling

Memory

Process

Treads

Virtual Memory

Read rest of entry

Operating System Chapterwise Notes of Galvin:Virtual Memory

Pages>> 1 2 3 4 5 6 7 8
Here we are giving chapter wise notes of operating system based on operating system concepts by galvin

Virtual Memory

q) how virtual memory is different from other memory management techniques?
a) it allows the execution of the process that need not be comletely in memory.

q) what are its advantages?
a) the process may be larger than the physical memory.allows processes to easily share files and address space.

note:- entire program is not needed always, onlysometimes:-
1) code that handles exceptions.
2) arrays ,lists,tables are often allocated more memory, than actually needed.

benefits of keeping in memory only the required instructins and data:-
1) more programs can be there in memory, more cpu uilization and throughput.
2) less I/O required to load or swap the processes.

note:- systems that support virtual memory, donot bother programmer to design overlays.

q) what is key concept behind virtual memory?
a) demand paging. demand segmentation can also be used, but segment replacement algorithms are very complex as they have variable sizes.

note:- here we can use pager instead of swapper.now a process needs to be in memory ,before its execution starts.but now instead of bringing all pages into memory, pager does not bring a page unless it is required.in begining pager makes a guess,which pages will be used and loads only those pages into memory, thus decreasing the swap time, and memory needed.

q) how we modify page table to know that which pages are in memory and which are not?
a) help of valid-invalid bit is taken.if a bit is valid, it means it is in logical address space and also is present in memory, if its invalid , it means either the page in not a valid logical address or right now its on disk and not in memory.

note:- page table entry for page on disk , contains invalid bit, or address of page on disk.

q) what is page - fault trap?
a) access to page that is currently not in memory is called page-fault.mapping hardware then sends trap to the o.s.

q) what is pure demand paging?
a) this concept says that never bring a page into memory until it is required.a process could start with no page in the memory.

q) what is swap space?
a) the portion of disk that contains the pages not in memory.

note:- if a page fault occurs when fetching a instruction , it needs to be fetched again. if page fault occurs when fetching an operand, then fetch and decode of instruction need to be done again.

note:-trying to increase degree of multiprogramming can increase the page fault rate.

q) what is modify/dirty bit?
a) when a page fault occurs and no free frame is there, we need to swap out a victim page and bring in the desired page.this takes double time to service page fault ie swapin+swapout. to reduce it we use modify bit.it is attached to each frame in physical memory. if frame is modified it is set. in this case it needs to be written back to memory. but if not changed only we swap in desired page overwritting it.read only pages help a lot in reducing the page fault service time, if they are the victims.

q) what do frame allocation algorithms do?
a) decide how many frames are to be allocated to a process.it also has a lot of affect on the page fault rate.

q) what is refernce string?
a) the string of memory references is called reference string.

q) how to implement FIFO page replacement algorithm?
a) way1) with each page in memory associate the time, when it came in, then remove the oldest page.
way2) make a FIFO queue of pages and remove 1 at the head.

q) what is belady's anomaly?
a) FIFO(some others are also there) suffers from belady's anomaly. here the number of page faults increase even with allocation of more frames to the process.

note:- of all the page replacement algorithms OPR has least page fault, though not practically possible.

q) what is logic of OPR?
a) remove the page that will not be used for the longest period of time.

q) what is logic of LRU?
a) here the page that has not been used for a long period of time is replaced. it is approximation to OPR.with each page its time of last use is attached.

q) implementation of LRU?
a) 1) counters:- with each page we have time-of-use field and we add to cpu a clock or counter, which is incremented for each memory reference.contents are copied to the referenced page.here we need to search page with least count. here we write to memory, and also counter is to be maintained to prevent overflow.

2) stack:- stack of page numbers. a page when referenced is moved to the top of stack.tail pointer points to LRU page easy to implement using doubly linked list.

note:- OPT and LRU donot suffer from belady's anomaly.

q) what are stack algorithms?
a) these never exhibit belady's anomaly.these are algorithms for which the set of pages in memory for n frames is always the subset of set of pages for n+1 frames.

note:- these algorithms slow down the process execution as for each memory reference , there is a need to update the timer or stack structures.

q) what are referenece bits?
a) its a technique used to assist LRU. with each page we associate a reference bit.initially all bits are cleared to 0 by O.s when it is referenced the hardware sets it to 1. so we can know which pages have been used and which have not been.

q) what additional feature added to reference bit?
a) now with each page a byte is attached ie 8 bits.it stores history.every interval(set by hardware), the refernce bit is set to high order bit, and all other bits are moved 1 postion right. smallest number is LRU.if same value FIFO is used.

q) what is 2nd chance alghorithm?
a) here only 1 refrence bit is used. if page is to be replaced it's reference bit is examined.if 0 it is replaced.if not, then it gets a 2nd chance ie bit is cleared and arrival time is set to current time, and moves further. it can also be implemented using the circular queue,where page with 0 reference bit is searched. if all are set, it acts as FIFO.

note:- we can also enhance the 2nd chance algorithm by using modify bit also along with. now we get 3 classes here:-
(0,0),(0,1),(1,0),(1,1).
case 1 : neither recently used nor modified- best page to replaced.
case 2 : not recently used but modified - not quite as good, page need to be written out on the disk before replacement
case 3 : recently used but not modified - probably will be used again soon
case 4 : recently used and modified - probably will be used again soon.

q) what are counting based page replacement algorithms?
a) here for each page , count the number of refernces made to it.
2 types are there:-
1) LFU:- page with low count is removed.
disadvantage:- a page that was used heavily in begining, but not needed now remains in memory.

2) MFU:-it argues that page with small count has just been brought in , and yet to be used.

note:- the minimum number of frames to be allocated to a process is also determined by the instruction -set architecture.ie enough pages must be there that the single instruction can reference.

note:- limit has been put on the levels of indirection to support virtual memory in context of minimum number of frames to be allocated to a process.

q) what is meant by equal allocation?
a) if we have m free frames and n processese, give each process m/n frames.

q) what is proportional allocation?
a) here we allocate number of frames to each process as s(i)/S *m; where S is total sum of virtual memory for each process. s(i) virtual memory for individual.

note:- we also need to consider the priority of the process while allocating frames rather than size.

q) what is global replacement and local replacement?
a) global replacement allows to select replacement frame from all frames even allocated to other processes.local replacement requires each process select replacement frame from its own set of allocated frames.

note:- higher priority process can select replacement frame from its own set or from lower proirity processes.

q) what is disadvantage of global page replacement?
a) a process cannot control its page faults.

note:- if number of frames allocated to a process fall below the minimum required by computer architecture, then process need to be swapped out completely.

q) what is thrashing?
a) its high paging activity, where process spend more time paging than execution.

note:- thrashing occurs because of over multiprogramming and global replacment.all processes are in pager device queue than ready queue.

q) how to prevent thrashing?
a) by allocating the process the number of frames it need. for this we use the locality model of process execution.

q) what is locality?
a)it is set of pages that are used together.program structure defines locality. eg:- a procedure its instructions,variables global variables form a locality.

note:- if fewer frames than its locality are assigned then the process will thrash.

Pages>> 1 2 3 4 5 6 7 8

Read rest of entry

Operating System Chapterwise Notes of Galvin:Threads

Pages>> 1 2 3 4 5 6 7 8
Here we are giving chapter wise notes of operating system based on operating system concepts by galvin


q) what is a thread?
a) it is a lightweight process, a basic unit of cpu utilization. it contains a thread id,program counter,register set and
stack.

q) what do a thread share with other threads of same process?
a) code section and data section.

note:- if a process has more than 1 thread it can do more than 1 task at a time.

q) give example of application with multiple threads?
a) web browser:- 1 thread display images ot text while other retrieves data from network.
word processor:- display graphics,read keystrokes and third one perform grammar and spelling check.

q) what are 2 kinds of threads?
a) 1) user threads and 2) kernel threads.

q) how are user thread implemented?
a) thread libraray.library gives support for thread creation, scheduling and management with nO help from kernel.

q) what is many to one model of threads?
a) there are many user-level threads but only 1 kernel thread.eg:- green threads(a thread library) for Solaris2.

q) what is 1-1 model?
a) each user thread is mapped to a kernel thread.here a user thread creation requires a corresponding kernel thread also.
there is a restriction on the number of threads suported by system. windows nt,2000 use this model.

q) what is a many-many model?
a) many user-level threads mapped to smaller or equal number of kernel threads.

q) how many kernel threads we can have in many-many model?
a) depends either on the particular application or a particular machine.

q) in case of multithreaded program, how can a fork behave?
a) 1) IT DUPLICATES all threads of its parent.
2) it is single threaded.

q) what is thread cancellation?
a) it is the task of terminating a thread before its completion.

q) any example of thread cancellation?
a) 1) if multiple threads are searching through database and 1 returns the result,remaining are cancelled.
2) if u click stop button in web browser,it stops web page from loading any further.
the thread that is to be cancelled is called the target thread.

q) what are 2 different kinds of thread cancellation?
a) 1) asynchronuos:- one thread immidiately terminates the target thread.
2) deffered:- target thread checks itself periodically to check if it should terminate.

q) what is difficulty in cancellation?
a) in situations where resources have been allocated to the cancelled thread, or if thread is cancelled in middle of
updating data it is sharing with other threads. in case of asynchronous cancellation it may occur that o.s is not able to
reclaim all resources from the thread.

q) what is signal used for ?
a) used in unix systems to notify a process that a particular event has occured. it may be recieved synchronously or
asynchronously depending on source and reason for event being signalled.

q) tell about synchronous signal?
a) it occurs when illegal memory access is there or division by 0 takes place.synchronous are delived to same process that
performed the operation causing signal.

note:- asynchronous signal is sent to other process.

q) what are various signal handlers?
a) 1) default signal handler.
2) user-defined -do-.

note:- take example of web server. it creates a new thread when a new request comes to it.if more requests are there, then
more threads may exhaust the system resources.to solve this we have thread pool.

q) what is concept of thread pool?
a) at time of process startup, create a number of threads and place them in pool to wait for work.they finish work and then
come back to pool. if request come and no thread is available, then request has to wait.

q) what is thread specific data?
a) each thread share data of process, but sometimes it may need its own copy of data. such data is called thread specific
data.

q) what are Pthreads?
a) it refers to a POSIX standard defining an API for thread creation and synchonization. it is specification for thread
behaviour not its implementation. o.s developer can use these specifications in any way he likes.generally libraries
implementing Pthreads are confined to the unix-based system like Solaris2.

Pages>> 1 2 3 4 5 6 7 8

Read rest of entry

Operating System Chapterwise Notes of Galvin:Process

Pages>> 1 2 3 4 5 6 7 8
Here we are giving chapter wise notes of operating system based on operating system concepts by galvin

PROCESS


q) what is a process?
a) a program in execution.

q) what is difference b/w the program and process?
a) program is passive entity,such as contents of file on disk. whereas process is a active entity, with program counter
indicating next instruction to be executed, and has set of associated resources.

q) how many states can a process be in?
a) 1)new 2)running 3)waiting 4)ready 5)terminated.

q) what is process control block?
a) each process in o.s is represented by process control block. it contains all information related to process. it contains:-
1) process state
2) program counter
3) cpu registers:- state of process is saved
4) cpu scheduling information:- process priority, pointers to scheduling queues.
5) memory management information:- limit and base registers, page tables.
6) accounting information:- amount of cpu and real time used.
7) i/o status information:- list of i/o devices allocated and list of open files.

q) what is ready queue?
a) processes that are in memory and are ready and are waiting to get executed are kept on list called ready queue, generally
implemented as linked list.

q) what is there in the ready queue?
a) process control blocks.

note:- there is device queue also for each device.

q) what is queueing daigram?
a) it is used to represent process scheduling,ie rectangles for queues,circles for resources etc.

q) how many types of schedulers are there?
a) in batch system, more processes are submitted than can be executed. they are spooled to disk. now we have long-term-
scheduler that selects process from the pool and load into memory. cpu or short-term scheduler selects process from memory
to be given cpu.cpu scheduler needs to take decision fast.

q) when is long term scheduler invoked?
a) when a process leaves the system.

note:- long-term scheduler must send proper mix of i/o bound and cpu bound processes to the memory.

q) which systems donot have long term scheduler?
a) time sharing systems like unix. new process is put in memory for cpu scheduler.

q) what is medium level scheduler?
a) it brings in the concept of swapping.

q) what is context switch?
a) to switch cpu to another process, needs saving state of old process and loading saved state of new process.

q) what is system call to create a new process?
a) create-process.

note:- child processes may get different resouces from its parent process or they may share resources.

q) in unix , how to create new process?
a) each process has a pid, and new process are created by fork system call.

q) what are types of concurrent processes in the system?
a) they may be independent(do not share data) or may be cooperating(share data).

q) why process cooperation is needed?
a) 1) information sharing:- shared file.
2) computation speed up:- task broken into subtasks.here we need multiple processing elements.
3) modularity

q) give examples of the producer consumer problem?
a) print program produce characters to be used by printer driver.compiler produces assembly code for assembler.

note:- a synchonization is required between producer and consumer. a buffer is required in between shared by both.

q) where do we get buffer from?
a) may programmer need to code it , or provided by o.s through use of IPC facility.

q) what is IPC?
a) it is inter process communication facility. it allows processes to communicate without sharing same address space.it is
mostly used in distributed systems. it is provided by message passing system. ex: chat program on WWW.

q) where is message passing used in computer?
a) in b/w micro kernels.

q) what operations do IPC provide?
a) at least 2 ie send(message) and recieve(message).

q) what is direct communication?
a) here we have:-
1) send(P,message):- send a message to process P.
2) recieve(Q,message):- receive a message from process Q.

q) what is indirect communication?
a) here messages are sent to and recieved from mailboxes,or ports.2 processes need to share a mailbox. it works as:-
1) send(A,message):- send a message to mailbox A.
2) recieve(A,message):- receive a message from mailbox A.

note:- mailbox can be owned by a process or by operating system.in second case o.s allows processes to create,send and
recieve and then delete a mailbox.

q) how many ways of message passing?
a) it can be blocking and non-blocking, also called as synchronous and asynchronous. it can be:-
1) blocking send
2) non blocking send
3) blocking recieve
4) non blocking recieve


q) what is rendezvous?
a) when both send and recieve are blocking ,then there is rendezvous b/w sender and reciever.

q) what is buffering here?
a) messages exchanged b/w processes reside in temporary queue. this queue can be implemented in 3 ways:-
1) 0 capacity:- no message should wait,so sender need to get blocked till recipient recieves.
2) bounded capacity:- sender need to block if queue is full.
3) unbounded capacity:- sender never blocks.

q) what is socket?
a) it is defined as end point for communication. processes communicating over network employ it.it is made up of IP address
concatenated with port number.
in genaral sockets use client-server architecture.

q) what are the ports that server listens to provide certain services?
a) telnet server listens to port 23
ftp server listens to port 21
http server listens to port 80.

note:- all ports below 1024 are used for standard services.

q) when a client process request for connection, what happens?
a) it is assigned port number >1024 by host computer. then connection will cosist of pair of sockets. then packets travel .
b/w client and server.

note:- processes on same host, when try to get connected to same server ,it would be given unique port number. all
connections must be unique.

q) how many types of sockets , java provide?
a) 3 types:-
1) connection oriented(TCP) :- implemented with Socket class.
2) connectionless(UDP) sockets use DatagramSocket class.
3) MulticastSocket class allows data to be sent to multiple recipients.

q) what is a thread?
a) it is also called light weight process. it consist of thread id,program counter,register set. it shares with other
threads belonging to same process code,data section and other o.s resources. traditional heavy weight process has single
thread of control. if a process has multiple threads,it can do more than 1 task at a time.

q) give an example of thread?
a) a word processor may have a thread for displaying graphics, another for reading keystrokes, third for performing
spelling and grammar check.they also play an important role in remote procedure calls(RPC).

note:- instead of process creation on web server to handle a client a thread is created to service request.


Pages>> 1 2 3 4 5 6 7 8

Read rest of entry

Operating System Chapterwise Notes of Galvin:Memory

Pages>> 1 2 3 4 5 6 7 8
Here we are giving chapter wise notes of operating system based on operating system concepts by galvin

MEMORY

q) on what do scheme for memory management depends?
a) hardware.

note:- memory can be viewed as the large array of bytes , each having an address.

q) what is the input queue?
a) collection of processes on the disk , waiting to be brought into the memory for execution , forms the input queue.

note:- compiler maps the symbolic address of the program into the relocatable address.loader convert it into physical address

q) different types of binding of instructions and data to memory address?
a) 1) compile time:- if we know at compile time where the program will reside in memory.if location changes, we need to
recompile it. eg:- MS-DOS .COM -format programs use this technique.
2) load time:-
3) execution time:- if process is to be moved in memory during execution time,run time binding is used.

q) what is logical address space and the physical address space?
a) address generated by cpu is logical address and address seen by memory is physical address. set of addresses is called
address space.

note:- in case of compile time and load time binding , the logical address and physical address are the same, whereas in
run time they are not.

q) what is memory management unit?
a) run time logical to physical address mapping is done by MMU.

q) what is concept of dynamic loading?
a) here the routinue is not loaded into memory until it is called.only main program is loaded.after call, routinue is loaded
and program's address table is also updated.to take advantage of this concept, programmer has to take proper care,not the
responsibilty of the O.S.

q) what is there in linking?
a) here the other modules and system libraries are included into the program image.

q) what is dynamic linking?
a) here all the system libraries or atleast the routines referenced in them are linked only when call is made at run time.

q) what is a stub?
a) it is used to support the dynamic linking.it is included for each library routine reference.it is a small piece of code,
that tells how to locate the library-routine in memory or how to load if routine not present.
** its advantage is that all the processes use only 1 copy of the routine.

q) what is concept of overlays?
a) it enables the process to be larger than the memory allocated to it. only required instructions and data are to be kept in the
memory. when other instructions are needed , they are brought in place of previous data, no longer needed.
eg:- 2 pass assembler.

note:- an overlay driver is used that reads code into memory.it also is responsibility of programmer to take advantage of
this concept.programmer only designs the overlay, o.s only do I/O here.

q) what is swapping?
a) it is process of shifting a process to backing store(swap out), and bringing a process to memory(swap in).

q) what is rollin and roll out?
a) it is variant of swapin and swap out. it is done when a higher priority process wants to come into the memory.

q) do a process swapped out , needs to be swapped in , in the same location?
a) in case of compiletime and loadtime binding---yes, but not in case of run time address binding.

q) when a process can't be swapped out?
a) if it's not idle.if a process is waiting for the I/O ,and I/O is asynchronously accessing the user memory for I/O buffers,
then it can't be swapped out.

**** in case of contigous memory allocation:-

note:- memory divided into 2 parts:-
1) o.s 2) user programs.

q) how to provide memory protection?
a) using a relocation and limit register.

note:- logical address is first compared with the limit register.

q) what is transient operating -system code?
a) o.s contains code and buffer space for devicedrivers. if device driver not commonly used,no need to keep the code and
data in memeory. such code that comes and goes as needed is called transient o.s.

q) what is MFT?
a) it is multiprogramming with fixed number of tasks. here the memory is divided into fixed sized of partitions. in 1
partition 1 process can reside at a time.it was used by IBM OS/360, now not in use.

q) what is MVT?
a) it is multiprogramming with variable number of tasks.primarily used in batch environment.

q) how MVT is implemented?
a) OS maintains a table indicating which parts of memory are free and which are allocated.

q) what is a hole?
a) free part of memory is called a hole.

q) how dynamic storage allocation problem solved?
a) it relates to how to satisfy the request of size n from the available holes.many strategies are there:- first fit, best
fit,worst fit.

q) what is the disadvantage of these algorithms above?
a) they suffer from external fragmentation.

q) what is external fragmentation?
a) it exists when we have total free memory to accomodate a process, but it is not contiguous.

q) what is internal fragmentation?
a) when physical memory is broken into fixed sized partitions.here the process may be smaller than the size of the partition.
so rest of space in partition is wasted. it is called internal fragmentation.

q) what is compaction?
a) it is one of the solution to the external fragmentation.here the free memory is moved to one part and all pragrams and
data on other side. this can be done if address binding is done at run time. it involves a lot of cost also.

note:- other solution to external fragmentation is paging and segmantation(here program need not to be in contiguous memory)

q) what is paging?
a) it allows the physical address space of the process to be non-contiguous. earlier when processes used to be swapped out
we need to search for free space on disk(backing store) too. so, external fragmantation on disk also occured.

q) concept of paging?
a) physical memory is broken into fixed sise blocks called frames.logical memory is broken into pages of same size of frames.
backing store is also divided into the blocks of size of frames.
when a process is to be loaded , its pages must be loaded into the frames.

q) now how cpu generates address?
a) now address has 2 parts:- p and d. p is the index into the page table, from where we get the frame number, which combines
with d part to form physical address.

q) how to decide how many bits for p and d?
a) page size is defined by hardware.this size is generally the power of 2.if size of logical address space is pow(2,m) and
the page size is pow(2,n), then higher order m-n bits will tell the page number and the n lower order bits will tell the
page offset.

note:- in paging we dont have external fragmentation, but we do have internal fragmentation.

q) so, can we have small page size to reduce the internal fragmentation?
a) but then the page table will grow in size , and overhead to maintian will increase.also with smaller page size disk I/O
will not be efficient.

note:- when a process arrives in the system , its size in pages is expressed.

q) what is frame table?
a) it is a table maintained by the O.s, which has 1 entry for each frame of physical memory.it tells whether a frame is free
or not, if not, then to which process it is allocated.

note:- a system call is made,suppose for I/O, then buffer address is passed as the parameter.

note:- for each process there is a page table.

q) do paging increase context switch time?
a) yes, because dispatcher has also to define hardware page table.

note:- the page table pointer is also stored in the process control block.

q) how to implement page table?
a) way 1) use of dedicated set of registers:- dispatcher needs to load these registers , in context switch.
this method is not feasible if page table has millions of entries.
way 2) here we store the page table in the main memory and PTBR stores its address.here context switch time is less
but here to make a access in memory , 2 memory accesses are required.

q) what is TLB(translation look-aside buffer)?
a) it is a high speed associative memory, with 2 fields tag and value.upto 60 to 1024 entries it can handle.it will contain
only few of the page table entries.

q) what if a search in TLB makes a miss?
a) then the reference to memory page table is made.the new entry is also added to the TLB. if no entry free, 1 need to be
replaced.

q) what do u mean that some entries in TLB are wired down?
a) it means that they cannot be removed from there.entries for kernel code are wired down.

q) what are protection bits?
a) they are stored into the page table only and they indicate during address mapping, that the particular page is read-write
or read-only.

q) what is valid-invalid bit?
a) it is 1 more bit attached to the page table entry.valid bit indicates that this page is in process's logical address space
and thus legal, and invalid bit indicates that the page is not in the logical address space of the process.they cause trap to
O.S.

note:- advantage of paging is sharing common code.it can be done by setting entry in the page table.

q) what is reentrant code?
a) that never changes during the execution. eg:- code of a text editor.it can be executed by more processes at same time.

q) name some programs that can be shared?
a) compilers,database-systems, run-time libraraies,etc. code shared must be reentrant.

q) what is segmentation?
a) here the user view of memory is as the collection of various segments.each segment has a name and length.the address here
consists of the segment number and the offset.
.

note:- when a user program is compiled, the compiler itself constructs various segments.

q) who does mapping here?
a) segmenation table, each entry here has base and limit of segment. here logical address has 2 parts , segment number and
offset, offset is compared against the segment limit.

q) what are advantages of segmentation?
a)1) main, functions,procedures, global variables,stacks,arrays,tables etc are various segments.because of segment containing
entries of same type,protection can be easily provided.
2) sharng of code and data can be done. only need to change process's segment table.

note:- in case of segmentation, the care must be taken while sharing the code segment, as they refer to themselves. all
sharing processes need to have same segment number for that code segment. this problem is not there in case of read only
segments.

Pages>> 1 2 3 4 5 6 7 8

Read rest of entry