SMP5: Scheduler with Signals 

/in /by

SMP5: Scheduler with Signals

In the last MP, we built a simulated OS process scheduler. The scheduler can

hold only a certain number of processes (workers) at one time. Once the process

has been accepted into the scheduler, the scheduler decides in what order the

processes execute. We implemented two scheduling algorithms: FIFO and Round

Robin.

In this MP, we are to simulate a time-sharing system by using signals and

timers. We will only implement the Round Robin algorithm. Instead of using

iterations to model the concept of “time slices” (as in the last MP), we use

interval timers.  The scheduler is installed with an interval timer. The timer

starts ticking when the scheduler picks a thread to use the CPU which in turn

signals the thread when its time slice is finished thus allowing the scheduler

to pick another thread and so on. When a thread has completely finished its work

it leaves the scheduler to allow a waiting thread to enter. Please note that in

this MP, only the timer and scheduler send signals. The threads passively handle

the signals without signaling back to the scheduler.

The program takes a number of arguments. Arg1 determines the number of jobs

(threads in our implementation) created; arg2 specifies the queue size of the

scheduler. Arg3 through argN gives the duration (the required time slices to

complete a job) of each job. Hence if we create 2 jobs, we should supply arg3

and arg4 for the required duration. You can assume that the autograder will

always supply the correct number of arguments and hence you do not have to

detect invalid input.

Here is an example of program output, once the program is complete:

% scheduler 3 2 3 2 3

Main: running 3 workers with queue size 2 for quanta:

3 2 3

Main: detaching worker thread 3075926960.

Main: detaching worker thread 3065437104.

Main: detaching worker thread 3054947248.

Main: waiting for scheduler 3086416816.

Scheduler: waiting for workers.

Thread 3075926960: in scheduler queue.

Thread 3075926960: suspending.

Thread 3065437104: in scheduler queue.

Thread 3065437104: suspending.

Scheduler: scheduling.

Scheduler: resuming 3075926960.

Thread 3075926960: resuming.

Scheduler: suspending 3075926960.

Scheduler: scheduling.

Scheduler: resuming 3065437104.

Thread 3065437104: resuming.

Thread 3075926960: suspending.

Scheduler: suspending 3065437104.

Scheduler: scheduling.

Scheduler: resuming 3075926960.

Thread 3075926960: resuming.

Thread 3065437104: suspending.

Scheduler: suspending 3075926960.

Scheduler: scheduling.

Scheduler: resuming 3065437104.

Thread 3065437104: resuming.

Thread 3075926960: suspending.

Scheduler: suspending 3065437104.

Thread 3065437104: leaving scheduler queue.

Scheduler: scheduling.

Scheduler: resuming 3075926960.

Thread 3075926960: resuming.

Thread 3065437104: terminating.

Thread 3054947248: in scheduler queue.

Thread 3054947248: suspending.

Scheduler: suspending 3075926960.

Thread 3075926960: leaving scheduler queue.

Scheduler: scheduling.

Scheduler: resuming 3054947248.

Thread 3054947248: resuming.

Thread 3075926960: terminating.

Scheduler: suspending 3054947248.

Scheduler: scheduling.

Scheduler: resuming 3054947248.

Thread 3054947248: suspending.

Thread 3054947248: resuming.

Scheduler: suspending 3054947248.

Scheduler: scheduling.

Scheduler: resuming 3054947248.

Thread 3054947248: suspending.

Thread 3054947248: resuming.

Scheduler: suspending 3054947248.

Thread 3054947248: leaving scheduler queue.

Thread 3054947248: terminating.

The total wait time is 12.062254 seconds.

The total run time is 7.958618 seconds.

The average wait time is 4.020751 seconds.

The average run time is 2.652873 seconds.

The goal of this MP is to help you understand (1) how signals and timers work,

and (2) how to evaluate the performance of your program. You will first

implement the time-sharing system using timers and signals. Then, you will

evaluate the overall performance of your program by keeping track of how long

each thread is idle, running, etc.

The program will use these four signals:

SIGALRM: sent by the timer to the scheduler, to indicate another time

quantum has passed.

SIGUSR1: sent by the scheduler to a worker, to tell it to suspend.

SIGUSR2: sent by the scheduler to a suspended worker, to tell it to resume.

SIGTERM: sent by the scheduler to a worker, to tell it to cancel.

You will need to set up the appropriate handlers and masks for these signals.

You will use these functions:

clock_gettime

pthread_sigmask

pthread_kill

sigaction

sigaddset

sigemptyset

sigwait

timer_settime

timer_create

Also, make sure you understand how the POSIX:TMR interval timer works.

There are two ways you can test your code.  You can run the built-in grading

tests by running “scheduler -test -f0 rr”.  This runs 5 tests, each of which can

be run individually.  You can also test you program with specific parameters by

running “scheduler -test gen …” where the ellipsis contains the parameters you

would pass to scheduler.

Programming

===========

Part I: Modify the scheduler code (scheduler.c)

———————————————–

We use the scheduler thread to setup the timer and handle the scheduling for the

system.  The scheduler handles the SIGALRM events that come from the timer, and

sends out signals to the worker threads.

Step 1.

Modify the code in init_sched_queue() function in scheduler.c to initialize the

scheduler with a POSIX:TMR interval timer. Use CLOCK_REALTIME in timer_create().

The timer will be stored in the global variable “timer”, which will be started

in scheduler_run() (see Step 4 below).

Step 2.

Implement setup_sig_handlers().  Use sigaction() to install signal handlers for

SIGALRM, SIGUSR1, and SIGTERM.  SIGALRM should trigger timer_handler(), SIGUSR1

should trigger suspend_thread(), and SIGTERM should trigger cancel_thread().

Notice no handler is installed for SIGUSR2; this signal will be handled

differently, in step 8.

Step 3.

In the scheduler_run() function, start the timer.  Use timer_settime().  The

time quantum (1 second) is given in scheduler.h.  The timer should go off

repeatedly at regular intervals defined by the timer quantum.

In Round-Robin, whenever the timer goes off, the scheduler suspends the

currently running thread, and tells the next thread to resume its operations

using signals. These steps are listed in timer_handler(), which is called every

time the timer goes off.  In this implementation, the timer handler makes use of

suspend_worker() and resume_worker() to accomplush these steps.

Step 4.

Complete the suspend_worker() function.  First, update the info->quanta value.

This is the number of quanta that remain for this thread to execute.  It is

initialized to the value passed on the command line, and decreases as the thread

executes.  If there is any more work for this worker to do, send it a signal to

suspend, and update the scheduler queue.  Otherwise, cancel the thread.

Step 5.

Complete the cancel_worker() function by sending the appropriate signal to the

thread, telling it to kill itself.

Step 6.

Complete the resume_worker() function by sending the appropriate signal to the

thread, telling it to resume execution.

Part II: Modify the worker code (worker.c)

——————————————

In this section, you will modify the worker code to correctly handle the signals

from the scheduler that you implemented in the previous section.

You need to modify the thread functions so that it immediately suspends the

thread, waiting for a resume signal from the scheduler. You will need to use

sigwait() to force the thread to suspend itself and wait for a resume signal.

You need also to implement a signal handler in worker.c to catch and handle the

suspend signals.

Step 7.

Modify start_worker() to (1) block SIGUSR2 and SIGALRM, and (2) unblock SIGUSR1

and SIGTERM.

Step 8.

Implement suspend_thread(), the handler for the SIGUSR1 signal.  The

thread should block until it receives a resume (SIGUSR2) signal.

Part III: Modify the evaluation code (scheduler.c)

————————————————–

This program keeps track of run time, and wait time.  Each thread saves these

two values regarding its own execution in its thread_info_t.  Tracking these

values requires also knowing the last time the thread suspended or resumed.

Therefore, these two values are also kept in thread_info_t.  See scheduler.h.

In this section, you will implement the functions that calculate run time and

wait time.  All code that does this will be in scheduler.c.  When the program

is done, it will collect all these values, and print out the total and average

wait time and run time.  For your convenience, you are given a function

time_difference() to compute the difference between two times in microseconds.

Step 9.

Modify create_workers() to initialize the various time variables.

Step 10.

Implement update_run_time().  This is called by suspend_worker().

Step 11.

Implement update_wait_time().  This is called by resume_worker().

Questions

==========

Question 1.

Why do we block SIGUSR2 and SIGALRM in worker.c?  Why do we unblock SIGUSR1 and

SIGTERM in worker.c?

Question 2.

We use sigwait() and sigaction() in our code. Explain the difference between the

two. (Please explain from the aspect of thread behavior rather than syntax).

Question 3.

When we use POSIX:TMR interval timer, we are using relative time. What is the

alternative? Explain the difference between the two.

Question 4.

Look at start_worker() in worker.c, a worker thread is executing within an

infinite loop at the end. When does a worker thread terminate?

Question 5.

When does the scheduler finish?  Why does it not exit when the scheduler queue

is empty?

Question 6.

After a thread is scheduled to run, is it still in the sched_queue? When is it

removed from the head of the queue? When is it removed from the queue completely?

Question 7.

We’ve removed all other condition variables in SMP4, and replaced them with a

timer and signals. Why do we still use the semaphore queue_sem?

Question 8.

What’s the purpose of the global variable “completed” in scheduler.c? Why do we

compare “completed” with thread_count before we wait_for_queue() in

next_worker()?

Question 9.

We only implemented Round Robin in this SMP. If we want to implement a FIFO

scheduling algorithm and keep the modification as minimum, which function in

scheduler.c is the one that you should modify? Briefly describe how you would

modify this function.

Question 10.

In this implementation, the scheduler only changes threads when the time quantum

expires.  Briefly explain how you would use an additional signal to allow the

scheduler to change threads in the middle of a time quantum.  In what situations

would this be useful?

MACOSX/assign3/assign3_part2/._Makefile

/in /by

__MACOSX/._assign3

assign3/.DS_Store

__MACOSX/assign3/._.DS_Store

assign3/assign3_part2/list.c

#include <stdio.h> #include “list.h” /* list helper functions */ int list_size(thread_info_list *list) { int cnt = 0; if (!list) return -1; pthread_mutex_lock(&list->lock); list_elem *le = list->head; while (le) { cnt++; le = le->next; } pthread_mutex_unlock(&list->lock); return cnt; } int list_insert_head(thread_info_list *list, list_elem *new) { if (!list || !new) return -1; pthread_mutex_lock(&list->lock); new->next = list->head; new->prev = 0; if (new->next) { new->next->prev = new; } list->head = new; if (list->tail == 0) { list->tail = new; } pthread_mutex_unlock(&list->lock); return 0; } int list_insert_tail(thread_info_list *list, list_elem *new) { if (!list || !new) return -1; pthread_mutex_lock(&list->lock); new->prev = list->tail; new->next = 0; if (new->prev) { new->prev->next = new; } list->tail = new; if (list->head == 0) { list->head = new; } pthread_mutex_unlock(&list->lock); return 0; } int list_remove(thread_info_list *list, list_elem *old) { if (!old || !list) return -1; pthread_mutex_lock(&list->lock); if (old->next) { old->next->prev = old->prev; } if (old->prev) { old->prev->next = old->next; } if (list->tail == old) { list->tail = old->prev; } if (list->head == old) { list->head = old->next; } old->next = old->prev = 0; pthread_mutex_unlock(&list->lock); return 0; } void print_list(thread_info_list *list) { pthread_mutex_lock(&list->lock); list_elem *le = list->head; while (le) { printf(“0x%X,”, (unsigned int)le->info); le = le->next; } pthread_mutex_unlock(&list->lock); printf(“\n”); }

__MACOSX/assign3/assign3_part2/._list.c

assign3/assign3_part2/worker.c

