CS3161 (A) OPERATING SYSTEM PRINCIPLES (DR. LIU WENYIN) (09CS3161_LW) - Homework 2

1. Servers can be designed to limit the number of open connections. For example, a server may wish to have only N socket connections at any point in time. As soon as N connections are made, the server will not accept another incoming connection until an existing connection is released. Explain how semaphores can be used by a server to limit the number of concurrent connections.

A semaphore is initialized to the number of allowable open socket connections. When a connection is accepted, the acquire ( ) method is called. When a connection is released, the release ( ) method is called. If the system reaches the number of allowable socket connections, subsequent calls to acquire ( ) will block until an existing connection is terminated and the release method is invoked.

2. What is the meaning of the term busy waiting? What other kinds of waiting are there in an operating system? Can busy waiting be avoided altogether? Explain your answer.

A process is waiting for an event to occur and it does so by executing instructions.
A process is waiting for an event to occur in some waiting queue (e.g. I/O, semaphore) and it does so without having the CPU assigned to it.
Busy waiting cannot be avoided altogether.

3. Consider the traffic deadlock depicted in Figure 1.
a. Show that the four necessary conditions for deadlock indeed hold in this example.
b. State a simple rule for avoiding deadlocks in this system.

Figure 1 Traffic deadlock.

l Mutual exclusion: Only one car may be occupying a particular spot on the road at any instant.
l Hold and wait: No car ever backs up.
l No pre-emption: No car is permitted to push another car out of the way.
l Circular wait: Each corner of the city block contains vehicles whose movement depends on the vehicles blocking the next intersection.

4. Consider the following snapshot of a system:


Allocation
Max
Available

ABCD
ABCD
ABCD
P0
0012
0012
1520
P1
1000
1750

P2
1354
2356

P3
0632
0652

P4
0014
0656


Answer the following questions using the banker’s algorithm:
a. What is the content of the matrix Need?

Process
A
B
C
D
P0
0
0
0
0
P1
0
7
5
0
P2
1
0
0
2
P3
0
0
2
0
P4
0
6
4
2

b. Is the system in a safe state?

System is in safe state because resources are available (1, 5, 2, 0).

c. If a request from process P1 arrives for (0, 4, 2, 0), can the request be granted immediately?

Request from process P1 can be granted immediately. Request is (0, 4, 2, 0) and available resource is (1, 5, 2, 0).

5. A single-lane bridge connects the two Vermont villages of North tunbridge and South tunbridge. Farmers in the two villages use this bridge to deliver their produce to the neighboring town. The bridge can become deadlocked if both a northbound and a southbound farmer get on the bridge at the same time (Vermont farmers are stubborn and are unable to back up.) Using semaphores, design an algorithm that prevents deadlock. Initially, do not be concerned about starvation (the situation in which northbound farmers prevent southbound farmers from using the bridge or vice versa).


6. Consider a paging system with the page table stored in memory.
(a) If a memory reference takes 200 nanoseconds, how long does a paged memory reference take?

400 nanoseconds; 200 nanoseconds to access the page table and 200 nanoseconds to access the word in memory.


(b) If we add associative registers, and 75 percent of all page-table references are found in the associative registers, what is the effective memory reference time? (Assume that finding a page-table entry in the associative registers takes zero time, if the entry is there.)

Effective access time = 0.75X (200 nanoseconds) + 0.25 X (400 nanoseconds) = 250 nanoseconds.


7. (a) Compare paging with segmentation with respect to the amount of memory required by the address translation structures in order to convert virtual addresses to physical addresses.

Paging requires more memory overhead to maintain the translation structures. Segmentation requires just two registers per segment: one to maintain the base of the segment and the other to maintain the extent of the segment. Paging on the other hand requires one entry per page, and this entry provides the physical address in which the page is located.

(b) Why are segmentation and paging sometimes combined into one scheme?

Segmentation and paging are often combined in order to improve upon each other. Segmented paging is helpful when the page table becomes very large. A large contiguous section of the page table that is unused can be collapsed into a single segment table entry with a page-table address of zero. Paged segmentation handles the case of having very long segments that require a lot of time for allocation. By paging the segments, we reduce wasted memory due to external fragmentation as well as simplify the allocation

CS3161 (A) OPERATING SYSTEM PRINCIPLES (DR. LIU WENYIN) (09CS3161_LW) - Answers to Tutorial 9 Questions

Q1 When does page fault occur ? Describe the action taken by the operating system when a page fault occurs.

A page fault occurs when an access to a page that has not been brought into main memory takes place (invalid page bit set in page table).
Page Fault Handling procedures,
(1)Scan the page table entry, the page is invalid – page fault occurs;
(2)O.S. generate TRAP interrupt;
(3)Locate the page with data in secondary storage;
(4)I/O requested to read the needed page into the available free frame;
(5)Upon completion of I/O, the process table and page table are updated as valid page and address in memory;
(6)The instruction is restarted.






Q2 (i) What is a page replacement ?(ii) What does the dirty bit mean ?


(i) Page replacement is the scheme (algorithm) to identify a victim page for replacement when all available frames (memory) are all currently used.
Page replacement operation involves selecting a frame (preferably not currently in use) as a victim for replacement; swap it out; swap in the desired page into the free frame; restart program.
Available page replacement scheme include FCFS, LFU, NRU.
(ii) A bit stored in the page table, if set, the page has been modified (dirty page), and must be written back to backing store before being use as a victim for page replacement to create a free frame in physical memory.
It is desirable try not to replace a dirty page, since it will take longer (with the write-back operation).




Q3 (i) What is Thrashing ?(ii) How does the system detect thrashing ?(iii) What can the system do to eliminate it ?


(i) Thrashing in a virtual memory system is a high page fault activities situation, where the system spends most of the time in page swapping than executing processes.
Thrashing is caused by under-allocation of the minimum number of pages required by a process, forcing it to continuously page fault.
(ii) The system can detect thrashing by elevating the level of CPU utilisation as compared to the level of multiprogramming.
The sudden drop in CPU utilisation while increasing the level of multiprogramming (increasing the number of processes) identifies the thrashing point.
(iii) Thrashing can be eliminated by reducing the level of multiprogramming, (that is to decrease the number of processes in the system).

