Introduction to the M/M/1 Queue

For one of my projects, I needed to learn how to build an M/M/1 event simulator.

I thought I’d post this for everyone to see and perhaps this might help you if you’re in a Queuing Theory class.

Let’s start with an example:

You want to simulate how long it takes for people to checkout at a gas station. We assume that there is only one cashier and that anyone in the line stays in the line. The line is FIFO (First In First Out or First Come First Served). With this in mind, we’ve studied surveillance tapes and we realize that on average six people come in per hour. From monitoring register transactions, we know on average the cashier can check out eight people an hour.

There is a lot of information there. Let’s break it down and give ourselves some variables:

  1. Arrival Rate(λ): 6
  2. Service Rate(μ): 8
  3. Number of Cashiers: 1
  4. Queuing Style: FIFO

With all of these in mind, we can begin to work with our problem.

First thing that we need to assume is that arrivals and departures are exponentially distributed. How do we know this? I’ll mention it later, but you don’t even need to know what that phrase means right now.

With this information, we can decide the following information right away:

  1. Queue Utilization: λ/μ
  2. Probability that there are 0 customers in line: 1 – λ/μ
  3. Average Waiting Time: λ/(μ(μ-λ))
  4. Average Time Customer Spends in the gas station: 1 / (μ – λ)
  5. Average Number of Customers Spends waiting for service: (λ * λ) / (μ(μ-λ))
  6. Average Number of Customers in the station: (λ/μ) / (1 – (λ/μ))

Now these are all static numbers. How do we actually make a simulation?

Well, remember how we said this is a M/M/1 queue? Well the M stands for exponential distribution. So we can calculate if there is an arrival in a certain unit of time with the following equation:

Probability of arrival = λ*e^-(λ * t)

(Hopefully now the gears are starting to turn in your head on how to do this)

In this case, t stands for time. So if we want to know what is the provability of an arrival in 1 second in our above example, then we have

6 * e^-(6 * 1) = 14.87%

What is e? e stands for our Euler’s number which is the opposite of the natural log. So, ln(e) = 1. Don’t worry about that too much if you don’t get it, normally there will be a button on your calculator that puts in e for you.

If you take a random number generator and compare that with the probability of an arrival, then you can figure out if an arrival occurred.

So (in C):


float result = 100 * lambda * pow(M_E, (lambda * time)); ///M_E is our Euler's Number

odds = rand() % 100;

if(result > odds)
{
printf("Arrival occurred!\n");
}
else
{
printf("No Arrival occurred!\n");
}

Now that we’ve got arrivals, let’s handle departures.

We are going to use a very similar equation:

μ*e^-(μ * t)

See? isn’t that different at all. The trick here is that we want to keep looping until we get a departure, because otherwise our customer will be stuck in limbo and never be able to leave (and that means that no one else can leave as well).

In C:

time = 0;
while(1)
{
time++;
float result = 100 * lambda * pow(M_E, (lambda * time)); ///M_E is our Euler's Number

odds = rand() % 100;

if(result > odds)
{
break;
}
}

Here we keep looping until we get what we want.

Finally, we need to be respectful of who is in the line in front of us.

To do this, we need to have some sort of way to track when people enter the line and how long it takes for them to leave. While I did this using C++ and a vector, it could be done in C using a linked list and then finding when the last departure is. Some last bits of code are to follow.

Psudocode:

if(last_departure > arrival)
{
leave_time = last_departure - arrival + time_checking_out
}
else
{
leave_time = arrival + time_checking_out
}

Hope this makes things easier for someone else.

Code:
Click Here!

Posted in Computer Science | Tagged , , | Leave a comment

@Anicorn_Watch The Trio of Time “Hidden Time Watch”

Taken from their website

A while back I came across this Kickstarter for an interesting watch concept.

