Does The Os Manage Cpu Registers?

Main Retentiveness

References:

1. Abraham Silberschatz, Greg Gagne, and Peter Baer Galvin, "Operating Arrangement Concepts, Ninth Edition ", Chapter eight

8.1 Background

• Obviously memory accesses and memory direction are a very important role of modern calculator operation. Every instruction has to be fetched from memory before it can be executed, and most instructions involve retrieving data from retentiveness or storing data in memory or both.
• The appearance of multi-tasking OSes compounds the complexity of memory management, because because equally processes are swapped in and out of the CPU, and so must their code and data be swapped in and out of memory, all at high speeds and without interfering with any other processes.
• Shared memory, virtual memory, the classification of retention as read-only versus read-write, and concepts similar copy-on-write forking all farther complicate the result.

8.one.1 Basic Hardware

• It should be noted that from the memory chips signal of view, all memory accesses are equivalent. The retention hardware doesn't know what a particular office of memory is existence used for, nor does it care. This is nearly true of the Os as well, although not entirely.
• The CPU can only access its registers and main memory. It cannot, for instance, make direct access to the hard drive, so any information stored at that place must first be transferred into the main retention chips earlier the CPU can piece of work with information technology. ( Device drivers communicate with their hardware via interrupts and "memory" accesses, sending short instructions for example to transfer data from the hard drive to a specified location in main retentivity. The deejay controller monitors the bus for such instructions, transfers the data, and so notifies the CPU that the data is there with another interrupt, only the CPU never gets direct access to the deejay. )
• Memory accesses to registers are very fast, generally one clock tick, and a CPU may exist able to execute more than one machine education per clock tick.
• Memory accesses to main memory are comparatively tiresome, and may take a number of clock ticks to complete. This would require intolerable waiting by the CPU if information technology were not for an intermediary fast memory cache built into most modernistic CPUs. The basic idea of the cache is to transfer chunks of memory at a time from the main memory to the cache, and then to access individual retentivity locations one at a time from the enshroud.
• User processes must exist restricted then that they only access memory locations that "vest" to that particular process. This is usually implemented using a base of operations register and a limit register for each process, as shown in Figures viii.1 and 8.ii below. Every memory access made past a user process is checked against these two registers, and if a memory access is attempted outside the valid range, then a fatal fault is generated. The Os apparently has admission to all existing memory locations, as this is necessary to swap users' code and information in and out of memory. It should also be obvious that changing the contents of the base of operations and limit registers is a privileged activity, allowed only to the OS kernel.

Figure 8.1 - A base and a limit register define a logical addresss space

Figure 8.2 - Hardware address protection with base of operations and limit registers

8.1.two Address Binding

• User programs typically refer to memory addresses with symbolic names such equally "i", "count", and "averageTemperature". These symbolic names must be mapped or bound to physical retentiveness addresses, which typically occurs in several stages:
  • Compile Time - If it is known at compile fourth dimension where a program will reside in concrete memory, then absolute code can be generated by the compiler, containing actual physical addresses. However if the load address changes at some afterward time, and so the program will have to exist recompiled. DOS .COM programs use compile time binding.
  • Load Time - If the location at which a programme volition be loaded is not known at compile fourth dimension, then the compiler must generate relocatable lawmaking , which references addresses relative to the commencement of the programme. If that starting address changes, and then the plan must exist reloaded merely not recompiled.
  • Execution Time - If a program can be moved around in retention during the grade of its execution, then bounden must be delayed until execution time. This requires special hardware, and is the method implemented by most mod OSes.
• Figure 8.3 shows the diverse stages of the binding processes and the units involved in each phase:

Figure viii.iii - Multistep processing of a user program

8.i.3 Logical Versus Physical Accost Space

• The accost generated by the CPU is a logical address , whereas the address actually seen by the memory hardware is a physical address .
• Addresses leap at compile time or load time take identical logical and concrete addresses.
• Addresses created at execution time, however, have different logical and physical addresses.
  • In this instance the logical address is also known as a virtual address , and the two terms are used interchangeably by our text.
  • The set of all logical addresses used past a program composes the logical address infinite , and the set of all corresponding physical addresses composes the physical accost infinite.
• The run time mapping of logical to physical addresses is handled by the memory-direction unit, MMU .
  • The MMU tin have on many forms. Ane of the simplest is a modification of the base-register scheme described earlier.
  • The base register is now termed a relocation register , whose value is added to every memory asking at the hardware level.