CS3161 (A) OPERATING SYSTEM PRINCIPLES (DR. LIU WENYIN) (09CS3161_LW) - Answers to Tutorial 8 Questions

Q1 Explain the difference between internal and external fragmentation in memory management. Suggest ways to reduce or solve of both types of fragmentation.


Internal fragmentation is the area in a region or a page which is not used by the job occupied that region or page. This space is unavailable for use by the system until that job is finished or the region is released.

External fragmentation is a region which is unused and available, but it is too small for any of the waiting jobs.

To reduce or solve problems of fragmentation :
Internal fragmentation - reduce size of individual region / allocation unit.
External fragmentation - break down request into non-contiguous portions, compaction, swapping.



Q2 What is compaction ? Why use it ?


Movement of processes to eliminate small free memory partitions. Compaction is used to eliminate memory fragmentation (external) and to increase memory utilization.

It allows smaller memory partitions to form fewer bigger ones, thus allowing larger processes to run.





Q3 Given memory partition of 100K, 500K, 200K, 300K, and 600K (in order), how each of the First-fit, Best-fit, and Worst-fit algorithms place processes of 212K, 417K, 112K, and 426K (in order) ? Which algorithm makes the most efficient use of memory ?


(1) First-fit :
212K is put in 500K partition
417K is put in 600K partition
112K is put in 288K partition (new partition 288K = 500K - 212K)
426K must wait
(2) Best-fit :
212K is put in 300K partition
417K is put in 500K partition
112K is put in 200K partition
426K is put in 600K partition
(3) Worst-fit :
212K is put in 600K partition
417K is put in 500K partition
112K is put in 388K partition
426K must wait

In this example, the best-fit turns out to be the best algorithm.



Q4 (i) What is paging ?(ii) What is a frame ?(iii) What is contained in the page table ?(iv) How many frames are needed for each page ?(V)Draw the diagram to show how paging works.


(i) Splitting program up into a group of fixed-equal-sized partitions, allowing the parts to be non-contiguous in memory, during the execution of the process.
(ii) Fixed-size block of physical memory, each block must be of the same size as one page.
(iii) Page number, frame number, base address of each frame, presence, protection (permission), dirty bit.
(iv) One.

CS3161 (A) OPERATING SYSTEM PRINCIPLES (DR. LIU WENYIN) (09CS3161_LW) - Answers to Tutorial 7 Questions

Q1 What is a critical section problem ? What is a safe state ?


Critical Section Problem
- A critical section is a section of code, sharing or interacts with other processes in which only one process (among processes) at a time can be executing.
- Critical section problem involved in design an algorithm which allows at most one process into the critical section at a time, without deadlock.

Safe State
- A set of resource allocations such that the system can allocate resources to each process (up to its maximum requested resources) and in some order (completion sequence), and still avoid a deadlock.





Q2 Define deadlock and the four necessary conditions needed before deadlock can occur ?


A situation where every process is waiting for an event which can be triggered only by another process.
The four necessary conditions for deadlock to occur :
1 Mutual exclusion: At least one resource must be held in a non-sharable mode.
2 Hold and wait: A process holding at least one resource is waiting for more resources held by other processes.
3 No preemption: Resource cannot be preempted.
4 There must be a circular waiting condition for processes.






Question 3

Consider the following snapshot of a system. There are no current outstanding queued unsatisfied requests.
Maximum resources
r1 r2 r3 r4
6 7 12 12
current allocation maximum demand
process r1 r2 r3 r4 r1 r2 r3 r4
p1 0 0 1 2 0 0 1 2
p2 2 0 0 0 2 7 5 0
p3 0 0 3 4 6 6 5 6
p4 2 3 5 4 4 3 5 6
p5 0 3 3 2 0 6 5 2
Is this system current in a safe or unsafe state ? Why ?




needs
r1 r2 r3 r4
0 0 0 0
0 7 5 0
6 6 2 2
2 0 0 2
0 3 2 0
Running the Banker's Algorithm, we see processes can finished in the order p1, p4, p5, p2, p3. The system is in a safe state since there is a completion path.

CS3161 (A) OPERATING SYSTEM PRINCIPLES (DR. LIU WENYIN) (09CS3161_LW) - Answers to Tutorial 6 Questions

Q1 Study of The Producer-Consumer Problem (Bounded Buffer Problem)(i) Using pseudo code to represent the problem;(ii) Provides a solution using semaphore;(iii) Provides a solution using monitor;


(i) Description of the problem
. Two processes share a common, fixed-size buffer
. One process, the producer, puts data into the buffer, the other process, the consumer, takes it out.
. When producer wants to put a datum into the buffer, but it is full, producer goes to sleep, to be awakened when the consumer removes one or more data.
. When consumer wants to remove a datum from the buffer, when the buffer is empty, consumer goes to sleep, until producer put one datum into the buffer.
nRepresentation of the producer-consumer problem
. count = variable, to keep track of the number of data in buffer
N = maximum number of data number the buffer can hold

. consumer test count,
either count = 0 , go to sleep
or count = count -1
. each process tests if the other process should be sleeping, if not, wakes it up
. SLEEP and WAKEUP are system call for process manipulation
. enter_data and remove_data are procedures for putting and taking data in and out of the buffer





Code representing the Producer-consumer problem :
#include “prototypes.h”
#define N 100 /* number of slots in the buffer */
int count = 0; /* number of data items in buffer */
void producer (void)
{
int data;
while (TRUE) { /* repeat forever */
data = produce_data(); /* generate next data */
if (count == N) sleep(); /* if buffer is full, go to sleep */
enter_data(data); /* put data in buffer */
count ++; /* increment count of data number in buffer */
if (count == 1) wakeup(consumer); /* buffer not empty now and can be consumed now, notify consumer…*/
}
}
void consumer(void)
{
int data;
while (TRUE) { /* repeat forever */
if (count == 0) sleep(); /* if buffer is empty, go to sleep */
data = remove_data(); /* take data out of buffer */
count --; /* decrement count of data number in buffer */
if (count == N -1) wakeup(producer); /* buffer becomes not full and can be put more data, should notify producer */
consume_data(data); /* print data */
}
}



. Race Condition can occur executing the above code :

count++ could be implemented as
register1 = count
register1 = register1 + 1
count = register1

