Projects In C++

  1. Interpreter
  2. Garbage Collector
  3. CPU Scheduler
  4. Resource Management for Distributed Continuous Media Servers (DCMS)
  5. Progressive Evaluation of OLAP Queries
  6. Declarative Networking
  7. Line Editor


Interpreter

Brief Description: Design and implement an interpreter for a simple (minimal, small) programming language. A suitable language might be a procedural, an object-oriented, a functional or a logic programming language. A suitable language must have both a means of abstraction (e.g. function definition, lambda expression) and a means of combination (e.g. function application). A particularly recommendable choice would be an interpreter for the (untyped) lambda calculus, which is the basis of functional programming languages.

Top


Garbage Collector

Brief Description: Design and implement a garbage collector suitable for the implementation of interpreters and virtual machines in C++. The garbage collector should provide an interface through which memory can be allocated and external pointers to managed memory can be registered/ unregistered.

Top


CPU Scheduler

Brief Description: This is a clock-driven simulation, in which the clock is a counter that is incremented each simulated second. The clock is initially 0, and continues “ticking” until all the jobs in the input have been serviced and left the system. This simulation runs until a particular number of jobs have been serviced. This number is input by the user.

When a job enters the system, it is enqueued on a wait queue. The CPU’s “queue” represents the jobs that are currently being serviced. If there is room in the CPU’s queue, a job is dequeued from the wait queue and enqueued onto the CPU queue. Jobs in the CPU queue are serviced using the following scheme: although the CPU actually executes only one job at a time, there can be as many as ten jobs in the CPU queue. To service these jobs, the CPU allocates a “time-slice” to each job in the CPU queue, depending on its class. To the observer, it appears that the CPU services several jobs simultaneously; however, most jobs are interrupted when they require I/O or other services. To avoid idleness while waiting for the required service, the CPU starts working on the next job in the CPU queue.

We simulate this by having each job fall into one of two job classes: I/O bound and CPU bound. I/O-bound jobs have a time-slice of 0.1 seconds, while CPU-bound jobs have a time-slice of 0.2 seconds. The job at the front of the CPU queue executes for its required time-slice; then it is dequeued and enqueued at the rear of the CPU queue. Jobs remain in the CPU queue until they complete their service time. Note that jobs may leave the CPU at non-integral times.

Your program must gather statistics, compute, and report the following information:

The number of jobs for each job class and CPU requirement.

  • The average time that a job spends in the wait queue.
  • The average elapsed time that a job spends in the CPU queue, for each of the job types, broken down by CPU time required and job class.
  • The percentage of the time that the CPU is busy. (The CPU is idle if there are no jobs in the system.)
  • The “through-put” of the system, expressed as the number of jobs handled per hour.
    To summarize, in each clock cycle (a simulated second), the following tasks are performed:
  • The clock is incremented.
  • If a job (or jobs) enters the system, determine the job number, job class, and CPU time required. The job class and CPU time required for each job must be determined by a random number generator. Time stamp the job, and enqueue it in the wait queue.
  • If the CPU queue is not full, dequeue the front job(s) from the wait queue and enqueue the job(s) in the CPU queue.
  • If the CPU queue is not empty, service the jobs in the CPU queue, giving each job serviced the correct time-slice. (Do not dequeue a job from the CPU queue until its “execution” is complete.) Otherwise, if the CPU queue is empty, increment the CPU idle time.
  • If a job (or jobs) completes its execution, remove it from the CPU queue and calculate the elapsed times for statistics.

Top

Input

Your program should prompt the user to input the simulation parameters:

  • The number of jobs to be generated.
  • The probability of one job entering the system in each simulated second.
  • The probability of two jobs entering the system in each simulated second.
  • The distribution of CPU service times for jobs (what percentage of jobs take 10, 20, 30 or 60 seconds). These must add up to 100%.
  • The job class distribution (what percentage of jobs are I/O bound and CPU bound). These must add up to 100%.

Output

All program output must be written to a text file, “CpuSim.out”, which is printed and turned in for grading.

  • Echoprint the simulation parameters supplied by the user. Be sure to label them clearly.
  • For the first 10 minutes of simulated clock time, print the job number, job class, CPU time and time each job entered the system.
  • After the first 10 minutes of simulated clock time, print out a system summary every 60 seconds. The summary should contain the time, the number of jobs in each queue, and the job number of the job at the front of the queue.
  • When the simulation is complete (the specified number of jobs have been executed), print a report of the job statistics as requested above. Be sure that your report is logically arranged and neatly labeled and formatted.

Simulation Parameters for Testing

Use the following input parameters for testing the simulation:

  • The number of jobs to execute is 250.
  • The probability of a job or jobs entering the system in any simulated second (one clock tick) is:
    0.040 for 1 job
    0.005 for 2 jobs entering in the same second.
  • The distribution of the CPU service times for jobs is:
    32.5% of the jobs require 10 seconds of CPU time
    50.0% of the jobs require 20 seconds of CPU time
    12.5% of the jobs require 30 seconds of CPU time
    5.0% of the jobs require 60 seconds of CPU time
  • The job class distribution is:
    65% of the jobs are I/O bound
    35% of the jobs are CPU bound

Top


Resource Management for Distributed Continuous Media Servers (DCMS)

