Semaphore in NachOS

Semaphore

View more presentations from naniix21_3

Encriptacion

View more presentations from naniix21_3

TLB

Tlb

View more presentations from naniix21_3

RSA

Rsa

View more presentations from naniix21_3

LRU

LRU Cache is implemented through the LinkedHashMap class, this holds values with unique key.

Many methods which have been used in the following program are explained as follows.

LinkedHashMap
This class is also used for the implementing the doubly linked list which tracks either insertion or access order.



Map.Entry
Objects are valid only to the duration of the interation.



e.getKey()
Returns the key corresponding to the value.



This entry is for points in second opportunity.

FIFO and Queue

FIFO: Allows data exchange between processes, with a queue where read us and write bytes.

A queue holds a collection of data or elements and follows the FIFO rule.
The FIFO that means which data added first in the list, only that element can be removed or retrieved first from the list.

I explain how a queue is implemented.

LinkedList()
- This is the constructor of the LinkedList class. This class importing the java.util package.



removeFirst()
Removes and returns the first element of the list



removeLast()
Removes and returns the last element of the list.



list.isEmpty()
This method checks whether the list is empty or not.



remove()
This method used to remove the elements in the list in a specified sequence.




This entry is for points in second opportunity.

File System

In this part talk about File System

File System : Structured information stored in a storage unit.

To open the file:



The path can be absolute or relative.
Oflag: Opens the file for reading, writing or both.
Commands:
- O_RDONLY - Read
- O_WRONLY - Write
- O_RDWR - Both



To create a link to a file:





This entry is for points in second opportunity.

Clock

View more presentations from naniix21_3

This entry is for points in second opportunity.

Sockets in Nach0s

Sockets in nach0s

View more presentations from naniix21_3

This entry is for points in second opportunity.

Links
http://www.sce.umkc.edu/~cotterr/cs423_fs05/cs423_fs05_lectures.html

http://java.sun.com/docs/books/tutorial/networking/

Security

Security

View more presentations from naniix21_3

In this part we will discuss the security, this entry is for points in second opportunity.

Sockets

Sockets

View more presentations from naniix21_3

In this part we will discuss the sockets, this entry is for points in second opportunity.

Network.h

View more presentations from naniix21_3

Links where I information support:
http://cs.nyu.edu/~yap/classes/compsys2/nachos/x326.html
http://gift.sourceforge.net/docs/0.11.x/libgift/network_8h.html

NachOs OS Network

Nach os network

View more presentations from naniix21_3

In this part I Network.cc explained.

The Nachos III Theorical Part - 2

The Nachos III Theorical Part

NETWORKING

Nachos III Theorical Part

The Nachos III Theorical Part

security.

references:
 PDF Of the Coruña University
 wikipedia

Practical Part II

Practical Part II

Using the file system functions




and here's the video about the slides

On the video.

1- check for the DISK of nachos ( the simulated HDD).
2- use the nachos -f to force the format of the hdd and there's no hdd then nachOS create one.
3- nachos create a new DISK with 5000bytes of space
4- Enter in /nachos/code/machine/disk.cc and modify the magicsize if you want more space
5- use nachos -cp to copy the halt program into the nachos DISK
6- use nachos -l to see the content of the DISK in this case only the file ALTO
7- now use nachos -x to execute  the program from nachos DISK
8- now copy one file to the DISK
9- use nachos -p to print the content of the file
10- that's all.

Java Stacks

Well we all know what batteries are in Java, but explain a little as we will need in the implementation of Nachos.

The first is to define the stack, ie, instantiate the class Stack.

Stack pila = new Stack();

When using a string, we mean what are strings.
The method that inserts elements in the stack is. Push (). This method will receive as a parameter the element to be inserted.

for (int x=1;x<=10;x++) pila.push(Integer.toString(x));

We have created a loop that we will create the numbers and we have relied on the Integer class and method. ToString () to convert numbers to strings.

Once we have all the elements, we proceed to drain the battery. We will have to interact on the stack until it is empty, which tells us the method. Empty (). In each iteration we extract an item from the stack using the method. Pop ().

while (!pila.empty())
System.out.println(pila.pop());


This is the code:

import java.util.*;
public class Pilando {
Stack pila = new Stack();
public void ingresar()
{
for (int x=1;x<=3;x++) { pila.push(Integer.toString(x)); } } public void sacar() { while (this.empty() == 1) { System.out.println("Sacando el elemento "+pila.pop()); } System.out.println("La pila esta vacía!!!"); } public void show1() { System.out.println("El primer elemento agregado es ---> "+pila.firstElement().toString());
}
public void show2()
{
System.out.println("El ultimo elemento agregado es ---> "+pila.lastElement().toString());
}
public void show3()
{
System.out.println("La cantidad de elementos es de ---> "+pila.size());
}
public int empty()
{
int valid = 1;
if(!pila.empty())
{
valid = 1;
}
else
if(pila.empty())
{
valid = 0;
}
return valid;
}
}

Analysis Algorithm

An algorithm is a finite set of unambiguous and effective instructions that indicate how to solve a problem, produce at least one outlet, receive zero or more inputs and to run, require a finite amount of resources.
The selection criteria are defined by CPU time, this implies that the program will be more efficient is faster.

For example Quicksort



In this case the strategy is to take an item and put in a pivotal part to the minor elements to the pivot and the other to those over the pivot. After recursive calls are made to order both parties. In this case also takes advantage of the fact that an array of size 1 isalready sorted.
The algorithm that starts the settlement into two parts (not equal) is defined in the algorithm 21. This algorithm part of the settlement into two parts using the first array element as a pivot.

In this case using the asymptotic analysis, we define:

Size of the problem: The array size
Basic Operation: Comparisons
To make the temporal analysis we noticed that the partitionalgorithm performs n comparisons. Informally this is because the pivot is compared against all array elements. We analyze each case quicksort.
Worst Case: Occurs when the pivot is the first element
Best case: The pivot is exactly half
In this case the array is divided into two parts of equal size.Assuming that n = 2k each party will have a size 2k 1 (for the pivot is now in order.)







Bibliography

- Thomas H. Cormen , Introduction to Algorithms, Mc Graw Hill, 2000
- Harel D., Algorithmics The Spirit of Computing, Addison Wesley, Segunda Edición, 1992
- Horowitz E., S. Sahni, Fundamentals of Computer Algorithms, Potomac, Maryland: Computer Science Press, Inc, 1978

Theorical Part II - Virtual Memory

Virtual Memory

David Berumen Salazar

"To give the illusion of unlimited ram for all of your programs" was one of the benefits virtual memory(VM) gave many years ago. Historically storaging devices have stayed behind in the miniaturization race; while the processors rapidly got smaller and faster, puting together millions and millions of transistors in a couple of centimeters, hard disks and ram still look like an ancient thing (SSD are a great step in this).

This gap between computing and data transfer power and the invention of multitasking were the motivations of VM. To overcome the hardware limitations, abstractions were developed and the idea behind them was to give to the user and kernel processes more address space sacrificing efficiency as less as possible, to make more things and get to use those much expensive processors, for example, using permanent storage devices to extend temporary ones by developing a VMM, but enough with history lets get to understand one of the dozens of ways to implement VMM, in this case, in Linux 2.6.

Overview of VMM in Linux 2.6 Kernel

Virtual Memory Management is one of the most complex things of any OS as it had been always developing to become more efficient and Linux its not the exception, if you want to understand the "Black Magic" behind this I recomend you "Understanding the Linux Virtual Memory Manager" by Mel Gorban, anyway I tried to minimize it as much as possible.

Much of the information I obtained came from "Understanding Virtual Memory In Red Hat Enterprise Linux " because I think it gives a pretty good overview. So if you want to learn for yourself check the pdf or ask me, I believe its an excellent exercise to look how it works a real VMM and understand that there are many ways to to VMM.

References:

- Understanding the Linux® Virtual Memory Manager

-

Understanding Virtual Memory In Red Hat Enterprise Linux 4

- and many more...

And also I did some performance tests of the VM and paging

- PERFORMANCE TESTS

This are the slides of the Linux VM overview

Also Here's the Theorical File systems Entry

Theorical Part II - File Systems

The slides for the Theorical part II





Systems Performance

direct comparison FAT vs EXT3

Ext3 vs FAT

First of all, the access time take 1ms  less on ext3
the read rate are 0.2 Mb/s more efficient on the ext3.
but the ext3 was released on november 2001, and the FAT system on August 1996, and the FAT systems works better with small files.



the pseudo-code for the File System.

Also Here's the Theorical Virutal Memory Entry

Practical Presentation 1

This is the explanation for the practical part 1.

We use the nachos java version 5.0 to test the practical assignments

For this presentation we've implemented a runnable program that shows the use of locks on the unbounded-buffer consumer-producer problem.

