程序代写代做代考 data structure algorithm CSCI 4061 – cscodehelp代写
CSCI 4061
Discussion week 4
Overview
¡ñ fork()
¡ñ exec()
¡ñ wait()
¡ñ Graphs – Representation, BFS and DFS
fork()
¡ñ A system call for creating a new process (child process)
¡ñ After a new child process is created, both parent and child processes will
execute the next instruction following the fork() system call.
¡ñ OS decides which process (between parent and child) will start running
first
¡ñ Return value:
¡ð Negative- creation of child process was unsuccessful
¡ð Zero- returned to the newly created child process
¡ð Positive- returned to the parent (caller). The value is basically the process ID of the
created new process
Example of fork()
pid_t pid = fork();
if (pid > 0) {
printf(¡°I¡¯m the parent!¡±);
} else {
printf(¡°I¡¯m the child!¡±);
}
// Failure omitted.
exec()
¡ñ Deletes the current program state and begins executing a new program.
¡ñ If successful, will not return to old program
¡ñ Has several variants: execl, execv, execp, exece
Example
// The char* cast is needed for NULL.
execl(¡°…path…¡±, (char*) NULL);
printf(¡°The exec call failed!¡±);
exit(1);
wait()
¡ñ Calling wait(NULL) in a parent process will cause it to wait for the next child to finish.
¡ñ After child process terminates, parent continues its execution after wait system call instruction.
Graph Data Structure
¡ñ A Graph is a non-linear data structure consisting of vertices and edges.
¡ñ Graphs are used to solve many real-life problems.
¡ð Graphs are used to represent networks , eg LinkedIn, Facebook
¡ñ Reference : https://www.geeksforgeeks.org/graph-data-structure-and-algorithms/
Graph Representation
¡ñ Adjacency List:
¡ð An array of all the vertices in the graph
¡ð Each element of the array will have a list of other vertices that it is connected to.
¡ð Eg, if List(a) = {b,c}, then vertex a is connected to b and c
¡ñ Adjacency Matrix
¡ð A 2D vector of size V x V, where V is the number of vertices in the
graph.
¡ð If Matrix(a,b) = 1, then there is an edge between vertex a and b
Breadth First Search (BFS)
¡ñ In this search algorithm, we traverse through vertices which are at the same
distance from the starting vertex before moving to a farther vertex.
¡ñ In this example, if B is the starting vertex the order of BFS traversal can be :
¡ð B -> A -> C -> D -> E -> F
Depth First Search (DFS)
¡ñ In this search algorithm, we traverse as far as possible from the starting
vertex before backtracking.
¡ñ In this example, if B is the starting vertex the order of DFS traversal can be :
¡ð B -> A -> D -> E -> C -> F
Today¡¯s Task
¡ñ Take home quiz on canvas: due Tuesday 11:59 PM
¡ñ Lab Exercise (template on canvas):
¡ð Write a program that takes one integer (say n) as command line argument.
¡ð Then it creates two child processes
¡ð The first child prints ¡°hello world¡± using ¡®echo¡¯ through execl() function
¡ð The second child runs the given executable ¡®lab4.o¡¯ (with argument n) using the execv()
function.
¡ð Lab4.0 should print numbers from 0 to n-1
Note:
1. Type in terminal ¡®chmod +x lab4.0¡¯ (if you get permission denied error).
2. Please use linux machines for this exercise.
