Get questions and answers for Computer Engineering

What are the three main purposes of an operating system?

List the four steps that are necessary to run a program on a completely dedicated machine.

What is the main advantage of multiprogramming?

What are the main differences between operating systems for mainframe computers and personal computers?

In a multiprogramming and time-sharing environment, several users share the system simultaneously. This situation can result in various security problems. a. What are two such problems?
b. Can we ensure the same degree of security in a time-shared machine as we have in
a dedicated machine? Explain your answer.

Define the essential properties of the following types of operating systems: a. Batch
b. Interactive
c. Time sharing
d. Real time
e. Network
f. Distributed

We have stressed the need for an operating system to make efficient use of the computing hardware. When is it appropriate for the operating system to forsake this principle and to “waste” resources? Why is such a system not really wasteful?

Under what circumstances would a user be better off using a time-sharing system, rather than a personal computer or single-user workstation?

Describe the differences between symmetric and asymmetric multiprocessing. What are three advantages and one disadvantage of multiprocessor systems?

What is the main difficulty that a programmer must overcome in writing an operating system for a real-time environment?

Prefetching is a method of overlapping the I/O of a job with that job’s own computation. The idea is simple. After a read operation completes and the job is about to start operating on the data, the input device is instructed to begin the next read immediately. The CPU and input device are then both busy. With luck, by the time the job is ready for the next data item, the input device will have finished reading that data item. The CPU can then begin processing the newly read data, while the input device starts to read the following data. A similar idea can be used for output. In this case, the job creates data that are put into a buffer until an output device can accept them. Compare the Prefetching scheme with the spooling scheme, where the CPU overlaps the input of one job with the computation and output of other jobs.

How does the distinction between monitor mode and user mode function as a rudimentary form of protection (security) system?

What are the differences between a trap and an interrupt? What is the use of each function?

For what types of operations is DMA useful? Explain your answer.

Which of the following instructions should be privileged?
a. Set value of timer.
b. Read the clock.
c. Clear memory.
d. Turn off interrupts.
e. Switch from user to monitor mode.

Some computer systems do not provide a privileged mode of operation in hardware. Consider whether it is possible to construct a secure operating system for these computers Give arguments both that it is and that it is not possible.

Some early computers protected the operating system by placing it in a memory partition that could not be modified by either the user job or the operating system itself. Describe two difficulties that you think could arise with such a scheme.

Protecting the operating system is crucial to ensuring that the computer system operates correctly. Provision of this protection is the reason behind dual-mode operation, memory protection, and the timer. To allow maximum flexibility, however, we would also like to place minimal constraints on the user. The following is a list of operations that are normally protected. What is the minimal set of instructions that must be protected?
a. Change to user mode.
b. Change to monitor mode.
c. Read from monitor memory.
d. Write into monitor memory.
e. Fetch an instruction from monitor memory.
f. Turn on timer interrupt.
g. Turn off timer interrupt.

Give two reasons why caches are useful. What problems do they solve? What problems do they cause? If a cache can be made as large as the device for which it is caching (for instance, a cache as large as a disk), why not make it that large and eliminate the device?

Writing an operating system that can operate without interference from malicious or undebugged user programs requires some hardware assistance. Name three hardware aids for writing an operating system, and describe how they could be used together to protect the operating system.

What are the five major activities of an operating system in regard to process management?

What are the three major activities of an operating system in regard to memory management?

What are the three major activities of an operating system in regard to secondary-storage management?

What are the five major activities of an operating system in regard to file management?

What is the purpose of the command interpreter? Why is it usually separate from the kernel?

List five services provided by an operating system. Explain how each provides convenience to the users. Explain also in which cases it would be impossible for user-level programs to provide these services.

What is the purpose of system calls?

Using system calls, write a program in either C or C++ that reads data from one file and copies it to another file. Such a program was described in Section 3.3.

Why does Java provide the ability to call from a Java program native methods that are written in, say, C or C++? Provide an example where a native method is useful.

What is the purpose of system programs?

What is the main advantage of the layered approach to system design?

What are the main advantages of the microkernel approach to system design?

What is the main advantage for an operating-system designer of using a virtual-machine architecture? What is the main advantage for a user?

Why is a just-in-time compiler useful for executing Java programs?

Why is the separation of mechanism and policy a desirable property?

