# Tag Info

## Hot answers tagged paging

18

I can see why you're confused. The diagram is a bit confusing, and may actually be incorrect. First off, let's think about why a kernel needs a memory allocator below the level of pages. This is probably already stuff that you mostly know, but I'll go through it for completeness. Pages are the typical "unit" of memory operations. When a user-space ...

9

I think this example can clarify all your doubts. For example: Assumes main memory is empty at the start page reference sequence is: 3 2 3 0 8 4 2 5 0 9 8 3 2 one reference bit per frame (called the "used" bit) P U 3 P U 2 P U 3 P U 0 P U 8 P U 4 +---+---+ +---+---+ +---+---+ +---+---+ +---+---+ +---+---+ | ...

8

A page is a region of virtual address space, and a page frame is a region of physical memory. A page which maps a region of physical memory must have the same size as that piece of physical memory, otherwise there's no point. They also typically must be aligned correctly. If you try to map, say, a 2Mb page frame into virtual memory, both the virtual address ...

8

If a reference arrives for a page already in memory, then the replacement algorithm doesn't get invoked at all. The clock replacement algorithm is trying to achieve some of the benefits of LRU replacement, but without the massive overhead of manipulating the LRU bits on every page hit. A page can be in one of three states: Present in memory and the ...

8

Emery Berger, Matthew Hertz & Yi Feng did some work on this. Garbage collection offers numerous software engineering advantages, but interacts poorly with virtual memory managers. Existing garbage collectors require far more pages than the application's working set and touch pages without regard to which ones are in memory, especially during ...

8

As I recall, copy collectors are supposed to be paging friendly, as the tracing by copying tends to improve the locality of pointer references. This has a positive effect on the program (mutator) that will cause less page faults when following links, and will also improve the next collection cycle as tracing will also cause less page faults. The tracing ...

8

I do not know the exact definitions of TLBs and look-ahead buffers, but here is what I understand about them. TLBs help make translations from virtual to physical addresses quicker via caching. So, you can see how the TLB is implementing temporal locality (any kind of caching is implementing temporal locality) in some sense. Look ahead buffers on the other ...

6

You are correct in your reasoning that the pages are $256$ bytes and that the physical memory capacity is $4096$ bytes. However, there are errors after that. The offset is the distance (in bytes) relative to the start of the page. I.e., logical_address mod page_size. The bits for this portion of the logical address are not translated (given power of two ...

6

The idea underneath the slab allocator is that the operating system needs specific but somewhat standard data structures (for example the process PCB, semaphores, file metadata etc) that suggest the memory usage that is necessary for them. The slab allocator algorithm provides stocks of memory areas whose dimensions and initialization are optimized for ...

6

As David Richerby says, it’s not clear what you don't understand.  Most of my answer here has already been presented in answers (or comments) to the questions you linked to. I’ll admit, though, that the Operating System Concepts book is probably not as clear as it should be. The book (going back to Figure 8.6 (Hardware support for relocation and limit ...

5

Well, this is the entire point of "virtual memory". When your program runs, the OS makes it believe it has all the memory just for itself. That is, addresses 1 to 10,000 (say), are all empty and ready for this program to use. If you run two programs, each one of them gets its own space - each one can access address 1 to 10,000 without any interference ...

5

LRU is most commonly used in 2-way associative caches, where it only requires a single bit that is set or cleared depending on the way accessed. (True LRU requires log2(N!) bits for N ways for each set.) For four-way and eight-way associativity, binary tree pseudo-LRU is commonly used, though some embedded systems might implement true LRU as such is easier ...

5

I think you need more than 2 page table levels. Here's what the page tables on AMD-64 (x86_64) look like. (This picture is from an article by Frank van der Linden about porting NetBSD to AMD-64.) Each page is 4K-byte and the system is byte-addressable so you need the bottom 12 bits of the virtual (logical) address to index into the physical page. The ...

5

Computer hardware is fundamentally parallel. Even a modern single CPU core is pipelined, meaning that at the same instant in time, one physical part of the CPU is initiating a fetch of an instruction, another is decoding a slightly earlier fetched instruction, another is calculating the new result of a slightly earlier decoded instruction, and another is ...

4

The Least-Recently Used (LRU) is a very common algorithm for page replacement, especially in system softwares that are exposed to data access of temporal locality.

4

why does it keep copy of instruction counter and register contents? It's because of process scheduling. Let's say a process comes in execution first time and executes some lines of instruction. The registers contain values as per the instructions executed till now. Now if the process switches from running state to waiting state (due to I/O or preemption) ...

4

You're looking at very vague descriptions and asking "What's the difference between these things that haven't been described properly?" For a more detailed understanding, you should, well, look for more detail, which is widely available. A page is a block of memory; a thread is a sequence of instructions to be executed.

4

The details depend on the processor architecture, but the principle is the same everywhere. All page tables of a given type at a given level have the same size. When all memory blocks have the same size, there is no fragmentation: a memory block is allocated starts at an offset which is a multiple of the block size, so the size of any hole is a multiple of ...

3

When we are using Virtual Memory, we are translating from a Virtual Address Space to a Physical Address Space. To understand why it requires $2^{35}$ entries, consider the page size. In order to byte address $8$KB, we require $2^{13}$ entries. If we consider the Virtual Address given to us of $48$ bits, this gives us $48-13=35$ bits. These are the bits that ...

3

Least recently used cache do the following things: we add the numbers to the top(front) representing that it is the "most recent" and thus the end of this will be the number which is least recent. If the cache is not full, 1 a). add to the cache if the entry is not in the cache. 1 b). If the entry is in cache we make that most recent and continue. If the ...