#include <stdio.h> #include <errno.h> #include <stdlib.h> #include <string.h> #include <signal.h> #include “scheduler.h” /******************************************************************************* * * Implement these functions. * ******************************************************************************/ /* Handler for SIGTERM signal */ void cancel_thread() { printf(“Thread %u: terminating.\n”, (unsigned int)pthread_self()); /* signal that done in queue */ sem_post(&queue_sem); pthread_exit(NULL); } /* TODO: Handle the SIGUSR1 signal */ void suspend_thread() { printf(“Thread %u: suspending.\n”, (unsigned int)pthread_self()); /*add your code here to wait for a resume signal from the scheduler*/ printf(“Thread %u: resuming.\n”,(unsigned int) pthread_self()); } /******************************************************************************* * * * ******************************************************************************/ /* * waits to gain access to the scheduler queue. */ static int enter_scheduler_queue(thread_info_t *info) { /* * wait for available room in queue. * create a new list entry for this thread * store this thread info in the new entry. */ sem_wait(&queue_sem); list_elem *item = (list_elem*)malloc(sizeof(list_elem)); info->le = item; item->info = info; item->prev = 0; item->next = 0; list_insert_tail(&sched_queue, item); return 0; } /* * leaves the scheduler queue */ void leave_scheduler_queue(thread_info_t *info) { printf(“Thread %lu: leaving scheduler queue.\n”, info->thrid); /* * remove the given worker from queue * clean up the memory that we malloc’d for the list * clean up the memory that was passed to us */ list_remove(&sched_queue, info->le); free(info->le); free(info); } /* * Initialize thread, enter scheduling queue, and execute instructions. * arg is a pointer to thread_info_t */ void *start_worker(void *arg) { thread_info_t *info = (thread_info_t *) arg; float calc = 0.8; int j = 0; /* TODO: Block SIGALRM and SIGUSR2. */ /* TODO: Unblock SIGUSR1 and SIGTERM. */ /* compete with other threads to enter queue. */ if (enter_scheduler_queue(info)) { printf(“Thread %lu: failure entering scheduler queue – %s\n”, info->thrid, strerror(errno)); free (info); pthread_exit(0); } printf(“Thread %lu: in scheduler queue.\n”, info->thrid); suspend_thread(); while (1) { /* do some meaningless work… */ for (j = 0; j < 10000000; j++) { calc = 4.0 * calc * (1.0 – calc); } } }

__MACOSX/assign3/assign3_part2/._worker.c

assign3/assign3_part2/Makefile

CC = gcc CCOPTS = -c -g -Wall LINKOPTS = -g -pthread -Wall EXEC=scheduler OBJECTS=scheduler.o worker.o list.o smp5_tests.o testrunner.o all: $(EXEC) $(EXEC): $(OBJECTS) $(CC) $(LINKOPTS) -o $@ $^ -lrt %.o:%.c $(CC) $(CCOPTS) -o $@ $^ clean: – $(RM) $(EXEC) – $(RM) $(OBJECTS) – $(RM) *~ – $(RM) core.* test: scheduler – ./scheduler -test -f0 rr – killall -q -KILL scheduler; true pretty: indent *.c *.h -kr

__MACOSX/assign3/assign3_part2/._Makefile

assign3/assign3_part2/scheduler.h

#ifndef __SCHEDULER_H_ #define __SCHEDULER_H_ #include <pthread.h> #include <semaphore.h> #include “list.h” #define QUANTUM 1 /* typedefs */ typedef struct thread_info { pthread_t thrid; int quanta; list_elem* le; /*added for evalution bookkeeping*/ struct timespec suspend_time; struct timespec resume_time; long wait_time; long run_time; } thread_info_t; /* functions */ void *start_worker(void *); long time_difference(const struct timespec*, const struct timespec*); int smp5_main(int argc, const char** argv); /* shared variables */ extern sem_t queue_sem; /* semaphore for scheduler queue */ extern thread_info_list sched_queue; /* list of current workers */ #endif /* __SCHEDULER_H_ */

__MACOSX/assign3/assign3_part2/._scheduler.h

assign3/assign3_part2/smp5_tests.c

/*************** YOU SHOULD NOT MODIFY ANYTHING IN THIS FILE ***************/ #define _GNU_SOURCE #include <stdio.h> #undef _GNU_SOURCE #include <stdlib.h> #include <string.h> #include <unistd.h> #include <signal.h> #include <sys/types.h> #include <sys/wait.h> #include “testrunner.h” #include “list.h” #include “scheduler.h” #include “worker.h” //#define quit_if(cond) do {if (cond) exit(EXIT_FAILURE);} while(0) #define quit_if(cond) do {if (cond) {printf(“Line %d.”,__LINE__);exit(EXIT_FAILURE);}} while(0) void args_to_nums(int argc, const char **argv, int *num_workers, int *queue_size, int **quanta) { int i; quit_if(argc < 4); *num_workers = atoi(argv[1]); *queue_size = atoi(argv[2]); *quanta = malloc(*num_workers * sizeof(int)); quit_if(*quanta == NULL); for(i=3;i<argc;i++) quanta[0][i-3] = atoi(argv[i]); } void nums_to_args(int num_workers, int queue_size, int *quanta, int *argc, char ***argv) { int i; *argc = num_workers+3; *argv = malloc(*argc*sizeof(char *)); quit_if(*argv==NULL); argv[0][0] = “scheduler”; argv[0][1] = malloc(3*sizeof(char)); quit_if(argv[0][1]==NULL); sprintf(argv[0][1],”%d”,num_workers); argv[0][2] = malloc(3*sizeof(char)); quit_if(argv[0][2]==NULL); sprintf(argv[0][2],”%d”,queue_size); for(i=0;i<num_workers;i++) { argv[0][i+3] = malloc(3*sizeof(char)); quit_if(argv[0][i+3]==NULL); sprintf(argv[0][i+3],”%d”,quanta[i]); } argv[0][i+3]=NULL; } /* Prepare input, reroute file descriptors, and run the program. */ void run_test(int argc, const char **argv) { //int fork_pid = fork(); //if (fork_pid == 0) { /* Reroute standard file descriptors */ freopen(“smp5.out”, “w”, stdout); /* Run the program */ quit_if(smp5_main(argc, argv) != EXIT_SUCCESS); fclose(stdout); //} else if (fork_pid > 0) { //waitpid(fork_pid, 0, 0); //} else { //fprintf(stderr, “run_test: fork() error\n”); //} } int test_output(FILE *stream, int nw, int qs, int *q) { int queue_size, queue_index; int num_workers, worker_index; int rv, in_queue, term, susp; unsigned long *queue, *workers, tid, prev, newwork, dummyl; int *remaining, *quanta; char dummyc; float tot_wait, tot_run, ave_wait, ave_run; int my_run, my_wait; rv = fscanf(stream,”Main: running %d workers with queue size %d for quanta:\n”,&num_workers, &queue_size); quit_if(rv != 2 || num_workers != nw || queue_size != qs); queue = malloc(queue_size*sizeof(long)); workers = malloc(num_workers*sizeof(long)); quanta = malloc(num_workers*sizeof(int)); remaining = malloc(queue_size*sizeof(int)); for(worker_index=0;worker_index<num_workers;worker_index++) { quit_if(fscanf(stream, ” %d”, quanta+worker_index) != 1); quit_if(quanta[worker_index]!=q[worker_index]); } fscanf(stream,”\n”); for(worker_index=0;worker_index<num_workers;worker_index++) { quit_if(fscanf(stream, “Main: detaching worker thread %lu.\n”,workers+worker_index) != 1); } quit_if(fscanf(stream, “Main: waiting for scheduler %lu.\n”,&dummyl) != 1); for(;queue_index<queue_size;queue[queue_index++]=0); worker_index = queue_index=0; in_queue = 0; quit_if(fscanf(stream, “Scheduler: waiting for workers.%c”,&dummyc)!=1 || dummyc != ‘\n’); for(queue_index = 0;queue_index < queue_size && queue_index < num_workers;queue_index++) { quit_if(fscanf(stream, “Thread %lu: in scheduler queue.\n”,&tid)!= 1 || tid != workers[worker_index]); quit_if(fscanf(stream, “Thread %lu: suspending.\n”,&tid)!= 1 || tid != workers[worker_index]); queue[queue_index]=tid; remaining[queue_index] = quanta[worker_index]; worker_index++; in_queue++; } my_run=0; my_wait = num_workers; queue_index = 0; term = susp = 0; while(worker_index < num_workers || in_queue > 0) { while(!queue[queue_index]) queue_index= (queue_index+1)%queue_size; quit_if(fscanf(stream, “Scheduler: scheduling.%c”,&dummyc)!=1 || dummyc != ‘\n’); quit_if(fscanf(stream, “Scheduler: resuming %lu.\n”,&tid) != 1); quit_if( tid != queue[queue_index]); if (prev == tid) { if(term) { quit_if(fscanf(stream, “Thread %lu: terminating.\n”,&tid) != 1 || tid != prev); } else if (susp){ quit_if(fscanf(stream, “Thread %lu: suspending.\n”,&tid) != 1); quit_if( tid != prev); } quit_if(fscanf(stream, “Thread %lu: resuming.\n”,&tid) != 1); quit_if(tid != queue[queue_index]); } else { quit_if(fscanf(stream, “Thread %lu: resuming.\n”,&tid) != 1 || tid != queue[queue_index]); if(term) { if(queue_size == 1) quit_if(fscanf(stream, “Scheduler: waiting for workers.%c”,&dummyc)!=1 || dummyc!=’\n’); quit_if(fscanf(stream, “Thread %lu: terminating.\n”,&tid) != 1 || tid != prev); if (in_queue == queue_size) { quit_if(fscanf(stream, “Thread %lu: in scheduler queue.\n”,&tid)!=1||tid != newwork); quit_if(fscanf(stream, “Thread %lu: suspending.\n”,&tid)!=1 || tid!=newwork); } } else if (susp && in_queue>1){ quit_if(fscanf(stream, “Thread %lu: suspending.\n”,&tid) != 1); quit_if( tid != prev); prev = tid; } } quit_if(fscanf(stream, “Scheduler: suspending %lu.\n”,&tid) != 1); quit_if(tid != queue[queue_index]); if(!–remaining[queue_index]) { quit_if(fscanf(stream, “Thread %lu: leaving scheduler queue.\n”,&tid)!=1 || tid != queue[queue_index]); term = 1; if(worker_index < num_workers) { queue[queue_index] = workers[worker_index]; remaining[queue_index] = quanta[worker_index]; newwork = workers[worker_index]; worker_index++; if(queue_size == 1) { prev = tid; quit_if(fscanf(stream, “Scheduler: waiting for workers.%c”,&dummyc)!=1 || dummyc!=’\n’); quit_if(fscanf(stream, “Thread %lu: terminating.\n”,&tid) != 1 || tid != prev); quit_if(fscanf(stream, “Thread %lu: in scheduler queue.\n”,&tid)!= 1 || tid != newwork); quit_if(fscanf(stream, “Thread %lu: suspending.\n”,&tid)!= 1 || tid != newwork); term = 0; susp = 0; my_wait++; } } else { queue[queue_index] = 0; in_queue–; } } else { term = 0; susp = 1; } prev = tid; my_run++; my_wait += in_queue+(num_workers-worker_index)-1+term; queue_index= (queue_index+1)%queue_size; } quit_if(fscanf(stream, “Th%c”,&dummyc) != 1); if (dummyc==’r’) { quit_if(fscanf(stream, “ead %lu: terminating.\nThe”,&tid)!=1 || tid != prev); } quit_if(fscanf(stream, ” total wait time is %f seconds.\n”,&tot_wait) != 1); quit_if(fscanf(stream, “The total run time is %f seconds.\n”,&tot_run) != 1); quit_if(fscanf(stream, “The average wait time is %f seconds.\n”,&ave_wait) != 1); quit_if(fscanf(stream, “The average run time is %f seconds.\n”,&ave_run) != 1); if (dummyc==’e’) quit_if(fscanf(stream, “Thread %lu: terminating.\nThe”,&tid) != 1|| tid != prev); quit_if(abs(tot_wait-my_wait)>1); quit_if(abs(tot_run-my_run)>1); quit_if(abs(tot_wait/num_workers-ave_wait)>.5); quit_if(abs(tot_run/num_workers-ave_run)>.5); return 0; } int general_test(int argc, const char **argv) { FILE *f; int nw, qs, *q; run_test(argc,argv); f = fopen(“smp5.out”,”r”); args_to_nums(argc,argv,&nw,&qs,&q); test_output(f,nw,qs,q); return EXIT_SUCCESS; } int specific_test(int nw, int qs, int *q) { FILE *f; int argc; char **argv; nums_to_args(nw,qs,q,&argc,&argv); run_test(argc,(const char **)argv); f = fopen(“smp5.out”,”r”); test_output(f,nw,qs,q); return EXIT_SUCCESS; } int test_3_1_2_2_2() { int q[3] = {2,2,2}; return specific_test(3,1,q); } int test_2_2_2_2() { int q[2]={2,2}; return specific_test(2,2,q); } int test_5_7_1_2_1_2_1() { int q[5] = {1,2,1,2,1}; return specific_test(5,7,q); } int test_4_1_1_2_3_4() { int q[4] = {1,2,3,4}; return specific_test(4,1,q); } int test_3_3_4_3_2() { int q[3] = {4,3,2}; return specific_test(3,3,q); } /* * Main entry point for SMP% test harness */ int run_smp5_tests(int argc, const char **argv) { /* Tests can be invoked by matching their name or their suite name * or ‘all’ */ testentry_t tests[] = { {“test_3_1_2_2_2”, “rr”, test_3_1_2_2_2}, {“test_2_2_2_2”, “rr”, test_2_2_2_2}, {“test_5_7_1_2_1_2_1”, “rr”, test_5_7_1_2_1_2_1}, {“test_4_1_1_2_3_4”, “rr”, test_4_1_1_2_3_4}, {“test_3_3_4_3_2”, “rr”, test_3_3_4_3_2}, {“general”, “gen”, general_test} }; int result = run_testrunner(argc, argv, tests, sizeof(tests) / sizeof(testentry_t)); unlink(“smp5.out”); return result; } /* The real main function. */ int main(int argc, const char **argv) { if (argc > 1 && !strcmp(argv[1], “-test”)) { return run_smp5_tests(argc – 1, argv + 1); } else { return smp5_main(argc, argv); } }

