Oral Questions 2018

Question 1

Structure of directory entry

Answer 1

The directory entry provides the information needed to find the disk blocks. Depending on the system, this information may be: the disk address of the entire file (with contiguous allocation), the number of the first block (both linked-list schemes), or the number of the i-node. (UNIX V7, ISO 9660)

Question 2

System call “exec”

Answer 2

Command exec in Linux is used to execute a command from the bash itself. This command does not create a new process it just replaces the bash with the command to be executed. If the exec command is successful, it does not return to the calling process.

Question 3

DMA structure

Answer 3

“Direct Memory Address (DMA) contains several registers that can be written and read by the CPU. These include a memory address register, a byte count register, and one or more control registers.

The control registers specify the I/O port to use, the direction of the transfer (reading from the I/O device or writing to the I/O device), the transfer unit (byte at a time or word at a time), and the number of bytes to transfer in one burst.”

Question 4

Advantages and disadvantages of small and big pages

Answer 4

“Small page size advantages:
– It reduces internal fragmentation.
– It will help to allocate small programs consisting of several phases. The smaller the page size is, the less memory will be wasted.

Small page size disadvantages:
– Having many pages means a large page table.
– Transferring a small page takes almost as much time as transferring a large page.
– Small pages use up much valuable space in the TLB.”

Question 5

Conditions for deadlocks

Answer 5

“Four conditions that must hold for there to be a (resource) deadlock:
– Mutual exclusion condition: Each resource is either currently assigned to exactly one process or is available.
– Hold and wait condition: Processes currently holding resources that were granted earlier can request new resources.
– No preemption condition: Resources previously granted cannot be forcibly taken away from a process. They must be explicitly released by the process holding them.
– Circular wait condition: There must be a circular list of two or more processes, each of which is waiting for a resource held by the next member of the chain.”

Question 6

Paging and segmentation

Answer 6

“Paging: To get a large linear address space without having to buy more physical memory.
Segmentation: To allow programs and data to be broken up into logically independent address spaces and to aid sharing and protection.”

Question 7

Scheduling

Answer 7

The part of the OS that makes the choice is called the scheduler, and the algorithm it uses is called the scheduling algorithm.

Question 8

Difference between virtual and physical memory

Answer 8

“– Physical memory is actual RAM, while virtual memory is a memory management technique that creates an illusion to users of a larger physical memory.
– Physical memory is faster than virtual memory.
– Physical memory uses swapping technique, while vitual memory uses paging.
– Physical memory is limited to the size of the RAM chip, while virtual memory is limited by the size of the hard disk. Physical memory can directly access the CPU, and virtual memory cannot.”

Question 9

TLB and Inverted page tables

Answer 9

“TLB (Transition Lookaside Buffer) or associative memory is small hardware device for mapping virtual addresses to physical addresses without going through the page table. When a virtual address is presented to the MMU for translation, the hardware first checks to see if its virtual page number is present in the TLB by comparing it to all the entries in parallel. If a valid match is found and the access does not violate the protection bits, the page frame is taken directly from the TLB (a protection fault is generated otherwise).

Inverted page tables: There is one entry per page frame in real memory, rather than one entry per page of virtual address space, so the size is proportional to physical memory, not the virtual address space. The entry contains a pair (process ID, virtual page address) and refers to a page frame.

Pitfall of inverted page tables: When process n references virtual page p, it is no longer possible to find the physical page by using p as an index into the page table. Instead, we must search the entire inverted page table for an entry (n, p). This search must be done on every memory reference, not just on page faults.”

Question 10

Can the size of virtual memory be less than size of physical memory?

Answer 10

Yes, it can (Suppose 8-GB RAM and 32-bit processor).

Question 11

Segmentation in Intel x86-64

Answer 11

In x86-64 CPUs, segmentation is considered obsolete and is no longer supported, except in legacy mode.

Question 12

Difference between hard links and soft links

Answer 12

“Hard links: A directory may contain several filenames that all map to the same i-node number and thus to the same file in the file system. Unix call these names pointers or links to the file. Hard links are new names for the same i-node. Link count in the i-node keeps track of how many directories contain a name number mapping for that i-node. Hard links cannot be made to a directory. This restriction means that every subdirectory has one and only one parent directory. A hard link and data it links to, must always exist in the same file system.