3

The virtual addresses must be canonical, the top 16 bits are all copies of the 48th bit. Using a non-canonical address (in the sense of using it as an address) generates a #GP. See also, the manual, volume 3, chapters 3 and 4. That is independent from the maximum physical address, which is not "canonical" in that way but just goes from 0 to some large ...

3

The CPU knows nothing about swapping. This is performed by the operating system. When a memory access takes place, the MMU consults page tables to find the physical address that is associated to a virtual address. Each page tables contains a number of descriptors that explain to the MMU what the physical address is. A page fault occurs when the descriptor ...

3

Clock is second chance. Given the same input they will both produce the same replacements at the same points in time. The only difference is the details of implementation. Second chance is usually described in terms of a "fifo" which is assumed to be a linked list where there is a pointer to the head and tail and every node contains a pointer to next. ...

3

Your answer and calculation is correct, if we used a one-level page table. However, a one-level page table is probably not a very likely implementation strategy, so it's more interesting to analyze the space consumption for a more plausible implementation strategy and work out what this would look like. A two-level page table is probably a more likely ...

3

Page table structure (and especially page table structure for software managed page tables) was a hot area of research in the mid 1990s. At its root this is just the problem of creating a data structure to represent a map from one set of integers (the keys (virtual addresses)) to another set of integers (physical addresses). So you should expect the answer ...

3

Since Logical address size is 47 bit, that means logical address space is 2^47 bytes ( assuming system is byte addressable ). Otherwise in general if the logical address is not given then also it can be found. Page size is 16 KB Logical address size is 47 bit 3 levels of page tables; all have the same size Page table entry size is 8 byte From the ...

3

Paging, caching, and buffering are too broad topics to cover in a single post. Briefly, they serve different purposes: Operating systems use paging as a memory management scheme. A computer stores and retrieves data from secondary storage (usually HDD) for use in main memory (RAM). For example, virtual memory implementations use paging. Page caching, on ...

3

Think of a simple scenario, where you have process A's page table. OS swaps out some of the pages, hence some of the page table entries will be invalidated and invalid bit has to be set. From Silberchatz, Section 9.4 Page replacement (Page 360): We can free a frame by writing its contents to swap space and changing the page table (and all other tables) to ...

3

Many people confuse these two bits. I'll try to explain the concept to best of my knowledge. Let's say we have 32 bit architecture. so process virtual address space(VAS) will have size of 2^32. VAS space of a process has kernel code and data part and user code and data part.Page table of process contains entries for both user/kernel part. kernel page table ...

3

Farthest-in-future is optimal, second chance can't be better. Second chance is a way to approximate LRU when the required hardware (access times, sort them) isn't available. Both try to approximate the optimal strategy, there certainly can be cases where one or the other is better.

Only top voted, non community-wiki answers of a minimum length are eligible