__MACOSX/assign3/assign3_part2/._smp5_tests.c

assign3/assign3_part2/testrunner.h

/*************** YOU SHOULD NOT MODIFY ANYTHING IN THIS FILE ***************/ typedef int (*test_fp) (int, const char **); typedef struct { const char *name; const char *suite; test_fp test_function; } testentry_t; int run_testrunner(int argc, const char **argv, testentry_t * entries, int entry_count); void set_testrunner_default_timeout(int s); void set_testrunner_timeout(int s);

__MACOSX/assign3/assign3_part2/._testrunner.h

assign3/assign3_part2/worker.h

#ifndef __WORKER_H_ #define __WORKER_H_ void cancel_thread(); void suspend_thread(); void leave_scheduler_queue(thread_info_t*); #endif

__MACOSX/assign3/assign3_part2/._worker.h

assign3/assign3_part2/list.h

#ifndef __LIST_H_ #define __LIST_H_ #include <pthread.h> typedef struct list_elem { struct list_elem *prev; struct list_elem *next; void *info; } list_elem; typedef struct thread_info_list { list_elem *head; list_elem *tail; pthread_mutex_t lock; } thread_info_list; int list_size(thread_info_list *list); int list_insert_head(thread_info_list *list, list_elem *new); int list_insert_tail(thread_info_list *list, list_elem *new); int list_remove(thread_info_list *list, list_elem *new); void print_list(thread_info_list *list); #endif /* __LIST_H_ */

__MACOSX/assign3/assign3_part2/._list.h

assign3/assign3_part2/README.txt

SMP5: Scheduler with Signals ============================ This MP is a variation of SMP4. In the last MP, we built a simulated OS process scheduler. The scheduler can hold only a certain number of processes (workers) at one time. Once the process has been accepted into the scheduler, the scheduler decides in what order the processes execute. We implemented two scheduling algorithms: FIFO and Round Robin. In this MP, we are to simulate a time-sharing system by using signals and timers. We will only implement the Round Robin algorithm. Instead of using iterations to model the concept of “time slices” (as in the last MP), we use interval timers. The scheduler is installed with an interval timer. The timer starts ticking when the scheduler picks a thread to use the CPU which in turn signals the thread when its time slice is finished thus allowing the scheduler to pick another thread and so on. When a thread has completely finished its work it leaves the scheduler to allow a waiting thread to enter. Please note that in this MP, only the timer and scheduler send signals. The threads passively handle the signals without signaling back to the scheduler. The program takes a number of arguments. Arg1 determines the number of jobs (threads in our implementation) created; arg2 specifies the queue size of the scheduler. Arg3 through argN gives the duration (the required time slices to complete a job) of each job. Hence if we create 2 jobs, we should supply arg3 and arg4 for the required duration. You can assume that the autograder will always supply the correct number of arguments and hence you do not have to detect invalid input. Here is an example of program output, once the program is complete: % scheduler 3 2 3 2 3 Main: running 3 workers with queue size 2 for quanta: 3 2 3 Main: detaching worker thread 3075926960. Main: detaching worker thread 3065437104. Main: detaching worker thread 3054947248. Main: waiting for scheduler 3086416816. Scheduler: waiting for workers. Thread 3075926960: in scheduler queue. Thread 3075926960: suspending. Thread 3065437104: in scheduler queue. Thread 3065437104: suspending. Scheduler: scheduling. Scheduler: resuming 3075926960. Thread 3075926960: resuming. Scheduler: suspending 3075926960. Scheduler: scheduling. Scheduler: resuming 3065437104. Thread 3065437104: resuming. Thread 3075926960: suspending. Scheduler: suspending 3065437104. Scheduler: scheduling. Scheduler: resuming 3075926960. Thread 3075926960: resuming. Thread 3065437104: suspending. Scheduler: suspending 3075926960. Scheduler: scheduling. Scheduler: resuming 3065437104. Thread 3065437104: resuming. Thread 3075926960: suspending. Scheduler: suspending 3065437104. Thread 3065437104: leaving scheduler queue. Scheduler: scheduling. Scheduler: resuming 3075926960. Thread 3075926960: resuming. Thread 3065437104: terminating. Thread 3054947248: in scheduler queue. Thread 3054947248: suspending. Scheduler: suspending 3075926960. Thread 3075926960: leaving scheduler queue. Scheduler: scheduling. Scheduler: resuming 3054947248. Thread 3054947248: resuming. Thread 3075926960: terminating. Scheduler: suspending 3054947248. Scheduler: scheduling. Scheduler: resuming 3054947248. Thread 3054947248: suspending. Thread 3054947248: resuming. Scheduler: suspending 3054947248. Scheduler: scheduling. Scheduler: resuming 3054947248. Thread 3054947248: suspending. Thread 3054947248: resuming. Scheduler: suspending 3054947248. Thread 3054947248: leaving scheduler queue. Thread 3054947248: terminating. The total wait time is 12.062254 seconds. The total run time is 7.958618 seconds. The average wait time is 4.020751 seconds. The average run time is 2.652873 seconds. The goal of this MP is to help you understand (1) how signals and timers work, and (2) how to evaluate the performance of your program. You will first implement the time-sharing system using timers and signals. Then, you will evaluate the overall performance of your program by keeping track of how long each thread is idle, running, etc. The program will use these four signals: SIGALRM: sent by the timer to the scheduler, to indicate another time quantum has passed. SIGUSR1: sent by the scheduler to a worker, to tell it to suspend. SIGUSR2: sent by the scheduler to a suspended worker, to tell it to resume. SIGTERM: sent by the scheduler to a worker, to tell it to cancel. You will need to set up the appropriate handlers and masks for these signals. You will use these functions: clock_gettime pthread_sigmask pthread_kill sigaction sigaddset sigemptyset sigwait timer_settime timer_create Also, make sure you understand how the POSIX:TMR interval timer works. There are two ways you can test your code. You can run the built-in grading tests by running “scheduler -test -f0 rr”. This runs 5 tests, each of which can be run individually. You can also test you program with specific parameters by running “scheduler -test gen …” where the ellipsis contains the parameters you would pass to scheduler. Programming =========== Part I: Modify the scheduler code (scheduler.c) ———————————————– We use the scheduler thread to setup the timer and handle the scheduling for the system. The scheduler handles the SIGALRM events that come from the timer, and sends out signals to the worker threads. Step 1. Modify the code in init_sched_queue() function in scheduler.c to initialize the scheduler with a POSIX:TMR interval timer. Use CLOCK_REALTIME in timer_create(). The timer will be stored in the global variable “timer”, which will be started in scheduler_run() (see Step 4 below). Step 2. Implement setup_sig_handlers(). Use sigaction() to install signal handlers for SIGALRM, SIGUSR1, and SIGTERM. SIGALRM should trigger timer_handler(), SIGUSR1 should trigger suspend_thread(), and SIGTERM should trigger cancel_thread(). Notice no handler is installed for SIGUSR2; this signal will be handled differently, in step 8. Step 3. In the scheduler_run() function, start the timer. Use timer_settime(). The time quantum (1 second) is given in scheduler.h. The timer should go off repeatedly at regular intervals defined by the timer quantum. In Round-Robin, whenever the timer goes off, the scheduler suspends the currently running thread, and tells the next thread to resume its operations using signals. These steps are listed in timer_handler(), which is called every time the timer goes off. In this implementation, the timer handler makes use of suspend_worker() and resume_worker() to accomplush these steps. Step 4. Complete the suspend_worker() function. First, update the info->quanta value. This is the number of quanta that remain for this thread to execute. It is initialized to the value passed on the command line, and decreases as the thread executes. If there is any more work for this worker to do, send it a signal to suspend, and update the scheduler queue. Otherwise, cancel the thread. Step 5. Complete the cancel_worker() function by sending the appropriate signal to the thread, telling it to kill itself. Step 6. Complete the resume_worker() function by sending the appropriate signal to the thread, telling it to resume execution. Part II: Modify the worker code (worker.c) —————————————— In this section, you will modify the worker code to correctly handle the signals from the scheduler that you implemented in the previous section. You need to modify the thread functions so that it immediately suspends the thread, waiting for a resume signal from the scheduler. You will need to use sigwait() to force the thread to suspend itself and wait for a resume signal. You need also to implement a signal handler in worker.c to catch and handle the suspend signals. Step 7. Modify start_worker() to (1) block SIGUSR2 and SIGALRM, and (2) unblock SIGUSR1 and SIGTERM. Step 8. Implement suspend_thread(), the handler for the SIGUSR1 signal. The thread should block until it receives a resume (SIGUSR2) signal. Part III: Modify the evaluation code (scheduler.c) ————————————————– This program keeps track of run time, and wait time. Each thread saves these two values regarding its own execution in its thread_info_t. Tracking these values requires also knowing the last time the thread suspended or resumed. Therefore, these two values are also kept in thread_info_t. See scheduler.h. In this section, you will implement the functions that calculate run time and wait time. All code that does this will be in scheduler.c. When the program is done, it will collect all these values, and print out the total and average wait time and run time. For your convenience, you are given a function time_difference() to compute the difference between two times in microseconds. Step 9. Modify create_workers() to initialize the various time variables. Step 10. Implement update_run_time(). This is called by suspend_worker(). Step 11. Implement update_wait_time(). This is called by resume_worker(). Questions ========== Question 1. Why do we block SIGUSR2 and SIGALRM in worker.c? Why do we unblock SIGUSR1 and SIGTERM in worker.c? Question 2. We use sigwait() and sigaction() in our code. Explain the difference between the two. (Please explain from the aspect of thread behavior rather than syntax). Question 3. When we use POSIX:TMR interval timer, we are using relative time. What is the alternative? Explain the difference between the two. Question 4. Look at start_worker() in worker.c, a worker thread is executing within an infinite loop at the end. When does a worker thread terminate? Question 5. When does the scheduler finish? Why does it not exit when the scheduler queue is empty? Question 6. After a thread is scheduled to run, is it still in the sched_queue? When is it removed from the head of the queue? When is it removed from the queue completely? Question 7. We’ve removed all other condition variables in SMP4, and replaced them with a timer and signals. Why do we still use the semaphore queue_sem? Question 8. What’s the purpose of the global variable “completed” in scheduler.c? Why do we compare “completed” with thread_count before we wait_for_queue() in next_worker()? Question 9. We only implemented Round Robin in this SMP. If we want to implement a FIFO scheduling algorithm and keep the modification as minimum, which function in scheduler.c is the one that you should modify? Briefly describe how you would modify this function. Question 10. In this implementation, the scheduler only changes threads when the time quantum expires. Briefly explain how you would use an additional signal to allow the scheduler to change threads in the middle of a time quantum. In what situations would this be useful?

