Hot answers tagged

14

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

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 ...


8

A computer typically has vastly more hard disk space that RAM. To compensate for limitations in the size of RAM, the operating system reserves part of the disk to use as additional RAM. This is called virtual memory. The RAM and the virtual memory are then divided into even chunks called pages. From the programmer's perspective, there is a large amount of ...


8

Since the number of frames is equal to the size of the memory divided by the page size, increasing the page size will proportionately decrease the number of frames. Having fewer frames will tend to increase the number of page faults because of the lower freedom in replacement choice. Imagine a system with four frames with the reference history of 0, 4, 3, ...


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 ...


7

To answer this question I will visit some prerequisite understanding. Pure demand paging cannot be accomplished without hardware support. All modern computer architectures support paging, however many have different implementation details. x86 processors use what is called a page table to keep track of virtual address spaces and page mappings, as well as ...


7

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 ...


7

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 ...


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 ...


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

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 ...


4

I am guessing that overheads P, S, and T exclude per page/segment overheads and are per-process overheads (if they are per-system overheads, the adjustments are obvious), so the overhead of each process would be P + page_count * 4 bytes for paging, S + segment_count * 8 bytes for segmentation, and T + segment_count * 8 bytes + page_count * 4 bytes for ...


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

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 ...


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

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

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

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

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) ...


3

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 ...


2

After careful reading i have come to understand that this is a complex behavior when the page size is doubled the page faults is reduced also when the page size is halved. The replacement algorithm considered is FIFO. note: page fault is denoted by p and no page fault by n number of frames = physical memory size / page size the page size = frame size ...


2

I see two possible flaws in your reasoning. 1) At least the first level of the page table is typically pinned in memory (so it could never cause a page fault). 2) The page fault rate is presumably independent of the TLB miss rate (i.e., it is page faults per access not page faults per TLB miss). This still will not provide an answer equal to any of the ...


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