Saturday, December 1, 2007

IS 226 - Project 1 - Part 1

Since reality's been keeping me so busy elsewhere, I thought I'd stick these links for the first IS 226 project. I thought it would be easier and less time-consuming for me to write an entry and get here from time to time rather than to organize my bookmarks which is close to a hodgepodge of ideas in an anything-goes forum.

Anyway here are the said links.
  1. www.google.com and search for “homepage design”
  2. The Ten Most Violated Homepage Design Guidelines
  3. Top Ten Guidelines for Homepage Usability
  4. Homepage Real Estate Allocation
  5. The Canonical Intranet Homepage
  6. Top Ten Web Design Mistakes of 2005
  7. Planning a usable website: A threestep guide
And now for the homepage...

Sunday, November 25, 2007

IS215 - Concurrent Processes Exercises - 2

11. Write a monitor solution to the readers and writers problem given in (8).

12. Outline a method of handling (detecting and recovering from) lost messages in a message passing system.

13. What issues are true for message passing implemented in distributed systems and that are not issues when message passing is implemented in single processor systems.

14. Trace the execution of the program for reading and writing to a buffer. Try to illustrate all possible executions of this program.

read()
{
while (TRUE) {
read(&item)
/* wait for empty buffer */
RECEIVE(write@uplb,&m);
construct_message(&m,item);
SEND(write@uplb,&m);
}
}

write()
{
while (TRUE) {
RECEIVE(read@upd,&m);
extract_item(&m,&item);
write(item);
SEND(read@upd,&m);
}
}

15. Compare and contrast the merits of semaphores over message passing and vice versa.

16. Show that semaphores, monitors and message passing solutions to the concurrency problem are equivalent.

17. Write a solution to the Dining Philosophers problem that contains

a) starvation problem
b) mutual exclusion violated

18. Write a correct solution to the Dining Philosophers problem that is different from the one given in book.

19. Show the correctness of the following solution to the Dining Philosophers problem:

int fork[5];

philosopher(i)
{
for( ; ; ) {
think;
while does not have both forks {
wait(fork[i]);
if (fork[(i+1) mod 5)] is free
wait(fork[(i+1) mod 5]);
else
signal(fork[i]);
}
eat;
signal(fork[i]);
signal(fork[(i+1) mod 5]);
}
}

20. Two brothers are seated opposite each other on a table with a plate of Palabok and fork. The action of each brother consists of alternate periods of picking food and chewing. The action starts by taking control of the fork, if successful starts to pick the food, then put the fork back on the table and starts to chew. After this, the cycle is repeated. A possible solution to this problem is the following:

jollibee()
{
/* execute in parallel */
brother(1) || brother(2);
}

brother(i)
{
while (TRUE) {
pick_fork();
pick_palabok();
put-Down_fork();
chew();
}
}

a) What are the possible problems that will be encountered by this solution?
b) When do the problems you identified occur? Give one instance for each problem.
c) Improve the solution using semaphores.

IS215 - Concurrent Processes Exercises - 1

1. Give two examples of competing processes in an actual system. Do the same for cooperating processes.

2. Write a procedure (different from what was given in this book earlier) use_resource() illustrating the following mutual exclusion problems:

a) starvation
b) mutual exclusion violated
c) deadlock

3. What is a monitor as used for regulating concurrent access to shared resources? Give examples of problems that may be eliminated by the use of a monitor.

4. Describe an approach to process synchronization. Illustrate your answer by outlining an algorithm for a cyclic buffering system; show how your algorithm works by considering the progress of a consumer and a producer processes as they advance through critical regions, get delayed on queues, etc.

5. When, and why, do processes need to synchronize their activities. Describe an approach to process synchronization based upon semaphores. Show how these may be used to solve two typical synchronization problems.

6. Illustrate or argue the correctness of the Dekker's algorithm? Do the same for the Paterson's algorithm and the engineering solution.

7. In order for the engineering solution to execute correctly, the test&set() function must be executed in one CPU cycle. Why is this so? What happens if this is not executed in one CPU cycle?

