IT 315 Information Technology Questions

What is the difference between Windows and UNIX permissions? (Hint: Bitmask 1010 666)

What is the bitmask in UNIX for all users to have all rights?

What did you like the most about this class?

What could be incorporated to enhance this class?

Chapter 2
Early Memory Management Systems
Understanding Operating Systems,8e
© 2018 Cengage. All Rights Reserved. May not be copied, scanned, or duplicated, in whole or in part, except for use as permitted in a license distributed with
a certain product or service or otherwise on a password-protected website for classroom use.
1
Learning Objectives
After completing this chapter, you should be able to describe:
• How four memory allocation schemes in this chapter manage incoming jobs
• How two memory allocation systems work: best-fit and first-fit
• How a memory list is used to keep the status of available memory
• The essential role of memory deallocation, and the consequences if it isn’t
performed
• How compaction can improve memory allocation efficiency
© 2018 Cengage. All Rights Reserved. May not be copied, scanned, or duplicated, in whole or in part, except for use as permitted in a license distributed
with a certain product or service or otherwise on a password-protected website for classroom use.
2
Introduction (1 of 2)
• Main memory management is critical
• Entire system performance is dependent on two items:
• Amount of memory available
• Optimization of memory during job processing
© 2018 Cengage. All Rights Reserved. May not be copied, scanned, or duplicated, in whole or in part, except for use as permitted in a license distributed
with a certain product or service or otherwise on a password-protected website for classroom use.
3
Introduction (2 of 2)
• This chapter introduces:
• Role of main memory (RAM)
• Four types: memory allocation schemes
– Single-user systems
– Fixed partitions
– Dynamic partitions
– Relocatable dynamic partitions
© 2018 Cengage. All Rights Reserved. May not be copied, scanned, or duplicated, in whole or in part, except for use as permitted in a license distributed
with a certain product or service or otherwise on a password-protected website for classroom use.
4
Single-User Contiguous Scheme (1 of 2)
• Entire program: loaded into memory
• Contiguous memory space: allocated as needed
• Jobs: processed sequentially
• Memory Manager: performs minimal work
• Evaluates incoming process size: loads if small enough to fit; otherwise, rejects and
evaluates next incoming process
• Monitors occupied memory space; when process ends, makes entire memory space
available and returns to Step 1
© 2018 Cengage. All Rights Reserved. May not be copied, scanned, or duplicated, in whole or in part, except for use as permitted in a license distributed
with a certain product or service or otherwise on a password-protected website for classroom use.
5
Single-User Contiguous Scheme (2 of 2)
• Disadvantages
• Multiprogramming or networking not supported
• Not cost effective: unsuitable for business when introduced in late 1940s and early
1950s
© 2018 Cengage. All Rights Reserved. May not be copied, scanned, or duplicated, in whole or in part, except for use as permitted in a license distributed
with a certain product or service or otherwise on a password-protected website for classroom use.
6
Fixed Partitions (1 of 4)
• Permits multiprogramming
• Main memory: partitioned
• Each partition: one job
• Static: reconfiguration requires system shut down
• Responsibilities
• Protecting each job’s memory space
• Matching job size with partition size
© 2018 Cengage. All Rights Reserved. May not be copied, scanned, or duplicated, in whole or in part, except for use as permitted in a license distributed
with a certain product or service or otherwise on a password-protected website for classroom use.
7
Fixed Partitions (2 of 4)
• Memory Manager: allocates memory space to jobs
• Information: stored in a table
(table 2.1)
A simplified fixed-partition memory table for several small jobs with the free partition
shaded.
© Cengage Learning 2018
© 2018 Cengage. All Rights Reserved. May not be copied, scanned, or duplicated, in whole or in part, except for use as permitted in a license distributed
with a certain product or service or otherwise on a password-protected website for classroom use.
8
Fixed Partitions (3 of 4)
(figure 2.2)
As the small jobs listed in Table 2.1 are loaded into the four fixed partitions, Job 3 must wait, even
though Partition 1 has 70K of available memory. These jobs are allocated space on the basis of
“first available partition that accommodates the job’s size.”
© Cengage Learning 2018
© 2018 Cengage. All Rights Reserved. May not be copied, scanned, or duplicated, in whole or in part, except for use as permitted in a license distributed
with a certain product or service or otherwise on a password-protected website for classroom use.
9
Fixed Partitions (4 of 4)
• Characteristics
• Requires contiguous loading of entire program
• Job allocation method
– First available partition with required size
• To work well:
– All jobs have similar size and memory size known ahead of time
• Arbitrary partition size leads to undesired results
– Partition too small
• Large jobs have longer turnaround time
– Partition too large
• Memory waste: internal fragmentation
© 2018 Cengage. All Rights Reserved. May not be copied, scanned, or duplicated, in whole or in part, except for use as permitted in a license distributed
with a certain product or service or otherwise on a password-protected website for classroom use.
10
Dynamic Partitions (1 of 2)
• Main memory: partitioned
• Jobs: given requested memory when loaded
• One contiguous partition per job
• Job allocation method
• First come, first serve
• Memory waste: comparatively small within partitions
• Disadvantages
• Full memory utilization: only when first jobs loaded
• Subsequent allocation: memory waste
– External fragmentation: fragments between blocks
© 2018 Cengage. All Rights Reserved. May not be copied, scanned, or duplicated, in whole or in part, except for use as permitted in a license distributed
with a certain product or service or otherwise on a password-protected website for classroom use.
11
Dynamic Partitions (2 of 2)
(figure 2.3)
Main memory use during
dynamic partition allocation.
Five snapshots (a-e) of main
memory as eight jobs are
submitted for processing and
allocated space on the basis of
“first come, first served.” Job 8
has to wait (e) even though
there’s enough free memory
between partitions to
accommodate it.
© Cengage Learning 2018
© 2018 Cengage. All Rights Reserved. May not be copied, scanned, or duplicated, in whole or in part, except for use as permitted in a license distributed
with a certain product or service or otherwise on a password-protected website for classroom use.
12
Best-Fit and First-Fit Allocation (1 of 10)
• Two methods for free space allocation
• First-fit memory allocation
– Memory Manager: free/busy lists organized by memory locations (low- to high-order memory)
– Job: assigned first partition large enough
– Fast allocation
• Best-fit memory allocation
– Memory Manager: free/busy lists ordered by size (smallest to largest)
– Job: assigned smallest partition large enough
– Least wasted space; internal fragmentation reduced
© 2018 Cengage. All Rights Reserved. May not be copied, scanned, or duplicated, in whole or in part, except for use as permitted in a license distributed
with a certain product or service or otherwise on a password-protected website for classroom use.
13
Best-Fit and First-Fit Allocation (2 of 10)
• Fixed and dynamic memory allocation schemes: use both methods
• First-fit memory allocation
• Advantage: faster allocation
• Disadvantage: memory waste
• Best-fit memory allocation
• Advantage: best use of memory space
• Disadvantage: slower allocation
© 2018 Cengage. All Rights Reserved. May not be copied, scanned, or duplicated, in whole or in part, except for use as permitted in a license distributed
with a certain product or service or otherwise on a password-protected website for classroom use.
14
Best-Fit and First-Fit Allocation (3 of 10)
(figure 2.5)
Using a first-fit scheme, Job 1 claims the first available space. Job 2 then claims the first partition large
enough to accommodate it, but by doing so it takes the last block large enough to accommodate Job 3.
Therefore, Job 3 (indicated by the asterisk) must wait until a large block becomes available, even though
there’s 75K of unused memory space (internal fragmentation). Notice that the memory list is ordered
according to memory location.
© Cengage Learning 2018
© 2018 Cengage. All Rights Reserved. May not be copied, scanned, or duplicated, in whole or in part, except for use as permitted in a license distributed
with a certain product or service or otherwise on a password-protected website for classroom use.
15
Best-Fit and First-Fit Allocation (4 of 10)
(figure 2.6)
Best-fit free scheme. Job 1 is allocated to the closest-fitting free partition, as are Job 2 and Job 3. Job 4
is allocated to the only available partition although it isn’t the best-fitting one. In this scheme, all four
jobs are served without waiting. Notice that the memory list is ordered according to memory size. This
scheme uses memory more efficiently but it’s slower to implement.
© Cengage Learning 2018
© 2018 Cengage. All Rights Reserved. May not be copied, scanned, or duplicated, in whole or in part, except for use as permitted in a license distributed
with a certain product or service or otherwise on a password-protected website for classroom use.
16
Best-Fit and First-Fit Allocation (5 of 10)
• First-fit algorithm
• Memory Manager: keeps two lists
– One for free memory
– One for busy memory blocks
• Loop: compares job size to each memory block size
– Until large enough block found: fits the job
• Job: stored into that memory block
• Memory Manager: moves out of the loop
– Fetches next job: entry queue
© 2018 Cengage. All Rights Reserved. May not be copied, scanned, or duplicated, in whole or in part, except for use as permitted in a license distributed
with a certain product or service or otherwise on a password-protected website for classroom use.
17
Best-Fit and First-Fit Allocation (6 of 10)
• First-fit algorithm (cont’d.)
• If entire list searched: no memory block large enough
– Job: placed into waiting queue
– Memory Manager: fetches next job
• Process repeats
© 2018 Cengage. All Rights Reserved. May not be copied, scanned, or duplicated, in whole or in part, except for use as permitted in a license distributed
with a certain product or service or otherwise on a password-protected website for classroom use.
18
Best-Fit and First-Fit Allocation (7 of 10)
(table 2.2)
These two snapshots of memory show the status of each memory block before and after 200 spaces
are allocated at address 6785, using the first-fit algorithm. (Note: All values are in decimal notation
unless otherwise indicated.)
© Cengage Learning 2018
© 2018 Cengage. All Rights Reserved. May not be copied, scanned, or duplicated, in whole or in part, except for use as permitted in a license distributed
with a certain product or service or otherwise on a password-protected website for classroom use.
19
Best-Fit Versus First-Fit Allocation (8 of 10)
• Best-fit algorithm
• Goal: find smallest memory block where job fits
• Entire table searched before allocation
© 2018 Cengage. All Rights Reserved. May not be copied, scanned, or duplicated, in whole or in part, except for use as permitted in a license distributed
with a certain product or service or otherwise on a password-protected website for classroom use.
20
Best-Fit and First-Fit Allocation (9 of 10)
(table 2.3)
These two snapshots of memory show the status of each memory block before and after 200 spaces
are allocated at address 7600 (shaded), using the best-fit algorithm.
© Cengage Learning 2018
© 2018 Cengage. All Rights Reserved. May not be copied, scanned, or duplicated, in whole or in part, except for use as permitted in a license distributed
with a certain product or service or otherwise on a password-protected website for classroom use.
21
Best-Fit Versus First-Fit Allocation (10 of 10)
• Hypothetical allocation schemes
• Next-fit: starts searching from last allocated block for next available block
• Worst-fit: allocates largest free available block
– Opposite of best-fit
– Good way to explore theory of memory allocation
– Not best choice for an actual system
© 2018 Cengage. All Rights Reserved. May not be copied, scanned, or duplicated, in whole or in part, except for use as permitted in a license distributed
with a certain product or service or otherwise on a password-protected website for classroom use.
22
Deallocation (1 of 2)
• Deallocation: releasing allocated memory space
• For fixed-partition system:
• Straightforward process
• Memory Manager: resets the job’s memory block status to “free” upon job
completion
• Any code may be used: e.g., 0 = free and 1 = busy
© 2018 Cengage. All Rights Reserved. May not be copied, scanned, or duplicated, in whole or in part, except for use as permitted in a license distributed
with a certain product or service or otherwise on a password-protected website for classroom use.
23
Deallocation (2 of 2)
• For dynamic-partition system:
• Algorithm: tries to combine free areas of memory
• More complex
• Three dynamic partition system cases: depending on position of block to be
deallocated
• Case 1: adjacent to another free block
• Case 2: between two free blocks
• Case 3: isolated from other free blocks
© 2018 Cengage. All Rights Reserved. May not be copied, scanned, or duplicated, in whole or in part, except for use as permitted in a license distributed
with a certain product or service or otherwise on a password-protected website for classroom use.
24
Relocatable Dynamic Partitions (1 of 8)
• Memory Manager: relocates programs
• All empty blocks: gathered together
• Empty blocks: compacted
• Make one memory block: large enough to accommodate some or all waiting jobs
© 2018 Cengage. All Rights Reserved. May not be copied, scanned, or duplicated, in whole or in part, except for use as permitted in a license distributed
with a certain product or service or otherwise on a password-protected website for classroom use.
25
Relocatable Dynamic Partitions (2 of 8)
• Compaction (memory defragmentation): operating system reclaims fragmented
memory space sections
• Most or all programs in memory: relocated
– Contiguous arrangement
• Operating system: distinguishes between addresses and data values
– Every address and address reference: adjusted to match the program’s new memory location
– Data values: left alone
© 2018 Cengage. All Rights Reserved. May not be copied, scanned, or duplicated, in whole or in part, except for use as permitted in a license distributed
with a certain product or service or otherwise on a password-protected website for classroom use.
26
Relocatable Dynamic Partitions (3 of 8)
(figure 2.7)
Three snapshots of memory before and after compaction with the operating system occupying the
first 10K of memory. When Job 6 arrives requiring 84K, the initial memory layout in (a) shows
external fragmentation totaling 96K of space. Immediately after compaction (b), external
fragmentation has been eliminated, making room for Job 6 which, after loading, is shown in (c).
© Cengage Learning 2018
© 2018 Cengage. All Rights Reserved. May not be copied, scanned, or duplicated, in whole or in part, except for use as permitted in a license distributed
with a certain product or service or otherwise on a password-protected website for classroom use.
27
Relocatable Dynamic Partitions (4 of 8)
(figure 2.9)
Contents of the relocation register for Job 4 (a) before the job’s relocation (a value of zero) and (b)
after compaction (a negative number).
© Cengage Learning 2018
© 2018 Cengage. All Rights Reserved. May not be copied, scanned, or duplicated, in whole or in part, except for use as permitted in a license distributed
with a certain product or service or otherwise on a password-protected website for classroom use.
28
Relocatable Dynamic Partitions (5 of 8)
• Compaction issues
• What goes on behind the scenes when relocation and compaction take place?
• What keeps track of how far each job has moved from its original storage area?
• What lists have to be updated?
© 2018 Cengage. All Rights Reserved. May not be copied, scanned, or duplicated, in whole or in part, except for use as permitted in a license distributed
with a certain product or service or otherwise on a password-protected website for classroom use.
29
Relocatable Dynamic Partitions (6 of 8)
• What lists have to be updated?
• Free list
– Showing the partition for the new block of free memory
• Busy list
– Showing the new locations: all relocated jobs already in process
• Each job: assigned new address
– Exceptions: those already at the lowest memory locations
© 2018 Cengage. All Rights Reserved. May not be copied, scanned, or duplicated, in whole or in part, except for use as permitted in a license distributed
with a certain product or service or otherwise on a password-protected website for classroom use.
30
Relocatable Dynamic Partitions (7 of 8)
• Special-purpose registers: help with relocation
• Bounds register
– Stores highest location accessible by each program
• Relocation register
– Contains adjustment value: added to each address referenced in the program; “zero” value, if
program not relocated
© 2018 Cengage. All Rights Reserved. May not be copied, scanned, or duplicated, in whole or in part, except for use as permitted in a license distributed
with a certain product or service or otherwise on a password-protected website for classroom use.
31
Relocatable Dynamic Partitions (8 of 8)
• Compacting and relocating: optimizes memory use
• Improves throughput
• Compaction: overhead
• Compaction timing options
• When a certain memory percentage is busy
• When there are waiting jobs
• After a prescribed time period has elapsed
• Goal: optimize processing time and memory use; keep overhead as low as
possible
© 2018 Cengage. All Rights Reserved. May not be copied, scanned, or duplicated, in whole or in part, except for use as permitted in a license distributed
with a certain product or service or otherwise on a password-protected website for classroom use.
32
Conclusion (1 of 2)
• Four memory management techniques
• Single-user systems, fixed partitions, dynamic partitions, and relocatable dynamic
partitions
• Common to all four techniques
• Entire program: 1) loaded into memory; 2) stored contiguously; 3) resides in memory
until completed
• All schemes
• Place severe restrictions on job size: limited by the largest petition
• Groundwork for more complex memory management
© 2018 Cengage. All Rights Reserved. May not be copied, scanned, or duplicated, in whole or in part, except for use as permitted in a license distributed
with a certain product or service or otherwise on a password-protected website for classroom use.
33
Conclusion (2 of 2)
• New modern memory management trends in late 1960s and early 1970s
• Discussed in next chapter
• Common characteristics of memory schemes
– Programs are not stored in contiguous memory
– Not all segments reside in memory during job execution
© 2018 Cengage. All Rights Reserved. May not be copied, scanned, or duplicated, in whole or in part, except for use as permitted in a license distributed
with a certain product or service or otherwise on a password-protected website for classroom use.
34