Soft links: A soft link or symbolic link contains a path to another file or directory and may point to any file or directory. Soft links can cross file systems.”

Question 13

“Structure of i-nodes
Where they are stored?
Protection bits”

Answer 13

“I-node (index-node) is associated with each file, which lists the attributes and disk addresses of the file’s blocks. Each i-node stores the attributes and disk block locations of the object’s data. File-system object attributes may include metadata (times of last change, access, modification), as well as owner and permission data.

Advantages of i-nodes:
– Only i-node for a file which is open must be in memory.
– Requires an array in memory whose size is proportional to the maximum number of files that may be open at once.

I-nodes are stored on disk.

Protection bits tell what kinds of access are permitted. In the simplest form, this field contains 1 bit, with 0 for read/write and 1 for read only. A more sophisticated arrangement is having 3 bits, one bit each for enabling reading, writing, and executing the page.”

Question 14

WSClock algorithm (Page replacing)

Answer 14

An algorithm which is based on the clock algorithm but also uses the working set information. Is widely used in practice since it is simple and provides good performance. The data structure is a circular, initially empty, list of page frames, as in the clock algorithm. As the pages are added, they go into the list to form a ring. Each entry contains the Time of last use field from the basic working set algorithm, as well as the R and M bits.

Question 15

Processes and threads: differences, advantages and disadvantages. Context switch

Answer 15

“Context switch is a procedure that a CPU follows to change from one process to another while ensuring that the tasks do not conflict.

A context switch can be performed entirely in hardware (physical media). Older CPUs, such as those in the x86 series, do it that way. However, most modern CPUs perform context switches by means of software (programming). A modern CPU can perform hundreds of context switches per second. Therefore, the user gets the impression that the computer is performing multiple tasks in a parallel fashion, when the CPU actually alternates or rotates between or among the tasks at a high rate of speed.”

Question 16

Mount table

Answer 16

Mounted table is a table of mounted disks.

Question 17

How Shortest Remaining Time First algorithm estimate how long process will execute?

Answer 17

We should know it in advance.

Question 18

What is FAT?

Answer 18

File Allocation Table

Question 19

“What is i-node? What it contains?
Can we have hard link in different partition?
Can we hard link directory?
Is inode created on soft link?”

Answer 19

“I-node (index-node) is associated with each file, which lists the attributes and disk addresses of the file’s blocks. Each i-node stores the attributes and disk block locations of the object’s data. File-system object attributes may include metadata (times of last change, access, modification), as well as owner and permission data.

A directory may contain several filenames that all map to the same i-node number and thus to the same file in the file system. Unix call these names pointers or links to the file.

Hard link and data it links to, must always exist in the same file system.
Hard links cannot be made to a directory. This restriction means that every subdirectory has one and only one parent directory.

Soft link or symbolic link contains a path to another file or directory and may point to any file or directory.”

Question 20

Compare LRU and NFU algorithms

Answer 20

“LRU (Least Recently Used) algorithm: When a page fault occurs, throw out the page that has been unused for the longest time (not cheap to implement).

NFU (Not Frequently Used): It is software simulation of LRU. NFU requires a software counter associated with each page, initially zero. At each clock interrupt the OS scans all the pages in memory and updates the counter by adding R bit to it. When a page fault occurs, the page with the lowest counter is chosen for replacement.”

Question 21

What is TLB?

Answer 21

TLB (Transition Lookaside Buffer) or associative memory is small hardware device for mapping virtual addresses to physical addresses without going through the page table.

Question 22

Fork and execve

Answer 22

In UNIX, there is only one system call to create a new process: fork, which creates an exact clone of the calling process. After the fork, the parent and the child processes, have the same memory image, environment strings and open files. Usually, the child process then executes execve or a similar system call to change its memory image and run a new program. The child can manipulate its file descriptors after the fork but before the execve in order to accomplish redirection of standard input, standard output, and standard error.

Question 23

Character and block type devices

Answer 23

