Computer System With I/O Devices, Cache Memory And RAID Levels

I/O Devices and Priorities

Part 1

Assume a computer system with four I/O devices: a printer, a disk, a communication line and a keyboard with increasing priorities of 2, 4, 5 and 6, respectively. At t=0, a user program starts. At t=20, a printer interrupt occurs. At t=25, a communication line interrupt occurs. At t=50, a disk interrupt occurs, and at t=60, a keyboard interrupt occurs. Assume all interrupts take 20-time units to finish. Please draw the time sequence as the textbook does.

   Process name            Process No.            AT            BT             Priority

       Printer                        1                         20              20                 2

         Disk                          2                        25              20                  4

          C.L                         3                           50             20                   5

    Keyboard                       4                           60             20                  6

At the arrival time, BT; time is taken to finish the process

Ghant chart

3/20           20/20        10/20        10/20         20/20     20/20        20/20

Idle

1

2

1

3

4

3

1

TAT = CT – AT

Total time taken to finish the process in 100

CT: Completion time

TAT: Turn Around Time

WT: Waiting Time

WT: 1 CT – Idle + AT; 100-20+20 = 60

       2    45-25+20 = 0

       3    90-50+20 = 20

      4    80 – 20+60=80

1. Consider a computer system with 128MB main memory with 512 KB cache. Each cache line has 8 bytes. Show the format of main memory address with direct mapping, associative mapping, 8-set associative mapping.

The memory size is 128 MB, and the cache is 512 KB with 8 bytes in each line

1. Direct mapping

Memory address bits = 27

Number of lines = (512*1024)/8 = 65536

Bits for lines = 2^16

Number of bytes in a line = 8

3-bit offset.

Address Bits = 27 = 8(Tag) + 16(line selection) + 3 (offset)

1. Associative Mapping

We combine the line selection with the tag, and now tag becomes 24 bits

Address bits = 24 (Tag) + 3 (Offset)

1. 8-set associative mapping

Number of lines per set is 8

Number of sets = 65536/8 = 8192

Bits for sets 13 bits

Address bits = 27 = 11 (tag) + 13 (Set) + 3(Offset)

1. Consider a 32-bit microprocessor that has an on-chip 16-Kbyte four-way set associative cache. Assume that the cache has a line size of four 32-bit words. Draw a block diagram of this cache, showing its organization and how the different address fields are used to determine a cache hit/miss?

The block diagram for cache memory:

To design the block diagram for cache memory, following points need to be considered

Write down the address format

Calculate the number of bits which are required for each of the fields in address format

Calculate the number of sets

Identify the set exactly where the information is stored.

Finally, draw the block diagram as per the requirements

Address format

The address format consists of three fields which are a tag, set and offset

N-bits	N-bits	N-bits
Tag field	Set field	Offset field

32-bit microprocessor

16KB on-chip main memory size

Main memory size = 16 * 1024

= 16384

= 2¹⁴

The block size = four 32 bits

= 16 bytes

Calculation for offset:

Given block size is four 32 bits = four 4-bytes. Therefore, for four 32-bit 16 bytes are required.

Cache Memory Mapping

To represent 16bytes, 4 bits are required which 2⁴

Block size gives the offset length which is 4-bits

Calculation for Set bit:

No. of blocks = Main memory size/ block size

= 2¹⁴/2¹⁰

No. of set = No. of blocks/ Associative (4way)

= 2¹⁰/4

=1024/4

=256 number of sets

Calculation for Tag bit:

We got the offset consists of 4 bits

Set consists of 8-bits therefore 256 = 2⁸

In that case, Tag = 32-bit upset bits – offset bits

= 32- 8-4

= 20 bits

The tag field therefore consists of 20-bits

20-bits	8-bits	4-bits
Tag field	Set field	Offset field

Tag

Set

Offset

Considering the above block diagram, since it is a 4-way set associative, four comparators are used where each address of the individual address of individual set is associated to it.

Part 2

Describe briefly RAID Level 1, 2, 3, 4, 5 and RAID Level 6. What are the main differences?  Suppose we are using RAID level 3 scheme with data disks X0, X1, X2, X3, and parity check disk X4. If disk X2 has failed, describe the details how the missing data can be restored or reconstructed from the remaining disks.

RAID Level 1

This level involves mirroring of data in drive 1 to drive 2. However, it offers 100% redundancy as the array will continue to work even if either of the disks fails. In that case, any firm that wants a better redundancy can choose this solution (Flores, Graves, Hartfield & Winograd, 2015).

RAID Level 2

This raid provides a very high data transfer rates. Within this level, the central controller synchronizes the disks by making them spin at the same angular orientation so that they all reach the index simultaneously (Flores, Graves, Hartfield & Winograd, 2015). Accordingly, this raid utilizes bit-level striping, and hence each sequential bit is placed on a different hard drive. However, the error correcting code is the Hamming code parity which is calculated across bits and thus stored separately in a single drive.