8. The readers and writers problem models access to a database. Consider a big database with many competing processes wishing to read and write into it. It is acceptable to have multiple processes reading the database at the same time, but if one process is writing, no other process may have access to the database, not even readers. Write a program employing semaphores that ensure correct execution of this.

9. What does the initial value of the semaphore s stands for?

10. Show that counting semaphores can be implemented using binary semaphores.

Saturday, November 24, 2007

IS215 - Resource Management Exercises - 2

11. Given a river crossing deadlock situation in Figure 6.3.

a) Name the three broad classes of policies dealing with deadlocks. Give one specific policy each to illustrate the classes using the river crossing 'deadlock situation.
b) Illustrate the Banker's algorithm using the river crossing deadlock situation.

12. The Banker's algorithm has some inherent weaknesses. Discuss some of these inherent weaknesses.

13. Deadlock avoidance is very expensive. Why?

14. Consider the traffic deadlock depicted in Figure 6.5.


Figure 6.5. Traffic deadlock

a) Show that the four necessary conditions for a deadlock indeed hold in the said situation.
b) Come up with a simple rule that will avoid deadlocks in the streets of Metro Manila.

15. Compare the four policies for dealing with deadlocks using the following criteria:

a) overhead introduced for adopting such policy,
b) inconvenience to users when a deadlock occurs,
c) difficulty of implementation.

16. Differentiate a deadlock situation from starvation.

17. Consider a computer system that has four magnetic tape drives (MT), four exchangeable disk drives (DD), two line printers (LP), and two card readers (CR). Suppose the current allocation of resources to processes are:

18. 19. P1 20. P2 21. P3 22. P4 23. Max
24. MT 25. 0 26. 0 27. 2 28. 2 29. 4
30. DD 31. 0 32. 0 33. 2 34. 2 35. 4
36. LP 37. 1 38. 0 39. 0 40. 0 41. 2
42. CR 43. 0 44. 1 45. 1 46. 0 47. 2

Suppose,

P1 is waiting for DD,
P2 is waiting for MT, and
P4 is waiting for CR.

Will a circular wait result if we allocate

LP to P2
LP to P3
LP to P4?

18. Why is deadlock recovery such a difficult policy to implement?

19.If the state is unsafe, it does not follow that the system will result to a deadlock. Explain why this is the case. Give an example of an unsafe state that will result to all the processes completing without deadlock occurring.

20. Under what circumstances would you adopt the following deadlock policies:
a) Bahala na
b) Avoidance
c) Detect and Recover
d) Prevention

IS215 - Resource Management Exercises - 1

1. Discuss the two resource allocations methods (static and dynamic). Give the advantages of one over the other.

2. Classify the following resources as either sharable or non-sharable: CPU, memory, line printer, card reader, magnetic tape, magnetic disk, file, database record.

3. Give an example of a system in a deadlock situation. The example should be a system with at least three different types of resources.

4. Explain the four conditions for a deadlock to occur. Is it necessary for all four conditions to hold for a deadlock to occur.

5. Why does the Bahala Na policy work? Why is this policy not often used?

6. How can the circularity condition be prevented from holding? Illustrate how deadlock can be avoided by preventing this condition.

7. How can hold and wait be prevented from holding? Illustrate how deadlock can be avoided by preventing this condition.

8. One way of detecting a deadlock is to detect if circularity wait already holds in the system.
Outline a method of detecting a deadlock.

9. Outline the cheapest method of recovering from a deadlock. Support your answer by arguing for it.

10. Aborting a process during deadlock recovery is not that simple. Explain.

IS215 - File and Disk Management Exercises - 2

11. What method of ensuring file systems reliability is suitable for each of the following 'file system:

a) small in size and data loss is tolerable (quite cheap to recover)
b) small and data loss are very expensive, hence it should be avoided
c) large in size and data loss is tolerable
d) large in size and data loss is very expensive

Explain your answer.

12. Periodic dump is expensive. Explain.

13. Discuss the procedure for recovering from file system crash, when the system used is a combination of periodic dump, incremental dump and transaction logging.

14. Name an actual system that uses the directory structure:

a) single-level directory
b) two-level directory structure
c) tree-structured directory
d) acyclic directory