I looked at it, watched the video, decided to back it and was an “Early Bird”. Eagerly waiting, my watch finally came in over the weekend. It was promised in October, but if you really think any Kickstarter campaign will be delivered on time, then you are going to be very disappointed.

So, let’s talk about this watch!

The good:

  • Firstly I opted for a metal band and it is hands down one of the best bands I’ve ever had for a watch. It is very robust, easy to adjust, and it doesn’t take off all of your arm hair.
  • Next is the glass, the glass on here is very nice to look at and is claimed to be sapphire glass (I don’t have the means to test or verify this). I do think it’s going to last a long time and not crack easily. It has a nice smooth feel and I can’t detect any imperfections by running my fingers and nails over it

The bad:

  • I got the “rose gold” color, but as it sits in front of me, it doesn’t have the right sheen of rose gold and more of a blanched copper.
  • This watch sits at 1/3 of an inch (8.5mm or 6 pennies stacked on each other) thick and I think that is remarkably thick. I think it should be at least half that size. After opening up the back, it appears that there is a lot of wasted space.
  • Speaking of opening up the back, it is really simple. This could easily be some generic watch guts.
  • Finally, what I was really disappointed in was the movement. I was thinking there was going to be a solid purple disk and the hour hand was just going to be a moving opacity filter. This isn’t the case. It is a gradient disk going from purple to white and moves as one unit. Kind of boring and also kind of cheap. I’d also note that the pictures show the gradient extending well over 180 degrees, but on mine, while it does extend past that, it is effectively non-existent past 135.

Overall thoughts:

Am I sad or do I regret that I backed this campaign? No.

Did I overpay at $140 USD? Oh yeah. Knowing what I know now, I would say that this timepiece is worth $100 at most, but I’d say it shouldn’t be sold for less than $56.

Should you get one? At the retail price of $220 (which by the way is significantly less than what the Kickstarter stated…) then there are much better watches to buy. For example, this Seiko.

Numerical review? 3/10. The biggest problems are it’s price, hour hand, and generic guts. You can slap a designer’s name on it, but it is still just an average over-priced watch.

Posted in Reviews | Tagged , , , | Leave a comment

PIC Watchdog Timers

I’m an admitted newbie to PIC uCs, but I thought I’d share a quick thing I just ran into and it deals with the watchdog timer.

I recently purchased some PIC16F722A-I/SP from Arrow, because unlike the PIC16F877A, these don’t need an external oscillator crystal.

I wanted to play with this and I thought the best way was to just do a little “Hello World” type blinky-led.

So, here was my code (note, I use MPLab and xc8):


/*
* File: main.c
* Author: ceneblock
*
* Created on November 21, 2017, 12:30 PM
*/

#define _XTAL_FREQ 16000000UL

// CONFIG1
#pragma config FOSC = INTOSCIO // Oscillator Selection bits (INTOSCIO oscillator: I/O function on RA6/OSC2/CLKOUT pin, I/O function on RA7/OSC1/CLKIN)
#pragma config WDTE = ON // Watchdog Timer Enable bit (WDT enabled)
#pragma config PWRTE = OFF // Power-up Timer Enable bit (PWRT disabled)
#pragma config MCLRE = ON // RE3/MCLR Pin Function Select bit (RE3/MCLR pin function is MCLR)
#pragma config CP = OFF // Code Protection bit (Program memory code protection is disabled)
#pragma config BOREN = ON // Brown-out Reset Selection bits (BOR enabled)
#pragma config BORV = 19 // Brown-out Reset Voltage selection bit (Brown-out Reset Voltage (VBOR) set to 1.9 V nominal)
#pragma config PLLEN = ON // INTOSC PLL Enable bit (INTOSC Frequency is 16MHz (32x))

// CONFIG2
#pragma config VCAPEN = DIS // Voltage Regulator Capacitor Enable bits (All VCAP pin functions are disabled)

// #pragma config statements should precede project file includes.
// Use project enums instead of #define for ON and OFF.

#include