__MACOSX/assign3/assign3_part2/._README.txt

assign3/assign3_part2/scheduler.c

#include <stdio.h> #include <stdlib.h> #include <string.h> #include <unistd.h> #include <errno.h> #include <time.h> #include <signal.h> #include “scheduler.h” #include “worker.h” /* * define the extern global variables here. */ sem_t queue_sem; /* semaphore for scheduler queue */ thread_info_list sched_queue; /* list of current workers */ static int quit = 0; static timer_t timer; static thread_info_t *currentThread= 0; static long wait_times; static long run_times; static int completed = 0; static int thread_count = 0; static void exit_error(int); /* helper function. */ static void wait_for_queue(); /******************************************************************************* * * Implement these functions. * ******************************************************************************/ /* * This function intializes the queue semaphore and the queue itself. */ /* * Update the worker’s current running time. * This function is called every time the thread is suspended. */ void update_run_time(thread_info_t *info) { /* TODO: implement this function */ } /* * Update the worker’s current waiting time. * This function is called every time the thread resumes. */ void update_wait_time(thread_info_t *info) { /* TODO: implement this function */ } static void init_sched_queue(int queue_size) { /* set up a semaphore to restrict access to the queue */ sem_init(&queue_sem, 0, queue_size); /* initialize the scheduler queue */ sched_queue.head = sched_queue.tail = 0; pthread_mutex_init(&sched_queue.lock, NULL); /* TODO: initialize the timer */ } /* * signal a worker thread that it can resume. */ static void resume_worker(thread_info_t *info) { printf(“Scheduler: resuming %lu.\n”, info->thrid); /* * TODO: signal the worker thread that it can resume */ /* update the wait time for the thread */ update_wait_time(info); } /*send a signal to the thread, telling it to kill itself*/ void cancel_worker(thread_info_t *info) { /* TODO: send a signal to the thread, telling it to kill itself*/ /* Update global wait and run time info */ wait_times += info->wait_time; run_times += info->run_time; completed++; /* Update schedule queue */ leave_scheduler_queue(info); if (completed >= thread_count) { sched_yield(); /* Let other threads terminate. */ printf(“The total wait time is %f seconds.\n”, (float)wait_times / 1000000); printf(“The total run time is %f seconds.\n”, (float)run_times / 1000000); printf(“The average wait time is %f seconds.\n”, (float)wait_times / 1000000 / thread_count); printf(“The average run time is %f seconds.\n”, (float)run_times / 1000000 / thread_count); } } /* * signals a worker thread that it should suspend. */ static void suspend_worker(thread_info_t *info) { int whatgoeshere = 0; printf(“Scheduler: suspending %lu.\n”, info->thrid); /*update the run time for the thread*/ update_run_time(info); /* TODO: Update quanta remaining. */ /* TODO: decide whether to cancel or suspend thread */ if(whatgoeshere) { /* * Thread still running: suspend. * TODO: Signal the worker thread that it should suspend. */ /* Update Schedule queue */ list_remove(&sched_queue,info->le); list_insert_tail(&sched_queue,info->le); } else { /* Thread done: cancel */ cancel_worker(info); } } /* * this is the scheduling algorithm * pick the next worker thread from the available list * you may need to add new information to the thread_info struct */ static thread_info_t *next_worker() { if (completed >= thread_count) return 0; wait_for_queue(); printf(“Scheduler: scheduling.\n”); /* return the thread_info_t for the next thread to run */ return sched_queue.head->info; } void timer_handler() { thread_info_t *info = 0; /* once the last worker has been removed, we’re done. */ if (list_size(&sched_queue) == 0) { quit = 1; return; } /*suspend the current worker*/ if (currentThread) suspend_worker(currentThread); //resume the next worker info = next_worker(); /* Update currentThread */ currentThread = info; if (info) resume_worker(info); else quit = 1; } /* * Set up the signal handlers for SIGALRM, SIGUSR1, and SIGTERM. * TODO: Implement this function. */ void setup_sig_handlers() { /* Setup timer handler for SIGALRM signal in scheduler */ /* Setup cancel handler for SIGTERM signal in workers */ /* Setup suspend handler for SIGUSR1 signal in workers */ } /******************************************************************************* * * * ******************************************************************************/ /* * waits until there are workers in the scheduling queue. */ static void wait_for_queue() { while(!list_size(&sched_queue)) { printf(“Scheduler: waiting for workers.\n”); sched_yield(); } } /* * runs at the end of the program just before exit. */ static void clean_up() { /* * destroy any mutexes/condition variables/semaphores that were created. * free any malloc’d memory not already free’d */ sem_destroy(&queue_sem); pthread_mutex_destroy(&sched_queue.lock); } /* * prints the program help message. */ static void print_help(const char *progname) { printf(“usage: %s <num_threads> <queue_size> <i_1, i_2 … i_numofthreads>\n”, progname); printf(“\tnum_threads: the number of worker threads to run\n”); printf(“\tqueue_size: the number of threads that can be in the scheduler at one time\n”); printf(“\ti_1, i_2 …i_numofthreads: the number of quanta each worker thread runs\n”); } /* * prints an error summary and exits. */ static void exit_error(int err_num) { fprintf(stderr, “failure: %s\n”, strerror(err_num)); exit(1); } /* * creates the worker threads. */ static void create_workers(int thread_count, int *quanta) { int i = 0; int err = 0; for (i = 0; i < thread_count; i++) { thread_info_t *info = (thread_info_t *) malloc(sizeof(thread_info_t)); info->quanta = quanta[i]; if ((err = pthread_create(&info->thrid, NULL, start_worker, (void *)info)) != 0) { exit_error(err); } printf(“Main: detaching worker thread %lu.\n”, info->thrid); pthread_detach(info->thrid); /* TODO: initialize the time variables for each thread for performance evalution*/ } } /* * runs the scheduler. */ static void *scheduler_run(void *unused) { wait_for_queue(); /* TODO: start the timer */ /*keep the scheduler thread alive*/ while( !quit ) sched_yield(); return NULL; } /* * starts the scheduler. * returns 0 on success or exits program on failure. */ static int start_scheduler(pthread_t *thrid) { int err = 0; if ((err = pthread_create(thrid, NULL, scheduler_run, 0)) != 0) { exit_error(err); } return err; } /* * reads the command line arguments and starts the scheduler & worker threads. */ int smp5_main(int argc, const char** argv) { int queue_size = 0; int ret_val = 0; int *quanta,i; pthread_t sched_thread; /* check the arguments. */ if (argc < 3) { print_help(argv[0]); exit(0); } thread_count = atoi(argv[1]); queue_size = atoi(argv[2]); quanta = (int*)malloc(sizeof(int)*thread_count); if (argc != 3 + thread_count) { print_help(argv[0]); exit(0); } for ( i = 0; i < thread_count; i++) quanta[i] = atoi(argv[i+3]); printf(“Main: running %d workers with queue size %d for quanta:\n”, thread_count, queue_size); for ( i = 0; i < thread_count; i++) printf(” %d”, quanta[i]); printf(“\n”); /*setup the sig handlers for scheduler and workers*/ setup_sig_handlers(); /* initialize anything that needs to be done for the scheduler queue. */ init_sched_queue(queue_size); /* creates a thread for the scheduler. */ start_scheduler(&sched_thread); /* creates the worker threads and returns. */ create_workers(thread_count, quanta); /* wait for scheduler to finish */ printf(“Main: waiting for scheduler %lu.\n”, sched_thread); pthread_join(sched_thread, (void **) &ret_val); /* clean up our resources */ clean_up(); /* this will wait for all other threads */ pthread_exit(0); } long time_difference(const struct timespec *time1, const struct timespec *time2) { return (time1->tv_sec – time2->tv_sec) * 1000000 + (time1->tv_nsec – time2->tv_nsec) / 1000; }

__MACOSX/assign3/assign3_part2/._scheduler.c

assign3/assign3_part2/testrunner.c