15. Discuss a method of checking the consistency of a file system.

16. During file system recovery after a crash, files are often compacted into contiguous regions on the disk even though such contiguity may be irrelevant to the file access method. Explain why compaction may still be advantageous.

17. Given the following requests for disk access in a disk whose tract number ranges from 0 to 99.

20, 7, 99, 56, 75, 19, 89, 2, 50

The read/write head is currently reading track number 15 and has just gone from track number 26, if the scheme used is:

a) First-Come-First-Serve
b) Shortest-Seek-Time-First
c) SCAN
d) CSCAN
e) N-Step SCAN

18. Differentiate non-contiguous sector allocation from non-contiguous block allocation.

19. What are the overheads involved with the allocation strategies: contiguous, linked, 'and indexed, if the file:

a) grows at the beginning
b) grows at the middle
c) grows at the end?

Answer also the cases when the file shrinks instead of grows.

20. All the disk scheduling algorithms (SSTF, SCAN, C-SCAN, N-Step SCAN) except FCFS are not truly fair (starvation may occur). Arrange the algorithms in order of degrading fairness. Show how you arrived at your answer.

IS215 - File and Disk Management Exercises - 1

1. What is a file? Describe the three most common file organizations.

2. What is a file descriptor? What is a file directory? What is the relationship between the two?

3. What is the difference of a tree-structured directory structure from an acyclic directory structure?

4. Suppose a computer system will be used for software development of a programming team.

a) What directory system is suited for this type of system?
b) What file protection scheme is needed to satisfy the needs of the users?
c) What file access methods should be supported?
d) What file allocation method should be used?

Answer the same questions for system intended as an automated teller machine (ATM).

5. Identify the minimal operations on files that will allow all other operations to be simulated using the operations in the minimal set operations.

6. One way of protecting the file system is through the use of passwords. Why is this method not used anymore in most modern operating systems?

7. Outline a method of protecting the files of a user in a multi-user operating system. The method should allow others to access the files of the user if he allows it.

8. What are the advantages of direct access to files over the sequential access to files? Are both access methods really necessary in an operating system?

9. What is the difference between sector and block file allocation methods? Is there a situation where both methods are one and the same?

10. What is the problem in contiguous allocation method that is solved by the linked allocation method?

IS215 - Memory Management Exercises - 2

11. Discuss the factors that may affect the performance of a paging system. For each of the sequence of page requests given below, and assuming a store size of four page frames, give the optimum sequence of page fetches and replacements and also, the sequence which would be generated if the replacement algorithm used is LRU. Do the same for FIFO. Comment on the results obtained.

a) 1, 2, 3, 4, 5, 1, 2, 3, 4, 5, 1, 2, 3, 4, 5, 1, 2, 3
b) 1, 2, 1, 3, 1, 4, 1, 5, 1, 2, 1, 3, 1, 4, 1, 5, 1, 2
c) 1, 2, 3, 4, 5, 4, 3, 2, 1, 2, 3, 4, 5, 4, 3, 2, 1, 2
d) 1, 2, 3, 4, 5, 4, 3, 2, 1, 5, 4, 3, 2, 1, 2, 3, 4, 5

12. With the sequence of page requests given in (11a-11d), give the contents of the memory for each sequence. Assume that the memory is initially empty and the working set is 4 pages at any instant.

13. Outline a possible structure for page and segment tables. Explain how an associative memory may be used to reduce effective access time. Show that if p% of accesses fail to match entries in the associative store then, in a page segmented addressing system, there will be a slow down of p%.

14. Local page replacement policy is prone to thrashing. Argue for or against this statement.

15. Paged segmentation was designed to combine the advantages of paging and segmentation. Hence there are problems present in

a) paging alone; and
b) segmentation alone

which are not in paged segmentation. List all these problems.

16. Demand and anticipatory fetch policies can be combined together. Outline a system that combines these two fetch policies.

17. Discuss how thrashing is avoided when the working set of a process is determined in advance.

18. Consider a swapping system. Measured utilization are:

CPU utilization - 20%
Swapping device (drum) - 99.7%
Other I/O devices - 5%