void main(void) {
TRISB = 0x00;
while(1)
{
RB0 = 1; // LED ON
__delay_ms(1000); // 1 Second Delay
RB0 = 0; // LED OFF
__delay_ms(1000); // 1 Second Delay
}

return;
}

The configuration bits I got from the IDE’s configuration bit configuration window (window -> configuration windows -> configuration bits).

So, ready to give it a go, I dropped it into my ZIF programmer, hooked up my PICKit 3 and everything went as it should! No Errors!

However, as I was watching the led flash on and off, I noticed that it wasn’t on for one second and off for another.

I tried adjusting the times in __delay_ms(), but that didn’t help. So I hopped on IRC and asked on freenode’s ##Electronics room. One of the users suggested that my problem was that I wasn’t clearing the watch dog timer before the delays.

So, I added in the following code:

asm("CLRWDT");

and now everything worked. That said, I could use this method or as the user suggested, I could extend the time before the watchdog timer resets. I might try that later, but this works.

This wasn’t my final solution though, while the inline assembly is just fine, I decided for this simple project I should just disable the watchdog timer all together, so changing the configuration bits:


#pragma config WDTE = OFF // Watchdog Timer Enable bit (WDT disabled)

Now everything is fine and dandy.

I’ll make a bigger project eventually, but for just right now, this is more than fine.

Posted in Engineering | Tagged , , , , | Leave a comment

6-chip BASIC computer with Z8671

