CSCI 1300 Operating Systems Study Sheet

Memory Management Techniques

Dynamic Partitions:

Single Contiguous Memory

The 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:

  1. Look up the starting address of the application program block.
  2. Add the byte number (offset) of the desired byte from the program to the starting address.

Example: Find the physical address of byte 2738 of the process.
The application program memory block starts at address 5000 in memory

5000 + 2738 = 7738, physical address of byte 2738

Fixed Partitions

The 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:

  1. Find the starting address of the partition assigned to the process.
  2. Add the byte number (offset) of the desired byte from the program to the starting address.

Example: Find the physical address of byte 2738 of the process.
The process is in partition 4, which starts at address 7280 in memory

7280 + 2738 = 10018, physical address of byte 2738 in process.

Paged Memory

The 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:

  1. Calculate the page number where the logical address is located by dividing the logical address by the page size. The remainder from this division gives the offset of the byte within the page.
  2. Look up the frame number for that page in the PMT.
  3. Calculate the starting address for the frame by multiplying the frame number by the frame size.
  4. Add the starting address for the frame to the byte offset within the page to get the physical address.

Example: Find the physical address of byte 8740 of the process. The PMT for the process is:

Page012345678
Frame922145311731823
  1. 8740 / 1024 = 8 with a remainder of 548 -> page 8, offset 548 <8,548>
  2. Page 8 is located in frame 23.
  3. 23 * 1024 = 23552 (starting physical address of frame 23)
  4. 23552 + 548 = 24100, physical address of byte 8740 of the process.

Dynamic Partitions

The 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:

  1. Find the starting address of the partition assigned to the process.
  2. Add the byte number (offset) of the desired byte from the program to the starting address.

Example: Find the physical address of byte 2738 of the process.
The process is in a partition which starts at address 7280 in memory

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 Served

Time 0 — P1 starts
Time 180 — P1 ends, P2 starts
Time 245 — P2 ends, P3 starts
Time 470 — P3 ends, P4 starts
Time 505 — P4 ends, P5 starts
Time 680 — P5 ends, P6 starts
Time 825 — P6 ends

Total execution time: 825

Shortest Service Time Next

Time 0 — P4 starts
Time 35 — P4 ends, P2 starts
Time 100 — P2 ends, P6 starts
Time 245 — P6 ends, P5 starts
Time 420 — P5 ends, P1 starts
Time 600 — P1 ends, P3 starts
Time 825 — P3 ends

Total execution time: 825

Round Robin (time slice = 50)

Time 0 — P1 starts
Time 50 — P1 is interrupted, P2 starts
Time 100 — P2 is interrupted, P3 starts
Time 150 — P3 is interrupted, P4 starts
Time 185 — P4 ends, P5 starts
Time 235 — P5 is interrupted, P6 starts
Time 285 — P6 is interrupted, P1 restarts
Time 335 — P1 is interrupted, P2 restarts
Time 350 — P2 ends, P3 restarts
Time 400 — P3 is interrupted, P5 restarts
Time 450 — P5 is interrupted, P6 restarts
Time 500 — P6 is interrupted, P1 restarts
Time 550 — P1 is interrupted, P3 restarts
Time 600 — P3 is interrupted, P5 restarts
Time 650 — P5 is interrupted, P6 restarts
Time 695 — P6 ends, P1 restarts
Time 725 — P1 ends, P3 restarts
Time 775 — P3 is interrupted, P5 restarts
Time 800 — P5 ends, P3 restarts
Time 825 — P3 ends

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 Served

Disk access requests will be handled in the order:
45, 12, 15, 66, 35, 72, 13, 19, 51, 4, 78, 2, 55

Shortest Seek Time Next

Disk access requests will be handled in the order:
35, 45, 51, 55, 66, 72, 78, 19, 15, 13, 12, 4, 2

SCAN Disk

Disk access requests will be handled in the order:
45, 51, 55, 66, 72, 78, 25, 19, 15, 13, 12, 4, 2