• Note that user programs never see physical addresses. User programs piece of work entirely in logical accost space, and whatever retentiveness references or manipulations are washed using purely logical addresses. Just when the address gets sent to the physical memory chips is the physical retentiveness address generated.

Effigy 8.four - Dynamic relocation using a relocation register

8.1.iv Dynamic Loading

• Rather than loading an entire program into memory at once, dynamic loading loads upwardly each routine equally it is called. The advantage is that unused routines need never be loaded, reducing full memory usage and generating faster program startup times. The downside is the added complexity and overhead of checking to see if a routine is loaded every time it is called and then and so loading it up if information technology is non already loaded.

eight.1.5 Dynamic Linking and Shared Libraries

• With static linking library modules get fully included in executable modules, wasting both deejay space and chief retentiveness usage, because every program that included a certain routine from the library would accept to have their own re-create of that routine linked into their executable code.
• With dynamic linking , nevertheless, only a stub is linked into the executable module, containing references to the actual library module linked in at run time.
  • This method saves disk space, considering the library routines do non need to be fully included in the executable modules, but the stubs.
  • We will also larn that if the code section of the library routines is reentrant , ( meaning it does not alter the code while it runs, making information technology condom to re-enter it ), then main retentivity can be saved past loading but ane copy of dynamically linked routines into memory and sharing the code amongst all processes that are meantime using it. ( Each process would take their own copy of the data section of the routines, but that may exist small-scale relative to the code segments. ) Obviously the OS must manage shared routines in retentiveness.
  • An added benefit of dynamically linked libraries ( DLLs , also known as shared libraries or shared objects on UNIX systems ) involves piece of cake upgrades and updates. When a program uses a routine from a standard library and the routine changes, then the plan must exist re-built ( re-linked ) in order to incorporate the changes. Even so if DLLs are used, and then as long as the stub doesn't change, the program can be updated merely by loading new versions of the DLLs onto the system. Version information is maintained in both the programme and the DLLs, so that a programme can specify a particular version of the DLL if necessary.
  • In practice, the start fourth dimension a program calls a DLL routine, the stub will recognize the fact and will replace itself with the actual routine from the DLL library. Further calls to the same routine volition access the routine directly and non incur the overhead of the stub access. ( Following the UML Proxy Pattern . )
  • ( Boosted information regarding dynamic linking is available at http://www.iecc.com/linker/linker10.html )

8.2 Swapping

• A process must be loaded into retention in order to execute.
• If there is not enough retentivity available to proceed all running processes in memory at the same time, then some processes who are non currently using the CPU may have their memory swapped out to a fast local disk called the backing store.

eight.two.1 Standard Swapping

• If compile-time or load-fourth dimension address binding is used, and so processes must exist swapped back into the same memory location from which they were swapped out. If execution time bounden is used, then the processes can be swapped back into any available location.
• Swapping is a very slow process compared to other operations. For example, if a user process occupied ten MB and the transfer charge per unit for the backing store were xl MB per second, then it would accept i/four second ( 250 milliseconds ) just to do the data transfer. Calculation in a latency lag of eight milliseconds and ignoring caput seek time for the moment, and farther recognizing that swapping involves moving former data out as well every bit new data in, the overall transfer time required for this swap is 512 milliseconds, or over one-half a 2nd. For efficient processor scheduling the CPU fourth dimension piece should be significantly longer than this lost transfer time.
• To reduce swapping transfer overhead, it is desired to transfer as fiddling data every bit possible, which requires that the system know how much memory a procedure is using, as opposed to how much it might utilize. Programmers can assist with this by freeing up dynamic memory that they are no longer using.
• It is important to swap processes out of retention only when they are idle, or more to the point, but when there are no pending I/O operations. ( Otherwise the awaiting I/O operation could write into the wrong process'southward memory space. ) The solution is to either swap simply totally idle processes, or do I/O operations only into and out of Os buffers, which are then transferred to or from process's master retentivity as a second stride.
• Most modern OSes no longer use swapping, because information technology is as well slow and there are faster alternatives available. ( e.yard. Paging. ) Yet some UNIX systems will still invoke swapping if the system gets extremely full, and then discontinue swapping when the load reduces again. Windows iii.1 would use a modified version of swapping that was somewhat controlled by the user, swapping process'south out if necessary and so only swapping them back in when the user focused on that particular window.

Effigy 8.5 - Swapping of two processes using a disk as a backing store

eight.2.2 Swapping on Mobile Systems ( New Section in 9th Edition )

• Swapping is typically non supported on mobile platforms, for several reasons:
  • Mobile devices typically apply flash retention in place of more spacious hard drives for persistent storage, and then at that place is not as much space available.
  • Flash memory tin only exist written to a limited number of times before it becomes unreliable.
  • The bandwidth to flash memory is also lower.
• Apple tree's IOS asks applications to voluntarily free up retention
  • Read-just data, eastward.thou. code, is simply removed, and reloaded afterwards if needed.
  • Modified data, e.g. the stack, is never removed, merely . . .
  • Apps that fail to free upwardly sufficient memory can be removed by the OS
• Android follows a similar strategy.
  • Prior to terminating a process, Android writes its application country to flash memory for quick restarting.

eight.3 Face-to-face Memory Allocation

• One approach to memory management is to load each process into a contiguous infinite. The operating system is allocated infinite commencement, usually at either low or high memory locations, then the remaining available memory is allocated to processes equally needed. ( The Bone is usually loaded low, because that is where the interrupt vectors are located, but on older systems office of the OS was loaded high to make more room in depression memory ( within the 640K barrier ) for user processes. )

8.3.1 Memory Protection ( was Memory Mapping and Protection )

• The organisation shown in Figure viii.half-dozen beneath allows protection against user programs accessing areas that they should not, allows programs to exist relocated to different memory starting addresses as needed, and allows the memory space devoted to the Os to grow or shrink dynamically as needs change.

Figure 8.6 - Hardware support for relocation and limit registers

eight.3.ii Retentiveness Allotment

• One method of allocating contiguous memory is to divide all bachelor memory into equal sized partitions, and to assign each process to their own division. This restricts both the number of simultaneous processes and the maximum size of each process, and is no longer used.
• An alternate arroyo is to keep a list of unused ( gratis ) memory blocks ( holes ), and to find a hole of a suitable size whenever a procedure needs to be loaded into memory. There are many unlike strategies for finding the "all-time" allocation of memory to processes, including the iii most commonly discussed:
  1. Outset fit - Search the list of holes until one is found that is big enough to satisfy the asking, and assign a portion of that pigsty to that process. Any fraction of the hole not needed by the request is left on the free list every bit a smaller hole. Subsequent requests may start looking either from the beginning of the listing or from the signal at which this search ended.
  2. Best fit - Classify the smallest pigsty that is big enough to satisfy the asking. This saves large holes for other procedure requests that may need them later, but the resulting unused portions of holes may be too small to be of any use, and volition therefore exist wasted. Keeping the free list sorted can speed upward the process of finding the right hole.
  3. Worst fit - Classify the largest hole available, thereby increasing the likelihood that the remaining portion will be usable for satisfying future requests.
• Simulations testify that either beginning or best fit are ameliorate than worst fit in terms of both time and storage utilization. First and best fits are virtually equal in terms of storage utilization, but commencement fit is faster.

8.3.3. Fragmentation

• All the retention allotment strategies suffer from external fragmentation , though first and all-time fits feel the problems more so than worst fit. External fragmentation means that the available memory is broken up into lots of piddling pieces, none of which is big plenty to satisfy the next memory requirement, although the sum total could.
• The corporeality of retention lost to fragmentation may vary with algorithm, usage patterns, and some pattern decisions such equally which end of a hole to allocate and which end to salvage on the free list.
• Statistical assay of first fit, for example, shows that for N blocks of allocated memory, another 0.v N volition be lost to fragmentation.
• Internal fragmentation also occurs, with all retentiveness allocation strategies. This is acquired by the fact that retentiveness is allocated in blocks of a fixed size, whereas the actual memory needed will rarely be that exact size. For a random distribution of retentiveness requests, on the average 1/two cake will exist wasted per memory asking, considering on the average the last allocated block volition exist only one-half full.
  • Annotation that the aforementioned effect happens with hard drives, and that modern hardware gives united states of america increasingly larger drives and memory at the expense of ever larger block sizes, which translates to more memory lost to internal fragmentation.
  • Some systems utilize variable size blocks to minimize losses due to internal fragmentation.
• If the programs in memory are relocatable, ( using execution-fourth dimension address binding ), then the external fragmentation trouble can be reduced via compaction , i.e. moving all processes down to one end of physical memory. This but involves updating the relocation register for each process, as all internal work is done using logical addresses.
• Another solution as we volition come across in upcoming sections is to allow processes to use non-contiguous blocks of concrete memory, with a dissever relocation annals for each cake.

8.4 Partition

8.4.i Basic Method

• Nearly users ( programmers ) practice not recall of their programs as existing in one continuous linear accost space.
• Rather they tend to think of their memory in multiple segments , each dedicated to a detail utilise, such as lawmaking, data, the stack, the heap, etc.
• Retentiveness segmentation supports this view by providing addresses with a segment number ( mapped to a segment base accost ) and an get-go from the beginning of that segment.
• For example, a C compiler might generate 5 segments for the user code, library code, global ( static ) variables, the stack, and the heap, equally shown in Figure 8.7:

Figure 8.7 Programmer'southward view of a program.

8.four.2 Sectionalisation Hardware

• A segment tabular array maps segment-offset addresses to physical addresses, and simultaneously checks for invalid addresses, using a organisation similar to the page tables and relocation base registers discussed previously. ( Note that at this point in the discussion of partitioning, each segment is kept in contiguous memory and may be of different sizes, but that division can likewise exist combined with paging equally we shall see presently. )

Figure 8.viii - Segmentation hardware

Figure viii.9 - Case of division

viii.five Paging

• Paging is a retentivity management scheme that allows processes physical retentivity to be discontinuous, and which eliminates issues with fragmentation by allocating memory in equal sized blocks known every bit pages .
• Paging eliminates nearly of the issues of the other methods discussed previously, and is the predominant retentiveness management technique used today.

viii.v.1 Basic Method

• The basic thought behind paging is to divide physical memory into a number of equal sized blocks called frames , and to divide a programs logical memory space into blocks of the aforementioned size chosen pages.
• Any folio ( from any procedure ) tin be placed into whatsoever available frame.
• The page table is used to await up what frame a particular page is stored in at the moment. In the following example, for instance, page 2 of the programme'southward logical memory is currently stored in frame three of physical memory:

Figure 8.10 - Paging hardware

Figure eight.eleven - Paging model of logical and physical memory

• A logical address consists of two parts: A page number in which the address resides, and an first from the kickoff of that folio. ( The number of bits in the page number limits how many pages a unmarried process tin can address. The number of bits in the offset determines the maximum size of each folio, and should stand for to the organisation frame size. )
• The page tabular array maps the page number to a frame number, to yield a physical address which likewise has two parts: The frame number and the starting time within that frame. The number of bits in the frame number determines how many frames the arrangement can address, and the number of bits in the offset determines the size of each frame.
• Page numbers, frame numbers, and frame sizes are determined by the compages, but are typically powers of ii, allowing addresses to be carve up at a certain number of bits. For case, if the logical address size is 2^m and the page size is 2^north, then the high-lodge m-n bits of a logical address designate the page number and the remaining north bits represent the starting time.
• Note also that the number of $.25 in the folio number and the number of bits in the frame number exercise not have to exist identical. The one-time determines the accost range of the logical accost space, and the latter relates to the concrete address space.

• ( DOS used to use an addressing scheme with 16 chip frame numbers and 16-bit offsets, on hardware that simply supported 24-bit hardware addresses. The result was a resolution of starting frame addresses finer than the size of a single frame, and multiple frame-beginning combinations that mapped to the same physical hardware address. )
• Consider the following micro example, in which a process has 16 bytes of logical retentivity, mapped in 4 byte pages into 32 bytes of physical retention. ( Presumably some other processes would be consuming the remaining sixteen bytes of physical retention. )

Figure 8.12 - Paging example for a 32-byte retentivity with 4-byte pages

• Note that paging is like having a tabular array of relocation registers, one for each folio of the logical memory.
• At that place is no external fragmentation with paging. All blocks of concrete retentiveness are used, and at that place are no gaps in between and no bug with finding the right sized hole for a particular clamper of memory.
• At that place is, nonetheless, internal fragmentation. Retention is allocated in chunks the size of a folio, and on the average, the last page volition only be one-half total, wasting on the average one-half a page of memory per process. ( Possibly more, if processes keep their code and information in separate pages. )
• Larger page sizes waste matter more memory, simply are more efficient in terms of overhead. Modernistic trends have been to increment folio sizes, and some systems even accept multiple size pages to try and make the best of both worlds.
• Page tabular array entries ( frame numbers ) are typically 32 bit numbers, allowing access to 2^32 physical folio frames. If those frames are 4 KB in size each, that translates to 16 TB of addressable physical memory. ( 32 + 12 = 44 bits of concrete address space. )
• When a process requests memory ( e.g. when its lawmaking is loaded in from disk ), complimentary frames are allocated from a gratis-frame list, and inserted into that process's page table.
• Processes are blocked from accessing anyone else'southward memory because all of their retentivity requests are mapped through their folio tabular array. There is no fashion for them to generate an address that maps into any other process'southward memory space.
• The operating system must keep track of each individual process'due south page tabular array, updating information technology whenever the process'southward pages become moved in and out of memory, and applying the correct page table when processing organization calls for a particular process. This all increases the overhead involved when swapping processes in and out of the CPU. ( The currently active page tabular array must exist updated to reverberate the process that is currently running. )

Figure 8.xiii - Free frames (a) before allocation and (b) later allocation

8.5.2 Hardware Support

• Page lookups must be done for every retentivity reference, and whenever a procedure gets swapped in or out of the CPU, its page tabular array must be swapped in and out too, along with the instruction registers, etc. Information technology is therefore appropriate to provide hardware support for this functioning, in order to get in as fast as possible and to make process switches every bit fast as possible besides.
• One option is to apply a set of registers for the page table. For example, the DEC PDP-11 uses 16-bit addressing and 8 KB pages, resulting in only viii pages per procedure. ( It takes 13 bits to address viii KB of outset, leaving only 3 $.25 to define a page number. )
• An alternate option is to shop the page table in main retentiveness, and to use a single register ( chosen the folio-table base of operations register, PTBR ) to tape where in memory the page tabular array is located.
  • Process switching is fast, because only the single annals needs to exist changed.
  • Still memory access just got half every bit fast, because every retention access now requires two memory accesses - 1 to fetch the frame number from memory so some other one to access the desired memory location.
  • The solution to this trouble is to use a very special high-speed memory device called the translation look-aside buffer, TLB.
    • The benefit of the TLB is that it tin search an entire table for a primal value in parallel, and if information technology is found anywhere in the tabular array, then the corresponding lookup value is returned.

    
    Effigy 8.14 - Paging hardware with TLB

    • The TLB is very expensive, all the same, and therefore very minor. ( Non large plenty to concord the unabridged page table. ) It is therefore used equally a cache device.
      • Addresses are first checked against the TLB, and if the info is not in that location ( a TLB miss ), and so the frame is looked upward from main memory and the TLB is updated.
      • If the TLB is full, then replacement strategies range from least-recently used, LRU to random.
      • Some TLBs permit some entries to be wired downwards , which ways that they cannot exist removed from the TLB. Typically these would exist kernel frames.
      • Some TLBs store address-space identifiers, ASIDs , to keep runway of which process "owns" a detail entry in the TLB. This allows entries from multiple processes to be stored simultaneously in the TLB without granting 1 process access to some other process's memory location. Without this feature the TLB has to be flushed clean with every process switch.
    • The per centum of time that the desired information is establish in the TLB is termed the hitting ratio .
    • ( Eighth Edition Version: ) For example, suppose that it takes 100 nanoseconds to access main memory, and only xx nanoseconds to search the TLB. And then a TLB hit takes 120 nanoseconds total ( twenty to find the frame number and then some other 100 to get become the data ), and a TLB miss takes 220 ( twenty to search the TLB, 100 to go get the frame number, and so another 100 to get get the data. ) So with an eighty% TLB hit ratio, the average memory access time would be:

    0.80 * 120 + 0.20 * 220 = 140 nanoseconds

    for a 40% slowdown to get the frame number. A 98% hit rate would yield 122 nanoseconds average admission fourth dimension ( you lot should verify this ), for a 22% slowdown.

    • ( Ninth Edition Version: ) The ninth edition ignores the 20 nanoseconds required to search the TLB, yielding

    0.lxxx * 100 + 0.20 * 200 = 120 nanoseconds

    for a 20% slowdown to get the frame number. A 99% hitting rate would yield 101 nanoseconds boilerplate access fourth dimension ( you should verify this ), for a 1% slowdown.

eight.5.3 Protection

• The page table can also assistance to protect processes from accessing memory that they shouldn't, or their ain retentivity in ways that they shouldn't.
• A chip or bits can exist added to the page table to classify a page as read-write, read-only, read-write-execute, or some combination of these sorts of things. Then each memory reference can be checked to ensure it is accessing the memory in the appropriate mode.
• Valid / invalid bits can be added to "mask off" entries in the folio table that are not in use by the current procedure, every bit shown by instance in Figure 8.12 beneath.
• Note that the valid / invalid bits described to a higher place cannot block all illegal memory accesses, due to the internal fragmentation. ( Areas of memory in the last page that are not entirely filled by the procedure, and may incorporate data left over by whoever used that frame last. )
• Many processes do not utilize all of the page tabular array available to them, particularly in modern systems with very large potential page tables. Rather than waste material memory by creating a full-size page table for every procedure, some systems use a page-table length register, PTLR , to specify the length of the page table.

Figure eight.fifteen - Valid (v) or invalid (i) bit in page tabular array

eight.5.iv Shared Pages

• Paging systems can make it very easy to share blocks of retentiveness, by but duplicating page numbers in multiple page frames. This may exist washed with either lawmaking or information.
• If code is reentrant , that ways that it does not write to or change the lawmaking in whatsoever mode ( information technology is non self-modifying ), and it is therefore safe to re-enter it. More importantly, it means the lawmaking tin be shared by multiple processes, so long as each has their own copy of the data and registers, including the pedagogy register.
• In the example given below, three different users are running the editor simultaneously, simply the code is only loaded into memory ( in the page frames ) i time.
• Some systems too implement shared retentiveness in this fashion.

Figure viii.16 - Sharing of lawmaking in a paging environs

eight.6 Structure of the Page Tabular array

8.vi.1 Hierarchical Paging

• Most mod computer systems support logical address spaces of 2^32 to ii^64.
• With a two^32 address space and 4K ( ii^12 ) page sizes, this get out 2^20 entries in the page table. At 4 bytes per entry, this amounts to a 4 MB folio table, which is too large to reasonably keep in face-to-face retentivity. ( And to swap in and out of retentivity with each procedure switch. ) Note that with 4K pages, this would accept 1024 pages just to concord the folio table!
• One option is to utilise a ii-tier paging organization, i.east. to page the page table.
• For instance, the 20 $.25 described above could be broken down into two 10-bit page numbers. The first identifies an entry in the outer folio table, which identifies where in memory to detect 1 page of an inner page table. The second 10 bits finds a specific entry in that inner page table, which in turn identifies a particular frame in physical memory. ( The remaining 12 bits of the 32 bit logical address are the offset inside the 4K frame. )

Figure 8.17 A two-level page-table scheme

Figure viii.18 - Address translation for a ii-level 32-scrap paging architecture

• VAX Architecture divides 32-bit addresses into four equal sized sections, and each page is 512 bytes, yielding an accost form of:

• With a 64-bit logical address space and 4K pages, there are 52 bits worth of page numbers, which is still too many fifty-fifty for two-level paging. I could increase the paging level, but with 10-bit page tables it would have 7 levels of indirection, which would exist prohibitively slow retentivity admission. So another approach must be used.

64-bits Two-tiered leaves 42 $.25 in outer table

Going to a fourth level still leaves 32 bits in the outer tabular array.

8.6.ii Hashed Folio Tables

• Ane common data construction for accessing data that is sparsely distributed over a broad range of possible values is with hash tables . Figure 8.xvi below illustrates a hashed page table using chain-and-bucket hashing:

Figure eight.nineteen - Hashed page tabular array

8.half-dozen.3 Inverted Page Tables

• Some other approach is to utilise an inverted page table . Instead of a table listing all of the pages for a detail process, an inverted page table lists all of the pages currently loaded in memory, for all processes. ( I.e. there is ane entry per frame instead of ane entry per page . )
• Admission to an inverted page table tin can be tiresome, every bit it may be necessary to search the entire table in order to discover the desired page ( or to discover that it is not there. ) Hashing the table can help speedup the search procedure.
• Inverted folio tables prohibit the normal method of implementing shared retentiveness, which is to map multiple logical pages to a mutual physical frame. ( Because each frame is now mapped to one and just one process. )

Figure 8.20 - Inverted page tabular array

eight.6.4 Oracle SPARC Solaris ( Optional, New Department in 9th Edition )

8.7 Example: Intel 32 and 64-bit Architectures ( Optional )

8.7.ane.i IA-32 Segmentation

• The Pentium CPU provides both pure sectionalization and partitioning with paging. In the latter case, the CPU generates a logical accost ( segment-first pair ), which the partitioning unit of measurement converts into a logical linear address, which in turn is mapped to a physical frame by the paging unit, as shown in Figure 8.21:

Figure 8.21 - Logical to physical accost translation in IA-32

8.7.1.ane IA-32 Sectionalization

• The Pentium architecture allows segments to be equally large every bit iv GB, ( 24 bits of offset ).
• Processes can have as many as 16K segments, divided into two 8K groups:
  • 8K private to that particular process, stored in the Local Descriptor Tabular array, LDT.
  • 8K shared amid all processes, stored in the Global Descriptor Table, GDT.
• Logical addresses are ( selector, offset ) pairs, where the selector is fabricated upwards of 16 $.25:
  • A xiii bit segment number ( up to 8K )
  • A 1 bit flag for LDT vs. GDT.
  • 2 bits for protection codes.

• The descriptor tables contain viii-byte descriptions of each segment, including base of operations and limit registers.
• Logical linear addresses are generated by looking the selector up in the descriptor table and adding the appropriate base of operations address to the starting time, every bit shown in Effigy 8.22:

Figure 8.22 - IA-32 sectionalisation

eight.vii.1.ii IA-32 Paging

• Pentium paging normally uses a two-tier paging scheme, with the beginning 10 $.25 being a page number for an outer page table ( a.k.a. page directory ), and the next ten bits being a folio number within one of the 1024 inner page tables, leaving the remaining 12 bits equally an get-go into a 4K folio.

• A special chip in the page directory tin can indicate that this page is a 4MB page, in which case the remaining 22 bits are all used every bit offset and the inner tier of folio tables is not used.
• The CR3 register points to the folio directory for the electric current process, every bit shown in Figure 8.23 below.
• If the inner folio table is currently swapped out to disk, and so the page directory volition have an "invalid bit" set up, and the remaining 31 $.25 provide data on where to find the swapped out page table on the disk.

Figure 8.23 - Paging in the IA-32 compages.

Figure 8.24 - Page address extensions.

8.7.2 x86-64

Effigy 8.25 - x86-64 linear address.

8.eight Example: ARM Architecture ( Optional )

Effigy 8.26 - Logical accost translation in ARM.

---

Erstwhile viii.7.3 Linux on Pentium Systems - Omitted from the Ninth Edition

• Considering Linux is designed for a wide multifariousness of platforms, some of which offer only express support for partition, Linux supports minimal segmentation. Specifically Linux uses only 6 segments:
  1. Kernel code.
  2. Kerned data.
  3. User code.
  4. User data.
  5. A task-land segment, TSS
  6. A default LDT segment
• All processes share the same user code and data segments, because all process share the aforementioned logical address space and all segment descriptors are stored in the Global Descriptor Table. ( The LDT is more often than not non used. )
• Each process has its own TSS, whose descriptor is stored in the GDT. The TSS stores the hardware country of a process during context switches.
• The default LDT is shared by all processes and generally not used, simply if a process needs to create its own LDT, it may exercise so, and employ that instead of the default.
• The Pentium architecture provides two $.25 ( 4 values ) for protection in a segment selector, but Linux just uses 2 values: user mode and kernel way.
• Because Linux is designed to run on 64-flake equally well every bit 32-fleck architectures, it employs a three-level paging strategy equally shown in Effigy viii.24, where the number of $.25 in each portion of the address varies by architecture. In the case of the Pentium architecture, the size of the middle directory portion is set to 0 $.25, effectively bypassing the middle directory.

viii.8 Summary

• ( For a fun and easy explanation of paging, y'all may desire to read well-nigh The Paging Game. )

Does The Os Manage Cpu Registers?,

Source: https://www.cs.uic.edu/~jbell/CourseNotes/OperatingSystems/8_MainMemory.html

Posted by: younkershescial.blogspot.com

Share this post