7 Department of Computer Science and Engineering - SVNIT, Surat 21 CS ie B.Tech. Ill - Semester - V - End Semester Examination, December- 2023 ¥ 7 i Course: Operating Systems (CS-301) ' fate: 05-12-2023 Time: 09-30 AM - 12-30 PM Marks: 50 Insteuctions: Figs othe otro right inccate tha marirum marks ofthe expecve question Q1 Answer the following: oe a, Discuss user space thread and kernel space thread in Linux. b._ Explain (i) Atomic operation and Spin-lock synchronization mechanism (il) Hard Link vs Soft link and Named Pipe in Linux c Draw a unified process state diagram showing the functionality of Long term, Short term, and Medium term scheduler. Q2_ Answer the following: ‘a. Forthe following code, assume initial values of flag(i] and flag{j] are False. 03 dof dof flagfi] = true; flag[j] = true: turn = while (flag(i] && turn critical section critical section flag{i} = false; flag{j] = false: remainder section remainder section J while (true); J while (true): “The above solution satisfies all the necessary requirements of the critical section problem’. Prove or disprove with proper justification, . Suppose that we have the following resources: A.B, C and threads T1, T2, T3, and T4, The 04 total number of each resource is: ‘Total —] Further, assume that processes have the A_ B Cc + following maximum requirements and 12 9 12 current allocations: Thread | Current Maximum 1D Allocation. A_[B [c ja [B |c Th 2_[1 [3 |4 {3 [4 TZ 112 (3 [5 [3 [3 73 s [4 [3 [eo |4 |3 m™ 12 11 [2 [4 {a [2 (1) Is the system potentially deadlocked (Le. unsafe)? In making this conclusion, you must show all your steps, intermediate matrices, ete. (ai) Assuming the allocations in (a), suppose that T1 asks for 2 more copies of A. Can the system grant this or not? Explain. (ii) Assuming the allocations in (a), what is the maximum number of additional copies of resources (A, B, and C) that TI can be granted in a single request without risking deadloc: Explain. Q3_ Answer the following: ‘a. Consider the following two threads, to be run concurrently in a shared memory (all variables 04 are shared between the two threads): Threvd A ThreadB | Assume a single-processor system, that 75:94) {| for G=0:]<5:J#4) { | load and store are atomic, that x is x2x+2: initialized to 0 before either inread star's. pp and that x must be Iescied into a repister before being incremented (and stored back to memory afterwards). The following questions consider the final value of x ater both threads have completed.seneme stud Qe Qs 6 (0) Give a concise proof why xs15 when both threads have completed. (ii) Give a concise proof why x#1 when both threads have completed. (ii))Suppose we replace ‘x=x+2’ in Thread B with an atomic double increment OPeration atomiciner2(x) that cannot be pre-empted while being executed. What are all the posible final values of x? Explain. (iv1What needs to be saved and restored on a context switch between two threads in the same Process? What if the two threads are in different processes? Be explicit. b. Consider three processes, all arriving at time zero, with total execution times of 10, 20 and 30 units, respectively. Each process spends the first 20% of execution time doing I/0 (reads the input data); the next 70% of time doing computation, and the last 10% of time doing 1/0 again (prints the results). The operating system uses a shortest remaining compute time first scheduling algorithm and schedules a new process either when the running process gets blocked on 1/0 or when the running process finishes its compute burst. Assume that all 1/0 operations can be overlapped as much as possible. For what percentage of time does the CPU remain idle?(show steps for your answer) a. (i) What is a process's context and what are the main steps involved in context switching? (ii) When can a process enter the Zombie state? How can it come out of it? b. Consider the following solution for the Producer-Consumer problem that uses two binary semaphores n and 5, initialized to @ and 1 respectively. Comment on the correctness of the solution. PRODUCER CONSUMER In the producer code, explain the dof dof impact of exchanging wait(Full) H/oroduce an item —_wait(empty); with wait(mutex), wait (Full) wait(mutex); i, In the consumer code, explain the wait(mutex); //Consume item in buffer mpact of exchanging wait(mutex) //place in buffer signal(mutex); with wait(empty). signal(mutex); signal(full); signal (Empty); J while(true) J while(true) Explain: (i) Why RAID 0 increases read performance but decreases fault tolerance? (ii) How RAID 1 increases both read performance and fault tolerance (surviving any single fault) at the cost of doubling disk usage? b. Explain with diagram Intel Core i7 page table translation scheme as discussed in class. In Linux 05, file system uses Inode data structure to store the attribute of file. (1) What is difference between Inode Table and File Allocation Table? (it) Where Inode of afile get stored in the disk? Where the Inode table get stored in the disk? Where the FAT get stored in the disk? (iif) How can you design a fault tolerant Inode table and FAT of a file system? Give an example of such file system, a. © A hard disk having 1000 cylinders, numbered from 0 to 999. The drive is currently serving a request at cylinder 143, and the previous request was at cylinder 125. The queue of pending requests in FIFO order is 86,450, 903, 714, 248, 509, 22, 750, and 130. What is total distance that the disk arm moves to satisfy all the pending requests, for each of the following disk scheduling algorithms? (1) SCAN (ii) LOOK. b. Explain with example belady’s anomaly with reference to page replacement algorithm, Discuss various 1/0 Buffering techniques with merits and demerits. 03 of of 03 03 04 04 04 o4Date: 04-10-2023, Department of Computer Science and Engineering - SVNIT, Surat B.Tech. Ill - Semester ~ V - Mid Semester Examinations, September - 2023 Course: Operating Systems (CS-301) Marks: Time: 02-00 PM - 3-30 PM Instructions: Figures to he extreme right indcate ihe maximum marks of he especbve queston Q1 Answer the following: ‘What is meant when saying that a scheduling algorithm could result in starvation? Clearly mention b, © the algorithms that could result in starvation. ‘When can a process be called as CPU bound process and 1/0 bound process? Explain why it ‘makes sense to give an /O-bound process higher priority for the CPU than a CPU-bound process. Consider the following cade segment( Assume required header files are included while running the aden : int main (void) ¢ for (int =2; i<=5; i++) { fork(); , Printf (“ATTEND CLASSESIn"); } . How many times “ATTEND CLASSES" is printed by the above code? (Justify your answer) Five jobs to be executed on a single processor system which arrives at time 0 in the order A, B, C, , E. Their CPU burst time’requirements are 4, 1, 8, 1, and 2 time units respectively. What is the average completion time under round robin scheduling with time slice of ane time unit? Justify your answer. Q2_ Answer the following: a3 a (i) Show the process state transition diagram assuming that thie operating system follows a non- preemptive CPU-scheduling policy {ii) Consider that a process P1 is running on the CPU and a process P2 is waiting for a disk read. Clearly list step by step what events need to happen and what actions need to be taken before P2 uns again. Assume that there are no other processes in the system. Consider the following set of processes, with length of the CPU bursts given in milliseconds. Assume Lower priority number indicates higher priority Priority No. Process Arrival Time Duration 0 o 5 4 1 2 6 2 2 4 3 1 3 wa 5 3 Draw the Gantt chart and illustrate the execution of these processes under the following scheduling algorithms a. _Non-pre-emptive priority scheduling b. Pre-emptive priority scheduling c. Compute the (a) average waiting time (b) average response time for each case Consider three CPU-intensive processes, which require 30, 20 and 10 time units and arrive at times 0, 2 and 6, respectively. How many context switches are needed if the operating system implements a pre-emptive shortest remaining time first scheduling algorithm? Assume that time units are integral and do not count the context switches at time zero and at the end . The address sequence generated by tracing a particular program executi paging system with 100 bytes per page i: 0100, 0200, 6430, O49, 0810 O6S0" osb6: Dae 0220, 0240, 0260, 0320, and 0470. Suppose that the memory can store only one page and ffxi the address which causes a page fault then the bytes from addresses x to x + 99 are loaded on the memory. How many page faults will occur? Justify your answer, A computer uses 46-bit vitual address, 32-bit physical address, and a three-fevel paged page table organization. The page table base register stores the base address of the first-level table (71), which occupies exactly one page. Each entry of T1 stores the base address of a page of the second-level table (72), Each entry of 2 stores the base address of a page of the thidlevel table" (T3). Each entry of T3 stores a paye table entry (PTE). The PTE is 22 bits in size, Tro Processor used in the computer has a 1 MB 16-way set associative virally indexed phystzall lagged cache, The cache block size is 64 bytes. What is tne size of @ page in KB in ine computer? Justify your answer. . co nT Q4 Answer the following: a. b. c. Explain with diagram Working-Set Model. ‘What is Page-Buffering Algorithm? Explain its function in brief. Describe how an Inverted Page Table (IPT) is used to transiato a vitual address into @ physical address. 7 30, 08 09Sardar Vallabhbhai National Institute of Technology, Surat Department of Computer Science and Engineering B Tech Il (Computer Science and Engincering)) - Fourth Semester €S208 - Automata and Formal Languages End Semester Examination, May 2023 Time: 2:00 to 5:00 Date: 02-05-2023 Marks: 50, Instructions + Please start the answer to each question on new page ONLY of your answer sheets + Please write your correct exam no without fil onthe answer sheets as wel asthe question papers. * lease be brief and to:the:point inthe attempting the answers to the theory questions. Unnecessary and Lnjustified elaboration will not fetch more marks + Bloom's Taxonomy level and Course outcome mapping - Understanding ~ CO1, Apply ~ CO2, Analysis (003, Evaluate - COs and Design - COS Q.1 State, with justification, whether or not each of the following languages (6) over an 5 = fa, b} is regular (Answer any three). co1 (H) i. {amb | m,n en} co2 (H) {w | wis not a palindrome} The set of al strings such that in each initial substring the number of occurrences of the letter a and the number of occurrences of the letter b differ by no more than 2. iv. The set of all strings that end in a and do not contain the substring bb. Q.2 Show the equivalence of the following regular expressions: (6 (0+ 1+ 00)" = (0+4)* (b) 2° (011)* [2° (011)*]* = (1 +021)" co1(H) (0+1+00)'=(0+1)" co2 (H) (11+ 111)" =(121°)" Q.3 Answer the following. [6] {a) Design Moore machines for the following and show the output using an CO2 (M) example, cos (M) i. calculate residue mod 4 for each binary string treated as binary integer. ji, for the input from (0 + 1 + 2)'which prints the residue module 5 of the input treated as a ternary (base 3 with digits 0, 1, 2) number. (b) Design Mealy machines that give a 1 as its output if and only if thedeast Last « three digits are all 1’s assume that 5 = (0,1}=O (input and output symbol set is same). Q.4 Answer the following. te) fal. DFA given by co2 (M) oj} 4 cos (H) a | a | a a {a | a “alas | a Give all the regular expressions Ry, Ry", and Ry. Think qi state as if it were the state with integer number i. Give a regular expression for the language of the automaton. (b) Construct a DFA equivalent to the following regular expressions Page 1 0f2as fa) (b) a6 fa) (b) a7 (a) (b) as (a) (b) Co) i. (oeayt(o0#12)(0+3)" i, 10+(0+22)0"2 Answer the following. (6) Consider the pushdown automaton M coi [M] K= {s, f), F= {fh 2 = (a, b), =e, ab co3 (M] B= Ms, a2) (a 6, B,€, (52M) (5. DG ed (UE, 9, a) Geel) (FP COS (H] ael > > J |. Trace all possible sequences of transitions of M on input aba. Show that aa, abb ¢ L(M), but baa, bab € L(M). ‘Analyse the transitions and describe L(M). Construct a push down automata (PDA) that recognizes the language =(K,2, 6, 6, 5, & F), where LM) = {a'blct | i, j, k20 and i+j =k). Design the transition diagram and give seven tuples specification for the PDA. Answer the following. {e) co1[M) Describe pumping lemma for the regular set. Using pumping lemma prove that the language L = {a°b! | n>=0}is not regular. coz (MI Convert the following grammar to an equivalent push down automata (PDA). 5 > @AS | BAB |aB, A bBB| aS |a, B > bA| a What is the language recognized by the resultant PDA? ‘Answer the following. {8} Give the equivalent context free grammar for the following push down C01 [M] automata (PDA) M = {(q, p}, {0, 1}, (X, 2}, 6, 4, Z @) 02 (M) 5 (a, 0, 2) = ((a, X2)}, 5 (4, 0, X)= {Ca XX)}, 8 (a, 4, X) = (Ca, XI} C04 [M] 5 (a, €, X) = (lp, €)}, 8 (P, 2, X) = {(P, X00} 8 (P, €, X) = {(P, €)} 5 (p, 1,2) = {(p, €)}- What is the language generated by the resultant grammar? Consider the PDA M = {{qo, 41,4, {0, 1}, (20, X}, 6, a0, Zo, {ar} 5 (qo, 1, Zo) = fqo, XZo)b, 5 (ao, 2, X) = {( a, XX)}, 5 (ao, 0, X) = (aa, X)} 5 (qu, 1, X) = {(ax, €)}, 6 (a1, & Zo) = {(a1, Z0))- i. What is the language recognized by the given PDA? ii, Construct an equivalent PDA acceptance by empty store N(M) which will recognize the same language. Answer the following (Any Two). te) With suitable example illustrates the following: C01 [M] i, Turing machine as a computational machine. 02 [M] ji, Turing machine as an input output device. cos [H] Design Turing machine for palindrome strings over {a, b}. i. Show an instantaneous description for ababa. Show an instantaneous description for baab. Design a Turing machine to accept strings of the language defined as L = {a?*b" | n>=0}. Show an instantaneous description for aaaabb. Page 20f2Date: 07/03/2023 Q ®) By counter evimple dis » t shat National Institute of Technology (SVNIT)» ‘Nenartnient af Computer Sefence and Engineering hareh. H Computer Science and Engineerit IVs ‘Subject: CS208 - A\ n and Formal Languages ‘Mid Semester Examination, March-2023 dar ViNabl Marks: 30 1 Answer the fom¥ings {061 rove the following statement: Sum of square of two integers is always a perfect squire. I where n> 1. tant = (at)! P(n): H+ 2-2! +. ng induction method prove that (08) Q2 Answer the following. a) ) @) ta? Construct the minimum inite state automat je. Here the D What is te language accepted by the following fi in the following transition tabl state equivalent DFA to the finite automata given final state, lo|0fta||> |rolea|>-| =|9|=\m]So}=\>| -| la|s|alololu|>|| 2} Design a minimal DFA that accepts all the strings over Y= to Kimod 4). si the strings over = (a,b), where number of b’s is congruent Construct the minimal DFA that accepts all the strings of a's and bs ae ern \gs of a's and b’s where every string start with b and Page 1 of 2o—seurat Qs a) » 9 a ° Q4 a) » Answer the following. (Any Five) 10) Construct the finite state automata M that recognizes the languaee generated f the following regular rammar G having production rules: 4 . Swalaa|bBle, Aadlas, B~ cle re a of linear grammar Define the condition for near grammar (restricted CRG) and give suitable exampk es and language generated by it. i ings over 5.7 (Gb) and test Give a context free grammar which generates the odd palindrome strings over EF (a,b) and test whether the given grammar is ambiguous oF not. , in the gmmar given Find the leftmost derivation and rightmost derivation for string W = aabbabba in the gammar give below. $+ aB|bA, A alas |bAd, B > b| bs |aBB. What are the closure properties of context free language (CFL)? Prove by contradiction te CEUs are not closed under the complement operations. Convert the given context free grammar to Chomsky normal form S>ABlaB, A-aable, B-~bbA 106) Answer the following. les $ + SaSbS | SbSaS | € ‘ 's and b’s will be generated by this grammar. Consider the grammar with the following production rul Prove by induction, any string having equal number of a Convert the following grammar G into GNF. ‘S->XA|BB,B = bISB,X > b,A >a Page 2 of 23. 4. 5. 6 i i LT. - Surat uter Science and Engineering Department, S.V.N- Beant CSE) 4” semester - End Semester Examination - May 2023 " Microprocessor and Interfacing Techniques (CS202) Date: 3" May 2023 ‘Time: 2-00 P.M. to 5-00 P.M. ‘Max Marks: 50 Instructions: Wie your B Tech. Admission No. and other details clearly on the Answ ‘answering the questions full marks of the respective question toa ne question on the new page ONLY in your answt facing circuit with 8085 to interface 12K ROM using d 1/0 interfacing with two 8255s using single 3 to 8 jer book and Question paper. Be precise and clear in Figure to the right carry Please start the answer for DOK Design and draw complete memory inter 4KXa IC and 2K RAM using 1KX8 IC an decoder with suitable start addresses. | b. Design and explain Multiplexed Scan Display for displaying DCSE using 8085 and 8255 ‘Assume suitable port addresses and write complete routine for the same. c. Enlist the merits and demerits of /O-mapped and Memory-mapped V/O. a. Draw and explain 8255 Mode-1 (output) with control and status signals. b. Design an I/O interfacing circuit to have counter 2 address as FCH and write 8085 ALP to generate square wave of 2ms time period using counter 0 of 8253 for input frequency of 1MH,. c. Explain with example Interrupt priority for 8085 interrupts. (Clearly mention IVT, Input signal, etc.). @ Provide a brief overview of working of 8279 keyboard/display interface and describe its functional pin diagram. a¢_Explain with example: XTHL, SPHL, PCHL instructions of 8085. Discuss with example RST n instruction of 8085. a/ Write 8085 assembly language program (ALP) to generate all Fibonacci numbers(in Decimal not in Hex), which can be represented using 2 digit packed BCD, and store them in successive locations starting from location 4000H OR a. Write 8085 ALP to convert an 8-digit packed BCD number stored in locations 4000H to 4003H to equivalent binary number. Store the result in locations 4004H to 4007H. ie) Name the command word and indicate the contents of the command word that is required to configure the 8259 for the following operations: i, ICW4 is going to be issued. ‘Several 8259s are to be used in the system, il, The address interval is required to be 4 bytes. iv. The IRo.7 requests are to be level triggered. v. The LS byte of interrupt vector address for IRo to be COH. -&/ Draw and Explain 8086 flag register. . Explain following instructions in 8086 with example and their effect on flag: LDS, SCAS and LAHF.. c&. Differentiate NEAR & FAR CALL, NEAR RET & FAR RET a. Write an 8086 ALP to compute nCr using recursive procedure. Assume that ‘n’ and ‘ris non- negative integers (8-bits) entered through keyboard. — OR {@ Write an 8086 ALP to check for palindrome for the given line through keyboard. Implement macro to take line input through keyboard. Implement procedures (i) for generating the reverse of the given line input and (i) to check for palindrome. Display output message/s using macro. bé. Enlist 8086 Interrupt Priority Structure. Describe action taken when 8086 Interrupts occurs and _/ explain in detail type-4 interrupt of 8086. / Enlist parameter passing techniques for procedure and discuss any one with 8086 ALP. 04 03 02 03 03 03 03 03 02 03 02 03 03 03 04 os 03DOCSE - S.V.NATIONAL INSTITUTE OF TECHNOLOGY - SURAT tn B.Tech. Il - Semester — IV - Mid Semester Examination 13" March ~ 2023 Microprocessor and Interfacing Techniques (CS202) Seat No, U21C S10 [Time: 9:00 - 10:30 Hours} [Total Marks: 30] a. Draw and explain 8085 flag register. 03 b. Explain the function of (i) READY (ii) HOLD pins of 8085. 02 & Explain with example SHLD, DAA, XTHL instructions of 8085, iS Draw and explain schematic to generate de-multiplexed address and data bus along with | 03 read/write control signals for memory and VO. Considering the following segment of 8085 ALP, draw and explain timing diagram for CALL | 03 instruction, 2000 LX! SP,FFF3H 2003 MVI A,10H 2 2009 PUSH PSw 200B CALL ABC(ABC is located at S5FFH) ‘Write an 8085 Assembly language Program (ALP) for the following a. A set of sixteen data bytes stored in the memory location starting at 4450H. Write an 8085 ALP | 03 to check each data byte for bits Ds and D;. If De or Dy is 1, reject the data bytes; otherwise, store the data bytes at memory locations starting at 4460H. Also count the total number of rejected bytes in a given set. b. Write an 8085 ALP to implement subroutine to generate rectangular wave with 200 us on-period and 400 us off-period. Assume 2MHz clock frequency. ¢. Write an 8085 ALP to design a down-counter to count from 99 to 0 in BCD with 2sec. delay | 04 (assume delay is available) between each count. Display the count at port A (Pa) of 8255 with port address as D7H. Design an interfacing circuit using 8255, 74138(3 to 8 decoder) and gates to have Pa address as D7H. Also mention Pa, Ps and Control register addresses for the above circuit, g ‘@. Discuss with complete program to implement RST 6 as a breakpoint facility 03 b._Explain with example RIM instruction of 8085. 2Computer Networks (C8303) Mid: Dept. of Computor Sei §. V. National Institute of Technology, Surat “Academic Year: 2023-2024 mester Exam y2ics (OO Date: October 06, 2023 Student Roll No Marks: 30 Duration: 90 Minutes ———————~ Answer the following questions. 1. Analyze different types of delay in packet-switched networks. Give suitable examples. (05 Marks} 2. Explain the five layers of Internet protoc ‘ol stack. (a) Give an example to discuss how the message is communicated from the source to the destination via a link-layer switch and the router. (b) Name the specific layers of Internet protocol stack implemented by devices such as source, destination, router, and link-layer switch. (c) Discuss which part of the packet is created/read/modified by a specific layer of the Internet protocol stack of the specific device. (08 Marks} 3. Compare persistent and non-persistent connections with suitable examples. (04 Marks} 4. “It is often desirable for a Web site to identify users, either because the server wishes to restrict user access or because it wants to serve content as a function of the user identity.” Design a mechanism such that web sites can use it to keep track of their users. Analyze your mechanism to show that it serves the purpose, [05 Marks] 5. Write client and server programs to implement client server application in Python. Use TCP. Briefly explain your programs. (08 Marks}Computer Networks (CS303) End-semester Exam Dept. of Computer Science and Engineering S. V. National Institute of Technology, Surat Academic Year: 2023-2024 Date: December 07, 2023____________ Student Roll No: _Uale$L00. Marks: 50 Duration: 90 Minutes SU Answer the following questions. 1. Explain the five layers of Internet protocol stack. Give an example to discuss how the message is communicated from the source to the destination via a link-layer switch and the router. [6 Marks] 2. Explain the types DNS servers. Give an example to query the DNS record from the DNS servers. Assume that the intarmediate servers do not cache the DNS records. Show both iterative and recursive ways to query the DNS databases. (6 Marks] 3. Design and analyze the reliable data transfer protocol for the transport layer. Justify your choices. (6 Marks] 4. What is the difference between IPv4 and iPv6 header? Explain the header fields changed in IPV6 and the reasons behind the sae. (6 Marks} 5. How does the ‘Traceroute program collect information about routers? With the help of ICMP messages, explain the functioning of the Traceroute program, [6 Marks} 6. Design a decentralized routing algorithm /pseudocode to find the shortest path between the source and destination. Give suitable example considering your algorithm. Analyze the time complexity. (6 Marks} 7. Ina shared broadcast channel, how to coordinate the channel access by multiple sending and receiving nodes? Briefly explains the following. [6 Marks} (a) Channel partitioning protocols (b) Random access protocols (c) Taking-turns protocols 8. Suppose you download a webpage. Which networking protocols are involved and why, when, and how do they provide the required functionality? Write your answer in sequence of steps. Furst step is already included. Complete the rest. (Hint: Protocols involved are DIP, UDP, TCP, IP’ Btheryet, DNS; Ape, HTTP, BGP, OSPR, etc) 1. Your operating system creates a DHCP request message. 2. ** The remaining steps you have to write... (08 Marks}