Midterm Flashcards
Draw Von Neumann’s architecture of a computer.
What are the five main categories of modern computer systems?
Personal Mobile Device (PMD)
Desktop Computing
Servers
Clusters / Warehouse Scale Computers
Embedded Computers
What is the primary task of an “operating system?”
Answer1: A program that
acts as an intermediary between a user of a computer and the computer
hardware. Or Answer2: OS is a resource allocator, which manages all resources,
decides between conflicting requests for efficient and fair resource use, and
controls programs within allocated space.
What are the two main characteristics of an OS?
Efficiency and
convenience. Efficiency means that the OS can manage multiple processes and
allocate memory to these processes fairly and efficiently. For example, if one
process is trying to hug a large number of frames, the other processes should not
be denied active frames. If a process is not using its frame or CPU assets, that
process should be deactivated. In servers, efficiency is of main importance.
Convenience is a factor that a system user expects from the OS. Allowing a user
to access programs and applications easily is an example. In mobile devices,
convenience is a major factor.
Explain the role of the OS as the resource manager
One of the main
tasks of an OS is to optimize the use of all computational resources to ensure good
overall performance while satisfying the requirements of specific applications,
including guaranteeing acceptable response times for interactive processes, meeting
deadlines of time-critical tasks, and allowing safe communication among different
tasks. A program typically alternates between phases of input, computation, and
output. Consequently, the CPU is underutilized during the I/O phases, while the I/O
devices are idle during the compute phase. The overall performance of all applications
can be improved by using concurrency. The OS tries to keep the CPU, main memory,
and all storage and I/O devices busy at all times by overlapping independent
operations whenever possible.
What is “multiprogramming?
Multiprogramming is a technique that keeps several
programs active in the main memory and switches execution among the different programs
to maximize the use of the CPU and other resources. Whenever a program enters an I/Obound phase where little CPU time is needed, other programs can resume and utilize the CPU
in the meantime. Similarly, whenever a device completes an operation, the OS activates
computations that can utilize the now available device.
What is time-sharing?
Time-sharing (multitasking) is an extension of
multiprogramming where the CPU is switched periodically among all active computations to
guarantee acceptable response times to each user. Time-sharing employs the concept of
virtualization by creating the illusion of having a separate virtual CPU for each computation
Situation 1 is a sequential system. First, program A is executed, and then program B.
Situation 2 is a multiprogramming case. Finally, situation 3 is time-sharing, where the
switching between programs A and B is done very quickly, and we are showing them as
running in parallel.
Multiprogramming generally improves CPU utilization and throughput. (True or False?)
True: Multiprogramming overlaps phases of computation and I/O from different
computations to better utilize the CPU and other resources, which improves overall
performance
The main objective of time-sharing is to improve resource utilization. (True or False?)
False: Resource utilization is improved by multiprogramming, which overlaps CPUbound and I/O-bound computations. On the other hand, Time-sharing only switches the
CPU among different computations to create the illusion of simultaneous execution, which
generally does not improve resource utilization beyond simple multiprogramming
Multiprogramming and time-sharing are not used together. (True or False?)
To achieve the best CPU utilization, _____ computations should run
simultaneously.
a) 2 b) more than 2 c) all available processes
B
Using more than two computations increases CPU utilization
but, at the same time, uses more memory and other resources. A careful
balance must be found to minimize overhead while still increasing overall
performance.
The use of time-sharing will _____.
a) speed up all computations
b) guarantee a reasonable response to each computation.
c) improve resource utilization
B
No computation can monopolize the CPU indefinitely
What is the OS kernel?
The kernel of an OS is the minimal set of
functions necessary to manage the system resources safely and efficiently. The
kernel typically provides essential services for memory and device management,
creating and managing computations, and communication among the different
concurrent activities within the system.
What are privileged instructions?
The instruction set provided
by the CPU is divided into two sets of privileged and non-privileged to deal with
security issues. A privileged instruction performs critical operations that access
I/O devices and the CPU’s status and control registers. Thus only the OS kernel is
allowed to execute privileged instructions.
What are the two modes that the CPU operates?
The CPU
operates in two different modes, indicated by a particular mode bit, to guarantee
that no programs outside the trusted kernel can use privileged instructions. Kernel
mode is the CPU state where both privileged and non-privileged instructions may
be used. User mode is the CPU state where only non-privileged instructions may be
used. Any attempt to execute a privileged instruction in user mode automatically
transfers control to the kernel.
What do interrupts and traps have in common? What are the differences between the two concepts?
Traps and interrupts both suspend the execution of the current
instruction sequence and temporarily divert control to a dedicated area within the OS kernel.
An external event causes an interrupt. Ex: The completion of an I/O operation or a timeout
signal from a clock. Interrupts are asynchronous to the current execution in that the
interruption may occur unpredictably between any two instructions. A trap is a particular case
of an interrupt caused by an event internal to the current execution. Ex: The execution of a
privileged instruction or an arithmetic overflow. Traps are synchronous to the current
execution in that the currently executing instruction causes the interruption. The interruption
can be unintentional, as in the case of an error, or intentional, as in the case of a supervisor call.
What is a process, and what is a process’s PCB?
A process is an instance of a program
being executed by an OS. For example, when a user opens a new application like a web browser
or text editor, the OS creates a new process. The OS itself is organized as a collection of
processes. The OS keeps track of each process using a process control block (PCB). PCB is a
data structure that holds information for a process, including the current instruction address,
the execution stack, the set of resources used by the process, and the program being executed
What is the content of the PCB of a process?
PCB contains a list of registers
of the process, program counter, memory management information, process id,
process state, and a list of files that are opened by the process.
A newly created process starts in the ready state. When the OS selects
the process for execution, it goes to the running state. When the OS interrupts
the process, for example, to let some other processes use the CPU, its state
changes to ready. When a process requests a currently unavailable resource,
such as a file already opened by another user or some input data, the process’s
state changes to “blocked.” When some other process releases the resource or
generates the data needed by the blocked process, the OS moves the blocked
process to ready.
The networks are categorized into four groups for networked distributed
computing in terms of the distance between members. What are these four types
of networks
LAN, WAN, MAN, PAN
In terms of the role of connected network members, computing environments are divided into two types. What are these two types of networks?
1) client-server, 2) peer-to-peer.
What is the difference between “emulation” and “virtualization?”
A. Emulation is used when the source CPU type (physically present) differs
from the target CPU type (the CPU for which a program is compiled for). For
example, Apple desktops switched from IBM CPU to Intel CPU, and old
software used Rosetta to run on emulated IBM CPU.
B. Virtualization allows a guest OS to run as an application on a host OS.
What is the difference between “full virtualization” and “paravirtualization?
In full virtualization, the guest is an original OS and wants to manage the memory,
perform protection, etc. In para-virtualization, guest OS is designed to run as a
guest in a virtual environment, is aware of other operating systems, and knows its
limitations. Para-virtualization requires the guest operating system to be modified
to use the hypervisor’s APIs, making it more efficient than full virtualization in
terms of CPU utilization and memory access. Para-virtualization is best suited for
situations where a high level of performance is required, such as in highperformance computing or data-intensive workloads.
What are the three types of services that cloud environments offer?
SaaS (software as a service), PaaS (platform as a service), and IaaS
(infrastructure as a service).
What are the three types of “cloud computing?”
Private, public,
hybrid
What are the three advantages of a “multiprocessor system” over a single processor?
1- Increased throughput,
2- Lower costthan using a collection of single processors,
3- Reliability is higher, and the system is more fault-tolerant
What is the difference between “symmetric” and “asymmetric” multiprocessors?
Asymmetric multiprocessor is a CPU scheduling
method in which all scheduling decisions, I/O processing, and other system
activities are handled by a single processor — the master server. The other
processors execute only user code. This is a simple method because only one core accesses the system data structures, reducing the need for data sharing. The
downfall of this approach is that the master server becomes a potential bottleneck
where overall system performance may be reduced.
Symmetric multiprocessor (SMT) is the standard approach for supporting
multiprocessors where each processor is self-scheduling.
What are the five activities of “process management?”
1-Creating and deleting both user and system processes
2-Suspending and resuming processes
3-Providing mechanisms for process synchronization
4-Providing mechanisms for process communication
5-Providing mechanisms for deadlock handling
What is the difference between “program” and “process”?
A program is a collection of instructions and is a passive entity. A process is a
program in execution and is an active entity.
What is a memory unit exposed to?
1- A stream of addresses + read requests
2- A stream of addresses + data and write requests
For a cache system, how long does one memory access take?
It takes many CPU cycles. AMAT= cache-hit-time+ miss-rate*miss-penalty
How long does one register access take?
It takes one clock cycle (or less)
What do we mean by “throughput of memory”?
Number of bytes accessed in a time unit (Bytes/sec)
What does “memory management” mean?
A system that determines whatis in memory and when. It is a system that optimizes
the CPU’s utilization and the overall computer’s response to users. (this question
says what MM has to do, but we don’t say how it will be done)
What does memory management do?
This is how MM should
implement its goal: It keeps track of which parts of the memory are currently
being used. It means there is, for example, a table showing which frames are
occupied by what pages. Next, it decides which processes (or parts thereof) and
data to move into and out of the memory. It means that the tale has a column for
the process IDs showing what pages each process owns. Finally, it allocates and deallocates the memory space as needed. The table should be updated as the
processes come in or go out
What is meant by the performance difference (gap) between DRAM and
CPU?
The throughput of DRAM is much lower than what the CPU
requires.
What is “memory hierarchy”?
Creating a pyramid with slow, cheap, and large memory at the bottom and placing
fast, expensive, and small memories at the top.
What is the “locality of reference”
When a reference is made
to memory, the same location, or locations near that, will be referenced soon.
How could we overcome the performance difference
By using
memory hierarchy
What is the effect of a “low” locality of reference?
Low locality
causes a high miss rate, forcing memory management to refer to slower parts of
the hierarchy
Suppose reading one word from the main memory takes 50 clocks, and
reading one block of words from memory would take 100 clocks. Also, assume
that reading one word from the cache would take 2 clock cycles. What should be
the maximum cache “miss rate” for this memory system to be worth having the
cache rather than directly accessing the main memory
Answer: 50> 2
+miss_rate*100. miss_rate should be less than 0.48
What are the primary and secondary memory layers?
What are the four categories of memories in terms of “access type”?
RAM, SAM, DASD, CAM. Nowadays, SAM (sequential access memory) is
not used anymore. RAM (Random access memory) is the method of accessing
SSDs and main memory. DASD is the method of accessing hard disks, a combination of SAM and RAM. Finally, CAM (Content addressable memory or
Associative Memory) is widely used. For example, CAM is used in TLBs, cache
structures, routers to lookup destination IPs, image search to lookup image
descriptions, etc.
What is the “inclusion principle” in the memory hierarchy?
The
content of layer 𝑖𝑖 of the hierarchy has to exist in layer 𝑖𝑖 + 1.
What are the four policies or questions in managing a memory hierarchy?
1- placement policy, 2- identification policy, 3- replacement policy, 4- update policy.
What is “mapping” in the context of memory management?
conversion of virtual addresses to physical addresses is called mapping.
What is “address binding”?
As a general definition, binding
means mapping from one address space to another. Traditionally, binding is
categorized into compile-time-binding, load-time-binding, and execution-timebinding.
Explain why load-time binding is not “dynamically relocatable” and why execution-time binding is dynamically relocatable
Load time binding: The compiler translates symbolic addresses to relative
(relocatable) addresses. The loader translates these to absolute addresses. If it is
not known at compile time where the process will reside in memory, then the
compiler must generate relocatable code. This is done once, and swapping cannot
be performed, which makes the method static.
Execution time binding: If the process can be moved during its execution from one
memory segment to another, then binding must be delayed until run time. The
absolute addresses are generated by hardware. Most general-purpose OSs use this
method (Dynamic).
Static-binding means locations are determined before execution. Dynamicbinding means locations are determined during execution.
What are “logical” and “physical” addresses? Answer:
Logical address – addresses generated by a program and sent to the CPU; also
referred to as virtual address
Physical addresses are addresses seen by the memory unit assigned to a program
depending on where the program resides in the main memory.
What is the job of the memory management unit (MMU)?
The run-time mapping from virtual to physical addresses is performed by
hardware called the memory-management unit (MMU).
What is “dynamic relocation”?
Dynamic relocation is relocating data or codes currently in the computer’s
memory to other parts of the computer, creating more efficient memory
storage while a program is still active
What are the minimum hardware requirements of an MMU for a dynamic
relocation?
A relocation register
Which type of program benefits most from dynamic relocation?
A
significant portion of the code is used for rare cases in some programs, and
only a small piece of the code is frequently used. For such applications,
dynamic relocation can be used efficiently. Such applications are known as 20-
80, which means that 20% of the code is used 80% of the time.
What is a “stub”?
Stub is used for dynamic linking, where linking is
postponed until execution time. A stub is a small piece of code used to locate
the appropriate memory-resident library routine. Stub replaces itself with the
address of the library routine and executes the routine.
What is the “Contiguous allocation” of memory?
Contiguous
allocation means allocating a contiguous region of the main memory to a
program.
Why is segmentation considered “Contiguous” and paging considered
“non-Contiguous”?
Segmentation allocates one piece of memory,
called a segment, to one program. Different parts of the memory, called pages,
could contain a part of a program in paging. These pages could be noncontiguous.
What are the elements of the two-tuple that a segment is referred to?
segment number and offset.
What are the minimum hardware requirements in a multiprogramming
system to ensure that each program only accesses its memory space? Draw
a simple block diagram for this protection system.
How could we define efficiency in a “variable partitioning” memory
system? b) What happens when a new process arrives? c) What happens
when the process exists? d) What kind of information does the OS maintain
in such a system?
a) The percentage of occupied memory when there is no room for a new
process is the efficiency—the higher this percentage, the smaller the useless
fragments.
b) When a process arrives, it is allocated memory from a hole large enough to
accommodate it.
c) The exiting process frees its partition. Then, adjacent accessible partitions
are combined.
d) OS maintains information about allocated partitions, and free partitions
(holes)
What strategies for “placement policy”in a “dynamic allocation” memory system are possible?
First fit, best fit, worst fit.
What are the two types of memory fragmentation?
internal
fragmentation, external fragmentation.
Which type of fragmentation occurs in the Contiguous allocation
system?
external fragmentation occurs between segments
True or false?: The 50-percent rule states that 50% of memory is lost to
external fragmentation when the first-fit policy is used.
False. The 50% rule means that 50% of the occupied space is useless
fragments. Hence, if segments occupy N bytes, then N/2 bytes are fragments,
which is 1/3 of the total memory space.
What is a solution for memory fragmentation in contiguous allocation?
What are the prerequisites of such a remedy, and what are the problems?
compaction is the solution. It requires that the code and data be
relocatable.
How does the “paging” system partition a program? Does it have to bring
the whole program into the memory?
Page size is a power of 2. In
paging, only one page of a program or data has to bring into the memory. Other
parts of the code or data are brought into the memory as needed.
What is the difference between a “frame” and a “page”?
The frame
and page are of the same size. A frame is referred to as a physical piece of
memory, and a page is referred to as the virtual address space.
What is the job of a “page table”?
t contains a translation (mapping)
of virtual to physical addresses.
Assume that the logical address is 24 bits and the physical memory is 1MB.
Also, assume that each page or frame is 4KB.
a) Show how the logical and physical addresses are partitioned.
b) What is the size of the page table?
c) Assume the logical address is ABCDEF, the content of the page table in
line DEF is AB, and in line ABC is F5. Where in the physical memory is this
logical address mapped?
Accessing the page table may have considerable delays. What is a solution to
reduce the average delay of the page address mapping?
Use of tlb
Suppose the logical address is 32 bits. The physical memory is 16MB. Pages
are 4KB. There is a TLB with 64 lines of associative memory with an access
time of 0.5 cycles. The access time of the page table is one cycle. The miss
rate of TLB is ten percent.
a) How big is the page table?
b) What is the average access time of this system?
c) Now consider the content of the page table and TLB as shown below.
Suppose logical address D00EF123 is issued, which cannot be found in
the TLB. Where in the physical memory is this address mapped? Where
will the logical address 12345F05 be mapped in the main memory?
d) Convert logical address FEDC05F2 to a physical address.
a) The page table has 2^20 lines. (32bits-12bits)= bits for virtual page #
b) EAT= 0.90.5+ 0.11=0.55 cycles
c) D000EF is the page number that is mapped at frame number 56F. Hence,
the physical address is 56F123. The logical address 12345F05 is found in
the TLB and the page table. We take the TLB content, which tells us that
the physical address is 567F05.
d) FEDC05F2 is mapped to F565F2.
What is the purpose of using “valid bit” in the page memory table?
This bit is just for protection purposes. The “valid” bit indicates that the
associated page is in the process’s logical address space and is, thus, a legal
page. The page is not in the process’s logical address space when the bit is
invalid. The use of the valid-invalid bit traps illegal addresses. The operating
system sets this bit for each page to allow or disallow access to the page.
What is a “reentrant” page? Usually, reentrant pages belong to some specific
processes. Name two examples of such processes.
the Reentrant code is non-self-modifying: it never changes during
execution. Thus, two or more processes can execute the same code
simultaneously. Each process has its copy of registers and data storage to hold
the data for its execution. The data for two different processes will, of course,
be different. The reentrant page is a read-only copy of code shared among
processes. Examples are text editors, compilers, C libraries, and Windows
systems
Name three strategies that are used to reduce the size of page tables when
the logical address is large.
Hierarchical Paging, Hashed Page Tables, Inverted Page Tables
Suppose the logical address is 32 bits and the page offset is 12 bits. Show an
example of a hierarchical page address.
Page num:
P1 = 10
P2 = 10
Page offset:
D=12
We have 32-bit virtual addresses and 24-bit physical addresses. Assume that we have 4KB pages. Based on the following diagram’s content,
where is the virtual address ABCDEF00 mapped? Where do we map
F00BC000? Where do we map 12356FFF?
ABCDEF00 is mapped to 567F00. Virtual address F00BC000 is
mapped to 345000. Logical address 12356FFF is not yet mapped to a
physical address.
Why is a hierarchical page addressing difficult for 64-bit logical
addressing? What are the two alternative methods?
Even a threelevel page table requires a 2^32 line third-level table. If we use more page
table layers, for example, eightlayers,then going through all layers to find the
page’s address would be prohibitively long. Alternative approaches are using
hash tables and TLBs.
Explain the following diagram. What are p, q, s, r, and d? Suppose the 64-
bit logical address of F1234567890ABCDE is mapped into the physical
address of 4FFCDE. What are the values of p, d, and r? Also, give an example
of the value of q.
we see that pages are 4KB since the low significant 12 bits of the
physical and logical addresses are the same. P is the page number which is 52
bits, and the first 13 Hex digits of the address. r is 4FF, and d is CDE. q is
another 52-bit page number that is hashed into the same place as p is hashed
to. Since we don’t know the hash function, we can throw in any 52-bit number
as q. For example, CADF13571234F is q.
a) What is an “inverted page table?” b) How can we limit the search process?
a) The page table is as big as the number of physical pages. This
method makes the page table size much smaller than using a table that has
2^(number of virtual pages). b) hashing could be used to limit the search. For
example, the virtual page number is hashed in three different methods to
restrict the search to only three entries of the inverted table
The 64-bit Sparc Solaris uses two hash tables. What are these two tables?
What is “page walk” in the memory mapping process of this system?.
two hash tables are used. One table is used for the user codes, and one table
for the OS. Also, a TLB is used for fast search. Page walk: If the address is not
in the TLB, the system “walks back” and searches the hash tables.
Some operating systems occasionally deactivate “swapping.” What is the
purpose, and what are the occasions?
swapping requires the transfer
of data and code from the main memory to the backing store. The data
transfer is time-consuming. In UNIX, swapping is disabled until the number of
allocated pages becomes higher than a threshold.
Suppose that a process takes 200MB of the main memory. This process
has to be swapped by sending it to the backing memory and bringing a new process, of the same size, into the main memory. The transfer rate is
150MB/sec. How long will this context switch take?
What is a “pending I/O” during process swapping? Explain “double
buffering”that is used to remedy pending I/O
Sometimes, a process
has to be swapped into the backing store, and that process may have been
transferring data from I/O. The swapped-out process would lose the data. OS
could use its memory space to buffer the I/O data, and when the process is
brought back into the main memory, OS should deliver the buffer data to the
process. The data is moved twice, which is called double buffering.
What is the maximum size of a segment in an IA-32 system? What are
the differences between LDT and GDT? The logical addresses in IA-32
systems consist of two parts. What are these two parts called, and what are
their purposes?
Addresses in IA-32 systems consist of a selector and
an offset. A selector is a 16-bit number consisting of s(13 bits), g(1 bit), p(2
bits). The s part designates the segment number, and g indicates whether the
segment is in the global descriptor table (GDT) or the local descriptor table
(LDT). Also, the 2 bits p is used for protection. An offset is a 32-bit number
specifying the location of the byte within the segment in question. An offset
of 32 bits means each segment could be as large as 4GB.
The following diagram shows the addressing system of the IA-32. What
is the difference between addressing a 4KB page and a 4MB page
f the virtual address is 32 bits, then the physical address is usually
less than 32 bits, for example, 28 bits. The high 10 bits of the virtual address
are used to find a line in the page directory. A bit in the content of the page
directory line indicates if the page size is 4MB or 4KB. For 4MB pages, the
page directory provides a 28-bit start address, and we add our 4MB page
offset of 22 bits to that. For 4KB pages, the page director offers a 28-bit
address that points to the start of a page table. The page table has 2^10 lines,
and using the page table part of the virtual address, we refer to the
appropriate line of the table. The content of the page table is a 28-bit physical
address which we add the 12-bit offset to it to get the physical address of the
line of the 4KB page.
The addressing method in the ARM architecture is shown below. Explain
how this architecture works for 4KB, 16KB, 1MB, and 16MB pages.
f the virtual page table is 32 bits,then the physical address is smaller,
and it is, for example, 28 bits. The outer page table entries consist of two bits
thatindicate the page size. For example,“00” means the page size is 4KB, “01”
means 16KB, “10” means 1MB, and “11” means that the referenced page is
16MB. Besides these two bits, the content of the outer page table has 28 bits,
which refer to either the inner page table or a 1MB or 16MB page. Hence, the
offset part could be 12 bits, 14 bits, 20 bits, or 24 bits.
What are the advantages of using Virtual memory
a) Only part of the program needs to be in memory for execution,
b) Logical address space can be much larger than physical space,
c) Several processes can share address spaces,
d) More efficient utilization of physical memory,
e) More programs can run concurrently,
f) Less I/O needed to load processes
How could we implement Virtual memory?
Demand paging and
demand segmentation.
What is the usual practice in the utilization of virtual address space?
A program consists of a fixed-size code and different data types. The
stack starts at the highest virtual address, and the code begins at address zero.
On top of the code are data, and on top of the data, the heap of linked variables
is placed.
What is a “lazy swapper”?
t starts swapping segments only when
the swap is needed to free space in the physical memory
What is a “pager”?
it performs the swapping operation on “pages”
rather than segments.
How is the “valid-invalid (VI)” bit used in a page table?
if there
were no such a bit, then the table’s initial content may be considered valid frame
numbers even if all the table entries were zero. Hence, initially, all of the “VI” bits
are zero. Initially, the first demand page causes a “page fault” because the VI bit
is zero. After the page is read, the bit becomes valid (one).
What are the contents of the entries on the page table below?
Line 0 of PT has 4, line 2 has 6, and line 5 has 9. Valid bits of these
lines are 1. The rest of the page table is empty (valid bits are zero.)
a) CPU is referencing a page that is not in the physical memory, and it has an
“invalid” bit in the page table
b) A trap (interrupt) occurs, and OS takes over the execution process
c) OS finds the demanded page in the hard disk
d) OS brings the demanded page into the physical memory
e) OS updates the page table’s frame number and valid bit.
f) The interrupted instruction of the process takes back control and restarts
execution.
What is the “zero-fill-on-demand” strategy?
OS adds a frame to
the list of “free-frame-list” by zeroing the content of a frame.
Does the zero-fill-on-demand strategy increase the efficiency of
demand paging?
No. It adds an overhead. It doesn’t help identify free
frames because checking the zero content of a frame is a lengthy process.
Testing the valid bit of a frame is much faster than seeing if the frame’s content
is zero. Hence, the only reason for zeroing the content is for security purposes.
For a demand paging system, assume that the page fault rate is 𝒑𝒑.
What is Effective Access Time (EAT) for such a system?
For a demand paging system, assume the following. The main
memory access time is 300 ns, and the access time to the hard disk is 11 ms
(including all the overheads and swap in and out time.) We want the
effective access time for such a system to be only 20% larger than the main
memory access time. What should be the maximum page fault rate?
What is “copy-on-write?”
Occasionally, two identical processes
are created. Each one should have its own memory space. But OS places only
one set of pages for both processes to use. If process1 writes into the shared
page A, then page A is copied for process1. As a result, process2 will have the
original copy of page A. This process is known as copy-on-write (CoW).
What happens if there is no free frame when a page fault occurs?
OS has to replace a frame to bring in the demanded page
What is a “modify (dirty) bit?”What is the difference between the “dirty”
bit and a valid bit?
The valid shows whether the content of the page
table is valid or not. The dirty bit shows whether the frame’s content has been
changed. If the dirty bit is zero, writing back the frame into the disk is
unnecessary.
What are “frame allocation” and “page replacement” algorithms?
Frame allocation determines which physical memory frames are
assigned to virtual memory pages. In contrast, page replacement determines
which virtual memory pages are moved from physical memory to make room for
new pages.
Suppose that we have the following sequence of references to virtual
pages. Each number in this sequence of 21 references shows the page number
that the CPU has referred to.
1, 4, 1, 6, 1,1,1,1, 6, 1,1,1,1, 6, 1,1,1,1, 6, 1,1
Using FIFO, how many page faults occur if a) we only have one frame in our
main memory? B) we have two frames in the memory? C) if we have three
frames? D) if we have four frames in the memory?
If the main
memory is only one frame, then a page fault occurs each time the sequence
wants to access a new page. For example, if the sequence has four
consecutive 1’s, then only the first reference to page 1 would cause a fault,
and the other three references to page 1 are hits. Hence, in the above
sequence, 11 page-faults occur if we only have one frame. If we have two
frames in the memory, then four page-faults occur. If we have three frames,
then three faults occur, and with four frames, we will have three page-faults
Suppose that we have the following string of references:
7,0,1,2,0,3,0,4,2,3,0,3,0,3,2,1,2,0,1,7,0,1.
Further, assume that we only have three frames in the main memory. We want
to use a FIFO strategy for page replacement. Fill out the frames in the image
below with the appropriate page number.
What is Belady’s optimal page replacement method?
t
considers that it knows the future and replaces the page that will not be used
shortly.
For the following string of references, fill out the image with
appropriate page numbers based on Belady’s Optimal replacement method:
For the following string of references, fill out the image with
appropriate page numbers based on LRU (least recently used) replacement
method:
What are the two main methods for implementing LRU?
1)
Use a counter next to each frame. Every time that frame is referenced, the
counter is incremented. The frame with the smallest counter value is replaced
when replacing a frame. After each frame replacement, all counters are reset o zero. 2) We can use a stack. When a page enters the main memory, the page
number will be on top of the stack. Every time a page is referenced, its number
goes to the top of the stack. When we want to replace a frame, the one at the
bottom of the stack is replaced
Suppose we are using a stack to implement the LRU replacement
method. Consider the string of references shown below. Suppose that we
know the content of the stack after point a. What will be the content of the
stack after point b?
How is the “second chance” or the “clock” replacement method
implemented?
A reference bit (W) is assigned to each frame. Every
time that a frame is referenced, its W bit is set to 1. When a frame is replaced,
all W bits are reset to zero. The FIFO strategy is implemented. When a page
fault occurs, the frames are tested based on FIFO. If the frame has a zero W,
then it is replaced. If the frame has one W, then it is given a second chance, and
its W is reset to zero. Then the next frame based on FIFO is checked, and so
on
Suppose that the main memory consists of 4 frames. The following
sequence of frames has been referenced: 0,1,2,3,2,1,0,3,2,3. A page fault
occurs at the end of this sequence, and one of the frames must be replaced
using the “clock” strategy. Which frame is replaced
What is the “enhanced second-chance” replacement method
it
uses two bits for each frame, a dirty-bit and a reference bit. “00” means that
the page is not referenced since the last page-fault, and is not modified. Such
a frame has the highest priority for replacement. “10” shows that the frame is
referred to but has not been changed. This page has the second-highest
replacement priority since it does not need a write-back. “01” indicates that
the page is not referenced but modified. This page has the second-lowest
priority for removal since we need to write it back into the disk. “11” means
that the page has been referenced and has been modified. This page has the
lowest priority for replacement. Based on FIFO, frames are tested. If the pair
of bits are 00, then the page is replaced. Otherwise, the reference bit of the
page is set to zero, and the next frame is tested. A second round is performed
if no frame is found in the first round.
What is LFU strategy for page replacement
Least frequently used
page is replaced. Each page has a counter, and every time it is referenced, its
counter is incremented. The page with the lowest number of references is
replaced. The goal is to replace a page that is not very useful and is referred to
not very often. The shortcoming is that a page that is just brought in may be
replaced
What is a page buffering algorithm?
The system keeps a pool of free
frames. When a page fault occurs, a victim frame is chosen as before.
However, the desired page is read into a free frame from the pool before the
victim is written out. This procedure allows the process to restart as soon as possible without waiting for the victim page to be written out. When the
victim is later written out, its frame is added to the free-frame pool.
Let us assume we are using “proportional allocation” for two processes. We
have 62 frames available. One of the processes has 10 pages, and the other
127 pages. How many frames are allocated to each one?
What is thrashing?
A page fault would occur if a process uses all of
its allocated memory space and needs another page. An active page of this
process has to be replaced, which causes another page fault. Hence, each page
fault replaces a frame that is being used and causes another page fault.
Continuous page faults severely reduce performance. This situation is known
as “thrashing.”
What is the relationship between locality and thrashing?
If the overall locality of all active processes is larger than the physical memory,
then thrashing occurs. This situation means that active processes need to
refer to a more extensive space than the main memory. Hence, one active
frame has to be replaced by a new page, and this loop causes threshing.
What is the difference between local and global replacements?
Answer: In the local replacement strategy, each process selects only from its
set of allocated frames. Hence, this method would result in a consistent perprocess performance but could result in underutilized memory. In the global
replacement, the system selects a replacement frame from the set of all
frames; one process can take a frame from another. This method’s execution
time can vary greatly because information about all processes should be
considered. But the overall throughput is better than local replacement,
which is currently the common method
What is the “reclaiming pages” approach in the global page
replacement strategy?
Reclaiming pages is the process of freeing up
memory pages that are no longer being used by a program or process to make
that memory available for other programs or processes.
(When a program or process requests memory, the operating system allocates
memory pages to that program or process. However, as the program or process
runs, it may no longer need all the memory pages allocated to it. For example, if a
program finishes using a particular data structure, the memory pages allocated to
that data structure can be reclaimed and made available for other programs. The
operating system typically keeps track of which each program or process is using
memory pages. When a program or process no longer needs a particular page, the
operating system can mark it as free and add it to a pool of available memory pages.
These free pages can then be allocated to other programs or processes that need
them.)
Let us assume that each row of the following matrix is stored on
one page. Which of the two pieces of code would cause fewer page faults
code in part B) reads one i and 128 j, which is one row of the matrix.
For example, data[0][0],….,data[0][127] are read all from one page. Hence, for
each row of the matrix, one page-fault occurs. Overall, the code in part B)
causes 128 page-faults, one for reading each matrix row. On the other hand,
the code of part A) causes one page-fault for each element of the matrix,
totaling 128×128 page-faults.
Windows implements “demand-paging” using “clustering.” What is
clustering?
Besides bringing in the demanded page, it also brings
in the surrounding pages. For example, if page number N from the virtual
space is demanded, then pages N-1 and N+1 are also brought into the main
memory.
What is the working set of a Process
Pi?
The list of all pages
referenced in the most recent ∆ time steps.
Consider the following figure, which shows a sequence of page
references. Why is the working set, at time t1, consisting of 1,2,5,6,7?
The value of Δ is 10; hence, the list of pages referenced in the past
ten steps, at time t1, consists of 1,2,5,6,7
What happens if the working set consists of a small number of page
references?
It means that the locality of the process is very high;
hence, the process needs to reference only a few pages.
Windows uses two concepts of “working set minimum” and
“working set maximum.” What are these two concepts, and how are they
used?
The working set minimum is the minimum number of pages
the process is guaranteed to have in memory. A process may be assigned
as many pages up to its working set maximum.
What are the similarities between Windows, Solaris, and Linux in
dealing with virtual memory?
They all use demand paging and
copy-on-write. Each system also uses a variation of LRU approximation
known as the clock algorithm.
What does Windows do when a process loses frames below its
“working set minimum”?
Windows will take away frames from processes that have frames more than their “working set minimum” and give them to those that have frames less than their minimum
What is “prepaging”?
When a process starts, it has a high
page fault rate because none of its needed pages are resident in the main
memory. We want to avoid high page faults; hence all or most of the pages
of the process are brought into the main memory before they are
demanded and before generating page faults. After a while, if some of these
pages are not being used, they will be replaced.
What is “page-fault frequency?
number of page faults that occur in a unit of time for a process is called page fault frequency. For example, suppose the number of faults that arise for a process in every
10000 references is very low. In that case, it means that the process has a
high locality and is not using all of its allocated frames, and we can take
away some of its unused frames. On the other hand, if the page-fault
frequency is very high, the process needs more frames, and we should
assign more frames to that process.