count-- could be implemented as
register2 = count
register2 = register2 - 1
count = register2

Consider this execution interleaving with “count = 5” initially:

S0: producer execute register1 = count {register1 = 5}
S1: producer execute register1 = register1 + 1 {register1 = 6}
S2: consumer execute register2 = count {register2 = 5}
S3: consumer execute register2 = register2 - 1 {register2 = 4}
S4: producer execute count = register1 {count = 6 }
S5: consumer execute count = register2 {count = 4}






(ii) Semaphores
. Semaphore is an integer variable
. When semaphore = 0, no resource is available
when semaphore > 0, # of resource abailable
. Semaphore can be operated in two operations ( Wait, Signal) :
Wait (sleep)
(i) checks to see if the semaphore value > 0 or = 0
(ii) if semaphore > 0, decrement the value, process execute critical section…,
if semaphore = 0, process put to sleep
Signal (wakeup)
(i) increment semaphore by 1
(ii) one of the sleeping process is awaken
. Wait () and Signal () operations are all done as a single, indivisible atomic action
. Signal and Wait are implemented as system calls; interrupts are disabled during execution to ensure atomic action ( protected by a lock variable mutex if necessary, as mutual exclusion)






The producer-consumer problem using semaphore
. Three semaphores are used :
full - counting the number of slots that are full.
empty - counting the number of slots that are empty.
The full and empty semaphores ensure that producer stops running when the buffer is full, consumer stops running when it is empty.
mutex - to make sure consumer and producer do no access the buffer at the same time.
mutex = 0 , no process can operate on semaphore ;
mutex = 1, process can perform Signal or Wait.
. Initially :
full = 0
empty = number of slot in the buffer.
mutex = 1 (can only take 1 or 0 - binary semaphore).
. Each process does a Wait before entering its critical region,
a Signal after leaving the critical region.




#include “prototypes.h”
#define N 100 /* number of slots in the buffer */
typedef int semaphore; /* semaphores are a special kind of int */
semaphore mutex = 1; /* controls access to critical region */
semaphore empty = N; /* counts empty buffer slots */
semaphore full = 0; /* counts full buffer slots */
void producer(void)
{
int data;
while (TRUE) { /* TRUE is the constant 1 */
data = produce_data(); /* generate data to put in buffer */
Wait(&empty); /* decrement empty count */
Wait(&mutex); /* enter critical region */
enter_data(data); /* put new data in buffer */
Signal(&mutex); /* leave critical region */
Signal(&full); /* increment count of full slots */
}
}
void consumer(void)
{
int data;
while (TRUE) { /* infinite loop */
Wait(&full); /* decrement full count */
Wait(&mutex); /* enter critical region */
data = remove_data(); /* take data from buffer */
Signal(&mutex); /* leave critical region */
Signal(&empty); /* increment count of empty slots */
consume_data(data); /* do something with the data */
}
}




(iii) Monitors
. monitor - a collection of procedures, variables and data structures in a package
. only one process can be active in a monitor at any instant
. compiler knows they are special monitor procedures (different from other procedure calls) and ensure only one process allows in the monitor, otherwise the calling process will be suspended until other process has left (mutual exclusion).
. Example of a monitor :
monitor example
integer i;
condition c;
procedure producer(x);
…
…
end;
procedure consumer(x);
…
…
end;
end monitor;
. A way for process to block when they cannot proceed - condition variables and operations WAIT and SIGNAL
When a monitor procedure finds that it cannot continue (such as for producer finds the buffer is full), it WAIT on the condition variable, full. The calling process will block itself, allowing another process (previously been blocked) to enter monitor
When a process (such as the consumer) wake up other sleeping process by doing a SIGNAL on the condition variable that other process is waiting on and must exited from the monitor immediately. SIGNAL must appear as the last statement (before exit) in a monitor.
The WAIT must come before the SIGNAL




Solution for the producer-consumer problem using monitor :
monitor ProducerConsumer
condition full, empty;
integer count, N;
function enter(data:integer);
begin
if count = N then wait(full);
enter_data(data);
count := count + 1;
if count = 1 then signal(empty)
end;
function remove(data:integer);
begin
if count = 0 then wait(empty);
data = remove_data;
count := count - 1;
if count = N - 1 then signal(full)
end;
count := 0;
end monitor;


procedure producer;
begin
while true do
begin
data = produce_data;
ProducerConsumer.enter(data)
end
end;
procedure consumer;
begin
while true do
begin
ProducerConsumer.remove;
consume_data(data)
end
end;
. monitors are a programming language concept and monitor procedures must be recognised by compiler to enforce mutual exclusion.

CS3161 (A) OPERATING SYSTEM PRINCIPLES (DR. LIU WENYIN) (09CS3161_LW) - Answers to Tutorial 5 Questions

Q1 Define the difference between Preemptive and Non-preemptive scheduling. State why strict non-preemptive scheduling is unlikely to be used in a computer centre, suggest a better scheme for interactive users.


Preemptive scheduling allows a process to be interrupted in the midst of its execution, taking the CPU away from it and allocating it to another process.

Non-preemptive scheduling ensures that a process relinquishes control of the CPU only when it finishes with its current burst.

Non-preemptive would not likely be used in a computer centre, especially in a time sharing system, because it cannot guarantee that each user gets a share of the CPU at regular intervals. Non-preemptiveness allows programs to run infinitely long thus making turnaround time (response time) for other submitted jobs even longer.

Round-Robin is a preemptive scheme that makes use of interrupt/context switching operation to allow processor switching between jobs. Long jobs cannot delay shorter ones, because short jobs are guaranteed of getting the processor periodically. Interactive users will thus receive the processor frequently enough to maintain good response times.





Q2 Explain the difference in degree to which the following scheduling algorithms discriminate in favour of short jobs.(i) First Come, First Served(ii) Round Robin(iii) Multi-level feedback queues


(i) First Come, First Served (FCFS) - discriminates against short jobs since any short jobs arriving after long jobs will have a long waiting time.
(ii) Round-Robin - treats all jobs equally (giving them equal bursts of CPU time) so short jobs will be able to leave the system faster since they will finish first.
(iii) Multi-Level Feedback Queues - discriminate very favourably toward short jobs since it works similar to the round robin algorithm.






Q3 What effect does the size of time quantum have on the performance of a round robin (RR) algorithm?