/*************** YOU SHOULD NOT MODIFY ANYTHING IN THIS FILE ***************/ /* A simple testrunner framework Original Author: L. Angrave */ #include <sys/types.h> #include <sys/wait.h> #include <errno.h> #include <stdio.h> #include <signal.h> #include <stdlib.h> #include <string.h> #include <assert.h> #include <unistd.h> #include “testrunner.h” /* Constants */ #define false (0) #define true (1) #define test_killed (2) /* defaults */ static int default_timeout_seconds = 15; static int timeout_seconds; void set_testrunner_default_timeout(int s) { assert(s > 0); default_timeout_seconds = s; } void set_testrunner_timeout(int s) { assert(s > 0); timeout_seconds = s; } /* — Helper macros and functions — */ #define DIE(mesg) {fprintf(stderr,”\n%s(%d):%s\n”,__fname__,__LINE__,mesg); exit(1);} static int eql(const char *s1, const char *s2) { return s1 && s2 && !strcmp(s1, s2); } /* Callback function for qsort on strings */ static int mystrcmp(const void *p1, const void *p2) { return eql((const char *) p1, (const char *) p2); } /* Stats of all tests run so far */ typedef struct { int ran, passed, failed; } stats_t; /* — Signal handlers — */ static pid_t child_pid; static int sent_child_timeout_kill_signal; static void kill_child_signal_handler(intsigno) { if (!child_pid) return; char m[] = “-Timeout(Killing test process)-“; write(0, m, sizeof(m) – 1); kill(child_pid, SIGKILL); sent_child_timeout_kill_signal = 1; } /* Internal function to run a test as a forked child. The child process is terminated if it runs for more than a few seconds */ static int invoke_test_with_timelimit(testentry_t * test, int redirect_stdouterr, int argc, const char **argv) { char fname[255]; int wait_status; pid_t wait_val; struct sigaction action; assert(!child_pid); assert(test && test->test_function && test->name); set_testrunner_timeout(default_timeout_seconds); errno = 0; child_pid = fork(); if (child_pid == -1) { fprintf(stderr, “-fork failed so running test inline-“); return test->test_function(argc, argv); } if (child_pid == 0) { if (redirect_stdouterr) { snprintf(fname, (int) sizeof(fname), “stdout-%s.txt”, test->name); fname[sizeof(fname) – 1] = 0; freopen(fname, “w”, stdout); memcpy(fname + 3, “err”, 3); freopen(fname, “w”, stderr); } exit(test->test_function(argc, argv)); } else { wait_status = -1; sigemptyset(&action.sa_mask); action.sa_handler = kill_child_signal_handler; sigaction(SIGALRM, &action, NULL); sent_child_timeout_kill_signal = 0; alarm(timeout_seconds); wait_val = waitpid(child_pid, &wait_status, 0); int child_exited_normally = WIFEXITED(wait_status); int child_exit_value = WEXITSTATUS(wait_status); int child_term_by_signal = WIFSIGNALED(wait_status); int child_term_signal = WTERMSIG(wait_status); if (child_term_by_signal) { fprintf(stderr, “testrunner:Test terminated by signal %d\n”, child_term_signal); fprintf(stderr, “testrunner:waitpid returned %d (child_pid=%d,wait_status=%d)”, wait_val, child_pid, wait_status); } if (child_pid != wait_val) fprintf(stderr, “testrunner: strange… wait_val != child_pid\n”); int passed = (child_pid == wait_val) && (child_exit_value == 0) && (child_exited_normally != 0); alarm(0); kill(child_pid, SIGKILL); child_pid = 0; return sent_child_timeout_kill_signal ? test_killed : passed ? 0 : 1; } } /* * run a test and update the stats. The main guts of this functionality is provided by invoke_test_with_timelimit * This outer wrapper updates thes output and statistics before and after running the test. */ static int run_one_test(stats_t * stats, testentry_t * test, int redirect_stdouterr, int argc, const char **argv) { int test_result; assert(stats && test->name && argc > 0 && argv && *argv); stats->ran++; stats->failed++; printf(“%2d.%-20s:”, stats->ran, test->name); fflush(stdout); test_result = invoke_test_with_timelimit(test, redirect_stdouterr, argc, argv); if (test_result == 0) { stats->failed–; stats->passed++; } printf(“:%s\n”, (test_result == 0 ? “pass” : test_result == 2 ? “TIMEOUT * ” : “FAIL *”)); return test_result != 0; } /* Help functionality to print out sorted list of test names and suite names */ static void print_targets(testentry_t tests[], int count) { const char **array; const char *previous; int i; array = (const char **) calloc(sizeof(const char *), count); /* Sort the test names and print unique entries */ for (i = 0; i < count; i++) array[i] = tests[i].name; qsort(array, count, sizeof(array[0]), mystrcmp); printf(“\nValid tests : all”); for (i = 0, previous = “”; i < count; i++) if (!eql(previous, array[i])) printf(” %s”, (previous = array[i])); /* Sort the suite names and print unique entries */ for (i = 0; i < count; i++) array[i] = tests[i].suite; qsort(array, count, sizeof(array[0]), mystrcmp); printf(“\nValid suites:”); for (i = 0, previous = “”; i < count; i++) if (!eql(previous, array[i])) printf(” %s”, (previous = array[i])); printf(“\n”); } /* * Main entry point for test harness */ int run_testrunner(int argc, const char **argv, testentry_t tests[], int test_count) { const char *test_name, *target; int i; stats_t stats; int target_matched, max_errors_before_quit, redirect_stdouterr; memset(&stats, 0, sizeof(stats)); max_errors_before_quit = 1; redirect_stdouterr = 0; assert(tests != NULL); assert(test_count > 0); assert(argc > 0 && argv && *argv); while (true) { target = argc > 1 ? argv[1] : “”; assert(target); if (*target != ‘-‘) break; argc–; argv++; if (target[1] == ‘f’ && target[2]) max_errors_before_quit = atoi(target + 1); else if (target[1] == ‘r’) redirect_stdouterr = 1; } target_matched = false; for (i = 0; i < test_count && (max_errors_before_quit < 1 || stats.failed != max_errors_before_quit); i++) { test_name = tests[i].name; assert(test_name); assert(tests[i].suite); assert(tests[i].test_function); if (eql(target, test_name) || eql(target, “all”) || eql(target, tests[i].suite)) { if (!target_matched) printf(“Running tests…\n”); target_matched = true; run_one_test(&stats, &tests[i], redirect_stdouterr, argc – 1, argv + 1); } } if (!target_matched) { fprintf(stderr, “Test ‘%s’ not found”, (strlen(target) > 0 ? target : “(empty)”)); print_targets(tests, test_count); } else { printf(“\nTest Results:%d tests,%d passed,%d failed.\n”, stats.ran, stats.passed, stats.failed); } return stats.passed == stats.ran && target_matched ? 0 : 1; }

__MACOSX/assign3/assign3_part2/._testrunner.c

 

From Case Project 8-6: Lake Point Security Consulting:

/in /by

From Case Project 8-6: Lake Point Security Consulting:

“Lake Point Consulting Services (LPCS) provides security consulting and assurance services to over 500 clients across a wide range of enterprises in more than 20 states. A new initiative at LPCS is for each of its seven regional offices to provide internships to students who are in
their final year of the security degree program at the local college.

Pomodoro Fresco is a regional Italian pizza chain that provides free open wireless access to its customers and secure wireless access for its staff. However, Pomodoro Fresco is concerned about the security of the WLAN. They have asked LPCS to make a presentation about wireless attacks and their options for security. LPCS has asked you to help them in the presentation.

You will create a PowerPoint presentation for a fictitious company regarding wireless security. Carefully read the case project statement and step number 1 to ensure you cover all of the requested topics. Refer to Tech Republic Article about Powerpoint (Links to an external site.) for proper use of developing presentations in PowerPoint.  I expect to see:

  • a few bulleted items on at least one slide
  • at least one applicable graphics (charts, graphs, clipart) to make the presentation interesting
  • you should have an introduction slide
  • presentation about wireless attacks and their options for security
  • a conclusion slide
  • a slide for the list of your sources
  • total of 10 to 20 slides (includes Introduction slide, Conclusion slide and Sources slide)

 

Homework for modifying the syntactic analyzer for the attached compiler by adding to the existing grammar. The full grammar of the language is shown below.

/in /by

Homework for modifying the syntactic analyzer for the attached compiler by adding to the existing grammar. The full grammar of the language is shown below. The highlighted portions of the grammar show what you must either modify or add to the existing grammar.

function:

function_header {variable} body

function_header:

FUNCTION IDENTIFIER [parameters] RETURNS type ;

variable:

IDENTIFIER : type IS statement

parameters:

parameter {, parameter}

parameter:

IDENTIFIER : type

type:

INTEGER | REAL | BOOLEAN

body:

BEGIN statement END ;

statement: expression ; |

REDUCE operator {statement} ENDREDUCE ; |

IF expression THEN statement ELSE statement ENDIF ; |

CASE expression IS {case} OTHERS ARROW statement ; ENDCASE ;

operator:

ADDOP | MULOP

case:

WHEN INT_LITERAL ARROW statement

expression:

( expression ) |

REAL_LITERAL

NOT expression

expression binary_operator expression |

|

INT_LITERAL | IDENTIFIER

| BOOL_LITERAL |

binary_operator: ADDOP | MULOP | REMOP | EXPOP | RELOP | ANDOP | OROP

In the above grammar, the red symbols are nonterminals, the blue symbols are terminals and the black punctuation are EBNF metasymbols. The braces denote repetition 0 or more times and the brackets denote optional.

You must rewrite the grammar to eliminate the EBNF brace and bracket metasymbols and to incorporate the significance of parentheses, operator precedence and associativity for all operators. Among arithmetic operators the exponentiation operator has highest precedence following by the multiplying operators and then the adding operators. All relational operators have the same precedence. Among the binary logical operators, and has higher precedence than or. Of the categories of operators, the unary logical operator has highest precedence, the arithmetic operators have next highest precedence, followed by the relational operators and finally the binary logical operators. All operators except the exponentiation operator are left associative. The directives to specify precedence and associativity, such as %prec and %left, may not be used

Your parser should be able to correctly parse any syntactically correct program without any problem.

You must modify the syntactic analyzer to detect and recover from additional syntax errors using the semicolon as the synchronization token. To accomplish detecting additional errors an error production must be added to the function header and another to the variable declaration.

Your bison input file should not produce any shift/reduce or reduce/reduce errors. Eliminating them can be difficult so the best strategy is not introduce any. That is best achieved by making small incremental additions to the grammar and ensuring that no addition introduces any such errors.

An example of compilation listing output containing syntax errors is shown below:

1 — Multiple errors 2

  1. function main a integer returns real; Syntax Error, Unexpected INTEGER, expecting ‘:’
  2. b: integer is * 2; Syntax Error, Unexpected MULOP
  3. c: real is 6.0;
  4. begin
  5. if a > c then 8      b   3.0;

Syntax Error, Unexpected REAL_LITERAL, expecting ‘;’

9      else

10          b = 4.;

11      endif;

12 ;

Syntax Error, Unexpected ‘;’, expecting END

Lexical Errors 0

Syntax Errors 4

Semantic Errors 0

————————————————————

listing.h

// This file contains the function prototypes for the functions that produce the // compilation listing

enum ErrorCategories {LEXICAL, SYNTAX, GENERAL_SEMANTIC, DUPLICATE_IDENTIFIER,
UNDECLARED};

void firstLine();
void nextLine();
int lastLine();
void appendError(ErrorCategories errorCategory, string message);

———————————————————————————-

makefile

compile: scanner.o parser.o listing.o
g++ -o compile scanner.o parser.o listing.o
scanner.o: scanner.c listing.h tokens.h
g++ -c scanner.c

scanner.c: scanner.l
flex scanner.l
mv lex.yy.c scanner.c

parser.o: parser.c listing.h
g++ -c parser.c

parser.c tokens.h: parser.y
bison -d -v parser.y
mv parser.tab.c parser.c
mv parser.tab.h tokens.h

listing.o: listing.cc listing.h
g++ -c listing.cc

———————————————————-

parser.y

%{

#include

using namespace std;

#include “listing.h”

int yylex();
void yyerror(const char* message);

%}

%error-verbose

%token IDENTIFIER
%token INT_LITERAL

%token ADDOP MULOP RELOP ANDOP

%token BEGIN_ BOOLEAN END ENDREDUCE FUNCTION INTEGER IS REDUCE RETURNS

%%

function:
function_header optional_variable body ;
function_header:
FUNCTION IDENTIFIER RETURNS type ‘;’ ;

optional_variable:
variable |
;

variable:
IDENTIFIER ‘:’ type IS statement_ ;

type:
INTEGER |
BOOLEAN ;

body:
BEGIN_ statement_ END ‘;’ ;
statement_:
statement ‘;’ |
error ‘;’ ;
statement:
expression |
REDUCE operator reductions ENDREDUCE ;

operator:
ADDOP |
MULOP ;

reductions:
reductions statement_ |
;
expression:
expression ANDOP relation |
relation ;

relation:
relation RELOP term |
term;

term:
term ADDOP factor |
factor ;
factor:
factor MULOP primary |
primary ;

primary:
‘(‘ expression ‘)’ |
INT_LITERAL |
IDENTIFIER ;
%%

void yyerror(const char* message)
{
appendError(SYNTAX, message);
}

int main(int argc, char *argv[])
{
firstLine();
yyparse();
lastLine();
return 0;
}
————————————————————————

scanner

/* Compiler Theory and Design
Dr. Duane J. Jarc */

/* This file contains flex input file */

%{
#include
#include

using namespace std;

#include “listing.h”
#include “tokens.h”

%}

%option noyywrap

ws       [ \t\r]+
comment       \-\-.*\n
line       [\n]
id       [A-Za-z][A-Za-z0-9]*
digit       [0-9]
int       {digit}+
punc       [\(\),:;]
%%

{ws}       { ECHO; }
{comment}   { ECHO; nextLine();}
{line}       { ECHO; nextLine();}
“<”       { ECHO; return(RELOP); }
“+”       { ECHO; return(ADDOP); }
“*”       { ECHO; return(MULOP); }
begin       { ECHO; return(BEGIN_); }
boolean       { ECHO; return(BOOLEAN); }
end       { ECHO; return(END); }
endreduce   { ECHO; return(ENDREDUCE); }
function   { ECHO; return(FUNCTION); }
integer       { ECHO; return(INTEGER); }
is       { ECHO; return(IS); }
reduce       { ECHO; return REDUCE; }
returns       { ECHO; return(RETURNS); }
and       { ECHO; return(ANDOP); }
{id}       { ECHO; return(IDENTIFIER);}
{int}       { ECHO; return(INT_LITERAL); }
{punc}       { ECHO; return(yytext[0]); }
.       { ECHO; appendError(LEXICAL, yytext); }

