GATE CSE 2004 | Question: 63

Question

Consider the following program segment for a hypothetical CPU having three user registers $R_1, R_2$ and $R_3.$ $$\begin{array}{|l|l|c|} \hline \text {Instruction}  &  \text{Operation }& \text{Instruction size} \\&& \text{(in words)} \\\hline \text{MOV $R_1,5000$} & \text{$R_1$} \leftarrow  \text{Memory$[5000]$}& \text{$2$} \\\hline\text{MOV $R2,(R1)$} & \text{$R2$} \leftarrow  \text{Memory$[(R_1)]$}& \text{$1$} \\\hline \text{ADD $R_2,R_3$} & \text{$R2$} \leftarrow  \text{$R_2 + R_3$} & \text{$1$} \\\hline \text{MOV $6000,R_2$} & \text{Memory$[6000]$} \leftarrow  \text{$R_2$} & \text{$2$} \\\hline \text{HALT} & \text{Machine Halts} & \text{$1$} \\\hline \end{array}$$Consider that the memory is byte addressable with size $32$ bits, and the program has been loaded starting from memory location $1000$ (decimal). If an interrupt occurs while the CPU has been halted after executing the HALT instruction, the return address (in decimal) saved in the stack will be

• A. $1007$
• B. $1020$
• C. $1024$
• D. $1028$

Comments

HALT – It is a machine control instruction. It invokes unconditional jump with starting address of HALT as Target Address.

ex:- L1 : JMP L1

While execution of this instruction CPU enters into a infinite loop so reset operation required to run the new program.

I1 : 1000 – 1007

I2: 1008 – 1011

I3: 1012 – 1015

I4: 1016 – 1023

I5: 1024 – 1027  

 So, as we can see by diagram 1024 will be pushed onto the stack.

Answer : C                                             

---

Consider that the memory is byte addressable with size 32 bits

Why are we considering the CPU WORD SIZE to be 32 bits from this above statement?

The term “WORD SIZE 32 bits” is nowhere mentioned.

We could have just thought of these 32 bits to be address bits of the memory.

Is the language used in the question standard?

Moreover it is said that the memory is said to be byte addressable.

The above quoted sentence simply does not convey the complete meaning to me.

Please help me...

---

Question has a word missing – “Consider that the memory is byte addressable with ‘word’ size 32 bits”.

---

@iamalokpandey, any single standard resource which supports whatever you have written about the HALT instruction. It seems like coming from some coaching notes where teacher made self-concepts. NO Single Standard Resource contains it Or supports it.

HLT Or Halt:

Stops instruction execution and places the processor in a HALT state. An enabled interrupt (including NMI and SMI), a debug exception, the BINIT# signal, the INIT# signal, or the RESET# signal will resume execution. If an interrupt (including NMI) is used to resume execution after a HLT instruction, the saved instruction pointer (CS:EIP) points to the instruction following the HLT instruction.

When a HLT instruction is executed on an Intel 64 or IA-32 processor supporting Intel Hyper-Threading Technology, only the logical processor that executes the instruction is halted. The other logical processors in the physical processor remain active, unless they are each individually halted by executing a HLT instruction.

The HLT instruction is a privileged instruction. When the processor is running in protected or virtual-8086 mode, the privilege level of a program or procedure must be 0 to execute the HLT instruction.

This instruction’s operation is the same in non-64-bit modes and 64-bit mode.

Source: https://www.felixcloutier.com/x86/hlt 

A special instruction, HALT, tells the CPU to stop executing altogether. If the instruction is the "halt" instruction, break out of the fetch/execute loop and exit the program. 

HALT	Halt; stop execution of instructions.

Source: https://people.engr.tamu.edu/djimenez/classes/312-fall21/hw6/hw6.html 

During the fetch-decode-execute cycle, the PC would get incremented to the next instruction. The program instructions are executed sequentially until the HALT instruction which stops the program.

Source: https://www.cs.uni.edu/~fienup/cs041s11/lectures/Supplement_MARE_AL.pdf  

