Structs Exercise
On path: Exercises | 0: Exercises • 1: Pointer Exercise • 2: Arguments Exercise • 3: Malloc Exercise • 4: Structs Exercise • 5: Processes Exercise • 6: Shared memory Exercise • 7: Pipes Exercise • 8: Exceptions Exercise • 9: Synchronisation Exercise • 10: Files Exercise • 11: Threads Exercise • 12: Unix proc Exercise |
---|
On path: Pointers | 1: Memory • 2: Arrays • 3: Pointers • 4: Pointer Exercise • 5: Structures • 6: Dynamic Memory Allocation • 7: Malloc Exercise • 8: Structs Exercise |
---|
Depends on | Dynamic Memory Allocation • Memory |
---|
The purposes of this exercise are:
- to augment understanding of memory layout
- to illustrate an example of the type of structures used in operating system functions
- to introduce some (confusing?) C language syntax
- to introduce dynamic memory allocation (in C)
This exercise uses principles illustrated in earlier exercises on pointers and memory allocation and you should be happy with those principles before proceeding.
Start with the code structures.c
, which is an example which builds
(and then destroys) a linked list. Check you can compile and run
it okay.
Look at the source code in conjunction with the output. About 10 lines down a C struct
is defined and named as a user-defined type “PCB”. This is a much simplified illustration of the sort of structure which can be used as a process control block.
This example starts off containing a couple of
int
data fields and a pointer to any similar structure. Later you may like to experiment adding some fields of your own to see what is affected.
This typedef
just defines the ‘class’; it does not
declare any actual variables.
A bit further down the typedef
is used to instantiate a structure – in this case called “dummy”. Only one instance is made here: the similar looking declarations are (potentially) pointers to such structures.
At this point you might like to start drawing the memory structures. Here’s a bit to get you started.
“dummy” is mostly not used – only the pointer is
important here … and that’s not used yet which is why it’s set to
NULL
.
We built it this way because it makes the code a bit shorter (so, maybe, clearer?): there is no need for special-case coding for an empty list. Syntax:
dummy.pNext
(for example) refers to the fieldpNext
in the instance.&
means “the address of” (remember?) which sets the pointer to the end of the list (pEnd
) to point at this ‘zero-th’ entry.
It is useful to establish the size of integers and pointers on the
system you are using. The code (print_structure()
) then prints the
(hexadecimal) address of each field in the structure. Your
drawing should show that these are spaced the appropriate
distances apart. The absolute values of the addresses don’t really
matter at the moment.
Skip over print_list()
– delete it if you like. At this point it’s
just saying there’s nothing there. Follow into add_entry()
though.
add_entry()
takes some data values and makes a new block (struct
instance) for them. This involves:
- dynamic allocation of a big enough memory block
- writing the data into the newly created block
- making the new block a potential list terminator
- pointing the current last block at the new block
- returning a pointer to the (new) last block in the list
Pause to understand that.Syntax:
pTemp->pNext
(for example) refers to the field ‘pNext’ in the struct pointed at bypTemp
. Pause to understand that; maybe draw it.If you’re insufficiently confused, instead of writing:
pTemp->pNext
we could write:(*pTemp).pNext
which has the same function, although that probably doesn’t make things much clearer.
After that, the code plays (as should you) at adding a few more links to the list and printing out the addresses.
A couple of things to observe, although different systems will vary:
- The dynamically allocated blocks will probably have addresses close to each other.
- The dynamically allocated blocks will probably have addresses somewhat different to the statically allocated
dummy
; this may be in a different segment.
Lastly, the list is stripped down and disposed of, block by block,
using the free()
call. This is Good Practice even though the
operating system will tidy up anyway when the process terminates.
Puzzle
You may see that the malloc elements are almost adjacent but have some small gaps between them. Speculate on why this might be. (This is quite difficult so don’t panic if you can’t think of anything.)
Submission
- A text figure showing the addresses and corresponding data of the data structures involved, at its fullest extent.
(Hint - don’t add too many more records!)
Something like this example (from a real, 32-bit x86 Linux system): - If you have any thoughts on the puzzle, append them, too.
For convenience, please amalgamate these into a single text file [ex4.txt
].