tech
CS2106 Lab
trivial ideas or great ideas
CS2106 lab
lab1
Task1:
Objective:
-
to learn how to code with multiple files, using headers.
-
to learn function pointers and pointer.
int func1(int x) {} int *func2(int x) {} // is a function that returns a pointer int (*fptr)(int x); // is a pointer to a function. fptr = func1; // we can assign a function to the func_pointer
Task2:
Objective:
- to learn how global data and local data are stored.
Global variables and static function variables will be stored in .data
Function variables will be stored on stack. - Static is stored on .bss if not initialized, and is stored on .data if initialized. The static variable is not created when function is called, instead it is created as the program starts. Its address will never be changed, so we can safely extract data from it throughout the execution
- Global static: restrains the variable scope within the same file
Local static: keep the local variable independent from function calls.
Task3:
Objective:
- malloc is creating a space on the heap.
- memcpy can copy any memory block,
p->name = (char *) malloc(strlen(name) + 1);
memcpy(p->name, name, strlen(name) + 1);
Task4:
Use linked list to build a file directory.
Significance:
TLinkedList // stores the struct data
*TlinkedList // stores the pointer to the struct. We need it because we can store prev and nxt;
**TLinkedList //stores the address of the address of the linked list node. We can switch between linked lists using this pointer.
// Implement a double linked-list
#include "llist.h"
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
// Initialize the linked list by setting head to NULL
// PRE: head is the pointer variable that points to the
// first node of the linked list
// POST: head is set to NULL
void init_llist(TLinkedList **head) {
*head = NULL;
}
// Create a new node
// PRE: filename = name of file to be inserted
// filesize = size of file in blocks
// startblock = File's starting block
// RETURNS: A new node containing the file information is created.
TLinkedList *create_node(char *filename, int filesize, int startblock) {
TLinkedList* node = (TLinkedList*)malloc(sizeof(TLinkedList));
strcpy(node->filename, filename);
node->filesize = filesize;
node->startblock = startblock;
node->next = NULL;
node->prev = NULL;
return node;
}
// Insert node into the end of the linkedlist indicated by head
// PRE: head = Pointer variable pointing to the start of the linked list
// node = Node created using create_node
// POST: node is inserted into the linked list.
void insert_llist(TLinkedList **head, TLinkedList *node) {
// int cnt = 0;
// printf("inside insert_llist");
if (*head == NULL) {
*head = node;
return ;
}
TLinkedList *head_cpy = *head;
while ((head_cpy)->next != NULL) {
// printf("%d\n", cnt++);
head_cpy = (head_cpy)->next;
}
(head_cpy)->next = node;
node->prev = (head_cpy);
return ;
}
// Delete node from the linkedlist
// PRE: head = Pointer variable pointing to the start of the linked list
// node = An existing node in the linked list to be deleted.
// POST: node is deleted from the linked list
void delete_llist(TLinkedList **head, TLinkedList *node) {
if (node == *head) {
*head = node->next;
free(node);
if (*head != NULL) {
(*head)->prev = NULL;
}
} else {
if (node->next == NULL) {
node->prev->next = NULL;
free(node);
} else {
node->prev->next = node->next;
node->next->prev = node->prev;
free(node);
}
}
}
// Find node in the linkedlist
// PRE: head = Variable that points to the first node of the linked list
// fname = Name of file to look for
// RETURNS: The node that contains fname, or NULL if not found.
TLinkedList *find_llist(TLinkedList *head, char *fname) {
TLinkedList *head_cpy = head;
while (head_cpy != NULL) {
if (*head_cpy->filename == *fname) {
// printf("head_cpy: %p, head: %p\n", head_cpy, head);
return head_cpy;
}
head_cpy = head_cpy->next;
}
// printf("head_cpy: %p, head: %p\n", head_cpy, head);
return NULL;
}
// Traverse the entire linked list calling a function
// PRE: head = Variable pointing to the first node of the linked list
// fn = Pointer to function to be called for each node
// POST: fn is called with every node of the linked list.
void traverse(TLinkedList **head, void (*fn)(TLinkedList *)) {
TLinkedList *head_cpy = *head;
while ((head_cpy) != NULL) {
fn(head_cpy);
head_cpy = head_cpy->next;
}
}
lab2
This lab asks us to design a shell that can run and stop processes. We need to follow the picture below.
We need to implement:
{program}(args...) // wait until program exits
{program}(args...)& // run in background
info option (0: all processes, 1: # of exited processes, 2: # of running processes, 3: # of terminating processes) //print info
quit //terminate all running processes using SIGTERM, and print "killing [pid]" for each terminated process. Don't wait for child processes, print "Goodbye!" and exit the shell
wait{PID} //block until PID done
terminate {PID} //send SIGTERM, state of {PID} should be "Terminating" until {PID} exits.
{program1} (args1...) ; {program2} (args2...) ; ... //execute each command sequentially.
{program} (args...) (< {file}) (> {file}) (2> {file}) // < {file}: reads {file} as input, > {file}: redirect stdout into {file}, 2> {file}: redirect stderr to {file}
{program} (args...) (< {file}) (> {file}) (2> {file}) &: run in background version
{program} (args...) (< {file}) (> {file}) (2> {file}); {program} (args...) (< {file}) (> {file}) (2> {file}); ...
Design:
maintaining PCBTable to keep track of the status of the process
quit: find all running processes, send SIGKILL to them.
When receiving a command, I first do preliminary parsing, to see:
- if it is a sequence. If it is, then redirect()->execute_program() for each one of the commands
- if it is info. -> getinfo()
- if it is wait. -> if running, then waitpid
- if it is terminate. -> if running, then send SIGKILL, and call terminate_process() to update PCBTable
- if it is running in background -> if background, call redirect()->execute_program() to handle.
Redirect: handles input, output, and call execute_program(), send file arguments to execute_program()
execute_program: handles background or wait
/**
* CS2106 AY25/26 Semester 1 - Lab 2
*
* This file contains function definitions. Your implementation should go in
* this file.
*/
#include "myshell.h"
#include <signal.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <sys/wait.h>
#include <stdbool.h>
int pid_count;
const char* status_string[5] = {"Error", "Exited", "Running", "Terminating", "Stopping"};
struct PCBTable processes[60];
void get_info(int option);
void execute_program(size_t num_tokens, char **tokens, bool immediate, char* input_file, char* output_file, char* err_file);
bool currently_running(int pid);
void create_process(int ppid);
void exit_process(int ppid, int return_val);
void terminate_process(int pid);
void check_status();
int min(int a, int b) {
return a < b ? a : b;
}
void my_init(void) {
for (int i = 0; i < 60; i++) {
processes[i].pid = -1;
processes[i].status = -1;
processes[i].exitCode = -1;
}
// Initialize what you need here
pid_count = 0;
}
void my_process_command(size_t num_tokens, char **tokens) {
bool is_sequential = false;
for (int i = 0; i < num_tokens - 1; i++) {
if (strcmp(tokens[i], ";") == 0) {
is_sequential = true;
break;
}
}
// printf("is_sequential: %d\n", is_sequential);
int start = 0;
int end = 0;
if (is_sequential) {
while (1) {
// printf("%d\n", end);
if (tokens[end] == NULL || strcmp(tokens[end], ";") == 0) {
char **slice = malloc((end - start + 1) * sizeof(char*));
for (int i = start; i < end; i++) {
slice[i - start] = tokens[i];
}
slice[end - start] = NULL;
redirect(end - start + 1, slice, false);
start = end + 1;
if (tokens[end] == NULL) {
// printf("already breaked!\n");
break;
}
}
end++;
}
} else if (strcmp(tokens[0], "info") == 0) {
if (num_tokens != 3) {
fprintf(stderr, "Wrong command\n");
return ;
}
get_info(atoi(tokens[1]));
} else if (strcmp(tokens[0], "wait") == 0) {
int pid = atoi(tokens[1]);
if (currently_running(pid)) {
int status;
waitpid(pid, &status, 0);
}
} else if (strcmp(tokens[0], "terminate") == 0) {
int pid = atoi(tokens[1]);
if (currently_running(pid)) {
kill(pid, SIGTERM);
terminate_process(pid);
}
}
else {
// printf("it is a program\n");
// printf("%d\n", num_tokens);
// printf("%s\n", tokens[num_tokens - 2]);
if (strcmp(tokens[num_tokens - 2], "&") == 0) {
char** prog_tokens = malloc(sizeof(char*) * (num_tokens - 1));
for (int i = 0; i < num_tokens - 1; i++) {
prog_tokens[i] = tokens[i];
}
redirect(num_tokens - 1, prog_tokens, true);
} else {
redirect(num_tokens, tokens, false);
}
}
}
void redirect(size_t num_tokens, char** tokens_, bool immediate) {
// printf("redirecting\n\n");
// printf("immd: %d\n", immediate);
char* input_file = malloc(sizeof(char) * 100);
char* output_file = malloc(sizeof(char) * 100);
char* err_file = malloc(sizeof(char) * 100);
input_file = NULL;
output_file = NULL;
err_file = NULL;
// for (int i = 0; i < num_tokens; i++) {
// printf("%s ", tokens_[i]);
// }
int end_token = num_tokens - 1;
for (int i = 0; i < num_tokens - 1; i++) { // to exclude the null
// printf("i = %d\n", i);
if (strcmp(tokens_[i], "<") == 0) {
input_file = tokens_[i + 1];
end_token = min(end_token, i);
} else if (strcmp(tokens_[i], ">") == 0) {
output_file = tokens_[i + 1];
end_token = min(end_token, i);
} else if (strcmp(tokens_[i], "2>") == 0) {
err_file = tokens_[i + 1];
end_token = min(end_token, i);
}
}
char** tokens = malloc(sizeof(char*) * (end_token + 1));
for (int i = 0; i < end_token; i++) {
tokens[i] = tokens_[i];
}
// printf("input_file: %s, output_file: %s, err_file: %s\n", input_file, output_file, err_file);
execute_program(end_token + 1, tokens, immediate, input_file, output_file, err_file);
}
void execute_program(size_t num_tokens, char **tokens, bool immediate, char* input_file, char* output_file, char* err_file) {
// printf("executing\n\n");
// printf("input == NULL?: %d\n", input_file == NULL);
FILE *fin = NULL;
FILE *fout = NULL;
FILE *ferr = NULL;
if (immediate) {
pid_t pid = fork();
if (pid == 0) {
if (input_file != NULL) {
fin = freopen(input_file, "r", stdin);
if (!fin) {
// freopen("/dev/tty", "r", stdin);
printf("%s does not exist\n", input_file);
_exit(1);
}
}
if (output_file != NULL) {
// printf("opening output file\n");
fout = freopen(output_file, "w", stdout);
}
if (err_file != NULL) {
ferr = freopen(err_file, "w", stderr);
}
int success = execv(tokens[0], tokens);
if (success == -1) {
fprintf(stderr, "%s not found\n", tokens[0]);
// close_redirection(input_file, output_file, err_file);
return ;
}
} else {
create_process(pid);
printf("Child [%d] in background\n", pid);
}
} else {
// printf("will wait\n");
pid_t pid = fork();
if (pid == 0) {
if (input_file != NULL) {
fin = freopen(input_file, "r", stdin);
if (!fin) {
printf("%s does not exist\n", input_file);
_exit(1);
}
}
if (output_file != NULL) {
// printf("opening output file\n");
fout = freopen(output_file, "w", stdout);
}
if (err_file != NULL) {
ferr = freopen(err_file, "w", stderr);
}
int success = execv(tokens[0], tokens);
// perror("execv failed");
if (success == -1) {
fprintf(stderr, "%s not found\n", tokens[0]);
// close_redirection(input_file, output_file, err_file);
return ;
}
} else {
create_process(pid);
// printf("tokens: ");
// for (int i = 0; i < num_tokens; i++) {
// printf("%s ", tokens[i]);
// }
// printf("\n");
int status;
waitpid(pid, &status, 0);
// printf("pid: %d\n", pid);
if (WIFEXITED(status)) {
// printf("WEXITSTATUS: %d\n", WEXITSTATUS(status));
exit_process(pid, WEXITSTATUS(status));
} else {
printf("not correctly returned\n");
}
}
}
// printf("closing redirection\n");
// close_redirection(input_file, output_file, err_file);
// printf("closed redirection\n\n");
return ;
}
void create_process(int ppid) {
// printf("[%d] created\n", ppid);
processes[pid_count].pid = ppid;
processes[pid_count].status = 2;
processes[pid_count].exitCode = -1;
pid_count++;
}
void exit_process(int ppid, int return_val) {
// printf("ppid: %d\nreturn_val: %d\n", ppid, return_val);
for (int i = 0; i < pid_count; i++) {
if (processes[i].pid == ppid) {
processes[i].exitCode = return_val;
processes[i].status = 1;
}
}
}
void terminate_process(int pid) {
for (int i = 0; i < pid_count; i++) {
if (processes[i].pid == pid) {
processes[i].status = 3;
processes[i].exitCode = SIGTERM;
}
}
}
void my_quit(void) {
check_status();
// Clean up function, called after "quit" is entered as a user command
for (int i = 0; i < pid_count; i++) {
if (processes[i].status ==2) {
kill(processes[i].pid, SIGTERM);
printf("killing [%d]\n", processes[i].pid);
}
}
for (int i = 0; i < 60; i++) {
processes[i].pid = -1;
processes[i].status = -1;
processes[i].exitCode = -1;
}
printf("\nGoodbye\n");
}
char* status_tostring(int s) {
switch (s)
{
case 1:
return "Exited";
/* code */
break;
case 2:
return "Running";
break;
case 3:
return "Terminating";
break;
case 4:
return "Stopped";
break;
default:
return "Error";
break;
}
}
void check_status() {
for (int i = 0; i < pid_count; i++) {
if (processes[i].status != 1) {
int status;
int ret = waitpid(processes[i].pid, &status, WNOHANG);
if (ret != 0) {
if (WIFSIGNALED(status)) {
exit_process(processes[i].pid, WTERMSIG(status));
} else {
exit_process(processes[i].pid, WEXITSTATUS(status));
}
}
}
}
return ;
}
bool currently_running(int pid) {
for (int i = 0; i < pid_count; i++) {
if (processes[i].pid == pid) {
if (processes[i].status == 2) {
return true;
} else {
return false;
}
}
}
return false;
}
void get_info(int option) {
check_status();
if (option == 0) { // print details
for (int i = 0; i < pid_count; i++) {
printf("[%d] ", processes[i].pid);
printf("%s ", status_string[processes[i].status]);
if (processes[i].status == 1) {
printf("%d", processes[i].exitCode);
}
printf("\n");
}
} else if (option == 1) { // print # of exited
int exit_count = 0;
for (int i = 0; i < pid_count; i++) {
if (processes[i].status == 1) {
exit_count++;
}
}
printf("Total exited process: %d\n", exit_count);
} else if (option == 2) { // print # of running
int running_count = 0;
for (int i = 0; i < pid_count; i++) {
if (processes[i].status ==2) {
running_count++;
}
}
printf("Total running process: %d\n", running_count);
} else if (option == 3) {
int terminating_count = 0;
for (int i = 0; i < pid_count; i++) {
if (processes[i].status ==2) {
terminating_count++;
}
}
printf("Total terminating process: %d\n", terminating_count);
} else {
fprintf(stderr, "Wrong command\n");
return ;
}
}
lab3
Task1
Objective:
- turn variables: use a global turn variable, that specifies this time who is able to execute. Those that cannot execute have to busy waiting.
- Use semaphore to implement the same thing. Set the first semaphore to 1, others to 0. And when the process is done executing, post the next semaphore
Task2
To design a program, where:
There is a barrier where all processes will be blocked at first, and only when the last process comes, it will unblock. In other words, processes are allowed to go only when all processes have reached the barrier.
Objectives:
- learn to design with semaphores
Design:
I have three semaphores:
- barrier: initialized to 0, because initially I don’t want anyone to pass the barrier unless all have reached.
- mutex[0]: initialized to 1. This is to guarantee the count of reached children.
- mutex[1]: initialized to 1. This is to guarantee the count of passed children.
In reach_barrier, I first use count to see if all processes have reached. If yes, then I will update barrier to let everyone go. But one thing to note here is that before everyone passed, no processes should be allowed to enter the next iteration. So I set mutex[0] as 0 to block the processes from going further. After using count to ensure all processes have passed, I set mutex[0] back to 1 to start the next iteration.
#include <stdio.h>
#include <semaphore.h>
#include <sys/shm.h>
#include <sys/wait.h>
sem_t *barrier;
sem_t *mutex;
int nproc;
int *count = 0;
int shmid_barrier, shmid_mutex, shmid_count;
void init_barrier(int numproc) {
shmid_barrier = shmget(IPC_PRIVATE, sizeof(sem_t), IPC_CREAT |0600);
barrier = (sem_t *)shmat(shmid_barrier, NULL, 0);
shmid_mutex = shmget(IPC_PRIVATE, sizeof(sem_t) * 2, IPC_CREAT | 0600);
mutex = (sem_t *)shmat(shmid_mutex, NULL, 0);
shmid_count = shmget(IPC_PRIVATE, sizeof(int) * 2, IPC_CREAT | 0600);
count = (int*)shmat(shmid_count, NULL, 0);
nproc = numproc;
sem_init(barrier, 1, 0);
sem_init(&mutex[0], 1, 1);
sem_init(&mutex[1], 1, 1);
}
void reach_barrier() {
sem_wait(&mutex[0]);
(count[0])++;
int val;
sem_getvalue(barrier, &val);
// printf("count: %d\tbarrier: %d\tproc: %d\n", *count, val, nproc);
sem_post(&mutex[0]);
if (count[0] == nproc) {
sem_wait(&mutex[0]);
count[0] = 0;
for (int i = 1; i < nproc; i++) sem_post(barrier);
} else {
// printf("arrived\n");
sem_wait(barrier);
sem_wait(&mutex[1]);
count[1]++;
sem_post(&mutex[1]);
if (count[1] == nproc - 1) {
count[1] = 0;
sem_post(&mutex[0]);
}
// printf("released\n");
sem_getvalue(barrier, &val);
// printf("barrier: %d\n", val);
}
}
void destroy_barrier(int my_pid) {
if(my_pid != 0) {
shmdt(mutex);
shmdt(barrier);
shmdt(count);
shmctl(shmid_barrier, IPC_RMID, NULL);
shmctl(shmid_mutex, IPC_RMID, NULL);
shmctl(shmid_count, IPC_RMID, NULL);
sem_destroy(barrier);
sem_destroy(mutex);
// Destroy the semaphores and detach
// and free any shared memory. Notice
// that we explicity check that it is
// the parent doing it.
}
}
Task3
Objectives:
- fork() creates child processes; pthread_create creates threads. Threads share the same .data, .code; but has different register and stack. Child processes shares nothing. So here H2O factory are threads, so we don't need to create shared memory. Idea is the same as Task2.
However I used share memory in this task.
Design:
I use mutex[0] to block oxygen arrival. When oxygen atom arrives, block it until it combines.
I use mutex[1] to block hydrogen arrival. When two hydrogen atom arrive, block it until it combines. Also it eliminates race condition.
I use mutex[2] to eliminate race conditions when counting how many oxygen and hydrogen atoms have combined.
Count[0]: number of O arrived
Count[1]: number of H arrived
Count[2]: number of released atoms.
I also use barrier to block the threads if the ingredients are not ready yet. If I checked that the ingredients are ready, I raise the barrier. Only after all atoms are combined, I signal mutex[0] and mutex[1] to continue to the next iteration.
/**
* CS2106 AY 25/26 Semester 1 - Lab 3
*
* Your implementation should be in this file.
*/
#include <stdio.h>
#include <semaphore.h>
#include <sys/shm.h>
#include <sys/wait.h>
// #include "barrier.h"
// static H2O h2o;
sem_t *barrier;
sem_t *mutex; //0 for oxygen, 1 for hy
int *count; //0 for oxygen, 1 for h
int shmid_barrier, shmid_mutex, shmid_count;
// Your initialization code goes here
void h2o_init() {
shmid_barrier = shmget(IPC_PRIVATE, sizeof(sem_t), IPC_CREAT |0600);
barrier = (sem_t *)shmat(shmid_barrier, NULL, 0);
shmid_mutex = shmget(IPC_PRIVATE, sizeof(sem_t) * 3, IPC_CREAT | 0600);
mutex = (sem_t *)shmat(shmid_mutex, NULL, 0);
shmid_count = shmget(IPC_PRIVATE, sizeof(int) * 3, IPC_CREAT | 0600);
count = (int*)shmat(shmid_count, NULL, 0);
sem_init(barrier, 1, 0);
sem_init(&mutex[0], 1, 1);
sem_init(&mutex[1], 1, 1);
sem_init(&mutex[2], 1, 1);
count[0] = 0;
count[1] = 0;
count[2] = 0;
}
// Synchronization code for hydrogen thread
void hydrogen_thread(void (*releaseHydrogen)(void)) {
sem_wait(&mutex[1]);
// printf("H arrived\n");
count[1]++;
// printf("H count: %d\n", count[1]);
sem_post(&mutex[1]);
if (count[1] == 2) {
sem_wait(&mutex[1]);
if (count[0] == 1) {
releaseHydrogen();
count[1] = 0;
for (int i = 1; i <= 2; i++) sem_post(barrier);
} else {
sem_wait(barrier);
// printf("H passed\n");
sem_wait(&mutex[2]);
releaseHydrogen();
count[2]++;
// printf("pass count: %d\n", count[2]);
sem_post(&mutex[2]);
if (count[2] == 2) {
count[2] = 0;
count[0] = 0;
count[1] = 0;
printf("\n");
sem_post(&mutex[0]);
sem_post(&mutex[1]);
}
}
} else {
sem_wait(barrier);
// printf("H passed\n");
sem_wait(&mutex[2]);
releaseHydrogen();
count[2]++;
// printf("pass count: %d\n", count[2]);
sem_post(&mutex[2]);
if (count[2] == 2) {
count[2] = 0;
count[0] = 0;
count[1] = 0;
printf("\n");
sem_post(&mutex[0]);
sem_post(&mutex[1]);
}
}
}
// Synchronization code for oxygen thread
void oxygen_thread(void (*releaseOxygen)(void)) {
sem_wait(&mutex[0]);
// printf("O arrived\n");
count[0]++;
// printf("O count: %d\n", count[0]);
if (count[1] == 2) {
releaseOxygen();
count[0] = 0;
for (int i = 1; i <= 2; i++) sem_post(barrier);
} else {
sem_wait(barrier);
// printf("O passed\n");
sem_wait(&mutex[2]);
releaseOxygen();
count[2]++;
// printf("pass count: %d\n", count[2]);
sem_post(&mutex[2]);
if (count[2] == 2) {
count[2] = 0;
count[0] = 0;
count[1] = 0;
printf("\n");
sem_post(&mutex[0]);
sem_post(&mutex[1]);
}
}
}
// Your cleanup code goes here
void h2o_destroy() {
shmdt(mutex);
shmdt(barrier);
shmdt(count);
shmctl(shmid_barrier, IPC_RMID, NULL);
shmctl(shmid_mutex, IPC_RMID, NULL);
shmctl(shmid_count, IPC_RMID, NULL);
sem_destroy(barrier);
sem_destroy(mutex);
}
Comments
No comments yet.