%%
—————————————————————-

listing.cc

// Compiler Theory and Design
// Dr. Duane J. Jarc

// This file contains the bodies of the functions that produces the compilation
// listing

#include
#include

using namespace std;

#include “listing.h”

static int lineNumber;
static string error = “”;
static int totalErrors = 0;

static void displayErrors();

void firstLine()
{
lineNumber = 1;
printf(“\n%4d “,lineNumber);
}

void nextLine()
{
displayErrors();
lineNumber++;
printf(“%4d “,lineNumber);
}

int lastLine()
{
printf(“\r”);
displayErrors();
printf(” \n”);
return totalErrors;
}
void appendError(ErrorCategories errorCategory, string message)
{
string messages[] = { “Lexical Error, Invalid Character “, “”,
“Semantic Error, “, “Semantic Error, Duplicate Identifier: “,
“Semantic Error, Undeclared ” };

error = messages[errorCategory] + message;
totalErrors++;
}

void displayErrors()
{
if (error != “”)
printf(“%s\n”, error.c_str());
error = “”;
}
———————————————————-

 

Cloud Computing: Concepts

/in /by

Topic:  Cloud Security (based on content from Chapter 6 in Cloud Computing: Concepts, Technology & Architecture)

Overview:  The diagram provided in the assignment rubric illustrates interaction between two cloud service consumers (A and B) and two virtual servers (A and B) hosted on a cloud.

Based on the limited information provided in the depicted scenario, describe three types of attacks that could potentially be carried out if any of the programs outside of the cloud were malicious.

Provide a brief explanation justifying the threat of each proposed attack. For each of the three types of attacks, please list and describe a potential cause.

Please ensure you refer to the attached document for details on the requirements for this assignment!

2 ) Discussion: 

 

In your initial post, discuss the differences between Virtualization and Cloud Computing.

Please find one organization that has recently adopted virtualization and summarize their reasons for taking this approach. What challenges did they face?

minimum of 500 words.

INFORMATION TECHNOLOGY DISASTER RECOVERY PLAN

/in /by

INFORMATION TECHNOLOGY DISASTER RECOVERY PLAN

 

Revision History

 

RevisionChangeDate
   
   
   
   
   
   
   

 

 

 

Official copies of the document are available at the following locations:

· Department of Information Technology Office

· Office and home of the Chief Information Officer

 

10

Contents

Revision History 1 Official copies of the document are available at the following locations: 1 Contents 2 Section 1: Introduction 3 Section 2: Scope 3 Section 3: Assumptions 3 Section 4: Definitions 3 Section 5: Teams 3 5.0.1 Incident Commander 3 5.0.2 Incident Command Team 3 5.1 Datacenter Recovery Team 3 5.2 Desktop, Lab, and Classroom Recovery Team 4 5.3 Enterprise Systems Recovery Team 4 5.4 Infrastructure and Web Recovery Team 4 5.5 Telecommunications, Network, and Internet Services Recovery Team 4 Section 6: Recovery Preparations 5 6.1 Data Recovery Information: 5 6.2 Central Datacenter and Server Recovery Information: 5 6.3 Network and Telecommunication Recovery Information: 5 6.4 Application Recovery Information: 5 6.5 Desktop Equipment Recovery Information: 5 Section 7: Disaster Recovery Processes and Procedures 5 7.1 Emergency Response: 5 7.2 Incident Command Team: 5 7.3 Disaster Recovery Teams: 5 7.4 General System/Application Recovery Procedures/Outline: 5 8.0 Network & Telecommunication Recovery Guidelines: 7 Appendix A. IT Contact List 7 Appendix B. Crisis Management Team Contact List 7 Appendix C: IT Recovery Priority List 7 C.1 IT Infrastructure Priorities: 7 C.2 IT System Priorities: 8 C.3 Consortium, Outsourced, and Cloud-based IT System Priorities: 8 C.4 IT Facility Priorities 9 Appendix D: Vendor Information 9 Appendix E: Disaster Recovery Signoff Sheet 10

 

Section 1: Introduction

Provide an introduction to the company/situation…

A copy of this plan is stored in the following areas:

 

· Department of Information Technology Office

· Office and home of the Chief Information Officer

 

Section 2: Scope

Determine/explain the scope of this plan.

 

 

Section 3: Assumptions

 

 

Section 4: Definitions

 

 

Section 5: Teams

5.0.1 Incident Commander

 

Chief Information Officer 
Home Phone: 
Cell Phone: 

 

5.0.2 Incident Command Team

 

Chief Information Officer 
Manager, User Support 
Manager, Infrastructure Services 
Manager, Information Systems 
Manager, Classroom and Media Services 

 

5.1 Datacenter Recovery Team

All Contact Information is located in Appendix A

 

 

 

 

 

 

 

 

 

 

 

 

Team Lead:Manager, Infrastructure Services
Team Members:System Administrators (2)
 Desktop Systems Administrator
 Network Communications Technicians (2)

 

 

5.2 Desktop, Lab, and Classroom Recovery Team

All Contact Information is located in Appendix A

Commander.

 

Team Lead:Manager, User Services
Team Members:Manager, Classroom and Media Services
 Desktop Systems Administrator
 Computing Coordinators (7)
 Lab and Student Computing Coordinator
 Equipment Systems Specialist

 

 

5.3 Enterprise Systems Recovery Team

All Contact Information is located in Appendix A

 

Team Lead:Manager, Information Systems
Team Members:Manager, Infrastructure Services
 Programmer/Analysts (4)
 Web Programmer/Analyst
 System Administrator
 Computing Coordinators supporting affected areas (business services, payroll, enrollment

services, etc.)

 Key Business Unit Personnel as needed by type of incident (payroll clerk, accountant,

registrar, etc.)

 

 

5.4 Infrastructure and Web Recovery Team

All Contact Information is located in Appendix A

Commander.

 

Team Lead:Manager, Infrastructure Services
Team Members:System Administrators (2)
 Desktop Systems Administrator
 Web Programmer/Analyst

 

 

5.5 Telecommunications, Network, and Internet Services Recovery Team

All Contact Information is located in Appendix A

Commander.

 

Team Lead:Manager, Infrastructure Services
Team Members:Communications Technicians (2)
 System Administrator

 

 

Section 6: Recovery Preparations

 

6.1 Data Recovery Information:

 

6.2 Central Datacenter and Server Recovery Information:

 

6.3 Network and Telecommunication Recovery Information:

 

6.4 Application Recovery Information:

 

6.5 Desktop Equipment Recovery Information:

Section 7: Disaster Recovery Processes and Procedures

7.1 Emergency Response:

 

7.2 Incident Command Team:

 

7.3 Disaster Recovery Teams:

7.4 General System/Application Recovery Procedures/Outline:

 

 

8.0 Network & Telecommunication Recovery Guidelines:

Appendix A. IT Contact List

 

 

Appendix B. Crisis Management Team Contact List

 

 

Appendix C: IT Recovery Priority List

The following priorities have been established by the department of Information Technology with consultation from the campus community.

 

C.1 IT Infrastructure Priorities:

 

C.2 IT System Priorities:

 

 

C.3 Consortium, Outsourced, and Cloud-based IT System Priorities:

 

Application/System NamePriorityRTORPO
    
    
    
    
    
    
    
    
    
    
    
    
    

 

(1) Critical – Basic infrastructure and must be restored as soon as possible.

(2) High – Systems of extreme importance, but do not provide infrastructure.

(3) Medium – Important systems and applications, but do not have university-wide impact.

(4) Low – Systems important to specific departments or specific small populations of users.

(5) Full –Systems that may not be restored to functional status until normal operations are reestablished.

Note: RTO is recovery time objective, RPO is recovery point objective

 

C.4 IT Facility Priorities

 

Building NamePriority
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  

 

Note: building list continues on next page.

 

(1) Critical, needed for maintenance of public health and safety, communications.

(2) High, needed for income maintenance for students, employees; payments to vendors; requirements for compliance or regulation; effect on cash flow; effect on production and delivery of services (housing, dining, student services).

(3) Medium, needed for mission of university, delivery of classes.

(4) Low, everything else

 

 

 

Appendix D: Vendor Information

 

Appendix E: Disaster Recovery Signoff Sheet

I have been briefed and given an overview of the Disaster Recovery Plan and I am familiar with my responsibilities.

 

NameSignatureDate
   
   
   
   
   
   
   
   
   
   
   
   
   
   
   
   
   
   
   
   
   
   
   
   
   
   
   
   
   
   
   
   
   
   
   
   
   
   

Displaying Accounts and Transactions in the Banking System

/in /by

Displaying Accounts and Transactions in the Banking System

Expand the Banking System from Lab 2 to display accounts and transactions.

Perform the following.

1. After a successful Login, develop the elements to display a list of accounts for the user.

2. Provide the ability for the user to select an account to display.

3. Develop the elements for displaying the transactions for the selected account. Display the running balance for the account.

When completed, place the project file into a zip file and submit it to Canvas.

(Using Lab1 source code we need to create all the above functionalities in Lab3 and code need to be without errors and operational).

Banking System

/in /by

Lab 1/Banking System/build.xml

Builds, tests, and runs the project Banking System.

Lab 1/Banking System/build/classes/.netbeans_automatic_build

Lab 1/Banking System/build/classes/.netbeans_update_resources

Lab 1/Banking System/build/classes/banking/BankingSystem.class

package banking;
public synchronized class BankingSystem {
    public void BankingSystem();
    public static void main(String[]);
}

Lab 1/Banking System/build/classes/banking/database/AccountDA.class

package banking.database;
public synchronized class AccountDA {
    public static java.util.ArrayList accounts;
    public void AccountDA();
    public static void add(banking.domain.Account);
    public static java.util.ArrayList getCustomerAccounts(int);
    public static void initialize();
    static void <clinit>();
}

Lab 1/Banking System/build/classes/banking/database/CustomerDA.class

package banking.database;
public synchronized class CustomerDA {
    private static java.util.ArrayList customers;
    public void CustomerDA();
    public static void add(banking.domain.Customer);
    public static java.util.ArrayList getCustomers();
    public static void inititialize();
    static void <clinit>();
}

Lab 1/Banking System/build/classes/banking/database/TransactionDA.class

package banking.database;
public synchronized class TransactionDA {
    private static java.util.ArrayList transactions;
    public void TransactionDA();
    public static void add(banking.domain.Transaction);
    public static java.util.ArrayList getAccountTransactions(int);
    public static void initialize();
    static void <clinit>();
}

Lab 1/Banking System/build/classes/banking/domain/Account.class

package banking.domain;
public abstract synchronized class Account {
    private int accountNumber;
    private int customerID;
    private String accountName;
    private java.util.Date dateOpened;
    public void Account();
    public void add();
    public String getAccountName();
    public int getAccountNumber();
    public static java.util.ArrayList getCustomerAccounts(int);
    public int getCustomerID();
    public java.util.Date getDateOpened();
    public java.util.ArrayList getTransactions();
    public static void initialize();
    public void setAccountName(String);
    public void setAccountNumber(int);
    public void setCustomerID(int);
    public void setDateOpened(java.util.Date);
    public String toString();
}

Lab 1/Banking System/build/classes/banking/domain/Asset.class

package banking.domain;
public synchronized class Asset extends Account {
    public void Asset();
}

Lab 1/Banking System/build/classes/banking/domain/Customer.class

package banking.domain;
public synchronized class Customer {
    private int customerID;
    private String name;
    private long phoneNumber;
    public void Customer();
    public void add();
    public static void add(Customer);
    public java.util.ArrayList getAccounts();
    public int getCustomerID();
    public static java.util.ArrayList getCustomers();
    public String getName();
    public long getPhoneNumber();
    public void setCustomerID(int);
    public void setName(String);
    public void setPhoneNumber(long);
    public static void initialize();
    public String toString();
}

