Check A
Practical Case Study A Operating Systems Programming – 300698 Operating Systems Programming (Advanced) – 300943 1 Introduction Operating Systems have a need for extremely compact data structures, as often these need to be stored wholly in memory. Examples of this are free memory lists, page tables and disk space bitmaps. This Practical Case Study will develop and refresh your knowledge of bit oper- ations, necessary to manipulate such compact data-structures. 2 Bit Operations The C programming language provides a full set of bit manipulation operators: • & bitwise and • | bitwise or • ˆ bitwise exclusive or • ˜ ones compliment • >> right shift • < left="" shift="" these="" operators="" can="" be="" used="" to="" manipulate="" values="" at="" the="" bit="" level.="" they="" each="" treat="" the="" values="" as="" if="" they="" were="" ‘arrays’="" of="" bits="" and="" applies="" the="" operation="" to="" each="" bit="" in="" turn.="" there="" are="" four="" main="" operations="" that="" we="" perform,="" setting="" a="" bit,="" unsetting="" a="" bit,="" testing="" if="" a="" bit="" is="" set="" and="" toggling="" a="" bit.="" to="" set="" a="" bit="" we="" use="" the="" bitwise="" or="" operator.="" to="" do="" this="" we="" bitwise="" or="" our="" value="" with="" a="" mask="" with="" the="" bits="" we="" want="" to="" turn="" on="" set="" to="" 1="" and="" all="" others="" 0.="" for="" example="" to="" turn="" on="" the="" third="" bit="" our="" mask="" would="" be="" 000001002="" (the="" subscript="" 2="" means="" that="" the="" number="" is="" expressed="" in="" binary,="" no="" subscript="" means="" decimal).="" to="" unset="" a="" bit="" we="" use="" the="" bitwise="" and="" operator.="" to="" do="" this="" we="" bitwise="" and="" our="" value="" with="" a="" mask="" with="" the="" bits="" we="" want="" to="" unset="" set="" to="" 0="" and="" all="" others="" 1.="" for="" example="" to="" unset="" the="" sixth="" bit="" our="" mask="" would="" be="" 110111112.="" we="" can="" also="" use="" the="" ones="" compliment="" operator="" to="" invert="" a="" mask="" used="" to="" set="" a="" bit.="" to="" test="" if="" a="" bit="" is="" set="" we="" use="" the="" bitwise="" and="" operator.="" to="" do="" this="" we="" bitwise="" and="" our="" value="" with="" a="" mask="" with="" the="" bits="" we="" want="" to="" test="" set="" to="" 1="" and="" all="" others="" 0.="" for="" example="" to="" test="" if="" the="" fifth="" bit="" is="" set="" our="" mask="" would="" be="" 000100002.="" to="" toggle="" a="" bit="" we="" use="" the="" bitwise="" exclusive="" or="" operator.="" to="" do="" this="" we="" bitwise="" exclusive="" or="" our="" value="" with="" amask="" with="" the="" bits="" we="" want="" to="" toggle="" set="" to="" 1="" and="" all="" others="" 0.="" for="" example="" to="" toggle="" the="" fourth="" bit="" our="" mask="" would="" be="" 000010002.="" 1="" binary="" hexadecimal="" octal="" decimal="" 0000="" 0="" 0="" 0="" 0001="" 1="" 1="" 1="" 0010="" 2="" 2="" 2="" 0011="" 3="" 3="" 3="" 0100="" 4="" 4="" 4="" 0101="" 5="" 5="" 5="" 0110="" 6="" 6="" 6="" 0111="" 7="" 7="" 7="" 1000="" 8="" 10="" 8="" 1001="" 9="" 11="" 9="" 1010="" a="" 12="" 10="" 1011="" b="" 13="" 11="" 1100="" c="" 14="" 12="" 1101="" d="" 15="" 13="" 1110="" e="" 16="" 14="" 1111="" f="" 17="" 15="" table="" 1:="" values="" for="" 1-16="" we="" can="" use="" the="" left="" shift="" operator="" to="" construct="" masks,="" by="" shifting="" the="" value="" 1="" the="" required="" number="" of="" positions.="" the="" shift="" operators="" can="" also="" be="" used,="" with="" masking="" to="" extract="" subfields="" or="" to="" encode="" sub-="" fields.="" 3="" number="" systems="" in="" the="" previous="" section="" various="" masks="" were="" presented,="" however="" earlier="" versions="" of="" the="" c="" pro-="" gramming="" language="" don’t="" allow="" numbers="" to="" be="" expressed="" in="" binary.="" c="" traditionally="" allows="" three="" styles="" of="" number:="" decimal,="" octal="" and="" hexadecimal.="" decimal="" numbers="" are="" the="" numbers="" we="" use="" every="" day.="" octal="" numbers="" are="" a="" base="" 8="" system.="" to="" specify="" to="" the="" c="" compiler="" that="" a="" number="" is="" octal="" you="" add="" the="" prefix="" 0.="" for="" example="" the="" decimal="" number="" 23="" would="" be="" written="" in="" octal="" in="" a="" c="" program="" as="" 027.="" the="" advantage="" of="" octal="" numbers="" is="" that="" each="" digit="" represents="" exactly="" three="" bits.="" octal="" numbers="" are="" often="" used="" for="" specifying="" permissions="" in="" unix.="" hexadecimal="" numbers="" are="" a="" base="" 16="" system,="" the="" letters="" a-f="" or="" a-f="" are="" used="" for="" the="" ex-="" tra="" positions.="" to="" specify="" to="" the="" c="" compiler="" that="" a="" number="" is="" hexadecimal="" you="" add="" the="" prefix="" 0x.="" for="" example="" the="" decimal="" number="" 23="" would="" be="" written="" in="" hexadecimal="" in="" a="" c="" program="" as="" 0x17.="" the="" advantage="" of="" hexadecimal="" numbers="" is="" that="" each="" digit="" represents="" exactly="" four="" bits.="" hexadecimal="" numbers="" are="" often="" used="" for="" specifyingmasks="" and="" memory="" addresses.="" table="" 1="" shows="" equivalent="" values="" for="" the="" numbers="" 1-16.="" 2="" 4="" programming="" tasks="" you="" should="" begin="" by="" reading="" the="" example="" code="" carefully.="" there="" are="" a="" number="" of="" files="" that="" are="" included="" in="" the="" download.="" the="" makefile="" contains="" the="" rules="" to="" build="" all="" of="" the="" questions="" code.="" you="" simply="" need="" to="" type="" make="" in="" the="" directory="" that="" you="" downloaded="" the="" code="" to="" to="" compile="" it="" all,="" and="" if="" you="" have="" made="" no="" changes="" to="" the="" file="" then="" running="" make="" a="" second="" time="" will="" say="" everything="" is="" up="" to="" date.="" if="" you="" wish="" to="" remove="" all="" of="" the="" compiler="" generated="" files="" then="" runmake="" clean.="" the="" code="" supplied="" on="" the="" vuws="" site="" will="" compile,="" it="" just="" wont="" do="" anything="" useful="" until="" you="" edit="" it.="" in="" this="" task="" we="" will="" use="" the="" uint8_t="" type="" that="" is="" defined="" in="" the="" header="" file="" stdint.h.="" this="" type="" is="" an="" unsigned="" 8="" bit="" integer.="" 4.1="" print="" a="" value="" in="" binary="" your="" first="" task="" to="" to="" implement="" the="" function="" print_bits().="" this="" function="" takes="" a="" single="" uint8_t="" value="" as="" a="" parameter="" and="" prints="" to="" stdout="" the="" value="" of="" the="" parameter="" in="" binary,="" starting="" with="" themost="" significant="" bit.="" it="" must="" always="" print="" out="" all="" 8="" bits,="" so="" the="" value="" 110="" should="" be="" displayed="" as="" 00000001="" and="" the="" value="" 1610="" should="" be="" displayed="" as="" 00010000.="" the="" file="" part1.c="" is="" the="" start="" of="" some="" testing="" for="" this="" function,="" you="" may="" wish="" to="" add="" more="" to="" this="" file="" if="" you="" wish.="" 4.2="" reverse="" the="" bits="" in="" a="" byte="" your="" next="" task="" is="" to="" implement="" the="" function="" reverse_bits()="" this="" function="" takes="" a="" single="" uint8_t="" value="" as="" a="" parameter="" and="" returns="" the="" value="" with="" its="" bits="" reversed.="" so="" 10000000="" would="" be="" transformed="" to00000001="" and10101000would="" be="" transformed="" to00010101.="" the="" file="" part2.c="" is="" the="" start="" of="" some="" testing="" for="" this="" function,="" you="" may="" wish="" to="" add="" more="" to="" this="" file="" if="" you="" wish.="" 4.3="" check="" if="" a="" bit="" is="" turned="" on="" your="" next="" task="" is="" to="" implement="" the="" functioncheck_bit()="" this="" function="" takes="" a="" twouint8_t="" values="" as="" a="" parameters,="" the="" first="" the="" value="" to="" check="" and="" the="" second="" the="" bit="" that="" you="" are="" iter-="" ested="" in.="" the="" function="" will="" return="" true="" if="" the="" bit="" is="" turned="" on="" in="" the="" value="" and="" false="" otherwise.="" the="" file="" part3.c="" is="" the="" start="" of="" some="" testing="" for="" this="" function,="" you="" may="" wish="" to="" add="" more="" to="" this="" file="" if="" you="" wish.="" 4.4="" toggle="" a="" bit="" in="" a="" value="" your="" next="" task="" is="" to="" implement="" the="" function="" toggle_bit()="" this="" function="" takes="" a="" pointer="" to="" a="" uint8_t="" value="" as="" the="" parameter="" to="" modify="" and="" a="" uint8_t="" value="" for="" the="" bit="" oyu="" are="" interested="" in.="" the="" function="" will="" update="" the="" value="" stored="" at="" the="" pointer="" toggling="" the="" bit="" you="" are="" interested="" in,="" i.e.="" if="" the="" bit="" is="" on="" turn="" it="" off,="" if="" it="" is="" off="" turn="" it="" on.="" the="" file="" part4.c="" is="" the="" start="" of="" some="" testing="" for="" this="" function,="" you="" may="" wish="" to="" add="" more="" to="" this="" file="" if="" you="" wish.="" 4.5="" extract="" a="" subset="" of="" bits="" from="" a="" value="" your="" next="" task="" is="" to="" implement="" the="" function="" get_subfield()="" this="" function="" takes="" a="" three="" uint8_t="" value="" as="" a="" parameters,="" the="" first="" is="" the="" value,="" the="" second="" is="" the="" first="" bit="" you="" are="" 3="" interested="" in="" and="" the="" third="" is="" the="" last="" bit="" you="" are="" interested="" in.="" you="" should="" mask="" off="" the="" bits="" that="" you="" are="" interested="" in="" and="" then="" shift="" them="" to="" the="" least="" significant="" position,="" i.e.="" the="" first="" bit="" you="" are="" interested="" in="" should="" bbecome="" bit="" 0.="" the="" file="" part5.c="" is="" the="" start="" of="" some="" testing="" for="" this="" function,="" you="" may="" wish="" to="" add="" more="" to="" this="" file="" if="" you="" wish.="" 4="" 5="" sample="" code="" this="" sample="" code="" is="" also="" available="" at="" the="" unit="" website.="" you="" may="" not="" need="" all="" the="" variables="" declared="" in="" this="" code="" and="" you="" may="" choose="" to="" add="" more.="" 5.1="" bits.h="" the="" headerfile="" that="" describes="" the="" functions="" to="" be="" implemented="" in="" this="" task,="" you="" should="" not="" need="" to="" modify="" this="" file.="" #ifndef="" osp_bits_h="" #define="" osp_bits_h="" *="" the="" above="" lines="" prevent="" multiple="" inclusion="" problems="" */="" void="" print_bits(uint8_t="" value);="" uint8_t="" reverse_bits(uint8_t="" value);="" uint8_t="" check_bit(uint8_t="" value,="" uint8_t="" bit);="" uint8_t="" toggle_bit(uint8_t="" *value,="" uint8_t="" bit);="" uint8_t="" get_subfield(uint8_t="" value,="" uint8_t="" start,="" uint8_t="" stop);="" #endif="" 5="" 5.2="" bits.c="">
#include #include"bits.h" void print_bits(uint8_t value) { } uint8_t reverse_bits(uint8_t value) { } uint8_t check_bit(uint8_t value, uint8_t bit) { } uint8_t toggle_bit(uint8_t *value, uint8_t bit) { } uint8_t get_subfield(uint8_t value, uint8_t start, uint8_t stop) { } 6 5.3 part1.c #include #include #include"bits.h" int main(int ac, char **av) { uint8_t val=0b10101010; print_bits(val); return 0; } 7 5.4 part2.c #include #include #include"bits.h" int main(int ac, char **av) { uint8_t val=0; uint8_t rev=0; for(val=0;val<255;val++) {="" printf("val:%u\n",val);="" print_bits(val);="" putchar(’\n’);="" rev="reverse_bits(val);" print_bits(rev);="" putchar(’\n’);="" }="" return="" 0;="" }="" 8="" 5.5="" part3.c=""> #include #include"bits.h" int main(int ac, char **av) { uint8_t val=0b10101010; uint8_t bit; print_bits(val); putchar(’\n’); for(bit=0;bit<8;bit++) {="" printf("bit="" %u="" is",bit);="" if(check_bit(val,bit))="" {="" printf("="" on\n");="" }="" else="" {="" printf("="" off\n");="" }="" }="" return="" 0;="" }="" 9="" 5.6="" part4.c=""> #include #include"bits.h" int main(int ac, char **av) { uint8_t val = 0; uint8_t bit; for(bit=0;bit<8;bit++) {="" printf("val:%u,="" bit:%u\n",val,bit);="" print_bits(val);="" putchar(’\n’);="" toggle_bit(&val,bit);="" print_bits(val);="" putchar(’\n’);="" }="" for(bit=""><8;bit++) {="" printf("val:%u,="" bit:%u\n",val,bit);="" print_bits(val);="" putchar(’\n’);="" toggle_bit(&val,bit);="" print_bits(val);="" putchar(’\n’);="" }="" return="" 0;="" }="" 10="" 5.7="" part5.c=""> #include #include"bits.h" int main(int ac, char **av) { uint8_t val=0b10101010; print_bits(val); putchar(’\n’); print_bits(get_subfield(val,0,2)); putchar(’\n’); print_bits(get_subfield(val,1,3)); putchar(’\n’); return 0; } 11 5.8 makefile Please note that formatting is very important in a makefile, and that the character before rm on line 6 must be a tab character. PROGS=part1 part2 part3 part4 part5 ALL: ${PROGS} clean: rm -f *.o ${PROGS} part1: part1.o bits.o part2: part2.o bits.o part3: part3.o bits.o part4: part4.o bits.o part5: part5.o bits.o bits.o: bits.c bits.h 12 Introduction Bit Operations Number Systems Programming Tasks Print a value in binary Reverse the bits in a byte Check if a bit is turned on Toggle a bit in a value Extract a subset of bits from a value Sample Code +bits.h+ +bits.c+ +part1.c+ +part2.c+ +part3.c+ +part4.c+ +part5.c+ +makefile+