The RAID 2 differs from the other levels of RAID since it does not utilize the standard way mirroring, stripping or parity. However, it usually implements these methods by separating data in bit level and then saving the bits over some different data disks along with redundancy disk. In that case, this configuration usually requires special driver hardware to make the disks spin synchronously. The raid two controller was expensive and hard to implement.

RAID Level 3

This raid is a Redundant Array of Independent Disks (RAID) standard which uses striping at the byte level and stores dedicated parity bits on a separate disk drive. Just like the raid 2, raid 3 requires a particular controller which allows for the synchronized spinning of all disks. The raid three usually strips the bits which are stored on the different disk drive. This configuration usually requires at least three separate hard disks where two are for stripping data and one for storing parity bits (Flores, Graves, Hartfield & Winograd, 2015).

RAID Levels and their Differences

The advantages of RAID 3 are high throughput for transferring large amounts of data and also resistant to disk failure and breakdown which therefore leads to its disadvantages as highlighted below. The first disadvantage is that the configuration may be too much if a small file transfer happens to be the only requirement. The second one is that disk failure may significantly decrease throughput.

RAID Level 4

This is a redundant array of independent Disks standard configuration which uses block-level data stripping along with a dedicated disk for storing parity bits. However, it does not require synchronized spinning and hence each disk functions independently when a single data blocks are requested (Flores, Graves, Hartfield & Winograd, 2015). This is in contrary to RAID 3 which stripes at block-level versus bit-level. This RAID does not distribute the parity bits, but the configuration requires at least three disks. However, RAID 4 and RAID 5 are similar, but RAID 4 holds all the parity bits within a single.

Some of the advantages of RAID 4 are as highlighted below. The first one is that data block striping which facilitates simultaneous input-output requests (Flores, Graves, Hartfield & Winograd, 2015). The second advantage is the low storage overhead which lowers as more disks are added. Lastly, it does not require synchronized spindles or controller. On the other hand, the disadvantages are parity drives may lead to bottlenecks along with slow random writes which result when a parity must be separately written for each write (Flores, Graves, Hartfield & Winograd, 2015).

RAID Level 5

This is a standard RAID level configuration which uses block-level data striping and hence distributes parity to all the disks. There is always some overhead during parity calculations but since the parity is written to all drives. The RAID 5 usually outperforms RAID 4 because of the low cost of redundancy it provides. This RAID is generally tolerant to single disk failures although it reduces the disk capacity since t stripes the data and parity bits across all disks. Some of the advantages of RAID 5 are tolerance to loss of a single drive, good random read performance and good sequential read and write performance (Flores, Graves, Hartfield & Winograd, 2015). On the other hand, the disadvantages are parity calculations may slow down the system and lastly, random write performance takes a hit because of parity overhead (Flores, Graves, Hartfield & Winograd, 2015).

RAID Level 6

This is also called double parity RAID since it utilizes two parity stripes on each disk.  As an illustration, it permits two disk failures within the RAID set before any data is lost. In that case, it offers very high fault and drives failure tolerance, and it is always utilized within the environments which require long data retention periods (Flores, Graves, Hartfield & Winograd, 2015).

Consider the following fixed-sector disk system of 512bytes/sector, with 96 sectors/track. Assume the disk rotates with speed at 360rpm. A processor reads one sector from the disk using interrupt-driven I/O, with one interrupt per byte. If it takes 2.5 microseconds to process each interrupt, what percentage of time will the processor spend on handling I/O (disregard seek time)? If we repeat the above problem using DMA and assume one interrupt per sector?

The disk has 512 bytes/sector

Each track contains 96 sectors

Disk rotation speed= 360 rpm (revolution per minute)

The time required for one revolution in seconds = 60/360*60/360 sec

= 0.1667 sec

The processor reads one sector from the disk with one interrupt per byte

The time required to process one interrupt is 2.5 µs

Since the disk has 512 bytes/sector and each byte generates an interrupt, the total number of interrupts generated is 512.

The time required to process 512 interrupts = 2.5 * 512

= 1280 µs

=1280 * 10^-6 sec

= 0.001280 sec

Therefore, the percentage of time that the processor spends in handling I/O = 100* (0.001280/0.001736)*100

= 74 %

References

Patterson, D. A., & Hennessy, J. L. (2013). Computer Organization and Design MIPS Edition: The Hardware/Software Interface. Newness.

Flores, F., Graves, M., Hartfield, B., & Winograd, T. (2015). Computer systems and the design of organizational interaction. ACM Transactions on Information Systems (TOIS), 6(2), 153-172.