At one extreme, if the time quantum is extremely large, the RR policy is the same as the FCFS policy. If the time quantum is small, it must be large with respect to context switch, otherwise overhead is too high.






Q4 What advantage is there in having different quantum sizes on different levels of a multi-level feedback queuing system ?



The advantage is that the short jobs will have highest priority if they are shorter than the initial quantum. This serves them fast and frees the CPU to concentrate on longer jobs.
The jobs that are pushed to the next level (lower priority), now can be given more time than the initial quantum since the goal is to run as many programs as fast as possible with minimal delays to other programs.
Therefore, by increasing the quantum with the level, shorter jobs will be allowed higher priority, and longer jobs will be allowed to run simultaneously with minimum delays.

CS3161 (A) OPERATING SYSTEM PRINCIPLES (DR. LIU WENYIN) (09CS3161_LW) - Answers to Tutorial 4 Questions

Q1 List the four major categories of the benefits of multithreaded programming. Briefly explain each.

The benefits of multithreaded programming fall into the categories: responsiveness, resource sharing, economy, and utilization of multiprocessor architectures.
Responsiveness means that a multithreaded program can allow a program to run even if part of it is blocked. Resource sharing occurs when an application has several different threads of activity within the same address space. Threads share the resources of the process to which they belong. As a result, it is more economical to create new threads than new processes. Finally, a single threaded process can only execute on one processor regardless of the number of processors actually present. Multiple threads can run on multiple processors, thereby increasing efficiency.

Q2 What resources are used when a thread is created ?
How do they differ from those used when a process is created ?

Thread context must be created, including a register set, location for storage during a context switching and a local stack to record the procedure call arguments, return values and return addresses and thread local storage.
Code and data are shared with parent process or parent thread (no loading or allocation of memory necessary).

Process creation similar to thread storage (as above), with extra storage for program instructions and data.
Codes and data may be loaded for every process into the allocated memory and no sharing with other processes.


Q3 What is a thread pool and why is it used?

A thread pool is a collection of threads, created at process startup, that sit and wait for work to be allocated to them. This allows one to place a bound on the number of concurrent threads associated with a process and reduce the overhead of creating new threads and destroying them at termination.

Q4 What are the differences between user-level threads and kernel-support threads ?

User-levels thread have no kernel support, so they are very inexpensive (in terms of resources demand) to create, destroy, and switch among threads do not cause interrupt to CPU.

Kernel support thread are more expensive (in resources) because system calls are needed to create and destroy them and the kernel must schedule them to share access to CPU. They are more powerful because they are independently scheduled and block individually.

CS3161 (A) OPERATING SYSTEM PRINCIPLES (DR. LIU WENYIN) (09CS3161_LW) - Answers to Tutorial 3 Questions

Q1 What is PCB? What information are usually stored in PCB?

PCB Stands for Process Control Block.

Process State
Program Counter
CPU Registers
CPU Scheduling information
Memory management information
I/O Status
Accounting information



Q2 Explain the concept of a context switch.

Whenever the CPU starts executing a new process, the old process's state must be preserved. The context of a process is represented by its process control block. Switching the CPU to another process requires performing a state save of the current process and a state restore of a different process. This task is known as a context switch. When a context switch occurs, the kernel saves the context of the old process in its PCB and loads the context of the new process scheduled to run.


Q3 Explain the main differences between a short-term and long-term scheduler.

The primary distinction between the two schedulers lies in the frequency of execution. The short-term scheduler is designed to frequently select a new process for the CPU, at least once every 100 milliseconds. Because of the short time between executions, the short-term scheduler must be fast. The long-term scheduler executes much less frequently; minutes may separate the creation of one new process and the next. The long-term scheduler controls the degree of multiprogramming. Because of the longer interval between executions, the long-term scheduler can afford to take more time to decide which process should be selected for execution.



Q4 We can describe much of processor management in terms of process state transition diagrams, such as:

Run 2 1 3 4 Wait Ready (Blocked)

(i) Give one example of "event" that causes each of the mark transitions ?
(ii) 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 also. Under what circumstances could transition 3 by one process immediately cause transition 1 by another process ? List all similar situations.


Q4 Process State Transitions

(i) Transition 1 - Last process completed or blocked, another process on the ready queue will be allocated the CPU for execution (Dispatch).
Transition 2 - Preemptive scheduling system
Transition 3 - Process requests an I/O operation
Transition 4 - I/O device completion, process joins the ready queue.

(ii) Process Transitions :
Process request I/O operation - When a process make an I/O service request (Transition 3), when the I/O device is not available at that time, it will go through a transition from run state to wait (blocked) state. At the same time another process on the ready queue will be allocated the CPU for execution (Transition 1) during that time.

Process exceeded the CPU allowance, completed execution or abortion in error condition (Transition 2), another process dispatch to use the CPU (Transition 1).

EE3120 (B) MP & ASSEMBLY LANGUAGE PROG (02EE3120) Assignment 2 Solution

Assignment 2 Solution 2008/9
Question 1 (34 marks)