“Block devices (Hard disks, Blu-ray discs):
– Store information in fixed-size blocks each one with its own address.
– Common block sizes range from 512 to 65,536 bytes.
– Transfers are in units of entire blocks.
– It is possible to read or write each block independently of all the other ones.

Character devices (Printers, Mice):
– Deliver or accept stream of characters, without regard to block structure.
– Not addressable, does not have any seek operation."

Question 24

Aging algorithm (Page replacing)

Answer 24

“Aging algorithm is a small modification to NFU:
– The counters are each shifted right 1 bit before the R bit is added in.
– The R bit is added to the leftmost rather than the rightmost bit.
Another difference is that in aging the counters have a finite number of bits so it is not possible to distinguish pages that were referenced 9 or 1000 ticks ago.”

Question 25

Which signals can not be caught

Answer 25

SIGKILL, SIGSTOP

Question 26

Mapped files

Answer 26

The idea is that a process can issue a system call to map a file onto a portion of its virtual address space. As pages are touched, they are demand paged in one page at a time, using the disk file as the backing store. When the process exits, or explicitly unmaps the file, all the modified pages are written back to the file on disk. If two or more processes map onto the same file at the same time, they can communicate over shared memory. Writes done by one process to the shared memory are immediately visible when the other one reads from the part of its virtual address spaced mapped onto the file. If memory-mapped files are available, shared libraries can use this mechanism.

Question 27

Difference between stdout and stderr

Answer 27

“stdout (standard output): Process writes normal information to this file handle.
stderr (standard error): Process writes error information to this file handle.”

Question 28

Disk scheduling algorithms

Answer 28

“Disk scheduling algorithms:
– FCFS (First-Come, First-Served)
– SSF (Shortest Seek First)
– Elevator algorithm”

Question 29

Cylinder skew

Answer 29

The position of sector 0 on each track is offset from the previous track when the low-level format is laid down. This offset, called cylinder skew, is done to improve performance. The idea is to allow the disk to read multiple tracks in one continuous operation without losing data.

Question 30

Device controller

Answer 30

The electronic component of the I/O device is called the device controller or adapter. On personal computers, it is often a chip on the parent board or a printed circuit card that can be inserted into a PCIe expansion slot. The interface between the controller and the device is often a very low-level one.

Question 31

Difference between mutex and semaphor

Answer 31

“Mutex and Semaphore both provide synchronization services but they are not the same.

Mutex is a mutual exclusion object that synchronizes access to a resource. It is created with a unique name at the start of a program. The Mutex is a locking mechanism that makes sure only one thread can acquire the Mutex at a time and enter the critical section. This thread only releases the Mutex when it exits the critical section. A Mutex is different than a semaphore as it is a locking mechanism while a semaphore is a signalling mechanism. A binary semaphore can be used as a Mutex but a Mutex can never be used as a semaphore.

Semaphore is a signalling mechanism and a thread that is waiting on a semaphore can be signaled by another thread. This is different than a mutex as the mutex can be signaled only by the thread that called the wait function. A semaphore uses two atomic operations, wait and signal for process synchronization.”

Question 32

Scheduling in real time systems

Answer 32

“Time plays an essential role.
Goals: Meeting deadlines (avoid losing data) and Predictability (avoid quality degradation inmultimedia systems)
Categories of the real-time systems: Hard real-time and Soft real-time
Categories of events: Periodic and Aperiodic (Is system schedulable?)”

Question 33

Preemptive and non-preemptive scheduling algorithms

Answer 33

“Nonpreemptive scheduling algorithm picks a process to run and then just lets it run until it blocks or voluntarily releases the CPU. No scheduling decisions are made during clock interrupts.

Preemptive scheduling algorithm picks a process and lets it run for a maximum of some fixed time. If it is still running at the end of the time interval, it is suspended and the scheduler picks another process to run.”

Question 34

TSL, Test Lock, Set Lock

Answer 34

“Mutual Exclusion with Busy Waiting: The TSL Instruction (hardware-assisted approach; works with multiple CPUs)

