by Zacharias @ http://inexactitu.de . March 17, 2011 . 12:20PM
1. The test-and-set (TS) instruction and the swap instruction are part of the hardware support for process synchronization contained in modern CPUs.
True. Since test-and-set solutions rely on condition codes (stored in the PSW), the processor reads the previous instruction.
2. Although the spin-lock solution and the Peterson algorithm provide busy-waiting solutions to the critical section problem, only the spin-lock solution controls the order of entry for waiting processes.
False. Spin-locks don’t control order. Peterson’s is a busy-wait in software.
3. In class we discussed a bounded-waiting solution to the critical section problem using test-and-set. This solution works because a process exiting the critical section transferees control of entry to the next process in an ordered list awaiting entry.
True. Bounded-waiting Mutual Exclusion with TestandSet().
4. In the single producer – single consumer, multi-slot budder problem, the critical section is the manipulation of the count of the number of filled cells.
True.
5. The implementation of the operations P & V on binary semaphores only require block/wakeup, while these same operations on general semaphores require block/wakeup and counting.
False. We want this to happen at their own rate. We are looking at the count value.
6. When semaphores and semaphore operations are implemented in a non-preeemmptable kernel, we will not have any busy waiting.
True. We need to do this if the semaphore is implemented in user-space.
7. In the multiple producer, multiple consumer problem with a multi-slot buffer, we require mutual exclusion of the ‘deposit’ and ‘take’ to ensure proper order of entry.
False. This solution doesn’t provide proper order. This only provides only the ability to feed the consumer empty spaces and the consumer full spaces.
8. How many philosophers may eat simultaneously in the Dining Philosophers problem with only 4 philosophers?
Two. Draw a picture if this isn’t obvious.
9. The readers-writers problem discussed in class…
c… required that no reader will be kept waiting unless a writer has already obtained permission to use the shared database.
10. A monitor wait() operation always blocks.
True. Waiting signal can be implemented using semaphores. A monitor wait using a binary semaphore initialized to 0, whenever a process waits, it’s guaranteed to block.
Questions about how semaphores are implemented and conditions are implemented. This is very important to synchronization.
by Zacharias @ http://inexactitu.de . February 24, 2011 . 1:06PM
1. Circle the following components of program state that are shared across threads in a multi-threaded process:
a. Register Values
b. Heap memory
c. Global values
d. Stack memory
e. Open Files
a, c, e.
Registers are part of the virtual CPU, as are stack and thread-private memory.
2. A good solution to the cirtical section problem included the condition of pregress, where each process waiting for entry to the critical section will be granted entry in order of arrival.
False.
Bounded waiting can be granted only after a certain amount of tried.
3. With user-level threads, thread control blocks are stored in memoery outside the kernel and managed in user mode.
True.
Everything that happens with management is done at user-level. The kernel doesn’t know about them. Only the process can manipulate them.
4. In an operating system that can schedule kernal level threads, there may be two independent thread scheduling mechanisms.
True.
There could be a user-level thread management system as well as the kernel’s.
5. A course-gained atomic action is one in which the statements in the critical section for a data item are designed so that the critical section cannot be executed concurrently with itself or other cirical sections for that data item.
True.
They are functionally indivisible. This is the def. of the critical path setion.
6. A thread pool is a collection of kernel threads, which can be created at process startup, reducing the real-time overhead of creating new application threads.
False.
When a user process creates a new thread, we’d like to map it to an existing kernel thread. The idea of pools is to have the threads already created, and it will map to a kernal thread. There is a delay involved with creating additional threads at the kernel level for user-level threads to map to.
7. Race conditions are possible in concurrent programs because of the unpredictable interleaving of atomic actions in the programs.
True.
Solve this and get a turing prize. Inturrupts aren’t serviced during atomic actions, for example.
8. In multithreaded programs, the kernel can inform an application about certain events using a proceadure known as an ______
upcall.
This sends a signal to the thread library to tell it to, for example, run another thread while that thread is locked. It is like a reverse
Not a signal, as they can/are be used for inter-process communication instead of an upcall, which is specific to threading. Also, the kernal can throw signals but not upcalls. The user-level thread library can receive signals, though.
9. Signals are delivered to a process, notifying it of the occurrence of an event, and synchronous signals are delivered to the thread running when the signal occurs.
True.
Async signals can be handled by any running thread.
Sync signals are in response to a failure (hardware-based): These are delivered to a running thread.
10. A successful call to an exec() function has a return to the calling program of a value 0, indicating no error.
False.
There is nobody to return to if you exec, exec overlays the running process (including, pid and other things, like file pointers)
by Zacharias @ http://inexactitu.de . November 22, 2010 . 5:45PM
I’ve been working on implementations of various Java programs and the like in my Data Structures and Algorithms class, and since I really like how this turned out, I figured it’d be worth sharing.
This is the first time I’ve used multiple buttons and the default UI layout – I think it’d be nice to share an implementation of it. This program also has a delightful side effect of showing how close heap sort works to O(n log(n)). Code follows:
main.class
// thanks to ping for heapsorter as well as rolf's colorbox
// Heapsort was originally published by J.W.J. Williams as
// Algorithm 232 in the journal Communications of the ACM [Wil 64].
package lab10;
public class Main{
private static int[] a;
private static int n;
static int[] w1;
static int w = 2000;
static ColorBox b1 = new ColorBox(w);
public static void main(String[] args) {
// int w = 600;
// ColorBox b1 = new ColorBox(w);
}
static int dh = 0;
static int sc = 0;
public static void sort(int[] a0)
{
a=a0;
n=a.length;
heapsort();
}
private static void heapsort()
{
buildheap();
while (n>1)
{
n--;
swap (0, n);
downheap (0);
}
}
private static void buildheap()
{
for (int v=n/2-1; v>=0; v--)
downheap (v);
}
private static void downheap(int v)
{
int k = 2*v+1; //k = root's children
while (k<n)
{
if (k+1<n)
if (a[k+1]>a[k]) k++;
if (a[v]>=a[k]){
return;
}
swap(v, k);
v=k;
k=2*v+1;
dh++;
}
}
private static void swap(int i, int j)
{
int t=a[i];
a[i]=a[j];
a[j]=t;
sc++;
}
}
/*
* Okay, these are the numbers I'm getting for the swaps needed for each job
* When I say "should be" number x, I'm speaking of the following formula for
* the O(n logn) amount of swaps required...
*
* x | x is a side of the array
* swaps = x^2 * lb(x^2)
* where lb is binary log.
*
* Since big O notation reperesents an >upper< bound after a certain nominal value
* none of the trials should be larger than O(n log n).
*
*
* size: 100
* swaps: 123891
* Should be ~130k
* http://www.wolframalpha.com/input/?i=100%5E2+%2A+lb%28100%5E2%29
*
* size: 200
* swaps: 575216
* Should be about ~611k swaps
* http://www.wolframalpha.com/input/?i=200%5E2+%2A+lb%28200%5E2%29
*
* size: 300
* swaps: 1399854
* Should be about ~ 1.4 million swaps
* http://www.wolframalpha.com/input/?i=300%5E2+%2A+lb%28300%5E2%29
*
* size: 400
* swaps: 2,619,194
* Should be about 2.7 million swaps
* http://www.wolframalpha.com/input/?i=400%5E2+%2A+lb%28400%5E2%29
*
* size: 500
* swaps: 4,248,474
* Should be ~ 4.4 million swaps
* http://www.wolframalpha.com/input/?i=500%5E2+%2A+lb%28500%5E2%29
*
* size: 1000
* swaps: 18,986,697
* Should be 19 million swaps
* http://www.wolframalpha.com/input/?i=1000%5E2+%2A+lb%281000%5E2%29
*
* size: 1500
* swaps: 45,343,618
* should be about ~ 47 million swaps
* http://www.wolframalpha.com/input/?i=1500%5E2+%2A+lb%281500%5E2%29
*
* size: 2000
* swaps: 83914749
* should be about ~ 87 million
* http://www.wolframalpha.com/input/?i=2000%5E2+%2A+lb%282000%5E2%29
*
*/
next, we have the ColorBox method provided by the Professor and it includes my added buttons. This is the first time I’ve ever implemented multiple buttons on the UI. I know, minor victory. But that, to me, is really what programming is all about – little victories until one day, bam, you are half competent.
ColorBox.class
/*
* ColorBox.java
* Created on November 1, 2007, 11:08 AM
* by Rolf Lakaemper
* Zach added the buttons and actions
*/
package lab10;
import java.awt.*;
import java.awt.event.ActionEvent;
import java.awt.event.ActionListener;
import javax.swing.*;
public class ColorBox extends JPanel implements ActionListener{
private static final int DEFAULTSIZE = 400;
private int []colors;
private int size;
//zach's buttons
public JButton j1;
public JButton j2;
public JButton j3;
/* Creates a new instance of ColorBox */
public ColorBox(int inSize) {
size = inSize;
colors = new int[size*size];
initRandom();
// Visuals
setPreferredSize(new Dimension(size,size));
JFrame frame = new JFrame("ColorBox");
add(j1 = new JButton("sort"));
add(j2 = new JButton("randomize"));
add(j3 = new JButton("downheaps and swaps"));
j1.addActionListener(new ActionListener() {
public void actionPerformed(ActionEvent ae) {
Main.w1 = Main.b1.getColorValues();
Main.sort(Main.w1);
Main.b1.setColorValues(Main.w1);}
});
j2.addActionListener(this);
j3.addActionListener(new ActionListener() {
public void actionPerformed(ActionEvent aw) {
System.out.println("size: " + size);
System.out.println("downheaps: " + Main.dh);
System.out.println("swaps: " + Main.sc);}
});
frame.setDefaultCloseOperation(frame.EXIT_ON_CLOSE);
frame.getContentPane().add(this);
frame.pack();
frame.setVisible(true);
}
/* Creates a new instance of ColorBox */
public ColorBox() {
this(DEFAULTSIZE);
}
public void initRandom(){
for (int i=0;i<colors.length;i++){
colors[i]=(int)(Math.floor(Math.random()*256));
}
}
public int[] getColorValues(){
// return a COPY of colors, keeps colors private
int []c=new int[colors.length];
System.arraycopy(colors,0,c,0,colors.length);
return(c);
}
public void setColorValues(int []c){
if (c.length!=colors.length){
System.out.println("Error, arrays of different size.");
}
else{
System.arraycopy(c,0,colors,0,colors.length);
}
repaint();
return;
}
public void paintComponent(Graphics g){
int count = 0;
for (int row=0;row<size;row++){
for (int r=row;r>=0;r--){
g.setColor(new Color(colors[count],0,0));
count++;
g.drawLine(row-r,r,row-r,r);
}
}
for (int col=1;col<size;col++){
for (int c=col;c<size;c++){
g.setColor(new Color(colors[count],0,0));
count++;
g.drawLine(c,size-c+col-1,c,size-c+col-1);
}
}
}
public static void main(String []args){
ColorBox cb = new ColorBox(500);
int []c=cb.getColorValues();
java.util.Arrays.sort(c);
cb.setColorValues(c);
}
public void actionPerformed(ActionEvent e) {
// randomize button
initRandom();
repaint();
// get ready for another run by setting counters to zero
// downheap set back to zero
Main.dh = 0;
// swap count set back to zero
Main.sc = 0;
// Junk drawer from other implementations/versions...
// long time1 = System.currentTimeMillis();
// Main.w1 = Main.b1.getColorValues();
// Main.sort(Main.w1);
// Main.b1.setColorValues(Main.w1);
// long time2 = System.currentTimeMillis();
// System.out.println(time2-time1);
}
}
by Zacharias @ http://inexactitu.de . November 11, 2010 . 11:21AM
remember that depending on your particular architecture, you can get some really strange results. As an example, on my macbook pro, I ran an application that polls the counter and asks it how many cycles it’s had since it was powered on. Thats how the spec works, anyways. I was getting some strange results I couldn’t explain, and it turns out every time rtdsc() was called, it was asking the other processor core.
Which wasn’t on when polled.
This meant that every other time it was asked, it was waking up a processor to say, eh, I’ve been awake for 287/24000000000 of a second.
I re-ran the results connected to a Unix server and got the right results.
So it goes. Click on the image below and experience the magic for yourself.
by Zacharias @ http://inexactitu.de . November 9, 2010 . 1:51PM
In hopes of recalling elementary string functions in C, I’m jotting this down with comments.
It makes a lot of sense to really understand library functions before you go and try to re-make Doom.
int strcmp (char *s, char *t)
{
for ( ; *s == *t; s++, t++)
if (*s == '\0')
return 0;
return *s - *t;
}
So first we look at the input: we have two char pointers. Since we don’t have to change either s or t in order to compare them, pointers are the most efficient way to refer to them.
There is three possible input situations, first s could be greater than t, t could be larger, or they could be the same. Implicitly, we are comparing s to t. The for loop at the first line is made to go until s and t become not equal or to report they’re equal if the end of line \0 enters.
Otherwise, the difference between the two strings are reported as the result. This will be positive if s is longer than t, or negative if t us larger.
Therefore we have a discrete output for each of the three conditions. Note that since this comparison (in the for loop) is done until the end of similarity, the worst-case order of magnitude for this function is O(n). All other cases are O(1).
by Zacharias @ http://inexactitu.de . October 12, 2010 . 7:28PM
I’m working on ways to trick myself to do code more often than my twice-weekly stay-up-late routine by making it more fun. To that end, I figured blogging about code will be helpful to that end. As a Computer Science major, I’m expected to write a ton of code and my antipathy to the process is only eclipsed bt my ability to procrastinate starting. As an example, I’m just posting the first .java files I have laying around. So, here it is:
colortest.java
import javax.swing.*;
import java.awt.event.*;</code>
public class Colortest
extends JFrame
{
public static void main(String[] args)
{
new Colortest(); // create Window
}
private Colortest()
{
super ("Colortest");
addWindowListener( // don't care about this
new WindowAdapter(){ // it only closes the application
public void windowClosing(WindowEvent event) // when you close
{System.exit(0);} // the window
}
);
setContentPane(new ColorPanel()); // the actual drawing pane
pack(); // organize, size etc.
setVisible(true); // show the window to the world !
}
}
colorpanel.java
import java.awt.*;
public class ColorPanel extends javax.swing.JPanel
{
// Fields ------------------------------------------------------------------
private final int numberOfRows = 32;
private final int numberOfColumns = 32;
private final int rectSize = 16;
private Color[][] colorField; </code>
// Methods -----------------------------------------------------------------
public ColorPanel() {
initColorArray(numberOfRows, numberOfColumns);
setPreferredSize(new Dimension(rectSize*numberOfColumns, rectSize*numberOfRows));
}
protected void paintComponent(Graphics g)
{
// get array-size
int rows = colorField.length; // number of rows
int columns = colorField[0].length; // number of columns
for (int r=0;r < rows; r++){
for (int c=0;c < columns; c++){
g.setColor(colorField[r]); // color for next rectangle
int positionX = c * rectSize; // position
int positionY = r * rectSize;
g.fillRect(positionX, positionY, rectSize, rectSize);
}
}
}
//vvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvv
/*
* initColorArray
* initialize 2 dimensional array 'colorField'
*/
private void initColorArray(int rows, int columns)
{
// A 2 dimensional array is an array of arrays
// hence it could be defined row-wise with different
// column - lengths ! However, the most usual case is a
// rectangular shape, i.e. every column has the same dimension.
// These arrays could be declared in a less complicated way
// by new arrayname[sizeRow][sizeCol].
// But to make clear, that we really deal with nested arrays we define
// them beyond in a more universal way.
colorField = new Color[rows][];
for (int i = 0; i < rows; i++){
colorField[i] = new Color[columns]; // every column with same size here
}
// now define different colors
for (int r=0; r < rows; r++){
for (int c = 0; c < columns; c++){
int red = (int)(255.0 * r / rows); // compute portions of red
int green = (int)(255.0 * c / columns); // and green (max = 255)
int blue = 0; // no blue today
colorField[r]1= new Color(red, green, blue);
}
}
}
//^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
}
by Zacharias @ http://inexactitu.de . October 12, 2010 . 6:33PM
I recently gave this presentation in the lab I work in. I was tasked to determine which solutions (locally connected to a very fast server platform) we could use to back up the myriad machines we use for Bioinformatic research.
Anyhoos, here’s the pdf . Enjoy.
by Zacharias @ http://inexactitu.de . May 19, 2010 . 10:43PM
Champions that will soon be retired, these are the tracks I overindulged in too many times on my iPod while listening to my expensive Shure SE110s, which I promptly lost in January; then, on some cheapo sony earbuds. About 3 weeks later, back into the sure grasp of Shure SE115s (which sound just as good and Jenny claims have a better fit.
The list, then.
Chamption Tracks
- C.R.E.A.M – Wu Tang Clan – from the Enter the Magical Mystery Chambers mashup. (free to download, too!)
- Just for Tonight – Groove Armada
- Paper Romance – Groove Armada
- Oil – MC Paul Barman
Albums
- Lock and Load – Denis Leary
- The Weather – Busdriver & Radioinactive with Daedelus
- Full Buck Moon Kaboom: The Mixtape -MC Paul Barman
- Black Light – Groove Armada
Podcasts
A couple of notes: MCPB has a new full-length album, the first since I was in goddamned high school. The Full Buck Moon Kaboom included some amazingly creative tracks, such as the hip-hop biography of Weird Al and the first half of the laws of power. So, I have high hopes for tracks I’ve heard the demo versions of and the MF Doom-cut jawns as well.
cheers.
by Zacharias @ http://inexactitu.de . April 6, 2010 . 1:39PM
If you can’t tell from the reaction below, I really enjoyed the talk and the multidisciplinary nature of high-level datacenter work. Also, datacenter is a word, screw you spellcheckers. Since the speaker didn’t speak on a specific project or challenge his company had, this is more general than usual. Something I realized later is that some of the biggest companies in IT happen to be German. SAP, a company who I also saw speak in this class this semester happened to be boring. SAP sent “campus representatives” instead of a working IT pro, which probably explains it.
Mr. Kleylein is a Vice President in charge of Siemens Medical’s datacenter operations. Mr. Kleylein gave a comprehensive look at the workings of a datacenter, instead of focusing on simply the systems in place. It seems that with many of our speakers, it would seem that the larger the responsibility of a position, the more “wide” a skillset needs to be. No students in our program would need to worry about physical security or engineering cooling systems, but in order to be in a VP position, a wider skillset becomes necessary.
Some of the numbers were interesting: 22 robotic tape arrays, 780TB of storage, which seems low, actually, thats about 1500 drives, assuming an average of 500GB/drive. 99.998% uptime means about 10 minutes of downtime a year.
Layers of redundancy and physical security are oft-overlooked aspects of Systems Analysis and have been for years (Kevin Mitnick wrote on this in the excellent The Art Of Deception). Streamlining code, designing interfaces, and having a marketing scheme all come AFTER YOU SECURE YOUR DATA. HIPPA notwithstanding, many knowledge workers become pretty bored pretty fast without having data to knowledge work. It’d be delightful if in-house datacenters were ran this well in many companies, but somehow I doubt that many organizations have the expertise in engineering or as critical data as life-or-death health information.
Seeing a trend towards higher set points for cooling by hardware manufacturers is great from an ecology view, as well. While individual datacenters can and do everything they can to reduce the environmental (carbon) impact of the large amounts of energy usage, efforts on the chip die can instantly make every datacenter in the country 5% more efficient by requiring 5% less energy to operate and cool. Even low-tech can help (blanking panels) when it comes to reducing the carbon footprint of a datacenter.
I felt like I had a good paradigm stretch when I saw how much engineering goes into the datacenter even when you don’t talk about the blades.
by Zacharias @ http://inexactitu.de . April 3, 2010 . 11:26PM
This assignment was to find and answer some questions regarding a project management tool. Even though I’m currently using Basecamp for a final group project, thats because of the cat-herding nature of having as-smart-as-you people in the group. Since the web is the new standard operating system, it made things easier than to find a tool that works for OS X, Linux, and Windows while seamlessly synchronizing. So, while I don’t think its the best. program. evar. it still is worthwhile.
The second portion of the assignment was to answer (in essay form) some questions regarding the process that Mariott used to standardize the bedding in the chains they run. Exciting!
Source be found here. Cheers.
I.
Basecamp (http://basecamphq.com) is a project created by the web design firm-accidental web application developer 37signals. 37 (as I’ll be referring to them through this assignment) tells the story of Basecamp being an internally developed to-do list for the firm’s growing business turns out to be just so good, that the firm decides to develop web applications.
The main selling points of Basecamp are: Ease of use and setup, security (this is true, for the wrong reasons, I’m afraid), remote access (all access is remote, isn’t it?), and a people-centric design. Basecamp is a web-based tool. All interactions are done within a web browser. Instead of starting from a product like MS Project, it’s better to start from a simple to-do list and add. The reason behind this was explained by one of 37′s founders as being the result of features being “guilty before proven useful.” PC Magazine touted the extensibility while making the point of some common collaboration feature’s absence: specifically chat, whiteboards, and file sharing (37 has a separate application for whiteboarding).
37 claims a disparate amount of customers, including a t-shirt e-business, wedding planners, “brand designers” (in quotes because I think that may be a made-up job), as well as larger businesses (usually a department or two, from what I gather). Basecamp was originally an application for web-based and design businesses, and although you’ll find allusions to other firms (manufacturing) knowledge work is the lion’s share of 37′s client base. 37′s other products, specifically the internal chat system called Campfire, have large blogs as clients.
Four reasons that I’d consider Basecamp: flexible pricing (which starts at $19.95/month, dead simple web interface means less training time for temporary/contract work or interns, Having an application hosted elsewhere would probably equate to higher uptime (or a waste, depending on a company’s IT infrastructure), and finally the lack of complexity would (hopefully) equate less time playing with pencils and more time writing homework.
* Information taken, unless denoted, from 37signal’s website, basecamphq.com and its press kit.
II.
“the team implemented several project management techniques, the most important being communication”
Oh, really? That’s project management?
Three factors need to be considered for project management: scope, time and cost. In regards to all three of these factors, the PMO (Project Management Office) for Marriot had unique challenges. The scope of the project involved over half a million beds across ten different brands. The time was more ambiguous – there were problems of deployment, logistical challenges brought on by offshore manufacturers needing longer lead times. Adding to the ambiguity was also cost, as the brands varied from low scale to luxury. Price performance would be needed at all levels in order to allow Marriot to remain competitive.
As mentioned earlier, the challenges of lead time by offshore production put pressure to start orders as early as possible. The problem was that without firm production numbers (for each of the ~1800 different pieces needed) cost couldn’t be determined. Another challenge was the multilingual nature of domestic and foreign employees who would be “deploying” the product (via a making-bed process that I didn’t see an E-R diagram attached for). Visual, non-lingual training material was produced to smooth out any transitions that would be needed without the expense and trouble of translation.
Factors that lead to success in this deployment using the project management process stem from the frequent communication between the PMO and everyone involved, including the offshore manufacturers, internal financiers, and brand owners. Both property managers (corporate franchisers) and franchisers needed education on the necessity of the change. MArriott using a database to smartly make orders and decide on a “standard” enterprise-wide probably saved a ton of money as well.
I think that the two most important skills used in the development of the new fit-and-finish of the guest rooms for Marriott were twofold: communication and effective selling to internal customers. First, we have not only the useful communications “hack” of creating non-lingual training material, there is the constant communications that the PMO and the internal customers, the stakeholders for brands and even individual hotels (at least one brand Marriott runs is exclusive to one hotel). Secondly, the effective two-way communication meant that when it was finally decided, buy-in was easy to get from these stakeholders who had “our” project in lieu of “their” project to revamp linens.
Newer Posts »
