Module 2. Deadlock and Memory Management
Module 2. Deadlock and Memory Management
Module 2. Deadlock and Memory Management
Under the normal mode of operation, a process may utilize a resource in only the following
sequence:
1. Request: If the request cannot be granted immediately (for example, the resource is
being used by another process), then the requesting process must wait until it
can acquire the resource.
2. Use: The process can operate on the resource.
3. Release: The process releases the resource.
But, if every process in the set is waiting for other processes to release the resource, then
the deadlock happens. Two general categories of resources:
Reusable: can be safely used by only one process at a time and is not
depleted (that is not reduced) by that use. For example, Processors, I/O channels,
main and secondary memory, devices, and data structures such as files,
databases, and semaphores. Here, deadlock occurs if each process holds
one resource and requests the other.
Consumable: one that can be created (produced) and destroyed (consumed). For
example, interrupts, signals, messages, and information in I/O buffers. Here,
deadlock may occur if a Receive message is blocking.
o P = {P1, P2, …, Pn}, the set consisting of all the processes in the system.
o R = {R1, R2, …, Rm}, the set consisting of all resource types in the system.
Request edge: A directed edge Pi Rj indicates that the process Pi has requested
for an instance of the resource Rj and is currently waiting for that resource.
Assignment edge: A directed edge Rj Pi indicates that an instance of the
resource Rj has been allocated to the process Pi
The following symbols are used while creating resource allocation graph:
A Process
Examples of resource allocation graph are shown in Figure 3.1. Note that, in Figure 3.1(c),
the processes P2 and P4 are not depending on any other resources. And, they will give up
the resources R1 and R2 once they complete the execution. Hence, there will not be any
deadlock.
(a) Resource allocation Graph (b) W ith a deadlock (c) with cycle but no
deadlock
3
Given the definition of resource allocation graph, we can understand that, if there is no
cycle in the graph, then there will not be a deadlock. If there is a cycle, there is a chance of
deadlock.
There are three general approaches exist for dealing with deadlock.
Prevent deadlock: Ensure that the system will never enter a deadlock
state.
Avoid deadlock: Make appropriate dynamic choices based on the current state of
resource allocation.
Detect Deadlock: Allow the system to enter a deadlock state and then recover.
and requesting Rj. This condition is impossible, because it implies i<j and j<i. But, here
also, the problems seen in hold-and-wait prevention are seen.
An alternative method for avoiding deadlocks is to require additional information about how
resources are to be requested. For this purpose, a simplest and most useful model is
designed: each process must declare the maximum number of resources of each type that
it may need. Given a priori information about the maximum number of resources of
each type that may be requested for each process, it is possible to construct an algorithm
that ensures that the system will never enter a deadlock state. This algorithm defines
the deadlock-avoidance approach. A deadlock-avoidance algorithm dynamically examines
the resource-allocation state to ensure that a circular-wait condition can never exist.
The resource-allocation state is defined by the number of available and allocated
resources, and the maximum demands of the processes.
A safe state is not a deadlock state. A deadlock state is an unsafe state. But, not all unsafe
states are deadlocks as shown in Figure 3.2. An unsafe state may lead to a deadlock.
As long as the state is safe, the OS can avoid unsafe (and deadlock) states. In an
unsafe state, the OS cannot prevent processes from requesting resources such that a
deadlock occurs: The behavior of the processes controls unsafe states.
To apply this algorithm, each process Pi must know all its claims before it starts executing.
If no cycle exists, then the allocation of the resource will leave the system in a safe state. If
the cycle is found, system is put into unsafe state and may cause a deadlock.
W hen a new process enters the system, it must declare the maximum number of
instances of each resource type that it may need. This number may not exceed the total
number of resources in the system. W hen a user requests a set of resources, the
system must determine whether the allocation of these resources will leave the system in a
safe state. If it will, the resources are allocated; otherwise, the process must wait until
some other process releases enough resources.
1. Safety Algorithm: It is for finding out whether a system is in safe state or not.
The steps are as given below –
1. Let Work and Finish be vectors of length m and n, respectively. Initialize:
Work = Available
Finish [i] = false for i = 1, 2, 3, …, n.
2. Find an i such that both:
(a) Finish [i] = false
(b) Needi Work
If no such i exists, go to step 4.
3. Work = Work + Allocationi
Finish[i] = true
go to step 2.
4. If Finish [i] == true for all i, then the system is in a safe state.
2. Resource – Request Algorithm: Let Requesti be the request vector for process Pi. If
Requesti [j] = k then process Pi wants k instances of resource type Rj.
9
If the resulting resource allocation is safe, then the transaction is complete and
the process Pi is allocated its resources. If the new state is unsafe, then P i
must wait for Requesti , and the old resource-allocation state is restored
Suppose, now the process P1 makes a request (1, 0, 2). To check whether this request can
be immediately granted, we can apply Resource-Request algorithm. If we assume that this
request is fulfilled, the new state would be as shown in Table 3.3. Now, by checking using
safety algorithm, we see that the sequence <P1, P3, P4, P0, P2> is in safe state. Hence,
this request can be granted.
1
0
Note that a detection-and-recovery scheme has some system overhead and run-time cost
is more.
Consider Figure 3.4 showing a resource allocation graph and its respective wait-for graph.
Figure 3.4 (a) Resource Allocation graph (b) corresponding wait-for graph
A deadlock exists in the system if and only if the wait-for graph contains a cycle. To detect
deadlocks, the system needs to maintain the wait-for graph and periodically to invoke an
algorithm that searches for a cycle in the graph.
The detection algorithm given below investigates every possible allocation sequence for
the processes that remain to be completed.
If deadlocks occur frequently, then the detection algorithm should be invoked frequently.
Resources allocated to deadlocked processes will be idle until the deadlock can be broken.
Deadlocks occur only when some process makes a request that cannot be granted
immediately. So, we could invoke the deadlock detection algorithm every time a request for
allocation cannot be granted immediately. In this case, we can identify not only the set of
processes that is deadlocked, but also the specific process that "caused" the deadlock.
Another alternative is to invoke the algorithm in periodic intervals, say, once in an hour or
whenever CPU utilization drops below certain level.
10
10
Aborting a process may not be easy. If the process was in the midst of updating a file,
terminating it will leave that file in an incorrect state. Similarly, if the process was in
the midst of printing data on the printer, the system must reset the printer to a correct
state before printing the next job. Many factors may determine which process is chosen to
abort:
Priority of the process.
How long process has computed, and how much longer to completion.
How many and what type of resources the process has used.
How many more resources process needs to complete.
How many processes will need to be terminated?
Is process interactive or batch?
never completes its designated task, a starvation situation that needs to be dealt with in
any practical system. Clearly, we must ensure that a process can be picked as a victim
only a (small) finite number of times.
The problem: Devise an algorithm that will allow the philosophers to eat. The
algorithm must satisfy mutual exclusion (no two philosophers can use the same fork at
the same time) while avoiding deadlock and starvation.
Each philosopher picks up the fork on the left side first and then the fork on the right. After
the philosopher is finished eating, the two forks are replaced on the table. This
solution leads to deadlock: If all of the philosophers are hungry at the same time, they all
sit down, they all pick up the fork on their left, and they all reach out for the other fork,
which is not there. In this undignified position, all philosophers starve.
To overcome the risk of deadlock, we could buy five additional forks or teach
the philosophers to eat spaghetti with just one fork. As another approach, we could
consider adding an attendant who only allows four philosophers at a time into the dining
room. W ith at most four seated philosophers, at least one philosopher will have access to
two forks.
MEMORY MANAGEMENT
3.8 BACKGROUND
It has been discussed earlier that CPU scheduling is used to increase the utilization of CPU
and to improve computer’s response to the user. For this, several processes must be kept
in the memory. Here we will discuss how memory is managed to achieve this.
Memory consists of a large array of words or bytes, each with its own address. The CPU
fetches instructions from memory according to the value of the program counter. These
instructions may cause additional loading/storing from/to specific memory addresses.
Due to several reasons, we can ignore how a memory address is generated by a program.
But, we have to consider only the sequence of memory addresses generated by the
running program.
Most systems allow a user process to reside in any part of the physical memory. Thus,
although the address space of the computer starts at 00000, the first address of the user
process need not be 00000. This arrangement affects the addresses that the user program
can use. In most cases, a user program will go through several steps-some of which may
be optional-before being executed as shown in Figure 3.7. Addresses may be represented
in different ways during these steps. Addresses in the source program are
generally symbolic such as count. A compiler will typically bind these symbolic
addresses to relocatable addresses (such as "14 bytes from the beginning of this
module"). The linkage editor or loader will in turn bind these relocatable addresses to
absolute addresses (such as 74014). Each binding is a mapping from one address space to
another.
The binding of instructions and data to memory addresses can be done in following ways:
Compile Time: If we know at compile time where the process will reside in
memory, then absolute code can be generated. After sometime, if this location
changes, then it is necessary to recompile this code.
Load Time: If it is not known at compile time where the process will reside in
memory, then the compiler must generate relocatable code. In this case,
final binding is delayed until load time.
15
15
Execution Time: If the process can be moved during its execution from one
memory segment to another, then binding must be delayed until run time. Special
hardware must be available for this scheme to work.
The set of all logical addresses generated by a program is a logical-address space; the set
of all physical addresses corresponding to these logical addresses is a physical-
address
16
16
space. The run-time mapping from virtual to physical addresses is done by a hardware
device called the memory-management unit (MMU).
The value in the base register (also called a relocation register) is added to every address
generated by a user process at the time it is sent to memory. For example, if the base is at
14000, then an attempt by the user to address location 0 is dynamically relocated to
location 14000; an access to location 346 is mapped to location 14346 (Figure 3.8). The
user program never sees the real physical addresses. The program can create a pointer to
location 346, store it in memory, manipulate it, compare it to other addresses-all as the
number 346. Only when it is used as a memory address (in an indirect load or store,
perhaps) is it relocated relative to the base register. The user program deals with
logical addresses. The memory-mapping hardware converts logical addresses into
physical addresses. The final location of a referenced memory address is not determined
until the reference is made. W e now have two different types of addresses: logical
addresses (in the range 0 to max) and physical addresses (in the range R + 0 to R +
max for a base value R). The user generates only logical addresses and thinks that the
process runs in locations 0 to max.
A shared library is a file that is intended to be shared by executable files and further
shared object files. Modules used by a program are loaded from individual shared
objects into memory at load time or run time, rather than being copied by a linker.
3.9 SWAPPING
A process needs to be in memory to be executed. A process, however, can be swapped
temporarily out of memory to a backing store, and then brought back into memory for
continued execution as shown in Figure 3.9. Such swapping may be necessary in
priority based scheduling or round-robin scheduling.
Normally a process that is swapped out will be swapped back into the same memory space
that it occupied previously. This restriction is dictated by the method of address binding. If
binding is done at assembly or load time, then the process cannot be moved to different
locations. If execution-time binding is being used, then a process can be swapped into a
different memory space, because the physical addresses are computed during execution
time.
Swapping requires a backing store. The backing store is a fast disk. It must be
large enough to accommodate copies of all memory images for all users, and it must
provide direct access to these memory images. The system maintains a ready queue
consisting of all processes whose memory images are on the backing store or in memory
and are ready to run. W henever the CPU scheduler decides to execute a process, it calls
the dispatcher. The dispatcher checks to see whether the next process in the queue is in
memory. If not, and there is no free memory region, the dispatcher swaps out a
process currently in memory and swaps in the desired process. It then reloads
registers as normal and transfers control to the selected process.
The context-switch time in such a swapping system is high. If we want to swap a process, it
must be idle.
W hen the CPU scheduler selects a process for execution, the dispatcher loads
the relocation and limit registers with the correct values as part of the context switch.
Because
19
19
every address generated by the CPU is checked against these registers, we can protect
OS and user programs and data from being modified by this running process.
How to satisfy a request of size n from a list of free holes is a dynamic storage-allocation
problem. There are following algorithms:
First Fit: Allocate the first hole that is big enough.
Best Fit: Allocate the smallest hole that is big enough. W e must search the entire
list, if the list is not ordered by size.
Worst Fit: Allocate the largest hole.
20
20
Best fit and first fit are better than worst fit with respect to time and storage utilization. First
fit is faster. All the three algorithms suffer from external fragmentation. As processes are
loaded and removed from memory, there will be multiple holes. External fragmentation
exists when enough total memory space is there to satisfy the request, but it is
not contiguous.
3.10.3 Fragmentation
Sometimes, the size of the hole is much smaller than the overhead required to track it.
Hence, normally, physical memory is divided into fixed-size block. Then memory is
allocated in terms of units. So, sometimes, the memory allocated for a process may be
slightly larger than what it requires. Such a difference is known as internal fragmentation.
For example, if the physical memory is divided into block of 4 bytes, and the
process requests for 6 bytes, then it will be allocated with 2 blocks. Hence, the total
allocation is 8 bytes leading to 2 bytes of internal fragmentation.
3.11 PAGING
Paging is a memory-management scheme that permits the physical-address space of
a process to be noncontiguous. Paging avoids the problem of fitting the varying-
sized memory chunks onto the backing store.
W hen the CPU scheduler selects a process for execution, the dispatcher loads
the relocation and limit registers with the correct values as part of the context switch.
Because every address generated by the CPU is checked against these registers, we
can protect OS and user programs and data from being modified by this running process.
Example:
Consider a page size of 4 bytes and a physical memory of 32 bytes (8 pages) as shown in
Figure 3.13. W e will see now, how the user's view of memory can be mapped into physical
memory:
Logical address 0 is page 0, offset 0. Indexing into the page table, we find that page
0 is in frame 5. Thus, logical address 0 maps to physical address 20 (= (5 x 4) + 0).
Logical address 3 (page 0, offset 3) maps to physical address 23 (= (5 x 4) + 3).
Logical address 4 (page 1, offset 0); according to the page table, page 1 is mapped
to frame 6. Thus, logical address 4 maps to physical address 24 (= (6 x 4) + 0).
Logical address 13 maps to physical address 9.
W hen paging is used, there will not be external fragmentation: Any free frame can
be allocated to a process that needs it. However, some internal fragmentation will be there.
To reduce it, small-sized pages are preferable. But, more number of pages will lead to
many entries in page-table, and hence much overhead. So, optimum selection of size
of each page is essential.
22
22
W hen a process needs to be executed, its size represented in terms of number of pages is
examined. Each page of the process needs one frame. Thus, if the process requires n
pages, at least n frames must be available in memory.
This double access problem can be solved by the use of a special fast-lookup
hardware cache called associative memory or translation look-aside buffers (TLBs).
The TLB is associative, high-speed memory. Each entry in the TLB consists of two parts: a
key (or tag) and a value. The TLB is used with page tables in the following way:
The TLB contains only a few of the page-table entries.
W hen a logical address is generated by the CPU, its page number is presented
to the TLB.
If the page number is found, its frame number is immediately available and
is used to access memory.
If the page number is not in the TLB (known as a TLB miss), a memory
reference to the page table must be made. W hen the frame number is
obtained, we can use it to access memory.
This is shown in Figure 3.14.
23
23
3.11.3 Protection
In paging technique, protection bits are associated with each frame are kept in the
page table. This will help memory protection. One bit can define a page to be read-write or
read- only. W hile referring the page table to get a frame number, the protection bits
are also checked. An attempt to write a read-only page causes hardware trap to OS.
Another bit attached to page table is valid – invalid bit. W hen this bit is set to valid,
it indicates that the respective page is in the logical address space of the process and
hence it is a legal/valid page. If this bit is set to invalid, the page is not in logical address
space of the process.
do so, two-level paging algorithm can be used. Here, the page table itself is paged
as shown in Figure 3.15.
Hashed Page Tables: A common approach for handling address spaces larger than 32
bits is to use a hashed page table, with the hash value being the virtual-page number. Each
entry in the hash table contains an array of linked lists that hash to the same location (to
handle collisions using open-hashing/separate chaining method). Each node in a linked list
consists of three fields:
The virtual page number
the value of mapped page frame
a pointer to the next element in the linked list.
Inverted Page Table: It is obvious that each process has its own page table and
every page table has one entry for each page. We know that a page represents
logical/virtual addresses. It is the OS which converts the logical addresses into physical
addresses later. As, a page table contains millions of entries, it is a burden on OS to covert
everything into physical address.
To avoid this problem, inverted page table is used. This table contains one entry for each
real physical frame of memory rather than for logical memory. Hence, only one page table
is sufficient for the system. As each process has its own address space, another entity
specifying process identifier (pid) in its address – space is used as shown in Figure 3.17.
The working is as explained below:
The page table contains pid and page number.
The CPU generates logical address containing pid, page number and offset.
The pair pid and page number is searched for, in the page table.
th
If the match is found at i entry, then the physical address will be <i, offset>
If the match is not found, illegal address access error occurs.
26
26
example: Assume that 40 users are using a text editor at a time. Let the text editor consists
of 150KB of code and 50KB of data space. We need 8000KB for 40 users. As text-editor is
reentrant, only one copy of the editor needs to be kept in the physical memory and it can be
shared among all the users. But, the data space should be different for every user. This is
depicted in Figure 3.18. In this example, size of each page (and also the frame) is taken as
50KB.
Such sharing technique can be applied for compilers, window systems, run-time libraries,
database systems etc.
3.12 SEGMENTATION
In paging, we have observed that user view of the memory and the actual physical memory
are different. User view of memory is mapped into physical memory.
3.12.2 Hardware
Here, a two dimensional user-defined addresses are mapped into one-dimensional physical
addresses. This mapping is affected by a segment table. Each entry of the segment table
has
segment base – contains the starting physical address where the segment resides in
memory
segment limit – specifies the length of the segment
A logical address consists of two parts: a segment number, s and an offset d. The segment
number is used as an index into the segment table. The offset d of the logical address must
be between 0 and the segment limit. If it is not, we trap to the OS (logical addressing
attempt beyond end of segment). If this offset is legal, it is added to the segment base to
produce the address in physical memory of the desired byte. The segment table is thus
essentially an array of base-limit register pairs. The structure is as given in Figure 3.20.
Example: Consider the situation shown in Figure 3.21. W e have five segments
numbered from 0 through 4. The segment table has a separate entry for each segment.
It is giving the beginning address of the segment in physical memory (or base) and the
length of that segment (or limit). For example, segment 2 is 400 bytes long and begins
at the location
4300.
29
29
3.12.3 Fragmentation
The long-term scheduler must find and allocate memory for all the segments of a user
program. This situation is similar to paging except that the segments are of variable length;
pages are all the same size. Thus, as with the variable-sized partition scheme,
memory allocation is a dynamic storage-allocation problem, usually solved with a best-fit
or first-fit algorithm. Segmentation may then cause external fragmentation, when all blocks
of free memory are too small to accommodate a segment. In this case, the process may
simply have to wait until more memory (or at least a larger hole) becomes available,
or until compaction creates a larger hole. Because segmentation is by its nature a
dynamic relocation algorithm, we can compact memory whenever we want. If the CPU
scheduler must wait for one process, because of a memory allocation problem, it may
(or may not) skip through the CPU queue looking for a smaller, lower-priority process to run.
Segmentation with paging is explained as below: Instead of an actual memory location, the
segment information includes the address of a page table for the segment. W hen
a program references a memory location the offset is translated to a memory address
using the page table. A segment can be extended simply by allocating another memory
page and adding it to the segment's page table. Also, the logical address space of a
process is divided into two partitions: one consisting of segments that are private to that
process, and the other partition consists of segments that can be shared among all the
processes.
(NOTE: Virtual Memory is the separation of user logical memory from physical memory. It
allows the execution of processes that may not be completely in memory. Hence, logical
address space can therefore be much larger than physical address space. Moreover, it
allows address spaces to be shared by several processes and also, allows for more
efficient process creation.)
Demand paging is similar to paging system with swapping. W henever process needs to
be executed, only the required pages are swapped into memory. This is called as
lazy swapping. As, the term swapper has a different meaning of ‘swapping entire
process into memory’, another term pager is used in the discussion of demand paging.
W hen a process is to be swapped in, the pager guesses which pages will be used
before the process is swapped out again. The pager brings only those necessary
pages into memory. Hence, it decreases the swap time and the amount of physical memory
needed.
In this scheme, we need to distinguish the pages which are in the memory and pages
which are there on the disk. For this purpose, the valid – invalid bit is used. W hen this bit is
set to valid, it indicates the page is in the memory. W hereas, the value of bit as
invalid indicates page is on the disk.
If the process tries to access a page which is not in the memory (means, it is on the disk),
page fault occurs. The paging hardware notices the invalid bit in the page table and cause
a trap to the OS. This trap is the result of the failure of OS to bring the desired page into
memory. This error has to be corrected. The procedure for handling this page fault is as
shown in Figure 3.22. The steps are explained below:
1. W e check an internal table (usually kept with the process control block) for
this process, to determine whether the reference was a valid or invalid memory
access.
2. If the reference was invalid, we terminate the process. If it was valid, but we have
not yet brought in that page into memory, it is brought now.
3. W e find a free frame.
31
4. W e schedule a disk operation to read the desired page into the newly 31
allocated frame.
32
32
5. W hen the disk read is complete, we modify the internal table kept with the
process and the page table to indicate that the page is now in memory.
6. W e restart the instruction that was interrupted by the illegal address trap. The
process can now access the page as though it had always been in memory.
It is important to realize that, because we save the state (registers, condition code,
instruction counter etc.) of the interrupted process when the page fault occurs, we can
restart the process in exactly the same place and state
In an extreme situation, a process may starts executing with no page in the memory.
So, each time an instruction has to be executed, page fault occurs and the required
page needs to be brought into the memory. This situation is called as pure demand
paging. That is, no page is brought into the memory until it is required.
3.15.1 Copy-on-Write
Usually, a system call fork() can be used to create a child process as a duplicate of
its parent. Alternatively, copy-on-write technique can be used. In this technique,
initially, parent and child processes share the same pages. These shared pages are
marked as copy-on-write pages. That is, if either process writes to a shared page, a copy of
the shared page is created. For example, assume the child process attempts to
33
modify a page 33
34
34
Now, OS has to make the frames free by swapping out some of the frames to disk
and bring newly requested pages into memory. This procedure is called as page
replacement.
(NOTE: W henever a page has to be swapped out, the question arises: whether this
page has to written back to disk? W riting is necessary if the page has been modified
during the process execution. Instead of writing every time a page is being swapped out,
a bit called as modify bit (or dirty bit) is introduced in the hardware. If any modification is
done, the bit is set, otherwise not. So, while swapping out a page, the value of this bit is
checked and the page is written to disk only if the bit is set. Otherwise, as the copy of the
page will always reside in the disk, it need not be written again.)
There are many page replacement algorithms. Every OS adopts its own page-replacement
scheme. The algorithm with the lowest page-fault rate must be chosen. Page-replacement
algorithm is evaluated by running it on a string of memory references (called as a
reference string). Normally, a reference string consists of the numbers indicating
the sequence of pages required by the process for execution. For applying any
algorithm for page – replacement, we must know the number of frames available.
for a page, it is checked inside the frames. If that page is not available, page – replacement
should take place.
NOTE that, the performance of FIFO page replacement algorithm is not good. Because, the
page that has been just swapped out may be needed immediately in the next step. This will
cause more page faults.
Sometimes, one may feel that increase in number of frames may decrease the page faults.
But this is not true always. For example, consider the reference string: 1, 2, 3, 4, 1, 2, 5, 1,
2, 3, 4, 5. Now, the number of page faults for three frames will be 9 and number of page
faults for four frames will be 10. Such an unexpected result is known as
Belady’s anomaly. It can be stated as: the page fault rate may increase as the number of
allocated frames increases.
Example:
37
37
Example:
NOTE: The major problem in LRU algorithm is hardware implementation. There are
two approaches for hardware implementation:
Counters: Each page table is associated with a time-of-use field and CPU is added
with a logical clock or counter. W hen a page needs to be changed, look at the
counters to determine which page has to be changed.
Stack: Keep a stack of page numbers. W henever a page is referenced, it
is removed from the stack and put on the top. In this way, the top of the stack is
always the most recently used page and the bottom is the least recently used
page. To maintain this stack, a doubly linked list can be used.
In a single processor system, if only one process has to be executed, all available frames
can be allocated to that process. If there are more pages than the frames, and the request
is made for a new page, then page – replacement has to be done. But, in case of
multiprogramming environment, there will be more than one process in memory at time.
Now, the logic used in single-processor system doesn’t work.
In most of the cases, as the number of frames allocated to each process decreases, the
page fault increases. This will slow down the process execution.
In general, each process should get a minimum number of frames. And this
minimum number is defined by the instruction –set architecture. Remember that, when a
page fault occurs before an executing instruction is complete, the instruction must be
restarted. Consequently, we must have enough frames to hold all the different pages that
any single instruction can reference. The maximum number of frames that can be
allocated to a process depends on available physical memory.
3.18 THRASHING
If the number of frames allocated to a low-priority process falls below the minimum number
required by the computer architecture, we must suspend the execution of that process. W
e should then page out its remaining pages, freeing all its allocated frames. This
provision introduces a swap-in, swap-out level of intermediate CPU scheduling.
W henever any process does not have enough frames, it will page-fault. At this point, it must
replace some page. However, since all its pages are in active use, it must replace a page
that will be needed again right away. Consequently, it quickly faults again, and again, and
again. The process continues to fault, replacing pages for which it then faults and
brings back in right away. This high paging activity is called thrashing. A process is
thrashing if it is spending more time paging than executing.