I didn't use any slide, i only showed my code to the classroom, compiled it and finally, execute my program.

On the Lock code, i used the one that nachos provide in his tar, and i just add two lines to check the execution without debug parameters.

These are the lines that i added:

in the acquire function

  System.out.println(" acquire successful by thread: "+ KThread.currentThread());

in the release function

 System.out.println(" release successful by thread: "+ KThread.currentThread());

the link to the Locks source code is here
(also you can check on /nachos/threads/Locks.java)

This is the code that i wrote:

package nachos.threads;
import nachos.threads.*;

public class Prueba{

private static Lock l = null;
private static Lock l1 = null;
private static int in_stock = 0;

public static class Producer implements Runnable{

     private KThread currentThread = null;

	public Producer(){ // constructor
	}	

	public void run(){ //metodo run, lo que hace mi programa
		System.out.println("\nThe Producer start...");		
			l.acquire();
			in_stock++;
			System.out.println("the producer make 1 item, now there are "+in_stock+" in stock."); 
			l.release();
			this.currentThread.yield(); 
         }
   }

public static class Consumer implements Runnable{

     private KThread currentThread = null;

	public Consumer(){ //constructor
	}	

	public void run(){ //metodo run, lo que hace mi programa
		System.out.println("\nThe Consumer start...");
		   l.acquire();
			while(in_stock <= 0){
			    currentThread.sleep(); }
			l1.acquire();
			  in_stock--; 
			l1.release();
			  System.out.println("the consumer take 1 item, now there are "+in_stock+" in stock.");
		     l.release();
			this.currentThread.yield(); 
	
         }
   }

	 public static void start() {
	
		l = new Lock();
		l1 = new Lock();

		while(true){
		try{
  			Thread.currentThread().sleep(2000);
		} catch(Exception e){ }
		new KThread(new Producer()).setName("Producer").fork(); 
		new KThread(new Consumer()).setName("Consumer").fork();

		new Producer().run();
		new Consumer().run();    }
 		}
}
  

Finally, i modify the nachos code because the "*** thread 'x' looped 'x' times" gives me headache, so i opened the ThreadedKernel.java and then i comment the line were  KThread.selfTest() is called for the ThreadedKernel and also i added the starter method of my class here :)

public void selfTest() {
	//KThread.selfTest();
	//Semaphore.selfTest();
	//SynchList.selfTest();
	Prueba.start();
	if (Machine.bank() != null) {
	    ElevatorBank.selfTest();
	}
    }
 

last edit 15/09/2011
changed> line x,x,x, on the Prueba.java. thanks Juan carlos.
changed> grammar and spelling (attempt to improve)

Here's the slides of the Theorical Part 1

Theorical 1

User program "Elevator" (Pseudocode)

Here is the pseudocode for an user program we are gonna try to develop for NachOS, it may have some flaws by now but we hope to make it work as it should :)

Implementing locks using Semaphores

Heres the algorithm of how we'll implement locks using semaphores. and actually a lock it is really a binary semaphore. here's the code.

Implement a condition variable using semaphores.

Class: ConditionSemaphores

Lock cl;
SemaphoreLinkedList waitQueue;


function: Constructor(Lock *cl)


function: sleep


function: wake


function: wakeall
Reference: we use the code of the Condition variables of the nachos (java version)

Consumer-Producer (Unbounded buffer)

For the problem of the consumer-producer there are many solutions, with the condition that the buffer where unbounded we reach to the next one.

function main

function producer

function consumer


How this algorithm will solve the problem? Well in this solution the producer is free to create items at any time, the cosumer doesn't care at all.
But if the consumer want to take an item, he need to check the amount of items in stock, if the amount is zero, he will do nothing.

How to compile NachOS 5.0j

Our team have successfully compiled and tested this version of NachOS in:

• Archlinux 2.6.39 32 bits
• Ubuntu 10.04 32 bits
• Ubuntu 11.04 64 bits
  

The next slideshow explains the steps to compile and test NachOS 5.0j:

Nachos 5.0j

Go to slideshare to watch a better quality version:
link

References:

- Download Java NachOS 5.0j here
- Download Crosscompiler here
- View Java NachOS README here

First Blog Entry

This is only the introduction.

We are the Os Class team :)
- Diana
- Ever
- Marco
- David

our Instructor Elisa Schaeffer
Class notes property of Martin c. Rinard
we're gonna use NachOS.
Obviously the java version.