The experimental Synthesis operating system has an assembler incorporated within the kernel. To optimize system-call performance, the kernel assembles routines within kernel space to minimize the path that the system call must take through the kernel. This approach is the antithesis of the layered approach, in which the path through the kernel is extended so that building the operating system is made easier. Discuss the pros and cons of the Synthesis approach to kernel design and to system-performance optimization.

MS-DOS provided no means of concurrent processing. Discuss three major complications that concurrent processing adds to an operating system.

Describe the differences among short-term, medium-term, and long-term scheduling.

A DECSYSTEM-20 computer has multiple register sets. Describe the actions of a context switch if the new context is already loaded into one of the register sets. What else must happen if the new context is in memory rather than in a register set and all the register sets are in use?

Describe the actions a kernel takes to context switch between processes.

Provide two programming examples of multithreading giving improved performance over a single-threaded solution.

Provide two programming examples of multithreading that would not improve performance over a single-threaded solution.

What are two differences between user-level threads and kernel-level threads? Under what circumstances is one type better than the other?

Describe the actions taken by a kernel to context switch between kernel-level threads.

Describe the actions taken by a thread library to context switch between user-level threads.

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

A CPU scheduling algorithm determines an order for the execution of its scheduled processes. Given n processes to be scheduled on one processor, how many possible different schedules are there? Give a formula in terms of n.

Define the difference between preemptive and nonpreemptive scheduling. State why strict nonpreemptive scheduling is unlikely to be used in a computer center.

Consider the following set of processes, with the length of the CPU-burst time given in milliseconds:

Suppose that the following processes arrive for execution at the times indicated. Each process will run the listed amount of time. In answering the questions, use nonpreemptive scheduling and base all decisions on the information you have at the time the decision must be made.

Consider a variant of the RR scheduling algorithm where the entries in the ready queue are pointers to the PCBs.
a. What would be the effect of putting two pointers to the same process in the ready queue?
b. What would be the major advantages and disadvantages of this scheme?
c. How would you modify the basic RR algorithm to achieve the same effect without the duplicate pointers?

What advantage is there in having different time-quantum sizes on different levels of a multilevel queuing system?

Consider the following preemptive priority-scheduling algorithm based on dynamically changing priorities. Larger priority numbers imply higher priority. When a process is waiting for the CPU (in the ready queue but not running), its priority changes at a rate _; when it is running, its priority changes at a rate _. All processes are given a priority of 0 when they enter the ready queue. The parameters _ and _ can be set to give many different scheduling algorithms.
a. What is the algorithm that results from _ >_>0?
b. What is the algorithm that results from _ < _ <0?

Many CPU scheduling algorithms are parameterized. For example, the RR algorithm requires a parameter to indicate the time slice. Multilevel feedback queues require parameters to define the number of queues, the scheduling algorithms for each queue, the criteria used to move processes between queues, and so on. These algorithms are thus really sets of algorithms (for example, the set of RR algorithms for all time slices, and so on). One set of algorithms may include another (for example, the FCFS algorithm is the RR algorithm with an infinite time quantum). What (if any) relation holds between the following pairs of sets of algorithms?
a. Priority and SJF
b. Multilevel feedback queues and FCFS
c. Priority and FCFS
d. RR and SJF

Suppose that a scheduling algorithm (at the level of short-term CPU scheduling) favors those processes that have used the least processor time in the recent past. Why will this algorithm favor I/O-bound programs and yet not permanently starve CPU-bound programs?

Why does Solaris 2 implement multiple locking mechanisms? Under what circumstances does it use spin locks, semaphores, adaptive mutexes, conditional variables, and readers-writers locks? Why does it use each mechanism? What is the purpose of turnstiles?

Explain the differences in the degree to which the following scheduling algorithms discriminate in favor of short processes:
a. FCFS
b. RR
c. Multilevel feedback queues

List three examples of deadlocks that are not related to a computer-system environment

Is it possible to have a deadlock involving only one single process? Explain your answer.

Consider a system consisting of four resources of the same type that are shared by three processes, each of which needs at most two resources. Show that the system is deadlock free.

Consider a system consisting of m resources of the same type, being shared by n processes. Resources can be requested and released by processes only one at a time. Show that the system is deadlock-free if the following two conditions hold:
a. The maximum need of each process is between 1 and m resources
b. The sum of all maximum needs is less than m + n