What will be the effect on CPU utilization if we

a) get a faster CPU
b) get a bigger hard disk for swapping
c) increase the degree of multiprogramming
d) decrease the degree of multiprogramming
e) get faster other I/O devices.

19. Consider a swapping system in which the memory is composed of the following hole sizes (assuming the leftmost hole is the first in the list):

10K, 4K, 20K, 18K, 9K, 12K, 15K

Which hole is taken for successive segment=requests of 12K, 5K, 10K for first-fit? Repeat the question for best-fit and worst-fit.

20. Which of the following programming techniques and structures are ideal for paging. Support your answer.

a) sequential search
b) binary search
c) array operations
d) stack operations

Which is ideal for segmentation?

IS215 - Memory Management Exercises - 1

Exercises

1. When binding of addresses to memory locations is done at execution time, relocation 'is less expensive than when binding is done at compile time. Explain.

2. The main problem of Multiprogramming with Fixed Number of Tasks is internal fragmentation while that of Multiprogramming with Variable Number of Tasks is external fragmentation. Explain.

3. Define swapping. What are the motivations for providing swapping? Show how this technique enables a reasonable response time to be given to each user of an interactive system. In what situation is swapping not effective?

4. Why is CPU utilization improved when swapping is upgraded from that where only one user process is allowed in memory at a time to one where more than one user process is allowed in memory at a time.

5. Outline one method of protecting the memory of a multi-user system. Specifically answer the question of how to protect the systems area (without totally preventing other users from accessing the said area as long as it is done correctly) and the areas allocated to other users.

6. Compaction usually introduces a high overhead because it has to consider the binding of user's variables to memory locations. Explain.

7. Differentiate temporal from spatial locality. Illustrate the two using access to the memory by the computer system.

8. Why is it impossible to share the code of a process that allows modification on the code itself.

9. Given the following segment table:
Segment NumberBaseLimit
050150
11000100
2500200
325050

What are the equivalent real addresses of the following virtual addresses:

a) (0, 10)
b) (1, 150)
c) (2,100)
d) (3, 25)

10. Assuming a page frame size of 1024 and given the following page table:
Page NumberBase
01024
13072
25120
32048

What are the equivalent real addresses of the following virtual addresses:
a) (0, 64)
b) (1, 1048)
c) (2, 1)
d) (3, 1024)

IS215 - Processor Management Exercises - 2

11. Explain what is a fair scheduling algorithm?

12. What are the objectives of CPU scheduling?

Answer

The main objective of CPU scheduling is "to allocate the CPU so as to optimize system performance without sacrificing user convenience... To achieve the objective of CPU scheduling, we need to provide a good performance using the measures outlined above, meet user specified deadlines, and provide good utilization of other system resources."

13.Describe the advantages and disadvantages of two short-term scheduling policies that could be used to select which process next enters the run state.

14. State an undesirable feature associated with each of the following scheduling algorithms:
a) First-come-first-serve
b) Shortest job first
c) Shortest remaining processing

15. Round robin schedulers normally maintain a list of all runnable processes, with each process occurring exactly once in the list. What would happen if a process occurred twice in the list? Can you think of any reason for allowing this?

16. When is the response time of a process different from its waiting time.

17. Most operating systems usually use a two-level scheduler.
a) Give two advantages of this set-up.
b) Give two disadvantages of this set-up.
c) Describe the actions of a two-level scheduler when it is called to select a process to be dispatched.

18. Minimizing mean response time is the same as maximizing throughput. Prove this 'statement.

19. Evaluate the scheduling algorithms
a) First-Come-First-Serve
b) Shortest Job Next
c) Shortest Remaining Processing Time

in terms of the following criteria:
CPU utilization
throughput
turnaround time
waiting time.

20. Short time slices means better response times. Explain why this is so?

IS215 - Processor Management Exercises - 1

Making use of the decryption routine before, I took the exercises contents in the single processor PDF for a ride. However it turned out that the text in text areas don't render pasted text from the clipboard properly especially for non-alphanumeric characters. If I end up having free time soon, I'll try and refine the functionality further. Right now, I need to sleep already.