Brief Description: Consider a network of storage and streaming nodes that serve continuous media objects such as video, audio, etc. [1]. Servers are scattered globally according to locality of users and interconnected via high-speed dedicated links. A user connects to some local server and requests for an object: we will implement a middle-ware to locate the replicas of the object in the network, determine the path with minimum cost to stream the object to the user across the network, and suggest an appropriate caching strategy to the servers along the path.

Considering the variable cost of the paths, use your imagination to visualize a DCMS network as a large set of moving objects (the servers and the media objects) interconnected via a bunch of springs (the links) according to a specific topology; i.e. similar to the funny models for molecular networks, as we have all seen and played with at our physics/chemistry labs! The loads imposed by users to the network at different points of time are the forces that cause the moving objects to vibrate. In such a dynamic environment, our middle-ware is supposed to monitor the spatial state of the objects and respond range and nearest neighbor queries in reply to local severs that try to reserve resources as users demand for objects. Distance scan queries can also come handy when servers along a path need to know if they are to cache the streamed objects; decision is to be made according to users’ access pattern that has temporal attributes.

Top


Progressive Evaluation of OLAP Queries

Brief Description: We will implement a 3-tier application that uses progressive algorithms to evaluate batches of range aggregate queries as efficiently as possible. The details of the application are yet to be decided, but two possibilities include:

  • a service to provide arbitrary scale moving average plots of stock prices.
  • an application providing user configurable summary views of a large climate dataset.

The client application will obtain all data from a middleware web service. We will define the interface for this service in a way that allows it to be used for a wide variety of applications and builds on recent research.

The web service may be partially written in Java, but the core algorithms will be implemented in C++, building on our existing code base. Embedded SQL will be used to access persistent data. Our algorithms will provide progressive OLAP by using successively better wavelet expansions of the batch of queries. These approximations can be evaluated efficiently as long as we store the wavelet transform of the data.

Work on the data tier of this application will include designing the relational store for transformed data and implementing batch load and update algorithms so that data can be streamed in to an operational database.

Top


Declarative Networking

Brief Description: Any widely-distributed system needs to track its participating nodes, and be able to send messages among those nodes. This facility is often called an overlay network, since it provides an application with customized networking functionality (naming, topology, routing) that runs as a layer over traditional IP networking. Overlays are in wide use, including in commercial mail/calendar servers, application-level multicast systems, and distributed hash tables (DHTs).

It is tricky to design, build, and deploy an overlay suited to a particular application and environment. To ease this process, we have implemented P2, a system which uses a high-level declarative language to express overlay networks in a highly compact and reusable form. P2 has been used to specify and execute working, detailed overlays in over 100x less code than is used in traditional implementations. P2 automatically compiles high-level specifications to a dataflow-oriented runtime system, which can itself be used by expert programmers to specify efficient overlays.

Our work on P2 is part of a more general effort to revisit networking technology through the lens of database query processing. Our approach could provide not only simpler, safer specifications for network protocols, but also — within the same framework — the ability to query, monitor and control all aspects of the network’s distributed state.

Top


Line Editor

Brief Description: Your text editor will allow, us to read a file into memory where we shall say that it is stored in a buffer. The buffer will be implemented as an object of a class that we call Editor. We shall consider each line of text in an Editor object to be a string. Hence, the Editor class will be based on a List of strings. We shall devise editing commands that will do list operations on the lines in the buffer and will do string operations on the characters in a single line.

Since, at any moment, the user may be typing either characters to be inserted into a line or commands to apply to existing text, a text editor should always be written to be as forgiving of invalid input as possible recognizing illegal commands, and asking for confirmation before taking any drastic action like deleting the entire buffer.

We shall supply arguments, known as command line arguments to the main program of your editor implementation. These arguments allow us to run a compiled program, edit, with a standard invocation: edit inifile outfile. Here is the list of commands to be included in your text editor. Each command is given by typing the letter shown in response to the editor’s prompt ‘??’. The command letter may be typed in either uppercase or lowercase.

  • ‘R’ Read the text file, whose name is given in the command line, into the buffer. Any previous contents of the buffer are lost. At the conclusion the current line will be the first line of the file.
  • ‘W’ Write the contents of the buffer to the text file whose name is given in the command line. Neither the current line nor the buffer is changed.
  • ‘I’ Insert a single new line. The user must type in the new line and supply its line number in response to appropriate prompts.
  • ‘D’ Delete the current line and move to the next line.
  • ‘F’ Find the first line starting from the current line, that contains a target string that will be requested from the user.
  • ‘L’ Show the length in characters of the current line and the length in lines of the buffer.
  • ‘C’ Change a string requested from the user to a replacement text, also requested from the user working within the current line only.
  • ‘Q’ Quit the editor: Terminate immediately.
  • ‘H’ Print out help messages explaining all the commands. The program will also accept ‘?’ as an alternative to ‘H’.
  • ‘N’ Next line; Advance one line through the buffer.
  • ‘P’ Previous line: Back up on: line in the buffer.
  • ‘B’ Beginning: Go to the first line of the buffer.
  • ‘E ‘ End: go to the last line of the buffer.
  • ‘G’ Go to a user-specified line number in the buffer.
  • ‘S’ Substitute a line typed in by the user for the current line. The function should print out the line for verification and then request the new line,
  • ‘V’ View the entire contents of the buffer, printed out to the terminal.

Top

Comments are closed.