Taken from CPUShack (http://www.cpushack.com/2010/10/15/zilog-the-first-decade-z80-z8-and-the-z8000/)
I’ve had some Z8671 chips for a while and I wanted to build a BASIC computer (get it?).

I just wanted it up and running (for now) and I came across this Hackaday Post and related GitHub. I learned from the eevlog forum that there is an appnote, but despite it now being the third result on Google, I had trouble finding it at first. For future people, here is a link to it.

My first try was to follow the picture from SmallRoomLabs to get it up and running, and….nothing. At best, I got garbage (when using a 4MHz crystal) and more often than not, I got nothing.

So I put the project away and came back to it with similar failures.

The past few weeks; however, I really wanted to get it up and going. What did I do? I outsourced it to one of my lab mates. He was able to consistently get garbage out to the monitor. We tried different crystals, but never got it up and going.

The other night; however, I found the app note and saw the example setup listed. I forwarded it to my lab mate and he apparently had already found it, but wasn’t getting good results (he later said that he ignored the example setup).

Being aware of this, I decided to try to build it according to spec and go from there. One of the things that is in the sheet and (apparently) is extremely important is the crystal speed. It

    needs

to be 7.3728MHz. 4Mhz and 8MHz just don’t work.

I ordered the correct crystal from Arrow ( click here to see why I’m using them now) and it just came in.

I put in the correct crystal, adjusted my BAUD rate and there we go!

With that, I tried to play with some of the configuration.

I swapped out the crystal, but that took me back a few steps.

I adjusted the resistor location and that got me mixed results. I found out the best results were to have a pull-up resistor on P1_0 (pin 21) and that’s the minimum that you need.

I also didn’t have a 22pf capacitor, so using my capacitor rules, I put a 20 and 2pf in parallel. With it up and running, I tried to reduce the capacitance needed and found that I can just use it with 20pf.

For UART, I’m using an FTDI adapter that provides power and Serial I/O. The RX on the FTDI is going to the SO on the Z8671 (pin 4) and likewise the TX is going to SI (pin 5).

So, let’s do a chip count and the relevant pins:

  1. FTDI
    • Vcc -> Z8671 Vcc (Pin 1)
    • Vcc -> 1K Ohm Resistor
    • GND -> Z8671 GND (Pin 11)
    • GND -> 20pf
    • GND -> 20pf
    • TX -> Z8671 SI (pin 5)
    • RX -> Z8671 SO (pin 4)
  2. 20pf
    • pin 1 -> GND
    • pin 2 -> 7.3728MHz Crystal
  3. 20pf (yes 2)
    • pin 1 -> GND
    • pin 2 -> 7.3728MHz Crystal
  4. 7.3628MHz Crystal
    • pin 1 -> Z8671 XTAL1 (pin 3)
    • pin 1 -> 20pf
    • pin 2 -> Z8671 XTAL2 (pin 2)
    • pin 2 -> 20pf (the other one)
  5. Z8671
    • Vcc (pin 1) -> FTDI Vcc
    • XTAL 2 (pin 2) -> 7.3628 MHz Crystal
    • XTAL 2 (pin 2) -> 20pf (the other one)
    • XTAL 1 (pin 3) -> 7.3628 MHz Crystal
    • XTAL 1 (pin 3) -> 20pf
    • P1_0 (pin 21) -> 1K Ohm resistor
  6. 1 KOhm Resistor
    • pin 1 -> FTDI Vcc
    • pin 2 -> Z8671 P1_0 (pin 21)

I could have just drawn a diagram, but on page 4 of the application note, you have one there for you. If you want reset, then just put a jumper from pin 6 -> Ground to turn it off and disconnect (and connect to Vcc) to turn it on.

I feel kinda of stupid now that I see how easy this is, but that’s the way it goes. 🙂

I”ll probably hook this up to another uC so that I can have a pocket basic computer (similar to here ), but that is to be determined.

Posted in Engineering | Tagged , | Leave a comment

Quickie Problem with STM32F103C8T6

I just ran into a quick problem with my STM32F103C8T6 that I got to play with. Whenever I tried to upload code, I kept getting this error:


Error in initializing ST-Link device. Reason: No device found on target.

I know that I had my settings correct (using an ST-Link, SWD, and outputting to Intel hex format) and that the device was still alive since it was running other code; however, even when trying with a different programmer and reverifying the pins, nothing happened.

To fix this, I simply held down the reset button and as I hit upload, I let the button go.

This seems to have fixed the problem, but it is very strange. Anyway, I hope that someone else can benefit from this..

Posted in Engineering | Tagged , , , | Leave a comment

Generic Action Cam Initial Impressions (iSpring)

From the amazon page

I picked up this camera off Amazon for $40 and wanted to use it as a cheap dash cam.

Unfortunately, that doesn’t seem to be possible (at least not easily, I’ll post a couple hacking posts later).

So let’s just review this as a camera.

First off, mine is branded as Gaminol and not iSpring, so these things must be rather generic…It is a small thing; however, and fits in the palm of the hand. Although I don’t own a GoPro, I think it is the same size.

The video quality, shown below both night and day on my bike inside the waterproof case, is meh. Despite it being at 1080p @ 60fps, it looks like garbage at night. I didn’t even need to blur out the license plates. So, if you’re in a hit and run, then good luck.

The same applies for the day, but it certainly looks nicer.

I’m not going to be too hard on the video quality, because it isn’t meant to be an expensive camera. It isn’t supposed to replace your Canon, Nikon, or Sony cameras, this is just a nifty little trinket.

There is a streaming app for it called iSmart DV (have you noticed that nothing brand or name-wise matches up yet?). It is bare bones and does what you expect it to; however, the battery indicator in the app is fake. I didn’t test the wifi indicator, but I imagine it is fake as well..

There are still some other problems though, the biggest is the build quality. It feels cheap — like if you drop it, then it would shatter.

On my camera, the volume buttons are put on upside down. The only reason why I know this is because the “volume down” button is supposed to turn on WiFi. The screen is way too bright and I didn’t see an option to reduce the brightness. I suppose I could put a resistor in there or pwm the back light, but it isn’t worth the effort.

So there was not a lot of care put in the the design and manufacture of the device…

When running the camera, it gets hot. Like REALLY HOT. This is going to be a problem for battery life and longevity. In fact, the battery life when running with the screen on is less than an hour, which is unacceptable for an action camera that is supposed to be taken camping, hiking, swimming, and so on.

For the price that I paid, it think it is just okay; however, I would not recommend paying a penny more. If you want a numerical review then I’d give it a 5/10 because of the heat and poor battery life.

Posted in Photography, Reviews | Tagged , , | Leave a comment

Hey everyone, I plan on doing some reviews of various gadgets that I get from a “what is this and should I get it” type of stance.

As a tease, I have a knock-off GoPro that I’ll do first; however, I plan for most of the reviews to be for music.

Posted on by ceneblock | Leave a comment

XBox 360 Chatpad Hacking

So I was watching an old episode of The Ben Heck Show on creating a pocket BASIC computer and in it, he mentioned using an XBox 360 Chatpad as the keyboard and reprogramming it as a serial keyboard instead.

Interested, I decided to order one and instead of the expected PIC16, I was greeted by a Microsoft X814364-001 and looking online, it seems that I’m not the only one with this problem; however, I did map out the pins and for the ICSP and they match up to the as expected to the Microsoft chip. My suspicion is that Microsoft had Microchip just mask the PIC and that they are the same device.

That said, another person tried to flash it over and seem to have failed noting that:


I can’t detect the pic and if i force it to flash the stuff (just select Pic16f883) it flashes but when it wants to verify there’s everything wrong and the pad works on the xbox like before so I guess it didn’t work

In that case, the user seems to have purchased a replacement PIC16, but I want to give it a try as well. My PicKit3 is sitting at the school, so I don’t have access to it to actually flash it right now; however, if it does work, then expect an update.

I’ve left some helpful links down below for those who want to modify their chatpads as well.

Links:
Ben Heck’s Original Post
PIC16F883 Sheet
Chatpad Pinout (really useful)

Posted in Engineering | Tagged , , , | 4 Comments

Writing an IRC bot

Some students wanted me to get involved with GHOULL again, and I agreed to. However, these guys will be in charge and I’ll just be lecturing..

Anyway, I decided we should have an IRC channel (freenode #GHOULL) and if we’re going to do that, then we should have a bot!

I found this guide for basic bot writing and wrote my own which can be found here.

It’s a very basic an primitive bot and needs a lot of improvements; however, I did want to mention some notes:

  1. As mentioned in the README, you’ll php5-sockets (or whatever version of php you’re using)
  2. Don’t try to send a lot of data, you’ll get throttled and then messages will be lost. You can get around this by giving your bot a voice with the following command:

    /msg ChanServ #GHOULL add GHOULL_bot +V
  3. All commands end with a `:` so

    write_socket($socket, "PRIVMSG #GHOULL: my text");

    This is important otherwise things will get messed up.
  4. sqlite and sqlie3 are not the same thing and the APIs are not compatible.

Those are the three big challenges that I’ve faced so far; however, I’m sure there will be more and I’ll try to remember to put them in the README.

The code is a little messy and uncommented; however, I tried to make everything as basic as I could. The hard stuff is in scripts/*.php as that deals with interacting with sqlite.

Posted in Computer Science | Tagged , , | Leave a comment

Getting Started with the BeagleBone PocketBeagle

Arrow current has a sale where when you spend over $20, you get upgraded to overnight shipping for free!

I saw this through an e-mail through them and I had just heard about the Pocket Beagle so I decided I’d order it.

I got that and some other goodies that I may write about later; however, there is not good documentation on how to get the device set up.

Having a BeagleBone Black, I figured it’d be plug-and-play; however, I was way wrong.


My first instinct was to just plug it in and I did and nothing happened. I’ve had problems with Ethernet over USB before, but I was expecting that since I was using Network Manager that everything would be somewhat “automagic”; however, nothing happened at all….well, that’s a lie. The device got really hot after being plugged in. I started to get worried that I had cooked the device by accident.

Confused and frustrated, I tried searching and there short reviews of the device, but nothing that really stood out. The getting started guide shows it working out of the box (but that guide pictures a Black..) so I was really thinking that I had a defective board.

There was a very short quickstart guide written on the cardboard backing of the package. So if you threw that away and this was your first device, then you’d be totally screwed as there isn’t anything yet. I may or may not have been that guy. 🙂

So enough ranting!


To get everything started, let’s get a list of what we’ll need:

  1. A minimum of 4GB MicroSD card
  2. A MicroUSB Cable
  3. A way to write data to the MicroSD card (This can be a USB adapter or a MicroUSB to SD for your computer or you might even have a microSD card on your laptop)

Now, these instructions are for Linux, but in all honesty they’re applicable to other OS as well.

Downloading an Image

First thing that we’ll do is get the latest image from beaglebone. Look for one that supports our device (in this case PocketBeagle). I have a copy that is recent as of the time or writing available for download; however, it is big and will take some time to download.

Once this is done, we’ll need to extract it. On Linux, I’ll be using unxz; however, I think xz files can be extracted on Windows and Mac using 7zip.


unxz ./bone-debian-9.1-iot-armhf-2017-09-21-4gb.img.xz

Burning our Image

With our image extracted, we’ll need to burn it to a microSD card. For Linux, I use dd. To use this, first we’ll need to know what drive the micro SD card is:


sudo fdisk -l

Disk /dev/sda: 298.1 GiB, 320072933376 bytes, 625142448 sectors
Units: sectors of 1 * 512 = 512 bytes
Sector size (logical/physical): 512 bytes / 512 bytes
I/O size (minimum/optimal): 512 bytes / 512 bytes
Disklabel type: dos
Disk identifier: 0x0002b49f

Device Boot Start End Sectors Size Id Type
/dev/sda1 * 2048 576909311 576907264 275.1G 83 Linux
/dev/sda2 576909312 625141759 48232448 23G 82 Linux swap / Solaris

Disk /dev/sdb: 16 GiB, 17179869184 bytes, 33554432 sectors
Units: sectors of 1 * 512 = 512 bytes
Sector size (logical/physical): 512 bytes / 8192 bytes
I/O size (minimum/optimal): 8192 bytes / 131072 bytes

You’ll then see something like /dev/sdX or /dev/mmcX (where X is a number or letter) and it’s size. If you see /dev/sdX then you’ll want to use /dev/sdX and not /dev/sdX1 or something, likewise, if you see /dev/mmcX then you’ll want to use /dev/mmcX and not /dev/mmcXp1.

This should be obvious, because if you look at /dev/sda in the example above, you’ll see that /dev/sda1 is underneath /dev/sda. Hopefully that isn’t too confusing..

Now to actually burn it:


sudo dd if=bone-debian-9.1-iot-armhf-2017-09-21-4gb.img of=/dev/sdX status=progress

This will take a while, but now that DD will show you progress so you don’t know if something has randomly died and you don’t know (and it beats sending USR1 to the process).

Note bene:

Luckily, if you’re using Windows, then there is Rufus and a helpful guide for Windows for burning Ubuntu to a USB disk. The only thing you’ll need to do differently is select the beaglebone .img instead of the Ubuntu one.

There are other guides for burning the image on Ubuntu and Mac if you found that all confusing.

Booting the device

With the image burned, you’ll now take the microSD card and insert it into a unplugged PocketBeagle.

With it inserted, you can now plug in your MicroUSB cable to the board and into your computer.

It’ll eventually boot and everything is finished once you can see a new drive and can follow the getting started guide

Miscellaneous

If you have issues with networking over USB, then try the following on Linux:

sudo ifup usb0 192.168.7.1
#Additional configuration may be needed, check your distro's documentation for further information.

For SSH:

User: debian
Pass: temppwd

Posted in Computer Science, Engineering | Tagged , , | Leave a comment