Usually after an instruction is executed, the program counter is increased by 1, and the whole "fetch-execute" cycle is repeated to execute the next instruction in memory. This process continues until a halt instruction is executed. 

The other CPU state consists of the program counter (or PC), which has 12 bits and holds the address of the next instruction to be executed, the run-flag, which is one bit and indicates whether the computer is running (1) or halted (0), and the arithmetic error bit (or AEB), which indicates whether there has been an arithmetic overflow error. 

halt -- stops execution (sets the run flag to 0) 

If the instruction that is executed is a halt instruction, all that happens is that the run flag (rf) is set to 0, and execution halts. 

Source: https://zoo.cs.yale.edu/classes/cs201/fall_2023/lectures/Architecture.html 

Program execution halts only if the machine is turned off, some sort of unrecoverable error occurs, or a program instruction(HALT) that halts the computer is encountered. (Source: William Stallings)

Answer 1

Option is D.

Word size is $32$ $bits$ ($4$ $bytes$). Interrupt occurs after execution of HALT instruction NOT during,  So address of next instruction will be saved on to the stack which is $1028$.  

(We have $5$ instructions starting from address $1000$, each of size $2, 1, 1, 2, 1$ totaling $7$ words $= 7 *4 =28$ $bytes$). 

$1000+ 28 = 1028$,

$1028$ is the starting address of NEXT Instruction .

After HALT instruction CPU enters a HALT state and if an interrupt happens the return address will be that of the instruction after the HALT. 

 References :

1.  https://x86.puri.sm/html/file_module_x86_id_134.html [ X86 Instructors Manual ]
2. http://electronics.stackexchange.com/questions/277735/what-happens-if-the-interrupt-occurs-during-the-execution-of-halt-instruction
3. https://en.wikipedia.org/wiki/HLT_(x86_instruction)

Comments

 kindly tell me how this 1028 came ?????????????????63. Word size is 32 bits (4 bytes). Interrupt occurs after execution of HALT instruction NOT during,  so address of next instruction will be saved on to the stack which is 1028.

---

@Shimpy: Explained now.

@csegate2 No, that is not correct.

---

What will be the return address to the stack if interrupt occurs during an instruction (like during halt)

I think in that case also processor will complete this ins. First

---

In that case there will be an infinite loop , how it can be solved

---

What is the value of PC at the end of execution of above program??

---

Just tell me one thing!

when the halt instruction is under execution, PC value will be the address of the next instruction which must be: 1028 right! As HALT according to user point of view is STOP but from system point of view it is the jump to the same instruction. Now after the execution of the HALT instruction even the PC value will be at 1024 then how can you conclude the PC value is 1028 as after execution of HALT it never get incremented?

---

HALT is infinite loop , then how it will break if no interrupt occurs . Consider this , you meant a program is in HALT forever , no matter what happens . This is not possible

---

1024 SEEMS TO BE CORRECT ANSWER. WHY IS 1028 SELECTED HERE???

---

Why are we considering that memory is byte addressable even when word size is given.

---

Unless it is explicitly mentioned we always consider byte addressable

---

How is 1028 correct? It must be 1024. Since interrupt will be checked only after the execution of the current instruction and by then PC value would change to 1024 and it will be pushed.

---

Given that Memory is

• Byte Addressable . ie one location takes one byte .
• one word is 4B => one word takes 4 memory locations

Instruction	Starting address	Ending address
I1  (2 words)	1000	1007
I2 (1 words)	1008	1011
I3 (1 words)	1012	1015
I4 (2 words)	1016	1023
I5 (1 words)	1024	1027

The next Instrction after I5 is stored at 1028

---

exactly that is my point, since halt instruction, while executing will make pc value 1024 from 1028 as halt means I5: JMP I5

so in the pc would be 1024.

---

