Sigcse 18
Sigcse 18
Sigcse 18
ABSTRACT work that we would have expected. Furthermore, when faced with
This work describes our experience in revising one of the major the daunting design space during their work, students would often
programming assignments for the second-year course Introduction resort to changing and tweaking what they had done so far in hopes
to Computer Systems, in which students implement a version of the of following some random walk to a su�ciently optimized solution
malloc memory allocator. The revisions involved fully supporting that would pass the assignment performance standards.
a 64-bit address space, promoting a more modern programming As a further shortcoming, students were encouraged to follow a
style, and creating a set of benchmarks and grading standards that programming style with extensive use of macros performing low-
provide an appropriate level of challenge. level address arithmetic. Many students struggled working with this
With this revised assignment, students were able to implement style of programming—the compiler did not generate meaningful
more sophisticated allocators than they had in the past, and they error messages, symbolic debugging tools could only provide a view
also achieved higher performance on the related questions on the into the post macro-expanded code, and it was very easy to make
�nal exam. mistakes in address computations. A small, but signi�cant number
of students failed to write allocators that could even pass all of
KEYWORDS the correctness tests. The ability of modern compilers to generate
e�cient code via inline substitution has made most macro-based
malloc, programming assignment, systems programming
programming obsolete.
ACM Reference Format: Previously, students would base their malloc on the code in The
Brian P. Railing and Randal E. Bryant. 2018. Implementing Malloc: Stu-
C Programming Language [6] and Computer Systems: A Program-
dents and Systems Programming. In SIGCSE ’18: SIGCSE ’18: The 49th
ACM Technical Symposium on ComputFS Science Education, February 21– mer’s Perspective [3]. From our review of student submissions,
24, 2018, Baltimore , MD, USA. ACM, New York, NY, USA, 6 pages. we concluded that there were several shortcomings in the assign-
https://doi.org/10.1145/3159450.3159597 ment and developed four areas for revision to the programming lab.
Listed here, these revisions will be discussed in greater detail later
1 INTRODUCTION in this work:
Teaching Introduction to Computer Systems, a course developed • Fully support a 64-bit address space. This required creating a
at Carnegie Mellon University [2] and widely adopted elsewhere, testing environment that allocated blocks of over 260 bytes,
exposes students to the basics of how the architecture, compiler, even though no existing system has access to that much
and operating system work together to support program execu- memory.
tion. The course makes use of seven programming assignments, • Promote a more modern programming style. Rather than writ-
termed labs, that explore di�erent aspects of the computer system. ing macros that performed low-level address calculations,
The most challenging lab for the course, distributed as part of the students were required to make best use of the abstractions
support materials for the Bryant-O’Hallaron textbook [3], requires provided by C, while still achieving high degrees of memory
students to implement a memory allocator based on malloc. Anec- utilization.
dotal reports by students, the instructors of more advanced systems • Use a set of carefully selected benchmark traces. These bench-
courses, and subsequent employers of the students indicate that this marks should challenge students to develop well-engineered
lab provides them an important experience in low-level program designs that achieve an appropriate balance between mem-
implementation, debugging, and tuning. ory utilization and throughput.
In re�ecting on the existing version of the malloc lab, we noted • Follow a revised time line and grading standards. We divided
that high scoring student submissions required identifying particu- the assignment into two phases to help students better man-
lar tricks and knowledge of the testing environment, all the while age their time.
not exploring the interesting design decisions and implementation
The rest of the paper is organized as follows: Section 2 provides
Permission to make digital or hard copies of all or part of this work for personal or the context of the course, Section 3 covers the overview of the mal-
classroom use is granted without fee provided that copies are not made or distributed
for pro�t or commercial advantage and that copies bear this notice and the full citation loc assignment, Section 4 explores the changes we made, Section 5
on the �rst page. Copyrights for components of this work owned by others than ACM presents our re�ections on the results, and Section 6 concludes
must be honored. Abstracting with credit is permitted. To copy otherwise, or republish,
to post on servers or to redistribute to lists, requires prior speci�c permission and/or a
this paper. Although the focus of this paper is on a speci�c assign-
fee. Request permissions from permissions@acm.org. ment for a speci�c purpose, we believe that many of the factors
SIGCSE ’18, February 21–24, 2018, Baltimore , MD, USA addressed are important considerations for any systems program-
© 2018 Association for Computing Machinery. ming assignment and that the approaches we devised have broader
ACM ISBN 978-1-4503-5103-4/18/02. . . $15.00
https://doi.org/10.1145/3159450.3159597 applications.
1.3
Header Payload Footer Allocated 1.2