An instruction like TSL RX,LOCK (Test and Set Lock) reads the contents of the memory word lock into register RX and then sets lock to be a nonzero value. The operations of reading the word and storing into it are guaranteed to be indivisible (the memory bus is locked). Different from disabling interrupts – doing it on processor 1 has no effect at all on processor 2. The first instruction copies the old value of lock to the register and then sets lock to 1. The old value is compared with 0:
– If it is nonzero, the lock was already set by another program;
– Sooner or later it will become 0 and the subroutine returns, with the lock set.

To clear the lock the program just stores a 0 in lock.”

Question 35

I-nodes: Where filename and attributes are located?

Answer 35

Attributes are stored in i-node, but file name and i-node number are stored in directory entry.

Question 36

Memory hierarchy

Answer 36

“– A few megabytes of very fast, expensive, volatile cache memory
– A few gigabytes of medium-speed, medium-priced, volatile main memory
– A few terabytes of slow, cheap, nonvolatile magnetic or solid-state disk storage”

Question 37

Address space

Answer 37

“Address space is a concept that helps solving protection and relocation problems. It is the set of addresses that a process can use to address memory. The address space creates a kind of abstract memory for programs to live in. Each process has its own address space, independent of those belonging to other processes.

Each program has its own address space, broken up into chunks called pages. Each page is a contiguous range of addresses and is mapped onto physical memory. Not all pages have to be in physical memory at the same time to run the program. When the program references a part of its address space that is not in physical memory, the OS gets the missing piece and re-executes the instruction that failed.”

Question 38

File system structure

Answer 38

“File systems are stored on disks. Most disks can be divided up into one or more partitions, with independent file systems on each partition.

Sector 0 of the disk is called the MBR (Master Boot Record) and is used to boot the computer. The end of the MBR contains the partition table which table gives the starting and ending addresses of each partition.

The layout of a disk partition also contains superblock which includes:
– magic number to identify the file-system type;
– number of blocks in the file system;
– other key administrative information.”

Question 39

OS and device controller communication

Answer 39

“Two ways:
– Assembler instructions that are working with the drivers address space
– Memory-mapped I/O”

Question 40

Why each thread has it’s own stack?

Answer 40

Each thread has its own stack that contains one frame for each procedure called but not yet returned from.

Question 41

Minor page fault, Major page fault, Segmentation fault

Answer 41

“– Minor page fault occurs when the page is actually in memory, but not in this process’ page table (it may have been brought in from disk by another process).
– Major page fault occurs if the page needs to be brought in from disk.
– Segmentation fault occurs when the program simply accesses an invalid address and no mapping needs to be added in the TLB.”

Question 42

Magic number

Answer 42

Although technically the file is just a sequence of bytes, the operating system will execute a file only if it has the proper format. It has five sections: header, text, data, relocation bits, and symbol table. The header starts with a so-called magic number, identifying the file as an executable file (to prevent the accidental execution of a file not in this format).

Question 43

“Communication deadlocks

How to solve?”

Answer 43

“Communication deadlock is an anomaly of cooperation synchronization. It is another kind of deadlock can occur in communication systems (e.g., networks), in which two or more processes communicate by sending messages.

Technique that can usually be employed to break communication deadlocks is timeouts. In most network communication systems, whenever a message is sent to which a reply is expected, a timer is started. If the timer goes off before the reply arrives, the sender of the message assumes that the message has been lost and sends it again (and again and again if needed). In this way, the deadlock is broken.”

Question 44

Thin Client

Answer 44

Thin client is a computer that runs from resources stored on a central server instead of a localized hard drive. Thin clients work by connecting remotely to a server-based computing environment where most applications, sensitive data, and memory, are stored.

Question 45

Soft timer

Answer 45

Most computers have a second programmable clock (soft timer) that can be set to cause timer interrupts at whatever rate a program needs. This timer is in addition to the main system timer whose functions were described above.

Question 46

Pipelines

Answer 46

Pipeline is a mechanism for inter-process communication using message passing. A pipeline is a set of processes chained together by their standard streams, so that the output text of each process (stdout) is passed directly as input (stdin) to the next one. The first process is not completed before the second is started, but they are executed concurrently.

Question 47

