Low-level, or hardware-aware, programming
What is systems programming?
Low-level, or hardware-aware, programming
What is the execution stack?
The stack of all currently executing functions, with the currently running function at the top.
What is a stack frame?
The portion of the stack in which a function runs and stores local variables.
What is the heap?
The portion of the process reserved for dynamic memory allocation requests.
What is the name of the compiler with use on goldengate and our lab machines?
gcc
How are boolean values handled in C?
All non-zero values are true. 0 is false.
How is C different from Java?
Many answers: Java has garbage collection whereas C
requires manual memory management. C compiles directly to
binary code whereas Java uses a virtual machine.
What is git?
Source control system.
How does git differ from Github?
Git is a source control system. Github is a
service for storing and managing git repositories.
What does the git commit command do?
Saves a snapshot of you code.
What does the git push command do?
Uploads your current git repository history to github.
What does the git pull command do?
Downloads your current git repository history to github.
What is the terminal?
Text-based window that runs a shell.
What is a shell?
A shell is a program that runs commands.
What shell do we use on goldengate?
bash
What is the difference between static and dynamic allocation of memory?
How do we dynamically allocate memory in C?
Think of an example where we would need to allocate memory dynamically.
What is a pointer?
What are common uses of pointers in C?
What are the differences between pass-by-value and pass-by-pointer?
Think of an example where we would need to pass a function argument by pointer.
What is a segmentation fault? Give three (or more) coding mistakes that cause segmentation faults.
What types of errors does valgrind detect?
Memory leaks, invalid reads, invalid writes
What is gdb?
The GCC debugger
What is a memory leak?
What is a void pointer?
A generic pointer that can point to any data type
Why do we need to recompile C code to run on different hardware and operating systems?
How are strings represented in binary in C?
A string is a null-terminated array of characters.
A character is an ASCII value
How are floating-point numbers represented in binary?
What is a bit?
Container for either 0 or 1
What is a byte? e.g. How many bits are in a byte?
A byte is the smallest addressable amount of memory
8 bits
Suppose we have 4 bytes of data in memory. How do we know whether these bytes represent string, floating-point number, color, or integer?
From the data type
What is overflow?
When does overflow occur for signed integers?
When does overflow occur for unsigned integers?
How do we negate a binary number?
What is signed extension?
What is the difference between text and binary files?
What is the different between little endian and big endian byte ordering?
Why (and when) is padding added to structs?
What is the difference between logical and arithmetic shifts?
What is the CPU?
What is RAM?
What is ISA?
What are the five main components of any Von Neuman Architecture?
What is the ALU?
What are registers? Name several important registers that are contained in the CPU.
What is a hardware bus?
What four steps are performed by the computing architecture every time it executes an instruction.
What is assembly language?
What types of operands are there in assembly?
How does assembly handle data types?
What does the lea instruction do? How does it differ from the mov command?
How are parameters passed to functions?
How is machine code generated from source code? What is the relationship between machine code and assembly?
What do the registers %rsp and %rbp represent? How do they relate to functions?
What the do the registers %rax and %eax typically represent? When do we use one versus the other?
What two steps occur when the CPU executes the instruction push %rbp?
What two steps occur when the CPU executes the instruction pop %rbp?
What does the instruction -0x4(%rbp) mean?
How is the function stack implemented in assembler?
Why do buffer overflows present security risks?
What does it mean to reverse engineer a program?
What are the two main jobs of the operating system?
What happens when the operating system runs a program?
Name three operating systems.
What does it mean to say that processes have a "lone view" of the operating system?
What does the OS store in a process?
What must the OS do to context switch between processes?
What is virtual address space (VAS)?
List two advantages of virtual address spaces?
When does the OS send the SIGSEGV signal?
How do we send a kill signal to a process?
What is the difference between an interrupt and a trap?
Why do we need interrupts and traps?
What is a process?
Why do we need special mechanisms, such as pipes or sockets, to communicate between processes?
How can you kill a process using ps ?
What is an orphan process?
What is a zombie process?
What are the different states that a process can be in?
Why might we want to register a signal handler for the SIGINT signal?
For processes to run concurrently, what is needed in terms of hardware?
What is a thread?
What is a mutex?
What is a race condition?
What does it mean for a task to be atomic?
What is deadlock?
What does it mean for a function to be thread safe?
Why and when might we want to use multiple threads?
When might we want to use multiple processes versus multiple threads?
For threads to run concurrently, what is needed in terms of hardware?
When designing a multi-threaded application, what factors should we consider?
What mechanisms can we use to synchronize between threads?
What is a critical section of code?
What is the memory hierarchy?
What are some examples of primary storage?
What are some examples of secondary storage?
What is locality and what impact does it have on performance?
How can a command like malloc keep track of the blocks of memory that the user requests?
In the reading on malloc, what was the purpose of the free list?
What are three characteristics of different types of memory?
What are different metrics we might consider for optimizing a program?
What types of optimizations can the compiler do?
What types of optimizations can the compiler NOT do?
What is function inlining?
What is loop unrolling?
What is the minimum size of the following structures and variables? If the variable is a pointer, give the size of the memory that the pointer points to.
struct Snack {
char name[32];
int quantity;
float cost;
};
struct Snack snacks[2];
Consider navigating directories from the command prompt in UNIX. Suppose you are in your home directory.
How would you create a subdirectory with name foo?
When Willow runs her program from the command line, she gets the following error? What is happening and how can she fix it?
$ ls
Makefile fortune fortune.c hello hello.c
$ hello
Command 'hello' not found
The following program crashes. What is the problem and how can we fix it?
#include <stdio.h>
int main() {
int* value = NULL;
int a = 4;
printf("value is %d\n", *value);
}
The following program crashes. What is the problem and how can we fix it?
#include <stdio.h>
#include <string.h>
void initialize(char text[]) {
strcpy(text, "pina collada");
}
int main() {
char str1[5];
initialize(str1);
printf("%s\n", str1);
return 0;
}
Draw the directory hierarchy that corresponds to the following commands
$ pwd
/home/qwerty
$ mkdir A
$ cd A
$ mkdir Z
$ touch talk.c
When Bella runs valgrind on her program, she receives an error. What is wrong with her program?
// ==2515== Conditional jump or move depends on uninitialised value(s)
// ==2515== at 0x484ED28: strlen
int main() {
char name[16];
for (int i = 0; i < strlen(name)-1; i++) {
name[i] = i+'a';
}
name[15] = '\0';
printf("Name is %s\n", name);
return 0;
}
Draw the stack diagram for the following program.
struct node { struct node* next; };
struct node* insert_front(struct node* head) {
struct node* n = malloc(sizeof(struct node));
n->next = head;
return n;
}
int main() {
struct node* list = insert_front(NULL);
// draw function stack here
}
Convert the following binary numbers to hexadecimal.
0110 1010
Convert the following binary numbers to hexadecimal.
1110 0011
Convert the following binary numbers to hexadecimal.
0110 1110
Convert the following hexadecimal numbers to binary.
0xF5
Convert the following hexadecimal numbers to binary.
0x03
Convert the following hexadecimal numbers to binary.
0x2D
Convert the following decimal numbers to hexadecimal.
72
0x42
Convert the following decimal numbers to hexadecimal.
54
0x36
Convert the following decimal numbers to hexadecimal.
25
0x17
Compute the following using 4-bit unsigned integers. Express your final answer in hexadecimal.
3 << 8
Compute the following using 4-bit unsigned integers. Express your final answer in hexadecimal.
2 & 7
Compute the following using 4-bit signed integers. Express your final answer in hexadecimal.
-6 >> 3
Compute the following using 4-bit signed integers. Express your final answer in hexadecimal.
2 ^ 7
What is the size of this struct? Assume standard data type sizes for x86_64 machines such as goldengate.
struct foo {
float x;
unsigned char c[3];
struct foo* v;
};
Ava implemented the following program to keep track of her finances. However, it’s not working properly. What is going on and how can she fix it?
int main() {
unsigned int balance = 1000;
for (unsigned int i = 10; i >= 0; i--)
{
balance -= 3;
}
return 0;
}
What is the value of flipped?
unsigned char a = 0x7E;
unsigned char leftMask = 0xC0;
unsigned char rightMask = 0x03;
unsigned char left = (leftMask & a) ;
unsigned char right = (rightMask & a) ;
unsigned char leftShift = left >> 4;
unsigned char rightShift = right << 4;
unsigned flipped = leftShift | rightShift;
0x24
Consider the following file permissions.
-rw-r--r-- 1 alinen alinen 191 Sep 10 12:07 greeting.c
-rwxr-xr-x 1 alinen alinen 15960 Sep 3 12:33 hello
-rw-r--r-- 1 alinen alinen 73 Sep 3 12:26 hello.cWhat octal number corresponds to the file permissions for hello.c?
0644, or 110 100 100
Suppose we have a 4-bit bit field that stores whether an animal can fly, swim, or walk, defined with the following masks
#define NONE 0x0
#define FLY 0x1
#define SWIM 0x2
#define WALK 0x4Suppose an animal’s bitfield contains the value 0x3. What capabilities does it have?
Does the following code produce an orphan process? Why or why not?
if (fork() == 0)
{
printf("Child, PID = %d\n", getpid());
exit(0);
}
else {
printf("Parent, PID = %d\n", getpid());
while(1) {}
}
Does the following code produce a zombie process? Why or why not?
if (fork() == 0)
{
printf("Child, PID = %d\n", getpid());
exit(0);
}
else {
printf("Parent, PID = %d\n", getpid());
while(1) {}
}
What possible outputs are there for this program?
int main() {
pid_t ret;
printf("A\n");
ret = fork();
if(ret == 0) {
printf("B\n");
ret = fork();
if(ret == 0) {
printf("C\n");
}
printf("D\n");
}
return 0;
}
ABCDD
ABDCD
How many times is Z printed?
int main() {
pid_t ret;
printf("A\n");
for (int i = 0; i < 3; i++) {
ret = fork();
if (ret == 0) {
printf("B\n");
}
}
printf("Z\n");
return 0;
}
8
How many times is B printed in the following example?
int main() {
pid_t ret;
printf("A\n");
for (int i = 0; i < 3; i++) {
ret = fork();
if (ret == 0) {
printf("B\n");
}
}
printf("Z\n");
return 0;
}
7 times
What is the output of the following program?
#include <stdio.h>
typedef void (*functionType)(int a, int b);
void example(int a, int b) {
printf("This is a function stored as data! %d %d\n", a, b);
}
int main() {
functionType myFunction = example;
(*myFunction)(10, 3);
}
Which of the following dereferences are safe?
void* generic = NULL;
int a = 3;
double b = 4.5;
generic = &b;
printf("test %f\n", *generic); // 1
printf("test %f\n", *((double *) generic)); // 2
printf("test %d\n", *((int *) generic)); // 3
1) Doesn't compile
2) Safe
3) Unsafe
Suppose a serial program takes 10 seconds to run but only 2 seconds with 4 cores. What is the efficiency?
speedup = Ts/Tp = 10/2 = 5
efficiency = speedup/ncores = 5/4
Suppose a program is 90% parallelizable and the serial version of the program (e.g. the one with one thread) takes 10 seconds to run. What is the speedup if we have 5 cores?
== Question
Suppose a program is 90% parallelizable and the serial version of the program
(e.g. the one with one thread) takes 10 seconds to run.
What is the theoretical best case speedup if we have infinitely many cores?
speedup = Ts/Tp = Ts/((0.9/5) * Ts + 0.1 * Ts) ~ 3.57
== Question
Draw a stack diagram for the following program. Show all intermediate values.
speedup = Ts/Tp = Ts/((0.9/inf) * Ts + 0.1 * Ts) = 10
#include <stdio.h>
int main() {
int vals[4] = {1,2,3,4};
for (int* ptr = vals; ptr < vals+4; ptr++) {
printf("%p %d\n", ptr, *ptr);
}
return 0;
}
The following program segmentation faults. What is the error?
#include <stdio.h>
int main() {
int* value = NULL;
printf("value is %d\n", *value);
int a = 4;
value = &a;
printf("value is %d\n", *value);
}
In the following code, give a variable whose usage has temporal locality. Give a variable with spatial locality.
#include <stdio.h>
int main() {
int i, size = 0;
int my_arr[10];
for (i = 0; i < 10; i++) {
my_arr[i] = i;
size++;
}
return 0;
}How the following code would change after constant folding?
#define N 5
int test1 = N - 4;
int test2 = N + 4;
Can the compiler optimize the following code? If no, how can we make the following code more efficient?
char text[64];
scanf(" %s", text);
int sum = 0;
for (int i = 0; i < strlen(text); i++) {
sum += text[i];
}
How would the following code change after constant propagation and dead code removed?
int debug = 0;
//sums up all the elements in an array
int doubleSum(int *array, int length){
int i, total = 0;
for (i = 0; i < length; i++){
total += array[i];
if (debug) {
printf("array[%d] is: %d\n", i, array[i]);
}
}
return 2 * total;
}
How would the following code change after unrolling the loop?
void loopDeLoo(float* pos, float scale){
int i;
for (i = 0; i < 3; i++){
pos[i] = scale * pos[i];
}
}
Why can’t the following code be optimized by the compiler?
void shiftAdd(int *a, int *b){
*a = *a * 10; //multiply by 10
*a += *b; //add b
}
Memory aliasing: the two pointers might refer to the same data or different
data. The compiler can't be sure and so does not risk altering the program
behavior by changing the code.
What in the following code can’t be optimized by the compiler?
int main() {
char test[32];
strcpy(test, "hello");
for (int i = 0; i < strlen(test); i++) {
printf("%c\n", test[i]);
if (i == 0) {
strcpy(test, "hello!");
}
}
}
Moving the call to strlen could change the behavior of the program, so the
compiler will not move it out of the loop. The programmer should avoid calling
functions repeatedly in a loop unless necessary.