Memory Management Techniques
Dynamic Partitions:
Single Contiguous MemoryThe operating system and a single application program divide the main memory between them. The operating system starts at byte address zero. Calculating physical address from logical address:
Example: Find the physical address of byte 2738 of the process. 5000 + 2738 = 7738, physical address of byte 2738 | Fixed PartitionsThe operating system sets up a group of fixed-sized permanent partitions. When a process begins, the operating system locates an empty partition that is at least as large as the process, and assigns it to the process. The partitions themselves never change. Calculating physical address from logical address:
Example: Find the physical address of byte 2738 of the process. 7280 + 2738 = 10018, physical address of byte 2738 in process. | ||||||||||||||||||||
Paged MemoryThe operating system breaks memory into small, fixed-sized frames, typically 1 kilobyte (1024 bytes) in size. When a process begins, it is broken into pages of the same size. The operating system assigns each page to an empty frame, tracking the assignments in a page-map table (PMT). Calculating physical address from logical address:
Example: Find the physical address of byte 8740 of the process. The PMT for the process is:
| Dynamic PartitionsThe operating system starts with a single large partition. When a process begins, the operating system locates an empty partition at least as large as the process, and splits it into two pieces. One piece is the same size as the process, and is assigned to the process. The other piece becomes a new, empty partition. When the operating system detects that two adjacent partitions are both empty, the partitions will be recombined to form a single larger partition. Once a process is assigned to a partition, that process remains in that partition until it finishes. The partitions are constantly changing, making memory usage more efficient at the cost of more work for the system. Calculating physical address from logical address:
Example: Find the physical address of byte 2738 of the process. 7280 + 2738 = 10018, physical address of byte 2738 in process. |
CPU Scheduling
First Come First Served (FCFS): first process arriving in the ready state will run first. Non-preemptive.
Shortest Service Time Next (SSTN): shortest process in the ready state will run next. Non-preemptive.
Round Robin: Processes take turns running for a set maximum amount of time before being interrupted and sent back to the ready state to allow another process to run.
Example: The ready state currently contains the following processes, with their estimated service times:
P1 (180), P2 (65), P3 (225), P4 (35), P5 (175), P6 (145)
First Come First ServedTime 0 — P1 starts Total execution time: 825 | Shortest Service Time NextTime 0 — P4 starts Total execution time: 825 | Round Robin (time slice = 50)Time 0 — P1 starts Total execution time: 825 |
Disk Scheduling
Total time to access data on a disk = seek time + latency + transfer time
- Seek time: time to position read/write head over requested track
- Latency: time for desired sector to rotate under the read/write head. Maximum value for latency is the time required for one complete rotation, which is 8.333 milliseconds for a 7200 rpm hard drive.
- Transfer time is the time required to transfer one block of data between RAM and secondary storage. Note that the transfer rate is a fixed number of bits per second.
Disk scheduling methods attempt to minimize the seek time, the only non-fixed part of the total access time.
First Come First Served (FCFS): first pending disk request arriving will be handled first.
Shortest Seek Time Next (SSTN): pending disk request on the nearest track will be handled first.
SCAN Disk: read/write heads move from edge of the disk to the center, then reverse direction and move back out to the edge. As the read/write head moves, it processes any pending disk requests on each track as it passes over the track.
Example: pending disk access requests have arrived in this order, and exist for tracks 45, 12, 15, 66, 35, 72, 13, 19, 51, 4, 78, 2, 55. The read/write head is currently positioned on track 39, and just came from track 27.
First Come First ServedDisk access requests will be handled in the order: | Shortest Seek Time NextDisk access requests will be handled in the order: | SCAN DiskDisk access requests will be handled in the order: |