Lab 1/Banking System/build/classes/banking/domain/Liability.class

package banking.domain;
public synchronized class Liability extends Account {
    public void Liability();
}

Lab 1/Banking System/build/classes/banking/domain/Transaction.class

package banking.domain;
public synchronized class Transaction {
    private double amount;
    private int transactionID;
    private java.util.Date transactionDate;
    private int accountNumber;
    private String description;
    public void Transaction();
    public void add();
    public int getAccountNumber();
    public double getAmount();
    public static java.util.ArrayList getAccountTransactions(int);
    public String getDescription();
    public java.util.Date getTransactionDate();
    public int getTransactionID();
    public static void initialize();
    public void setAccountNumber(int);
    public void setAmount(double);
    public void setDescription(String);
    public void setTransactionDate(java.util.Date);
    public void setTransactionID(int);
    public String toString();
}

Lab 1/Banking System/manifest.mf

Manifest-Version: 1.0 X-COMMENT: Main-Class will be added automatically by build

Lab 1/Banking System/nbproject/build-impl.xml

Must set src.dir Must set test.src.dir Must set build.dir Must set dist.dir Must set build.classes.dir Must set dist.javadoc.dir Must set build.test.classes.dir Must set build.test.results.dir Must set build.classes.excludes Must set dist.jar Must set javac.includes No tests executed. Must set JVM to use for profiling in profiler.info.jvm Must set profiler agent JVM arguments in profiler.info.jvmargs.agent

Lab 1/Banking System/nbproject/genfiles.properties

build.xml.data.CRC32=db319861 build.xml.script.CRC32=538a4852 build.xml.stylesheet.CRC32=8064a381@1.80.1.48 # This file is used by a NetBeans-based IDE to track changes in generated files such as build-impl.xml. # Do not edit this file. You may delete it but then the IDE will never regenerate such files for you. nbproject/build-impl.xml.data.CRC32=db319861 nbproject/build-impl.xml.script.CRC32=ae7b57ca nbproject/build-impl.xml.stylesheet.CRC32=830a3534@1.80.1.48

Lab 1/Banking System/nbproject/private/private.properties

compile.on.save=true user.properties.file=C:\\Users\\dstrong\\AppData\\Roaming\\NetBeans\\8.2\\build.properties

Lab 1/Banking System/nbproject/private/private.xml

file:/C:/Users/dstrong/Documents/Yogi/Courses/CIS640/Projects/Labs/Banking%20System/Banking%20System/src/banking/domain/Transaction.java file:/C:/Users/dstrong/Documents/Yogi/Courses/CIS640/Projects/Labs/Banking%20System/Banking%20System/src/banking/database/TransactionDA.java

Lab 1/Banking System/nbproject/project.properties

annotation.processing.enabled=true annotation.processing.enabled.in.editor=false annotation.processing.processor.options= annotation.processing.processors.list= annotation.processing.run.all.processors=true annotation.processing.source.output=${build.generated.sources.dir}/ap-source-output build.classes.dir=${build.dir}/classes build.classes.excludes=**/*.java,**/*.form # This directory is removed when the project is cleaned: build.dir=build build.generated.dir=${build.dir}/generated build.generated.sources.dir=${build.dir}/generated-sources # Only compile against the classpath explicitly listed here: build.sysclasspath=ignore build.test.classes.dir=${build.dir}/test/classes build.test.results.dir=${build.dir}/test/results # Uncomment to specify the preferred debugger connection transport: #debug.transport=dt_socket debug.classpath=\ ${run.classpath} debug.test.classpath=\ ${run.test.classpath} # Files in build.classes.dir which should be excluded from distribution jar dist.archive.excludes= # This directory is removed when the project is cleaned: dist.dir=dist dist.jar=${dist.dir}/Banking_System.jar dist.javadoc.dir=${dist.dir}/javadoc excludes= includes=** jar.compress=false javac.classpath= # Space-separated list of extra javac options javac.compilerargs= javac.deprecation=false javac.external.vm=true javac.processorpath=\ ${javac.classpath} javac.source=1.8 javac.target=1.8 javac.test.classpath=\ ${javac.classpath}:\ ${build.classes.dir} javac.test.processorpath=\ ${javac.test.classpath} javadoc.additionalparam= javadoc.author=false javadoc.encoding=${source.encoding} javadoc.noindex=false javadoc.nonavbar=false javadoc.notree=false javadoc.private=false javadoc.splitindex=true javadoc.use=true javadoc.version=false javadoc.windowtitle= main.class=banking.BankingSystem manifest.file=manifest.mf meta.inf.dir=${src.dir}/META-INF mkdist.disabled=false platform.active=default_platform run.classpath=\ ${javac.classpath}:\ ${build.classes.dir} # Space-separated list of JVM arguments used when running the project. # You may also define separate properties like run-sys-prop.name=value instead of -Dname=value. # To set system properties for unit tests define test-sys-prop.name=value: run.jvmargs= run.test.classpath=\ ${javac.test.classpath}:\ ${build.test.classes.dir} source.encoding=UTF-8 src.dir=src test.src.dir=test

Lab 1/Banking System/nbproject/project.xml

org.netbeans.modules.java.j2seproject Banking System

Lab 1/Banking System/src/banking/BankingSystem.java

Lab 1/Banking System/src/banking/BankingSystem.java

package  banking ;

import  banking . domain . Customer ;
import  banking . domain . Account ;
import  banking . domain . Transaction ;
import  java . util . ArrayList ;

public   class   BankingSystem   {

public   static   void  main ( String []  args )   {
Customer . initialize ();
Account . initialize ();
Transaction . initialize ();

ArrayList < Customer >  customers  =   Customer . getCustomers ();

for ( int  i  =   0 ;  i  <  customers . size ();  i ++ ){
System . out . println ( customers . get ( i ));
}
}
}

Lab 1/Banking System/src/banking/database/AccountDA.java

Lab 1/Banking System/src/banking/database/AccountDA.java

package  banking . database ;

import  banking . domain . Account ;
import  banking . domain . Asset ;
import  banking . domain . Liability ;

import  java . util . ArrayList ;
import  java . util . Date ;

public   class   AccountDA   {
public   static   ArrayList < Account >  accounts  =   new   ArrayList < Account > ( 5 );

public   static   void  add ( Account  acc )   {
accounts . add ( acc );
}

public   static   ArrayList < Account >  getCustomerAccounts ( int  custID )   {
Account  acc ;
ArrayList < Account >  customerAccounts  =   new   ArrayList < Account > ( 5 );

for ( int  i  =   0 ;  i  <  accounts . size ();  i ++ )   {
acc  =  accounts . get ( i );
if   ( acc . getCustomerID ()   ==  custID )
customerAccounts . add ( acc );
}

return  customerAccounts ;
}

public   static   void  initialize (){
Account  a ;
Date  today  =   new   Date ();

a  =   new   Asset ();
a . setAccountNumber ( 10101 );
a . setCustomerID ( 101 );
a . setAccountName ( "Customer One Checking Account" );
a . setDateOpened ( today );
a . add ();

a  =   new   Asset ();
a . setAccountNumber ( 10102 );
a . setCustomerID ( 101 );
a . setAccountName ( "Customer One Savings Account" );
a . setDateOpened ( today );
a . add ();

a  =   new   Asset ();
a . setAccountNumber ( 10201 );
a . setCustomerID ( 102 );
a . setAccountName ( "Savings Account" );
a . setDateOpened ( today );
a . add ();

a  =   new   Liability ();
a . setAccountNumber ( 10202 );
a . setCustomerID ( 102 );
a . setAccountName ( "Customer Two Credit Card" );
a . setDateOpened ( today );
a . add ();
}
}

Lab 1/Banking System/src/banking/database/CustomerDA.java

Lab 1/Banking System/src/banking/database/CustomerDA.java

package  banking . database ;

import  banking . domain . Customer ;
import  java . util . ArrayList ;

public   class   CustomerDA   {
private   static   ArrayList < Customer >  customers  =   new   ArrayList < Customer > ( 5 );

public   static   void  add ( Customer  c )   {
customers . add ( c );
}

public   static   ArrayList < Customer >  getCustomers ()   {
return  customers ;
}

public   static   void  inititialize ()   {
Customer  c ;

c  =   new   Customer ();
c . setCustomerID ( 101 );
c . setName ( "Customer One" );
c . setPhoneNumber ( 5551212 );
c . add ();

c  =   new   Customer ();
c . setCustomerID ( 102 );
c . setName ( "Customer Two" );
c . setPhoneNumber ( 4442323 );
c . add ();
}
}

Lab 1/Banking System/src/banking/database/TransactionDA.java

Lab 1/Banking System/src/banking/database/TransactionDA.java

package  banking . database ;

import  banking . domain . Transaction ;

import  java . util . ArrayList ;
import  java . util . Date ;

public   class   TransactionDA   {
private   static   ArrayList < Transaction >  transactions  =   new   ArrayList < Transaction > ( 5 );

public   static   void  add ( Transaction  trans )   {
trans . setTransactionID ( transactions . size ()   +   1 );
transactions . add ( trans );
}

public   static   ArrayList < Transaction >  getAccountTransactions ( int  accNo ){
ArrayList < Transaction >  accountTransactions  =   new   ArrayList < Transaction > ( 5 );
Transaction  trans ;

for   ( int  i  =   0 ;  i  <  transactions . size ();  i ++ )   {
trans  =  transactions . get ( i );
if   ( accNo  ==  trans . getAccountNumber ())
accountTransactions . add ( trans );
}
return  accountTransactions ;
}

public   static   void  initialize ()   {
Transaction  t ;
Date  today  =   new   Date ();

t  =   new   Transaction ();
t . setAccountNumber ( 10101 );
t . setTransactionDate ( today );
t . setDescription ( "Transaction 1" );
t . setAmount ( 100 );
t . add ();

t  =   new   Transaction ();
t . setAccountNumber ( 10101 );
t . setTransactionDate ( today );
t . setDescription ( "Transaction 2" );
t . setAmount ( - 21.95 );
t . add ();

t  =   new   Transaction ();
t . setAccountNumber ( 10101 );
t . setTransactionDate ( today );
t . setDescription ( "Transaction 3" );
t . setAmount ( 16.25 );
t . add ();

t  =   new   Transaction ();
t . setAccountNumber ( 10102 );
t . setTransactionDate ( today );
t . setDescription ( "Transaction 1" );
t . setAmount ( 50.00 );
t . add ();

t  =   new   Transaction ();
t . setAccountNumber ( 10102 );
t . setTransactionDate ( today );
t . setDescription ( "Transaction 2" );
t . setAmount ( 250.00 );
t . add ();

t  =   new   Transaction ();
t . setAccountNumber ( 10102 );
t . setTransactionDate ( today );
t . setDescription ( "Transaction 3" );
t . setAmount ( - 10.00 );
t . add ();

t  =   new   Transaction ();
t . setAccountNumber ( 10202 );
t . setTransactionDate ( today );
t . setDescription ( "Transaction 1" );
t . setAmount ( 500.00 );
t . add ();

t  =   new   Transaction ();
t . setAccountNumber ( 10202 );
t . setTransactionDate ( today );
t . setDescription ( "Transaction 2" );
t . setAmount ( - 50.00 );
t . add ();

t  =   new   Transaction ();
t . setAccountNumber ( 10202 );
t . setTransactionDate ( today );
t . setDescription ( "Transaction 3" );
t . setAmount ( 25.00 );
t . add ();

t  =   new   Transaction ();
t . setAccountNumber ( 10201 );
t . setTransactionDate ( today );
t . setDescription ( "Transaction 1" );
t . setAmount ( 49.75 );
t . add ();

t  =   new   Transaction ();
t . setAccountNumber ( 10201 );
t . setTransactionDate ( today );
t . setDescription ( "Transaction 2" );
t . setAmount ( 16.25 );
t . add ();

t  =   new   Transaction ();
t . setAccountNumber ( 10201 );
t . setTransactionDate ( today );
t . setDescription ( "Transaction 3" );
t . setAmount ( - 25.0 );
t . add ();
}
}

