Memory Management: Linking and Loading Concepts, Process and Main Memory Management and The First Fit Policy.

By -

4.3 Linking and Loading Concepts

In Figure 4.2 we depict the three stages of the way a HLL program gets processed.

clip_image002

Figure 4.2: Linking and loading.

The three stages of the processing are:

Y Stage 1: In the first stage the HLL source program is compiled and an object code is produced. Technically, depending upon the program, this object code may by itself be sufficient to generate a relocatable process. However many programs are compiled in parts, so this object code may have to link up with other object modules. At this stage the compiler may also insert stub at points where run time library modules may be linked.

Y Stage 2: All those object modules which have sufficient linking information (generated by the compiler) for static linking are taken up for linking. The linking editor generates a relocatable code. At this stage, however, we still do not replace the stubs placed by compilers for a run time library link up.

Y Stage3: The final step is to arrange to make substitution for the stubs with run time library code which is a relocatable code.

When all the three stages are completed we have an executable. When this executable is resident in the main memory it is a runnable process.

Recall our brief discussion in the previous section about the binding of variables in a program. The compiler uses a symbol table to generate addresses. These addresses are not bound, i.e. these do not have absolute values but do have information on sizes of data. The binding produced at compile time is generally relative. Some OSs support a linking loader which translates the relative addresses to relocatable addresses. In any event, the relocatable process is finally formed as an output of a loader.

4.4 Process and Main Memory Management

Once processes have been created, the OS organizes their execution. This requires interaction between process management and main memory management. To understand this interaction better, we shall create a scenario requiring memory allocations. For the operating environment we assume the following:

  • A uni-processor, multi-programming operation.
  • A Unix like operating system environment.

With a Unix like OS, we can assume that main memory is partitioned in two parts. One part is for user processes and the other is for OS. We will assume that we have a main memory of 20 units (for instance it could be 2 or 20 or 200 MB). We show the requirements and time of arrival and processing requirements for 6 processes in Table 4.1.

clip_image003

Table 4.1: The given data.

We shall assume that OS requires 6 units of space. To be able to compare various policies, we shall repeatedly use the data in Table 4.1 for every policy option. In the next section we discuss the first fit policy option.

With these requirements we can now trace the emerging scenario for the given data. We shall assume round robin allocation of processor time slots with no context switching

clip_image004

Table 4.2: FCFS memory allocation.

over-heads. We shall trace the events as they occur giving reference to the corresponding part in Table 4.2. This table also shows a memory map as the processes move in and out of the main memory.

4.5 The First Fit Policy: Memory Allocation

In this example we make use of a policy called first fit memory allocation policy. The first fit policy suggests that we use the first available hole, which is large enough to accommodate an incoming process. In Figure 4.3, it is important to note that we are following first-come first-served (process management) and first fit (memory allocation) policies. The process index denotes its place in the queue. As per first-come first-served policies the queue order determines the order in which the processes are allocated areas. In addition, as per first-fit policy allocation we scan the memory always from one end and find the first block of free space which is large enough to accommodate the incoming process.

In our example, initially, processes P1, P2, P3 and P4 are in the queue. The allocations for processes P1, P2, P3 are shown in 4.3(a). At time 5, process P2 terminates. So, process P4 is allocated in the hole created by process P2. This is shown at 4.3(b) in the figure. It still leaves a hole of size 3. Now on advancing time further we see that at time 8, process P1 terminates. This creates a hole of size 3 as shown at 4.3(c) in the figure.

This hole too is now available for allocation. We have 3 holes at this stage. Two of these 3 holes are of size 3 and one is of size 2. When process P5 arrives at time 10, we look for the first hole which can accommodate it. This is the one created by the departure of process P1. Using the first-fit argument this is the hole allocated to process P5 as shown in Figure 4.3(d). The final allocation status is shown in Figure 4.3. The first-fit allocation policy is very easy to implement and is fast in execution.

clip_image005

Figure 4.3: First-fit policy allocation.

Comments

Post a Comment

Popular posts from this blog

Input Output (IO) Management:HW/SW Interface and Management of Buffers.

By -
Image
5.3 HW/SW Interface IO management requires that a proper set-up is created by an application on computer system with an IO device. An IO operation is a combination of HW and SW instructions as shown in Figure 5.8. Following the issuance of an IO command, OS kernel resolves it, and then communicates Figure 5.8: Communication with IO devices. with the concerned device driver. The device drivers in turn communicate with IO devices. The application at the top level only communicates with the kernel. Each IO request from an application results in generating the following: Naming or identification of the device to communicate. Providing device independent data to communicate; The kernel IO subsystem arranges for the following: The identification of the relevant device driver. We discuss device drivers in Section 5.3.1. Allocation of buffers. We discuss buffer management in Section 5.4. Reporting of errors. Tracking the device usage (is the device free, who is the current u...
Read more

Introduction to Operating Systems:Early History: The 1940s and 1950s

By -
Early History: The 1940s and 1950s Operating systems have evolved over the last 60 years through several distinct phases or generations that correspond roughly to the decades (see the Operating Systems Thinking feature, Innovation).3 In the 1940s, the earliest electronic digital computers did not include operating systems.4, 5, 6 Machines of the time were so primitive that programmers often entered their machine-language programs one bit at a time on rows of mechanical switches. Eventually, programmers entered their machine-language programs on punched cards. Then, assembly languages—which used English-like abbreviations to represent the basic operations of the computer— were developed to speed the programming process. General Motors Research Laboratories implemented the first operating sys- tem in the early 1950s for its IBM 701 computer.7 The systems of the 1950s generally executed only one job at a time, using techniques that smoothed the transition between jobs to obtain maximu...
Read more

Input Output (IO) Management:IO Organization.

By -
Image
IO Organization In the previous section we discussed various issues that arise from the need to support a wide range of devices. To meet these varied requirements, a few well understood modalities have evolved over time. The basic idea is to select a mode of communication taking device characteristics into account or a need to synchronize with some event, or to just have a simple strategy to ensure a reliable assured IO. Computers employ the following four basic modes of IO operation: 1. Programmed mode 2. Polling mode 3. Interrupt mode 4. Direct memory access mode. We shall discuss each of these modes in some detail now. 5.2.1 Programmed Data Mode In this mode of communication, execution of an IO instruction ensures that a program shall not advance till it is completed. To that extent one is assured that IO happens before anything else happens. As depicted in Figure 5.1, in this mode an IO instruction is issued to an IO device and the program executes in “busy-waiting” (idli...
Read more