File system layout

Answer 47

“File systems are stored on disks. Most disks can be divided up into one or more partitions, with independent file systems on each partition.

Sector 0 of the disk is called the MBR (Master Boot Record) and is used to boot the computer. The end of the MBR contains the partition table which table gives the starting and ending addresses of each partition.

Boot sequence:
– BIOS reads in and executes the MBR.
– MBR locates the active partition, reads in its first block, which is called the boot block, and executes it.
– The program in the boot block loads the operating system contained in that partition.

The layout of a disk partition also contains superblock which includes:
– magic number to identify the file-system type;
– number of blocks in the file system;
– other key administrative information.”

Question 48

Page replacement algorithms: FIFO, Second Chance and Clock algorithm

Answer 48

“FIFO algorithm: The OS maintains a list of all pages currently in memory, with the most recent arrival at the tail and the least recent arrival at the head. On a page fault, the page at the head is removed and the new page added to the tail of the list.

Second chance algorithm: We can modify FIFO to avoid the problem of throwing out a heavily used page. It can be done by inspecting the R bit of the oldest page:
– 0: the page is both old and unused, so it is replaced immediately;
– 1: the bit is cleared, the page is put onto the end of the list of pages, and its load time is updated.

Clock algorithm: This algorithm uses approach to keep pages on a circular list and to have a “clock hand” that points to the oldest page. When a page fault occurs, the page being pointed to by the hand is inspected.
– If its R bit is 0, the page is evicted, the new page is inserted into the clock in its place, and the hand is advanced one position;
– If R is 1, it is cleared and the hand is advanced to the next page. This process is repeated until a page with R = 0 is found.”

Question 49

Categories of scheduling algorithms

Answer 49

“Three environments worth distinguishing are:
– Batch systems (Throughput, Turnaround time, CPU utilization)
– Interactive systems (Response time, Proportionality)
– Real-time systems (Meeting deadlines, Predictability)”

Question 50

Process statuses

Answer 50

“The complete list of process states is:

1. The process is executing in user mode.
2. The process is executing in kernel mode.
3. The process is not executing but is ready to run as soon as the kernel schedules it.
4. The process is sleeping and resides in main memory.
5. The process is ready to run, but the swapper (process 0) must swap the process into main memory before the kernel can schedule it to execute.
6. The process is awaiting an event and has been swapped to secondary storage (a blocked state).
7. The process is returning from kernel to user mode, but the kernel preempts it and does a context switch to schedule another process.
8. The process is newly created and is in a transition state; it is not yet ready to run, nor it is sleeping (the initial state for all the processes except process 0).
9. Process executed the exit system call and no longer exists, but it leaves a record for its parent process to collect (the final state of a process).”

Question 51

What is stored in the process table? List 6 items.

Answer 51

Program counter, registers, program status word, pointer to stack segment info, process state, priority, scheduling parameters, process ID, parent process, process group, signals, time when process started, CPU time used…

Question 52

Can we make a soft link to a directory? A hard link?

Answer 52

“Soft link: yes

Hard link: no”

Question 53

Monitors, Barriers

Answer 53

"Monitor is a higher-level synchronization primitive – it is a collection of procedures, variables, and data structures that are all grouped together in a special kind of module or package. Processes may call the procedures in a monitor whenever they want to, but they cannot directly access the monitor’s internal data structures from procedures declared outside the monitor. Only one process can be active in a monitor at any moment. When a process calls a monitor procedure, the first few
instructions of the procedure will check to see if any other process is currently active within the monitor. If no other process is using the monitor, the calling process may enter.

Barriers: Some applications are divided into phases and have the rule that no process may proceed into the next phase until all processes are ready to proceed to the next phase. This behavior may be achieved by placing a barrier at the end of each phase. When a process reaches the barrier, it is blocked until all processes have reached the barrier. This allows groups of processes to synchronize.”

Question 54

Thrashing

Answer 54

Thrashing is a program’s behavior when it is causing page faults every few instructions.

Question 55

Zombie process state

Answer 55

When a process completes, it invokes the exit system call, thus entering the states “kernel running” and, finally, the “zombie” state.