Lab 1/Banking System/src/banking/domain/Account.java

Lab 1/Banking System/src/banking/domain/Account.java

package  banking . domain ;

import  banking . database . AccountDA ;
import  java . util . Date ;
import  java . util . ArrayList ;

public   abstract   class   Account   {
private   int  accountNumber ;
private   int  customerID ;
private   String  accountName ;
private   Date  dateOpened ;

public   void  add ()   {
AccountDA . add ( this );
}

public   String  getAccountName ()   {
return  accountName ;
}

public   int  getAccountNumber ()   {
return  accountNumber ;
}

public   static   ArrayList < Account >  getCustomerAccounts ( int  custID )   {
return   AccountDA . getCustomerAccounts ( custID );
}

public   int  getCustomerID ()   {
return  customerID ;
}

public   Date  getDateOpened ()   {
return  dateOpened ;
}

public   ArrayList < Transaction >  getTransactions ()   {
return   Transaction . getAccountTransactions ( accountNumber );
}

public   static   void  initialize ()   {
AccountDA . initialize ();
}

public   void  setAccountName ( String  accountName )   {
this . accountName  =  accountName ;
}

public   void  setAccountNumber ( int  accountNumber )   {
this . accountNumber  =  accountNumber ;
}

public   void  setCustomerID ( int  customerID )   {
this . customerID  =  customerID ;
}

public   void  setDateOpened ( Date  dateOpened )   {
this . dateOpened  =  dateOpened ;
}

public   String  toString ()   {
ArrayList < Transaction >  transactions  =  getTransactions ();
double  sum  =   0.0 ;

String  returnString  =   "Account: "   +  accountNumber  +   " "   +  accountName  +   " "   +  dateOpened ;
for   ( int  i  =   0 ;  i  <  transactions . size ();  i ++ ){
sum  =  sum +=  transactions . get ( i ). getAmount ();
returnString  =  returnString  +   "\n          "   +  transactions . get ( i )   +   "  "   +  sum ;
}

return  returnString ;
}

}

Lab 1/Banking System/src/banking/domain/Asset.java

Lab 1/Banking System/src/banking/domain/Asset.java

package  banking . domain ;

public   class   Asset   extends   Account   {

}

Lab 1/Banking System/src/banking/domain/Customer.java

Lab 1/Banking System/src/banking/domain/Customer.java

package  banking . domain ;

import  banking . database . CustomerDA ;
import  banking . domain . Account ;
import  java . util . ArrayList ;

public   class   Customer   {
private   int  customerID ;
private   String  name ;
private   long  phoneNumber ;

public   void  add ()   {
CustomerDA . add ( this );
}

public   static   void  add ( Customer  c )   {
CustomerDA . add ( c );
}

public   ArrayList < Account >  getAccounts ()   {
return   Account . getCustomerAccounts ( customerID );
}

public   int  getCustomerID ()   {
return  customerID ;
}

public   static   ArrayList < Customer >  getCustomers ()   {
return   CustomerDA . getCustomers ();
}

public   String  getName ()   {
return  name ;
}

public   long  getPhoneNumber ()   {
return  phoneNumber ;
}

public   void  setCustomerID ( int  customerID )   {
this . customerID  =  customerID ;
}

public   void  setName ( String  name )   {
this . name  =  name ;
}

public   void  setPhoneNumber ( long  phoneNumber )   {
this . phoneNumber  =  phoneNumber ;
}

public   static   void  initialize ()   {
CustomerDA . inititialize ();
}

public   String  toString ()   {
String  returnString  =   "\nCustomer "   +  customerID  +   " "   +  name ;
ArrayList < Account >  accounts  =  getAccounts ();

for   ( int  i  =   0 ;  i  <  accounts . size ();  i ++ )   {
returnString  =  returnString  +   "\n     "   +  accounts . get ( i );
}

return  returnString ;
}
}

Lab 1/Banking System/src/banking/domain/Liability.java

Lab 1/Banking System/src/banking/domain/Liability.java

package  banking . domain ;

public   class   Liability   extends   Account {

}

Lab 1/Banking System/src/banking/domain/Transaction.java

Lab 1/Banking System/src/banking/domain/Transaction.java

package  banking . domain ;

import  banking . database . TransactionDA ;

import  java . util . ArrayList ;
import  java . util . Date ;

public   class   Transaction   {
private   double  amount ;
private   int  transactionID ;
private   Date  transactionDate ;
private   int  accountNumber ;
private   String  description ;

public   void  add ()   {
TransactionDA . add ( this );
}

public   int  getAccountNumber ()   {
return  accountNumber ;
}

public   double  getAmount ()   {
return  amount ;
}

public   static   ArrayList < Transaction >  getAccountTransactions ( int  accNo )   {
return   TransactionDA . getAccountTransactions ( accNo );
}

public   String  getDescription ()   {
return  description ;
}

public   Date  getTransactionDate ()   {
return  transactionDate ;
}

public   int  getTransactionID ()   {
return  transactionID ;
}

public   static   void  initialize ()   {
TransactionDA . initialize ();
}

Building a Calculator

/in /by

Lab #1 — Building a Calculator

Your task for Lab #1 is to build a calculator in Java that has two modes, controllable by command-line options postfix and infix. In both modes the calculator will read lines of input from standard input. For each input line, the calculator will evaluate the expression that was input and print the result on a separate line. The program ends when it encounters the EOF character,similar to the behavior of most Unix utilities.

To simplify matters regarding dealing with different types of numbers, in this assignment, all numbers are to be represented internally as either Java floatprimitives or Floatobjects depending on your implementation choices.

Your calculator will implement the following operations:

  • +, -, *, /
  • ^ (exponentiation: e.g., 2^3 = 8).

Your calculator will implement expressions containing either a sole number or operations applied to numbers.

Mode #1 — Postfix Notation

The first mode that you will implement is one where the calculator accepts anexpression that is expressed in postfix notation. For those of you familiar with HP’s line of scientific and graphing calculators, postfix notation is also known as RPN or Reverse Polish Notation, in honor of the Polish logician Jan Łukasiewicz who invented Polish notation, also known as prefix notation.

Here are examples of expressions written in postfix notation with their conversions to infix notation and their evaluations:

2 3 +

2 + 3

5

2 3 + 5 *

(2 + 3) * 5

25

2 3 5 * +

2 + (3 * 5)

17

2 3 2 ^ * -10 –

2 * (3 ^ 2) – -10

28

How an RPN calculator works internally is as follows: it maintains an internal stack that is used to store operands and intermediate results. Let’s use the expression “4 3 + 5 *” as an example. The first thing that we do is lexical analysis on the input string by first splitting the string by its whitespace characters and then performing the proper type conversions on the numbers, resulting in a list that looks like this:

[4.0, 3.0, “+”, 5.0, “*”]

Next, we iterate through the list. For each number, we push it onto the stack. Once we reach an operator on the list, we pop the stack twice, perform that operation on the popped numbers, and then push the result onto the stack. In this example, the elements 3.0 and 4.0 are popped from the stack. We then perform the “+” operation on the second and first elements popped from the stack (order matters for “-”, “/”, and “^”), and then push the result (12.0) onto the stack. Then, as we continue iterating through the list, we encounter 5.0, and thus we push it on the stack, resulting in a stack with the elements 12.0 (bottom) and 5.0 (top). Finally, the last token in the list is “*”, and so we pop the stack twice, multiplying 5.0 and 12.0 to get 60.0, and then we push it back on the stack.

When we have exhausted the list of tokens, we pop the stack and print the popped value as the result of the expression.

One of the nice properties of postfix notion is the lack of a need to specify operator precedence. It is this property that makes it possible to implement an RPN calculator without the need for specify a formal grammar for expressions. In fact, there are full-fledged programming languages such as Forth and PostScript that use postfix notation and rely on a stack.

Mode #2 — Infix Notation

Unlike a postfix calculator where parsing is a very straightforward task, parsing is not as straightforward in infix notation, since you have to concern yourself with expressions of arbitrary length and operator precedence. Your calculator will have to properly implement the PEMDAS (parentheses, exponents, multiplication, division, addition, subtraction) order of operations that are from elementary algebra.

Thankfully with the help of parser generators such as ANTLR, you won’t have to deal with the labor of implementing parsing algorithms.

Here is an excellent tutorial for using ANTLR:https://tomassetti.me/antlr-mega-tutorial/ (Links to an external site.). Please also refer to the main ANTLR website athttps://www.antlr.org (Links to an external site.).

Your goals are the following:

  1. Write a BNF or EBNF grammar that is able to represent expressions in infix notation that is also able to implement the PEMDAS order of operations.
  2. Express that grammar as an ANTLR grammar.
  3. Use ANTLR to generate an abstract syntax tree.
  4. Traverse the abstract syntax tree to evaluate the expression. There are two ways of doing this: (1) either evaluating the abstract syntax tree directly, or (2) using the AST to generate a postfix notation representation of the expression, and then evaluating it as in Mode #1.

Some Examples:

$ java Calculator postfix

Calculator> 2 4 * 2 ^ 10 –

54

Calculator> 5

5

Calculator> 8 24 + 9 –

23

$ java Calculator infix

Calculator> (2 * 4)^2 – 10

54

Calculator> 5

5

Calculator> 8 + 24 – 9

23

Deliverable:

A collection of Java and ANTLR source code files in a *.zip archive, where the main method is located in a class called Calculator and in a file called Calculator.java.

Grading Rubric:

Mode #1 (Postfix Notation): 30%

Mode #2 (Infix Notation Grammar and Parsing): 50%

Mode #2 (Infix Notation Evaluation): 20%

Note:Your code must compile in order for it to receive any credit; any submission that does not compile will receive a grade of 0%.

 

Adder.java

/in /by

Adder.g4

grammar Adder; WS : [ \t\r\n]+ -> skip ; Num : (‘-‘)?[0-9]+ | (‘-‘)?[0-9]+’.'[0-9]+ ; expr : expr ‘+’ expr # addExpr | Num # numExpr ; start : expr EOF ; Error : . ;

Adder.java

Adder.java

import  org . antlr . v4 . runtime . * ;
import  org . antlr . v4 . runtime . tree . * ;
import  java . io . * ;

public   class   Adder   {
public   static   void  main ( String []  args )   throws   IOException   {
BufferedReader  in  =
new   BufferedReader ( new   InputStreamReader ( System . in ));
CharStream  inputStream  =   CharStreams . fromReader ( in );
AdderLexer  lexer  =   new   AdderLexer ( inputStream );
CommonTokenStream  commonTokenStream  =   new   CommonTokenStream ( lexer );
AdderParser  parser  =   new   AdderParser ( commonTokenStream );
parser . setErrorHandler ( new   BailErrorStrategy ());

ParseTree  tree  =  parser . start ();
AdderInterpreter  interpreter  =   new   AdderInterpreter ();
Float  result  =  interpreter . visit ( tree );
System . out . println ( result . toString ());
}
}

AdderInterpreter.java

AdderInterpreter.java

public   class   AdderInterpreter   extends   AdderBaseVisitor < Float >   {
@ Override
public   Float  visitAddExpr ( AdderParser . AddExprContext  ctx )   {
float  result  =  visit ( ctx . expr ( 0 )). floatValue ()   +
visit ( ctx . expr ( 1 )). floatValue ();
return   Float . valueOf ( result );
}

@ Override
public   Float  visitNumExpr ( AdderParser . NumExprContext  ctx )   {
return   Float . valueOf ( ctx . Num (). getText ());
}

@ Override
public   Float  visitStart ( AdderParser . StartContext  ctx )   {
return  visit ( ctx . expr ());
}
}