After HALT has been fetched from memory, Program counter will increment itself to point to next instruction. Now that HALT occupied addresses 1024, 1025, 1026 and 1027 (since HALT is 4 bytes long), program counter will be incremented to 1028 to point to next intruction (while HALT is executing, HALT needn't be completed for PC to be incremented). When an interrupt comes, we push the value inside the program counter as the return address onto the stack. This value inside PC is 1028 and that is the return address. I do not see where the confusion is.

---

@Bikram Sir, perfect now :))

---

If the interrupt occurs during the ADD instruction, what will be the return address pushed? Would it be 1000+(2+1+1)*4 = 1016? Please tell if I am correct or not.

---

Correct @shraddha

---

@Bikram Sir I am still confused, In one of the comments above ::

After HALT has been fetched from memory, Program counter will increment itself to point to next instruction. Now that HALT occupied addresses 1024, 1025, 1026 and 1027 (since HALT is 4 bytes long), program counter will be incremented to 1028 to point to next instruction (while HALT is executing, HALT needn't be completed for PC to be incremented). When an interrupt comes, we push the value inside the program counter as the return address onto the stack. This value inside PC is 1028 and that is the return address. I do not see where the confusion is.

But, we know that an interrupt is processed only after the execution of an instruction and not in between.So, when interrupt occurs halt must have been executed atleast once.Thus,incrementing the value of PC to 1024 from 1028.

Please clarify where I am thinking wrong!!

---

@ VS 

Read below reference and see how it match with the statement said in Question !

From the x86 instruction manual ---- > If an interrupt  is used to resume execution after a HLT instruction, the saved instruction pointer  points to the instruction following the HLT instruction. [1]

here in this question they also asked  ..If an interrupt occurs while the CPU has been halted AFTER executing the HALT instruction,

then the return address (in decimal) saved in the stack will be starting address of next instruction that is 1028 .

References:

[1] https://x86.puri.sm/html/file_module_x86_id_134.html

 

---

@Bikram Sir Thanks a lot :).Now clear !!

---

@shraddha priya  and @VS

If the interrupt occurs during the ADD instruction ,  then the return address pushed is 

1000+(2+1+1)*4  = 1000 + 16 = 1016

 Program has been loaded starting from memory location 1000 in decimal .

For  MOV R1, 5000       location is 1000-1007 as it is 2 words 

MOV R2(R1)                  location is  1008-1011  , it is 1 word 

ADD R2, R3                   location is  1012-1015  , it is 1 word 

so next memory address which is going to store in stack is 1016 .

---

@Bikram sir ..Thanks for the explanation !!

---

sir in the question it says the memory is word addressable with size 32 bits.so we have to multiply 1 word with 4bytes and hence the result 1016  ?

---

yes correct.. 1 word = 32 Bits.

---

after fetching halt instruction, PC value will become 1028. but while executing halt instruction pc value again goes to 1024 because HALT is unconditional jump to itself, so if interrupt comes while executing halt instruction, pc value will be 1024.

please verify?

---

 Akash Mittal  

Read my all above comments in this answer.. 

.If an interrupt occurs while the CPU has been halted AFTER executing the HALT instruction, then the return address (in decimal) saved in the stack will be starting address of next instruction that is 1028 .

---

But there is no next instruction after HALT @Bikram sir as mentioned...Hence by default the meaning of HALT as we know is looping within itself so next address will be same as that of HALT as there is no instruction after HALT in the given question..

Hence 1028 address means there is some next sequential instruction after HALT which is a wrong claim with respect to the given question..

Hence 1024 should be correct..

---

Notice --> "Interrupt comes during the halt instruction" and "Interrupt comes after halt instruction", both are same. Because interrupt are served only after execution of current instruction.

---

@ Habibkhan Bhai,

Answer may very depending according to architecture. But i think in most of the cases PC value will not remain 1024 if interrupt comes otherwise it will go in infinite loop. 

---

What should be the final answer 1024/1028

---

Consider that the memory is byte addressable with size 32 bits

with *word of size 32 bits.

---

@Bikram sir when memory is word addressable of size 32 bits. Then why are you treating it as byte addressable?

---

