1) Base of hexadecimal number system? Answer : 16 2) Universal gate in digital logic? Answer : NAND 3) Memory type that is non-volatile? Answer : ROM 4) Basic building block of digital circuits? Answer : Gate 5) Device used for data storage in sequential circuits? Answer : Flip-flop 6) Architecture with shared memory for instructions and data? Answer : von Neumann 7) The smallest unit of data in computing? Answer : Bit 8) Unit that performs arithmetic operations in a CPU? Answer : ALU 9) Memory faster than main memory but smaller in size? Answer : Cache 10) System cycle that includes fetch, decode, and execute? Answer : Instruction 11) Type of circuit where output depends on present input only? Answer : Combinational 12) The binary equivalent of decimal 10? Answer : 1010 13) Memory used for high-speed temporary storage in a CPU? Answer : Register 14) Method of representing negative numbers in binary? Answer : Two's complement 15) Gate that inverts its input signal? Answer : NOT 16)...
Thrashing
* If a process cannot keep its least required number of frames, then it must be interchanged out, freeing up frames for other processes. This is an mid level of CPU scheduling.
* But what about a process that can keep its least, but cannot keep all of the frames that it is currently using on a regular basis? In this case it is forced to page out pages that it will required again in the very near future, leading to large numbers of page faults.
* A process that is taking more time paging than implementing is said to be thrashing.
Cause of Thrashing
* Early process scheduling schemes would manage the level of multiprogramming permitted based on CPU utilization, adding in more processes when CPU utilization was low.
* The problem is that when memory filled up and processes started take up lots of time waiting for their pages to page in, then CPU utilization would lower, causing the schedule to add in even more processes and aggravate the problem! Eventually the system would basically grind to a stop.
* Local page replacement policies can stop one thrashing process from taking pages away from other processes, but it still tends to clog up the I/O queue, thereby slowing down any other process that requires to do even a little bit of paging (or any other I/O for
that matter. )
* To prevent thrashing we must give processes with as many frames as they really require "right now", but how do we know what that is?
* The locality model notes that processes typically obtains memory references in a given locality, making lots of references to the same general area of memory before moving periodically to a new locality, as shown in Figure below. If we could just keep as many frames as are concerned in the current locality, then page faulting would occur primarily on switches from one locality to another. ( E.g. when one function subsists and another is called. )
working-set model
The working set model is situate on the concept of locality, and determines a working set window, of length delta. Whatever pages are added in the most recent delta page references are said to be in the processes working set window, and has its present working set, as illustrated in below Figure:
* The selection of delta is anlytical to the success of the working set model - If it is too small then it does not enclose all of the pages of the current locality, and if it is too large, then it encloses pages that are no longer being frequently accessed.
* The total demand, D, is the total of the sizes of the working sets for all processes. If D surpass the limit the total number of available frames, then at least one process is thrashing, because there are not sufficient frames available to satisfy its minimum working set. If D is possibly less than the currently accessable frames, then additional processes can be launched.
* The strong part of the working-set model is keeping trace of what pages are in the present working set, since every reference adds one to the set and deletes one older page. An estimation can be made using reference bits and a timer that goes off after a regulate interval of memory references:
• For example, suppose that we place the timer to go off after each 5000 references ( by any process ), and we can store two additional historical reference bits in addition to the current reference bit.
• Every time the timer goes off, the current reference bit is imitate to one of the two
historical bits, and then cleared.
• If one of the three bits is place, then that page was referenced within the last 15,000 references, and is considered to be in that processes reference set.
• Finer resolution can be reached with more historical bits and a more frequent
timer, at the expense of greater overhead.
Page-Fault Frequency
* A more direct method is to recognize that what we really want to control is the page-fault rate, and to allote frames based on this directly measurable value. If the page-fault rate exceeds a certain upper bound then that process requires more frames, and if it is below a given lower bound, then it can provide to give up some of its frames to other processes.
* ( I suppose a page-replacement strategy could be devised that would choose victim frames based on the process with the lowest current page-fault frequency. )
