The Elements of Computing Systems: Building a Modern Computer from First Principles (45 page)
Read The Elements of Computing Systems: Building a Modern Computer from First Principles Online
Authors: Noam Nisan,Shimon Schocken
BOOK: The Elements of Computing Systems: Building a Modern Computer from First Principles
2.52Mb size Format: txt, pdf, ePub
Figure 12.6a
Basic memory allocation scheme (wasteful).
Basic memory allocation scheme (wasteful).
This algorithm is clearly wasteful, as it does not reclaim the space of decommissioned objects.
Improved Memory Allocation Algorithm
This algorithm manages a linked list of available memory segments, called
freeList
. Each segment contains two housekeeping fields: the segment’s length and a pointer to the next segment in the list. These fields can be physically kept in the segment’s first two memory locations. For example, the implementation can use the convention segment.length==segment[0] and segment.next==segment[1]. Figure 12.6b (top left) illustrates a typical freeList state.
This algorithm manages a linked list of available memory segments, called
freeList
. Each segment contains two housekeeping fields: the segment’s length and a pointer to the next segment in the list. These fields can be physically kept in the segment’s first two memory locations. For example, the implementation can use the convention segment.length==segment[0] and segment.next==segment[1]. Figure 12.6b (top left) illustrates a typical freeList state.
When asked to allocate a memory block of some given size, the algorithm has to search the
freeList
for a suitable segment. There are two well-known heuristics for doing this search. Best-fit finds the segment whose length is the closest (from above) to the required size, while first-fit finds the first segment that is long enough. Once a suitable segment has been found, the required memory block is taken from it (the location just before the beginning of the returned block, block [-1], is reserved to hold its length, to be used during de-allocation). Next, this segment is updated in the
freeList,
becoming the part that remained after the allocation. If no memory was left in the block, or if the remaining part is practically too small, the entire segment is eliminated from the
freeList.
freeList
for a suitable segment. There are two well-known heuristics for doing this search. Best-fit finds the segment whose length is the closest (from above) to the required size, while first-fit finds the first segment that is long enough. Once a suitable segment has been found, the required memory block is taken from it (the location just before the beginning of the returned block, block [-1], is reserved to hold its length, to be used during de-allocation). Next, this segment is updated in the
freeList,
becoming the part that remained after the allocation. If no memory was left in the block, or if the remaining part is practically too small, the entire segment is eliminated from the
freeList.
When asked to reclaim the memory block of an unused object, the algorithm appends the de-allocated block to the
freeList.
The details are given in figure 12.6b.
freeList.
The details are given in figure 12.6b.
After a while, dynamic memory allocation schemes like the algorithm in figure 12.6b may create a block fragmentation problem. Hence, some kind of “defrag” op-eration should be considered, namely, merging memory areas that are physically consecutive in memory but logically split into different segments in the
freeList
. The defragmentation operation can be done each time an object is de-allocated, or when alloc() fails to find an appropriate block, or according to some other intermediate or ad-hoc condition.
freeList
. The defragmentation operation can be done each time an object is de-allocated, or when alloc() fails to find an appropriate block, or according to some other intermediate or ad-hoc condition.
Figure 12.6b
Improved memory allocation scheme (with recycling).
Improved memory allocation scheme (with recycling).
Suppose we want to use high-level operations like s1=“New York” or s2= readLine (“enter a city”). How can we implement these variable-length abstractions? The common approach in modern languages is to use a String class that supplies services for creating and manipulating string objects. The string object can be physically realized using an array. Normally, when the string is created, this array is allocated to hold some maximum possible length. The actual length of the string at each point of time may be shorter than this maximum, and must be maintained throughout the string object’s life cycle. For example, if we issue a command like s1.eraseLastChar (), the actual length of s1 should decrease from 8 to 7 (although the length of the initially created array does not change). In general then, array locations beyond the current length are not considered part of the string contents.
Most programming languages feature string types, as well as other data types of variable lengths. The string objects are usually provided by the language’s standard library, for example, the String and StringBuffer classes in Java or the strXXX functions in C.
12.1.5 Input/Output ManagementComputers are typically connected to a variety of input/output devices such as keyboard, screen, mouse, disk, network card, etc. Each of these I/O devices has its own electromechanical and physical idiosyncrasies, and thus reading and writing data on them involves many technical details. High-level languages abstract these details away from the programmer using high-level operations like c=readChar () and printChar (c). These operations are implemented by OS routines that carry out the actual I/O.
Hence, an important function of the operating system is handling the various I/O devices connected to the computer. This is done by encapsulating the details of interfacing the device and by providing convenient access to its basic functionality, using a set of O/S routines collectively known as the device driver. In this book we describe the basic elements of handling the two most prevalent I/O devices: a screen and a keyboard. We divide the handling of the screen into two logically separate modules: handling graphics output and handling character output.
Graphics Output
Pixel Drawing
Most computers today use raster, also called bitmap, display technologies. The only primitive operation that can be physically performed in a bitmap screen is drawing an individual
pixel
—a single “dot” on the screen specified by (
column, row
) coordinates. The usual convention is that columns are numbered from left to right (like the conventional
x
-axis) while rows are numbered from the top down (opposite of the conventional
y
-axis). Thus the screen coordinates of the top left pixel are (0,0).
Most computers today use raster, also called bitmap, display technologies. The only primitive operation that can be physically performed in a bitmap screen is drawing an individual
pixel
—a single “dot” on the screen specified by (
column, row
) coordinates. The usual convention is that columns are numbered from left to right (like the conventional
x
-axis) while rows are numbered from the top down (opposite of the conventional
y
-axis). Thus the screen coordinates of the top left pixel are (0,0).
The low-level drawing of a single pixel is a hardware-specific operation that depends on the particular interface of the screen and the underlying graphics card. If the screen interface is based on a RAM-resident memory map, as in Hack, then drawing a pixel is achieved by writing the proper binary value into the RAM location that represents the required pixel in memory (see figure 12.7).
The memory map interface of the Hack screen was described in section 5.2.4. Formulating a drawPixel algorithm that follows this contract is a simple task left to the reader as an exercise. So, now that we know how to draw a single pixel, let us turn to describing how to draw lines and circles.
Line Drawing
When asked to draw a line between two locations on a bitmap screen, the best that we can possibly do is approximate the line by drawing a series of pixels along the imaginary line connecting the two points. Note that the “pen” that we use can move in four directions only: up, down, left, and right. Thus the drawn line is bound to be jagged, and the only way to make it look good is to use a high-resolution screen. Since the receptor cells in the human eye’s retina also form a grid of “input pixels,” there is a limit to the image granularity that the human eye can resolve anyway. Thus, high-resolution screens and printers can fool the human eye to believe that the lines drawn by pixels or printed dots are visibly smooth. In fact they are always jagged.
When asked to draw a line between two locations on a bitmap screen, the best that we can possibly do is approximate the line by drawing a series of pixels along the imaginary line connecting the two points. Note that the “pen” that we use can move in four directions only: up, down, left, and right. Thus the drawn line is bound to be jagged, and the only way to make it look good is to use a high-resolution screen. Since the receptor cells in the human eye’s retina also form a grid of “input pixels,” there is a limit to the image granularity that the human eye can resolve anyway. Thus, high-resolution screens and printers can fool the human eye to believe that the lines drawn by pixels or printed dots are visibly smooth. In fact they are always jagged.
Figure 12.7
Drawing a pixel.
Drawing a pixel.
The procedure for drawing a line from location (
x
1,
y
1) to location (
x
2,
y
2) starts by drawing the (
x
1,
y
1) pixel and then zigzagging in the direction of (
x
2,
y
2), until this pixel is reached. See figure 12.8a for the details.
x
1,
y
1) to location (
x
2,
y
2) starts by drawing the (
x
1,
y
1) pixel and then zigzagging in the direction of (
x
2,
y
2), until this pixel is reached. See figure 12.8a for the details.
To extend this algorithm to a general-purpose line drawing routine, one also has to take care of the possibilities dx, dy < 0, dx > 0, dy < 0, and dx < 0, dy > 0. To complete the picture, note that the special cases
dx
= 0 or
dy
= 0, required for drawing vertical and horizontal lines, are not handled by this algorithm. These widely used cases should probably benefit from a separate and optimized treatment anyway.
dx
= 0 or
dy
= 0, required for drawing vertical and horizontal lines, are not handled by this algorithm. These widely used cases should probably benefit from a separate and optimized treatment anyway.
An annoying feature of the algorithm in figure 12.8a is the use of division operations in each loop iteration. Not only are these division operations time-consuming, but they also require floating point operations rather than simple integer arithmetic. The first obvious solution is to replace the
a/dx
<
b/dy
condition with the equivalent
a
·
dy
<
b
·
dx
, which requires only integer multiplication. Further, careful inspection of the algebraic structure of the latter condition reveals that it may be checked without using any multiplication at all. As shown in figure 12.8b, this may be done efficiently by maintaining a variable that updates the value of
a
·
dy
—
b
·
dx
each time either
a
or
b
are modified.
a/dx
<
b/dy
condition with the equivalent
a
·
dy
<
b
·
dx
, which requires only integer multiplication. Further, careful inspection of the algebraic structure of the latter condition reveals that it may be checked without using any multiplication at all. As shown in figure 12.8b, this may be done efficiently by maintaining a variable that updates the value of
a
·
dy
—
b
·
dx
each time either
a
or
b
are modified.
Figure 12.8a
Line drawing.
Line drawing.
Figure 12.8b
Efficient testing using addition operations only.
Efficient testing using addition operations only.
Circle Drawing
There are several ways to draw a circle on a bitmap screen. We present an algorithm (figure 12.9) that uses three routines already implemented in this chapter: multiplication, square root, and line drawing.
There are several ways to draw a circle on a bitmap screen. We present an algorithm (figure 12.9) that uses three routines already implemented in this chapter: multiplication, square root, and line drawing.
The algorithm is based on drawing a series of horizontal lines (like the typical line ab in figure 12.9), one for each row in the range
y
—r to
y
+ r. Since r is specified in pixels, the algorithm ends up drawing a line in every screen row along the circle’s north-south axis, resulting in a completely filled circle. A trivial tweaking of this algorithm can yield an empty circle as well.
y
—r to
y
+ r. Since r is specified in pixels, the algorithm ends up drawing a line in every screen row along the circle’s north-south axis, resulting in a completely filled circle. A trivial tweaking of this algorithm can yield an empty circle as well.
Note that the algorithm is somewhat inefficient, since the square root computation in each iteration is an expensive operation. There exist many more efficient circle-drawing algorithms, including ones that involve addition operations only, in the same spirit of our line-drawing algorithm.
Character Output
All the output that we have described so far is graphical: pixels, lines, and circles. We now describe how characters are printed on the screen, pixel by pixel, using the good services of the operating system. Here are the details.
All the output that we have described so far is graphical: pixels, lines, and circles. We now describe how characters are printed on the screen, pixel by pixel, using the good services of the operating system. Here are the details.
Other books
Quiet as a Nun by Antonia Fraser
Sword Of God by Kuzneski, Chris
Cloud Atlas by David Mitchell
Secrets by Robin Jones Gunn
Resurrección by Craig Russell
Lessons in Love by Emily Franklin
Seth's Chance [Brac Pack 27] by Lynn Hagen
Royal Pain by Mulry, Megan
Threads: The Reincarnation of Anne Boleyn by Nell Gavin
Carlie Simmons (Book 3): The Way Back by Sawyer, JT