Consider the following resource-allocation policy. Requests and releases for resources are allowed at any time. If a request for resources cannot be satisfied because the resources are not available, then we check any processes that are blocked, waiting for resources. If they have the desired resources, then these resources are taken away from them and are given to the requesting process. The vector of resources for which the waiting process is waiting is increased to include the resources that were taken away.
For example, consider a system with three resource types and the vector Available initialized to (4, 2, 2). If process P0 asks for (2, 2, 1), it gets them. If P1 asks for (1, 0, 1), it gets them. Then, if P0 asks for (0, 0, 1), it is blocked (resource not available). If P2 now asks for (2, 0, 0), it gets the available one (1, 0, 0) and one that was allocated to P0 (since P0 is blocked). P0’s Allocation vector goes down to (1, 2, 1), and its Need vector goes up to (1, 0, 1). a. Can deadlock occur? If so, give an example. If not, which necessary condition cannot occur?
b. Can indefinite blocking occur?

Explain the difference between internal and external fragmentation.

Describe the following allocation algorithms:
a. First fit
b. Best fit
c. Worst fit

When a process is rolled out of memory, it loses its ability to use the CPU (at least for a while). Describe another situation where a process loses its ability to use the CPU, but where the process does not get rolled out

Given memory partitions of 100K, 500K, 200K, 300K, and 600K (in order), how would 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?

Why are page sizes always powers of 2?

Consider a logical address space of eight pages of 1024 words each, mapped onto a physical memory of 32 frames.
a. How many bits are there in the logical address?
b. How many bits are there in the physical address?

On a system with paging, a process cannot access memory that it does not own; why? How could the operating system allow access to other memory? Why should it or should it not?

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?
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.)

What is the effect of allowing two entries in a page table to point to the same page frame in memory? Explain how this effect could be used to decrease the amount of time needed to copy a large amount of memory from one place to another. What effect would updating some byte on the one page have on the other page?

Why are segmentation and paging sometimes combined into one scheme?

Describe a mechanism by which one segment could belong to the address space of two different processes.

Explain why it is easier to share a reentrant module using segmentation than it is to do so when pure paging is used.

Consider the following segment table:

Consider the Intel address translation scheme shown in Figure 9.20.
a. Describe all the steps that the Intel 80386 takes in translating a logical address into a physical address.
b. What are the advantages to the operating system of hardware that provides such complicated memory translation hardware?
c. Are there any disadvantages to this address translation system?

Under what circumstances do page faults occur? Describe the actions taken by the operating system when a page fault occurs.

Assume a page reference string for a process with m frames (initially all empty). The page reference string has length p with n distinct page numbers occurring in it. For any page-replacement algorithms,
a. What is a lower bound on the number of page faults?
b. What is an upper bound on the number of page faults?

A certain computer provides its users with a virtual-memory space of 232 bytes. The computer has 218 bytes of physical memory. The virtual memory is implemented by paging, and the page size is 4096 bytes. A user process generates the virtual address 11123456. Explain how the system establishes the corresponding physical location. Distinguish between software and hardware operations.

Which of the following programming techniques and structures are “good” for a demand paged environment? Which are “not good”? Explain your answers.
a. Stack
b. Hashed symbol table
c. Sequential search
d. Binary search
e. Pure code
f. Vector operations
g. Indirection

Assume we have a demand-paged memory. The page table is held in registers. It takes 8 milliseconds to service a page fault if an empty page is available or the replaced page is not modified and 20 milliseconds if the replaced page is modified. Memory access time is 100 nanoseconds.
Assume that the page to be replaced is modified 70 percent of the time. What is the maximum acceptable page-fault rate for an effective access time of no more than 200 nanoseconds?

Consider the following page-replacement algorithms. Rank these algorithms on a five point scale from “bad” to “perfect” according to their page-fault rate. Separate those algorithms that suffer from be lady’s anomaly from those that do not.
a. LRU replacement
b. FIFO replacement
c. Optimal replacement
d. Second-chance replacement

When virtual memory is implemented in a computing system, there are certain costs associated with the technique and certain benefits. List the costs and the benefits. Is it possible for the costs to exceed the benefits? If it is, what measures can be taken to ensure that this does not happen?

An operating system supports a paged virtual memory, using a central processor with a cycle time of 1 microsecond. It costs an additional 1 microsecond to access a page other than the current one. Pages have 1000words, and the paging device is a drum that rotates at 3000 revolutions per minute and transfers 1 million words per second. The following statistical measurements were obtained from the system: 1 percent of all instructions executed accessed a page other than the current page. Of the instructions that accessed another page, 80 percent accessed a page already in memory. When a new page was required, the replaced page was modified 50 percent of the time.
Calculate the effective instruction time on this system, assuming that the system is running one process only, and that the processor is idle during drum transfers.