Answer 1(a)(i)In asynchronous serial transmission, the transmitter's clock and receiver's clock are not synchronized. In order toreceive data correctly, it is necessary to define a protocol on how the data are packed, how many bits constitute acharacter, and when the data begins and ends. Generally, this is done by placing a character between start and stopbits as shown in the following figure. This is called framing.Framing ASCII “A”(41H)When a start bit is received, the receiver will delay a fixed amount of clock cycles which is roughly equal to thehalf period of the data bit width, then sample the data line at roughly the middle of the data bit. If the clockfrequencies for the transmitter and receiver ends are close enough, this provides highly reliable data reception.However, both parties must agree upon the same number of data bits and parity bits in a frame.[5 marks]Answer 1(a)(ii)In 8-bit UART variable mode, the shift clock is derived from the system (x'tal frequency) clock through a series ofdividers shown in the figure below. First the system oscillating frequency will be divided by 12. Timer 1 whichhas to be programmed into 8-bit auto reload model is the second stage of clock division. The dividing constant isdetermined by the value stored in TH1 register. The overflow clock is further divided by 2 if the SMOD bit in thePCON register is 0, otherwise no division is result. Finally, the clock will be divided by 16 before entering into theserial port shift clock. The baud rate can be computed according to the formula:Baud rate =2SMOD32 12 (256-TH1)osc × f× ×Assuming system clock is 11.0592MHz and SMOD=0, for a value of TH 1=253 (i.e., -3 in 8-bit sign integer), thebaud rate is20 11.0592 10632 12 (256-253)× ×× × =9600[6 marks]Answer 1(a)(iii)Main:Continue:Wait:Forever:Sting:Answer 1(b)(i)ORG 0200HMOV DPTR, #StringMOV TMOD, #20HMOV THl,#-24MOV SCON, #50HSETB TR1CLR AMOVC A, @A+DPTRJZ ForeverMOV SBUF, AJNB TI, WaitCLR TIINC DPTRSJMP ContinueSJMP ForeverORG 0400HDB "City University of Hong Kong", 0END; load DPTR with String address; Timer 1, 8-bit auto reload; 1200 baud; 8-bit UART variable; start Timer 1; Read character of Sting»; write to serial port; wait for TI to set; wait TI; increase pointer; continue to transmit next char; do nothing[8 marks]Vector-table approach to interrupt handling is to assign a fixed location in program memory for storing the jumpvector for each interrupt source. When an interrupt happens, processor will finish the current instruction and savethe PC value on stack and then jump to the corresponding location according to the interrupt source. Generally, ajump instruction to the starting address of the interrupt service routine (ISR) will perform. In the case of 8051,there are six interrupt sources including RESET. We can place a LJMP ISR_Address instruction in thecorresponding location. For example, the following instructions put a jump vector for timer 0 interrupt:ORG 0000BHLJMP Timer1_ ISRTimerl1_ISR:ORG 0100H............RETISince the gap between interrupt vectors (except RESET) is eight bytes, we can put the interrupt service routinedirectly in the jump vector location if the size of its ISR is less than or equal 8 bytes. This helps to speed upinterrupt handling for fast real time response.Interrupt ROM Location (Hex) Pin[5 marks]Flag ClearingReset 0000 9 AutoExternal hardware interrupt 0 (INTO) 0003 P3.2(12) AutoTimer 0 interrupt (TFO) 000B AutoExternal hardware interrupt 1 (INT1) 0013 P3.3(13) AutoTimer 1 interrupt (TF1) 001B AutoSerial COM interrupt (RI and TI) 0023 Programmer clears it.Answer 1(b)(ii)ORG 0000H ; Reset vectorLJMP Main;ORG 000BH ; Timer 0 interrupt vectorCPL P2.1 ; toggle P2.1 for square wave outputRETI ; return from ISR;ORG 0023H ; Serial port interrupt vectorLJMP Serial ; jump to serial ISRRETIMain: ORG 0030HMOV P1,#OFFH ; make P1 an input portMOV TMOD, 22H ; timer 0 and 1 are 8-bit auto reloadMOV TH1,#-12 ; 1200 baud rateMOV SCON, #50H ; 8-bit UART with REN enableMOV THO, #-46 ; period for 10 kHz square waveMOV IE, #92H ; enable serial and timer 0 interruptsSETB TR1 ; start timer 1SETB TRO ; start timer 0Back: MOV A, P1 ; read data from Port 1MOV SBUF, A ; write it out to serial portSJMP Back ; loop indefinitely;ORG 0100H ; serial ISR locationSerial: JB TI, Trans ; jump if tx interrupt otherwise rxinterruptMOV A, SBUF ; get the received dataMOV P0,A ; and write it to P0CLR RI ; clear RI (non auto-cleaning)RETI ; return from ISRTrans: CLR TI ; clear TI (non auto-cleaning)RETI ; return from ISREND[10 marks]Question 2 (34 marks)Answer 2(a)ALE is the address latch enable signal output from the 8051 family of microcontrollers. It is a pulse for latching the low-order byte of taccesses to external memory or I/O. Because the low-order byte address (AO-A7) is time-multiplexed with the data (DO-D7) on the phyAD7). A latch, e.g. 74LS373, can be used to latch the address (AO-A7), while data bus (DO-D7) will be available after the addrefollowing circuit can be used. The advantage of using multiplexed bus in 8051 is to save a number of physical pin sfor the chip to codevices. However, by doing so, the speed of external access will be reduced because address and data are multiplexed on the sameaddress has to be latched first, then come the data.[6 marks]Answer 2(b)(i)ROM with an address range 0000 - 3FFF has a size of 16 kbytes. EPROM with an address range 0000 -1FFF has a size of 8 kbytes; RAM with an address range COOO - DFFF has a size of 8 kbytesROM chip required is 1 EPROM chip required is 1 RAM chiprequired is 2[5 marks]Answer 2(b)(ii)[11 marks]Answer 2(b)(iii)

EE3120 (B) MP & ASSEMBLY LANGUAGE PROG (02EE3120) Quiz 3 Solution

Quiz 3 (Total 60 marks)

1.

Show the stack and stack content for the following code:

003B 120300 LCALL DELAY
003E 80F0 BACK: SJMP BACK ;keep doing this
0040
0040 ;----------------------this is the delay subroutine
0500 ORG 500H
0500 DELAY:
0500 7DFF MOV R5,#0FFH ;R5=255
0502 DDFE AGAIN: DJNZ R5,AGAIN ;stay here
0504 22 RET ;return [10 marks]

Ans:
Stack /Stack Content

003B 120300 / 09 / 00 3E
003E 80F0 /07
0040 /?
0040 /?
0500 /09 /00 3E
0500 /09 /00 3E
0500 7DFF /09 /00 3E
0502 DDFE /09 /00 3E
0504 22 /07


2. Find the value (in hex) loaded into TH in each of the following.
(a) MOV TH0,#110
(b) MOV TH0,#-30
[10 marks]
(a) 6EH

(b) E2H


3. Given the LCD command write routine COMNWRT. Assume connections P2.1 = RS, P2.2 =R/W, P2.3 = E, write i) a program to call the display the data and ii) a subroutine to display the data (iii) the data "Hello" is checked again its completion of write by a busy flag connected to P2.7. Use the instruction MOVC.
.
[20 marks]
Ans:

MAIN:
MOV DPTR, #MYDATA
HERE:
CLR A
MOVC A, @A+DPTR
JZ DONE
ACALL DISPLAY_DATA
INC DPTR
SJMP HERE
DONE: SJMP DONE [10 marks]

