A bitmap is a string of n binary disgits that can be used to represent the status of n items. For example, suppose we have several resources, and the avilability of each resource is indicated by the value of a binary digit:0 means that the resource is availlable, while 1 indicates that it is unavailable )or vice versa). The value of the i(th) position in the bitmap is associated with the i(th) reosurce. As an example, consider the bitmap shown below:
001011101
Resource 2,4,5,6, and 8 unavailable; resource 0,1,3,and 7 are available.
The power of bitmaps becomes apparent when we consider their space efficiency. If we were to use an eight-bit Boolean value instead of a single bit, the resulting data structure would be eight times larger. Thus, bitmaps are commonly used when there is a need to represent the availability of a large number of resources. Disk direves provide a nice illustration. A medium-sized disk drive might be divided into several thousand individual units, called disk blocks. A bitmap can be used to indicate the availability of each disk block.
In summary, data strures are prevasive in operating system implementations. Thus, we will see the structures discussed here, along with others, throughout this text as we explore kernel algorithms and their implementation.
댓글 없음:
댓글 쓰기