Consider a demand-paging system with the following time-measured utilizations: CPU utilization 20% Paging disk 97.7% Other I/O devices 5% Which (if any) of the following will (probably) improve CPU utilization? Explain your answer.
a. Install a faster CPU.
b. Install a bigger paging disk.
c. Increase the degree of multiprogramming.
d. Decrease the degree of multiprogramming.
e. Install more main memory.
f. Install a faster hard disk or multiple controllers with multiple hard disks.
g. Add pre paging to the page fetch algorithms.
h. Increase the page size.

Consider the following page reference string:
1, 2, 3, 4, 2, 1, 5, 6, 2, 1, 2, 3, 7, 6, 3, 2, 1, 2, 3, 6
How many page faults would occur for the following replacement algorithms, assuming one, two, three, four, five, six, or seven frames? Remember all frames are initially empty, so your first unique pages will all cost one fault each.
LRU replacement
FIFO replacement
Optimal replacement

Suppose that you want to use a paging algorithm that requires a reference bit (such as second-chance replacement or working-set model), but the hardware does not provide one. Sketch how you could simulate a reference bit even if one were not provided by the hardware, or explain why it is not possible to do so. If it is possible, calculate what the cost would be.

Segmentation is similar to paging but uses variable-sized “pages.” Define two segment replacement algorithms based on FIFO and LRU page-replacement schemes. Remember that since segments are not the same size, the segment that is chosen to be replaced may not be big enough to leave enough consecutive locations for the needed segment. Consider strategies for systems where segments cannot be relocated, and those for systems where they can.

A page-replacement algorithm should minimize the number of page faults. We can do this minimization by distributing heavily used pages evenly over all of memory, rather than having them compete for a small number of page frames. We can associate with each page frame a counter of the number of pages that are associated with that frame. Then, to replace a page, we search for the page frame with the smallest counter.
a. Define a page-replacement algorithm using this basic idea. Specifically address the problems of (1) what the initial value of the counters is, (2) when counters are increased,
(3) When counters are decreased, and (4) how the page to be replaced is selected. b. How many page faults occur for your algorithm for the following reference string, for four page frames?
1, 2, 3, 4, 5, 3, 4, 1, 6, 7, 8, 7, 8, 9, 7, 8, 9, 5, 4, 5, 4, 2
c. What is the minimum number of page faults for an optimal page-replacement strategy for the reference string in part b with four page frames?

Consider a demand-paging system with a paging disk that has an average access and transfer time of 20 milliseconds. Addresses are translated through a page table in main memory, with an access time of 1 microsecond per memory access. Thus, each memory reference through the page table takes two accesses. To improve this time, we have added an associative memory that reduces access time to one memory reference, if the page-table entry is in the associative memory. Assume that 80 percent of the accesses are in the associative memory and that, of the remaining, 10 percent (or 2 percent of the total) cause page faults. What is the effective memory access time?

Consider a demand-paged computer system where the degree of multiprogramming is currently fixed at four. The system was recently measured to determine utilization of CPU and the paging disk. The results are one of the following alternatives. For each case, what is happening? Can the degree of multiprogramming be increased to increase the CPU utilization? Is the paging helping?
a. CPU utilization 13 percent; disk utilization 97 percent
b. CPU utilization 87 percent; disk utilization 3 percent
c. CPU utilization 13 percent; disk utilization 3 percent

We have an operating system for a machine that uses base and limit registers, but we have modified the machine to provide a page table. Can the page tables be set up to simulate base and limit registers? How can they be, or why can they not be?

What is the cause of thrashing? How does the system detect thrashing? Once it detects thrashing, what can the system do to eliminate this problem?

What problems arise if the directory structure is a general graph?

What is garbage collection?

How can we protect files on a single-user system?

What might damage files?

List kinds of access we might want to limit on a multi user system.

List four ways systems might provide for users to protect their files against other users.

In the IBM/370, memory protection is provided through the use of keys. A key is a 4-bit quantity. Each 2K block of memory has a key (the storage key) associated with it? The CPU also has a key (the protection key) associated with it. A store operation is allowed only if both keys are equal, or if either is zero. Which of the following memory-management schemes could be used successfully with this hardware?
a. Bare machine
b. Single-user system
c. Multiprogramming with a fixed number of processes
d. Multiprogramming with a variable number of processes
e. Paging
f. Segmentation