DISPLAY_DATA:
ACALL READY
MOV P1,A ; port 1 fort DATA
SETB P2.1 ;RS=1 FOR Control DATA
CLR P2.2 ;R/W=0 FOR Control WRITE
SETB P2.3 ;H-TO-L FOR Control Enable
CLR P2.3
RET
READY:
SETB P2.7
CLR P2.1
SETB P2.2
BACK:
CLR P2.3
SETB P2.3
CLR P2.3
JB P2.7, BACK
RET [10 marks]

;P2.7=INPUT TO READ BUSY FLAG
;RS=0
;R/W=-1 FOR READ
ORG 300H
MYDATA: DB "Hello",0

ORG 400H
COMNWRT:
MOV P2,A
CLR P2.1
CLR P2.2
SETB P2.3
CLR P2.3
RET

4. Program Timer 1 to be an event counter. Use mode 2 and display the decimal count on P2, P1, and P0 continuously. Set the initial count to 55.
Ans:
MOV TMOD, #60h ; 0110 0000 [timer 1 c/t = 1 time 1 =1]
MOV TL1, #-55 ; count value
MOV TH1, #-55 ; preload
SETB P3.5
AGAIN: SETB TR1
BACK: MOV A, TL1
ACALL CONVERT
JNB TF1, BACK
CLR TR1
CLR TF1
SJMP AGAIN [10 marks]
;--This will convert from, binary (hex)
;to decimal and send each digit to the port
CONVERT:
MOV B,#10
DIV AB
MOV P0,B
MOV B,#10
DIV AB
MOV P1,B
MOV P2,A
RET [10 marks]

[20 marks]

EE3120 (B) MP & ASSEMBLY LANGUAGE PROG (02EE3120) Tutorial 1 solution

Chapter 1 Introduction
1. (a) 4
(b) 4
(c) 4
(d) 1048 576, 220
(e) 1024K
(f) 1073 741 824, 230
(g) 1 048 576K
(h) 1024M
(i) 8388608, 8192K
2. 1 million pages
3. (a) 589824 bytes
(b) 576 bytes
4. Data bus is bidirectional, address is unidirectional.
5. PC (Program Counter)
6. ALU
7. Address, control and data
8. EAstands forExternalAccess.WhenEAis 0, itwill access the externalmemory.
9. ALE is being usedwhen the external accessmode is being activated, i.e.EA=0. If aROM
is being accessed, a read operation will be needed, so PSEN is used to activate the ROM
andALEis usedtoactivate the address latchinorder tolet the address get into theROM.

EE3120 (B) MP & ASSEMBLY LANGUAGE PROG (02EE3120) Assignment 1 Solution

Question 1 (25 marks)
(a) The 8051 microprocessor is classified as an 8-bit microprocessor. In the controlsignals there are three control signal pins ALE/PROG, PSEN and EA. What are thefunctions of these pins?[6 marks]Ans:ALE/PROG -􀃆Address Latch Enable/ Program Pulse; it is for latching the low byte ofthe address during accesses to external memory. This pin is also the program pulseinput (PROG) during Flash programming.PSEN -􀃆 Program Store Enable; it is the read strobe to external program memoryEA -􀃆 External Memory Access; EA must be strapped to GND in order to enable thedevice to fetch code from external program memory locations starting at 0000H upto FFFFH. [2 each total 6 marks](b) Indicate the source addressing modes of the following 8051 assembly instructions andexplain the operation of each instruction with a suitable diagram:i) MOVC A,@A+PCii) ADD A, R0iii) MOV DPTR,#1200[9 marks]Ans: i) MOVC A,@A+PC is index addressing mode (or code indirect addressing); loadthe content of the effective address stored at PC + value in Accumulator to theAccumulatorii) ADD A, R0 is direct (register) addressing; new content of accumulator is the sum ofold content of accumulator and value stored in register R0iii) MOV DPTR,#1200 is immediate addressing where value of DPTR is loaded with deciamal value of 1200.[1 for address mode and 2 for explanation each and total 9 marks](c) Explain the difference between DB and EQU assembly directives, which one actuallygenerates code?[6 marks]Ans: DB is define byte value and EQU is assigning constant.DB generates codes and EQU does not.[ 2 each total 6 marks](d) Explain the use of subroutine. Describe its process of operation. [4 marks]Ans:⇒ If the same instruction sequence is being used repeatedly, a subroutine is used andcalled by the main program as many times as needed.[1 marks]The operations are⇒ A call to subroutine causes a jump to the address where the subroutine is located andafter executing the subroutine, the program resumes operation at the next instruction(in main program) after the call⇒ The return address must be stored so that the main program can resume after it returnsfrom subroutine⇒ To do this, the stack area of internal RAM is used to automatically store this returnaddress[one each and total 3 marks and max4 marks](a) Explain the mechanism of a stack and describe how a stack is implemented in an8051 microprocessor. Explain how the stack can be used for storing localvariables within the subroutine. What are the advantages of using a stack instoring local variables?[7 marks]Ans:The stack is the memory area that used for storing the return address and all the usedregisters’ contents and the mechanism is based on first in last out when a routine isbeing called.[2 marks]The stack is used in the following steps:⇒ The stack is accessed by a Register SP (stack pointer) which points to the lastused location of the stack.⇒ The default location of is at address 07⇒ SP can be relocated by assigning value with an 8 byte address e.g. MOV SP,#30H⇒ The SP is not only used to access and stack and it points to the last used locationof the stack. The programmer must aware of the largest size of the stack andprevents the stack overflow, i.e. overwritten useful data.[4 marks]The advantages for storing local variables are:⇒ Allow additional temporarily store of registers’ values to avoid modificationswhen manipulation will change registers’ values⇒ Allow restorationof register values when manipulation is restated.[2 marks][1 each total 8 marks](b) Supposing an 8051 microcontroller is used. Show the contents of the stack andstack pointer after execution of the instruction for each line of the followingprogram.ORG 0MOV SP,#90HMOV R4,#1EHMOV R3,#DBHMOV R2,#10HPUSH 4PUSH 3PUSH 2CLR AMOV R2,AMOV R3,APOP 2POP 3POP 4[7 marks]Ans:INSTRUCTIONS SP afterexecution oftheinstructionContents ofthe stackORG 0 07H ?MOV SP,#90H 90H ?MOV R4,#1EH 90H ?MOV R3,#DBH 90H ?MOV R2,#10H 90H ?PUSH 4 91H 1EHPUSH 3 92H DBHPUSH 2 93H 10HCLR A 93H 10HMOV R2,A 93H 10HMOV R3,A 93H 10HPOP 2 92H DBHPOP 3 91H 1EHPOP 4 90H ?[0.5 each total 7 marks](c) Write an 8051 assembler subroutine to search for the maximum value in a tablewith 10 entries. The subroutine should be called by passing the table address andtable size via stack. The returned maximum value can be passed via register. Askeleton C program for your reference is shown below:#define SIZE 10short int table[SIZE] = {3,1,7,4,9,10,2,5,6,8} ;short int max ;// In the main program, the function is called as shown:max = findmax(table, size) ;// This is the findmax functionshort int findmax(short int t[], int s){ // subroutine program body is in here}[10 mark]Ans:ORG 100SIZE EQU 10FINDMAX: MOV Max, #0 ;clear maxMOV DPTR,Table ; assign table pointerMOV R0,#SIZE ;CounterCLR A ; clear AMOV R2,A ; clear R2 stores indexLOOP: MOV A, R2 ; update indexMOV R1, @A+DPTR ; get current data from tableMOV A, Max ; max stores the resultSUB A, R1 ; calculate Max - current dataJNC POSITIVE ; jump if result is positive or 0MOV Max,R1 ; update max if negativePOSITIVE: INC R2 ; increase indexDJNZ R0,LOOP ;repeat all dataORG 200 ;store max resultMax: 0ORG 210 ; store table dataTable: DB 3,1,7,4,9,10,2,5,6,8[0.5 each total 10 marks]