Lots of speculation as to which is correct : 1024 or 1028. 

Read this on x86 instruction set reference

http://c9x.me/x86/html/file_module_x86_id_134.html

Answer should be 1028

---

nice link abhisek

---

now it is clear how 1028 will be the answer thanks bikram sir

---

https://retrocomputing.stackexchange.com/questions/6729/uses-for-the-halt-instruction

---

what is the ans in answer key of gate paper.

---

I am still confused! after reading all these references:

The references says:

If an interrupt (including NMI) is used to resume execution after a HLT instruction, the saved instruction pointer (CS:EIP) points to the instruction following the HLT instruction.

But in the question it is no where mentioned that this interrupt is used to get the system out of the halted state! it just says that interrupt occurs after the execution of halt instruction. what if it is some other interrupt?

and what if the reset instruction is used to get the system out of the halted state?

---

@Bikram sir,

Although I understood the solution. The link you provided as a reference is not working.

---

https://x86.puri.sm/html/file_module_x86_id_134.html

https://electronics.stackexchange.com/questions/277735/what-happens-if-the-interrupt-occurs-during-the-execution-of-halt-instruction/277744

https://stackoverflow.com/questions/16597784/machine-instructions-and-memory-address

http://archive.is/W0oDB

---

In above question if halt occurred during the execution of the halt instruction than what could be the return address pushed onto the stack

---

During execution of HALT instruction value of PC again 1024(starting address  of HALT)..So during execution of HALT instruction interrupt occurs,So PC value 1024 must pushed into the stack,not 1028. This is exception for HALT instruction

---

I think in both cases the answer should be same as the interrrupt is processed only after the execution of current instruction

---

https://x86.puri.sm/html/file_module_x86_id_134.html

In this link, Instruction resumes is the sense of executing interrupt service routine, which is not in the actual instruction sequence or program.after servicing interrupt service routine, it will come back again at halt instruction.

we're wrongly interpreting the Instruction resumes term.

ans should be 1024.

---

1024 should be correct answer

---

I have a doubt. Memory starting address is given in decimal and size of total instruction is in bytes,then how decimal and bytes addition is taking place?

---

Refer my comment HERE for several standard resources supporting the answer 1028. NOT a Single Standard Resource supports 1024. Students who are giving answer are following some poor coaching notes, not following the standard resources. 

Answer 2

answer should be 1024 because consider the case where halt statement is succeeded by some AlU instructions now if you'll store the next intruction as the return address when an interrupt occur while executing halt then in that case after executing the interrupt program will execute those alu instruction which should not happen as program is already halted

Comments

True it is a valid case.

---

@Sneha negi Ma'am, I understood from your answer that after HALT is executed no other instruction should be executed. But the below statement in the question 

after executing the HALT instruction, the return address will be...

Doesn’t it means now HALT has been executed and now its time for another instruction ?

Thanks in advance ! 

Answer 3

It is clearly mentioned that HALT instruction has executed completely.

Now some other instruction just began its fetch at 1028, interrupt came, so it is bit OBVIOUS that 1028 will be the answer,

1007, 1020 are useless options

 

D is the corect answer

Comments

No, HALT instruction changes the Program counter value to 1024, so that program remains halted until it is restarted again, so the PC value will remain 1024 which will be pushed onto the stack

Answer 4

Working of HALT:

HALT instruction stops the execution of a program by changing the PC value to the current instruction program counter value (1028 is replaced with 1024 in this case) so when the HLT instruction is completed, the CPU fetches the instruction from the location specified in PC (PC contains 1024, ie HLT instruction) and increments the PC value to 1028 and does the same thing.

Now the fetched HALT instruction does the same thing again and again ( ie Changing the PC value to 1024 from 1028). It halts the program only from the user point of view, but HALT is simply busy waiting from the CPU point of view. 

So ans is 1024

 

PS: From Chottu’s comment "Interrupt comes during the halt instruction" and "Interrupt comes after halt instruction", both are the same. Because interrupt is served only after execution of current instruction.