Anyway, here are the exercises for the processor management chapter after a few tweaks from the resulting text:


1. Providing good response time at a terminal might introduce large overheads that in effect will reduce the overall CPU utilization. Explain what are these overheads that will reduce CPU utilization.

2. When we view all the processes in the system, we can see that a state transition by one process could cause another process to make a state transition. Under what circumstances, if any, could the following cause-and-effect transitions occur?

a) block -> dispatch
b) preempt -> dispatch
c) block -> preempt
d) wake-up -> dispatch

3. Under what circumstances, if any, would the following transitions cause no other immediate transitions:

a) dispatch
b) preempt
c) block
d) wake-up

4. Differentiate preemptive from non-preemptive scheduling in terms of when to change the program currently in control of the CPU.

Answer

Preemptive scheduling refers to a scheduling strategy where "the CPU is suspended when a higher priority process is in the ready queue" while non-preemptive scheduling refers to a scheduling strategy where "even if a higher priority process is ready, the running process is allowed to continue until either it is blocked or completes its execution."

5. When no process is ready to take control of the CPU, we need to have something to keep the CPU busy. Why?

6. State the effect of

a) time slicing; and
b) increasing the time for one interaction

on the response time of a process.


7. What is the purpose of a dispatcher in an operating system? Illustrate your answer by showing the sequence of events and dispatcher actions that occur when a process enters the run state from the ready state.

8. Differentiate high-level scheduling of jobs and low-level scheduling of processes.

Answer

High-level scheduling of jobs refers to swapping processes in and out of memory. Issues concerning high-level scheduling include deciding if another process can still run, whether the process table is full, whether the user process limit has been reached and whether to load to swap space or memory. Low-level scheduling on the other hand refers to deciding which process in memory should get CPU time next.

9. The scoring system in high-level scheduling usually "age". Why is there a need to "aged" the scores?

10. Short-term scheduling can either be preemptive or non-preemptive. Differentiate these two methods of short-term scheduling.

Thursday, November 22, 2007

PDF Encryption

Messing It Up

One thing frustrating I encountered when copy-pasting stuff from the Single Processor PDF was that things messed up during the paste-part. To see this, try highlighting the a few words or line of texts from the said PDF.



Then pasting it in any word processor or text editor produces garbage. The next screenshot was how it appeared in Notepad++ here.



Not good especially if copy-paste saves a lot of time. And today's just two days before the deadline! If I just had the time, I would've even bothered to create at least an equivalent Word document for easier searching of terms and concepts if the time still permitted.


Workarounds Anyone?

Now I don't know if there are any third-party software for this one. What I do know is that the mapping's pretty obvious. You might want to try and comparing ASCII values of characters from several encrypted and decrypted samples. If you do so, you'll end up with:

y = ( x + 29 ) mod 256

Nothing much useful there though except if it can be used without the calculator and ASCII table.

So I actually spent time to create a working decryption form for it, (a horribly crude but functional one that is.) So after a few lines of Javascript and HTML code, it worked!

Check it out below.




Decrypt Now

What's With The New Blog?

Just another attempt at organizing MIS routines.

Since I just started with my MIS studies at UPOU, I've had less time for my other blogs, (Half-Empty, Half-Full and The Domino Effect both at Wordpress). It might seem a little odd then that one of the reasons I chose to fix my already crazy schedule is to create yet another one.

But what can I do, I have to start organizing stuff somewhere. At the rate regular and freelance work along with family responsibilities pour in, I can't make a dedicated and specialized online storage for the things the way I want it. Throw in the slow yet merciless ticking of the clock and I have to make my move now.

Why the Blog? Because I don't have the time to create a CMS for the stuff, not even something half-baked. Sure there are several-minute-setup CMS services out there but I'm more used to blogging. Perhaps a move elsewhere in the future might be in order but for now, this should do.

Why Blogger? I find the functionalities of Wordpress too constraining especially the lack of support for some HTML and Javascript, especially for the latter. Since I intend to include some functionalities here, the lack of client-side scripting appears glaring.

So after a deep breath, here goes nothing...