EE3120 (B) MP & ASSEMBLY LANGUAGE PROG (02EE3120) Quiz 2 Solution

Quiz 2 (total 60 marks)

1. Compile and state the contents of each ROM location for the following data.
ORG 100H
MYDAT_1: DB "EE3210"
MYDAT_2: DB "Spring"
MYDAT_3: DB "12-2-10"
[10 marks]

Ans:
0100 1 ORG 100H [1 mark]
0100 45453332 2 MYDATA__1: DB "EE3210" [3 marks]
0104 3130
0106 53707269 3 MYDATA 2: DB "Spring" [3 marks]
010A 6E67
010C 31322D32 4 MYDATA_3: DB "12-2-10" [3 marks]
0110 2D3130


2. In the 8051, which register bank conflicts with the stack? What is the size of the stack pointer (SP) register?
[10 marks]
Ans: Register bank 08 conflicts with the stack. [5 marks]

SP size is 8 bits. [5 marks]


3. Explain what is the difference between these two instructions.
(a) MOV A0H,#10H (b) MOV @R0 , #10H ;if R0=A0H
[10 marks]

Ans:
(a) Puts 10h in the address A0h of the SFRs (which is P2) [5 marks]
(b) Write 10h into the address A0h which is referred as memory [5 marks]

4. Assuming the use of bank 1, find at what RAM location each of the following lines stored the data.
(a) MOV R4,#16H (b) MOV R1,#20H (c)MOV R3,#24H (d) MOV R7,#12H
[12 marks]
Ans:
Bank 1 location from 08-0F; i.e. R0 locates at 08 and R7 locates at 0F

(a) MOV R4,#16H will write to RAM location 0C
(b) MOV R1,#20H will write to RAM location 09
(c) will write to RAM location 0B
(d) will write to RAM location 0F [3 each total 12 marks]

5. Find the contents of register A after each of the following instructions,
MOV A,#60H
ANL A,#36H
[8 marks]
Ans:
MOV A,#60H Accumulator A stores 60H [4 marks]
ANL A,#36H Value A will operate an “ANL” with 36, ie 0110 0000 (60) and 0011 0110 (36) = 0010 0000 and get 20. [4 marks]


Write a program to get 8-bit data from P0 and send it to ports P1 and P2.
[10 marks]
Ans:

ORG 0000h [1 marks]
MOV A, #0FFH[2 marks]
MOV P0, A[2 marks]
MOV A, P0[1 marks]
MOV P1, A[1 marks]
MOV P2, A[1 marks]
HERE: SJMP HERE[1 marks]
END[1 marks]

EE3120 (B) MP & ASSEMBLY LANGUAGE PROG (02EE3120) - Quiz 1 solution

Quiz 1 Solution (total 60 marks)
1. If a given computer has a total of 16 megabytes of memory, how many bytes (in decimal) is this? How many kilobytes is this? [10 marks]

Ans:
Let 2^n = 16M=16x10^6 [2 marks]
n log 2 = log 16 +6 log 10
n = (log 16 +6 )/log 2
= 23.93 [2 marks]
Round n to the nearest integer = 24 [2 marks]
In decimal 2^24 = 16,777,216 bytes [2 marks]
In kilobyte 2^24 = 16,777,216 /1024 =16,384 kilobytes [2 marks]

2. A given mass storage device such as a hard disk can store 1 gigabytes of information. Assuming that each page of text has 50 rows and each row has 40 columns of ASCII characters (each character = 1 byte), approximately how many pages of information can this disk store? [20 marks]

Ans:
Let 2^n = 1G=1x10^9 [2 marks]
n log 1 = log 1 +9 log 10
n = (log 1 +9 )/log 2
= 29.897 [2 marks]
Round n to the nearest integer = 30 [2 marks]
In decimal 2^30 = 1,073,741,824 bytes [2 marks]
Page no. m = = 1,073,741,824 /50x40x1 byte = 536,870.912 [6 marks]
Truncate m = 536,870 pages [6 marks]

3. In a given byte-addressable computer, memory locations 20000H to 7FFFFH are available for user programs. The first location is 20000H and the last location is 7FFFFH. Calculate the following:(a) The total number of bytes available (in decimal)(b) The total number of kilobytes (in decimal) [20 marks]

Ans:
Start address is 20000H and end address 7FFFFH. [5 marks] Total locations available = (7FFFF-20000 +1)H =(5FFFF +1)H =60000H [5 marks]

a) Total number of byte in decimal 60000H= 393216 [5 marks]

b) Total number of kilobyte in decimal (393216/1024) = 384K [5 marks]

4. What EA stands for? What does it mean when it is inputting a ground signal? [10 marks]

Ans: EA stands for External Access. [5 marks]
When EA is 0, it will access the external memory. [5 marks]

EE 2000 Logic Circuit Design, Semester A, 2007/08, Tutorial 2

Level 1
Question 1: Complete the following table by encoding the decimal number 215 in the following format. Please show the bit configuration and count the number of bits used.





Question 2: Gray Code
(a) Convert the binary numbers “1101001” to gray
(b) Convert the gray code “11001100111” to binary


Question 3: Find and correct the error in the following code sequence. Assume odd-parity has been used.


Level 2
Question 4: An interesting application of the 2 of 5 Code is the U.S. Postal Service bar code (ZIP code). The bar code is not the same as what we learnt in lecture.

Decimal	USPS bar code	Decimal	USPS bar code
0	11000	5	1010
1	11	6	1100
2	101	7	10001
3	110	8	10010
4	1001	9	10100

Each digit is represented by 5 bars. 0 is printed as a short bar while 1 is printed as a long tall bar. The ZIP code appears between two tall bars called frame bars which serve to define the beginning and ending of the bar code. A final check sum digit is also included.

(a) Can you guess the ZIP code?
(b) Can you guess the usage of the check sum digit?


Question 5: There are many ways to represent decimal digits on computers. For the weighted code, you have learnt 8421 code, 5421 code and 2421 code. The numbers in the code name indicated the weights of each digit. Can you guess how the (8, 4, -2, -1) code looks like?
(a) Please complete the following table

Question 6: Design a 4-bit unit-distance code for representing the ten decimal digits (i.e. 0, 1, 2, … 9) that has the property that the code words for any two digits only differ by one bit. (Hints: Gray code is not appropriate since decimal 0 (0000) and decimal 9 (1101) differs by 3 bits)

Question 7: The following block of data is received from the transmission system with a vertical parity system. Horizontal parity is to be odd; vertical parity is to be even. An all-1s is EOB.

(a) Find any parity failure
(b) Correct the error, if possible
(c) Is it possible to have three bits in error? If yes, please show several possible locations.

EE 2000 Logic Circuit Design - Semester A, 2007/08 - Tutorial 1

EE 2000 Logic Circuit Design,
Semester A, 2007/08
Tutorial 1
Week 2 (12th September, 2007)
The questions are divided into two levels. Level 1 is the basic level question. You should
be able to answer them after completing the lecture. Level 2 is the advanced level
question. You may have to take a research before answering them. Please be prepared
before the tutorial.
Level 1
Question 1: Complete the following table by converting the below numbers to decimal,
binary, octal and hexadecimal number systems.

Decimal	Binary	Octal	Hexadecimal
27	11011	33	1B
237.25	11101101.01	355.2	ED.4
250.8	1111 1010.1100 1100…	372.6314 6314…	FA.CC…

Question 2:
(a) What is the largest binary number that can be obtained with 16 bits?
(1111 1111 1111 1111)2

(b) What is its decimal equivalent?

 2¹⁵ + 2¹⁴ + … + 2¹ + 2⁰ = 2¹⁶ – 1 = 65535

Question 3: Find the 1's and 2's complements of the following 8-digit binary numbers:

(a) 0010 1010
1101 0101 (1’s complement)
1101 0110 (2’s complement)

(b) 1111 1111
0000 0000 (1’s complement)
0000 0001 (2’s complement)


Question 4: Perform the arithmetic operations (-128) + (-1) in binary using

(a) 8-bit signed 2's complement representation for negative numbers

-128 = 1000 0000;
-1 = 1111 1111;
(-128) + (-1)
= 1000 0000 + 1111 1111
= (1) 0111 1111
Discard carry, we get 0111 1111
(Result incorrect. Overflow because –ve + -ve becomes +ve)

(b) 9-bit signed 2’s complement representation for negative numbers
Does overflow happen? Why?

-128 = 1 1000 0000;
-1 = 1 1111 1111;
(-128) + (-1)
= 1 1000 0000 + 1 1111 1111
= (1) 1 0111 1111
Discard carry, we get 1 0111 1111 (= -129)
(No overflow as –ve + -ve gives a –ve number)


Level 2
Question 5: Please calculate a + b, a - b, a · b, and a / b for the pair of binary numbers a
= 10101 and b = 1011 without converting to decimal (Show your work and the carries)

A = 10101, B = 1011

  11110

   10101

+)  1011

 100000 a + b = 100000

01010

 10101

-) 1011

   1010 a - b = 1010 (You can get the same result if using 2’s complement)

      10101

x)     1011

10101000

              0

    101010

      10101

11100111 a · b = 11100111

                 01

1011 ) 10101

             1011

               1010 a / b: quotient = 1, remainder = 1010

Question 6: Determine the value of x if (211)x = (152)8.


(211)x = (152)8
2 · x2 + 1 · x + 1 = 1 · 82 + 5 · 8 + 2
2x2 + x – 105 = 0
(2x + 15)(x – 7) = 0
∴ x = 7 (x must be a positive integer so cannot be -7.5)


Question 7: Formulate a simple procedure for converting base-4 numbers directly to
hexadecimal number. Use the procedure to convert (12321)4 to base 16. (Hints: 42 = 16)

Partition the digits into groups of 2 each (one hex digit = 2 base-4 digits)

Add necessary 0s to the left and right

Replace each group of base-4 digits by the hex equivalent

So, (12321)₄

= (01 23 21)₄ (Note: 23₄ = 2·4¹+ 3·4⁰ = 11 = B₁₆)

= (1 B 9)₁₆

Question 8: In the lecture, we only discuss the r’s-complement and (r-1)’s-complement
of an integer number. Find the 1’s complement and 2’s complement of the following
fractional binary numbers.
(a) 010.11

1’s complement: 2³ - 010.11 - 2^-2 = 101.00

                                2’s complement: 2³ - 010.11 = 101.01

(b) 11011.100

1’s complement: 2⁵ - 11011.100 - 2^-3 = 00100.011

                                 2’s complement: 2⁵ - 11011.100 = 00100.100